英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

用于可伸缩图像搜索的局部化哈希

Brian Kulis Kristen Grauman

UC Berkeley EECS and ICSIBerkeley, CA 94720 kulis@eecs.berkeley.edu

UT Austin Computer Science Dept. Austin, TX 78712 grauman@cs.utexas.edu

摘要：

快速的检索方法对于大规模的和数据驱动的视觉应用很关键。最近的研究将高维特征或复杂距离函数嵌入低维汉明空间的方法可以有效搜索项目的地方。然而，现有的方法并不适用于高维的kernefied为内核嵌入底层特性时的数据是未知的。我们将展示如何泛化位置敏感的哈希以适应任意内核函数，使该算法在保证大量有用相似度的前提下，可以保留算法的子线性时间相似度搜索保证功能。由于许多成功的基于映像的内核具有未知的或不可计算的嵌入，这对于图像检索任务尤其有价值。我们验证在多个大规模数据集上进行了技术分析，并进行了验证实现准确和快速的性能，例如基于对象分类、特征匹配和基于内容检索。

1. 介绍

快速索引和搜索大型数据库是至关重要的基于内容的图像和视频检索-特别是给定的各种各样的可视数据的可用性不断增加有趣的领域，如科学图像数据，网上社区照片收集，新闻照片收集，或监测档案。最基本也是最基本的任务在图像搜索中最“近邻”的问题是:取a查询图像并准确找到最常见的例子与大型数据库中的类似。一个简单的解决方案查找邻居需要搜索所有n个数据库项然后根据它们与查询的相似性对它们进行排序，但是当n很大的时候，这个就变得非常昂贵或者当单个相似函数的值是昂贵的计算。对于视觉应用程序，这种复杂性被通常最有效的事实放大了表现形式是高维的或结构化的，并且是最好的已知的距离函数需要大量的计算来比较一对对象。为了使大规模搜索变得实用，视觉研究人员最近有没有研究过近似相似搜索技术，这种技术牺牲了可预测的准确性损失甚至允许对高维输入进行快速查询[25,24,12,16,4]。解决这个问题的方法，大多数值得注意的是，位置敏感的哈希(LSH)[10,3]提供了在(1 e)次内检索项的概率保证最优相似度，查询次数为次线性关于n，基本思想是计算随机哈希函数保证类似例子的高碰撞概率。本着同样的精神，一个数字的方法展示了如何形成低维二进制嵌入，以捕获更昂贵的距离函数[1,28,22,31]。这一行的工作显示了相当大的希望，为各种图像搜索任务，如近重复检索，基于实例的对象识别，姿态估计和特征匹配。尽管哈希算法在视觉相似性搜索方面取得了成功任务，现有的技术有一些重要的限制。当前的方法通常假设要散列的数据来自多维向量空间，需要数据的底层嵌入必须是显式的已知的和可计算的。例如，LSH依赖于带有输入向量的随机投影;光谱散列(31)假设向量具有已知的概率分布。这是一个有问题的限制，考虑到许多最近成功的视觉结果使用核心函数潜在的嵌入只被隐式地知道(例如，只有内核函数是可计算的)。到目前为止，使用LSH及其变体搜索数据是不可能的许多强大的内核——包括许多专为图像比较而设计的内核[33,34,30]，as还有一些基本的常用函数，比如高斯函数RBF。此外，由于视觉表现往往是最自然编码的结构化输入(例如，集，图，树)，缺乏具有性能的快速搜索方法对灵活内核的保证是不方便的。

在这篇文章中，我们提出了一种基于lsh的技术在任意内核上执行快速相似搜索功能。问题如下:给定一个核函数

（1-1）

和n的一个数据库对象,如何快速找到最相似的项目用核函数表示的查询对象q，即，argmaxikappa;(q, xi) ?就像标准的LSH，哈希函数包括计算随机投影;但是,与标准LSH，这些随机投影只使用核函数和稀疏集的例子来构造来自数据库本身。我们的主要技术贡献是制定LSH输入所需的随机投影内核空间。我们的建设依赖于适当的利用的中心极限定理，它允许我们使用数据库中的项来近似一个随机向量。的得到的方案，我们称之为kerneised LSH (KLSH)概括激光冲徊化时场景特征空间嵌入(phi;(x)phi;(y))要么是未知或不可数的。我们用几个可视化的实例验证了我们的方案搜索任务。对于目标识别，我们给出的结果并展示了我们的哈希方案在此数据集上的性能优于现有的哈希方法可以计算任意内核上的哈希函数。对于具有较大数据库的特性索引，我们将在本地斑块的照片旅游数据集[26,14]。最后,我们用8000万的小图像数据集做实验图像[27]，以展示我们的技术的缩放能力到非常大的数据库。因为我们的算法支持快速近似搜索任意的内核，我们现在可以访问许多人需要更广泛的相似函数类基于内容的检索应用程序。

1. 相关工作

在这一节中，我们将回顾快速搜索算法的相关工作及其在视觉搜索问题中的应用。数据结构使用空间分区和递归超平面分解(例如,kminus;d树[9])提供一个ef -精确搜索低维矢量数据的有效方法，然而，在实践中，它们在高维数据中会出现故障，并且不能提供比最糟糕的线性查询时间保证更好的性能。由于高维图像描述符通常用于对象识别，已经探索了减轻这些因素的方法作为层次特征量化[18]，决策树[19]，优先级队列[2]。基于树的搜索结构可以使用任意度量[29,5]，通过利用三角形不等式消除了向量空间的假设。然而,在实践中，需要选择有用的分区策略很好的启发式，而且，尽管使用对数查询时间对于期望，矩阵树方法也可以退化为根据分布对所有项进行线性时间扫描表示数据集的距离。随机近似相似搜索算法已设计为保留查询时间保证，即使是高维的输入。位置敏感哈希[10,3]通过高度哈希提供了次线性时间搜索类似的例子一起出现在哈希表中;激光冲徊化功能容纳汉明距离[15]，内积[3]，p规范[6]，归一化部分匹配[12]，并且学到了Mahalanobis metrics[16]都是在之前的工作中开发出来的。视觉研究人员已经证明了这类方法在各种图像搜索中的有效性应用程序，包括形状匹配、位姿推断和词袋索引[25,24,12,16,4]。然而,因此到目前为止，LSH仍然不允许使用任意的内核函数。嵌入函数提供了另一种有用的映射方法昂贵的距离函数在计算上更易于管理。最近的工作已经考虑了如何构造或学习一种可以保持所需距离函数的嵌入，通常是为了映射到一个更容易的低维空间可搜索已知的技术[1,20,28,22,31]。这些方法都与LSH有关，因为两者都要求很小可用于对类似输入进行编码的“键”，这些键通常存在于Hamming空间中。虽然大多数工作通过向量输入，[1]中的技术接受一般的距离函数，尽管它的训练过程是基于启动的是相当昂贵的，搜索是通过线性扫描完成的。最近的“光谱哈希”算法[31]就要求这样数据来自欧几里得空间且分布均匀

3.背景：Locality-Sensitive

哈希我们首先简要回顾一下位置敏感的哈希(LSH)。假设我们的数据库是向量的集合x1,hellip;给定一个查询向量q，我们感兴趣在数据库中查找与查询最相似的项。LSH背后的基本思想是将数据投影到低维二进制(汉明)空间;也就是说,每个数据点映射到b位向量，称为哈希键。如果这个投影被恰当地执行，我们可以发现在时间上近似最近的邻居是非线性的哈希键是通过应用b二进制值哈希来构造的功能h1,hellip;hellip;， hb到每个数据库对象。为了有效，每个哈希函数h必须满足localitysensitive哈希属性:

, （3-1）

当sim(xi, xj ) isin; [0, 1]是相似度函数的兴趣时。直觉是这样的:如果我们只能依靠高度相似的例子在哈希表中碰撞在一起(即，分配相同的哈希键）则然后在查询时，将显示最相似的示例直接哈希到存储桶，并且只需要搜索那些示例。给定有效的LSH函数，检索(1 e)-的查询时间对于汉明函数，近邻被

（3-2）

所限制距离[10]。因此，我们可以用hellip;来权衡hellip;的准确性搜索所需的查询时间。例如，考虑著名的内积相似度:

. （3-3）

在[3]中，Charikar显示a这个相似函数的哈希函数基于四舍五入随机超平面积的输出:

, （3-4）

其中r是一个随机超平面，来自与输入x维数相同的零均值多元高斯N(0,I)。这个哈希函数遵守localitysensitive哈希属性的事实源于Goemans的结果威廉姆森[11]，他展示了随机的r符合下公式：

. （3-5）

程序上，我们从N (0, I)中选择一个随机的向量r，然后为数据库中的每个x计算r^Tx，然后对a在b个随机向量上重复这个总共有b个哈希函数。然后，哈希表由哈希键及其指向数据项的指针。给定一个查询向量q，一个通过应用相同的方法计算它的哈希键哈希函数。查询散列到。中的某些桶哈希表，它与存储的例子。只搜索这些示例。

为了执行近似相似性搜索，我们使用[3]中的方法，该方法需要搜索k=1近似NN的符合：

（3-6）

的示例。给定数据库哈希键：

（3-7）

随机排列位的形式，和每个列表的排列哈希键是按字典顺序排序，形成M个排序的顺序。一个查询哈希键索引到每个排序的顺序与二进制搜索，最近的2M的例子是近似值最近的邻居。此外，我们还引入了一个参数这是搜索排序后的箱子时要考虑的可能的最近邻居的数量排列。有关详细信息，请参见[3]。以前，哈希函数是为用例设计的其中相似函数sim为p范数，马氏度规，或内积[6,16,3]。在这个工作,感兴趣的相似性函数是一个任意的内核函数：

（3-8）

对于一些(可能是未知的)嵌入函数phi;(·)。在下一节，我们将介绍绘制散列的算法对于任何内核满足Eqn.1的函数。

4.Kernelized Locality-Sensitive哈希

提出了随机超平面哈希方法charkar假设向量是显式表示的，因此r^Tx的符号很容易计算。我们现在考虑数据kernealized的情况;我们表示输入phi;(x)和假设底层嵌入可能未知或昂贵的计算。我们只能通过如下的内核函数访问数据

, （4-1）

因此目前尚不清楚如何计算散列函数的例子,RBF内核一个无限大的嵌入，让它看起来甚至不可能构造r。将LSH应用于此场景的挑战是如何从N(0,I)中构造一个向量r这样r^Tphi;(x)可以通过内核计算函数。

我们方法的主要思想是把r构造成a数据库项子集的加权和。适当的构造将允许随机超平面散列函数的计算完全通过核函数的计算，但也将确保r近似为高斯函数。考虑每个数据点phi;(xi)从数据库作为一个矢量D意味着mu;和一些潜在的分布协方差Sigma;,通常是未知的。给定自然数t，定义函数如下：

, （4-2）

其中S是从D中选择i.id.的一组t数据库对象。中间限值[21]定理告诉我们,对于足够大t,如下随机向量

（4-3）

是根据分发的多元高斯N(0，Sigma;)。使用变白变换,向量Sigma;^1/2(ztilde;t)进行分配到N (0, I)，恰好是Eqn. 2中要求的分布。

因此,表示我们的随机向量为r =Sigma;1/2（ztilde;t）,并且哈希函数h(phi;(x))由如下函数得到：

. （4-4）

协方差矩阵Sigma;和数据的均值mu;是未知的，所以必须通过样本近似的数据。我们选择一组p个数据库对象，其中我们不损失通用性地表示为第一个p项phi;(x1)、hellip;phi;(xp)的数据库(我们将讨论选择的值)。现在我们可以(含蓄地)估计一下均值为

. （4-5）

从概念上讲，我们也可以形成了协方差矩阵Sigma;p样品,我们不能显式地存储这个矩阵。为了计算h(phi;(x)),我们将使用一种技术类似于在内核PCA[23]中使用的项目协方差矩阵的特征向量。在我们的例子中,如果Sigma;的特征分解是VLambda;V ^T,然后Sigma;^1/2 =VLambda;^(1/2)V^ T。因此可以得到如下公式：

, （4-6）

在p个采样点上定义一个核矩阵，将其表示为K,让其特征分解为K = UTheta;U^T。注意Lambda;的非零特征值等于零Theta;的特征值。进一步，表示的第k个特征向量的第k个特征向量核矩阵是uk。根据核的推导PCA，我们可以计算投影,公式如下

, （4-7）

在phi;(xi)采样数据点。我们完成的计算h(phi;(x))通过执行这个计算k特征向量,从而导致以下表达式:

. （4-8）

我们用Eqn. 4替换每一个特征向量内积并展开得到的表达式为:

. （4-9）

现在我们重新排序求和和并重新组织项:

. （4-10）

最后,我们利用

（4-11）

的事实并且进一步简化得到:

， （4-12）

这意味着高斯随机向量可以表示为

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[19678]，资料为PDF文档或Word文档，PDF文档可免费转换为Word