详解相似图片匹配算法：差异值哈希算法 + 颜色直方图

eternalshallow 发布于2019-07-31 10:17 / 3409人阅读

摘要：由于最近涉及到匹配相似图片的问题，所以在此记录下解决办法差异值哈希算法颜色直方图环境要求库库差异值哈希算法检索相似图片，第一个想到的就是差异值哈希算法。

由于最近涉及到匹配相似图片的问题，所以在此记录下解决办法：差异值哈希算法 + 颜色直方图

环境要求：Python cv2库 math库

差异值哈希算法

检索相似图片，第一个想到的就是差异值哈希算法。这个算法的步骤是：

缩小尺寸
一般将图片缩放为 8 * 8 的尺寸大小，共64个像素的图片。但是由于64个像素对于我来说，损失的细节太多所以我选择了缩放到 33 * 32 的尺寸大小

彩色图像灰度化
由于我们现有的图片是由 RGB 三原色构成，每个像素点是一个由这三个颜色组成的一个 list 。而 RGB 三个颜色中每个颜色值都是用 8 个比特来表示，大小范围是 0 ～ 255(2^8 - 1)，就一共有 256 * 256 * 256 种颜色。并且作为一个像素类似于这样的数值：[253 255 255] 是不利于简单比较的，肉眼看着类似的颜色，但是它的三个颜色分布可能相差很多。所以将它灰度化，用 256 个不同的灰色表示现有的图片。由于现在用一种灰色表示三种颜色，原来每个像素是一个 list 现在就降维成一个数值，数值的大小还是比较容易比较的。

比较像素的灰度值
比较图片灰度化的每行相邻像素之间的大小，每行后面像素值大于前面一个像素值那么记为1，如果不大于则记为0

计算哈希值
根据上一步得到了由0和1构成的数组合在一起就构成了1024位的整数

对比不同图片的汉明距离
对比两个图片生成的整数有多少位不一样。一般汉明距离小于 5 ，两张图片的相似度就很高了。

差异值哈希算法的 Python 代码

import cv2

# 差异值哈希算法
def dhash(image):
    resize_height, resized_width = 32, 33
    # 缩放到(resized_width, resize_height)尺寸的大小
    resized_img = cv2.resize(image, (resized_width, resize_height))
    # 图片灰度化
    grey_resized_img = cv2.cvtColor(resized_img, cv2.COLOR_RGB2GRAY)
    # 差异值计算
    hash_list = []
    for row in range(resize_height):
        for col in range(resized_width - 1):
            # 每行前一个颜色强度大于后一个，值为1，否则值为0
            if grey_resized_img[row, col] > grey_resized_img[row, col + 1]:
                hash_list.append("1")
            else:
                hash_list.append("0")

    return "" . join(hash_list)

# 比较汉明距离
def hamming_distance(dhash1, dhash2):
    return bin(int(dhash1, base = 2) ^ int(dhash2, base = 2)).count("1")

# 读取图片内容
img1 = cv2.imread(img1_path)
# 读取图片内容
img2 = cv2.imread(img2_path)
if hamming_distance(dhash(img1), dhash(img2)) <= 5:
    print("相似图片")

颜色直方图

由于差异值哈希失去了太多的细节，适合比较原图或者缩略图。所以我再加上颜色直方图的比较计算图片间的接近程度，用以排除部分像素的微小差异。

缩小尺寸
一般将图片缩放为 8 * 8 的尺寸大小，共64个像素的图片。但是由于64个像素对于我来说，损失的细节太多所以我选择了缩放到 32 * 32 的尺寸大小

降低位深
原来 RGB 每个颜色都有 256 种变化，现在做一个映射，将原来的 256 分为 8(3个比特表示) 个颜色区间。类似旧的 0 - 31 对应新的颜色 0，以达到降低计算的效果

计算像素值
由于降低了位深，图片颜色值变小。每个颜色值不大于8（0 - 7），然后我们给三元素不同的权重，分别为 8 * 8，8，1 作为数组的 key，用以统计每个颜色的像素出现次数，并且不会出现不同颜色统计到了同一个 key 值下的目的。

计算相似度
计算出像素值后得到，我们得到了以不同颜色的数值为 key，出现次数为 value 的数组。这时候我们可以使用用余弦相似度去计算相同颜色出现次数的相似度，越是相似的像素最后值越接近于1。截图来自于WiKi

颜色直方图的 Python 代码

import cv2
from math import sqrt

# 颜色映射
def bgr_mapping(img_val):
    # 将bgr颜色分成8个区间做映射
    if img_val >= 0 and img_val <= 31: return 0
    if img_val >= 32 and img_val <= 63: return 1
    if img_val >= 64 and img_val <= 95: return 2
    if img_val >= 96 and img_val <= 127: return 3
    if img_val >= 128 and img_val <= 159: return 4
    if img_val >= 160 and img_val <= 191: return 5
    if img_val >= 192 and img_val <= 223: return 6
    if img_val >= 224: return 7

# 颜色直方图的数值计算
def calc_bgr_hist(image):
    if not image.size: return False
    hist = {}
    # 缩放尺寸减小计算量
    image = cv2.resize(image, (32, 32))
    for bgr_list in image:
        for bgr in bgr_list:
            # 颜色按照顺序映射
            maped_b = bgr_mapping(bgr[0])
            maped_g = bgr_mapping(bgr[1])
            maped_r = bgr_mapping(bgr[2])
            # 计算像素值
            index   = maped_b * 8 * 8 + maped_g * 8 + maped_r
            hist[index] = hist.get(index, 0) + 1
    
    return hist

# 计算两张图片的相似度
def compare_similar_hist(h1, h2):
    if not h1 or not h2: return False
    sum1, sum2, sum_mixd = 0, 0, 0
    # 像素值key的最大数不超过512，直接循环到512，遍历取出每个像素值
    for i in range(512):
        # 计算出现相同像素值次数的平方和
        sum1 = sum1 + (h1.get(i, 0) * h1.get(i, 0))
        sum2 = sum2 + (h2.get(i, 0) * h2.get(i, 0))
        # 计算两个图片次数乘积的和
        sum_mixd = sum_mixd + (h1.get(i, 0) * h2.get(i, 0))
    # 按照余弦相似性定理计算相似度
    return sum_mixd / (sqrt(sum1) * sqrt(sum2))

# 读取图片内容
img1 = cv2.imread(img1_path)
# 读取图片内容
img2 = cv2.imread(img2_path)
if compare_similar_hist(calc_bgr_hist(img1), calc_bgr_hist(img2)) < 0.9999:
    print("相似图片")

总结

总的来说：差异值哈希算法 + 颜色直方图解决了我的相似图片匹配问题。

参考资料

相似图片搜索的原理一
相似图片搜索的原理二

GPU云服务器云服务器字符串相似度匹配算法自相似算法哈希算法最小哈希算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/43565.html

利用python进行识别相似图片（一）

摘要：图像指纹与汉明距离在介绍下面其他判别相似度的方法前，先补充一些概念。汉明距离为，即代表两张图片完全一样。下一次将讲述利用和以训练好的模型来进行人脸识别。本文参考文章和图片来源的文章赖勇浩的文章下一篇地址利用进行识别相似图片二文章简介在网上看到python做图像识别的相关文章后，真心感觉python的功能实在太强大，因此将这些文章总结一下，建立一下自己的知识体系。当然了，图像识别这个...

HitenDev 2019-07-24 18:28 评论0 收藏0
文字检测识别系统好用吗？都针对什么进行识别？

摘要：神经网络以上验证码识别都依赖于字符切分，切分的好坏几乎直接决定识别的准确程度。目前验证码识别最先进的是谷歌在识别街景图像中门牌号码中使用的一套的算法。最近在一个爬虫项目中遇到了验证码，需要机器自动识别绕过。刚好与题主的问题类似，在这里做一些分享。在网上调研了资料和文献后，分别采用OCR识别和模板库匹配方法对不同类型验证码进行了识别。主要过程可以分解为三个步骤：1.图片清理，2.字符...

wanglu1209 2019-06-28 11:14 评论0 收藏0
如何识别图片验证码？

摘要：图片验证码是目前最常用的一种。神经网络以上验证码识别都依赖于字符切分，切分的好坏几乎直接决定识别的准确程度。目前验证码识别最先进的是谷歌在识别街景图像中门牌号码中使用的一套的算法。全自动区分计算机和人类的图灵测试（Completely Automated Public Turing test to tell Computers and Humans Apart，简称CAPTCHA），...

y1chuan 2019-06-28 11:12 评论0 收藏0
从零开始的无人驾驶 1

摘要：霍夫变化是图像变化中的经典算法，主要用来寻找图像中符合某种特征的集合，说白了就是检测直线圆椭圆。定向梯度直方图相比于之前的特征，特征更加健壮，并且无视颜色的影响。行为克隆算是的一种。 Lanes Finding with Computer Vision 利用计算机视觉进行道路检测，一般包括6部分：摄像头校正(camera calibration)、图像失真校正(distortion c...

marek 2019-06-26 18:47 评论0 收藏0
爬虫敏感图片的识别与过滤，了解一下？

摘要：爬虫敏感图片的识别与过滤，了解一下需求我们需要识别出敏感作者的头像把皮卡丘换成优雅的。对比哈希不同图片对比的方法，就是对比它们的位哈希中，有多少位不一样汉明距离。爬虫敏感图片的识别与过滤，了解一下？需求我们需要识别出敏感作者的avatar头像,把皮卡丘换成优雅的python。敏感图片样本属性: showImg(https://ws3.sinaimg.cn/large/006tN...

linkin 2019-07-31 11:17 评论0 收藏0