FOLLOWUS
Department of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China
Center of Network and Computation, Huazhong University of Science and Technology, Wuhan 430074, China
[ "Ze-bin WU, E-mail: zbwu@hust.edu.cn" ]
Jun-qing YU, E-mail: yjqing@hust.edu.cn
纸质出版日期:2019-04,
收稿日期:2017-12-12,
修回日期:2019-04-11,
Scan QR Code
吴泽斌, 于俊清. 向量量化综述[J]. 信息与电子工程前沿(英文), 2019,20(4):507-524.
ZE-BIN WU, JUN-QING YU. Vector quantization: a review. [J]. Frontiers of information technology & electronic engineering, 2019, 20(4): 507-524.
吴泽斌, 于俊清. 向量量化综述[J]. 信息与电子工程前沿(英文), 2019,20(4):507-524. DOI: 10.1631/FITEE.1700833.
ZE-BIN WU, JUN-QING YU. Vector quantization: a review. [J]. Frontiers of information technology & electronic engineering, 2019, 20(4): 507-524. DOI: 10.1631/FITEE.1700833.
向量量化用于语音与图像编码可有效减小带宽和存储开销。根据码书生成过程,可将传统向量量化方法分为7类:树形向量量化、直和向量量化、迪卡尔积向量量化、格子向量量化、基于分类的向量量化、反馈向量量化以及模糊向量量化。在过去10年中,基于向量量化的近似近邻搜索发展迅速,涌现大量在大规模数据集内存中搜索图像的编码方法。这些方法的一个显著特征是使用多个码书,形成两种新的码书结构:线性组合码书和联合码书,这将成为未来发展趋势。这些方法用于近似近邻搜索的本质是在速度、准确率和空间开销之间权衡,有时其中一个会受损。因此,找到一个在速度、准确率和空间开销中平衡的向量量化方法依然是一个值得研究的问题。
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.
近似近邻搜索图像编码向量量化
Approximate nearest neighbor searchImage codingVector quantization
SC Ahalt, , , AK Krishnamurthy, , , P Chen, , , 等. . Competitive learning algorithms for vector quantization. . Neur Netw, , 1990. . 3((3):):277--290. . DOI:10.1016/0893-6080(90)90071-Rhttp://doi.org/10.1016/0893-6080(90)90071-R..
LF Ai, , , JQ Yu, , , YF He, , , 等. . High-dimensional indexing technologies for large-scale content-basedimage retrieval: a review. . J Zhejiang Univ-Sci C (Comput & Electron), , 2013. . 14((7):):505--520. . DOI:10.1631/jzus.CIDE1304http://doi.org/10.1631/jzus.CIDE1304..
LF Ai, , , JQ Yu, , , T Guan, , , 等. . Efficient approximate nearest neighbor search by optimized residual vector quantization. . 12th Int Workshop on Content-Based Multimedia Indexing, , 2014. . p.1--4. . DOI:10.1109/CBMI.2014.6849842http://doi.org/10.1109/CBMI.2014.6849842..
A Babenko, , , V Lempitsky. . The inverted multi-index. . IEEE Conf on Computer Vision and Pattern Recognition, , 2012. . p.3069--3076. . DOI:10.1109/CVPR.2012.6248038http://doi.org/10.1109/CVPR.2012.6248038..
A Babenko, , , V Lempitsky. . Additive quantization for extreme vector compression. . IEEE Conf on Computer Vision and Pattern Recognition, , 2014. . p.931--938. . DOI:10.1109/CVPR.2014.124http://doi.org/10.1109/CVPR.2014.124..
A Babenko, , , V Lempitsky. . Tree quantization for large-scale similarity search and classification. . IEEE Conf on Computer Vision and Pattern Recognition, , 2015. . p.4240--4248. . DOI:10.1109/CVPR.2015.7299052http://doi.org/10.1109/CVPR.2015.7299052..
CF Barnes, , , S Rizvi, , , NM Nasrabadi. . Advances in residual vector quantization: a review. . IEEE Trans Image Process, , 1996. . 5((2):):226--262. . DOI:10.1109/83.480761http://doi.org/10.1109/83.480761..
K Beyer, , , J Goldstein, , , R Ramakrishnan, , , 等. . When is "nearest neighbor" meaningful. . In: Beeri C, Buneman P (Eds.), Database Theory——ICDT'99.Springer Berlin Heidelberg, , 1999. . p.217--235. . DOI:10.1007/3-540-49257-7_15http://doi.org/10.1007/3-540-49257-7_15..
JC Bezdek, , , R Ehrlich, , , W Full. . FCM: the fuzzy c-means clustering algorithm. . Comput Geosci, , 1984. . 10((2-3):):191--203. . DOI:10.1016/0098-3004(84)90020-7http://doi.org/10.1016/0098-3004(84)90020-7..
JC Bezdek, , , ECK Tsao, , , NR Pal. . Fuzzy kohonen clustering networks. . IEEE Int Conf on Fuzzy Systems, , 1992. . p.1035--1043. . DOI:10.1109/FUZZY.1992.258797http://doi.org/10.1109/FUZZY.1992.258797..
J Brandt. . Transform coding for fast approximate nearest neighbor search in high dimensions. . IEEE Conf on Computer Vision and Pattern Recognition, , 2010. . p.1815--1822. . DOI:10.1109/CVPR.2010.5539852http://doi.org/10.1109/CVPR.2010.5539852..
A Buzo, , , A Gray, , , R Gray, , , 等. . Speech coding based upon vector quantization. . IEEE Trans Acoust Speech Signal Process, , 1980. . 28((5):):562--574. . DOI:10.1109/TASSP.1980.1163445http://doi.org/10.1109/TASSP.1980.1163445..
WY Chan, , , A Gersho. . Enhanced multistage vector quantization with constrained storage. . 24th Asilomar Conf on Signals, Systems, and Computers, , 1990. . p.659--663. . DOI:10.1109/ACSSC.1990.523420http://doi.org/10.1109/ACSSC.1990.523420..
WY Chan, , , S Gupta, , , A Gersho. . Enhanced multistage vector quantization by joint codebook design. . IEEE Trans Commun, , 1992. . 40((11):):1693--1697. . DOI:10.1109/26.179932http://doi.org/10.1109/26.179932..
HH Chen, , , JJ Ding, , , HT Sheu. . Image retrieval based on quadtree classified vector quantization. . Multim Tools Appl, , 2014. . 72((2):):1961--1984. . DOI:10.1007/s11042-013-1492-yhttp://doi.org/10.1007/s11042-013-1492-y..
JC Chuang, , , YC Hu, , , CC Lo, , , 等. . Improved mean-removed vector quantization scheme for grayscale image coding. . Int J Signal Process Image Process Patt Recogn, , 2013. . 6((5):):315--332. . DOI:10.14257/ijsip.2013.6.5.28http://doi.org/10.14257/ijsip.2013.6.5.28..
JH Convay, , , NJA Sloane. . Fast quantizing and decoding algorithms for lattice quantizers and codes. . IEEE Trans Inform Theory, , 1982. . 28((2):):227--232. . DOI:10.1109/TIT.1982.1056484http://doi.org/10.1109/TIT.1982.1056484..
S Dasgupta, , , Y Freund. . Random projection trees and low-dimensional manifolds. . 40th Annual ACM Symp on Theory of Computing, , 2008. . p.537--546. . DOI:10.1145/1374376.1374452http://doi.org/10.1145/1374376.1374452..
S Dasgupta, , , Y Freund. . Random projection trees for vector quantization. . IEEE Trans Inform Theory, , 2009. . 55((7):):3229--3242. . DOI:10.1109/TIT.2009.2021326http://doi.org/10.1109/TIT.2009.2021326..
T Eriksson, , , E Agrell. . Lattice-Based Quantization: Part Ⅱ., , ::G teborg, SwedenTechnical Report No.18, Chalmers University of Technology, , 1996. ..
T Fischer. . A pyramid vector quantizer. . IEEE Trans Inform Theory, , 1986. . 32((4):):568--583. . DOI:10.1109/TIT.1986.1057198http://doi.org/10.1109/TIT.1986.1057198..
J Foster, , , R Gray, , , M Dunham. . Finite-state vector quantization for waveform coding. . IEEE Trans Inform Theory, , 1985. . 31((3):):348--359. . DOI:10.1109/TIT.1985.1057035http://doi.org/10.1109/TIT.1985.1057035..
Y Freund, , , S Dasgupta, , , M Kabra, , , 等. . Learning the structure of manifolds using random projections. . 20th Int Conf on Neural Information Processing Systems, , 2007. . p.473--480. . ..
TZ Ge, , , KM He, , , QF Ke, , , 等. . Optimized product quantization for approximate nearest neighbor search. . IEEE Conf on Computer Vision and Pattern Recognition, , 2013. . p.2946--2953. . DOI:10.1109/CVPR.2013.379http://doi.org/10.1109/CVPR.2013.379..
TZ Ge, , , KM He, , , QF Ke, , , 等. . Optimized product quantization. . IEEE Trans Patt Anal Mach Intell, , 2014. . 36((4):):744--755. . DOI:10.1109/TPAMI.2013.240http://doi.org/10.1109/TPAMI.2013.240..
A Gersho. . Asymptotically optimal block quantization. . IEEE Trans Inform Theory, , 1979. . 25((4):):373--380. . DOI:10.1109/TIT.1979.1056067http://doi.org/10.1109/TIT.1979.1056067..
A Gersho. . On the structure of vector quantizers. . IEEE Trans Inform Theory, , 1982. . 28((2):):157--166. . DOI:10.1109/TIT.1982.1056457http://doi.org/10.1109/TIT.1982.1056457..
A Gersho, , , R Gray. . Vector Quantization and Signal Compression, , ::Berlin, GermanySpringer, , 1991. ..
YC Gong, , , S Lazebnik. . Iterative quantization: a procrustean approach to learning binary codes. . IEEE Conf on Computer Vision and Pattern Recognition, , 2011. . p.817--824. . DOI:10.1109/CVPR.2011.5995432http://doi.org/10.1109/CVPR.2011.5995432..
R Gray. . Vector quantization. . IEEE ASSP Mag, , 1984. . 1((2):):4--29. . DOI:10.1109/MASSP.1984.1162229http://doi.org/10.1109/MASSP.1984.1162229..
R Gray, , , DL Neuhoff. . Quantization. . IEEE Trans Inform Theory, , 1998. . 44((6):):2325--2383. . DOI:10.1109/18.720541http://doi.org/10.1109/18.720541..
D Guo, , , CQ Li, , , L Wu. . Parametric and nonparametric residual vector quantization optimizations for ANN search. . Neurocomputing, , 2016. . 21792--102. . DOI:10.1016/j.neucom.2016.04.061http://doi.org/10.1016/j.neucom.2016.04.061..
HM Hang, , , JW Woods. . Predictive vector quantization of images. . IEEE Trans Commun, , 1985. . 33((11):):1208--1219. . DOI:10.1109/TCOM.1985.1096238http://doi.org/10.1109/TCOM.1985.1096238..
JP Heo, , , Z Lin, , , SE Yoon. . Distance encoded product quantization. . IEEE Conf on Computer Vision and Pattern Recognition, , 2014. . p.2139--2146. . DOI:10.1109/CVPR.2014.274http://doi.org/10.1109/CVPR.2014.274..
P Indyk, , , R Motwani. . Approximate nearest neighbors: towards removing the curse of dimensionality. . 30th Annual ACM Symp on Theory of Computing, , 1998. . p.604--613. . DOI:10.1145/276698.276876http://doi.org/10.1145/276698.276876..
H Jgou, , , M Douze, , , C Schmid. . Hamming embedding and weak geometric consistency for large-scale image search. . 10thEuropean Conf on Computer Vision, , 2008. . p.304--317. . DOI:10.1007/978-3-540-88682-2_24http://doi.org/10.1007/978-3-540-88682-2_24..
H Jgou, , , M Douze, , , C Schmid. . Product quantization for nearest neighbor search. . IEEE Trans Patt Anal Mach Intell, , 2010. . 33((1):):117--128. . DOI:10.1109/TPAMI.2010.57http://doi.org/10.1109/TPAMI.2010.57..
H Jgou, , , F Perronnin, , , M Douze, , , 等. . Aggregating local image descriptors into compact codes. . IEEE Trans Patt Anal Mach Intell, , 2012. . 34((9):):1704--1716. . DOI:10.1109/TPAMI.2011.235http://doi.org/10.1109/TPAMI.2011.235..
BH Juang, , , A Gray. . Multiple stage vector quantization for speech coding. . IEEE Int Conf on Acoustics, Speech, and Signal Processing, , 1982. . p.597--600. . DOI:10.1109/ICASSP.1982.1171604http://doi.org/10.1109/ICASSP.1982.1171604..
Y Kalantidi, , , Y Avrithis. . Locally optimized product quantization for approximate nearest neighbor search. . IEEE Conf on Computer Vision and Pattern Recognition, , 2014. . p.2329--2336. . DOI:10.1109/CVPR.2014.298http://doi.org/10.1109/CVPR.2014.298..
NB Karayiannis, , , PI Pai. . Fuzzy vector quantization algorithms and their application in image compression. . IEEE Trans Image Process, , 1995. . 4((9):):1193--1201. . DOI:10.1109/83.413164http://doi.org/10.1109/83.413164..
J Kieffer. . Stochastic stability for feedback quantization schemes. . IEEE Trans Inform Theory, , 1982. . 28((2):):248--254. . DOI:10.1109/TIT.1982.1056487http://doi.org/10.1109/TIT.1982.1056487..
T Kim. . New finite state vector quantizers for images. . Int Conf on Acoustics, Speech, and Signal Processing, , 1988. . p.1180--1183. . DOI:10.1109/ICASSP.1988.196809http://doi.org/10.1109/ICASSP.1988.196809..
T Kohonen, , , T Huang, , , M Schroeder. . Self-Organization and Associative Memory. . Springer-Verlag, Berlin, , 1984. . p.3406--3409. . DOI:10.1007/978-3-662-00784-6http://doi.org/10.1007/978-3-662-00784-6..
SC Liu, , , JR Shao, , , HT Lu. . Generalized residual vector quantization and aggregating tree for large-scale search. . IEEE Trans Multim, , 2017. . 19((8):):1785--1797. . DOI:10.1109/TMM.2017.2692181http://doi.org/10.1109/TMM.2017.2692181..
S Lloyd. . Least squares quantization in {PCM}. . IEEE Trans Inform Theory, , 1982. . 28((2):):129--137. . DOI:10.1109/TIT.1982.1056489http://doi.org/10.1109/TIT.1982.1056489..
DG Lowe. . Object recognition from local scale-invariant feature. . 7thIEEE Int Conf on Computer Vision, , 1999. . p.1150--1157. . DOI:10.1109/ICCV.1999.790410http://doi.org/10.1109/ICCV.1999.790410..
DG Lowe. . Distinctive image features from scale-invariant keypoints. . Int J Comput Vis, , 2004. . 60((2):):91--110. . DOI:10.1023/b:visi.0000029664.99615.94http://doi.org/10.1023/b:visi.0000029664.99615.94..
J Martinez, , , J Clement, , , HH Hoos, , , 等. . Revisiting additive quantization. . 14thEuropean Conf on Computer Vision, , 2016. . p.137--153. . DOI:10.1007/978-3-319-46475-6_9http://doi.org/10.1007/978-3-319-46475-6_9..
M Muja, , , DG Lowe. . Fast approximate nearest neighbors with automatic algorithm configuration. . 4thInt Conf on Computer Vision Theory and Applications, , 2009. . p.331--340. . DOI:10.5220/0001787803310340http://doi.org/10.5220/0001787803310340..
D Nister, , , H Stewenius. . Scalable recognition with a vocabulary tree. . IEEE Conf on Computer Vision and Pattern Recognition, , 2006. . p.2161--2168. . DOI:10.1109/CVPR.2006.264http://doi.org/10.1109/CVPR.2006.264..
M Norouzi, , , DJ Fleet. . Cartesian k-means. . IEEE Conf on Computer Vision and Pattern Recognition, , 2013. . p.3017--3024. . DOI:10.1109/CVPR.2013.388http://doi.org/10.1109/CVPR.2013.388..
A Oliva, , , A Torralba. . Modeling the shape of the scene: a holistic representation of the spatial envelope. . Int J Comput Vis, , 2001. . 42((3):):145--175. . DOI:10.1023/A:1011139631724http://doi.org/10.1023/A:1011139631724..
EC Ozan, , , S Kiranyaz, , , M Gabbouj. . K-subspaces quantization for approximate nearest neighbor search. . IEEE Trans Knowl Data Eng, , 2016a. . 28((7):):1722--1733. . DOI:10.1109/TKDE.2016.2535287http://doi.org/10.1109/TKDE.2016.2535287..
EC Ozan, , , S Kiranyaz, , , M Gabbouj. . Competitive quantization for approximate nearest neighbor search. . IEEE Trans Knowl Data Eng, , 2016b. . 28((11):):2884--2894. . DOI:10.1109/TKDE.2016.2597834http://doi.org/10.1109/TKDE.2016.2597834..
M Park, , , K Gunda, , , H Gupta, , , 等. . Optimized transform coding for approximate KNN search. . British Machine Vision Conf, , 2014. . p.1--12. . DOI:10.5244/c.28.34http://doi.org/10.5244/c.28.34..
W Patchoo, , , TR Fischer, , , C Maddex. . $$L_1$$-norm-based coding for lattice vector quantization. . Asia-Pacific Signal and Information Association Annual Summit and Conf, , 2013. . p.1--4. . DOI:10.1109/APSIPA.2013.6694164http://doi.org/10.1109/APSIPA.2013.6694164..
L Paulev, , , H Jgou, , , L Amsaleg. . Locality sensitive hashing: a comparison of hash function types and querying mechanisms. . Patt Recogn Lett, , 2010. . 31((11):):1348--1358. . DOI:10.1016/j.patrec.2010.04.004http://doi.org/10.1016/j.patrec.2010.04.004..
F Perronnin, , , C Dance. . Fisher kernels on visual vocabularies for image categorization. . IEEE Conf on Computer Vision and Pattern Recognition, , 2007. . p.1--8. . DOI:10.1109/CVPR.2007.383266http://doi.org/10.1109/CVPR.2007.383266..
B Ramamurthi, , , A Gersho. . Classified vector quantization of images. . IEEE Trans Commun, , 1986. . 34((11):):1105--1115. . DOI:10.1109/TCOM.1986.1096468http://doi.org/10.1109/TCOM.1986.1096468..
M Sabin, , , R Gray. . Product code vector quantizers for speech waveform coding. . Global Telecommunications Conf, , 1982. . p.1087--1091. . DOI:10.1109/CVPR.2007.383266http://doi.org/10.1109/CVPR.2007.383266..
M Sabin, , , R Gray. . Product code vector quantizers for waveform and voice coding. . IEEE Trans Acoust Speech Signal Process, , 1984. . 32((3):):474--488. . DOI:10.1109/TASSP.1984.1164346http://doi.org/10.1109/TASSP.1984.1164346..
P Schnemann. . A generalized solution of the orthogonal Procrustes problem. . Psychometrika, , 1966. . 31((1):):1--10. . DOI:10.1007/bf02289451http://doi.org/10.1007/bf02289451..
CE Shannon. . A mathematical theory of communication. . Bell Syst Tech J, , 1948. . 27((3):):379--423. . DOI:10.1002/j.1538-7305.1948.tb01338.xhttp://doi.org/10.1002/j.1538-7305.1948.tb01338.x..
CE Shannon. . Coding theorems for a discrete source with a fidelity criterion. . IRE National Convention Record, Part 4, , 1959. . p.93--126. . DOI:10.1109/9780470544242.ch21http://doi.org/10.1109/9780470544242.ch21..
C Silpa-Anan, , , R Hartley. . Optimized KD-trees for fast image descriptor matching. . IEEE Conf on Computer Vision and Pattern Recognition, , 2008. . p.1--8. . DOI:10.1109/CVPR.2008.4587638http://doi.org/10.1109/CVPR.2008.4587638..
J Sivic, , , A Zisserman. . Video Google: a text retrieval approach to object matching in videos. . 9th IEEE Int Conf on Computer Vision, , 2003. . p.1470--1477. . DOI:10.1109/ICCV.2003.1238663http://doi.org/10.1109/ICCV.2003.1238663..
GE Tsekouras, , , DM Tsolakis. . Fuzzy clustering-based vector quantization for image compression. . In: Chatterjee A, Siarry P (Eds.), Computational Intelligence in Image Processing. Springer Berlin Heidelberg, , 2013. . p.93--105. . DOI:10.1007/978-3-642-30621-1_5http://doi.org/10.1007/978-3-642-30621-1_5..
GE Tsekouras, , , M Antonios, , , C Anagnostopoulos, , , 等. . Improved batch fuzzy learning vector quantization for image compression. . Inform Sci, , 2008. . 178((20):):3895--3907. . DOI:10.1016/j.ins.2008.05.017http://doi.org/10.1016/j.ins.2008.05.017..
T Tuytelaars, , , C Schmid. . Vector quantizing feature space with a regular lattice. . IEEE 11th Int Conf on Computer Vision, , 2007. . p.1--8. . DOI:10.1109/ICCV.2007.4408924http://doi.org/10.1109/ICCV.2007.4408924..
JF Wang, , , JD Wang, , , JK Song, , , 等. . Optimized Cartesian k-means. . IEEE Trans Knowl Data Eng, , 2014. . 27((1):):180--192. . DOI:10.1109/TKDE.2014.2324592http://doi.org/10.1109/TKDE.2014.2324592..
BC Wei, , , T Guan, , , JQ Yu. . Projected residual vector quantization for ANN search. . IEEE Multim, , 2014. . 21((3):):41--51. . DOI:10.1109/MMUL.2013.65http://doi.org/10.1109/MMUL.2013.65..
Y Weiss, , , A Torralba, , , R Fergus. . Spectral hashing. . 20thInt Conf on Neural Information Processing Systems, , 2008. . p.1753--1760. . ..
Y Xia, , , KM He, , , F Wen, , , 等. . Joint inverted indexing. . IEEE Int Conf on Computer Vision, , 2013. . p.3416--3423. . DOI:10.1109/ICCV.2013.424http://doi.org/10.1109/ICCV.2013.424..
JB Yuan, , , XW Liu. . Product tree quantization for approximate nearest neighbor search. . IEEE Int Conf on Image Processing, , 2015a. . p.2035--2039. . DOI:10.1109/ICIP.2015.7351158http://doi.org/10.1109/ICIP.2015.7351158..
JB Yuan, , , XW Liu. . Transformed residual quantization for approximate nearest neighbor search. . arXiv:1512.06925, , 2015b. ..
L Zhang, , , M Zhang, , , Q Pan, , , 等. . An effective image coding method using lattice vector quantization in wavelet domain. . Int J Signal Process Image Process Patt Recogn, , 2014. . 7((2):):305--316. . DOI:10.14257/IJSIP.2014.7.2.28http://doi.org/10.14257/IJSIP.2014.7.2.28..
T Zhang, , , C Du, , , JD Wang. . Composite quantization for approximate nearest neighbor search. . 31thInt Conf on Machine Learning, , 2014. . p.838--846. . ..
T Zhang, , , GJ Qi, , , JH Tang, , , 等. . Sparse composite quantization. . IEEE Conf on Computer Vision and Pattern Recognition, , 2015. . p.4548--4556. . DOI:10.1109/CVPR.2015.7299085http://doi.org/10.1109/CVPR.2015.7299085..
关联资源
相关文章
相关作者
相关机构