CLC number: TP391
On-line Access: 2024-08-27
Received: 2023-10-17
Revision Accepted: 2024-05-08
Crosschecked: 2019-04-11
Cited: 0
Clicked: 6973
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.
[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>