百万量级的汉明距离的数据有没有什么快速计算接近的方法呢？

[phpfpm]

目前有近 100w 图片需要判重，挑了几个 hash 算法，正在跑 hamming code，都是 128bit 的 binary

这些图片都是经过 md5 与判重之后的图片了，所以需要找出来一些汉明距离接近的肉眼观察一下

所以要找到一些距离是 0,1,2,3 的图片组。

当然了，挨个计算一次(1M * 1M = 1T)

好像似乎，也不是很长时间吧，还勉强能接受，跑几天跑完了

有什么能再快一些的算法吗？

目前有一台机器(9400f+1660s)可以跑一点机器学习，勉强够看。

[douglas1997]

先算出图像指纹，在进行比对？我觉得算法慢是因为直接算一对一对图像的汉明距离，这个才是费时间的，而不是 1M*1M 。

比较简单直接的策略，可以考虑：

- 图像降采样
- 取 128Bit 的其中 8Bit/16Bit 作为比对的样本数据
- 生成图像指纹
- 多进程

[mcfog]

简单的削减一下数量级吧，比如按 bit1 的位数分组，只在邻接的 k 组之间比较。或者先按前 k 位分组在组内找，然后按后 k 位分组在组内找

[newdongyuwei]

图片的话 phash，dhash 比较靠谱吧

[momocraft]

排序後逐個比對可以嗎? (你的問題好像可以接受實際接近但漏掉的, 即 true negative)

[ipwx]

你需要的是，能够用向量空间的欧几里得距离表示图片相似度的某个模型。

因为欧几里得距离下，可以用 KD-tree 进行相似向量查找。整个数据集两两找一遍是 N log N 的。

[momocraft]

可能會漏掉非常多, 排序會導致實際只比較 LSB 附近的 bit

[ifzzzh]

locality-sensitive hashing 了解一下

[also24]

之前做过类似需求… 也是困扰在这个地方

[liukangxu]

看看 Google 是怎么做的： https://www2007.org/papers/paper215.pdf

[phpfpm]

@douglas1997 128bit 已经是图像指纹了，不是两个 1M 比指纹，是 1M 个 128bit 的 hash 比距离

[phpfpm]

@newdongyuwei 已经在跑 p,dhash 了

确实 dhash 好一些，还挑了几个别的算法。
全量跑一遍 1M*5 个 hash 算法得两三天(主要是资源在 nas 上 io 慢机器也不快）


@momocraft

排序肯定不行，排序相当于只有前缀分组，会漏掉特别多
@ipwx
对，有这玩意么
其实细想一下，汉明距离就是 n-dimission 的距离，不过 nlgn 的算法仅限于 2 维来着？

[phpfpm]

@ifzzzh
@liukangxu
我看下这俩算法，不过我估计学不会……

[also24]

想起来之前做的一个简单优化：
统计 phash 中 1 的个数，然后只搜索对比 1 的数量相近的内容。

假如我们需要汉明距离小于等于 6，那 1 的数量差也不应该大于 6 才对。

[liukangxu]

@phpfpm 看 Google 这篇论文就够了，和你的场景基本一致，解法也很简单

[phpfpm]

@all

算了 25k of 720k 的摘要 hash，用 dhash 就能找到约 0.5k 的 dup，相当于汉明距离=0

这个已经足够 make sense 了~

汉明距离 1+的以后慢慢算，可以结合几种不同的 hash 去重~

[phpfpm]

@also24 嗯 可以按照 1 的个数将分组缩小 128/dist 倍，计算量也减少这么多。
@liukangxu 感谢！

[ipwx]

@phpfpm emmm 其实 kd-tree 是 kN log N，k 是维度。所以 k 不大的情况下，也差不多是 N log N 了。但是它处理的是 特征向量，不是汉明码。汉明码是 0-1 binary 数据，反而不好处理。特征向量是实数向量，反而好处理一些。

产生图片特征向量，其实应该还是个 research topic 。我搞深度学习，但是不搞图片压缩，不太清楚那种算法比较成熟。你要让我想一下哪些方向有可能，然后进一步进入这个领域研究，我可能做得到。但现阶段给不了你意见。

[aec4d]

ficapy.com/2018/03/04/Postgresql_use_bktree_hamming/ 以前做过类似的，BK 树可以优化

[imn1]

如果只是百万级汉明不需要几天啊，我觉得#1 说得对，你是否每次都算一遍？
你应该缓存 hash 值的
然后建议分段，如果有分类别什么的，那将大大降低循环次数

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 ）的话，可以适当调高临界值，甚至只用一种算法也够了

还有一种模式匹配算法，不过只适合小图找大图（就是大图里面的一部分），或者有裁切的图找原图，不适合找相似的图，此处不详说了

[phpfpm]

@imn1 非常感谢这么详细的回答！

其实我还没开始计算百万级的汉明距离(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 的情况。

毛菇如果把历史数据都读取到内存当中算一趟的时间应该在可接受的范围内吧……

[phpfpm]

@imn1 我尝试了一下算 hash dup 的算力。
必要的缓存优化我做了，hash 全部读取到内存没有 io 问题。

计算 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 个小时。

[phpfpm]

@also24 又做了一个优化，比较 distance 之前算下 bit count 的差值，超过阈值就不算了。
这样又可以快一点点。

[imn1]

@phpfpm #21
有点没看明白
你的程序是 compare(pic1, pic2)，在里面 hash 然后比较，这样的么？
这样 compare(pic1, pic3)的话，pic1 不是又要重新 hash 一次？

应该转成两个步骤
hash1=img_hash(pic1)
hash2=img_hash(pic2)
hash3=img_hash(pic3)
……
然后入库
用数据库的值 compare(hash1, hash2)，这个不需要多次 hash 了

[phpfpm]

@imn1 处理的已经是针对 hash，而不是图片了。

踩了一个语言的坑，有一些代码写的还不够 dry，目前已经优化到计算
5*200*25k 个 distance 用 10s 了。

[lizytalk]

lsh 可以么？

[phpfpm]

@lizytalk lsh 是分段的，会降低敏感度，因为图片无法分段。

[imn1]

@phpfpm
呃，我想起 RadialVariance/ColorMoment 是用在什么场合较佳了
aHash/pHash/dHash 对于有较大水印的图判断不准，多数为 False，但这两个能判断出是相似的图(True)

[also24]

@phpfpm #22
对，我说的 1 的数量其实就是 bit count
不过大部分环境下都有对 bit count 方法做了优化的原生方法，刚才忘了说了……

上次搞这个事儿大概是 4 年前了，所以忘了好多细节 =。=

[imn1]

@phpfpm
还有一个是旋转的图也能判别，我忘了是哪个，不过网络图片这个问题不常见，摄影的才比较多

[phpfpm]

@also24 我直接硬数的，反正 n^2 的算法里面的 n 次 bit 计算怎么搞都不差太多……
但是优点确实是能省好多 distance
毛估，distance 计算数量减少百分之 90，但是多算了 n 次绝对值相减，里外里效率提升 50%这样

ext_gmp 的 distance 已经很省时间了

[phpfpm]

@imn1 世界上最好的语言对 OpenCV 的封装不好。。。
当然 php74 之后就有 ffp 了，拭目以待吧~

[phpfpm]

@imn1 更正一下，FFI

我的场景这个判重已经足够了，稍后算一下几个 hash 算法的 dist 的权重，做一个新的阈值。

[yuruizhe]

@phpfpm
有个不成熟的想法，设置一个“绝对距离”的概念
绝对距离=0{0000}
绝对距离=1{0001，0010，0100，1000}
绝对距离=2{0011，0101，0110，...}
...
1.反正每个组内的元素，两两汉明距离都为 2 或 4 或 6 或...
2.在两个临近组间找汉明距离为 1 的两个点
依次类推...
（脑袋一拍，没有验证，不要怼我）

[JCZ2MkKb5S8ZX9pq]

自己本機上處理過，hash 之後丟數據庫了，重複的加數組最後再摘出來。
然後 hash 前分精度，先 8x8 過掉一些，重複的部分再提高精度 hash 。
1Mx1M 這個應該是不必的。

[phpfpm]

@yuruizhe 没毛病，空间换时间。
你空间给小了和 1-count 预处理效果差不多
给大了……你给不起。。
128bit 不小的。。。

[vchar2ex]

https://github.com/idealo/imagededup 这里 phash, dhash 有现成的，可以测试一下看看效果如何

[phpfpm]

@vchar2ex 我已经找到实现了，我的问题不是如何算 hash，而是如何降低复杂度快速去找。

[NcAtN]

VideoComparerWin 这个是视频查重的..你看下原理 可以用来图片么 还是这个工具直接带图片查重 忘记了

[yuruizhe]

@phpfpm
不是真正的分配 2^128 那么多的空间，我的意思是分箱，把哈希码分组存在 subset 里，如果 element 在 subset_1 中，就去 subset_0 与 subset_2 里寻找与 element 的汉明距离为 1 的其他 element

[tzm41]

我想法感觉跟楼上几位相似。楼主的问题是要求 L1 nearest neighbors，数据是 128-dim binary 。近似加快的方法就是做一个 L2 embedding，感觉应该是 Johnson-Lindenstrauss 之类的。

[0o0o0o0]

向量搜索，记得有一个叫 hnsw 的算法。。。不知道可不可以。。。

[phpfpm]

@0o0o0o0
@tzm41
@yuruizhe
@also24

昨天想了一个思路，准备动手去做
还是空间换时间，而且要利用好“diff < n”这个条件去筛。

128bit diff <=3 那么把 128bit 分成四段，至少能有一段是完全一致的。

1M 个 分成 4M 段 每段按照哈希值存到一个桶里面，会有 2^32 个桶，每个桶基本不会有冲突。
之后每个 hash 找近邻的时候只需要找 4 段对应的 hash 取个并集，算一下这部分就好。

[phpfpm]

根据上面的帖子优化了一版
从 5*200*25k 个 distance 用 10s 了
到 5*200*200k 个 distance 用 15s

之后一个点的全量数据对比 (5*1M ）个 distance 在 20s 内能搞定，考虑用队列离线算~