传统哈希编码方法

哈希编码就如同从一组图像中学习到一种映射 $f$ ， $f$ 可以使图像映射至二值的哈希编码上。可以想见，这是一个困难的问题。对于这个问题，传统方法的解决思路是：先对原图像用人工提取的特征来表达，即先从原图像压缩至特征表达，然后再从特征表达映射至哈希编码。

以KSH（Supervised Hashing with Kernel）为例，其所代表的算法如下。

（1）提取特征。在训练集 $T$ 内共含 $M$ 张图，遍历 $m = 1,2,\dots,M$ ，对第 $m$ 张图提取人工特征，如HoG、SIFT等，然后将特征连接起来形成一个长向量来表达该图： $\text{feature}(m)$ 。

（2）分解相似度矩阵。

（2a）将 $T$ 按照标准的两两相似/不相似结果构建矩阵 $S$ 。（即1为相似，0为不相似，则 $S$ 为0和1组成的矩阵，且 $S_{ij}$ 为图 $i$ 和图 $j$ 相似与否的标注结果。）

（2b）将 $S$ 分解成 $HH^\top$ ，使得 $\min|HH^\top-S|$ ，则 $H$ 为训练集 $T$ 对应的哈希编码矩阵，其第 $m$ 行对应图片 $m$ 的哈希编码值。

（3）求得特征表达至哈希值的映射 $g$ ： $\text{feature}(m)\to H(m)$ 。训练学习结束。

（4）测试时，对应图片 $I$ ，先同样提取特征表达 $\text{feature}(I)$ ，再根据映射 $g$ 得到其哈希编码 $H(I)=g(\text{feature}(I))$ 。

从以上步骤可以看出，难点集中在第（2b）步，即将相似度矩阵 $S$ 分解成可能的哈希编码矩阵 $HH^\top$ ，并且约束 $H$ 的取值为0或1。因此，研究者针对如何近似分解相似度矩阵做了大量艰苦的工作。尽管如此，传统方法还是有很大的局限性的。比如，如果训练集过大，则意味着 $S$ 也会过大，分解起来会变的十分困难，甚至不可达成。

而深度学习介入后，这些局限被逐渐打破。深度学习的应用也不是一蹴而就的，在逐步尝试和摸索后，终于找到了一条简捷有力的途径。