矢量量化编码算法及应用研究

【作者】 陆哲明；

【导师】 孙圣和；

【作者基本信息】 哈尔滨工业大学 ， 2001， 博士

【摘要】 在航天、军事、气象、医学、多媒体等领域中经常需要大量存储和传输各种静态图像和视频图像。为了提高传输效率和减少存储空间,必须采取有效的压缩编码算法消除图像中所包含的各种冗余信息并在给定的失真条件下使用尽量少的比特数来描述图像。矢量量化(VQ)作为一种有效的有损压缩技术,其突出优点是压缩比大以及解码算法简单,因此它已经成为图像压缩编码的重要技术之一。矢量量化压缩技术的应用领域非常广阔,如军事部门和气象部门的卫星(或航天飞机)遥感照片的压缩编码和实时传输、雷达图像和军用地图的存储与传输、数字电视和DVD的视频压缩、医学图像的压缩与存储、网络化测试数据的压缩和传输、语音编码、图像识别和语音识别等等。矢量量化技术的研究涉及多学科领域的理论和技术,无论从理论角度还是从应用角度来看,开展对矢量量化技术的研究,不但具有重要的学术意义,还有极为重要的国防意义和经济意义。矢量量化的理论基础是香农的速率失真理论,其基本原理是用码书中与输入矢量最匹配的码字的索引代替输入矢量进行传输和存储,而解码时只需简单的查表操作。本文系统地综述了矢量量化技术理论在近二十年来的发展历程、目前的研究现状和未来的发展趋势。本文在静态图像压缩编码的应用背景下,重点研究基本矢量量化的三大关键技术,即码书设计、码字搜索和码字索引分配。一方面,分析现存的各种算法的优缺点,提出各种改进算法。另一方面,结合其它领域的技术和理论,提出各种新颖的算法,并开辟矢量量化技术的新应用方向——数字水印处理。本论文的主要创新成果如下所述: 传统的遗传码书设计算法采用基于码书的解描述方案并在每次迭代中融入传统的码书设计算法(LBG),所以计算量非常大。为了减少计算量,本文提出基于训练矢量划分的遗传码书设计算法,该算法在每次迭代中不需要融入LBG算法; 为进一步提高码书性能,本文把遗传码书设计算法和传统的模拟退火算法相结合,提出遗传退火码书设计算法。仿真实验表明,与LBG算法相比,这两种算法不仅大大降低了码书设计时间而且显著提高了码书性能。为了改善禁止搜索算法的局部搜索能力以提高搜索全局最优码书的能力,本文在禁止搜索算法中融入模拟退火机制,提出改进的禁止搜索码书设计算法。其次,利用禁止搜索技术,解决了传统的最大下降码书设计算法的最优分割更多还原

【Abstract】 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.更多还原