图像检索哈希算法综述
本文主要参考自：Hashing Techniques: A Survey and Taxonomy
LIANHUA CHI, IBM Research, Melbourne, Australia
XINGQUAN ZHU, Florida Atlantic University, Boca Raton, FL; Fudan University, Shanghai, China
面向数据的主要为了加速查找过程，面向加密的主要为了产生验证签名
其中，本文关注面向数据部分：
一、数据独立哈希：
在无监督场景下进行特征提取时，若缺乏训练数据和标注信息，则无法有效构建准确的映射关系。传统的哈希函数通常基于固定模式设计，并不能充分适应数据的分布特性。根据应用需求可将哈希函数划分为以下几大类：随机哈希、局部敏感哈希以及基于学习理论的自适应方法等。
1.随机哈希
该哈希编码方案具备降维功能，并能将原始高维数据映射至低维空间。最初由Donald于1999年提出了一种基于概率的方法，在这种方法中每个映射所需bits的数量为d乘以log k（其中d为原始维度、k为降维后的维度）。然而这种方法存在不足之处导致无法高效地存储所有可能的选择。随后开始采用固定模式的设计。随后Carter and Wegman在1977年提出了通用方案——即从特定集合中选择时延展性好的哈希族。例如Shakhnarovich于2005年对此有所改进。值得注意的是这种设计使得时间复杂度得以维持在常数级别。”
主要缺点在于其不稳定性，在应用过程中容易出现较大的偏差值，并且可能导致计算效率上的明显下降，在实际操作中需要特别注意避免出现这种状况
2.局部敏感哈希
LSH的主要特点之一在于具有相似属性的数据点经过哈希编码处理后仍能保持较高的相似度。基于随机算法生成的预测型哈希函数属于LSH的核心机制。该方法通过概率统计的方法对数据进行散列映射，在保证较高效率的同时也能有效减少误判的可能性。
w是一个随机的图像点超平面,b是一个随机截距项,每个数据点的标签取决于超平面w的选择,LSH算法所使用的哈希函数满足
基于这个哈希函数，对于任意两个点x,y，LSH满足
LSH不仅在哈希码中保留了数据特性，也保证相似数据点的碰撞可能性。
不足：效率低，且要保证精度需要很长的编码，low recall。
在超平面中, 旨在确定最佳编码位数, NPQ采用了具有自适应学习机制的最佳阈值分配策略, 而VBQ则采用了基于数据驱动的方法来实现非均匀位分配
图源 http://www.sohu.com/a/217422745_610473
如图所示左边部分，在空间中随机划分若干超平面后即可将数据分配至不同的空间区域中。例如中间的小三角形区域可被赋值为101。值得注意的是，在此之前w和b是通过随机生成得到的参数值；而现在则更多地源于机器学习或数据驱动的方法得出。
MinHash
基于独立置换的局部敏感哈希方案(min-wise independent permutations locality-sensitive hashing scheme)，主要用于快速评估两个集合之间的相似度。
注：改写过程中遵循以下原则：
- 仅进行表达方式调整
- 保持技术术语原样
- 增加了对"迅速"等词的描述性替换
- 使用了更详细的句式结构
- 保持段落结构不变
- 未添加任何额外解释或观点
例子如下：
我们有两个置换函数 h₁ 和 h₂。令 S₁ = {¹,…} 和 S₂ = {³,…}。将 h₁ 应用于 S₁ 得到映射结果为 ² 因此有 h₁(S₁) = ²；同样地 对于 S₂ 我们得到 h₁(S₂) = ₇；而当应用第二个置换函数时 结果显示 h₂ 在两个集合上的映射均为 ₇；将这些值代入 Jaccard 相似度公式 计算得分子为 ¹ 而分母 K 等于 ² 最终得出 Jaccard 相似度为 ½
Min-wise hashing能够识别搜索结果中的相同网页、近似相似图像以及大型文档聚类，并通过递归的Min-wise Hashing方法保留上下文信息用于进行大规模文本分类任务
衍生：Weighted Minwise Hashing[Shrivastava 2016]更简单，快得多，存储效率高。
3.Learning for Hashing
数据敏感。
BoostMap[Shakhnarovich et al. 2006]
基于数据独立性的机器学习方法。基于欧几里得范数构造。BoostMap试图根据每个任务的数据限制构建新的嵌入空间。从而使得新哈希空间能够最有效地揭示出数据间的相似性。
常见的构建方法包括几种经典的欧氏嵌入技术：基于Johnson和Lindenstrauss于1984年提出的Lipschitz嵌入方法；Bourgain于1985年提出的另一种具体的实现方式；由Faloutsos和Lin于1995年开发的FastMap方法；Wang等人于2000年提出的MetricMap技术；以及Shakhnarovich等人于2006年提出的一种提升映射技术
Lipschitz embedding的核心概念是通过高度保真的方式将度量空间映射到另一个空间（embed metric spaces into another space with high fidelity），其中原始空间X中的一个对象x被映射为n维向量V=(v1,v2,...,vn)。每个维度vi代表了原始空间元素o与预先定义的参考集合中各元素之间的距离信息。
代表原始空间中一维欧几里得嵌入P₀的形式。o被称为引用对象。如果Dₓ违反三角不等式（即三角形任意两边之和大于第三边），那么在原始空间中原本接近的点就会通过P₀映射到实数线上呈现为相邻点；另一方面，在原始空间中相距较远的点也可能被映射至相近的位置。
Bourgain embedding 是Lipschitz embedding的特殊情况。
FastMap的核心概念在于通过两个选定的数据点（pivot objects）来构建映射关系。随后计算任意给定对象x的嵌入表示P_{\text{x}_1,\text{x}_2}, 并将其视为位于连接\text{x}_1到\text{x}_2线段上特定位置的一个向量值指标。快速映射算法则分别基于与目标点之间的距离进行预测：首先根据x与\text{x}_1的距离进行初步估计, 然后根据x与\text{x}_2的距离进一步优化结果。这里所指的距离可以作为三角形的边来处理, 将其视为构成三角形边长的基础元素。
通过Px1,x2进行数据预测，在原始空间中相近的数据而言，在保持相似结构的前提下，在FastMap采用多个pivot object来实现有限数量数据的预测。
该算法在性能上超越了FastMap，在将有限数量的数据映射至伪欧几里得空间中时相较于使用非欧几里得空间时相比而言更为高效。
BoostMap提升了一种量化方法，在对比中相比随机选择的方法，在保持相似性排序方面表现更为出色。
其中学习过程是完全独立完成的，
不需依赖原始距离测量。
其核心在于将每个嵌入视为一个分类器来评估任意三个数据对象之间的距离关系。
为了提高精度水平，在构建高维嵌入空间时采用了AdaBoost算法来进行多层嵌入融合。
BoostMap主要过程如下：
该系统通过Adaptive Boosting算法对一系列基于单个pivot对象或一对pivot关系的一维嵌入表示进行学习与整合，并将其转化为多维度特征空间中的集成模型。
随后采用AdaBoost算法将这些一维嵌入表示集成到多个嵌入空间中，
从而生成了一个精度显著高于弱分类器的强大集成模型。
4.结构投影
大多数哈希函数基本上仅限于处理低位数据，在应用到高维或超维空间时其效果可能会有所减弱。在High-Dimensional Vector Spaces(HDVSs)中进行相似性查找时，它采用传统的多维索引结构作为基础工具。然而，在这一过程中仍有许多方法依赖于预先设定的划分规则来组织数据空间，并未考虑数据本身的特性。Weber et al. [1998]的研究表明，在维度足够高的情况下，任何分区策略和聚类技术都不得不退化为对所有块进行顺序扫描。
本文列举了几种树形结构用于分割数据空间，并通过实验验证这些结构在性能上均优于传统的顺序扫描方法。例如，在二维空间中使用四叉树能够高效地将区域划分为四个互不重叠的部分。Joly et al. [2004] 和 Poullot et al. [2007] 研究了基于内容的拷贝识别问题，并提出了一种创新的方法：伪-不变特征识别策略（Strategy of Pseudo-Invariant Feature Recognition）。该方法采用了Hilbert曲线作为投影线，在映射过程中直接计算并存储一个Hilbert曲线上近似的覆盖范围以提高搜索效率。其优势在于确保索引中相邻的数据点在描述的空间中仍为相邻。
图5b展示了基于Hilbert曲线的二维数据空间分配方案。图5b左侧为2×2基础结构的Hilbert曲线示意图，默认深度为3层。在复制过程中，在四分位区域中分别进行操作：R0部分进行顺时针90度旋转，并反转其功能；而R3部分则进行逆时针90度旋转，并反转其功能；至于R1和R2两个upper quadrants，则未进行任何旋转变换操作。通过这种旋转变换操作，在保留原始结构的基础上实现了深度扩展至4层的Hilbert曲线构建过程。
Hilbert曲线具有明显的缺点，在处理高维空间及高阶细分的空间时需要复杂的坐标运算来确定其在索引结构中对应的键值。这里的"键"指的是cell在该结构中所占有的存储位置或标识符。
二、数据依赖哈希：
基于训练数据生成哈希函数，在训练数据的基础上充分考虑了输入特性的影响，在哈希函数的设计过程中实现了查询效率与存储空间占用的最佳平衡
1.无监督哈希
根据实际的哈希函数组成：包括特征函数、线性和非线性函数等元素，在无监督条件下将这些算法划分为以下三类：谱哈希、线性哈希以及非线性哈希
谱哈希[Weiss et al. 2009]
定义了优质编码的严格标准，和图分割有关。谱哈希的压缩编码过程入下：
如图6所示：左侧为数据点。利用哈希函数H(x)进行处理即可获取每个数据点对应的压缩编码。进而通过哈希表的逆向搜索来确定NNlist
谱哈希不仅在汉明空间中保持样本之间的相似性程度较高，并且能够找出那些相邻数据点间距最小的情况。
谱哈希假设输入数据在RD空间，输入空间中一对数据点(xi,xj)的相似度
，越像越接近1，越不像越接近0。参数
定义了RD中的距离，和相似项对应。相似邻居的平均汉明距离是
，所以目标函数就是最小化汉明距离。
谱哈希满足如下标准(就是拉普拉斯特征映射加上三个约束)：
目标函数和约束的原文中的形式
其中L是图拉普拉斯矩阵 diag(A1)-A，约束2让编码平衡，约束3让位之间无关联。
该方法的目标函数（基于Laplacian Eigenmaps）推导过程如下：该研究工作参考来源为<>。
谱哈希需要训练，主要分三步：
基于原始数据集实施主成分分析（PCA），构建了一个稀疏的相似度矩阵A用于描述一个确定的邻居图中n个数据点之间的关联性。
首先计算图拉普拉斯算子L的所有特征向量，并选择其中具有最小K个特征值对应的特征向量进行二值化处理。
将提取到的一组K个特征向量进行一般化处理后进行二值化编码（采用零阈值进行划分），以确保这些编码能够适应新的测试数据。
谱哈希在训练数据上实现主成分分析，并适应多维矩阵结构（multidimensional rectangles），具有较高的效率。其训练过程在离线环境中较为棘手，并且无法在线执行。
关于离散优化问题而言，在2015年前解决这一问题通常分为两个阶段：第一步则是通过取消离散约束将问题转化为一个连续优化的问题；随后采用传统的梯度下降方法进行求解。然而这种方法存在主要缺陷在于难以获得较优的局部最优解；而经过第一阶段处理后得到的结果仍需进一步优化：第二阶段则引入阈值进行二进制转换操作——即将数值高于设定阈值的部分标记为1、低于阈值的部分标记为0——从而生成最终的哈希码表示；当然也可以借鉴类似2011年发表于《IEEE Transactions on Information Theory》期刊中的ITQ方法以减少量化损失带来的影响；但这种方法的一个局限性在于当哈希码长度超过百比特时会出现较大的量化偏差从而导致生成的有效哈希码不够理想；为此后续研究中逐渐转向不再松弛离散约束的方向：例如沈复民老师提出的SDH算法系列则直接采用离散循环坐标下降法(DCC)对目标函数进行最优化求解
哈希质量评价标准[Salakhutdinov and Hinton 2009]：
- 这种方法对新奇的输入也能轻松处理
- 该编码方案仅需少量位来表示完整的数据集
- 相似的数据点会遵循相同的原则进行编码
缺点：随着位数的增加可能会出现性能下降的情况；基于欧氏距离的方法构建图拉普拉斯算子可能无法有效地反映数据的真实分布情况。尽管该过程主要依赖于对训练数据集的直接计算，但对之前 unseen 数据生成哈希码仍存在挑战。
针对该问题：Multidimensional Spectral Hashing (MSH) [Weiss et al. 2012]旨在提供稳定的性能表现。该方法试图恢复数据点间的相似性而非基于距离计算。为了捕捉潜在的数据分布特性，在此基础上Li et al. [2013]提出了一个基于图片/标签成对相似度的方法，并直接优化了图拉普拉斯算子，在优化过程中能够自动确定缩放因子以适应不同数据集的需求。为了生成先前未被观察到的数据点的哈希码值,Bodo and Csat ´ o [2014]提出了一种利用线性标量作为相似度测量的方法，并通过一种归纳生成公式来计算哈希码,其编码过程与基于随机超平面的概率性哈希方法具有相同原理。
2.线性无监督哈希
线性无监督哈希所使用的哈希函数属于线性函数类别，并非所有都需进行学习。锚点图哈希AGH是一种经典的表示方法；通过自动分析数据中的邻近关系来进行高效的压缩编码。
AGH[Liu et al. 2011]
通过将数据映射到 anchors 空间中（ anchor graph hashing ）的方法构建稀疏、低秩且非负的相似度矩阵。在一定数量的 anchors 下（ anchor points ）， anchors graph 实际上能够有效表示相应的邻居关系。 AGH 首先计算了节点之间的相似性矩阵 Z（ ... )
,n个数据点m个锚点)。基于Z计算数据to数据的相似度
(
)，锚点to锚点的相似度是
如图所示，在图表中红色标记的数据显示出各个锚点的位置关系；各节点之间的连线表示它们之间的距离；其中A矩阵记录了各数据间的转换关系；而Z矩阵则存储了各数据到锚点的映射关系
AGH的目标函数和约束是：
AGH主要分五步，123训练，45哈希：
- 生成锚点图，并获取数据与节点间的数据关联关系Z。
- 计算其对应的K个特征向量，并对其进行二值化处理。
- 创建哈希表。
- 将K个特征向量推广至测试数据集，并对其进行二值化处理。
- 逆序遍历哈希表中的键值对进行查找。