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 高,就用这个了
====
完结撒花