本博客中使用的代码见本文末尾
度量两张图片的相似度有许多算法, 本文讲介绍工程领域中最常用的图片相似度算法之一 --Hash 算法. Hash 算法准确的说有三种, 分别为平均哈希算法 (aHash), 感知哈希算法你(pHash) 和差异哈哈希算法(dHash).
三种 Hash 算法都是通过获取图片的 hash 值, 再比较两张图片 hash 值的汉明距离 (韩明距离的概念可见本公众号《》一文) 来度量两张图片是否相似. 两张图片越相似, 那么两张图片的 hash 数的汉明距离越小. 下面本文将分别介绍这三种 Hash 算法.
1 平均哈希算法(aHash)
1.1 算法步骤
平均哈希算法是三种 Hash 算法中最简单的一种, 它通过下面几个步骤来获得图片的 Hash 值, 这几个步骤分别是 (1) 缩放图片;(2) 转灰度图; (3) 算像素均值;(4)根据相似均值计算指纹. 具体算法如下所示:
表 1 aHash 得到图片 Hash 值地算法
步骤 | 具体内容 |
---|---|
缩放图片 | 输入图片大小尺寸各异,为了统一图片的输入,统一将图片尺寸缩放为 8*8,一共得到了 64 个像素点。 |
转灰度图 | 输入图片有些为单通道灰度图,有些 RGB 三通道彩色图,有些为 RGBA 四通道彩色图。也为了统一下一步输入标准,将非单通道图片都转为单通道灰度图。 其中 RGB 三通道转单通道算法有下面几种: 1. 浮点算法:Gray=R0.3+G 0.59+B0.11 30+G59+B 11)/100 151+B*28)>>8; |
算像素均值 | 通过上一步可得一个 8x8 的整数矩阵 G,计算这个矩阵中所有元素的平均值,假设其值为 a |
据像素均值计算指纹 | 初始化输入图片的 ahash = "" 从左到右一行一行地遍历矩阵 G 每一个像素如果第 i 行 j 列元素 G(i,j) >= a,则 ahash +="1"如果第 i 行 j 列元素 G(i,j) |
得到图片的 ahash 值后, 比较两张图片 ahash 值的汉明距离, 通常认为汉明距离小于 10 的一组图片为相似图片.
1.2 具体实例
本文图片为 Lena 图来说明.
图 1 Lena(Origin)图
图 2 转为 8x8 尺寸的 Lena 图
图 3 转为灰度 8x8 尺寸的 Lena 图
其中转为 8x8 尺寸的 Lena 对应的数据矩阵为:
很容得到如上矩阵所有元素的均值 a= 121.328125, 将上述矩阵中大于或等于 a 的元素置为 1, 小于 a 的元素置为 0, 可得:
所以可得 Lena 图的 aHash 为
1011111010011110100111011010100110101011101000110000111000101100
将二进制形式 ahash 转十六进制 hash 为
be9e9da9aba30e2c
为了测试 aHash 算法的效果, 我们用一张带噪声 Lena(noise)图和与 Lena 不一样的 Barbara 做图片相似度对比实验, 其中 Lena(noise)和 Barbara 如下:
图 4 Lena(noise)图
图 5 Barbara 图
通过 aHash 算法容易得三个图片的 hash 值, 然后根据 hanming 距离计算 Lena(origin).PNG 和 Lena(noise).PNG Barbar.PNG 之间汉明距离, 具体如下:
图 6 aHash 算法图片相似度实验
由上图可见 aHash 能区别相似图片和差异大的图片.
2 感知哈希算法(pHash)
2.1 算法步骤
感知哈希算法是三种 Hash 算法中较为复杂的一种, 它是基于 DCT(离散余弦变换)来得到图片的 hash 值, 其算法几个步骤分别是 (1) 缩放图片;(2) 转灰度图; (3) 计算 DCT;(4)缩小 DCT; (5)算平均值;(6) 计算指纹. 具体算法如下所示:
表 2 pHash 得到图片 Hash 值地算法
步骤 | 具体内容 |
---|---|
缩放图片 | 统一将图片尺寸缩放为 32*32,一共得到了 1024 个像素点。 |
转灰度图 | 统一下一步输入标准,将非单通道图片都转为单通道灰度图。 |
计算 DCT | 计算 32x32 数据矩阵的离散余弦变换后对应的 32x32 数据矩阵 |
缩小 DCT | 取上一步得到 32x32 数据矩阵左上角 8x8 子区域 |
算平均值 | 通过上一步可得一个 8x8 的整数矩阵 G, 计算这个矩阵中所有元素的平均值,假设其值为 a |
计算指纹 | 初始化输入图片的 phash = "" 从左到右一行一行地遍历矩阵 G 每一个像素 < br ztid="139"ow="0"oh="0"> 如果第 i 行 j 列元素 G(i,j) >= a,则 phash +="1" 如果第 i 行 j 列元素 G(i,j) |
得到图片的 phash 值后, 比较两张图片 phash 值的汉明距离, 通常认为汉明距离小于 10 的一组图片为相似图片.
2.2 具体实例
仍用 Lena 图来说明.
图 7 转为灰度 32x32 尺寸的 Lena 图
图 8 灰度 32x32 尺寸 Lena 图对应的 DCT 矩阵
通过计算可得灰度 32x32Lenna 图对应的 DCT 矩阵左上角 8x8 区域子矩阵为:
很容得到如上矩阵所有元素的均值 a= 77.35, 将上述矩阵中大于或等于 a 的元素置为 1, 小于 a 的元素置为 0, 可得:
所以可得 Lena 图的 pHash 为
1001100111000100010101000010010101100000001000111000001010000000
将二进制形式 phash 转十六进制 hash 为
99c4542560238280
为了测试 pHash 算法的效果, 同样用一张带噪声 Lena(noise)图和与 Lena 不一样的 Barbara 做图片相似度对比实验. 通过 pHash 算法容易得三个图片的 hash 值, 然后根据 hanming 距离计算 Lena(origin).PNG 和 Lena(noise).PNG Barbar.PNG 之间汉明距离, 具体如下:
图 9 pHash 算法图片相似度实验
由上图可见 pHash 能区别相似图片和差异大的图片.
3 差异哈希算法(dHash)
3.1 算法步骤
相比 pHash,dHash 的速度要快的多, 相比 aHash,dHash 在效率几乎相同的情况下的效果要更好, 它是基于渐变实现的. 其算法几个步骤分别是 (1) 缩放图片;(2) 转灰度图; (3) 计算 DCT;
(4)缩小 DCT; (5)算平均值;(6) 计算指纹. 具体算法如下所示:
表 3 dHash 得到图片 Hash 值地算法
步骤 | 具体内容 |
---|---|
小图片 | 统一将图片尺寸缩放为 9x8,一共得到了 72 个像素点 |
转灰度图 | 统一下一步输入标准,将非单通道图片都转为单通道灰度图。 |
算差异值 | 当前行像素值 - 前一行像素值, 从第二到第九行共 8 行,又因为矩阵有 8 列,所以得到一个 8x8 差分矩阵 G |
算平均值 | 通过上一步可得一个 8x8 的整数矩阵 G, 计算这个矩阵中所有元素的平均值,假设其值为 a |
计算指纹 | 初始化输入图片的 dhash = "" 从左到右一行一行地遍历矩阵 G 每一个像素 < br ztid="194"ow="0"oh="0"> 如果第 i 行 j 列元素 G(i,j) >= a,则 dhash +="1" 如果第 i 行 j 列元素 G(i,j) |
得到图片的 phash 值后, 比较两张图片 phash 值的汉明距离, 通常认为汉明距离小于 10 的一组图片为相似图片.
3.2 具体实例
仍用 Lena 图来说明.
图 7 转为灰度 9x8 尺寸的 Lena 图
通过计算可得灰度 9x8Lenna 图数据矩阵为:
从第二行开始进行减去前一行操作, 可得如下查分矩阵
将上述矩阵中大于或等于 0 元素置为 1, 小于 a 的元素置为 0, 可得:
所以可得 Lena 图的 dHash 为
0101100000110111111010000101001001101011101011110001010001010000
将二进制形式 dhash 转十六进制 hash 为
99c4542560238280
为了测试 dHash 算法的效果, 同样用一张带噪声 Lena(noise)图和与 Lena 不一样的 Barbara 做图片相似度对比实验. 通过 pHash 算法容易得三个图片的 hash 值, 然后根据 hanming 距离计算 Lena(origin).PNG 和 Lena(noise).PNG Barbar.PNG 之间汉明距离, 具体如下:
图 9 dHash 算法图片相似度实验
由上图可见 dHash 能区别相似图片和差异大的图片.
总结
关于图像相似度算法除了 Hash 算法, 在传统算法领域中还有基于 SIFT 的匹配算法, 基于 Gist 特征的匹配算法; 在深度学习领域中有基于 ResNet 全连接的匹配算法. 感兴趣的读者可以通过 google 来了解这些算法.
参考资料
本文代码
GitHub 代码 https://github.com/Kalafinaian/blog_code
来源: https://www.cnblogs.com/Kalafinaian/p/11260808.html