基于树结构矢量量化码书的快速搜索算法

针对树结构矢量量化存在所选码字不一定是最佳匹配码字的问题,提出一种快速搜索算法,可以准确地找到输入矢量的最佳匹配码字.该方法利用了三角不等式作为继续搜索与停止搜索的依据,可以快速排除不可能节点,保留可能节点.实验结果表明,用该方法恢复的图像质量要好于双路搜索方法恢复的图像.     

Fast closest codeword search algorithms for vector quantisation

One of the most serious problems for vector quantisation is the high computational complexity of searching for the closest codeword in the codebook design and encoding phases. The authors present a fast algorithm to search for the closest codeword. The proposed algorithm uses two significant features of a vector, mean value and variance, to reject many unlikely codewords and saves a great deal of computation time. Since the proposed algorithm rejects those codewords that are impossible to be the closest codeword, this algorithm introduces no extra distortion than conventional full search method. The results obtained confirm the effectiveness of the proposed algorithm     

一种基于不等式的矢量量化快速码字搜索算法

传统矢量量化编码算法码字搜索范围较大,编码时间较长.文章提出一种基于不等式的矢量量化快速码字搜索算法.该算法将方差不等式和三角不等式引入范数排序算法(NOS),有效减小了码字搜索范围.实验结果表明,重构图像峰值信噪比(PSNR)相同时,该算法编码时间较低.     

基于FPGA的EBNNS矢量量化码字搜索算法的电路设计

等和值块扩展最近邻搜索算法(EBNNS)是一种快速矢量量化码字搜索算法,该算法首先将码书按和值大小排序分块,编码时查找与输入矢量和值距离最近的码书块中间码字,并将它作为初始匹配码字.然后在该码字附近上下扩展搜索相邻码字中距输入矢量最近的码字,最后将搜索到的最匹配码字在码书中的地址输出.同时本文对该算法进行了FPGA设计.设计时采用串并结合和流水线结构,折中考虑了硬件面积和速度.结果表明针对所用FPGA器件Xilinx xc2v1000,整个系统最大时钟频率可达88.36MHz,图像处理速度约为2.2 MPixel/s.     

哈德码变换域等均值等方差最近邻矢量量化码字搜索算法

本文提出一种基于哈德码变换的等均值等方差最近邻(HTEENNS)快速矢量量化码字搜索算法.在编码前,该算法预先计算每个码字的哈德码变换,然后根据各码字哈德码变换的第一维系数大小的升序排列对码字进行排序.在编码过程中,首先计算输入矢量的哈德码变换和方差,然后选取与输入矢量哈德码变换的第一维系数最近的码字作为初始匹配码字,然后利用两条有效的删除准则在该码字附近进行上下搜索与输入矢量最近的码字.测试结果表明,本文算法比等均值最近邻搜索算法(ENNS)、等均值等方差最近邻搜索(EENNS)算法和哈德码变换域部分失真搜索算法等算法有效得多.     

等均值等范数最近邻矢量量化码字搜索算法

本文提出了一种等均值等范数最近邻(EENNS)矢量量化码字搜索算法.在编码前,该算法预先计算每个码字的均值和范数,然后根据均值大小的升序排列对码字进行排序.在编码过程中,首先选取与输入矢量均值最近的码字作为初始匹配码字,然后利用两条有效的删除准则在该码字附近进行上下搜索与输入矢量最近的码字.测试结果表明,本文算法比等均值最近邻搜索算法(ENNS)和最近提出的范数排序搜索(NOS)算法有效得多.     

基于自适应搜索范围及顺序的快速矢量量化编码算法

本文提出了一种新颖的快速矢量量化编码算法.该算法在编码前预先计算每个码字的四个特征量,然后根据各特征量的升序排列分别对码字进行排序以生成四个排序码书.在编码过程中,对于不同的输入矢量,自适应产生不同的动态码字搜索范围及顺序而排除大部分码字.测试结果表明,本文算法只需搜索3%到8%码字而获得与穷尽搜索算法相近的编码质量,实际编码时间减少约93%.     

Two fast nearest neighbor searching algorithms for image vectorquantization

In this paper, two efficient codebook searching algorithms for vector quantization (VQ) are presented. The first fast search algorithm utilizes the compactness property of signal energy on transform domain and the geometrical relations between the input vector and every codevector to eliminate those codevectors that have no chance to be the closest codeword of the input vector. It achieves a full search equivalent performance. As compared with other fast methods of the same kind, this algorithm requires the fewest multiplications and the least total times of distortion measurements. Then, a suboptimal searching method, which sacrifices the reconstructed signal quality to speed up the search of nearest neighbor, is presented. This algorithm performs the search process on predefined small subcodebooks instead of the whole codebook for the closest codevector. Experimental results show that this method not only needs less CPU time to encode an image but also encounters less loss of reconstructed signal quality than tree-structured VQ does     

基于特征值排序的部分失真快速码字搜索算法

提出了一种矢量量化快速码字搜索算法．该算法在编码前预先计算每个码字的特征值并按顺序排列；在编码时，根据每个输入矢量的特征值来确定码字搜索顺序。同时限定相应的搜索范围及利用有效的码字删除准则，从而大大提高了编码速度．实验表明，该算法只需要穷尽算法2％-4％的编码时间就可以获得与之较为接近的编码质量，编码速度与ASRSS算法及MEENNS算法相比也有明显提高。     

An efficient encoding algorithm for vector quantization based on subvector technique

In this paper, a new and fast encoding algorithm for vector quantization is presented. This algorithm makes full use of two characteristics of a vector: the sum and the variance. A vector is separated into two subvectors: one is composed of the first half of vector components and the other consists of the remaining vector components. Three inequalities based on the sums and variances of a vector and its two subvectors components are introduced to reject those codewords that are impossible to be the nearest codeword, thereby saving a great deal of computational time, while introducing no extra distortion compared to the conventional full search algorithm. The simulation results show that the proposed algorithm is faster than the equal-average nearest neighbor search (ENNS), the improved ENNS, the equal-average equal-variance nearest neighbor search (EENNS) and the improved EENNS algorithms. Comparing with the improved EENNS algorithm, the proposed algorithm reduces the computational time and the number of distortion calculations by 2.4% to 6% and 20.5% to 26.8%, respectively. The average improvements of the computational time and the number of distortion calculations are 4% and 24.6% for the codebook sizes of 128 to 1024, respectively.     

Variable-branch tree-structured vector quantization

Tree-structured vector quantizers (TSVQ) and their variants have recently been proposed. All trees used are fixed M-ary tree structured, such that the training samples in each node must be artificially divided into a fixed number of clusters. This paper proposes a variable-branch tree-structured vector quantizer (VBTSVQ) based on a genetic algorithm, which searches for the number of child nodes of each splitting node for optimal coding in VBTSVQ. Moreover, one disadvantage of TSVQ is that the searched codeword usually differs from the full searched codeword. Briefly, the searched codeword in TSVQ sometimes is not the closest codeword to the input vector. This paper proposes the multiclassification encoding method to select many classified components to represent each cluster, and the codeword encoded in the VBTSVQ is usually the same as that of the full search. VBTSVQ outperforms other TSVQs in the experiments presented here.     

快速最近邻矢量量化码字搜索算法

本文综述了各种快速最近邻矢量量化码字搜索算法,按照算法的特点对各种快速算法进行了归类,对各种算法的编码时间、平均失真计算次数、额外存储量和离线计算量进行了仿真、比较和分析,并提出作者的一些改进算法或改进思路.     

A Fast Encoding Algorithm for Vector Quantization Using Difference Pyramid Structure

This paper proposed a fast vector quantization encoding algorithm called difference pyramid search (DPS). According to the formation of the difference pyramid and partial distortion elimination, a rejection test inequality is derived to progressively reject a lot of nonclosest code words as early as possible. Experimental results show that the proposed DPS algorithm outperforms other pyramid-based fast search algorithms, including mean pyramid search, L2-norm pyramid search, and mean-variance pyramid search.     

Efficient search algorithm for fast encoding of images using vectorquantisation

A fast algorithm for image coding using vector quantisation which exploits the spatial redundancies in the image is proposed. The algorithm speeds up the codeword search phase required for nearest neighbour encoding, by utilising the high amount of intravector and intervector correlations. A novel prediction mechanism is used to exploit the intervector correlations and a mean pyramid representation is used for exploiting the intravector correlations. The prediction mechanism also enables a further reduction in bit rate compared to ordinary vector quantisation. Simulation results show the effectiveness of the proposed method     

Fast search algorithms for vector quantization of images usingmultiple triangle inequalities and wavelet transform

The encoding of vector quantization (VQ) needs expensive computation for searching the closest codevector to the input vector. This paper presents several fast encoding algorithms based on multiple triangle inequalities and wavelet transform to overcome this problem. The multiple triangle inequalities confine a search range using the intersection of search areas generated from several control vectors. A systematic way for designing the control vectors is also presented. The wavelet transform combined with the partial distance elimination is used to reduce the computational complexity of the distance calculation of vectors. The proposed algorithms provide the same coding quality as the full search method. The experimental results indicate that the new algorithms perform more efficiently than existing algorithms.     

A lattice vector quantization using a geometric decomposition

An efficient lattice vector quantization design and the associated fast coding algorithm are proposed for high-bit-rate, high-quality data compression applications. The codewords are uniformly distributed and densely packed as 2ⁿ-dimensional lattice points, based on a geometric lattice decomposition technique. The maximum quantization error has been chosen as the design criterion. For high-rate applications, it has the following advantages: (1) simple vector codeword generation; (2) no codewords need to be stored and only predetermined rules are used at encoder and decoder ends; (3) highly regular code structure, so that encoding is done via an inverse tree-search suitable for fast parallel processing, and decoding is done similar to a scalar quantizer; (4) high coding quality capability, viz. the maximum quantization distortion can be prespecified to a desired value and the entire hyper-region is covered uniformly; and (5) dimensionality saving can be easily predicted and it can be achieved using fixed-length codes     

Peano scanning based fast encoding algorithm for vectorquantisation

An effective method for encoding image-input blocks in vector quantisation (VQ) is proposed. For each codeword in the codebook, a group of Peano scannings of selected feature vectors is computed. Each Peano scanning acts as a transform from a higher dimension to one dimension, while preserving neighbourhood adjacency. An ordered list of the Peano scannings and their link to the codebook is stored. Coding is conducted by restricting the search to two windows of codewords with the closest Peano scannings to that of the input block. Each window centre is found in logarithmic time proportional to the codebook size. The number of codewords to be searched is fixed, and is determined by some additional distortion that is acceptable over exhaustive search methods. Coded images show no significant degradation, while maintaining considerable constant search-time savings over exhaustive search methods. The algorithm can be used with other fast full-search equivalent methods, and can use savings from other methods in searching within the windows as well     

Fast codeword search algorithm for real-time codebook generation inadaptive VQ

Adaptive vector quantisation is used in image sequence coding where the code-book is updated continuously to keep track with the changing source statistics. Hence, for real-time video coding applications, both the processes of quantising the input vectors and updating the codebook are required to be fast. Since the nearest codeword search is involved in both these processes, a fast codeword search algorithm can make the coding process time efficient. The authors describe a proposed codeword search algorithm with reduced search space. The algorithm uses the mean value and the sum of the absolute differences as the two criteria to reject unlikely codewords, thereby saving a great deal of computational time, while introducing no more distortion than the conventional full search algorithm. Simulation results obtained confirm the effectiveness of the proposed algorithm in terms of computational complexity     

一种基于并行结构的快速VQ编码算法

为提高编码速度，本文提出了一种新的快速矢量量化编码搜索算法。文中首先讨论了码书矢量平均值与失真测度之间的变化关系，并根据其结果提出基本的四分法均值排序搜索算法；然后结合并行硬件的优点，提出一种基于并行结构的四分法均值排序搜索VQ编码算法。测试结果表明，与传统的完全搜索算法及部分快速搜索算法相比，本文算法大大减少了编码时间。     

Fast planar-oriented ripple search algorithm for hyperspace VQ codebook.

This paper presents a fast codebook search method for improving the quantization complexity of full-search vector quantization (VQ). The proposed method is built on the planar Voronoi diagram to label a ripple search domain. Then, the appropriate codeword can easily be found just by searching the local region instead of global exploration. In order to take a step further and obtain the close result full-search VQ would, we equip the proposed method with a duplication mechanism that helps to bring down the possible quantizing distortion to its lowest level. According to the experimental results, the proposed method is indeed capable of providing better outcome at a faster quantization speed than the existing partial-search methods. Moreover, the proposed method only requires a little extra storage for duplication.