目前有近 100w 图片需要判重，挑了几个 hash 算法，正在跑 hamming code，都是 128bit 的 binary
这些图片都是经过 md5 与判重之后的图片了，所以需要找出来一些汉明距离接近的肉眼观察一下
所以要找到一些距离是 0,1,2,3 的图片组。
当然了，挨个计算一次(1M * 1M = 1T)
好像似乎，也不是很长时间吧，还勉强能接受，跑几天跑完了
有什么能再快一些的算法吗？
目前有一台机器(9400f+1660s)可以跑一点机器学习，勉强够看。
比较简单直接的策略，可以考虑：
– 图像降采样
– 取 128Bit 的其中 8Bit/16Bit 作为比对的样本数据
– 生成图像指纹
– 多进程
因为欧几里得距离下，可以用 KD-tree 进行相似向量查找。整个数据集两两找一遍是 N log N 的。
确实 dhash 好一些，还挑了几个别的算法。
全量跑一遍 1M*5 个 hash 算法得两三天(主要是资源在 nas 上 io 慢机器也不快）
@momocraft
排序肯定不行，排序相当于只有前缀分组，会漏掉特别多
@ipwx
对，有这玩意么
其实细想一下，汉明距离就是 n-dimission 的距离，不过 nlgn 的算法仅限于 2 维来着？
假如我们需要汉明距离小于等于 6，那 1 的数量差也不应该大于 6 才对。
算了 25k of 720k 的摘要 hash，用 dhash 就能找到约 0.5k 的 dup，相当于汉明距离=0
这个已经足够 make sense 了~
汉明距离 1+的以后慢慢算，可以结合几种不同的 hash 去重~
产生图片特征向量，其实应该还是个 research topic 。我搞深度学习，但是不搞图片压缩，不太清楚那种算法比较成熟。你要让我想一下哪些方向有可能，然后进一步进入这个领域研究，我可能做得到。但现阶段给不了你意见。
windows 有个软件 Similar Images，32bit，可以缓存 hash，作者应该弃坑了，好几年没更新，百万级也就小时级别（不过一次跑百万可能会崩，只能分段）
我自己写的 python 也不用那么久，只是估计，没试过百万，不过我是 hash 和匹配分开（整理时顺便 hash 入库，目前约 50M 张），然后匹配是家常便饭，经常跑小量（千张到万张）匹配，主要是入库时做去重，已经整理入库的就不需要互相比较了
说说算法，常见的 hash 有这几种
cv2.img_hash_PHash
cv2.img_hash_AverageHash
cv2.img_hash_RadialVarianceHash
cv2.img_hash_MarrHildrethHash
cv2.img_hash_ColorMomentHash
cv2.img_hash_BlockMeanHash
cv2 就是 opencv，BlockMean 最快，但极其不准，基本弃了，RadialVariance/ColorMoment 较慢，但还是有点用，ahash/phash 速度适中，MarrHildrethHash 我很少用，主要是搞不清它什么场合更佳
我个人的经验是，aHahs/pHash 中其中一个匹配（ OR ），ColorMomentHash/RadialVarianceHash 中其中一个匹配（ OR ），这两组 AND 的话，基本就确定重复了 —— 指没有漏判，然后找出的结果中只有很少是错判，错判不到千分之一（分母是全体，包含不重复的）
不过临界值还是要自己调，aHash/pHash/ColorMomentHash 我都是用 3，RadialVarianceHash 我用 0.95 ，全部都比网上代码样例的建议值宽松很多，单独一个算法用这个临界值的话误判会更大，但我组合起来用误判就很小了，这样比单独一个 hash 使用更严格临界值结果还好 —— 原理是图片质量不高的话，应该宽松些，这样不会漏掉，但很多误判，然后用组合降低误判。如果图片质量很高，例如全部都是没有 PS 的摄影作品（ raw 或近似 raw ）的话，可以适当调高临界值，甚至只用一种算法也够了
还有一种模式匹配算法，不过只适合小图找大图（就是大图里面的一部分），或者有裁切的图找原图，不适合找相似的图，此处不详说了
其实我还没开始计算百万级的汉明距离(o(n^2))，因为汉明码还没有预处理完——数据在 nas 上得先下载下来再算。
好吧，刚才打点看了一下，不是 io 的问题，就是 hash 算的慢（算 hash 呢，还没比呢）
服务器是一台 thinkpad 的，i5 4200u(1.6G~2.6G)
单线程跑满 hash 一个 100k 的图片大概需要 200ms （单线程），其他开销<5ms(数据库，网络，本地临时文件写）
算法（采用了 ah,dh, PercepiahHash，另外一个包的 ph 和 dh ），都是 php 的，算了 5 个 hash 。
我不太清楚其他语言算这个是不是能快一些，反正服务器也比较渣，之后跑判重肯定换个环境了，只是数据都在一个工程比较好管理。
等 hash 跑完我先用 dist=0 （完全匹配，基于数据库算下增量数据）简单提供一个服务，之后再慢慢跑 dist=1,2,3 的情况。
毛菇如果把历史数据都读取到内存当中算一趟的时间应该在可接受的范围内吧……
计算 5(个算法）*200 个 src*10k 个目标的汉明距离大概需要 1 分钟
i5 [email protected] 睿频到 2.2 的单核
如果目标上升到 1M(100 倍），5*200 这组需要的时间将会上升到 100 分钟
当然换一个好点的 cpu 提升 10 倍也就顶天了，10 分钟算 200 个（因为前面的 target 少）
1M=200*5000, 算均值是 5 分钟一批，需要 25000 分钟，大概 400 个小时。
应该转成两个步骤
hash1=img_hash(pic1)
hash2=img_hash(pic2)
hash3=img_hash(pic3)
……
然后入库
用数据库的值 compare(hash1, hash2)，这个不需要多次 hash 了
踩了一个语言的坑，有一些代码写的还不够 dry，目前已经优化到计算
5*200*25k 个 distance 用 10s 了。
上次搞这个事儿大概是 4 年前了，所以忘了好多细节 =。=
ext_gmp 的 distance 已经很省时间了
我的场景这个判重已经足够了，稍后算一下几个 hash 算法的 dist 的权重，做一个新的阈值。
昨天想了一个思路，准备动手去做
还是空间换时间，而且要利用好“diff < n”这个条件去筛。
128bit diff <=3 那么把 128bit 分成四段，至少能有一段是完全一致的。
1M 个 分成 4M 段 每段按照哈希值存到一个桶里面，会有 2^32 个桶，每个桶基本不会有冲突。
之后每个 hash 找近邻的时候只需要找 4 段对应的 hash 取个并集，算一下这部分就好。
之后一个点的全量数据对比 (5*1M ）个 distance 在 20s 内能搞定，考虑用队列离线算~