Vector Quantization Encoding Algorithm And Applied Research

In the fields such as spaceflight, military affairs, weather, medicine and multimedia, a large number of still images and videos are often required to be stored and transmitted. To improve the transmission efficiency and reduce the storage requirement, efficient encoding algorithms should be used to remove the residual information in images, and fewer bits should be used to describe images on restrictions of given distortion. Vector quantization(VQ) is an efficient lossy compression technique, whose prominent virtues are high compression ratio and simple decoding process, so it has become one of important compression techniques for image coding. VQ compression technique has broad applicable fields, such as compression and real-time transmission of satellite-sensed or plane-sensed images for military or weather departments, storage and transmission of radar images and military maps, video compression for digital television and DVD, compression and storage of medical images, compression and transmission of network-based test data, speech coding, image recognition and speech recognition, and so on. The research on VQ involves lots of theories and techniques from various academic subjects, and has significance for academic, economic and national defence from angles of theory and application. VQ technology is based on Shannon's rate-distortion theory. VQ finds the nearest codeword for each input vector and transmits the corresponding index to the decoder, thus in the decoding phase merely a simple table-look-up operation is required. This dissertation systematically summarizes the 20-year-development course, current status and future development trend of VQ technology. In the application background of still image encoding, this dissertation investigates three key techniques of basic VQ, i.e., codebook design, codeword search and codeword index assignment. On the one hand, some modified algorithms are presented after analyzing the virtues and shortcomings of existing algorithms. On the other hand, some novel methods are proposed by combining VQ with other technology and theories. Moreover, a new application of VQ, i.e., digital image watermarking, has been exploited in this dissertation. Main innovative contributions are as follows: Conventional genetic codebook design methods adopt the codebook-based solution description and use LBG in each iteration, so they need huge computation. In order to release the load, a genetic codebook design method based on the partition of the training set is proposed, which doesn't require LBG in each iteration. To further improve the codebook performance, a genetic simulated annealing codebook design method is also presented, in which the simulated annealing is combined with genetic algorithms. Test results show that, compared with the LBG algorithm, the proposed two algorithms can reduce the computation time as well as improve the codebook performance. To improve the local search ability of Tabu search approach and improve the ability of finding the global optimal codebook, the simulated annealing mechanism is applied in Tabu search algorithm. Moreover, Tabu search approach is used to solve the hard problem of searching the optimal partitioning superplane in the conventional maximum decent codebook design method. In addition, Tabu search approach is also used in the fuzzy c-means algorithm to improve the codebook performance. Simulation shows that the proposed three algorithms can significantly improve the codebook performance. Based on the mean-variance inequality, by decomposing each vector into two subvectors, an efficient subvector mean-variance codeword elimination criterion is presented. Both theoretical analysis and simulation show that this criterion can eliminate a larger number of codewords. In addition, To release the storage load of triangle inequality elimination method, this dissertation develops an efficient codeword elimination criterion by combining the triangle inequality with the mean inequality. Finally, according to the mean-variance inequality, this dissertation introduces variance pyramids in the mean pyramid codeword search algorithm to improve the codeword search efficiency. By utilizing the virtues of the Hardamard transform, i.e., no multiplication requirement and satisfactory energy compaction, an efficient Hardamard transform based codeword search algorithm is presented. Test results show that the proposed algorithm is more efficient than the wavelet transform based codeword search algorithm. To the question of the underuse of the search range and sequence in traditional codeword search algorithms, four characteristic values are introduced in the proposed algorithm with adaptive search range and sequence. Test results showthat the proposed algorithm can significantly improve the search efficiency with a little extra distortion. To the shortcoming of fixed bit rate of the full search algorithm, two variable rate codeword search algorithms are presented. In the first algorithm, based on the correlation vector quantization, the diagonal encoding sequence is adopted and the high correlation between neighboring image blocks is considered, so both the computation time and the bit rate are reduced. By combining the correlation VQ technique and the side-match VQ algorithm, a variable side-match VQ algorithm is also presented. Test results show that, compared with the side-match VQ, the proposed algorithm can obtain lower bit rate, less computation time and higher performance. To reduce the channel distortion caused by the transmission of codeword indices in the noisy channel, a modified Tabu search codeword index assignment algorithm with simulated annealing is presented. On the condition of BPSK modulate style, a Tabu energy allocation codeword index transmission algorithm is presented, in which the conventional energy allocation method is combined with the Tabu search algorithm. Simulation results show that the proposed two algorithms can reduce much channel distortion. To the status that nobody pay attention to the robustness of digital watermarking algorithm against the VQ compression, a general framework of VQ based digital image watermarking algorithm is presented,and two efficient algorithms, i.e., public watermarking and private watermarking algorithms, are also presented. Codebook partition concepts are introduced in the proposed algorithms to solve the watermarking embedding problem of VQ based digital watermarking. In the public watermarking algorithm, a simple and efficient codebook expansion technique is introduced to meet the requirements of the watermark extraction without the original image. Test results show that the proposed two algorithms are efficient and secret, and have enough robustness to the VQ compression.