Vector Quantization And Its Application To Image Processing

Vector quantization (VQ) is an efficient coding technique to quantize signal vectors due to its excellent rate-distortion performance. It has been widely used in signal and image processing, such as pattern recognition, speech, and image coding. The codebook designing method and encoding method play an important role in VQ and decide VQ performance. To obtain the better codebook and perform encoding, the heavy computations, which are called as the computing complexities of VQ, are required. The computing complexities of VQ increase with the increase of the dimension of vector. It becomes a serious barrier of VQ applied to the signal processing, especially in the real-time signal processing. How to reduce its computing complexities has become an important investigating field for decades of years. By using many nonlinear signal-processing methods to codebook design and a lot of fast searching methods to encoding, many VQ methods have been developed.In this thesis, the VQ in the field of image processing, as a field in which VQ is widely used, is investigated. By using the feature of image efficiently, we make some novel researches on the codebook design and fast encoding. The main results are as follows:1. Some existing initial codebook algorithms are investigated. A new initial codebook algorithm is proposed. In the proposed method, training vectors are sorted according to the norm or sum of training vectors. Then, the ordered vectors are partitioned into N groups where N is the size of codebook. The initial codewords are obtained from calculating the centroid of each group. It can be efficiently applied to smooth images.2. Some existing codebook designs are investigated in detail. Their shortages are carefully analyzed. The moderate principle is firstly proposed- Using this principle, the influence of nontypical training vectors on codeword is reduced or eliminated. Then each codeword becomes a representation of most typical training vectors in its cell. Using this principle, an additive condition for VQ optimization, which makes the sub-distortion of each cell close to each other, can be got. The improvements to existing algorithms, such as the frequency sensitive self-organizing feature maps (FSOFM) algorithm, and the frequency sensitive competitive learning (FSCL) algorithm, can be obtained. The realization of the two improved methods in wavelet domain is researched. Another improved method, which combined wavelet transform with the optimal Nonlinear Interpolative Vector Quantization (NLIVQ), is also researched. In a word, the moderate principle can be used to improve codebook and reduce computations.3. Some existing fast searching algorithms, which are based on the inequalities elimination and can achieve the same quality of encoded images as the full searching algorithm (FSA), are investigated in detail. By comparing the eliminating efficiency of each low dimensional feature of a vector (the sum, the variance, and the norm), three eliminating methods, which are the method based on subvector norm, the method based on vector sum and subvector norm, and the method based on subvector sum and variance, are proposed. Combined these eliminating inequalities with the partial distance elimination (PDE) method, the search efficiency can be further improved.4. By using the codebook based on equidistortion SOFM algorithm, the descriptors of color image in the content-based, image retrieval (CBIR) system are constructed by the index histogram of VQ-compressed index sequence. By using the fast searching method based on the eliminating inequality of subvector norm, a fast searching method in color image retrieval database is presented.