向AI转型的程序员都关注了这个号👇👇👇
机器学习AI算法工程 公众号:datayx
本文主要调研了一下海量图片(>1000000张)去重的方法,在调研之前,先考虑一下自己能想到的方法的可行性。
文献发表:《基于pHash分块局部探测的海量图像查重算法》https://kns.cnki.net/KCMS/detail/detail.aspx?dbcode=CJFD&filename=JSJY201909051
在调研之前,思考一下能想到的比较简单的方法。当然下面的方法都是在拿到图片特征之后做的。
这种方法原始,简单,粗暴。基本思想就是挑选一个图片pair,按照某种方法计算相似度(可以是图片特征之间的相似度,可以是由网络计算的相似度),相似度低于某个阈值,则认为它们是重复的,然后从数据库中移除其中一张图片即可。这种方法虽然简单,但实际上并不可行,因为数据量太大,时间复杂度为O(n^2)。
生成图片的pHash,并计算pair之间pHash的Hamming distance。当然这种方法复杂度也是非常高的O(n^2)。
生成图片的特征向量并聚类,簇的数量需要设定的非常多(>10000)。每一个簇内计算图片对的距离,然后移除掉距离足够小的图片之一。但是这种方法复杂度也是挺高的,改进策略是进行多阶段聚类。首先设定第一次聚类的簇数为一个比较小的数(<100),然后聚类。然后对每一个簇再分别聚类,对第i个簇c_i,设定子簇数为|c_i| / b。
该算法的主要步骤是这样
这种方法需要做一些test查看每个list的规模,如果规模足够小,那么遍历一个pair的图片复杂度也不高,甚至于对于一些没有重复的图片,一个list只有单独的一张图片。不过条件是pHash的效果要比较好才行。即相似的图片pHash之间具有较小的Hamming distance。
目前的代码实现了该算法
参考:https://www.jianshu.com/p/c87f6f69d51f
这种方法也是减小可能相似的pair的搜索空间。原始的方法思想:
原始的方法有些不合理的条件,对距离的要求太过苛刻。一种改进是:
关键问题是:bucket与bucket之间尽管不相交,但bucket掌握的范围边界可能仍然存在相似甚至相同的样本对。这部分样本是无法探测到的。
Bucket如何建立?比较简单的方法是计算x到其他样本的最大距离,按照最大距离将距离区间划分成若干等分。
参考:https://www.xzbu.com/8/view-7438065.htm
局部敏感Hash算法希望原始特征空间中保持相邻的数据在经过某种Hash方法后依然有较高概率能保持相邻。
这里我们以基于minHash的局部敏感Hash算法为例。
首先讲解一下minHash算法的步骤:
对于signature,我们可以知道有这样一个性质,越是相似的样本,相同的h_i值就越多,因为h_i是整数。
基于minHash的LSH方法步骤:
2.根据pHash值探测重复图片
2.1.不具传递性的重复图片探测. 假设sim(a, b) < threshold,sim(b, c) < threshold,那么a和b,b和c都被认为是重复的。如果sim(a, c)>threshold,则a,c被认为是不重复的.
2.2.具有传递性的重复图片探测. 假设sim(a, b) < threshold,sim(b, c) < threshold,那么a和b,b和c都被认为是重复的。且a,c也被认为是重复的.
输出是一个json文件,通过d = json.load(open(output_path))读取。d是一个list,其中每一项也是一个list,存放着相同图片的全路径。
给定一张图片的路径或者是图片文件夹路径,查询在图片库中是否有与之重复的图片。
1.生成图片的phash分块索引库。
原文地址 https://github.com/xuehuachunsheng/DupImageDetection
机器学习算法AI大数据技术