相似图片搜索算法介绍

妖狐艹你老母 2022-06-10 14:06 256阅读 0赞

## 前言 ##

之前对图片聚类有一丢丢的研究，最近发现，使用一些相似图片搜索算法也可以实现图片聚类的目标：将同类别或差不多的图片聚在一起。所以整理出相似图片搜索算法介绍这篇文章，主要介绍AutoEncoder、based CNN、Hash等算法，细分又包括：AutoEncoder、Siamese Network、2-channel、Central-surround two-stream network、aHash、pHash、dHash等算法。

## AutoEncoder ##

AE作为一种无监督算法，通过encode和decode两个过程实现，当encode和decode过程均为一层时，AE很类似PCA；多层时，又有些类似神经网络。

![Center][]

如上图所示，code左侧的为encode层，右侧为decode层，目的是使得输入的x和输出的x\_head越接近越好，所以在误差反向传播时需要优化x和x\_head的差异值。通过encode和decode两个过程，AE可以提取图片特征，不断的训练之后就可以通过得到的特征参数对相似图片进行搜索。AutoEncoder详细介绍 [点击这里][Link 1]。

我的 [一篇文章][Link 2]实现了AutoEncoder对MNIST数据集的特征提取； [另一篇文章][Link 3]实现了AutoEncoder对相似图片的搜索。

## Based CNN ##

这个板块中的算法来自 [这篇论文][Link 4]，主要介绍了Siamese Network、2-channel、Central-surround two-stream network、SSP几种算法，并对比他们之间的联系和区别。

### Siamese Network ###

这个算法最初用于手写签字的识别，之后又应用在相似图片的处理上面，如下图所示，patch1和patch2为输入图片，两张图片分别经过卷积层（包括卷积、ReLU、最大池化等过程），得到两个特征向量，接着进入黄色的全连接层，最后输出两个图片的相似度。在Siamese Network算法中，两个patch在卷积层中的权值共享。

论文中有对Siamese Network算法进行改进，变为Pseudo-siamese算法，这个算法与Siamese Network的区别为：卷积层中的权值不共享，在下图中间部分可以看到。

![Center 1][]

## 2-channel ##

channel这个词最先是在图片灰度上面提到的，像MNIST数据集，图片都是黑白的，channel为1，彩色图片channel为3，分为R、G、B三个channel，顾名思义，这个算法就是由两个channel组成，这两个channel就是要比较的两张图片，如下图所示，与上面Siamese Network算法的不同之处在于，这个算法合并了上面的两个卷积层，使两张图片编程一张，举个例子，有两张（1，32，32）的黑白图片，放在这个算法中，就相当于是对卷积层输入一个（2，32，32）的图片，然后在经过一层全连接，输出一个值，这个输出的值就表示两张图片的差异。

![Center 2][]

### Central-surround two-stream network ###

这个算法在2-channel的基础上进行了改进，对比上下两张图，如果不考虑右侧蓝色块，仅考虑左侧的结构，和2-channel是一样的，这个算法的改进之处在于：

首先，左侧输入的图片不再是原图，而是经过了处理，如图所示，经过了下采样，使得图像变小，Paper中介绍的原图patch大小为64\*64，那么在左侧的输入为32\*32。其次，右侧的输入图片为原始图片的中心部分，大小也是32\*32，这样一来，左右两侧的输入图片大小相等。

![Center 3][]

### SSP ###

我们平时的输入图片多为32\*32、64\*64、128\*128这种，图片的长和宽都是确定的，如果原始图片的长和宽不确定，我们使用前需要进行预处理，这样就影响了图片的精度，SSP算法就是为了解决这个问题。

## Hash Method ##

Hash算法作为大多图片搜索引擎的核心算法，其准确率和效率均很高，本板块将介绍Hash的三种核心算法：aHash、pHash、dHash。

### aHash ###

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

![Center 4][] ![Center 5][]

### 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.得到信息指纹：组合64个信息位，顺序随意保持一致性即可。  
8.对比指纹：计算两幅图片的指纹，计算汉明距离（从一个指纹到另一个指纹需要变几次），汉明距离越大则说明图片越不一致，反之，汉明距离越小则说明图片越相似，当距离为0时，说明完全相同。（通常认为距离>10 就是两张完全不同的图片）

### dHash ###

相比pHash，dHash的速度要快的多，相比aHash，dHash在效率几乎相同的情况下的效果要更好，它是基于渐变实现的。  
步骤：  
1.缩小图片：收缩到9\*8的大小，一遍它有72的像素点  
2.转化为灰度图：把缩放后的图片转化为256阶的灰度图。（具体算法见平均哈希算法步骤）  
3.计算差异值：dHash算法工作在相邻像素之间，这样每行9个像素之间产生了8个不同的差异，一共8行，则产生了64个差异值  
4.获得指纹：如果左边的像素比右边的更亮，则记录为1，否则为0.

## 参考资料 ##

[http://www.phash.org/download/][http_www.phash.org_download]

[http://soledede.iteye.com/blog/1940910  
][http_soledede.iteye.com_blog_1940910]

[https://github.com/hjaurum/DHash/blob/master/dHash.py  
][http_soledede.iteye.com_blog_1940910]

[http://python.jobbole.com/81277/][http_python.jobbole.com_81277]

[Center]: /images/20220610/f1030f17709344c68be4e303d34beaa1.png
[Link 1]: http://blog.csdn.net/roguesir/article/details/77469665
[Link 2]: http://blog.csdn.net/roguesir/article/details/77248171
[Link 3]: http://blog.csdn.net/roguesir/article/details/77449992
[Link 4]: https://arxiv.org/abs/1504.03641
[Center 1]: /images/20220610/3e31b85e359149d5acf63fad6e4cfe7e.png
[Center 2]: /images/20220610/f6ebb7adb21a4678a33314c75bd67a6f.png
[Center 3]: /images/20220610/d5be27df0101435da138be66beb165da.png
[Center 4]: https://img-blog.csdn.net/20170821170400710?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcm9ndWVzaXI=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 5]: /images/20220610/19a4813f2bfb4f6d881747f4fc9ee946.png
[http_www.phash.org_download]: http://www.phash.org/download/
[http_soledede.iteye.com_blog_1940910]: http://soledede.iteye.com/blog/1940910
[http_python.jobbole.com_81277]: http://python.jobbole.com/81277/