哈希与二值哈希的近似最近邻搜索优化方法

基于哈希的近似最近邻搜索将高维向量映射为二值哈希码，通过对比哈希码的汉明距离实现相似性查询。哈希方法的重点是相似性保持，即保持哈希空间的相似性关系与原始数据空间的相似性关系尽可能一致，这是影响基于哈希的近似最近邻搜索精度的关键。

一、哈希的基本概念

哈希是将图像的高维特征向量映射到低维空间、生成图像低维表示的过程。以二进制哈希码为例[7]:

给定一个样本点x∈RD，可以通过一系列哈希函数H＝{h1，h2，…，hK}计算一个K比特的二进制码y＝{y1，y2，…，yK}，即

其中，第k个比特yk＝hk(x)。可见，哈希函数执行的是从原始数据到二进制码的映射:hk:RD→B，这样一个二进制哈希编码过程就是样本点从原始空间到二进制空间(汉明空间)的一个映射:

式中，yi＝[h1(xi)，…，hk(xi)，…，hK(xi)]，yj＝[h1(xj)，…，hk(xj)，…，hK(xj)]。

哈希方法具有两大优点:一是对存储空间的要求大大降低。例如，存储8000万幅尺寸为32×32像素的图像数据需要600GB容量(数据格式为double类型)，如果转换为64bit的二进制码，则仅需600MB存储空间[7]；二是计算复杂度低，计算两个二进制哈希码之间的汉明距离仅需要位运算。哈希方法的缺点是由于损失了大量原始数据可能导致检索精度降低。因此，提升哈希方法的精度一直是研究人员关注的重点。Torralba等(2008)提出，以图像压缩为例，可以使用少量位数表示图像信息而不影响图像识别的准确率。因此，从理论上讲，哈希方法可以实现保证精度的同时减少检索时间[9]。

二、基于哈希的近似最近邻搜索算法

基于哈希的近似最近邻搜索包括哈希编码和哈希排序两个步骤，如图7-1所示。哈希编码过程又可以分为投影和量化两个阶段。哈希编码是设计哈希函数生成哈希码的过程，哈希函数设计的目标是尽可能保持原始空间中样本点之间的相似性关系；哈希排序是对数据库中的点进行排序的过程。

(www.xing528.com)

图7-1　基于哈希的近似最近邻搜索(Pipeline)

哈希编码一般遵循两个原则。一是码长短。码长短可以保证生成的哈希码占用较小的内存空间和保证高计算效率。二是保距。即原始空间中相似的样本点编码之后得到的二进制哈希码之间的汉明距离要小。此外，哈希编码一般还需要满足平衡性和独立性。平衡性指的是编码以后的所有点中为0和为1的编码各占一半，这样才能保证熵最大，哈希编码性能最好；独立性指的是不同哈希函数之间要相互独立，从而保证对数据空间进行最有效的分割，尽量避免信息冗余。

1.哈希函数的设计

哈希函数的目标是将样本表示成一串固定长度的二值编码(0/1或－1/＋1)，使得相似的样本具有相似的二值码。相似性保持是设计哈希函数最基本的原则。目前已经提出很多种设计哈希函数的方法，例如采用随机投影的超平面或者超球面作为哈希函数、通过成对标签约束或者三元组约束优化哈希函数参数、基于核方法构建哈希函数等。其中，最简单常用的是基于线性投影的哈希函数，式(7.6)给出第k个哈希函数的泛化形式:

经典的局部敏感哈希(locality sensitive hashing，LSH)采用随机投影生成的超平面作为哈希函数，根据数据点落在超平面的哪一侧，分别生成0或1，虽然有严格的理论基础，但是在实际应用中，需要较长的二进制码才能得到令人满意的检索效果。为了得到码长更短、检索性能更好的二值码，研究人员做了很多努力，包括构建不同的目标函数、采用不同的优化方法、利用图像的标签信息、使用非线性模型等。

哈希函数的目标是得到二值编码，但是由于优化过程中会遇到离散取值的约束，为此，常采用一个更宽松的约束，比如不再要求“二值码”是二值的，而是只要在一个规定的范围中即可。优化结束后，再对松弛过的“二值码”进行量化，得到最终的二值码。

2.基于哈希的近似最近邻搜索搜索策略

基于哈希的近似最近邻搜索有两种策略:一种是哈希表查找，通过构建哈希表，使得距离近的数据点的碰撞概率(collision probability)最大而距离远的点的碰撞概率最小，可进一步分为单表(图7-2(b)所示)和多表(图7-2(a)所示)；另一种是哈希码排序(图7-2(c)所示)，通过计算查询点与所有候选点之间的哈希距离获取距离最近的一组点，由于需要进行穷举搜索和重排序，计算效率不如哈希表查找。一种实用的方法是将哈希表查找和哈希码排序结合起来(图7-2(d)所示)，首先利用倒排索引检索一个小候选数据集构建哈希表，然后基于该候选数据集计算哈希码之间的距离实现最近邻搜索。

图7-2　基于哈希的近似最近邻搜索策略[12]