论文总字数：23632字

目 录

1绪论 1

1.1研究目的与意义 1

1.2 国内外发展现状 1

2相关研究的介绍 2

2.1 最近邻搜索 2

2.2 K-means算法 2

2.2.1 概念 2

2.2.2 主要思想 2

2.2.3 注意问题 2

2.3高维数据的快速最近邻算法FLANN 3

2.3.1简介 3

2.3.2快速近似NN匹配 3

2.4 矢量量化 4

3乘积量化 5

3.1乘积量化 5

3.2倒排索引 6

3.2.1 背景 6

3.2.2 图像倒排索引 6

3.2.3粗糙量化器 6

3.3搜索算法 7

4 乘积量化核心代码 8

4.1 pq_test.m 8

4.2 pq_test_load_vectors.m 9

4.3 pq_test_compute_stats.m 10

4.4 pq_search.m 11

4.5 pq_new.m 11

4.6 pq_assign.m 12

4.7 ivfpq_search.m 12

4.8 ivfpq_new.m 13

4.9 ivfpq_assign.m 14

5实验过程 14

5.1 实验数据集 14

5.2 实验结果 14

5.2.1 ADC乘积量化编码 14

5.2.2 IVFADC乘积量化编码 16

5.3 结果分析 17

5.3.1 ADC与IVFADC的比较 17

5.3.2 与其他搜索方法的比较 17

6优化的乘积量化 19

6.1 量化失真作为目标函数 20

6.2 最优乘积量化 20

6.2.1 非参数解决办法 21

6.2.2 参数解决办法 22

6.2.3 非参数和参数方法的比较---组合性 23

7结论 23

8讨论 23

图像索引技术的设计与实现

吴伟

，China

Abstract：Product quantification is an effective method to solve the problem of the balance between consumption and memory retrieval efficiency. It is mainly targeted at high-dimensional vector retrieval problems. Product quantification algorithm The main idea is to decompose the space to low-dimensional subspace Cartesian product, and were quantified for each subspace. A product capable of producing very large quantizer codebook in low memory consumption, because only subspace quantized into codeword will be stored.

This paper mainly for the method were tested and the, due to limited conditions, I debug the the matlab version of the program, and because of the need to Yael library function as the premise, had to in Linux environment running. Experimental results show that, compared to the traditional SH algorithm, using this index technology, can achieve a good effect in the query accuracy and memory footprint.

First, I will introduce the background of the image index and the most advanced algorithms outstanding, and comb main idea, and then I will combine the code to tell how the index structure is set up, of course, I will make a final summary on how to optimize the product quantization algorithm own conjecture and opinion.

Keywords: nearest neighbor search；product quantification；high-dimensional image index；inverted file index

1绪论

1.1研究目的与意义

随着多媒体技术的飞速发展，图像存储的不断扩充，图像索引技术也必须适应新的需求。因此，图像索引技术的更新和改进在许多多媒体应用上有很重要的作用。

近似搜索在数据挖掘分类技术中是最简单的方法之一，但是对于数据个数较大的数据集，线性搜索寻找KNN时间消耗太大，内存占用也是巨大的。为了研究更加完善和效率更高的索引结构，引入了基于乘积量化的近邻搜索算法，这个算法是以在内存和效率之间达到平衡为目的，既能减少图像索引占用的内存，又能得到较好的检索质量和较快的检索速度。这种技术允许在内存量有限大矢量数据集索引的搜索，乘积量化的优势在于能从少量的类别通过笛卡尔积运算得到大量的类别。乘积量化算法将大搜索空间分解为晓得搜索空间从而提升搜索效率，这个对于容量非常大的图像搜索来说是非常有意义的。

1.2 国内外发展现状

20世纪70年代，数据库方面的研究人员就如何对图像资源进行有效的管理和查询开始了研究，从最初的基于文本的图像检索到后来的基于内容的检索技术。图像索引的结构也有了很大的转变，其中Herve Jegou在2011年提出的基于乘积量化的近邻搜索算法是一种非常优化的算法，它的搜索精度优于三个国家的最先进的方法，可扩展性进行验证的数据集有二十亿个向量。

一些多维的索引方法，例如流行的KD树或者其他分支界限法都是被提出来减少搜索时间的，但是对于高维度来说这些方法没有强力详尽的距离计算有效，它的复杂度为O（nD）。有大量的关于索引算法的文献通过近邻搜索算法克服了这个问题。这些算法的共同关键思想时发现邻近算法有高概率的唯一，而不是概率1。大部分的努力一直致力于欧几里德距离，尽管最近提出了其他归纳指标。Herve Jegou考虑到欧几里德距离，这与许多应用程序有关。在这种情况下，一个最流行的ANN算法是欧几里得位置敏感哈希算法，提供了理论保证搜索质量有限的假设。它已经成功的用于局部描述符和3D对象索引。

相比基于ANN算法通常是检索质量和效率之间的权衡。然而，这种权衡的索引结构没有考虑索引结构。对于E2LSH,内存使用甚至可能高于原来的向量。此外,E2LSH和FLANN需要执行最后的评估步骤基于精确L2距离,这需要索引向量存储在主内存访问速度是很重要的。这个约束严重限制向量的个数,可以由这些算法处理。直到最近,研究人员想出了方法限制了内存的使用。Herve Jegou等人提出的近邻搜索就是有效平衡搜索效率和内存使用的技术。

乘积量化是由Herve Jegou等人2011年在IEEEE上发表的论文《product quantization for approximate nearest neighbor》中提出来的。这个算法是以在内存和效率之间达到平衡为目的，既能减少图像索引占用的内存，又能得到较好的检索质量和较快的检索速度。对于任何基于固定维数特征的事物，它可以应用到其索引结构的建立及检索上。它属于ANN(approximate nearest neighbor)算法。与它相关的算法有E2LSH（Euclidean Locality-Sensitive Hashing）， KD-trees，K-means。

  Herve Jegou在这篇论文中给出了一个实现ADC和IVFADC距离计算的简单的matlab版本。提供这个试验是为了阐述说明乘积量化方法在性能和内存占用之间的平衡是优于国内外最先进的搜索技术的。

2相关研究的介绍

2.1 最近邻搜索

运用特征聚合的方法，将图片做成定长向量，作为图像的表达形式。

这样面临两个问题：1、存储开销大：数据库占用内存十分大，而内存的占用直接决定了系统的开销。

2、搜索速度慢：从数据库图像中查找与给定向量相似度最高的图像，需要将给定图像的表达向量和数据库的所有表达向量逐个比较，才能找到距离最近的向量，这样的过程十分耗时。

因此，为了解决上述两个问题，需要将表达图像特征的向量进行压缩，得到更为紧凑的表达，并且使得搜索速度大幅度提升。这就关系到了一个最近邻搜索问题，即在一个大的数据库中，需要找出与查询向量最近的一个或者多个向量。

最近邻搜索大致分为两种，一种是线性搜索算法，需要访问数据库的所有向量，主要方法有二进制编码。还有一种是非线性搜索方法，不需要访问数据库的所有向量，主要方法为基于倒排表搜索的方法。

2.2 K-means算法

2.2.1 概念

K-means算法是一种早期就被提出来的聚类算法，它采用距离作为相似性的评价指标，通过计算两个向量的距离来判断图像的相似度。该算法把簇当作是距离靠近的向量组成，为了得到紧凑而且独立的簇。

2.2.2 主要思想

计算方法如下：

1. 从数据集中随机选取k个中心点作为质心
2. 遍历所有数据，将每个数据划分到最近的质心的类中
3. 计算每个聚类的平均值，并且作为新的质点
4. 重复步骤2和3，直到k个质心收敛，或者达到最大迭代数

时间复杂度：O(t*K*m*n),其中t是迭代的次数，K是聚类的个数，m是记录数，

n是向量维数

剩余内容已隐藏，请支付后下载全文，论文总字数：23632字

相关图片展示：