Vector Quantization And Image Compression--The Analysis Of Theory, The Design Of Algorithm, Application And Implementation

Vector Quantization is regarded as a hopeful method because high compression ratio and small distortion. The main components of VQ are codebook, encoder and decoder. The algorithms about training codebook and designing encoder are the two main problems because its decoder is very simple. The key of the VQ is the codebook because its codebook decides its performance. How to design the fast algorithm is the main research topic. The dissertation analyses some properties of VQ and presents some serial algorithm and parallel algorithm for the two main problems. The author's main research topics are listed following. The Analysis of Theory :1) The author proofs that the entropy sequence of each region sequence is convergent in the general codebook generation algorithms such as LEG algorithm The correctness of the convergence regularity is tested by the typical test image Lena and Barb.2) The local clustering property is proofed and tested in the dissertation.3) The property that the same codebook is generated over different Banach Space is proofed and tested in the dissertation.4) The property that the centroid sequence is converging is proofed and tested in the dissertation. Training Algorithm Researching:5) According to 1, a new training algorithm is presented. The experiment shows that the PSNR difference between the new algorithm and LBG is less than 0.15dB, but the running time of it is at most one second of the LBG algorithm.6) According to 2, a new training algorithm is presented. The experiment shows that the PSNR difference between the new algorithm and LBG is less than 2%, but the running time of it is about 1/4.61-1/13.6 factor of the LBG algorithm.7) According to 4, a new training algorithm is presented. The experiment shows that the PSNR difference between the new algorithm and LBG is less than 0.15dB, but the running time of it is at most one second of the LBG algorithm.8) According to 2 and 3, a new training algorithm is presented. The experiment shows that the PSNR difference between the new algorithm and LBG is less than 2%, but the running time of it is about 1/3.741-1/9.59 factor of the LBG algorithm.9) The traditional codebook generation methods such as LBG algorithm use the convergence of distortion sequence as the condition of the end of algorithms. A simple and fast Codebook generation algorithm by the property of the convergence of the size of region is presented in this dissertation. Compared with LBG algorithm, it is simple, fast and easy to be comprehended and controlled. The author tests the performance of thealgorithm by typical test image Lena and Barb. The result shows that the PSNR difference between the algorithm and LBG is 0.1 dB, but the running time of it is at most one second of LBG. The Design of Encoder:10) The searching problem over a k-dimensional space is defined as follows. Given a metric space S and a finite subset T, for an arbitrary element x that belongs to S, a fast search algorithm is needed to find an element y that belongs to T such that the distance between x and y is not larger than a preparative real number. To resolve the problem, the author presented a universal fast search algorithm done by which the average number ofelements to be searched is not larger than 0(log2 | T |). Moreover, thealgorithm can be applied to resolve the fast encoding problem of vector quantization in data compression. The proposed algorithm has the same time complexity with lattice VQ and tree-structure VQ approximately. However, compared with the lattice VQ, it does not depend on many constrained conditions, and compared with tree-structure VQ, the criterion of minimum distortion can be guaranteed by performing it. The Design of Parallel Algorithm11) Design the parallel algorithms according the serial algorithm is this dissertation. The experiment shows that the efficiency of encoding can be up to 70% approximately.