2011年IEEE论文：乘积量化提升图像检索效率

需积分: 50 175 浏览量更新于2024-07-19 1 收藏 721KB PDF 举报

在信息技术领域，特别是在图像检索技术中，乘积量化（Product Quantization, PQ）是一种重要的近邻搜索方法，首次被提出并详细阐述于2011年发表在IEEE Transactions on Pattern Analysis and Machine Intelligence（TPAMI）上的一篇论文，由Hervé Jégou、Matthijs Douze和Cordelia Schmid共同完成，论文编号为inria-00514462v1。这篇论文的重要性在于它革新了传统的图像索引方法，使得大规模数据集中的高效近邻查询成为可能。乘积量化的核心思想是将高维向量空间中的数据进行分块并量化，通过将每个维度的子空间进行独立的离散化，形成一个由多个小的量化码书组成的复合码书。这种方法可以显著减少存储空间的需求，同时保持一定的查询精度。传统的欧几里得距离搜索在高维空间中效率低下，而PQ通过将查询过程分解为一系列简单的比较操作，极大地提高了查询速度，特别是在大数据场景下，如社交媒体图片搜索或视频检索等。该论文首先详细介绍了乘积量化的工作原理，包括如何将原始特征向量分解成多个子向量，以及如何使用不同的量化策略（如均匀量化或非均匀量化）来压缩这些子向量。然后，作者探讨了编码和解码过程，以及如何通过编码后的码本来近似原始数据的分布，从而找到最接近查询样本的邻居。为了保证查询质量，论文还讨论了如何选择合适的量化粒度和编码树结构，以及如何通过在线学习或预训练的方法优化这些参数。此外，为了平衡存储成本和查询性能，作者提出了一种称为“组分解”的技术，进一步提升了搜索效率。论文最后展示了乘积量化在实际应用中的效果，包括图像检索任务上的实验结果，证明了其在大规模数据集上的高效性和准确性。尽管最初的版本发表于2011年，但后续的研究和优化使其成为了现代计算机视觉和信息检索领域不可或缺的技术之一，为后续的多模态数据搜索、深度学习加速和分布式计算提供了坚实的基础。总结来说，乘积量化是一项关键的IT技术，它在图像检索领域的革新性工作推动了计算机视觉、搜索引擎和大数据处理的发展，成为了提高近邻搜索性能的重要工具。通过深入理解其原理、优化方法和应用场景，IT专业人士能够更好地利用这一技术来解决实际问题。

[21] uses a binary signature to reﬁne quantized SIFT

or GIST descriptors in a bag-of-features image search

framework.

In this paper, we construct short codes using quanti-

zation. The goal is to estimate distances using vector-

to-centroid distances, i.e., the query vector is not quan-

tized, codes are assigned to the database vectors only.

This reduces the quantization noise and subsequently

improves the search quality. To obtain precise distances,

the quantization error must be limited. Therefore, the

total number

k of centroids should be sufﬁciently large,

e.g., k = 2

for 64-bit codes. This raises several issues

on how to learn the codebook and assign a vector. First,

the number of samples required to learn the quantizer

is huge, i.e., several times

k. Second, the complexity of

the algorithm itself is prohibitive. Finally, the amount of

computer memory available on Earth is not sufﬁcient to

store the ﬂoating point values representing the centroids.

The hierarchical k-means see (HKM) improves the

efﬁciency of the learning stage and of the corresponding

assignment procedure [15]. However, the aforementioned

limitations still apply, in particular with respect to mem-

ory usage and size of the learning set. Another possibility

are scalar quantizers, but they offer poor quantization er-

ror properties in terms of the trade-off between memory

and reconstruction error. Lattice quantizers offer better

quantization properties for uniform vector distributions,

but this condition is rarely satisﬁed by real world vectors.

In practice, these quantizers perform signiﬁcantly worse

than k-means in indexing tasks [22]. In this paper, we

focus on product quantizers. To our knowledge, such a

semi-structured quantizer has never been considered in

any nearest neighbor search method.

The advantages of our method are twofold. First, the

number of possible distances is signiﬁcantly higher than

for competing Hamming embedding methods [20], [17],

[19], as the Hamming space used in these techniques

allows for a few distinct distances only. Second, as a

byproduct of the method, we get an estimation of the

expected squared distance, which is required for

ε-radius

search or for using Lowe’s distance ratio criterion [23].

The motivation of using the Hamming space in [20],

[17], [19] is to compute distances efﬁciently. Note, how-

ever, that one of the fastest ways to compute Hamming

distances consists in using table lookups. Our method

uses a similar number of table lookups, resulting in

comparable efﬁciency.

An exhaustive comparison of the query vector with all

codes is prohibitive for very large datasets. We, therefore,

introduce a modiﬁed inverted ﬁle structure to rapidly

access the most relevant vectors. A coarse quantizer

is used to implement this inverted ﬁle structure, where

vectors corresponding to a cluster (index) are stored in

the associated list. The vectors in the list are represented

by short codes, computed by our product quantizer,

which is used here to encode the residual vector with

respect to the cluster center.

The interest of our method is validated on two

kinds of vectors, namely local SIFT [23] and global

GIST [18] descriptors. A comparison with the state of

the art shows that our approach outperforms existing

techniques, in particular spectral hashing [19], Hamming

embedding [20] and FLANN [9].

Our paper is organized as follows. Section II intro-

duces the notations for quantization as well as the prod-

uct quantizer used by our method. Section III presents

our approach for NN search and Section IV introduces

the structure used to avoid exhaustive search. An evalua-

tion of the parameters of our approach and a comparison

with the state of the art is given in Section V.

II. B

ACKGROUND: QUANTIZATION, PRODUCT

QUANTIZER

A large body of literature is available on vector

quantization, see [24] for a survey. In this section, we

restrict our presentation to the notations and concepts

used in the rest of the paper.

A. Vector quantization

Quantization is a destructive process which has been

extensively studied in information theory [24]. Its pur-

pose is to reduce the cardinality of the representation

space, in particular when the input data is real-valued.

Formally, a quantizer is a function

q mapping a D-

dimensional vector x ∈ R

to a vector q(x) ∈ C =

; i ∈ I}, where the index set I is from now on

assumed to be ﬁnite:

I = 0 . . . k − 1. The reproduction

values c

are called centroids. The set of reproduction

values

C is the codebook of size k.

The set V

of vectors mapped to a given index i is

referred to as a (Voronoi) cell, and deﬁned as

, {x ∈ R

: q(x) = c

(2)

The

k cells of a quantizer form a partition of R

. By

deﬁnition, all the vectors lying in the same cell

are

reconstructed by the same centroid c

. The quality of a

quantizer is usually measured by the mean squared error

between the input vector

x and its reproduction value

q(x):

MSE(q) = E



d(q(x), x)



p(x) d



q(x), x



dx,

(3)

剩余14页未读，继续阅读

我们去桥东吧

粉丝: 3
资源: 1

2011年IEEE论文：乘积量化提升图像检索效率

Product Quantization for Nearest Neighbor Search

乘积量化 特征匹配

product quantization SDC算法在Windows下的实现

quantization bit 对信号量化的影响

数字图像的quantization parameters有哪些

AttributeError: quantization

向量量化模型有哪些，举例，分别作用

神经网络模型压缩之量化神经网络模型压缩之量化

python实现得到数字图像的quantization parameters

pytorch的Quantization介绍

最新资源

乘积量化特征匹配