基于邻域相似性的图像码字快速搜索算法

doi:10.13229/j.cnki.jdxbgxb20210216

吉林大学学报(工学版) ›› 2022, Vol. 52 ›› Issue (8): 1865-1871.doi: 10.13229/j.cnki.jdxbgxb20210216

• 计算机科学与技术 • 上一篇

基于邻域相似性的图像码字快速搜索算法

曲福恒¹(),丁天雨¹,陆洋¹,杨勇^1,²(),胡雅婷³

^1.长春理工大学计算机科学技术学院，长春 130022
^2.长春师范大学教育学院，长春 130032
^3.吉林农业大学信息技术学院，长春 130118

收稿日期:2021-03-18 出版日期:2022-08-01 发布日期:2022-08-12
通讯作者: 杨勇 E-mail:qufuheng@163.com;yy@mail.ccsfu.edu.cn
作者简介:曲福恒（1979-），男，副教授，博士. 研究方向：数据挖掘，图像处理. E-mail：qufuheng@163.com
基金资助:
吉林省教育厅科学技术研究项目(JJKH20220777KJ);国家自然科学基金项目(41671397);吉林省教育厅“十三五”科学技术项目(JJKH20181164KJ)

Fast image codeword search algorithm based on neighborhood similarity

Fu-heng QU¹(),Tian-yu DING¹,Yang LU¹,Yong YANG^1,²(),Ya-ting HU³

^1.College of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022，China
^2.College of Education，Changchun Normal University，Changchun 130032，China
^3.College of Information Technology，Jilin Agricultural University，Changchun 130118，China

Received:2021-03-18 Online:2022-08-01 Published:2022-08-12
Contact: Yong YANG E-mail:qufuheng@163.com;yy@mail.ccsfu.edu.cn

摘要/Abstract

摘要：

有序平均距离部分码书搜索算法（MPS）是一种针对于图像矢量量化过程的码字快速搜索算法，为寻找初始匹配码字，MPS算法需要计算所有矢量与码书中所有码字之间的均值平方距离，对于 $n$ 个矢量与长度为 $k$ 的码书来说，此部分的计算量为 $O (n k + k l o g k)$ ，这限制了MPS的加速效果。针对此问题，本文提出了基于邻域相似性的图像码字快速搜索算法。首先，对原始码书根据码字分量和值按照从小至大排序获得排序码书；然后，在当前图像矢量的邻居矢量中确定候选初始匹配码字，再通过距离比较确定最终初始匹配码字；最后，以初始匹配码字为起始搜索点进行基于排序码书的码字搜索。算法将MPS算法中初始匹配码字选择计算量降低至 $O (n + k l o g k)$ ，并且具有与全搜索算法以及MPS算法一样的结果。不同算法的对比实验结果表明，FSNS算法具有最高的加速比，平均时间加速比为4.38~11.24，而MPS算法与ITIE算法分别为3.19~6.01与1.49~2.99。

关键词: 计算机应用技术, 矢量量化, 邻域相似性, 码字搜索, 图像压缩

Abstract:

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 (n k + k l o g 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 l o g 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.

Key words: computer application technology, vector quantization, neighborhood similarity, codeword search, image compression

中图分类号:

TP391

曲福恒,丁天雨,陆洋,杨勇,胡雅婷. 基于邻域相似性的图像码字快速搜索算法[J]. 吉林大学学报(工学版), 2022, 52(8): 1865-1871.

Fu-heng QU,Tian-yu DING,Yang LU,Yong YANG,Ya-ting HU. Fast image codeword search algorithm based on neighborhood similarity[J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(8): 1865-1871.

图/表 5

图1

表1

表2

图2

图3

参考文献 14

1	李志军,杨楚皙,刘丹,等. 基于深度卷积神经网络的信息流增强图像压缩方法[J]. 吉林大学学报: 工学版,2020, 50(5): 1788-1795.
	Li Zhi-jun, Yang Chu-xi, Liu Dan, et al. Deepconvolutional network based image compression with enhance-ment of information flow[J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(5): 1788-1795.
2	Zuo Z, Lan X, Deng L, et al. An improved medical i-mage compression technique with lossless region of int-erest[J]. Optik, 2015, 126(21): 2825-2831.
3	李雄飞,宋璐,张小利. 基于协同经验小波变换的遥感图像融合[J]. 吉林大学学报: 工学版, 2019, 49(4): 1307-1319.
	Li Xiong-fei, Song Lu, Zhang Xiao-li. Remote sensing image fusion based on collaborative empirical wavelet transform[J]. Journal of Jilin University(Engineering andTechnology Edition), 2019, 49(4): 1307-1319.
4	Bei C, Gray R. An improvement of the minimum distortion encoding algorithm for vector quantization[J]. IEEE Tranactions on Communications, 1985, 33(10): 1132-1133.
5	Ra S W, Kim J K. A fast mean-distance-ordered partial codebook search algorithm for image vector quantization[J]. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 1993, 40(9): 576-579.
6	Song B C, Ra J B. A fast search algorithm for vector quantization using L/sub 2/-norm pyramid of codewords[J]. IEEE Transactions on Image Processing, 2002, 11(1): 10-15.
7	Pan Z, Kotani K, Ohmi T. Fast encoding method for vector quantization using modified L/sub 2/-norm pyramid[J]. IEEE Signal Processing Letters, 2005, 12(9): 609-612.
8	Lu Z M, Chu S C, Huang K C. Equal-average equal-variance equal-norm nearest neighbor codeword search algorithm based on ordered Hadamard transform[J]. International Journal of Innovative Computing, Information and Control, 2005, 1(1): 35-41.
9	Swilem A. A fast vector quantization encoding algorithm based on projection pyramid with Hadamard transformation[J]. Image and Vision Computing, 2010, 28(12): 1637-1644.
10	Chang C C, Hsieh Y P. A fast VQ codebook search with initialization and search order[J].Information Sciences, 2012, 183(1): 132-139.
11	Chu C P, Yeh C Y, Hwang S H. An efficient tree‐structured vector quantization using dynamic triangular inequality elimination[J]. IEEJ Transactions on Electrical and Electronic Engineering, 2014, 9(Sup.1): 70-72.
12	Yang P Y, Tsai J T, Chou J H. PCA-based fast search method using PCA-LBG-based VQ codebook for codebook search[J]. IEEE Access, 2016, 4: 1332-1344.
13	Jamali M, Ghafarinia V, Montazeri M A. An optimized fast codeword search algorithm for vector quantization[C]∥24th Iranian Conference on Electrical Engineering, Shiraz, Iran, 2016: 77-81.
14	Yeh C Y. Iterative triangular inequality elimination algorithm for codebook search of vector quantization[J]. IEEJ Transactions on Electrical and Electronic Engineering, 2018, 13(10): 1528-1529.

相关文章 15

[1]	刘铭,杨雨航,邹松霖,肖志成,张永刚. 增强边缘检测图像算法在多书识别中的应用[J]. 吉林大学学报(工学版), 2022, 52(4): 891-896.
[2]	方世敏. 基于频繁模式树的多来源数据选择性集成算法[J]. 吉林大学学报(工学版), 2022, 52(4): 885-890.
[3]	王生生,陈境宇,卢奕南. 基于联邦学习和区块链的新冠肺炎胸部CT图像分割[J]. 吉林大学学报(工学版), 2021, 51(6): 2164-2173.
[4]	赵宏伟,张子健,李蛟,张媛,胡黄水,臧雪柏. 基于查询树的双向分段防碰撞算法[J]. 吉林大学学报(工学版), 2021, 51(5): 1830-1837.
[5]	曹洁,屈雪,李晓旭. 基于滑动特征向量的小样本图像分类方法[J]. 吉林大学学报(工学版), 2021, 51(5): 1785-1791.
[6]	王春波,底晓强. 基于标签分类的云数据完整性验证审计方案[J]. 吉林大学学报(工学版), 2021, 51(4): 1364-1369.
[7]	钱榕,张茹,张克君,金鑫,葛诗靓,江晟. 融合全局和局部特征的胶囊图神经网络[J]. 吉林大学学报(工学版), 2021, 51(3): 1048-1054.
[8]	周炳海,吴琼. 基于多目标的机器人装配线平衡算法[J]. 吉林大学学报(工学版), 2021, 51(2): 720-727.
[9]	许骞艺,秦贵和,孙铭会,孟诚训. 基于改进的ResNeSt驾驶员头部状态分类算法[J]. 吉林大学学报(工学版), 2021, 51(2): 704-711.
[10]	宋元,周丹媛,石文昌. 增强OpenStack Swift云存储系统安全功能的方法[J]. 吉林大学学报(工学版), 2021, 51(1): 314-322.
[11]	李志军,杨楚皙,刘丹,孙大洋. 基于深度卷积神经网络的信息流增强图像压缩方法[J]. 吉林大学学报(工学版), 2020, 50(5): 1788-1795.
[12]	车翔玖,董有政. 基于多尺度信息融合的图像识别改进算法[J]. 吉林大学学报(工学版), 2020, 50(5): 1747-1754.
[13]	陈绵书, 王园园, 桑爱军, 陈贺新. 基于多维矢量矩阵理论的KL变换[J]. 吉林大学学报(工学版), 2016, 46(2): 627-631.
[14]	胡冠宇, 乔佩利. 基于云群的高维差分进化算法及其在网络安全态势预测上的应用[J]. 吉林大学学报(工学版), 2016, 46(2): 568-577.
[15]	郑寇全,雷英杰,王睿,余晓东. 基于矢量量化的长期直觉模糊时间序列预测[J]. 吉林大学学报(工学版), 2014, 44(3): 795-780.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

码书长度	测试图像	搜索时间/ms				距离减少比例
码书长度	测试图像	FS	ITIE	MPS	本文	ITIE	MPS	本文
64	Airplane	43.10	13.80	12.80	7.30	0.91	0.683	0.899
	Baboon	38.70	23.80	16.50	14.50	0.81	0.582	0.750
	Couple	42.70	14.10	12.80	8.20	0.90	0.659	0.876
	Lena	44.40	14.50	12.10	8.40	0.90	0.684	0.900
	Peppers	39.90	12.50	12.40	6.90	0.91	0.684	0.891
128	Airplane	82.80	28.50	19.90	11.50	0.92	0.687	0.912
	Baboon	80.40	41.50	28.10	22.20	0.86	0.609	0.786
	Couple	78.80	26.50	22.10	12.00	0.92	0.673	0.900
	Lena	81.70	26.90	19.60	11.50	0.92	0.697	0.914
	Peppers	79.40	24.90	20.00	11.40	0.92	0.698	0.925
256	Airplane	157.70	59.00	36.40	20.70	0.94	0.699	0.913
	Baboon	158.90	83.60	56.70	36.90	0.91	0.625	0.806
	Couple	162.00	59.80	46.50	18.70	0.94	0.687	0.913
	Lena	160.20	59.00	34.70	18.30	0.94	0.700	0.926
	Peppers	156.40	62.60	37.80	16.90	0.94	0.700	0.937
512	Airplane	305.80	149.80	84.10	34.90	0.95	0.701	0.914
	Baboon	313.40	187.90	114.70	71.20	0.94	0.650	0.826
	Couple	298.50	140.20	77.70	30.10	0.95	0.699	0.924
	Lena	309.60	146.50	67.90	28.40	0.95	0.712	0.937
	Peppers	296.20	119.70	69.10	25.00	0.95	0.712	0.938
1024	Airplane	594.40	389.30	153.40	53.50	0.97	0.712	0.925
	Baboon	585.80	553.30	174.70	102.40	0.96	0.674	0.849
	Couple	601.70	402.80	154.70	55.10	0.97	0.711	0.926
	Lena	596.50	391.80	147.50	44.10	0.97	0.723	0.949
	Peppers	587.30	317.90	156.40	39.40	0.97	0.713	0.949

码书长度	测试图像	搜索时间/ms				距离减少比例
码书长度	测试图像	FS	ITIE	MPS	本文	ITIE	MPS	本文
64	Airplane	20.20	6.80	5.00	4.60	0.86	0.841	0.862
	Baboon	20.50	13.50	9.00	8.30	0.57	0.650	0.671
	Couple	21.00	7.30	6.20	4.80	0.83	0.809	0.840
	Lena	20.40	7.10	4.80	4.00	0.86	0.851	0.883
	Peppers	20.10	6.50	4.90	3.60	0.88	0.862	0.894
128	Airplane	39.60	12.10	8.00	6.30	0.88	0.842	0.873
	Baboon	39.20	25.00	15.00	13.90	0.65	0.672	0.702
	Couple	40.20	12.00	9.90	7.20	0.87	0.820	0.861
	Lena	40.50	12.80	7.60	5.70	0.89	0.863	0.904
	Peppers	40.00	11.00	7.20	5.50	0.90	0.873	0.904
256	Airplane	79.90	29.50	13.70	11.00	0.89	0.852	0.883
	Baboon	82.50	50.90	25.90	24.00	0.72	0.703	0.723
	Couple	79.50	28.10	16.60	11.70	0.88	0.831	0.872
	Lena	83.70	27.90	13.00	9.70	0.91	0.873	0.905
	Peppers	82.00	25.30	13.20	9.20	0.90	0.873	0.915
512	Airplane	155.30	76.40	27.80	21.70	0.90	0.863	0.894
	Baboon	177.50	101.30	51.00	43.30	0.78	0.714	0.745
	Couple	164.70	68.60	32.70	25.60	0.90	0.842	0.863
	Lena	161.10	83.20	23.90	16.90	0.91	0.874	0.915
	Peppers	153.90	73.30	22.70	16.90	0.91	0.874	0.915
1024	Airplane	306.40	207.50	48.60	38.00	0.92	0.863	0.894
	Baboon	300.30	259.20	87.70	81.20	0.83	0.735	0.755
	Couple	307.70	201.70	54.80	40.00	0.92	0.842	0.883
	Lena	306.80	223.50	41.60	31.40	0.93	0.884	0.925
	Peppers	305.60	217.30	41.70	27.70	0.92	0.884	0.926

基于邻域相似性的图像码字快速搜索算法

Fast image codeword search algorithm based on neighborhood similarity

RICH HTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 14

相关文章 15

Metrics

本文评价

推荐阅读 0