Deep Hash in Large Scale Image Retrival

《Deep Hash in Large Scale Image Retrival》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、【大规模图像检索的利器】Deep哈希算法介绍原创 2016-06-20 刘昊淼 深度学习大讲堂前言 在最近邻搜索（nearestneighborsearch）问题中，给定一个查询（query），目标是要找到空间中离它最近的点。这里所说的空间可以是任意的空间，比如特征空间，或者语义空间。具体来说，在图像检索这个问题中，每张图像对应空间中的一个点，而所谓的“近”既可以是外观上的近（看着像），也可以是语义上的近（同类）。以下图为例，当我把左侧的图像扔给两个不同的搜索引擎后，得到的返回结果就对应上面的两种情况。事实上，如果不对效果做什么要求的话，想要

2、实现上面这样的功能其实并不难。最直接的方法就是用一种特征来表示每张图像（比如AlexNet中fc7层的输出），然后通过计算查询图像（上图左）和数据库中图像在特征空间中的欧式距离，并按照距离从小到大的顺序，返回数据库中的图像。  上面这种方法虽然看上去简单粗暴，但是却不失为一种有效的做法。但是，随着互联网上的图像越来越多，这种方法的短板也体现得淋漓尽致——存储空间消耗大，检索速度慢。具体来说，如果使用上面提到的AlexNet中fc7层的输出来表示每张图像，那么表示一百万张图像就需要大约15GB的存储空间（单精度浮点数），而计算查询图像和数据库中

3、每张图像的距离，则需要8192次加法操作和4096次乘法操作，遍历完所有的一百万张图像再返回结果的话，恐怕用户早就等得不耐烦了。考虑到现在互联网上的数据规模动辄就是上亿的级别，这种方法就显得更不靠谱了。        为了解决上面方法对存储空间和检索时间的不切实际的要求，近年来近似最近邻搜索（approximatenearestneighborsearch）技术发展迅猛，因为其对空间和时间的需求大幅降低，而且能够得到不错的检索结果，因此成为了一种实用的替代方案。在这其中，哈希（hashing）作为一种代表性方法，近年来受到了广泛的关注。本文首

4、先对哈希算法的发展历程进行简单的介绍，然后按照相关性，对近年来的一些主要的深度哈希算法进行介绍，最后对现有深度哈希方法进行简单的总结。发展历程  在哈希算法中，通常的目标是将样本表示成一串固定长度的二值编码（通常使用0/1或-1/+1表示其中的每个bit），使得相似的样本具有相似的二值码（使用Hamming距离度量二值码之间的相似性）。在最初的工作中，作者提出在特征空间中随机选择一些超平面对空间进行划分，根据样本点落在超平面的哪一侧来决定每个bit的取值。这类方法虽然有严格的理论证明保证其效果，但是在实际操作中通常需要比较多的bit才能得到令

5、人满意的检索效果。 在之后的工作中，为了得到编码长度更短、检索效果更好的二值码，人们进行了很多尝试，包括构建不同的目标函数、采用不同的优化方法、利用图像的标签信息、使用非线性模型等。随着研究的深入，利用二值编码进行检索的性能也逐步提升。        与常见的机器学习算法不同，哈希方法的目标是得到二值编码，所以优化过程中经常会遇到离散取值的约束，因此通常来说无法使用基于梯度的方法对目标函数进行优化。为了简化问题，通常的做法是改用一个更宽松的约束，比如不再要求“二值码”是二值的，而是只要在一个规定的范围中即可。优化结束后，再对松弛过的“二值码”

6、进行量化，得到最终的真二值码，深度哈希算法通常也采用这种做法。深度哈希算法  最早的基于深度学习的哈希算法应该是2009年由Hinton研究组提出的SemanticHashing方法[1]。对于这个方法来说，深度模型只是提供了一定的非线性表示能力，而网络的输入仍是手工设计的特征，和现在通常意义上的深度学习算法还是有一定的区别，因此本文中不作具体介绍。在这之后，基于SemanticHashing出现了一些改进，但是也都没有掀起什么大的风浪，在此一笔带过。  时间来到2014年，受到CNN强大学习能力的鼓舞，中山大学的潘炎老师研究组和颜水成老师合

7、作，在美国人工智能协会年会（AAAI2014）上发表的论文提出了一种名为CNNH（ConvolutionalNeuralNetworkHashing）的方法[2]，把基于CNN的深度哈希算法推到了前台。CNNH的做法如下图所示，首先通过对相似度矩阵（矩阵中的每个元素指示对应的两个样本是否相似）进行分解，得到样本的二值编码；然后，利用CNN对得到的二值编码进行拟合。拟合的过程相当于一个多标签预测问题，作者使用了交叉熵损失来达到这个目的，这一步对应图中最右侧红色节点。此外，作者还提出加入分类的损失函数来进一步提升性能（softmax，对应图中最右

8、侧黑色节点）。  尽管实验中CNNH相比传统的基于手工设计特征的方法取得了显著的性能提升，但是这个方法仍然不是端到端的方法，学到的图像表示不能反作用于二值编码的更新