Full Text:   <733>

Summary:  <786>

CLC number: TP391

On-line Access: 2019-05-14

Received: 2017-12-12

Revision Accepted: 2018-03-17

Crosschecked: 2019-04-11

Cited: 0

Clicked: 3330

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Jun-qing Yu

http://orcid.org/0000-0001-7057-0402

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2019 Vol.20 No.4 P.507-524

http://doi.org/10.1631/FITEE.1700833


Vector quantization: a review


Author(s):  Ze-bin Wu, Jun-qing Yu

Affiliation(s):  Department of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China; more

Corresponding email(s):   zbwu@hust.edu.cn, yjqing@hust.edu.cn

Key Words:  Approximate nearest neighbor search, Image coding, Vector quantization


Ze-bin Wu, Jun-qing Yu. Vector quantization: a review[J]. Frontiers of Information Technology & Electronic Engineering, 2019, 20(4): 507-524.

@article{title="Vector quantization: a review",
author="Ze-bin Wu, Jun-qing Yu",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="20",
number="4",
pages="507-524",
year="2019",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1700833"
}

%0 Journal Article
%T Vector quantization: a review
%A Ze-bin Wu
%A Jun-qing Yu
%J Frontiers of Information Technology & Electronic Engineering
%V 20
%N 4
%P 507-524
%@ 2095-9184
%D 2019
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1700833

TY - JOUR
T1 - Vector quantization: a review
A1 - Ze-bin Wu
A1 - Jun-qing Yu
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 20
IS - 4
SP - 507
EP - 524
%@ 2095-9184
Y1 - 2019
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1700833


Abstract: 
vector quantization (VQ) is a very effective way to save bandwidth and storage for speech coding and image coding. Traditional vector quantization methods can be divided into mainly seven types, tree-structured VQ, direct sum VQ, Cartesian product VQ, lattice VQ, classified VQ, feedback VQ, and fuzzy VQ, according to their codebook generation procedures. Over the past decade, quantization-based approximate nearest neighbor (ANN) search has been developing very fast and many methods have emerged for searching images with binary codes in the memory for large-scale datasets. Their most impressive characteristics are the use of multiple codebooks. This leads to the appearance of two kinds of codebook: the linear combination codebook and the joint codebook. This may be a trend for the future. However, these methods are just finding a balance among speed, accuracy, and memory consumption for ANN search, and sometimes one of these three suffers. So, finding a vector quantization method that can strike a balance between speed and accuracy and consume moderately sized memory, is still a problem requiring study.

向量量化综述

摘要:向量量化用于语音与图像编码可有效减小带宽和存储开销。根据码书生成过程,可将传统向量量化方法分为7类:树形向量量化、直和向量量化、迪卡尔积向量量化、格子向量量化、基于分类的向量量化、反馈向量量化以及模糊向量量化。在过去10年中,基于向量量化的近似近邻搜索发展迅速,涌现大量在大规模数据集内存中搜索图像的编码方法。这些方法的一个显著特征是使用多个码书,形成两种新的码书结构:线性组合码书和联合码书,这将成为未来发展趋势。这些方法用于近似近邻搜索的本质是在速度、准确率和空间开销之间权衡,有时其中一个会受损。因此,找到一个在速度、准确率和空间开销中平衡的向量量化方法依然是一个值得研究的问题。

关键词:近似近邻搜索;图像编码;向量量化

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Ahalt SC, Krishnamurthy AK, Chen P, et al., 1990. Competitive learning algorithms for vector quantization. Neur Netw, 3(3):277-290.

[2]Ai LF, Yu JQ, He YF, et al., 2013. High-dimensional indexing technologies for large-scale content-based image retrieval: a review. J Zhejiang Univ-Sci C (Comput & Electron), 14(7):505-520.

[3]Ai LF, Yu JQ, Guan T, et al., 2014. Efficient approximate nearest neighbor search by optimized residual vector quantization. 12th Int Workshop on Content-Based Multimedia Indexing, p.1-4.

[4]Babenko A, Lempitsky V, 2012. The inverted multi-index. IEEE Conf on Computer Vision and Pattern Recognition, p.3069-3076.

[5]Babenko A, Lempitsky V, 2014. Additive quantization for extreme vector compression. IEEE Conf on Computer Vision and Pattern Recognition, p.931-938.

[6]Babenko A, Lempitsky V, 2015. Tree quantization for large-scale similarity search and classification. IEEE Conf on Computer Vision and Pattern Recognition, p.4240-4248.

[7]Barnes CF, Rizvi S, Nasrabadi NM, 1996. Advances in residual vector quantization: a review. IEEE Trans Image Process, 5(2):226-262.

[8]Beyer K, Goldstein J, Ramakrishnan R, et al., 1999. When is “nearest neighbor” meaningful? In: Beeri C, Buneman P (Eds.), Database Theory—ICDT’99. Springer Berlin Heidelberg, p.217-235.

[9]Bezdek JC, Ehrlich R, Full W, 1984. FCM: the fuzzy textitc-means clustering algorithm. Comput Geosci, 10(2-3):191-203.

[10]Bezdek JC, Tsao ECK, Pal NR, 1992. Fuzzy kohonen clustering networks. IEEE Int Conf on Fuzzy Systems, p.1035-1043.

[11]Brandt J, 2010. Transform coding for fast approximate nearest neighbor search in high dimensions. IEEE Conf on Computer Vision and Pattern Recognition, p.1815-1822.

[12]Buzo A, Gray A, Gray R, et al., 1980. Speech coding based upon vector quantization. IEEE Trans Acoust Speech Signal Process, 28(5):562-574.

[13]Chan WY, Gersho A, 1990. Enhanced multistage vector quantization with constrained storage.24th Asilomar Conf on Signals, Systems, and Computers, p.659-663.

[14]Chan WY, Gupta S, Gersho A, 1992. Enhanced multistage vector quantization by joint codebook design. IEEE Trans Commun, 40(11):1693-1697.

[15]Chen HH, Ding JJ, Sheu HT, 2014. Image retrieval based on quadtree classified vector quantization. Multim Tools Appl, 72(2):1961-1984.

[16]Chuang JC, Hu YC, Lo CC, et al., 2013. Improved mean-removed vector quantization scheme for grayscale image coding. Int J Signal Process Image Process Patt Recogn, 6(5):315-332.

[17]Convay JH, Sloane NJA, 1982. Fast quantizing and decoding algorithms for lattice quantizers and codes. IEEE Trans Inform Theory, 28(2):227-232.

[18]Dasgupta S, Freund Y, 2008. Random projection trees and low-dimensional manifolds. 40th Annual ACM Symp on Theory of Computing, p.537-546.

[19]Dasgupta S, Freund Y, 2009. Random projection trees for vector quantization. IEEE Trans Inform Theory, 55(7):3229-3242.

[20]Eriksson T, Agrell E, 1996. Lattice-Based Quantization: Part II. Technical Report No. 18, Chalmers University of Technology, Göteborg, Sweden.

[21]Fischer T, 1986. A pyramid vector quantizer. IEEE Trans Inform Theory, 32(4):568-583.

[22]Foster J, Gray R, Dunham M, 1985. Finite-state vector quantization for waveform coding. IEEE Trans Inform Theory, 31(3):348-359.

[23]Freund Y, Dasgupta S, Kabra M, et al., 2007. Learning the structure of manifolds using random projections. 20th Int Conf on Neural Information Processing Systems, p.473-480.

[24]Ge TZ, He KM, Ke QF, et al., 2013. Optimized product quantization for approximate nearest neighbor search. IEEE Conf on Computer Vision and Pattern Recognition, p.2946-2953.

[25]Ge TZ, He KM, Ke QF, et al., 2014. Optimized product quantization. IEEE Trans Patt Anal Mach Intell, 36(4):744-755.

[26]Gersho A, 1979. Asymptotically optimal block quantization. IEEE Trans Inform Theory, 25(4):373-380.

[27]Gersho A, 1982. On the structure of vector quantizers. IEEE Trans Inform Theory, 28(2):157-166.

[28]Gersho A, Gray R, 1991. Vector Quantization and Signal Compression. Springer, Berlin, Germany.

[29]Gong YC, Lazebnik S, 2011. Iterative quantization: a procrustean approach to learning binary codes. IEEE Conf on Computer Vision and Pattern Recognition, p.817-824.

[30]Gray R, 1984. Vector quantization. IEEE ASSP Mag, 1(2):4-29.

[31]Gray R, Neuhoff DL, 1998. Quantization. IEEE Trans Inform Theory, 44(6):2325-2383.

[32]Guo D, Li CQ, Wu L, 2016. Parametric and nonparametric residual vector quantization optimizations for ANN search. Neurocomputing, 217:92-102.

[33]Hang HM, Woods JW, 1985. Predictive vector quantization of images. IEEE Trans Commun, 33(11):1208-1219.

[34]Heo JP, Lin Z, Yoon SE, 2014. Distance encoded product quantization. IEEE Conf on Computer Vision and Pattern Recognition, p.2139-2146.

[35]Indyk P, Motwani R, 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. $30^text{th}$ Annual ACM Symp on Theory of Computing, p.604-613.

[36]Jégou H, Douze M, Schmid C, 2008. Hamming embedding and weak geometric consistency for large-scale image search. 10th European Conf on Computer Vision, p.304-317.

[37]Jégou H, Douze M, Schmid C, 2010. Product quantization for nearest neighbor search. IEEE Trans Patt Anal Mach Intell, 33(1):117-128.

[38]Jégou H, Perronnin F, Douze M, et al., 2012. Aggregating local image descriptors into compact codes. IEEE Trans Patt Anal Mach Intell, 34(9):1704-1716.

[39]Juang BH, Gray A, 1982. Multiple stage vector quantization for speech coding. IEEE Int Conf on Acoustics, Speech, and Signal Processing, p.597-600.

[40]Kalantidi Y, Avrithis Y, 2014. Locally optimized product quantization for approximate nearest neighbor search. IEEE Conf on Computer Vision and Pattern Recognition, p.2329-2336.

[41]Karayiannis NB, Pai PI, 1995. Fuzzy vector quantization algorithms and their application in image compression. IEEE Trans Image Process, 4(9):1193-1201.

[42]Kieffer J, 1982. Stochastic stability for feedback quantization schemes. IEEE Trans Inform Theory, 28(2):248-254.

[43]Kim T, 1988. New finite state vector quantizers for images. Int Conf on Acoustics, Speech, and Signal Processing, p.1180-1183.

[44]Kohonen T, Huang T, Schroeder M, 1984. Self-Organization and Associative Memory. Springer-Verlag, Berlin, p.3406-3409.

[45]Liu SC, Shao JR, Lu HT, 2017. Generalized residual vector quantization and aggregating tree for large-scale search. IEEE Trans Multim, 19(8):1785-1797.

[46]Lloyd S, 1982. Least squares quantization in PCM. IEEE Trans Inform Theory, 28(2):129-137.

[47]Lowe DG, 1999. Object recognition from local scale-invariant feature. 7th IEEE Int Conf on Computer Vision, p.1150-1157.

[48]Lowe DG, 2004. Distinctive image features from scale-invariant keypoints. Int J Comput Vis, 60(2):91-110.

[49]Martinez J, Clement J, Hoos HH, et al., 2016. Revisiting additive quantization. 14th European Conf on Computer Vision, p.137-153.

[50]Muja M, Lowe DG, 2009. Fast approximate nearest neighbors with automatic algorithm configuration. 4th Int Conf on Computer Vision Theory and Applications, p.331-340.

[51]Nister D, Stewenius H, 2006. Scalable recognition with a vocabulary tree. IEEE Conf on Computer Vision and Pattern Recognition, p.2161-2168.

[52]Norouzi M, Fleet DJ, 2013. Cartesian textitk-means. IEEE Conf on Computer Vision and Pattern Recognition, p.3017-3024.

[53]Oliva A, Torralba A, 2001. Modeling the shape of the scene: a holistic representation of the spatial envelope. Int J Comput Vis, 42(3):145-175.

[54]Ozan EC, Kiranyaz S, Gabbouj M, 2016a. K-subspaces quantization for approximate nearest neighbor search. IEEE Trans Knowl Data Eng, 28(7):1722-1733.

[55]Ozan EC, Kiranyaz S, Gabbouj M, 2016b. Competitive quantization for approximate nearest neighbor search. IEEE Trans Knowl Data Eng, 28(11):2884-2894.

[56]Park M, Gunda K, Gupta H, et al., 2014. Optimized transform coding for approximate KNN search. British Machine Vision Conf, p.1-12.

[57]Patchoo W, Fischer TR, Maddex C, 2013. L1-norm-based coding for lattice vector quantization. Asia-Pacific Signal and Information Association Annual Summit and Conf, p.1-4.

[58]Paulev' e L, J' egou H, Amsaleg L, 2010. Locality sensitive hashing: a comparison of hash function types and querying mechanisms. Patt Recogn Lett, 31(11):1348-1358.

[59]Perronnin F, Dance C, 2007. Fisher kernels on visual vocabularies for image categorization. IEEE Conf on Computer Vision and Pattern Recognition, p.1-8.

[60]Ramamurthi B, Gersho A, 1986. Classified vector quantization of images. IEEE Trans Commun, 34(11):1105-1115.

[61]Sabin M, Gray R, 1982. Product code vector quantizers for speech waveform coding. Global Telecommunications Conf, p.1087-1091.

[62]Sabin M, Gray R, 1984. Product code vector quantizers for waveform and voice coding. IEEE Trans Acoust Speech Signal Process, 32(3):474-488.

[63]Schönemann P, 1966. A generalized solution of the orthogonal Procrustes problem. Psychometrika, 31(1):1-10.

[64]Shannon CE, 1948. A mathematical theory of communication. Bell Syst Tech J, 27(3):379-423.

[65]Shannon CE, 1959. Coding theorems for a discrete source with a fidelity criterion. IRE National Convention Record, Part 4, p.93-126.

[66]Silpa-Anan C, Hartley R, 2008. Optimized KD-trees for fast image descriptor matching. IEEE Conf on Computer Vision and Pattern Recognition, p.1-8.

[67]Sivic J, Zisserman A, 2003. Video Google: a text retrieval approach to object matching in videos. 9th IEEE Int Conf on Computer Vision, p.1470-1477.

[68]Tsekouras GE, Tsolakis DM, 2013. Fuzzy clustering-based vector quantization for image compression. In: Chatterjee A, Siarry P (Eds.), Computational Intelligence in Image Processing. Springer Berlin Heidelberg, p.93-105.

[69]Tsekouras GE, Antonios M, Anagnostopoulos C, et al., 2008. Improved batch fuzzy learning vector quantization for image compression. Inform Sci, 178(20):3895-3907.

[70]Tuytelaars T, Schmid C, 2007. Vector quantizing feature space with a regular lattice. IEEE $11^text{th}$ Int Conf on Computer Vision, p.1-8.

[71]Wang JF, Wang JD, Song JK, et al., 2014. Optimized Cartesian textitk-means. IEEE Trans Knowl Data Eng, 27(1):180-192.

[72]Wei BC, Guan T, Yu JQ, 2014. Projected residual vector quantization for ANN search. IEEE Multim, 21(3):41-51.

[73]Weiss Y, Torralba A, Fergus R, 2008. Spectral hashing. 21th Int Conf on Neural Information Processing Systems, p.1753-1760.

[74]Xia Y, He KM, Wen F, et al., 2013. Joint inverted indexing. IEEE Int Conf on Computer Vision, p.3416-3423.

[75]Yuan JB, Liu XW, 2015a. Product tree quantization for approximate nearest neighbor search. IEEE Int Conf on Image Processing, p.2035-2039.

[76]Yuan JB, Liu XW, 2015b. Transformed residual quantization for approximate nearest neighbor search. arXiv:1512.06925

[77]Zhang L, Zhang M, Pan Q, et al., 2014. An effective image coding method using lattice vector quantization in wavelet domain. Int J Signal Process Image Process Patt Recogn, 7(2):305-316.

[78]Zhang T, Du C, Wang JD, 2014. Composite quantization for approximate nearest neighbor search. $31^text{st}$ Int Conf on Machine Learning, p.838-846.

[79]Zhang T, Qi GJ, Tang JH, et al., 2015. Sparse composite quantization. IEEE Conf on Computer Vision and Pattern Recognition, p.4548-4556.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE