Several Compression Methods Of Graph And Image

With the rapid development of science techniques, and the acceleration of equipments up-dating, the data of images and graphs are increasing at a quick rate and the rate is far more than the increasing speed of the hard disk capacity. It does not meet our demand only depending on the development of hard disk capacity. So the compression methods of image and graph are always the research pots. In this dissertation, I propose an optimal truncation model for im-age compression, present two mesh parameterizations aiming to increasing the compressibility of geometry images and give a fast and efficient skew detection method for scanned document images. The main works include as follows:(1) An optimal truncation method for image compression. Image compression can be thought as the truncation to original image data. Compression performance is due to the se-lection of truncation points. The truncation problem can be transformed into an optimization problem with constrained conditions. According to different applications, the locations of op-timal truncation points are different. Two new goal functions according to special applications are presented, the optimal R-D curves can be customized and the optimal truncation points on the curves are found iteratively. The model can embed easily into other coding methods and continue the high effectiveness.(2) Mesh parameterizations for geometry images with high compressibility. We propose two mesh parameterizations aiming to increasing the compressibility of geometry images gen-erated from open meshes, direct manner and indirect manner. In direct manner, we firstly design a compressibility aware energy of the mesh by studying the relationship between the one-ring neighbors of mesh vertex and the4-neighbors of image point. Secondly, we solve the param-eterization by minimizing the energy defined as a weighted sum of the compressibility aware term and the conformal term. As a result, a geometry image with the low local linear error is constructed by uniformly resampling the parameterized mesh in its parameter domain. The novel idea of indirect manner is that we use an indirect way to construct a resulting parameter domain according to a desired geometry image with the low local linear error. We first move image pixels according to the current parameter domain to decrease the local linear error. Then we formulate a relationship between the moved image pixels and the current parameter domain. Finally, we use the relationship to update the parameter domain by redistributing the image pix-els to their original positions. Meanwhile, a feature-preserving scheme is introduced to assist the accurate reconstruction of mesh features.(3) A skew detection method for document images. A document image can be regarded as an image with periodic texture according to text line ordered by rows or columns. Fourier transform is a particularly useful tool for analyzing periodic texture. The peaks in the power spectrum are always the result of corresponding periodic structures in the spatial image, whose value and location reveal the periodicity and orientation. By the aid of power spectrum, two fast skew detection methods are presented for document images without any iteration. Because the rounding error is difficult to be eliminated, the initial angle is a detected angle with coarse accuracy. With a fast converging method being introduced, a fast and efficient skew detection method is presented in this dissertation.