Parametric and nonparametric residual vector quantization optimizations for ANN search

详细信息    查看全文

• 作者：Dan Guo^a ; ^{guodan@hfut.edu.cn" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Chuanqing Li^a ; ^{lichuanqing@mail.hfut.edu.cn" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Lv Wu^b ; ^{wulv@whut.edu.cn" class="auth_mail" title="E-mail the corresponding author}Author Vitae
• 关键词：Residual vector quantization ; Vector quantization optimization ; Parametric optimization ; Nonparametric optimization ; Stage codebook
• 刊名：Neurocomputing
• 出版年：2016
• 出版时间：12 December 2016
• 年：2016
• 卷：217
• 期：Complete
• 页码：92-102
• 全文大小：1047 K

文摘

For approximate nearest neighbor (ANN) search in many vision-based applications, vector quantization (VQ) is an efficient compact encoding technology. A representative approach of VQ is product quantization (PQ) which quantizes subspaces separately by Cartesian product and achieves high accuracy. But its space decomposition still leads to quantization distortion. This paper presents two optimized solutions based on residual vector quantization (RVQ). Different from PQ, RVQ simulates restoring quantization error by multi-stage quantizers instead of decomposing it. To further optimize codebook and space decomposition, we try to get a better discriminated space projection. Then an orthonormal matrix R is generated. The RVQ's nonparametric solution alternately optimizes R and stage-codebooks by Singular Value Decomposition (SVD) in multiple iterations. The RVQ's parametric solution assumes that data are subject to Gaussian distribution and uses Eigenvalue Allocation to get each stage-matrix {R_l}(1≤l≤L) at once, where L is the stage number of RVQ. Compared to various optimized PQ-based methods, our methods have good superiority on restoring quantization error.