哈希(Hash) 算法是将任意长度的输入，变换为固定长度的输出，是一种压缩映射，即，变换后的空间是通常是远小于原始输入的空间的.

哈希算法的映射是非唯一的，也就是说，不同的输入可能会映射为相同的输出，根据输出不能唯一的确定输入.

哈希算法可以简单的理解为，一种将任意长度的输入，压缩到某一固定长度的输出的变换函数. 如：

$$ h = Hash(I) $$

哈希是一种加密算法，是一种单向加密的，即，只有加密过程，没有解密过程，具有明文到密文的不可逆映射性.

在相似性图片搜索的中，常用的哈希算法有以下几种：

[1] - 均值哈希算法(Average Hashing, aHash)

[2] - 差异值哈希算法(Difference Hashing, dHash)

[3] - 感知哈希算法(Perception Hashing, pHash)

[4] - 小波哈希算法(Wavelet Hashing, wHash)

OpenCV 库中也给出了一部分哈希算法的实现：

The module brings implementations of different image hashing algorithms.

这里仅简单对 aHash 和 pHash 进行说明.

1. aHash

一张图片是一个二维信号的，其包含了不同频率的成分，如图：

低频成分 - 亮度变化小的区域，描述了大范围的信息.

高频成分 - 亮度变化剧烈的区域，如边缘信息，描述了细节信息.

大图片具有很高的频率；而小图片缺乏图片的细节信息，具有低频信息. 例如，图片的下采样操作，是缩小图片的过程，其实际上是损失高频信息的过程.

图片的 aHash 的计算过程如下：

[1] - 缩放

将图片缩放到指定大小，如8x8，保留图片的结构信息，过滤细节信息.

[2] - 灰度化

将缩放后的图片转换为 256 阶的灰度图.

[3] - 均值计算

计算灰度图所有像素的平均值.

[4] - 比较像素值与平均值

像素值大于平均值的记为1，像素值小于平均值的记为0. 长度为如 8x8=64位.

[5] - 生成 Hash.

将得到 1 和 0 ，根据顺序组合，即可得到图片的 Hash 值. (顺序不固定，但在作图片相似性比较时，二者的生成顺序要保持一致.)

Python实现如下：

from PIL import Image
import numpy as np

def binary_array_to_hex(arr):
    bit_string = ''.join(str(b) for b in 1 * arr.flatten())
    width = int(numpy.ceil(len(bit_string)/4))
    return '{:0>{width}x}'.format(int(bit_string, 2), width=width)

def average_hash(img_pil, hash_size=8):
    if hash_size < 2:
        raise ValueError("Hash size must be greater than or equal to 2")

    #[1]-[2]
    image = img_pil.convert("L").resize((hash_size, hash_size), Image.ANTIALIAS)

    #[3]
    pixels = np.asarray(image)
    avg = pixels.mean()

    #[4]-[5]
    diff = pixels > avg
    
    return binary_array_to_hex(diff)

或：

import cv2
import numpy as np

def binary_array_to_hex(arr):
    bit_string = ''.join(str(b) for b in 1 * arr.flatten())
    width = int(numpy.ceil(len(bit_string)/4))
    return '{:0>{width}x}'.format(int(bit_string, 2), width=width)

def aHash(img_cv2, hash_size=8):
    #[1]
    img=cv2.resize(img_cv2,(hash_size,hash_size),interpolation=cv2.INTER_CUBIC)
    #[2]
    gray=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
    
    #[3]
    avg = np.average(gray)

    #img_list = gray.reshape(hash_size*hash_size, ).tolist()
    #diff = ['0' if i < avg else '1' for i in img_list]
    #[4]-[5]
    diff = gray > avg
    
    return binary_array_to_hex(diff)

在进行图片相似性对比时，可以计算哈希值之间的汉明距离(Hamming distance)，两个 64 位的Hash值位数相同的数量，相同的位数越多，则图片越相似. 通过设定阈值，如，汉明距离小于5表示相似；汉明距离大于5 表示不相似.

2. pHash

aHash 具有简单、速度较快的优点，但易受均值的影响，精度较低.

pHash 是一种更鲁棒的哈希算法，其使用离散余弦变换(DCT) 获取图片的低频成分.

DCT 是一种图片压缩算法，将图片从像素域变换到频率域(频域). 一般情况下，图片存在很多冗余和相关性的，所以在转换到频率域后，只有很少的一部分频率分量的系数才不为0，大部分系数都为0(接近于0).

图片的 pHash 的计算过程如下：

[1] - 缩放

将图片缩放到指定大小.

[2] - 灰度化

将缩放后的图片转换为 256 阶的灰度图.

[3] - DCT计算

计算图片的 DCT 变换，得到 DCT 系数矩阵，如32x32 大小的矩阵.

[4] - 缩小 DCT 尺寸

只选取DCT矩阵左上角的部分矩阵，如 8x8 矩阵，其描述了图片中的低频成分.

[5] - 均值计算

计算 DCT 矩阵的平均值.

[6] - 比较像素值与平均值

像素值大于平均值的记为1，像素值小于平均值的记为0. 长度为如 8x8=64位.

[7] - 生成 Hash.

将得到 1 和 0 ，根据顺序组合，即可得到图片的 Hash 值. (顺序不固定，但在作图片相似性比较时，二者的生成顺序要保持一致.)

Python 实现如下：

from PIL import Image
import numpy as np
import scipy.fftpack
    
def phash(img_pil, hash_size=8, highfreq_factor=4):
    if hash_size < 2:
        raise ValueError("Hash size must be greater than or equal to 2")

    img_size = hash_size * highfreq_factor
    image = img_pil.convert("L").resize((img_size, img_size), Image.ANTIALIAS)
    pixels = numpy.asarray(image)
    dct = scipy.fftpack.dct(scipy.fftpack.dct(pixels, axis=0), axis=1)
    dctlowfreq = dct[:hash_size, :hash_size]
    med = np.median(dctlowfreq)
    diff = dctlowfreq > med
    
    return binary_array_to_hex(diff)


def phash_simple(img_pil, hash_size=8, highfreq_factor=4):
    img_size = hash_size * highfreq_factor
    image = img_pil.convert("L").resize((img_size, img_size), Image.ANTIALIAS)
    pixels = np.asarray(image)
    dct = scipy.fftpack.dct(pixels)
    dctlowfreq = dct[:hash_size, 1:hash_size+1]
    avg = dctlowfreq.mean()
    diff = dctlowfreq > avg
    
    return binary_array_to_hex(diff)

3. 参考文档

[1] - 据说，80%的人都搞不懂哈希算法

[2] - OpenCV - The module brings implementations of different image hashing algorithms

[3] - 图像检索：图像拷贝检索PHash改进方案

[4] - 图像相似性算法-感知哈希算法

[5] - Github - JohannesBuchner/imagehash

[6] - 较大规模图片 使用phash去重

[7] - 哈希算法实现图像相似度比较(Python&OpenCV)

[8] - pHash算法python+opencv实现

[9] - 感知哈希算法

[10] - PhotoBatch-图片去重(3)

[11] - 相似性︱python+opencv实现pHash算法+hamming距离（simhash）（三）

[12] - 图片去重 Image Deduplicator (imagededup)

Last modification：February 20th, 2021 at 03:00 pm
© 允许规范转载