基于子空间三角不等式的高维码字搜索算法

A Fast Codeword Search Algorithm for High-Dimensional VQ Encoding Using Triangle Inequality in Subspace

本文分析了码字搜索算法中基于均值、方差和范数的删除准则,指出基于方差和范数的删除准则之间存在冗余缺陷.在此基础上,提出了一种新的子空间三角不等式删除准则,根据子空间中码字与参考点之间的距离来排除候选码字.基于方差的删除准则可以看成是子空间三角不等式删除准则的特例.在新的删除准则中,通过选择合适的子空间参考点,能够排除更多的不匹配码字.在编码前,首先计算每个码字的哈德码变换,并且计算在子空间中码字与参考点之间的距离,然后根据各码字哈德码变换域的第一维系数对码字进行升序排列.在编码过程中,根据码字的均值来终止最近邻搜索过程,采用子空间三角不等式删除准则来排除不匹配码字.测试结果表明,本文算法的搜索时间快于其他码字搜索算法,其搜索时间比当前最快的哈德码变换域等均值等方差等范数搜索算法要快8%~26%左右.

Elimination criteria based on mean value,variance and norm was often used in the VQ encoding to reject unlikely codewords.However,these elimination criteria have obvious computational redundancy.A new elimination criteria based on triangular inequality in subspace was proposed.By finding the optimal reference point of distance computation,the new elimination criteria can reject more unlikely codewords than other elimination criteria using variance and norm.The elimination criteria based on variance can be seen as the special case of new elimination criteria.Before the search process,all codewords in the codebook are Hadamard-transformed and sorted in the ascending order of their first elements.During the search process,the mean value of a vector was used to terminate the search process,and the new elimination criteria based on triangular inequality in subspace was applied to reject most unlikely codewords.Experiments results demonstrate that the performance of the proposed algorithm is much better than other nearest neighbor codeword search algorithms.Compared with the Hadamard-Transformed based Equal-Average Equal-variance Equal-norm Nearest Neighbor Search algorithm,the proposed algorithm reduces the computational time by 8% to 26%.