陆哲明
论文题目：矢量量化编码算法及应用研究
作者简介：陆哲明，男，1974年06月出生，1997年09月师从于哈尔滨工业大学孙圣和教授，于2001年04月获博士学位。
摘 要
在航天、军事、气象、医学、多媒体等领域中经常需要大量存储和传输各种静态图像和视频图像。为了提高传输效率和减少存储空间，必须采取有效的压缩编码算法消除图像中所包含的各种冗余信息并在给定的失真条件下使用尽量少的比特数来描述图像。矢量量化(VQ)作为一种有效的有损压缩技术，其突出优点是压缩比大以及解码算法简单，因此它已经成为图像压缩编码的重要技术之一。矢量量化压缩技术的应用领域非常广阔，如军事部门和气象部门的卫星(或航天飞机)遥感照片的压缩编码和实时传输、雷达图像和军用地图的存储与传输、数字电视和DVD的视频压缩、医学图像的压缩与存储、网络化测试数据的压缩和传输、语音编码、图像识别和语音识别等等。矢量量化技术的研究涉及多学科领域的理论和技术，无论从理论角度还是从应用角度来看，开展对矢量量化技术的研究，不但具有重要的学术意义，还有极为重要的国防意义和经济意义。
矢量量化的理论基础是香农的速率失真理论，其基本原理是用码书中与输入矢量最匹配的码字的索引代替输入矢量进行传输和存储，而解码时只需简单的查表操作。本文系统地综述了矢量量化技术理论在近二十年来的发展历程、目前的研究现状和未来的发展趋势。本文在静态图像压缩编码的应用背景下，重点研究基本矢量量化的三大关键技术，即码书设计、码字搜索和码字索引分配。一方面，分析现存的各种算法的优缺点，提出各种改进算法。另一方面，结合其它领域的技术和理论，提出各种新颖的算法，并开辟矢量量化技术的新应用方向——数字水印处理。本论文的主要创新成果如下所述：
传统的遗传码书设计算法采用基于码书的解描述方案并在每次迭代中融入传统的码书设计算法(LBG)，所以计算量非常大。为了减少计算量，本文提出基于训练矢量划分的遗传码书设计算法，该算法在每次迭代中不需要融入LBG算法；为进一步提高码书性能，本文把遗传码书设计算法和传统的模拟退火算法相结合，提出遗传退火码书设计算法。仿真实验表明，与LBG算法相比，这两种算法不仅大大降低了码书设计时间而且显著提高了码书性能。为了改善禁止搜索算法的局部搜索能力以提高搜索全局最优码书的能力，本文在禁止搜索算法中融入模拟退火机制，提出改进的禁止搜索码书设计算法。其次，利用禁止搜索技术，解决了传统的最大下降码书设计算法的最优分割超平面的搜索问题。最后，本文把禁止搜索算法应用到模糊c均值算法中。
仿真实验表明，这三种算法能明显改善码书性能。
在均值-方差不等式的基础上，通过将矢量分解为两个子矢量，推导出子矢量均值方差不等式删除准则，理论分析和仿真实验表明该准则能够排除大量的不匹配码字，提高码字搜索效率。另外，针对三角不等式删除准则的额外存储量大的缺点，本文通过结合均值不等式，推导出一条强有力的删除准则，大大缓解了额外存储量的负担并提高了算法效率。最后，在均值金字塔的基础上，本文根据均值方差不等式引入方差金字塔，提出均值-方差金字塔快速码字搜索算法，大大提高了码字搜索效率。本文利用哈德码变换的能量集中特性和不需要乘法运算的优点，提出哈德码变换域快速码字搜索算法，实验表明该算法比小波变换域码字搜索算法的效率高。针对传统码字搜索不注重搜索范围和顺序的缺点，本文通过引入四个特征值，提出自适应搜索范围及顺序的快速码字搜索算法，实验表明在引入少量额外失真的条件下该算法可以大大提高码字搜索效率。针对穷尽搜索算法比特率固定的缺点，提出两种变比特率码字搜索算法。首先，在相关矢量量化编码算法基础上，采用对角编码顺序，充分考虑图像块间的相关性，减少了编码时间并降低了比特率。另外，通过结合相关矢量量化编码技术和边缘匹配矢量量化算法，提出变比特率的边缘匹配矢量量化编码算法，仿真结果表明该算法比基本的边缘匹配矢量量化编码算法的比特率低，编码速度快，编码质量高。
为了降低码字索引在噪声信道中传输时所引起的信道失真，本文在禁止搜索中融入模拟退火机制，提出禁止模拟退火码字索引分配算法。在数字信号采用BPSK方式进行调制的情况下，本文将能量分配算法与禁止搜索算法相结合，提出禁止能量分配码字索引传输算法。仿真实验表明这两种算法能够有效地降低信道失真。
针对当前热门的版权保护技术——数字水印处理技术对于抗矢量量化压缩的稳健性无人问津的情况，提出基于矢量量化的数字图像水印处理基本框架，并提出两种有效的数字水印处理算法：私有水印算法和公有水印算法。在两种算法中引入码书划分的概念，有效地解决了矢量量化水印嵌入问题。在公有水印算法中引入简单有效的码书扩展技术，实现了公有水印算法在抽取过程中不需要原始图像参与的要求。仿真结果表明这两种算法都是隐秘的和有效的，并对VQ压缩具备足够的稳健性。
关键词 矢量量化；码书设计；码字搜索；码字索引分配；数字水印处理
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 show that 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.
Key words Vector Quantization; Codebook Design;
Codeword Search; Codeword Index Assignment; Digital Watermarking
