SIGAI 特约作者
manyi
视觉算法工程师
今天我们来介绍一下图片检索技术，图片检索就是拿一张待识别图片，去从海量的图片库中找到和待识别图片最相近的图片。这种操作在以前依靠图片名搜图的时代是难以想象的，直到出现了 CBIR(Content-based image retrieval)技术，依靠图片的内容去搜图。比较常见的图搜平台有百度、谷歌、拍立淘等，有些图搜技术已经能达到非常不错的效果。接下来我们做个测试，给出一个柯基宝宝的图片，分别用三家搜索引擎进行搜索：
图 1 原图
图 2 百度搜索结果
图 3 谷歌搜索结果
图 4 拍立淘搜索结果
早期的图片检索技术都是基于文本的，需要按照图片的名称去搜索对应的图片，而这样有个很明显的缺陷就是：大量的图片需要人为事先去命名，这个工作量太大了。随后渐渐出现了基于内容的图片检索技术，较早出现的有哈希算法 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 是 3232，保留左上角的 88，这些代表的图片的最低频率
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 向量即可找到最相似的图片。
图 5 基于单词包模型的图片特征示意图
三、指数权重 VLAD
VLAD(Vector of Aggragate Locally Descriptor)相对于 BOW 的差别就是，BOW 是把局部特征的个数累加到聚类中心上，而 VLAD 是把局部特征相对于聚类中心的偏差(有正负)累加到聚类中心上，而且是对最相邻的 k 个聚类中心都进行累加(k 一般设为 4 左右)，这样能很大程度地提高特征量化的准确度，而且还能减少聚类中心的数目以提高量化速度。在累加每一个局部特征的偏差时，实际上累加的不是一个数，而是一个局部特征向量，比如用 SIFT 特征时累加的就是一个 128 维的向量，这样最终 VLAD 向量的维度就是 128*聚类中心个数。如果聚类中心个数是 256，最终的 VLAD 向量就是 32768 维。用这么大的向量去表征一副图片，显然会显得冗余，所以我们对直接累加的 VLAD 向量还要进行 PCA 降维，作者在使用 VLAD 向量的时候把它降到了 512 维，识别速率有了质的提升而识别率却基本维持不变。
因为 PCA 降维矩阵是按照特征值从大到小排列的，所以经过 PCA 降维处理后特征向量的前几个数据所占的比重会比较大，要远大于平均值，如图 6 所示。这样对特征的提取会造成较大干扰，因为若是前几个数据出现了差错，其引起的数据波动也往往比较大，在比较特征向量相似度时就容易产生较大误差，所以理想情况是使特征向量中前几个过大的数据按一定比例缩小，而使后面变化不大的数据尽量保持不变。
通过观察特征向量直方图可以发现它在二维坐标上的分布类似于指数函数，如图 7a)所示为指数函数 
，所以考虑用图 7b)所示的指数函数 
作为权重和特征向量的每一个数据相乘。
图 6 PCA 降维后的 VLAD 向量
图 7 指数函数
但是在权重和数据相乘的时候还会有一个问题：当 x 取值很接近 0 的时候权重值 g(x)也很接近 0，当权重过小时会抹掉特征向量的前几个数据，这样会造成特征向量的部分数据无效，在度量特征向量相似度时反而会增大误差，所以在取离散 g(x)值作权重的时候不能从 0 开始取值而应当有一个初始值。
将图 6 的特征向量和离散权重相乘可得到新的特征向量直方图，如图 8 所示，可见特征向量的前几个较大的数据被削减，而后续数据基本维持不变。
图 8 指数权重 VLAD
针对权重 VLAD 的提升效果，我们用 6 类图片做了识别率的对比：
表 1 VLAD 与权重 VLAD 的识别率对比
但是用 VLAD 向量做图片检索也存在很多缺点：首先，作为传统的图像识别方法，它需要手动提取特征，再加上 K-means 聚类时间长，会使得算法很繁琐；其次在向量量化的过程中会损失特征的精度，模板图片的设计也显得很粗糙，而且整个过程没有设计反馈系统，系统无法自动升级，迁移性很差。
四、FV
FV(Fisher Vector)是一种类似于 BOW 词袋模型的一种编码方式，如提取图像的 SIFT 特征，通过矢量量化(K-Means 聚类)，构建视觉词典(码本)，FV 采用混合高斯模型(GMM)构建码本，但是 FV 不只是存储视觉词典的在一幅图像中出现的频率，并且 FV 还统计视觉词典与局部特征的差异。可见 FV 和 VLAD 的差别就是 FV 用 GMM 构建码本，而 VLAD 用 K-Means 构建码本。
FV 其实就是对于高斯分布的变量求偏导！也就是对权重、均值、标准差求偏导得到的结果，其本质上是用似然函数的梯度向量来表达一幅图像，这个梯度向量的物理意义就是数据拟合中对参数调优的过程，下面我们来说一下 GMM。
事实上，GMM 和 K-means 很像，不过 GMM 是学习出一些概率密度函数来(所以 GMM 除了用在 clustering 上之外，还经常被用于 density estimation )，简单地说，K-means 的结果是每个数据点被分配到其中某一个 cluster 了，而 GMM 则给出这些数据点被分配到每个 cluster 的概率，从而也可以通过设置概率阈值把数据点分配到多个 cluster，又称作 soft assignment 。
但是 GMM 有个缺点就是计算量很大，GMM 每一次迭代的计算量比 K-means 要大许多，所以有一个更流行的做法是先用 K-means (已经迭代并取最优值了)得到一个粗略的结果，然后将其 cluster 作为初值传入 GMM 函数，再用 GMM 进行细致迭代。
五、SPM
由于 BOW 模型完全缺失了空间位置信息，会使特征的精度降低很多，而 SPM(Spatial Pyramid Matching)就在 BOW 的基础上加了一个空间位置信息，也相当于在 BOW 的基础上加了一个多尺度，盗用一下论文的图：
图 9 SPM 三个尺度示意图
上图中的点、菱形和十字架分别代表不同的局部特征。左边相当于原图，中间把原图分成了四小块，右边把原图分成了 16 小块，各图的小块大小是不一样的，所以能体现出多尺度信息，而各小块的位置体现出空间信息。然后对每一个小块单独进行聚类和量化，即相当于在多个尺度上进行 BOW 操作：
- 本文地址：基于内容的图像检索技术综述 传统经典方法
- 本文版权归作者和AIQ共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出
K 是维度信息，比如单通道图像只有行和列两个维度，那么 K 就是 2。L 是尺度的个数，X_m_和 Y_m_代表点集中的点，当 L=0 时，上式就退化为 BOW 了。在识别的时候我们把 L=0、1、2 三个尺度的图片总共 21 个小块的特征串接起来，1+4+16=21。
关于图像的稀疏编码
对于二维数据，我们还可以用图像压缩来说明。类似于将图像的每个像素点当作一个数据，跑一下 K-means 聚类，假设将图像聚为 k 类，就会得到每类的质心 centroids，共 k 个，然后用这些质心的像素值来代替对应的类里的所有点的像素值。这样就起到压缩的目的了，因为只需要编码 k 个像素值(和图像每个像素点的对这 k 个值得索引)就可以表示整张图像了。当然，这会存在失真，失真的程度跟 k 的大小有关。最偏激的就是原图像每个像素就是一个类，那就没有失真了，当然这也没有了压缩。
(一)、VQ(vector quantization)
首先我们来巴拉一下 VQ，其实 VQ 就是上面提到的 BOW 特征量化，只不过 VQ 常常被用来稀疏 SPM 特征：
上式中，Xi 表示第 i 个局部特征(如 SIFT 特征)，B 为聚类中心，Ci 表示第 i 个局部特征特征所对应聚类中心的编码系数。Card (Ci)=1 表示每个 Xi 只用一个 B 来表示，即 Ci 只有一个非零分量，其余分量全为零。虽然 VQ 方法得到的编码系数足够稀疏，但由于它把局部特征只量化到一个聚类中心上，没有考虑特征的多层语义信息，导致很大的编码误差。
(二)、SC(Sparse coding)
为了减少向量量化的信息损失，在基于 SPM 模型的稀疏编码中提出 ScSPM，通过使用 B 的 L2 范数松弛约束条件，ScSPM 的目标函数为：
上式取消了中 Ci >= 0 的约束条件，因此每个特征可以用多个聚类中心进行表示。
(三)、LLC(locality-constrained linear coding)
在 ScSPM 之后是 LLC，LLC 对 ScSPM 的改进，在于引入了局部约束，其实也就是上文提到的 VLAD 向量，LLC 是把特征量化到附近的多个聚类中心，所以才有局部约束这种提法。盗用一下 Jinjun Wang 论文里的图直观说明 VQ、ScSPM 和 LLC 三者的区别：
图 10 VQ、SC、LLC 对比
上述列举的只是传统的图片搜索方法，而目前主流的 CBIR 系统都是结合深度学习去做的，深度学习相对于传统方法是一个质的提升。
推荐阅读
[1] 机器学习-波澜壮阔 40 年 SIGAI 2018.4.13.
[2] 学好机器学习需要哪些数学知识？SIGAI 2018.4.17.
[3] 人脸识别算法演化史 SIGAI 2018.4.20.
[4] 基于深度学习的目标检测算法综述 SIGAI 2018.4.24.
[5] 卷积神经网络为什么能够称霸计算机视觉领域？ SIGAI 2018.4.26.
[6] 用一张图理解 SVM 的脉络 SIGAI2018.4.28.
[7] 人脸检测算法综述 SIGAI 2018.5.3.
[8] 理解神经网络的激活函数 SIGAI 2018.5.5.
[9] 深度卷积神经网络演化历史及结构改进脉络-40 页长文全面解读 SIGAI2018.5.8.
[10] 理解梯度下降法 SIGAI 2018.5.11.
[11] 循环神经网络综述—语音识别与自然语言处理的利器 SIGAI2018.5.15
[12] 理解凸优化 SIGAI 2018.5.18
[13] 【实验】理解 SVM 的核函数和参数 SIGAI2018.5.22
[14] 【SIGAI 综述】行人检测算法 SIGAI2018.5.25
[15] 机器学习在自动驾驶中的应用—以百度阿波罗平台为例(上) SIGAI 2018.5.29
[16] 理解牛顿法 SIGAI 2018.5.31
[17] 【群话题精华】5 月集锦—机器学习和深度学习中一些值得思考的问题 SIGAI 2018.6.1
[18] 大话 Adaboost 算法 SIGAI2018.6.2
[19] FlowNet 到 FlowNet2.0：基于卷积神经网络的光流预测算法 SIGAI2018.6.4
[20] 理解主成分分析(PCA) SIGAI 2018.6.6
[21] 人体骨骼关键点检测综述 SIGAI2018.6.8
[22] 理解决策树 SIGAI 2018.6.11
[23] 用一句话总结常用的机器学习算法 SIGAI 2018.6.13
[24] 目标检测算法之 YOLO SIGAI 2018.6.15
[25] 理解过拟合 SIGAI 2018.6.18
[26] 理解计算：从 √2 到 AlphaGo ——第 1 季 从 √2 谈起 SIGAI 2018.6.20
[27] 场景文本检测——CTPN 算法介绍 SIGAI2018.6.22
[28] 卷积神经网络的压缩和加速 SIGAI2018.6.25
[29] k 近邻算法 SIGAI 2018.6.27
[30] 自然场景文本检测识别技术综述 SIGAI 2018.6.27
[31] 理解计算：从 √2 到 AlphaGo ——第 2 季 神经计算的历史背景 SIGAI2018.7.4
[32] 机器学习算法地图 SIGAI2018.7.6
[33] 反向传播算法推导-全连接神经网络 SIGAI2018.7.9
[34] 生成式对抗网络模型综述 SIGAI0709.
[35] 怎样成为一名优秀的算法工程师 SIGAI0711.
[36]理解计算：从根号 2 到 AlphaGo——第三季 神经网络的数学模型 SIGAI0716
[38] 基于深度负相关学习的人群计数方法 【获取码】SIGAI0718
[39] 流形学习概述【获取码】SIGAI0720
[40] 关于感受野的总结 【获取码】SIGAI0723
[41] 随机森林概述 【获取码】SIGAI0725
注意：本文归作者所有，未经作者允许，不得转载
