用 Python 实现哈希算法检测重复图片

2018-11-25 本文已影响16人水之心

在 Python 中导入 hashlib 模块，调用函数就可以生成某一个字符串或者文件的哈希值。这个算法对于未被篡改的上传文件非常有效，如果输入数据有细微变化，加密哈希算法都会导致雪崩效应，从而造成新文件的哈希值完全不同于原始文件哈希值。

import hashlib

某些情况下，我们需要检测图片之间的相似性，进行我们需要的处理：删除同一张图片、标记盗版等。

如何判断是同一张图片呢？最简单的方法是使用加密哈希（例如 MD5, SHA-1）判断。但是局限性非常大。例如一个 txt 文档，其 MD5 值是根据这个 txt 的二进制数据计算的，如果是这个 txt 文档的完全复制版，那他们的 MD5 值是完全相同的。但是，一旦改变副本的内容，哪怕只是副本的缩进格式，其 MD5 也会天差地别。比如，下面的两个字符串只是一个 . 符号的差别，MD5 却变化很大：

txt = b'The quick brown fox jumps over the lazy dog'

print(txt, hashlib.md5(txt).hexdigest())
print(txt+b'.', hashlib.md5(txt+b'.').hexdigest())

b'The quick brown fox jumps over the lazy dog' 9e107d9d372bb6826bd81d3542a419d6
b'The quick brown fox jumps over the lazy dog.' e4d909c290d0fb1ca068ffaddf22cbd0

因此加密哈希只能用于判断两个完全一致、未经修改的文件，如果是一张经过调色或者缩放的图片，根本无法判断其与另一张图片是否为同一张图片。
那么如何判断一张被PS过的图片是否与另一张图片本质上相同呢？比较简单、易用的解决方案是采用感知哈希算法（Perceptual Hash Algorithm)。

感知哈希算法是一类算法的总称，包括 aHash、pHash、dHash。顾名思义，感知哈希不是以严格的方式计算 Hash 值，而是以更加相对的方式计算哈希值，因为“相似”与否，就是一种相对的判定。^[1]

aHash：平均值哈希。速度比较快，但是常常不太精确。
pHash：余弦感知哈希。精确度比较高，但是速度方面较差一些。
dHash：差异值哈希。Amazing！精确度较高，且速度也非常快。

我们先看看一张图片：

import cv2
from IPython.display import Image
from matplotlib import pyplot as plt
%matplotlib inline

img_name = 'E:/Data/URLimg/猫/喜马拉雅猫/27.jpg'
Image(img_name)

output_6_0.jpeg

下面我们主要研究以图搜图，它最核心的东西就是怎么让电脑识别图片。为了了解以图搜图，我们先看看哈希感知算法基本原理：

把图片转成一个可识别的字符串，这个字符串也叫哈希值
和其他图片匹配字符串，通过哈希值计算两张图片的汉明距离（Hamming Distance），通过汉明距离的大小，判断两张图片的相似程度。

ahash

均值哈希算法，

模糊化处理：使用 Opencv3 直接以 Gray 格式读取图片，然后将其缩小至 $8 \times 8$ 大小以减少计算量。
计算均值得到这个平均值之后，再和每个像素对比。像素值大于平均值的标记成 $1$ ，小于或等于平均值的标记成 $0$ 。组成 $64$ 个数字的字符串(看起来也是一串二进制的)。

def aHash(image_path, hash_size=8):
    '''
    get image ahash string
    '''
    img = plt.imread(image_path) # 转换为灰度图
    gray_img = cv2.cvtColor(img, cv2.COLOR_RGB2GRAY)
    resize_img = cv2.resize(gray_img, (hash_size, hash_size))
    # avg 和每个像素比较
    img_ = resize_img > resize_img.mean()
    # 二值化
    img_bi = ''.join(img_.astype('B').flatten().astype('U').tolist())
    #切割，每4个字符一组，转成16进制字符
    return ''.join(map(lambda x:'%x' % int(img_bi[x:x+4],2), range(0,64,4)))

print('图片的 aHash:', aHash(img_name))

图片的 aHash: bdc1c041767e7ca8

dHash

缩放图片

如果我们要计算上图的 dHash 值，第一步是把它缩放到足够小。为什么需要缩放呢？因为原图的分辨率一般都非常高。一张 $200 \times 200$ 的图片，就有整整 $4$ 万个像素点，每一个像素点都保存着一个 RGB 值， $4$ 万个 RGB，是相当庞大的信息量，非常多的细节需要处理。因此，我们需要把图片缩放到非常小，隐藏它的细节部分，只见森林，不见树木。建议缩放为 $8\times 9$ ，虽然可以缩放为任意大小，但是这个值是相对合理的。而且宽度为 $9$ ，有利于我们转换为 hash 值，往下面看，你就明白了。

img = plt.imread(img_name) # 转换为灰度图
hash_size = 8
gray_img = cv2.cvtColor(img, cv2.COLOR_RGB2GRAY)
resize_img = cv2.resize(gray_img, (hash_size+1, hash_size))

# 缩放为 8 * 9 分辨率后
plt.imshow(resize_img)
plt.show()

output_11_0.png

具体的流程和 aHash 差不多，只需要将均值改为水平梯度计算即可。该算法计算相邻像素之间的亮度差异并确定相对梯度。感知哈希算法从文件内容的各种特征中获得一个能够灵活分辨不同文件微小区别的多媒体文件指纹。

def dhash(image_path, hash_size=8):
    '''
    get image dhash string
    '''
    img = plt.imread(image_path)  # 转换为灰度图
    gray_img = cv2.cvtColor(img, cv2.COLOR_RGB2GRAY)
    resize_img = cv2.resize(gray_img, (hash_size+1, hash_size))
    # 计算水平梯度
    differences = []
    for t in range(resize_img.shape[1]-1):
        differences.append(resize_img[:, t] > resize_img[:, t+1])
    img_ = np.stack(differences).T
    # 二值化
    img_bi = ''.join(img_.astype('B').flatten().astype('U').tolist())
    # 切割，每4个字符一组，转成16进制字符
    return ''.join(map(lambda x: '%x' % int(img_bi[x:x+4], 2), range(0, 64, 4)))

为了方便，我将其封装为一个类：

class XHash:
    '''
    感知 Hash 算法
    '''
    def __init__(self, image_path, hash_type):
        self.image_path = image_path
        self.hash_size = 8
        self.type = hash_type
        if self.type == 'aHash':
            self.hash = self.__aHash()
        elif self.type == 'dHash':
            self.hash = self.__dHash()
        
    def __get_gray(self, img):
        '''
        读取 RGB 图片 并转换为灰度图
        '''
        # 由于 cv2.imread 无法识别中文路径，所以使用 plt.imread
        return cv2.cvtColor(img, cv2.COLOR_RGB2GRAY) # 转换为灰度图
    
    def __difference(self):
        '''
        比较左右像素的差异
        '''
        img = plt.imread(self.image_path)
        resize_img = cv2.resize(img, (self.hash_size+1, self.hash_size))
        gray = self.__get_gray(resize_img)
        differences = []
        for t in range(resize_img.shape[1]-1):
            differences.append(gray[:, t] > gray[:, t+1])
        return np.stack(differences).T
    
    def __average(self):
        '''
        与像素均值进行比较
        '''
        img = plt.imread(self.image_path)
        resize_img = cv2.resize(img, (self.hash_size, self.hash_size))
        gray = self.__get_gray(resize_img)
        return gray > gray.mean()
    
    def __binarization(self, hash_image):
        '''
        二值化
        '''
        return ''.join(hash_image.astype('B').flatten().astype('U').tolist())
    
    def __seg(self, hash_image):
        img_bi = self.__binarization(hash_image)
        return ''.join(map(lambda x: '%x' % int(img_bi[x:x+4], 2), range(0, 64, 4)))
    
    def __aHash(self):
        return self.__seg(self.__average())
    
    def __dHash(self):
        return self.__seg(self.__difference())



class XHash_Haming:
    '''
    计算两张图片的相似度
    '''
    def __init__(self, image_path1, image_path2, hash_type):
        self.hash_img1 = XHash(image_path1, hash_type).hash
        self.hash_img2 = XHash(image_path2, hash_type).hash
    def hash_haming(self):
        '''
        计算两张通过哈希感知算法编码的图片的汉明距离
        '''
        return np.array([self.hash_img1[x] != self.hash_img2[x] for x in range(16)], dtype='B').sum()

import os

dir_name = 'E:/Data/URLimg/猫/test/'

print(os.listdir(dir_name))

['16 - 副本.jpg', '6 - 副本.jpg', '6.jpg', '8 - 副本 - 副本.jpg', '8 - 副本.jpg']

import sys
sys.path.append('E:/zlab')
from dhash import XHash, XHash_Haming

我们这里有两个副本，我们看看它们的 dHash：

class Pairs:
    '''
    使用 dHash 实现哈希感知算法
    '''

    def __init__(self, root):
        if root == None:
            root = os.getcwd()
        self.names = {
            j: os.path.join(root, name)
            for j, name in enumerate(os.listdir(root))
        }
        self.__hashs = np.array([
            XHash(self.names[name], 'dHash').hash
            for name in self.names.keys()
        ])
        self.__cal_haming_distance(self.__hashs)

    def __cal_haming_distance(self, hashs):
        '''
        计算两两之间的距离
        '''
        j = 0
        pairs = {}
        while j < hashs.shape[0]:
            for i in range(j + 1, hashs.shape[0]):  # 图片对，过滤到已经计算过的 pairs
                pairs[j] = pairs.get(j, []) + \
                    [np.array(hashs[i] != hashs[j]).sum()]
                continue
            j += 1
        self.pairs = pairs

    def get_names(self):
        n = len(self.pairs)
        temp = {}
        while n > 0:
            n -= 1
            for i, d in enumerate(self.pairs[n]):
                if d == 0:
                    temp[n] = temp.get(n, []) + [i + n + 1]
                    continue
        return temp

    def del_repeat(self):
        P = self.get_names()
        for j in P:
            for i in P[j]:
                try:
                    os.remove(self.names[i])
                except FileNotFoundError:
                    print('已经移除，无需再次移除！')
        print('删除完成！')```


```python
pairs = Pairs(dir_name)

pairs.pairs

{0: [15, 15, 13, 13], 1: [0, 16, 16], 2: [16, 16], 3: [0]}

我们可以通过汉明距离判定：0 与 1、3 与 4 号图片分别是同一张图片，仅仅保留一张，删除重复图片：

os.listdir(dir_name)

['16 - 副本.jpg', '6 - 副本.jpg', '6.jpg', '8 - 副本 - 副本.jpg', '8 - 副本.jpg']

pairs.del_repeat()
os.listdir(dir_name)

['16 - 副本.jpg', '6 - 副本.jpg', '8 - 副本 - 副本.jpg']

自动把重复的图片删除了！

pairs.names

{0: 'E:/Data/URLimg/猫/test/16 - 副本.jpg',
 1: 'E:/Data/URLimg/猫/test/6 - 副本.jpg',
 3: 'E:/Data/URLimg/猫/test/8 - 副本 - 副本.jpg'}

该代码被我放在 GitHub，在不断的改进中。

Erum: https://www.jianshu.com/p/193f0089b7a2 ↩

用 Python 实现哈希算法检测重复图片

ahash

dHash

缩放图片

猜你喜欢

热点阅读