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

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

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

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

基于Voronoi图的自适应快速码字搜索算法

PVDS算法因搜索固定数量的纹波导致搜索范围过大,编码效率较低。针对该问题,提出一种基于Voronoi图的自适应纹波搜索算法APVDS。通过实验确定一组合理的阈值,每搜索一个纹波就根据阈值判断是否达到搜索停止条件,由此减少所需搜索的纹波数。仿真实验结果表明,自适应搜索到2个纹波后,APVDS与PVDS算法的编码质量基本相同,但平均搜索范围明显缩小,平均编码时间也相应减少。     

等和值块扩展最近邻矢量量化码字搜索算法

论文提出一种等和值块扩展最近邻矢量量化码字搜索算法。该算法将码书按和值大小排序分块,并将每一块中间或中间附近的码字的和值作为本码书块的特征和值。编码时,查找与输入矢量和值距离最近的码书块并作为初始匹配码书块。然后在该码书块附近上下扩展搜索相邻码书块中距输入矢量最近的码字。该算法具有无复杂运算的特点,易于VLSI技术实现。仿真结果表明,该算法是一种有效的码字搜索算法。     

自适应子矢量划分的快速码字搜索算法

矢量量化编码过程中需要进行大量的矢量间距离计算,这个过程的计算复杂度极高,严重限制了其实际使用。为了加速矢量量化的编码过程,已经提出了各种基于1维特征量的码字搜索算法来减小码字搜索的范围。本文在基于不等式的快速搜索算法基础上,通过使用更有效的基于特征量的搜索算法,并引入自适应子矢量划分的方法,将额外增加的存储空间从N(N-1)/2降低到了13N,码字搜索范围减小了33.88%～50.94%,编码时间减少了10.82%～27.16%。     

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

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

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

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

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

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

一种基于小波变换的静止图像编码方法

随着小波分析的理论研究水平不断提高,其应用领域也在不断地扩展。特别是在信号和图像处理方面,由于小波变换具有良好的时频局部化性能,使其在该领域有着广泛的应用。本文通过对小波函数、多分辨分析等小波变换的有关概念和理论的介绍,以及对矢量量化方法的分析,提出了一种基于小波变换和矢量量化的图像编码方法,并在计算机上模拟实验,得到较好的重建效果。     

初始码字间距最大化的矢量量化码书设计算法

目前对传统LBG算法的改进措施一般以增加时间开销作为代价.本文提出一种新的矢量量化码书设计改进措施--初始码字间距最大化:初始码书中的码字全部来自输入的训练矢量,且每一个新的初始码字尽可能地远离现有的码字,实验结果表明:本算法完全消除了空胞腔现象,更有效地避免了局部最优,能获得质量更高的码书;收敛速度快,具有较低的时间消耗.本算法在时间开销以及码书质量这两个方面都优于传统LBG和基于人工蚁群优化的码书设计算法等改进算法.     

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.     

面向近似最近邻搜索的码字扩展增强型残差量化

为了进一步提高图像特征向量的近似最近邻搜索精度,提出一种码字扩展增强型残差量化方法,将增强型残差量化与均值等分向量计算方法相结合,降低码书训练误差并提高特征向量量化精度.在码书训练阶段,除第1层码书训练外,利用均值等分向量计算方法将上一层码书训练的误差向量作为下一层码书训练的输入,在此基础上提出迭代优化方法降低码书训练的全局量化误差;在特征向量量化阶段,利用均值等分向量计算方法对每层码书进行扩展,用得到的新码字对该层输入特征向量进行量化以提高量化精度;最后对特征向量近似最近邻搜索,提出一种非对称欧几里得度量计算方法.在2个公开的SIFT和GIST数据集上与5种典型方法进行实验的结果表明,所提方法可降低码书训练误差10%~24%,提高近似最近邻搜索召回率1%~44%;另外,在获得相同召回率条件下,所提方法可使码书的规模减小50%.     

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

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

哈夫曼编码乘积量化的图像哈希检索方法

目的 基于哈希编码的检索方法是图像检索领域中的经典方法。其原理是将原始空间中相似的图片经哈希函数投影、量化后,在汉明空间中得到相近的哈希码。此类方法一般包括两个过程：投影和量化。投影过程大多采用主成分分析法对原始数据进行降维,但不同方法的量化过程差异较大。对于信息量不均衡的数据,传统的图像哈希检索方法采用等长固定编码位数量化的方式,导致出现低编码效率和低量化精度等问题。为此,本文提出基于哈夫曼编码的乘积量化方法。方法 首先,利用乘积量化法对降维后的数据进行量化,以便较好地保持数据在原始空间中的分布情况。然后,采用子空间方差作为衡量信息量的标准,并以此作为编码位数分配的依据。最后,借助于哈夫曼树,给方差大的子空间分配更多的编码位数。结果 在常用公开数据集MNIST、NUS-WIDE和22K LabelMe上进行实验验证,与原始的乘积量化方法相比,所提出方法能平均降低49%的量化误差,并提高19%的平均准确率。在数据集MNIST上,与同类方法的变换编码方法（TC）进行对比,比较了从32 bit到256 bit编码时的训练时间,本文方法的训练时间能够平均缩短22.5 s。结论 本文提出了一种基于多位编码乘积量化的哈希方法,该方法提高了哈希编码的效率和量化精度,在平均准确率、召回率等性能上优于其他同类算法,可以有效地应用到图像检索相关领域。     

一种快速、有效的量化与基于小波的图像压缩

量化是利用小波变换的图像压缩编码技术的关键环节之一。矢量量化和标量量化各有长短,该文将这二者有机地结合起来,称为混合量化(HQ—Hybrid Quantization)。它既有矢量量化的高效率,又具有标量量化的简单性,不需要进行码书训练,不要做乘除法。并用标准测试图像与其它方法的压缩结果进行了比较。     

基于改进人工蜂群的图像矢量量化码书设计算法

为了进一步提高图像矢量量化的码书质量,提出了一种新的图像压缩矢量量化码书设计算法。该算法采用均方误差(MSE)作为码书设计的适应度函数,利用改进的人工蜂群算法进行适应度函数的优化求解,增强了算法的自组织性和收敛性,大大减少了陷入局部收敛的可能性。将一种基于和值特性的快速码字搜索思想引入到码书设计算法中,使算法计算量明显降低。仿真结果表明,该算法具有计算时间短、收敛速度快的优点,并且生成的码书质量好、稳定性强。