一、单模态哈希：

LSH (Locality Sensitive Hashing，局部敏感哈希)

论文链接：Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality - STOC1998
LSH扩展及实现链接：LSH Algorithm and Implementation (E2LSH)

局部敏感哈希是最初的用来做图像哈希索引的算法，基本思想是使用一组哈希函数将数据散列到不同的桶中，即令相近的数据落在同一个哈希桶中，越相似的数据落到同一个桶中的概率越大。

下图描述了LSH算法流程：
这里写图片描述

SH (Spectral Hashing，谱哈希)

论文及其实现链接：Spectral Hashing and its Implementation - NIPS08

谱哈希首先分析和总结了图像哈希编码应满足的条件，即：
（ 1）获得新图像哈希编码的算法易于实现；
（ 2）语义相同的图像有相同或相近的哈希编码序列，语义不同的图像得出差异性较大的哈希编码序列；
（ 3）图像的内容特征用较短的哈希编码序列就能表示。

为达到这三个条件的要求，谱哈希将编码过程视为图分割过程，对高维数据集进行谱分析，通过放松约束条件将问题转化成拉普拉斯特征图的降维问题，从而求解得到图像数据的哈希编码。

(推导省略)

SH算法的步骤：
第一步：采用主成分分析（PCA）算法获取图像数据的各个主成分方向；
第二步：在每个主成分方向按论文公式(5)计算特征值，并选取前 r 个最小的值，总共得到 r * d 个特征值，再将其按从小到大的顺序排序，取前 r 个最小的特征值，计算其对应的特征函数值；
第三步：将特征函数值在零点进行二元量化（sign函数）得到哈希编码。

主成分分析(PCA)算法是最常用的降维算法之一，但每个主成分方向上的方差是不同的，方差较大的主成分方向包含更多的信息。在每个主成分方向上用相同长度的二元码对图像进行编码是不合理的，因此谱哈希为方差大的主成分方向分配更多的比特。

谱哈希的缺点是它有两个条件在实际情况中很难同时得到满足，即假设数据是从多维均匀分布中采样得到的而且要求不同维度上的哈希编码之间相互独立，因此谱哈希的广泛使用受到了限制。

AGH (Anchor Graph Hashing，锚点图哈希)

论文链接：Hashing with Graphs - ICML11

AGH受谱哈希的启发，提出了与谱哈希相同的优化问题，但对目标函数的求解过程设计了自己的方案，脱离了数据是从多维均匀分布中采样得到这一先验假设的束缚，用近似邻接矩阵 A 代替邻接矩阵W (锚点图A是n*m的, 而邻接矩阵W是n*n的, m远小于n)，降低了时间复杂度，具有更好的广泛适用性。
AGH的基本思想是用数据聚类中心与每个数据样本点之间的近邻图去近似数据样本点与样本点之间的近邻图，用近似邻接矩阵代替原来的邻接矩阵。

AGH步骤如下：
第一步：对图像训练数据集进行聚类，得到 m 个聚类中心，每个聚类中心称为一个锚点；
第二步：建立锚点与图像训练数据中每个样本点之间的关系，称为锚点图，用矩阵 Z 表示，矩阵中每个元素使用论文中公式(2)计算；
第三步：根据这里写图片描述构造近似邻接矩阵 A，最后使用论文中公式(5)(6)得到最终的哈希码。

Discrete Graph Hashing (离散图哈希)

论文链接：Discrete Graph Hashing-NIPS-14
论文+附录：discrete-graph-hashing

简单理解：1. AGH建立锚点图；2. 去除松弛约束，直接对于离散约束求解

训练时哈希码通过对离散约束求解得来，当进行测试查询时，对于query q，B(q)=sign(Wz(q))，z(.)是一个非线性核映射(本文使用高斯核)。

SDH (监督离散哈希)

论文链接：Supervised Discrete Hashing - CVPR15

主要思想：
1. 通过将哈希码映射到 label 标签信息上，从而不需要通过计算相似性矩阵来将标签信息嵌入到哈希码生成过程当中;
2. 不对离散约束进行松弛，直接使用DCC算法在离散约束下按位求解哈希码

二、量化：

PQ和ck-means在前面的一篇博客中写过，这里不再赘述，链接：量化方法之PQ and ck-means

ITQ (Iterative Quantization, 迭代量化哈希)

ITQ 是一种基于PCA的图像哈希算法，不同于谱哈希为方差大的主成分方向分配更多的比特， ITQ 通过旋转主成分方向使得旋转后各方向的方差尽量保持平衡。

ITQ步骤：
1. 首先用 PCA 对数据进行降维并对降维后的结果进行二值量化处理得到所有数据的初始哈希编码，这样原始数据被嵌入到了汉明空间中，各数据位于超立方体的顶点上；
2. 对主成分方向进行一次随机旋转，可以较好的平衡不同主成分方向的方差，接着对编码矩阵和旋转矩阵进行交替优化，以最小化量化误差为目标，旋转若干次后将得到局部最优解。

下图是 ITQ 的基本思想示意图：
这里写图片描述
红线代表主成分方向，将数据向各主成分方向投影后进行二值量化得到的编码具有较大的误差，同一类数据被不同的哈希编码序列表示了出来，也就是类似的图像落在了不同的哈希桶中。(b)对主成分方向进行了一次随机旋转，减小了投影值与哈希编码之间的量化误差。(c)是通过 ITQ 优化后得到的最终的投影向量及哈希编码序列，可以看到，此时量化误差达到最小，同一类数据落在了同一个哈希桶中。