基于内容的图像检索技术综述 传统经典方法_感知哈希图像检索流程图

SIGAI特约作者
manyi
视觉算法工程师

其它机器学习、深度学习算法的全面系统讲解可以阅读《机器学习-原理、算法与应用》，清华大学出版社，雷明著，由SIGAI公众号作者倾力打造。

• 书的购买链接
• 书的勘误，优化，源代码资源

今天我们来介绍一下图片检索技术，图片检索就是拿一张待识别图片，去从海量的图片库中找到和待识别图片最相近的图片。这种操作在以前依靠图片名搜图的时代是难以想象的，直到出现了CBIR(Content-based image retrieval)技术，依靠图片的内容去搜图。比较常见的图搜平台有百度、谷歌、拍立淘等，有些图搜技术已经能达到非常不错的效果。接下来我们做个测试，给出一个柯基宝宝的图片，分别用三家搜索引擎进行搜索：

 

 

早期的图片检索技术都是基于文本的，需要按照图片的名称去搜索对应的图片，而这样有个很明显的缺陷就是：大量的图片需要人为事先去命名，这个工作量太大了。随后渐渐出现了基于内容的图片检索技术，较早出现的有哈希算法LSH(Locality-Sensitive Hashing)，随后图搜这一块逐渐丰富，从BOF -> SPM -> ScSPm ->LLC 使传统的图搜技术逐渐成熟。下面我们就来巴拉一下传统图搜技术的前世今生。

一、LSH

LSH(Locality-Sensitive Hashing)较为官方的理解为：将原始数据空间中的两个相邻数据点通过相同的映射后，这两个数据点在新的数据空间中仍然相邻的概率很大，而不相邻的数据点被映射到同一个桶的概率很小。也就是说，如果我们对原始数据进行一些hash映射后，我们希望原先相邻的两个数据能够被hash到相同的桶内，具有相同的桶号。因此，LSH算法使用的关键是针对某一种相似度计算方法，找到一个具有以上描述特性的hash函数，使得经过它们的哈希映射变换后，原始空间中相邻的数据落入相同的桶内，那么我们在该数据集合中进行近邻查找就变得容易，只需要将查询数据进行哈希映射得到其桶号，然后取出该桶号对应桶内的所有数据，再进行线性匹配即可查找到与查询数据相邻的数据。

上面的叙述太过理论化，那么hash算法具体怎么应用到图搜技术中呢？参照nash_同学我们列举了三种不同的hash算法：

(一)、平均哈希算法(aHash)

此算法是基于比较灰度图每个像素与平均值来实现的，最适用于缩略图搜索。

步骤：
1.缩放图片：为了保留结构去掉细节，去除大小、横纵比的差异，把图片统一缩放到8*8，共64个像素。
2.转化为灰度图：把缩放后的图片转化为256阶的灰度图
3.计算平均值： 计算进行灰度处理后图片的所有像素点的平均值
4.比较像素灰度值：遍历64个像素，如果大于平均值记录为1，否则为0.
5.得到信息指纹：组合64个bit位，顺序随意保持一致性即可。
6.对比指纹：计算两幅图片的汉明距离，汉明距离越大则说明图片越不一致，反之，汉明距离越小则说明图片越相似，当距离为0时，说明完全相同。(通常认为距离>10 就是两张完全不同的图片)

(二)、感知哈希算法(pHash)

平均哈希算法过于严格，不够精确，更适合搜索缩略图，为了获得更精确的结果可以选择感知哈希算法，它采用的是DCT(离散余弦变换)来降低频率的方法。

步骤：
1.缩小图片：32 * 32是一个较好的大小，这样方便DCT计算
2.转化为灰度图：把缩放后的图片转化为256阶的灰度图
3.计算DCT:DCT把图片分离成分率的集合
4.缩小DCT：DCT是32*32，保留左上角的8*8，这些代表的图片的最低频率
5.计算平均值：计算缩小DCT后的所有像素点的平均值
6.进一步减小DCT：大于平均值记录为1，反之记录为0
7.得到信息指纹：同平均哈希算法
8.对比指纹：同平均哈希算法

(三)、差异哈希算法( dHash)

相比pHash，dHash的速度要快的多，相比aHash，dHash在效率几乎相同的情况下的效果要更好，它是基于渐变实现的。

步骤：
1.缩小图片：收缩到9*8的大小，共72个像素点
2.转化为灰度图：把缩放后的图片转化为256阶的灰度图
3.计算差异值：dHash算法工作在相邻像素之间，这样每行9个像素之间产生了8个不同的差异，一共8行，则产生了64个差异值
4.获得指纹：如果左边像素的灰度值比右边高，则记录为1，否则为0
5.对比指纹：同平均哈希算法

二、BOW-> BOF

BOW(Bag of Words) 模型最初被用在文本分类中，将文档表示成特征矢量。它的基本思想是假定对于一个文本，忽略其词序和语法、句法，仅仅将其看做是一些不同类别词汇的集合，而文本中的每个词汇都是独立的。简单说就是将每篇文档都看成一个袋子，这个袋子里面装的是各种类别的词汇，我们按照类别把整篇文档的词汇归为不同的类，比如这些词汇的类可以是枪、银行、船、人、桌子等，然后依据每个类别中词汇出现的频率来判断整篇文档所描述的大致内容。比如一篇文档中枪、银行这两类词汇出现的概率比较高，我们就可以判断这篇文档和武装押运有关，或者是关于土匪抢银行的，兄台们可自行发挥自己的脑洞。

类比到图像就是BOF(Bag of Features)了，以上所述的“袋子”就相当于是一副完整的图像，而“词汇”则相当于图像的局部特征(如SIFT、SURF)，先用这些局部特征来训练出图像的聚类中心，训练聚类中心的过程即相当于按照类别把文档的词汇归为不同的类。在图片检索的时候，对图片的每一个局部特征用近邻查找法找到距离它最近的聚类中心，并把此聚类中心上局部特征的数目加一，依次遍历每一个局部特征后就把一副图片映射到一个聚类中心上，即图片的量化。最后以这些聚类中心为横坐标，以每个聚类中心的局部特征个数为纵坐标可以得到一个直方图，该直方图表示的向量就是一副图片映射到聚类中心的BOF向量。图片检索的时候只要依次比较图像的BOF向量即可找到最相似的图片。

三、指数权重VLAD

<