英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
可扩展的近重复SIFT图像匹配算法的修剪改进
摘要
在大的图像集合中进行图像的检测是一项艰巨的任务，因为图像是很少相同的。如裁剪，旋转和轻微的光度变化的几何变化是不适合基于内容的检索技术，而数字水印技术的实际检索应用有限。最近的变换尺度不变特征的应用程序（SIFT）兴趣点对这个领域表现出较高的效率，但可仍然有生成每个图像的特征点的数量太大的问题。在这项工作中，我们发现，该应用程序域，在损失效果几乎可以忽略不计的前提下，SIFT兴趣点可以被大幅削减来大量减少内存需求和查询的运行时间。研究表明，与使用原SIFT特征相比，修剪功能扩展之后的算法在包含成千上万的图像集中表现较好。
关键字：近重复图像匹配，近重复图像
1．引言
在网络上，我们经常会发现复制的，不同版本的，甚至只有部分图像的缩略图，或相同的数字图像的不同形式，在法律上或以其他方式，以不同的来源保存。这些图像通常几乎是相同的，但他们并没有被识别为相同，这是因为共同的图像处理，例如转换为灰度，在色彩平衡和对比度上的转换，缩放，旋转，裁剪，和过滤图像。这种图像的变种通常被称为近重复图像。
在多数情况下，重复的和近重复图像的存储和检索可能是不必要的，并且来自网络的有关图像，可能进一步存在著作权的侵犯。然而，这些近重复图像的检测是一个艰巨的任务，因为两个图像版本很少相同。它们可以以文件名，格式和大小不同; 由于在不同的软件编码标准的多样，简单地保存图像可能会导致按位的差异。
虽然复制的数字图像的检测已在数字水印领域得到广泛研究[Hartung amp; Kutter 1999, Johnson, Duricamp; Jajodia 1999, Kang, Huang amp; Shi 2002, Kang, Huang, Shi amp; Lin 2003]，但这些方法在特定的情况下却不适用于检索应用。[Luamp; Hsu 2005, Qamra, Meng amp; Chang 2005]。同样，也不适用于基于内容的检索技术[Smeulders, Worring, Santini, Gupta amp; Jain 2000] - 一个很好的研究领域 – 且不适用于他们依据图像的颜色，纹理或形状相似的特征而设计的更广泛的匹配;这些技术已被证明效果有限[Chang, Wang amp; Wiederhold 1998, Sebe, Lew amp; Huijsmans 1999, Luo amp; Nascimento 2003]。
对于近重复的图像的检索的任务，Ke等人在2004年已经采用PCA-SIFT局部描述符，对大约20,000图像的中等大小的图像采集表现出近乎完美的精度，但没有讨论扩展性和效率方面的问题。在大型专有的图像采集方面，Qamra等在2005年对近重复检索提出感知距离函数，它使用图像的颜色和纹理特征;然而，它只侧重于有限的效果而只简短的讨论了效率方面。Lu 和 Hsu在2005年证明了图像散列技术用于20,000张近重复图像的检索有一定效果，其中改变的数目，虽然大，但有很大限制。
到目前为止，在这个领域中，只有Ke等人[2004]阐述了一个即使变化相对比较严重也确实是高精度的方法。然而，随着应用SIFT[2004罗威]一个固有的问题就是（代表与PCA-SIFT局部描述符）是大量的特征 - 从几百到几千 - 每幅图像都生成，其中每个特征是通过一个高维特征代表向量表示[K＆Sukthankar2004]。虽然这些大量的图像特征是使用局部性敏感哈希编号[吉奥尼斯，达克和1999年Motwani，Ke等人编入索引。2004]，但我们可以说，这样大量的特征对中度到大的图像集是不切实际的。
该SIFT探测器最初设计用于即使是很小的物体遮挡的稳健匹配;因此，对于这样的应用特征的数量至关重要[Lowe 2004, Ke amp; Sukthankar 2004]。我们假设只有一小部分子集特征需要近重复图像匹配，因为在这个领域最感兴趣的图像包含和原图相比高感性的相似性[Qamra et al. 2005]。在这项工作中，我们提出了一个修剪策略减少SIFT特征（结果PCA-SIFT的局部描述符）的数量，从而使这些描述符在含有成千上万的图像的大集合中匹配的很好。这样的剪枝策略同时降低了索引的大小和查询响应时间分别到之前方法的1/10和1/50，且对效率的影响很小。
在下面的章节中，我们描述了鲜明的局部描述符（主要是SIFT和PCA-SIFT）。在第三节，我们讨论使用局部敏感哈希索引结构；在第四节，我们介绍我们的修剪SIFT兴趣点的方法，并在第六节，我们描述评价方法和实验建立；第六节展现并讨论结果然后在第七节得出结论。
2. 特殊的局部描述符
计算了图像的局部描述符已被证明是对物体识别和健壮图像匹配很有效[Lowe 2004]。给定一个图像，这个想法是检测具有几何不变性和光度不变性，且使鲜明的局部描述符可以计算的每个图像区域（约兴趣点居中）。热门区域探测包括哈里斯点，哈里斯 - 拉普拉斯，哈里斯 - 仿射，黑森州 - 拉普拉斯和黑森州仿射;流行的描述符包括SIFT（尺度不变特征变换）[Lowe 2004]和PCA-SIFT [Ke amp; Suk-thankar 2004]，仅举几例。有关区域检测和局部描述符的完整调查，读者可以了解米科瓦伊奇克和施密德[2003]的工作。
在这项工作中，我们使用SIFT（尺度不变特征变换）检测仪 - 它使用类似黑森州 - 拉普拉斯地区 - 因为它已经被证明优于大多数现有的探测器[Mikolajczyk amp; Schmid 2003]。我们应用了PCA-SIFT的SIFT兴趣点的描述符，而不是原来的SIFT描述符，因为它已被报道为两个高度鲜明[Ke amp; Sukthankar 2004]和用于近重复图像检测非常有效[Ke et al. 2004]。
SIFT和PCA-SIFT描述符
该尺度不变特征变换（SIFT）[Lowe 2004]被设计为强大的在缩放，旋转和仿射变换下图像特征检测不变的。有在SIFT四个主要的计算阶段，用于提取一组图像特征，即尺度空间极值检测，关键点定位，定向分配以及生成局部描述符的。
在SIFT检测的第一阶段中，高斯差值（DOG）函数使用高斯金字塔，以确定在不同的位置和尺度下的局部峰值（关键点）。（这是通过查找局部尺度空间的高斯差值极值实现的）。在第二阶段，局部的不良和几个阈值水平不稳定的关键点都将被丢弃;主要是基于对比度水平及主曲率比[Lowe 2004]。所有稳定关键点被确定后，每个关键点在第三阶段被分配一个旋转不变性的主导方向。在主导取向的阈值的80％以内如果有多个取向，那么将会产生额外的关键点;因此，可以有多个关键点具有相同比例，位置，但不能有相同的取向。
不计算SIFT局部描述符，我们使用这已被证明是相对于其他描述符最出众的PCA-SIFT描述符[Mikolajczyk amp; Schmid 2003]。为了产生局部描述符，PCA-SIFT使用相同的信息作为原始SIFT描述，即，位置，规模，以及主导方向。PCA-SIFT并置为41times;41区域中的水平和垂直梯度地图 - 围绕关键点为中心的，旋转至其取向对准一个规范方向 - 以产生2times;39times;39=3042元件局部描述符（特征矢量）。
在有多个主导取向的情况下，使用一个独立的向量计算每个取向。然后，每个矢量被投影 - 使用主成分分析，为维数降低的常用技术 - 使用预先计算本征空间至低维特征空间。已经凭经验确定了N = 36为本地描述特征空间的近重复图像检索有良好表现;其中任意两个的PCA-SIFT的局部描述符在3000的欧几里德距离（L2范数）内被认为相似的（匹配）的。因此，在这项工作中，我们使用相同的设置。
PCA-SIFT的局部描述符的数量是由通过SIFT检测的关键点（取决于图像复杂程度）决定的，每幅图像通常有从几百到几千个。如此大量的索引的PCA-SIFT的局部描述符对大的图像集合是不切实际和昂贵的。我们后来发现，可以通过在第二阶段中改变的阈值来显著减少了SIFT产生关键点的数目，从而使匹配近重复图像的效率极大提高而准确性仅轻微损失。
索引的局部描述符
索引的一组36维的PCA-SIFT描述符，我们使用局部敏感散列（LSH）索引方案[Indyk amp; Motwani 1998, Gionis et al. 1999, Datar, Immorlica, Indyk amp; Mirrokni 2004, Ke et al. 2004, Bawa, Condie amp; Ganesan 2005] 在高维空间的近似最近邻匹配。
给定一组点（PCA-SIFT描述符）的P，在近似最邻近搜索的两点之间的距离可以被定义为：
其中q是查询点，以及d（q，P）为q的到最近的点P的距离。LSH的关键思想是使用一个系列的散列函数，以确保碰撞的两个点的概率和它们之间的距离是密切相关的。
一个散列函数可以被定义为g i（P）=（H 1（P），...，（HK（P）），其中i =1，...，L，其中k确定冲突的概率，并L 确定未匹配上的程度。更具体地说，在P上的元件之间的距离任何q，pisin;P上，该系列的散列函数是（R1，R2，P1，P2）敏感的[Gionis et al. 1999]：
其中beta;（Q，R）表示该组的r到q的距离内的元件的。另外地，要求p1gt; P 2和r1 lt;r2必须满足的局部性灵敏度。
这一系列函数可以被有效计算d维的汉明间距H d[Gionis et al. 1999]，由此每个d维矢量p（X1，...，XD）可以被映射到d lsquo;= Cd（其中C表示最大的p中的坐标），转化向量p为二进制海明字符串p。
对于给予的转化向量prsquo;，一个散列gI（P），对于i= 1，...，L，可以由矢量p的投影获得到坐标设置I I（其中I是由k个元素代替{1，...，d}的随机采样）基本上散列点p到 gi（p）。由于桶的数量可以根据集P的基数比较高，标准散列的第二个层次是用来映射gI（P）的内容到一个哈希表[Gionis et al. 1999]。因此，有一个总L- LSH表，每个都使用LSH函数从H d集合。每个散列表大小M的是使用确定为：
其中，n是一个点的集合中的总数，并且B，L，和k（对于功效临界），是根据经验分别确定为大小为20，20和450 [Ke et al. 2004];利用参数alpha;被选择为0.5。
对于给定的估计的哈希表，所有点共享相同的散列值（碰撞），由曼哈顿距离（L 1范数嵌入在海明空间），比那些不相同的更相互接近一些。因此，一个近似最近邻居匹配的搜索空间大大减少那些有着相同的哈希值的点。为了进一步消除伪匹配的数量，作为LSH索引结构基于L 1只返回近似匹配需要额外的验证步骤，而PCA-SIFT功能需要两个向量是一个L2之内的3000 （欧几里得）规范被视为匹配[Ke amp; Sukthankar 2004]。因此，所有的关键点匹配是后处理丢弃伪匹配。最后过滤阶段是使用稳健估计诸如随机采样一致性（RANSAC）施加[Fischler amp; Bolles 1981]以几何级数验证两个图像确实近重复，以确保高精度的返回答案。我们在我们的工作中采用相同的过滤。
对于查询评估，所有的候选匹配由LSH指数为每个查询返回的关键点。因此，每个查询图像被视为点集，模拟多点查询评估。为了有效地做到这一点，我们使用Ke等人使用的相同的框架。在那，我们维持两个辅助索引结构 - 文件表（FT）和关键点表（KT）-to地图SIFT关键点（和PCA-SIFT描述符）与其对应的图像;在KT的条目包括文件ID（FT指数位置）和关键点信息（x和y的位置，规模，方向和PCA-SIFT局部描述符）的。单个图像的查询评估的成本在很大程度上取决于在任何给定的图像的组密钥点P的基数。我们观察了很大的爬网图像采集，这意味着1900点查询到LSH索引单个图像查询的评价平均1900关键点;这是计算密集型和高度不切实际的大型图片集在线互动查询。
在下一节中，我们介绍我们的修剪SIFT兴趣点的方法。
修剪SIFT兴趣点
与SIFT检测器，计算关键点的数量典型地在10 3的顺序（这取决于图像内容，大小和复杂性）。这样的量的关键点往往是至关重要的对象识别，甚至是封闭的小物件，都可以方便可靠地匹配。然而，对于在大集合的检索的任务，例如大量关键点可以任何有效的索引结构减少到一个顺序搜索。
我们假设，即近重复图像检测的应用程序域可能不需要的全部关键点，并且通常是一个小的子集就足够了。合理的被认为接近重复的图像匹配的应用常常被定位于显示高知觉相似[Qamra et al. 2005];甚至裁剪图像（在一定程度上）将具有许多相似的特征（对象，对象，纹理和形状）到原始图像。
为了减少SIFT兴趣关键点的数量，我们改变施加到丢弃候选的局部峰值，具体地，低对比度（强度）的阈值。此前，0.03阈值经验观察 [Lowe 2004]物体识别的领域的工作，但它通常会产生大量的关键点。然而，使用几何验证技术如RANSAC[费什勒＆博尔斯1981]，只有少量的关键点 - 3-5 个- 所需的可靠的图像匹配[Lowe 2004, Ke et al. 2004]。
此列入阈值可以用来减少关键点集合的基数有两种方法：
1、选择的对比度值最显著的排名前N个的关键点；
2、提高列入阈值丢弃关键点。
这两种方法都可以用于减少关键点的数量。然而，第二种方法中，产生关键点的一个不稳定的数
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[153873]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
