图像相似度中的Hash算法

水深无声 2023-08-17 15:16 77阅读 0赞

**本博客中使用的代码见本文末尾**

度量两张图片的相似度有许多算法，本文讲介绍工程领域中最常用的图片相似度算法之一——Hash算法。Hash算法准确的说有三种，分别为平均哈希算法(aHash)、感知哈希算法你(pHash)和差异哈哈希算法(dHash)。

三种Hash算法都是通过获取图片的hash值，再比较两张图片hash值的汉明距离(韩明距离的概念可见本公众号《》一文)来度量两张图片是否相似。两张图片越相似，那么两张图片的hash数的汉明距离越小。下面本文将分别介绍这三种Hash算法。

# 1 平均哈希算法（aHash） #

## 1.1 算法步骤 ##

平均哈希算法是三种Hash算法中最简单的一种，它通过下面几个步骤来获得图片的Hash值，这几个步骤分别是(1) 缩放图片；（2）转灰度图; (3) 算像素均值；（4）根据相似均值计算指纹。具体算法如下所示:

表1 aHash得到图片Hash值地算法

<table> 
 <thead> 
  <tr> 
   <th style="text-align:center;">步骤</th> 
   <th style="text-align:left;">具体内容</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="text-align:center;">缩放图片</td> 
   <td style="text-align:left;">输入图片大小尺寸各异，为了统一图片的输入，统一将图片尺寸缩放为8*8，一共得到了64个像素点。</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">转灰度图</td> 
   <td style="text-align:left;">输入图片有些为单通道灰度图，有些RGB三通道彩色图，有些为RGBA四通道彩色图。也为了统一下一步输入标准，将非单通道图片都转为单通道灰度图。 其中RGB三通道转单通道算法有下面几种:<br>1.浮点算法：Gray=R<em>0.3+G</em>0.59+B<em>0.11<br>2.整数方法：Gray=(R</em>30+G<em>59+B</em>11)/100<br> 3.移位方法：Gray =(R<em>76+G</em>151+B*28)&gt;&gt;8; <br>4.平均值法：Gray=（R+G+B）/3; <br>5.仅取绿色：Gray=G；</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">算像素均值</td> 
   <td style="text-align:left;">通过上一步可得一个8x8的整数矩阵G，计算这个矩阵中所有元素的平均值，假设其值为a</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">据像素均值计算指纹</td> 
   <td style="text-align:left;">初始化输入图片的ahash = "" <br>从左到右一行一行地遍历矩阵G每一个像素如果第i行j列元素G(i,j) &gt;= a，则ahash += "1"如果第i行j列元素G(i,j) &lt;a， 则ahash += "0"</td> 
  </tr> 
 </tbody> 
</table>

得到图片的ahash值后，比较两张图片ahash值的汉明距离，通常认为汉明距离小于10的一组图片为相似图片。

## 1.2 具体实例 ##

本文图片为Lena图来说明.

![1180694-20190728203332334-1937770367.png][]  
图1 Lena(Origin)图![1180694-20190728203353051-1451482282.png][]  
图2 转为8x8尺寸的Lena图![1180694-20190728203407828-102610299.png][]  
图3 转为灰度8x8尺寸的Lena图

其中转为8x8尺寸的Lena对应的数据矩阵为:

![1180694-20190728203430886-1727245248.png][]

很容得到如上矩阵所有元素的均值a= 121.328125, 将上述矩阵中大于或等于a的元素置为1, 小于a的元素置为0，可得：

![1180694-20190728203456548-1330466930.png][]

所以可得Lena图的aHash为

1011111010011110100111011010100110101011101000110000111000101100

将二进制形式ahash转十六进制hash为

be9e9da9aba30e2c

为了测试aHash算法的效果，我们用一张带噪声Lena(noise)图和与Lena不一样的Barbara做图片相似度对比实验，其中Lena(noise)和Barbara如下:

![1180694-20190728203523628-1749121579.png][]  
图4 Lena(noise)图![1180694-20190728203547647-338202473.jpg][]  
图5 Barbara图

通过aHash算法容易得三个图片的hash值，然后根据hanming距离计算Lena(origin).png和Lena(noise).png Barbar.png之间汉明距离，具体如下:

![1180694-20190728203611932-1707762231.png][]  
图6 aHash算法图片相似度实验

由上图可见aHash能区别相似图片和差异大的图片。

# 2 感知哈希算法（pHash） #

## 2.1 算法步骤 ##

感知哈希算法是三种Hash算法中较为复杂的一种，它是基于DCT（离散余弦变换）来得到图片的hash值，其算法几个步骤分别是(1) 缩放图片；（2）转灰度图; (3) 计算DCT；（4）缩小DCT; (5)算平均值；(6) 计算指纹。具体算法如下所示:

表2 pHash得到图片Hash值地算法

<table> 
 <thead> 
  <tr> 
   <th style="text-align:center;">步骤</th> 
   <th style="text-align:left;">具体内容</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="text-align:center;">缩放图片</td> 
   <td style="text-align:left;">统一将图片尺寸缩放为32*32，一共得到了1024个像素点。</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">转灰度图</td> 
   <td style="text-align:left;">统一下一步输入标准，将非单通道图片都转为单通道灰度图。</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">计算DCT</td> 
   <td style="text-align:left;">计算32x32数据矩阵的离散余弦变换后对应的32x32数据矩阵</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">缩小DCT</td> 
   <td style="text-align:left;">取上一步得到32x32数据矩阵左上角8x8子区域</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">算平均值</td> 
   <td style="text-align:left;">通过上一步可得一个8x8的整数矩阵G, 计算这个矩阵中所有元素的平均值，假设其值为a</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">计算指纹</td> 
   <td style="text-align:left;">初始化输入图片的phash = ""<br>从左到右一行一行地遍历矩阵G每一个像素<br>如果第i行j列元素G(i,j) &gt;= a，则phash += "1"<br>如果第i行j列元素G(i,j) &lt;a， 则phash += "0"</td> 
  </tr> 
 </tbody> 
</table>

得到图片的phash值后，比较两张图片phash值的汉明距离，通常认为汉明距离小于10的一组图片为相似图片。

## 2.2 具体实例 ##

仍用Lena图来说明.

![1180694-20190728203639341-869018741.png][]  
图7 转为灰度32x32尺寸的Lena图![1180694-20190728203703007-26099029.png][]  
图8 灰度32x32尺寸Lena图对应的DCT矩阵

通过计算可得灰度32x32Lenna图对应的DCT矩阵左上角8x8区域子矩阵为:

![1180694-20190728203724225-1309910173.png][]

很容得到如上矩阵所有元素的均值a= 77.35, 将上述矩阵中大于或等于a的元素置为1, 小于a的元素置为0，可得：

![1180694-20190728203745755-1114656269.png][]

所以可得Lena图的pHash为

1001100111000100010101000010010101100000001000111000001010000000

将二进制形式phash转十六进制hash为

99c4542560238280

为了测试pHash算法的效果，同样用一张带噪声Lena(noise)图和与Lena不一样的Barbara做图片相似度对比实验。通过pHash算法容易得三个图片的hash值，然后根据hanming距离计算Lena(origin).png和Lena(noise).png Barbar.png之间汉明距离，具体如下:

![1180694-20190728203805272-799151123.png][]  
图9 pHash算法图片相似度实验

由上图可见pHash能区别相似图片和差异大的图片。

# 3 差异哈希算法（dHash） #

## 3.1 算法步骤 ##

相比pHash，dHash的速度要快的多，相比aHash，dHash在效率几乎相同的情况下的效果要更好，它是基于渐变实现的。其算法几个步骤分别是(1) 缩放图片；（2）转灰度图; (3) 计算DCT；  
（4）缩小DCT; (5)算平均值；(6) 计算指纹。具体算法如下所示:

表3 dHash得到图片Hash值地算法

<table> 
 <thead> 
  <tr> 
   <th style="text-align:center;">步骤</th> 
   <th style="text-align:left;">具体内容</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="text-align:center;">小图片</td> 
   <td style="text-align:left;">统一将图片尺寸缩放为9x8，一共得到了72个像素点</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">转灰度图</td> 
   <td style="text-align:left;">统一下一步输入标准，将非单通道图片都转为单通道灰度图。</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">算差异值</td> 
   <td style="text-align:left;">当前行像素值-前一行像素值， 从第二到第九行共8行，又因为矩阵有8列，所以得到一个8x8差分矩阵G</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">算平均值</td> 
   <td style="text-align:left;">通过上一步可得一个8x8的整数矩阵G, 计算这个矩阵中所有元素的平均值，假设其值为a</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">计算指纹</td> 
   <td style="text-align:left;">初始化输入图片的dhash = ""<br>从左到右一行一行地遍历矩阵G每一个像素<br>如果第i行j列元素G(i,j) &gt;= a，则dhash += "1"<br>如果第i行j列元素G(i,j) &lt;a， 则dhash += "0"</td> 
  </tr> 
 </tbody> 
</table>

得到图片的phash值后，比较两张图片phash值的汉明距离，通常认为汉明距离小于10的一组图片为相似图片。

## 3.2 具体实例 ##

仍用Lena图来说明.

![1180694-20190728203837943-1643707343.png][]  
图7 转为灰度9x8尺寸的Lena图

通过计算可得灰度9x8Lenna图数据矩阵为:

![1180694-20190728203900096-1993619560.png][]

从第二行开始进行减去前一行操作，可得如下查分矩阵

![1180694-20190728203929772-1653871644.png][]

将上述矩阵中大于或等于0元素置为1, 小于a的元素置为0，可得：

![1180694-20190728203959284-775360251.png][]

所以可得Lena图的dHash为

0101100000110111111010000101001001101011101011110001010001010000

将二进制形式dhash转十六进制hash为

99c4542560238280

为了测试dHash算法的效果，同样用一张带噪声Lena(noise)图和与Lena不一样的Barbara做图片相似度对比实验。通过pHash算法容易得三个图片的hash值，然后根据hanming距离计算Lena(origin).png和Lena(noise).png Barbar.png之间汉明距离，具体如下:

![1180694-20190728204021974-1582207230.png][]  
图9 dHash算法图片相似度实验

由上图可见dHash能区别相似图片和差异大的图片。

# 总结 #

关于图像相似度算法除了Hash算法，在传统算法领域中还有基于SIFT的匹配算法，基于Gist特征的匹配算法；在深度学习领域中有基于ResNet全连接的匹配算法。感兴趣的读者可以通过google来了解这些算法。

## 参考资料 ##

[432-Looks-Like-It][]  
[529-Kind-of-Like-That][]

## 本文代码 ##

[Github代码][Github]

转载于:https://www.cnblogs.com/Kalafinaian/p/11260808.html

[1180694-20190728203332334-1937770367.png]: /images/20230810/86b6bd802d8d4a13a1a78d28bf7d9d68.png
[1180694-20190728203353051-1451482282.png]: /images/20230810/f7f06638973749bba14f501d8f80dd9d.png
[1180694-20190728203407828-102610299.png]: /images/20230810/560480334a4f4ade9e27d87d65792645.png
[1180694-20190728203430886-1727245248.png]: /images/20230810/2cb29157eb464a91ac34024fc5847c9a.png
[1180694-20190728203456548-1330466930.png]: /images/20230810/654d175d841c4cfe89c125f35b1fb7bc.png
[1180694-20190728203523628-1749121579.png]: /images/20230810/436a681ec6cb4370a65c2a627375a5b2.png
[1180694-20190728203547647-338202473.jpg]: /images/20230810/e545151a05c648019842a1bb3102a48a.png
[1180694-20190728203611932-1707762231.png]: /images/20230810/8c341eb69f494833a84295e52c590f00.png
[1180694-20190728203639341-869018741.png]: /images/20230810/5cb596a17f3c4eba869865b5cb197e05.png
[1180694-20190728203703007-26099029.png]: /images/20230810/531b4f3b6e8947518e9d145d905c7b8c.png
[1180694-20190728203724225-1309910173.png]: /images/20230810/dde456dfa86249309461f87be3e4a2c9.png
[1180694-20190728203745755-1114656269.png]: /images/20230810/7e7432448a8c49788ba17fe11f53c820.png
[1180694-20190728203805272-799151123.png]: /images/20230810/ff3957e6360446688809d39314410696.png
[1180694-20190728203837943-1643707343.png]: /images/20230810/252b0f30fc964b8eb6f3dffb5a8f301f.png
[1180694-20190728203900096-1993619560.png]: /images/20230810/c35de86236b24be7ab0c339b858357ec.png
[1180694-20190728203929772-1653871644.png]: /images/20230810/5193c042a88147e3bb35a6a048ae4b89.png
[1180694-20190728203959284-775360251.png]: /images/20230810/4b381b3b78a9454abfd695e783b6f2d9.png
[1180694-20190728204021974-1582207230.png]: /images/20230810/354c9e45272c4291950467ba0e7d1145.png
[432-Looks-Like-It]: http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html
[529-Kind-of-Like-That]: http://www.hackerfactor.com/blog/index.php?/archives/529-Kind-of-Like-That.html
[Github]: https://github.com/Kalafinaian/blog_code