摘要
有序平均距离部分码书搜索算法(MPS)是一种针对于图像矢量量化过程的码字快速搜索算法,为寻找初始匹配码字,MPS算法需要计算所有矢量与码书中所有码字之间的均值平方距离,对于n个矢量与长度为k的码书来说,此部分的计算量为O (nk+k log k),这限制了MPS的加速效果。针对此问题,本文提出了基于邻域相似性的图像码字快速搜索算法。首先,对原始码书根据码字分量和值按照从小至大排序获得排序码书;然后,在当前图像矢量的邻居矢量中确定候选初始匹配码字,再通过距离比较确定最终初始匹配码字;最后,以初始匹配码字为起始搜索点进行基于排序码书的码字搜索。算法将MPS算法中初始匹配码字选择计算量降低至O (n+k log k),并且具有与全搜索算法以及MPS算法一样的结果。不同算法的对比实验结果表明,FSNS算法具有最高的加速比,平均时间加速比为4.38~11.24,而MPS算法与ITIE算法分别为3.19~6.01与1.49~2.99。
The mean distance ordered partial codebook search(MPS)algorithm is a fast codebook search algorithm for image vector quantization. However,in order to find the initial matching codeword,the MPS algorithm needs to calculate the mean squared distance between all vectors and all codewords. For a codebook with n vectors and length k,the calculation amount of this part is O( nk + k log k),which limits the acceleration effect of MPS. To solve this problem,an image codeword fast search algorithm based on neighborhood similarity was proposed. The algorithm first sorts the original codebook from small to large according to the codeword components and values to obtain the sorted codebook. Then,the candidate initial matching codeword is determined in the neighbor vector of the current image vector,and the final initial matching codeword is determined by distance comparison. Finally,a codeword search based on the sorted codebook is performed with the initial matching codeword as the starting search point. The algorithm reduces the calculation amount of initial matching codeword selection in the MPS algorithm to O( n +k log k),and has the same results as the full search algorithm and the MPS algorithm. The results of comparative experiments on the test images show that the FSNS algorithm has the highest speedup ratio,and the average time speedup ratio ranges from 4.38~11.24,while the MPS algorithm and ITIE algorithm are 3.19~6.01 and 1.49~2.99.
作者
曲福恒
丁天雨
陆洋
杨勇
胡雅婷
QU Fu-heng;DING Tian-yu;LU Yang;YANG Yong;HU Ya-ting(College of Computer Science and Technology,Changchun University of Science and Technology,Changchun 130022,China;College of Education,Changchun Normal University,Changchun 130032,China;College of Information Technology,Jilin Agricultural University,Changchun 130118,China)
出处
《吉林大学学报（工学版）》
EI
CAS
CSCD
北大核心
2022年第8期1865-1871,共7页
Journal of Jilin University:Engineering and Technology Edition
基金
吉林省教育厅科学技术研究项目(JJKH20220777KJ)
吉林省教育厅“十三五”科学技术项目(JJKH20181164KJ)
国家自然科学基金项目(41671397)。
关键词
计算机应用技术
矢量量化
邻域相似性
码字搜索
图像压缩
computer application technology
vector quantization
neighborhood similarity
codeword search
image compression
