快速码字搜索算法中一维特征量的最佳选择方法

矢量量化编码过程中的最近邻码字搜索需要进行大量的矢量间距离的计算,这个过程的计算复杂度极高,严重限制了其实际使用.为了加速矢量量化的编码过程,许多文献提出了各种不同组合的基于均值、2-范数、方差和角度的矢量一维特征量的快速最近邻矢量量化码字搜索算法.通过实验给出了这四个一维特征量单独使用以及相互组合的所有情况下各算法的搜索范围和编码时间,并对它们进行了比较和分析,进而提出了在实际进行编码时如何最优地进行一维特征量选取的准则.     

基于改进的参考矢量选取的码字快速搜索算法

矢量量化的编码过程计算复杂性极高,为了减少编码时大量的矢量间距离计算,许多文献提出利用不等式关系以较少的计算量来估算距离的方法。在Chang等人提出的利用双限制三角不等式的快速搜索算法基础上,通过改进参考矢量的选取方法,有效提高了码字搜索的效率。实验结果表明,改进算法的码字排除率可以提高3.735%9.976%,编码时间可以减少6.03%35.25%。     

码书排序对快速码字搜索算法性能影响的分析

矢量量化快速码字搜索算法中,为了有效地减小搜索范围,必须对原始码书按一定的准则进行重新排序。对现存的两类快速码字搜索算法进行了总结,其中一类是码书按1维顺序关系排序,另一类是码书按2维相邻关系排序。通过实验给出了两类算法的搜索范围和编码时间,并进行了比较和分析,进而提出了在实际编码时如何更好地使用这两种排序关系的准则。     

一种快速的矢量量化编码

研究了一种基于均方误差（MSE）测度的矢量量化快速编码算法。算法利用小波变换的特点,合理地构造矢量,便于非线性插补矢量量化技术的使用,也使部分失真排除法的效率大大提高。使用矢量的二范数和距离测度关系的码字排除方法,再结合非线性插补矢量量化技术和部分失真排除法,在搜索编码过程中,有效排除部分候选码字。实验结果表明,相对于穷尽搜索方法,计算量有明显降低,计算时间显著减少。     

一种新颖的基于哈德码变换的码字搜索算法

针对图像矢量量化编码的复杂性,提出了一种新颖的快速最近邻码字搜索算法。该算法首先计算出每个码字和输入矢量的哈德码变换,然后为输入矢量选取范数距离最近的初始匹配码字,利用多控制点的三角不等式和两条有效的码字排除准则,把不匹配的码字排除,最后选取与输入矢量最匹配的码字。实验结果表明,新算法相比于其他算法,在保证编码质量的前提下,码字搜索时间和计算量均有了明显降低。     

一种改进的AEI算法中初始匹配码字的快速查找方法

矢量量化（VQ）是一种高效的有损压缩技术。快速码字搜索算法是矢量量化的核心问题之一,其性能决定了编码时间。快速码字搜索算法中,绝对误差不等式删除算法(AEI)是一种典型的3步算法,其第1步查找输入矢量的初始匹配码字的方法采用了Minimax法,是整个AEI算法中计算量最大的步骤,严重影响了算法的效率。针对这个问题,提出了一种新的查找初始匹配码字的方法——Partial Minimax法。该方法在保证所找到的初始匹配码字与原始AEI算法相同并且重建图像的PSNR（峰值信噪比）值不变的前提下,可显著减小这一步骤的计算量和查找时间,从而有效地提高了算法的总体编码速度。     

基于主分量分析的相关矢量量化编码算法

在编码前,首先计算码书中所有码字在主轴上的投影值,然后按照这些投影值从小到大对码字进行排序;在编码过程中,利用邻近图像块的高度相关性和当前输人矢量在主轴上的投影值共同确定相应的码字搜索范围．实验结果表明,与传统穷尽搜索矢量量化编码法相比,虽然文中算法的编码质量略有下降,但编码速度和压缩效率都有了显著的提高．     

改进的矢量量化码字快速搜索法

矢量量化技术是一种高效和有竞争力的数据压缩方法,但由于其编解码过程中需要较大的计算量影响了其使用。提出了一种改进的基于子矢量特征值的码字快速搜索算法。算法充分利用矢量的3个特征值即和值、子矢量和值以及方差,建立起一种5步码字排除法,使得算法能够快速排除大部分不匹配码字,实现减少计算量的目的。仿真实验结果表明,算法的计算量要小于ZhiBin算法、Pan算法以及Chen算法,证明了改进算法的有效性。     

均值与矢量量化复合快速图像编码算法

矢量量化是一种有效的数据压缩技术,由于其算法简单,具有较高的压缩率,因而被广泛应用于数据压缩编码领域。通过对图像块灰度特征的研究,根据图像的平滑与否,提出了对图像进行均值和矢量量化复合编码算法,该算法对平滑图像块采用均值编码,对非平滑块采用矢量量化编码。这不仅节省了平滑码字的存储空间,提高了码书存储效率,并且编码速度大大提高。同时采用码字旋转反色（2R）压缩算法将码书的存储容量减少到1/8,并结合最近邻块扩展搜索算法（EBNNS）对搜索算法进行优化。在保证图像画质的前提下,整个系统的图像编码速度比全搜索的普通矢量量化平均提高约7.7倍。     

基于Hadamard变换和矢量分割的快速搜索算法

为了对图像信号进行快速有效压缩,提出了一种改进的基于Hadamard变换和矢量分割的双测试算法.该算法首先在Hadamard域中对空域双测试算法的两个删除准则进行了等效变换;然后在实验的基础上,对变换域码字和输入矢量进行了恰当的矢量分割;最后在码字搜索过程中,利用其中一个最为有效的删除准则来排除大部分的不匹配码字.实验结果表明,改进算法能大大提高码字的搜索效率,搜索范围可减少到原始算法搜索范围的约14%～17%.总体编码时间也减少到原始算法编码时间的约35%～45%.     

A fast VQ codebook search with initialization and search order

Vector quantization (VQ), a lossy image compression, is widely used for many applications due to its simple architecture, fast decoding ability, and high compression rate. Traditionally, VQ applies the full search algorithm to search for the codeword that best matches each image vector in the encoding procedure. However, matching in this manner consumes a lot of computation time and leads to a heavy burden for the VQ method. Therefore, Torres and Huguet proposed a double test algorithm to improve the matching efficiency. However, their scheme does not include an initiation strategy to choose an initially searched codeword for each image vector, and, as a result, matching efficiency may be affected significantly. To overcome this drawback, we propose an improved double test scheme with a fine initialization as well as a suitable search order. Our experimental results indicate that the computation time of the double test algorithm can be significantly reduced by the proposed method. In addition, the proposed method is more flexible than existing schemes.     

Novel full-search schemes for speeding up image coding using vector quantization

The routine for finding the closest codeword in the encoding phase of vector quantization (VQ) is high computational complexity and time consuming, especially when the codewords deal with the high-dimensional vectors. In this paper, we propose three newly developed schemes for speeding up the encoding phase of VQ. The proposed schemes can easily filter out many impossible codewords such that the search domain is reduced. The experimental results show that the computational time of our proposed schemes can save more than 41–52% computational time in a full search scheme. Furthermore, our schemes only require fewer than 84% of the computational time required in recently proposed alternative.     

基于快速相关矢量量化的图象编码算法

图象编码已经成为当今计算机世界的重要问题,而矢量量化（ＶＱ）又是近年来有损图象压缩的一种重要技术,它的优点是比特率低以及解码简单,但是其穷尽搜索编码计算量较大,为了降低编码时间,已经有多种快速算法出现在一些文献中,然而这些算法往往不能进一步降低比特率,为了解决这一问题,因此提出了一种新颖快速相关矢量量化（ＣＶＱ）图象编码算法,该算法对图象块的编码采用对角顺序,即在编码过程中根据当前图象块（ＣＶＱ）     

应用多索引加法量化编码的近邻检索算法

目的 海量图像检索技术是计算机视觉领域研究热点之一,一个基本的思路是对数据库中所有图像提取特征,然后定义特征相似性度量,进行近邻检索。海量图像检索技术,关键的是设计满足存储需求和效率的近邻检索算法。为了提高图像视觉特征的近似表示精度和降低图像视觉特征的存储空间需求,提出了一种多索引加法量化方法。方法 由于线性搜索算法复杂度高,而且为了满足检索的实时性,需把图像描述符存储在内存中,不能满足大规模检索系统的需求。基于非线性检索的优越性,本文对非穷尽搜索的多索引结构和量化编码进行了探索新研究。利用多索引结构将原始数据空间划分成多个子空间,把每个子空间数据项分配到不同的倒排列表中,然后使用压缩编码的加法量化方法编码倒排列表中的残差数据项,进一步减少对原始空间的量化损失。在近邻检索时采用非穷尽搜索的策略,只在少数倒排列表中检索近邻项,可以大大减少检索时间成本,而且检索过程中不用存储原始数据,只需存储数据集中每个数据项在加法量化码书中的码字索引,大大减少内存消耗。结果 为了验证算法的有效性,在3个数据集SIFT、GIST、MNIST上进行测试,召回率相比近几年算法提升4%~15%,平均查准率提高12%左右,检索时间与最快的算法持平。结论 本文提出的多索引加法量化编码算法,有效改善了图像视觉特征的近似表示精度和存储空间需求,并提升了在大规模数据集的检索准确率和召回率。本文算法主要针对特征进行近邻检索,适用于海量图像以及其他多媒体数据的近邻检索。     

FPGA implementation of full-search vector quantization based on partial distance search

This paper presents a novel algorithm for field programmable gate array (FPGA) realization of vector quantizer (VQ) encoders using partial distance search (PDS). In most applications, the PDS is adopted as a software approach for attaining moderate codeword search acceleration. In this paper, a novel PDS algorithm well suited for hardware realization is proposed. The algorithm employs subspace search, bitplane reduction, and multiple-coefficient accumulation techniques for the effective reduction of the area complexity and computation latency. Concurrent encoding of different input vectors for further computation acceleration is also allowed by the employment of multiple-module PDS. The proposed implementation has been embedded in a softcore CPU for physical performance measurement. Experimental results show that the implementation provides a cost-effective solution to the FPGA realization of VQ encoding systems where both high throughput and high fidelity are desired.     

An improved search algorithm for vector quantization using mean pyramid structure

Vector quantization (VQ) is a well-known data compression technique. In the codebook design phase as well as the encoding phase, given a block represented as a vector, searching the closest codeword in the codebook is a time-consuming task. Based on the mean pyramid structure and the range search approach, an improved search algorithm for VQ is presented in this paper. Conceptually, the proposed algorithm has the bandpass filter effect. Each time, using the derived formula, the search range becomes narrower due to the elimination of some portion of the previous search range. This reduces search times and improves the previous result by Lee and Chen (A fast search algorithm for vector quantization using mean pyramids of codewords. IEEE Trans. Commun. 43(2/3/4), (1995) 1697–1702). Some experimental results demonstrate the computational advantage of the proposed algorithm.     

PDVQ图像编码系统的算法研究

PDVQ图像编码系统首先将码书进行方向性分类,把每类方向性码书中的码字按码字和值进行升序排列,并根据EBNNS算法将码书分块。编码时,先根据输入图像块的相关性进行PDVQ编码,然后分析输入图像块的方向性来选择相应的分类子码书,在该子码书中根据输入图像块的和值确定码字搜索范围,最后在确定的搜索范围内搜索最匹配码字。仿真结果表明,该系统集合了动态图像块划分（PDVQ）、基于方向性分类编码和等和值块扩展最近邻码字搜索（EBNNS）三种算法的优点,在保证重建图像质量前提下,缩短了编码时间,并提高了压缩比。     

Hadamard transform based fast codeword search algorithm for high-dimensional VQ encoding

An efficient nearest neighbor codeword search algorithm for vector quantization based on the Hadamard transform is presented in this paper. Four elimination criteria are derived from two important inequalities based on three characteristic values in the Hadamard transform domain. Before the encoding process, the Hadamard transform is performed on all the codewords in the codebook and then the transformed codewords are sorted in the ascending order of their first elements. During the encoding process, firstly the Hadamard transform is applied to the input vector and its characteristic values are calculated; secondly, the codeword search is initialized with the codeword whose Hadamard-transformed first element is nearest to that of the input vector; and finally the closest codeword is found by an up-and-down search procedure using the four elimination criteria. Experimental results demonstrate that the proposed algorithm is much more efficient than the most existing nearest neighbor codeword search algorithms in the case of problems of high dimensionality.     

Compression of 3-D Point Visual Data Using Vector Quantization and Rate-Distortion Optimization

In this paper, we propose adaptive and flexible quantization and compression algorithms for 3-D point data using vector quantization (VQ) and rate-distortion (R-D) optimization. The point data are composed of the position and the radius of sphere based on QSplat representation. The positions of child spheres are first transformed to the local coordinate system, which is determined by the parent-children relationship. The local coordinate transform makes the positions more compactly distributed in 3-D space, facilitating an effective application of VQ. We also develop a constrained encoding method for the radius data, which can provide a hole-free surface rendering at the decoder side. Furthermore, R-D optimized compression algorithm is proposed in order to allocate an optimal bitrate to each sphere. Experimental results show that the proposed algorithm can effectively compress the original 3-D point geometry at various bitrates.