为什么在图像检索里面使用到哈希（hashing）算法？

基于哈希算法的图像检索方法将图片的高维内容特征映射到汉明空间（二值空间）中,生成一个低维的哈希序列来表示一幅图片,降低了图像检索系统对计算机内存空间的要求,提高了检索速度,能更好的适应海量图片检索的要求。

最近或者最近邻问题在大规模的数据查询中用得非常多。但是他们都会遇到一个问题，就是"维数灾难"。也就是说当数据的维数太大的时候，之前的那些索引方法（如KD树）就不能起到作用，这时候新的方法就很有必要，哈希算法满足了这个要求。

?

相似性搜索算法的评价标准

为了解决相似性搜索问题,人们提出了很多相似性搜索的算法实现,而为了衡量这些算法的优劣,需要引入相似性搜索算法的评价机制。一般来讲,一个相似性搜索算法可以从以下几个方面进行评价

这个性质描述的是相似性搜索算法的查询质量。对于给定的查询请求,算法必须返回符合条件的查询结果,而且查询结果最好能和通过线性查找得到的结果一致。文本检索领域的两个著名指标可以用在此处来衡量查询质量,它们分别是召回率(recall)和精度(precision)。

召回率和精度的定义如下:

CBIR中的Hashing算法有哪些？

要解决这个问题，首先我们得用数学的方法将这个问题描述一下：

我们有一个包含个点的集合，，这样矩阵的形式就是。我们的目标是寻找到一个二元编码的集合，c表示编码的长度。对于每一个位我们使用，是超平面的系数。

从训练数据是否有Label（标记）上来分，CBIR中的hashing算法分为三类，监督学习，无监督学习，半监督学习。

?

监督学习

Semantic hashing (RBMs)

受限玻尔兹曼机是一个深度学习模型，每一层都表示一个受限玻尔兹曼机,最底层受限玻尔兹曼机的输入是原始高维数据,通过该受限玻尔兹曼机计算得到一个中间值,然后将这个中间值作为下一个受限玻尔兹曼机的输入,继续计算得到新的中间值,重复此过程,直到从顶层的受限玻尔兹曼机计算得到最终的编码结果。这个过程被称作预训练。而图的右半部分表示将这个深度学习模型展开之后,通过调整这个深度学习模型中每层之间的参数和权重,进而得到一个深度自动编码机的过程。这个过程被称作微调。

RBMs包括两个重要的步骤:无监督的训练和监督的调整。无监督训练阶段,利用

贪心训练算法逐步逐层的计算输入与输出之间的关系。通过对比度使得每一层的参数收敛。每一层的参数都作为计算下一层参数的输入。在调整阶段,加标签的数据被用来调整无监督训练阶段学习到的神经网络。

缺点：

实验证明,受限玻尔兹曼机索引算法可以得到较好的索引结果。但由于其自身模型的复杂性,导致其运行效率低下,需要花费较长时间来得到训练结果。

?

非监督学习

位置敏感哈希(Locality Sensitive Hashing LSH,1999)

LSH是最近比较流行的一种相似性搜索算法，它的基本思想是通过k个串联的具有位置敏感性的哈希函数将原始的数据空间映射到二维的数据空间，然后在查询时计算查询点的K维哈希值,根据该哈希值取得候选数据集,最后通过计算候选数据集中每个点与查询点的距离得到符合查询条件的结果。LSH具有较好的时间效率,而且在高维数据空间依然能够保持良好的性能,因此被广泛应用在很多领域。

?

这个方法其实是最简单的一种hash方法，只要产生k个哈希函数h（x），对于每一个数据点x，进行计算，就能得到hash值。

?

缺点：

位置敏感哈希索引算法极大地提高了高维数据索引的效率,解决了树形结构索引算法无法克服的效率问题,但是由于位置敏感哈希索引算法中采用了随机映射算法,使得索引结果不可控,在实际应用中结果不稳定,并且实验表明,随着索引编码位数的上升,索引结果提升缓慢。与其他语义哈希索引算法相比,位置

敏感哈希索引算法的索引结果准确率较低。

?

谱哈希（NIPS 08）

方法：

谱哈希索引算法根据索引编码应该满足的条件,对原始高维数据集进行谱分析,再通过放松限制条件,将该问题转换成拉普拉斯特征图的降维问题从而求解。然后谱哈希索引算法引入了特征函数的概念来处理训练集外数据的问题。整个算法流程如下:首先利用主成分分析法对原始高维数据进行降维处理,然后计算得到所有的解析特征函数(analytical eigenfunction), 最后将这些解析特征函数二值化从而得到最终的二元索引编码。

但是由于谱哈希索引算法在其索引编码过程中,直接应用了主成分分析法来

对高维特征进行降维处理,从而使得原始特征的每一维(例如视觉单词)都参与

到后续编码过程中,但是一般而言,给定一幅图像,其所蕴含的语义只需有限视

觉单词就能表达,而不用所有视觉单词来参与表达。由于没有处理冗余高维

特征的问题,谱哈希索引算法的结果受到一定影响。并且谱哈希索引算法假设了

原始高维数据均匀分布,从而选择了理论最优值0作为阈值。但是在实际应用中

数据并不能总是满足均匀分布这个条件,因此选择0作为阈值不适合所有的数据

集。

谱哈希的目标函数如下：

?

?

其中是相关性矩阵，;保证了索引编码是二进制结果，保证了所有编码结果的每位为-1或1的概率是相等的，即为50%；保证了索引编码结果每一位是互不相关的。

为了求解该公式, 谱哈希引入拉普拉斯矩阵L并且松弛的二元限制条件,于是公式求解转换成求解的特征值问题，即拉普拉斯特征图的降维。最后公式的解就是D – W的前k个最小特征值(除0以外)对应的特征向量。其中D是一个的对角矩阵，并且。为了解决训练集外图像索引编码的问题,可将特征向量转化为特征方程,通过有权重的拉普拉斯—贝特拉米算子的特征方程来实现。所求得的特征方程和特征解如下：

ITQ算法（2013）

这个方法是同学极力向我推荐的一个方法，主要原因就是方法简单，好理解，同时效果又很好。

该算法分为两部分，第一部分是PCA，第二部分是旋转迭代。

第一步是PCA：

根据半监督学习，我们的目标是使得每一位比特的方差最大，并且各自无关。这样我们就可以写出目标函数：

下面就是简单的将sgn去掉，也就是{-1,1}空间转化为连续空间，就能得到

是对 的松弛，我们可以理解为超平面互相垂直。同时，这跟PCA的目标函数相同，所以，可以使用PCA的方法。

第二步：迭代量化

假设是映射空间的一个向量，那么sgn(v)就是超方体（hypercube）的最近的顶点，那么损失函数越小，结果就越能保留数据的位置结构（locality structure）。回到第一步我们会发现，如果W是最优解，那么也是最优解，前提是R是一个的正交矩阵。因此，我们可以对映射数据进行正交变换，从而使得

这样，这个方程就变为通过旋转V来使得损失函数最小，解决这个问题的方法是一种类似于K均值的迭代量化方法。

固定R更新B。展开一下上式，就会变为以下形式：

所以，我们可以得到

其中。这样就能够得到。

固定B更新R。对于固定了B来求解R，这就是一个正交P问题(Orthogonal Procrustes problem)，直接通过一下方式来求得：首先用SVD分解的矩阵,，使得然后得到。

作者使用了50次的迭代，就能收敛了。

这样，这个简单的方法就结束了。

?

半监督学习

Semi-Supervised Hashing for Scalable Image Retrieval（2010 CVPR）

方法：

?

利用半监督哈希算法来进行图像检索是王骏等人2010年在CVPR上提出的,前面介绍的监督哈希算法和无监督哈希算法都有其明显的优缺点。无监督哈希算法

的速度相对于监督哈希算法来说要快,且不需要图库中的图片有任何标签,完全利用图片的内容特征来学习哈希函数,但这样也会失去图片标签带有的丰富的语义信息。监督哈希算法要求训练图片带有标签,利用了图片标签带有的丰富语义信息来学习哈希函数,但监督哈希算法的速度较慢。王骏提出一种半监督哈希算法，充分融合了无监督哈希和监督哈希算法的优点。

巨量的图片中有一小部分是带有标签的，剩余部分不带有标签，这是与现实情况相符的。半监督哈希要求训练库中有一小部分图片带有标签，这些标签信息提供监督信息。图片的内容特征提供非监督信息。结合监督信息和非监督信息来学习哈希函数。这一思想与现实情况完全相符。

半监督哈希的算法过程如下:

定义如下目标函数:

?

上式中,表示图片的哈希码序列的第k个,值为1或-1。为所要学习的向量。因为X是以0对称的，所以。表示图片i和j的标签一样或者说图片i和图片j相似, 表示图片i和图片j的标签不同或者说图片i和图片j不相似。

我们可以使用矩阵形式来表示上述式子，首先定义一个矩阵和带有成对标签信息的，我们对S进行如下定义：

最大化上述目标函数的意义是使得相似的图片或者标签相同的图片的哈希码的对应位均为1或-1，而标签不相同的图片的哈希码的对应位一个为1，令一个为-1，也就是说能保证相似图片的哈希码理论上一样，而不相似的图片哈希码相差大。目标函数写成矩阵形式如下:

另外假设，将X_L映射到K位比特的哈希代码，这样目标函数J(W)就可以被表示成这样：

用sgn()函数取代一下就能够得到

函数的意思是对矩阵里面每个元素使用sign函数

上式中只有监督信息成分,在实际的使用过程之中，尤其是当有标签的数量相对于整体数据库比较小的时候（）有过拟合的情况（overfitting），所以就需要加上"规则（regularization）"。根据谱哈希，希望产生的哈希编码能够独立，并且通过平衡切割数据，使得每一位多包含的信息量最大。能够满足平衡条件的 会将X分成相等的大小的两部分。

松弛目标函数：

上面式子提出的问题本身是一个NP问题，为了解决这个问题，我们要使用松弛技术。首先我们使用"signed magnitude"技术，这个技术在谱哈希中也是用到了，就是讲{-1,1}的哈希空间直接变换到实数R空间，这样目标函数就变为了：

之后松弛平衡分割,作者推导出这个式子，意味着平衡分割跟使得k位的方差最大是等价的：

之后目标函数又可以改写成为

令，这样我们就能得到

而正交的关系可以通过来松弛。这样一个最优化为题就被成功地转化为一个求解矩阵M的特征的问题：

这里是矩阵M最大的特征值，而是相应的特征向量。这样我们就成功地求取了W。

本身能达到这样已经不错了，但是作者在这个方法上面还更近了一步，作者认为还可以松弛正交限制。因为正交限制的作用是使得各个比特位不相关，但是这会导致问题。在大多数实际的数据库中，大方差只出现在很少的几个方向上，正交限制强迫我们去选择方差小的比特位，这样会导致低位的比特的质量不高，不能够包含足够的信息。这样，作者为了替代原来的hard constrains，而使用了惩罚项，这样的话目标函数就可以改写为：

这样就可以同归对W进行微分，来求解了：

然后拆开，就能够得到：

假如是正定的，那么这个方程将很好解，正定的条件也很简单，就是
。

我们假设，如果Q是正定的，那么Q可以改写为（Cholesky decomposition）。而,我们就能够得到。是矩阵M的最大的k个特征向量。