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

doi:10.13229/j.cnki.jdxbgxb20210216

Abstract

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

CLC Number:

TP391

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.

Figures/Tables 5

Fig.1

Table 1

Table 2

Fig.2

Fig.3

References 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.

Related Articles 15

[1]	Ming LIU,Yu-hang YANG,Song-lin ZOU,Zhi-cheng XIAO,Yong-gang ZHANG. Application of enhanced edge detection image algorithm in multi-book recognition [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(4): 891-896.
[2]	Shi-min FANG. Multiple source data selective integration algorithm based on frequent pattern tree [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(4): 885-890.
[3]	Sheng-sheng WANG,Jing-yu CHEN,Yi-nan LU. COVID⁃19 chest CT image segmentation based on federated learning and blockchain [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(6): 2164-2173.
[4]	Hong-wei ZHAO,Zi-jian ZHANG,Jiao LI,Yuan ZHANG,Huang-shui HU,Xue-bai ZANG. Bi⁃direction segmented anti⁃collision algorithm based on query tree [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(5): 1830-1837.
[5]	Jie CAO,Xue QU,Xiao-xu LI. Few⁃shot image classification method based on sliding feature vectors [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(5): 1785-1791.
[6]	Chun-bo WANG,Xiao-qiang DI. Cloud storage integrity verification audit scheme based on label classification [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(4): 1364-1369.
[7]	Rong QIAN,Ru ZHANG,Ke-jun ZHANG,Xin JIN,Shi-liang GE,Sheng JIANG. Capsule graph neural network based on global and local features fusion [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(3): 1048-1054.
[8]	Qian-yi XU,Gui-he QIN,Ming-hui SUN,Cheng-xun MENG. Classification of drivers' head status based on improved ResNeSt [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(2): 704-711.
[9]	Yuan SONG,Dan-yuan ZHOU,Wen-chang SHI. Method to enhance security function of OpenStack Swift cloud storage system [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(1): 314-322.
[10]	Zhi-jun LI,Chu-xi YANG,Dan LIU,Da-yang SUN. Deep convolutional networks based image compression with enhancement of information flow [J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(5): 1788-1795.
[11]	Xiang-jiu CHE,You-zheng DONG. Improved image recognition algorithm based on multi⁃scale information fusion [J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(5): 1747-1754.
[12]	HU Guan-yu, QIAO Pei-li. High dimensional differential evolutionary algorithm based on cloud population for network security prediction [J]. 吉林大学学报(工学版), 2016, 46(2): 568-577.
[13]	CHEN Mian-shu, WANG Yuan-yuan, SANG Ai-jun, CHEN He-xin. KL transformation based the theory of multidimensional vector matrix [J]. 吉林大学学报(工学版), 2016, 46(2): 627-631.
[14]	ZHENG Kou-quan, LEI Ying-jie, WANG Rui, YU Xiao-dong. Long-term intuitionistic fuzzy time series forecasting based on vector quantization [J]. 吉林大学学报(工学版), 2014, 44(3): 795-780.
[15]	HOU A-lin, LIAO Qing, JIN Zhi-juan, CHEN Juan, GENG Ying. Compression algorithm of computer-generated hologram based on artificial neural network [J]. 吉林大学学报(工学版), 2013, 43(增刊1): 21-24.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

码书长度	测试图像	搜索时间/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)