直方图计算法

这里先用直方图进行简单讲述。

先借用一下 恋花蝶 的图片,

从肉眼来看,这两张图片大概也有八成是相似的了。

在python中可以依靠 Image 对象的 histogram() 方法获取其直方图数据,但这个方法返回的结果是一个列表,如果想得到下图可视化数据,需要另外使用 matplotlib ,这里因为主要介绍算法思路, matplotlib 的使用这里不做介绍。

是的,我们可以明显的发现,两张图片的直方图是近似重合的。所以利用直方图判断两张图片的是否相似的方法就是,计算其直方图的重合程度即可。

计算方法如下:

$$

\frac{1}{N}\sum_{i=1}^n\left(1-\frac{|g_i-s_i|}{Mac(g_i,s_i)}\right)

$$

其中gi和si是分别指两条曲线的第i个点。

最后计算得出的结果就是就是其相似程度。

不过,这种方法有一个明显的弱点,就是他是按照颜色的全局分布来看的,无法描述颜色的局部分布和色彩所处的位置。

也就是假如一张图片以蓝色为主,内容是一片蓝天,而另外一张图片也是蓝色为主,但是内容却是妹子穿了蓝色裙子,那么这个算法也很可能认为这两张图片的相似的。

缓解这个弱点有一个方法就是利用 Image 的 crop 方法把图片等分,然后再分别计算其相似度,最后综合考虑。
图像指纹与汉明距离

在介绍下面其他判别相似度的方法前,先补充一些概念。第一个就是 图像指纹

图像指纹和人的指纹一样,是身份的象征,而图像指纹简单点来讲, 就是将图像按照一定的哈希算法,经过运算后得出的一组二进制数字。

说到这里,就可以顺带引出 汉明距离 的概念了。

假如一组二进制数据为 101 ,另外一组为 111 ,那么显然把第一组的第二位数据 0 改成 1 就可以变成第二组数据 111 ,所以两组数据的汉明距离就为 1

简单点说,汉明距离就是 一组二进制数据变成另一组数据所需的步骤数 ,显然,这个数值可以 衡量两张图片的差异 ,汉明距离越小,则代表相似度越高。汉明距离为0,即代表两张图片完全一样。

如何计算得到汉明距离,情况下面三种哈希算法
平均哈希法(aHash)

此算法是基于比较灰度图每个像素与平均值来实现的

一般步骤

1.缩放图片,可利用 Image 对象的 resize(size) 改变,一般大小为8*864个像素值。

2.转化为灰度图转灰度图的算法。

    1.浮点算法:Gray=Rx0.3+Gx0.59+Bx0.11

    2.整数方法:Gray=(Rx30+Gx59+Bx11)/100

    3.移位方法:Gray =(Rx76+Gx151+Bx28)>>8;

    4.平均值法:Gray=(R+G+B)/3;

    5.仅取绿色:Gray=G;

在 python 中,可用 Image 的对象的方法 convert(‘L’) 直接转换为灰度图

3.计算平均值:计算进行灰度处理后图片的所有像素点的平均值。

4.比较像素灰度值:遍历灰度图片每一个像素,如果大于平均值记录为1,否则为0.

5.得到信息指纹:组合64个bit位,顺序随意保持一致性。

最后比对两张图片的指纹,获得汉明距离即可。
感知哈希算法(pHash)

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

一般步骤:

缩小图片: 32 * 32 是一个较好的大小,这样方便DCT计算

转化为灰度图:把缩放后的图片转化为256阶的灰度图。(具体算法见平均哈希算法步骤)

计算DCT:DCT把图片分离成分率的集合

缩小DCTDCT是 32 * 32 ,保留左上角的 8 * 8 ,这些代表的图片的最低频率

计算平均值:计算缩小DCT后的所有像素点的平均值。

进一步减小DCT:大于平均值记录为1,反之记录为0.

得到信息指纹:组合64个信息位,顺序随意保持一致性。

最后比对两张图片的指纹,获得汉明距离即可。

这里给出别人的DCT的介绍和计算方法(离散余弦变换的方法)

DCT的维基百科
luoweifu的博客
dHash算法

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

步骤:

缩小图片:收缩到9*8的大小,一遍它有72的像素点

转化为灰度图:把缩放后的图片转化为256阶的灰度图。(具体算法见平均哈希算法步骤)

计算差异值:dHash算法工作在相邻像素之间,这样每行9个像素之间产生了8个不同的差异,一共8行,则产生了64个差异值

获得指纹:如果左边的像素比右边的更亮,则记录为1,否则为0.最后比对两张图片的指纹,获得汉明距离即可。

总结

这几种算法是识别相似图像的基础,显然,有时两图中的人相似比整体的颜色相似更重要,所以我们有时需要进行人脸识别,然后在脸部区进行局部哈希,或者进行其他的预处理再进行哈希,这里涉及其他知识本文不作介绍。

文档更新时间: 2019-06-14 13:43   作者:月影鹏鹏