LAST UPDATE: August 18th 2018, 9:55:03 PM

电脑里近4000张用来做壁纸的图片好像有那么1%是重复的
机器学习也不会，只能用哈希混混日子这样子

顺手 diss 一下网上大多数千篇一律的文章

远离 pillow, 拥抱 opencv
缩图片要选好插值模式，随便查了一下选了双三次插值
pillow 巨慢，opencv 速度快
pillow 多慢？ 在 ahash 中用 pillow 比用 opencv 慢了 60 倍，过分了……

均值哈希 average_hash ahash

原理: 转为灰度图，压缩大小，算均值，逐像素比较得出哈希

• 敏感性较高，图片稍微变化对结果影响极大，原因是该哈希方法较为简单，极大程度上基于图像原本的像素信息
• 在压缩为 8x8 大小错误率较高
• 调整为 16x16 大小、Hamming Distance 为 3 的情况下得到预期结果
• 运行速度快，毕竟计算简单

#!/usr/bin/python

import pathlib

from functools import reduce
from itertools import chain

import cv2
# from PIL import Image

flatten = lambda lst: list(chain.from_iterable(lst))

pic_dir = pathlib.Path('./pic')
pic_hash = []
duplicate_pics = []
H, W = 16, 16

for pic in pic_dir.iterdir():
    if str(pic).endswith('db'):
        continue
    pic_ori = cv2.imread(str(pic), cv2.IMREAD_GRAYSCALE)
    pic_16x16 = flatten(cv2.resize(pic_ori, (H, W), interpolation=cv2.INTER_CUBIC).tolist())
    # pic_ori = Image.open(pic).convert('L')
    # pic_16x16 = pic_ori.resize((H, W), Image.BICUBIC).getdata()
    avg_gc = sum(pic_16x16) / H / W
    avg_hash = reduce(
        lambda res, item: (res << 1) | item,
        map(
            lambda gc: 0 if gc < avg_gc else 1,
            pic_16x16
        )
    )
    for _n, _h in pic_hash:
        if bin(avg_hash ^ _h).count('1') <= 3:
            duplicate_pics.append((pic.name, _n))
            break
    else:
        pic_hash.append((pic.name, avg_hash))


print(duplicate_pics)

运行时间

$ time python ahash.py
real  0m31.303s
user  0m30.422s
sys   0m1.036s

感知哈希 Perceptual_hashing phash

原理: 两次 DCT 把图像能量按照频度大致分开，能量高的低频信息聚集于左上角，取左上角做均值哈希

• 准确率与图片压缩时的尺寸以及最后取低频区大小呈正相关，毕竟保留越多的信息肯定更精确
• 根据网络上资料，压缩图片时 32x32 的尺寸便于做 DCT 运算，但经过尝试感觉这个尺寸下错误率较高，遂提高尺寸，在 64x64 的尺寸下体验较好
• 取低频区 16x16 体验极差，32x32 大小、Hamming Distance 为 2 时错误率低但不为零
• 大部分资料说 Hamming Distance 小于等于 5 可以认为非常相似，但尝试后感觉 5 太大了，越大错误率越高，但太小可能错过某些有细微差别的重复图片，有两张看上去相同的图 phash 居然有一个二进制位不同
• 速度较慢，但是敏感性低，不易受简单干扰影响

#!/usr/bin/python

import pathlib

from functools import reduce
from itertools import chain
from operator import add

import cv2

flatten = lambda lst: list(chain.from_iterable(lst))
cat_bit = lambda res, x: res << 1 | x
calc_bit = lambda avg, lst: [0 if x < avg else 1 for x in lst]
p_hash = lambda avg, lst: reduce(cat_bit, calc_bit(avg, lst))

pic_dir = pathlib.Path('pic')
pic_hash = []
duplicate_pics = []

for pic in pic_dir.iterdir():
    if str(pic).endswith('db'):
        continue
    pic_ori = cv2.imread(str(pic), cv2.IMREAD_GRAYSCALE)
    pic_64x64 = cv2.resize(pic_ori, (64, 64), interpolation=cv2.INTER_CUBIC).astype('float32')

    pic_dct = cv2.dct(cv2.dct(pic_64x64))
    pic_dct.resize(32, 32)
    pic_dct = flatten(pic_dct.tolist())

    avg_dct = sum(pic_dct) / len(pic_dct)

    pic_p_hash = p_hash(avg_dct, pic_dct)
    for _n, _h in pic_hash:
        if bin(pic_p_hash ^ _h).count('1') <= 2:
            duplicate_pics.append((pic.name, _n))
            break
    else:
        pic_hash.append((pic.name, pic_p_hash))

print(duplicate_pics)

运行时间

$ time python phash.py
real  1m0.046s
user  0m59.173s
sys   0m1.010s

差异值哈希 different_hash dhash

原理: resize 为 (N, N + 1) 的尺寸然后对每行做差异值运算，合并起来作为哈希。本质上是基于图像渐变

• 稳定性估计比 ahash 稍微强
• 速度与 ahash 不相上下
• (16， 17) 尺寸、Hamming Distanec 为 6 时得到预期结果

#!/usr/bin/python

import pathlib

from itertools import chain
from functools import reduce

import cv2

flatten = lambda lst: list(chain.from_iterable(lst))

pic_dir = pathlib.Path('pic')
pic_hash = []
duplicate_pics = []
H, W = 16, 17

for pic in pic_dir.iterdir():
    if str(pic).endswith('db'):
        continue
    pic_ori = cv2.imread(str(pic), cv2.IMREAD_GRAYSCALE)
    pic_16x17 = cv2.resize(pic_ori, (H, W), interpolation=cv2.INTER_CUBIC).tolist()
    pic_d_hash = reduce(
        lambda res, x: res << 1 | x,
        flatten(
            [1 if _x > _n else 0 for _x, _n in zip(lst, lst[1:])]
            for lst in pic_16x17
        )
    )
    for _n, _h in pic_hash:
        if bin(pic_d_hash ^ _h).count('1') <= 6:
            duplicate_pics.append((pic.name, _n))
            break
    else:
        pic_hash.append((pic.name, pic_d_hash))

print(duplicate_pics)

运行时间

$ time python dhash.py
real  0m40.084s
user  0m39.141s
sys   0m1.140s

Conclusion

综合来看 dhash 确实优势比较大，运算比 phash 快，稳定性比 ahash 高，就用这个了

====

完结撒花