【作者】 庞朝阳；

【导师】 孙世新；

【作者基本信息】 电子科技大学 ， 计算机应用， 2002， 博士

【摘要】 由于向量量化(Vector Quantization，简称VQ)的压缩比高、失真小，因此它被认为是很有希望的编码方法。码书、搜索器、索引器是向量量化的三个组成部分，向量量化系统由VQ编码器和解码器构成，而解码器只是实现查表操作，所以向量量化器设计的关键内容是VQ编码器中的码书和搜索器设计。其中码书的设计最为关键，它直接影响量化器的性能、编码效率及其实现复杂度。向量量化的两大公认主要问题是码书、搜索器的设计算法。在向量量化中，如何提高处理机速度是比较重要的，因为向量量化的搜索器和码书设计都需要快速处理。并行处理技术是一种提高处理速度的重要方法。该论文工作集中，主要围绕向量量化两大公认主要问题展开。针对这两大主要问题，逐一进行了相关的理论分析，然后根据自己的理论提出了若干串行算法，并且对相应的并行算法作了一定程度的探讨和实验。 具体工作如下： ● 对向量量化的理论分析、证明： 1) 证明了以著名的LBG算法为代表的一般码书训练算法在迭代过程中，各区域序列对应的熵序列收敛。该论文用典型的测试图象Lena、Barbara进行实验，验证了熵收敛规律的正确性。 2) LBG算法代表了码书训练算法的基本思想，目前许多算法都是基于它的，但关于它的理论分析文献不是太多。该论文从理论上分析、证明了LBG算法迭代过程中失真序列分区域收敛特性，并从实验上验证了该特性。 3) 证明了LBG算法作用在以同一有限维线性空间为基础的范数不同的Banach空间上时，只要初始码书相同，则产生相同码书。我们用典型的测试图象Lena进行实验，验证了该结论的正确性。从而在研究LBG算法性能时，我们只需选择最容易研究的Banach空间作研究对象。另外，选择计算量较小的范数，在一定条件下，会减少码书训练时间。 4) 证明了以LBG算法为代表的一般码书训练算法在迭代过程中，各区域序列对应的质心序列收敛。 ● 针对码书设计的算法研究： 5) 以LBG算法为代表的传统的码书训练算法基本上都用量化失真序列收敛作算法停止条件。本文提出了一种简单、快速的新算法。它的基本思想是，不必计算量化失真，直接用区域序列对应的熵序列收敛作停止条件。该算法与经典的LBG算法相比，结构更简单、速度更快、更容易理解。我们用典型的测试图象Lena、Barb做实验。实验结果表明，该算法与著名的LBG算法的PSNR相差小于0.1dB，但它的运行速度比LBG快2倍以上。 6) 以LBG算法为代表的码书训练算法的研究在向量量化技术中比较重要，其中快速算法的研究近十年来倍受关注。本文提出了与不同的快速算法LC。它是基于LBG的，其基本思想是尽早删除迭代过程中已趋稳定的区域，大幅度减少计算的冗余量。它与LBG算法相比，结构简单、速度快。用典型的测试图像Lena和Barbara做实验， 电子科技大学博士论文 表明LC算法峰值信噪比只比LBG算法少2％左右，但运行速度是LBG 的4．61～13．6倍。在比特率为0．375 bit／Pixel条件下，LC算法 与LBG算法的重建图像质量无明显差别。 7）利用LBG算法迭代过程中质心序列收敛特性，提出了一种快速算法。 它的基本思想是，直接去掉LBG算法中量化失真计算，用质心序列收 敛作停止条件。我们用典型的测试图象Lena、Barb做实验。实验结 果表明，该算法与著名的LBG算法的PSNR相差小于0．ldB 但它的 运行时间至少比LBG的运行时间少一半。 8）利用范数等价性和 LBG算法迭代过程中数据是分区域收敛性质，提出 新的码书训练算法FLC。该方法用计算量小的范数进行距离计算和尽 早删除聚类过程中己趋稳定的区域，从而速度非常快。我们用典型的 测试图象Lena和Barb做实验，表明FLC算法以峰值信噪比只比LBG 算法少0．25～0．43dB为代价，把运行时间缩短为LBG的1／3．74～ 1月．59。从失真、运行时间、算法结构是否简单、普遍适用性角度考 虑，与文中六类算法相比，它是综合性能最好的算法。 9）以LBG算法为代表的传统的码书训练算法基本上都用量化失真序列 收敛作算法停止条件。本文提出了一种简单、快速的新算法。它的基 本思想是，不必计算量化失真，直接用区域序列中各区域的元素个数 所成序列收敛作停止条件。该算法与经典的LBG算法相比，结构更简 单、速度更快、更容易理解和控制。我们用典型的测试图象Lena、 Barb做实验。实验结果表明，该算法与著名的LBG算法的PSNR相差 小于 0．ldB 但它的运行速度比 LBG快 2倍以上。 ．关于向量量化的搜索器的算法研究： 10）针对高维度量空间，该论文提出的一个时间复杂性度为 O（IOg。N〕快 速搜索算法。并且从理论上完整地论证了该算法（算法正确性、空间 复杂性、时间复杂性），然后再用实验验证。搜索器的设计是向量量 化另一个重要研?更多还原

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