[TOC]
上传图片的时候总有一些傻逼上传重复的,浪费空间啊。
所以加了一个MD5检测重复,但是md5哈希只要文件变了一点点就完全不同。
所以本狗就在思考一种基于内容检测的识别,能够对应缩略图,小水印,改色这样的重复检测。
首先要解决的是图像特征的提取,图像特征的维度网上方法太多了,等下再说。
我们把图像特征映射到一串hash值上,就要求对于图片key的轻微变化,反应在value上也只有对应的轻微变化。
这里我们可以使用局部敏感哈希(Local Sensitive Hashing-LSH)+ 聚类算法来实现。
不过考虑到复杂程度,可以选择一种更加简单的方法,Detecting duplicate images using Python
使用dHash+汉明距离,文中给出了一种MYSQL的搜索方法。
SELECT pk, hash, BIT_COUNT(
CONV(hash, 16, 10) ^ CONV('4c8e3366c275650f', 16, 10)
) as hamming_distance
FROM image_hashes
HAVING hamming_distance < 4
ORDER BY hamming_distance ASC;
不过实际中却发现在进行进制转换的时候搜索结果总是有问题,MYSQL的BIT_COUNT只支持十进制,
所以在入库的时候保存为十进制,最后问题得到圆满解决,十六位的十六进制保存的最大值正好是bigint的无符号型的最大值。
simhash方案
除了上面的连接介绍的方法外,还有一种优化过的算法phash。 这儿的hash算法都是单就图片单个特征计算出的。而事实上我们还能对图片的多个特征进行计算,比如将图片里的内容识别出来,拆分成人脸,物体,然后给每个特征向量进行加权,然后合并降维处理,形成新的hash。
抽屉原理
当把许多simhash的64位二进制特征值保存到数据库的时候,可以使用上面的sql来查询相似度,但是当数量继续增长的时候,这种方法效率就不行了。 那么现在来定义一下什么才是足够相似,比如bitcount小于等于3的时候为相似,那么根据抽屉原理,最少分成四段来存放hash才能保证至少有一段hash是可以完全一致的。 我们现在把hash分成四段,每段16位。那么我们就不必全部扫描比对,只需要依次查询四段hash,直到找到其中一段完全相同为止。然后再取出相同的依次比对,找出满足条件的图片。 参考:https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/06.03.md
bit_count
在两两比对抑或运算后,需要使用bit_count进行统计1的个数。这儿有几种方法。这三个效率最好的是getBitCount。来源:
How to fastest count the number of set bits in php?
function countSetBits($int) {
return substr_count(decbin($int), '1');
}
function getBitCount($value) {
$count = 0;
while($value)
{
$count += ($value & 1);
$value = $value >> 1;
}
return $count;
}
function NumberOfSetBits($v) {
$c = $v - (($v >> 1) & 0x55555555);
$c = (($c >> 2) & 0x33333333) + ($c & 0x33333333);
$c = (($c >> 4) + $c) & 0x0F0F0F0F;
$c = (($c >> 8) + $c) & 0x00FF00FF;
$c = (($c >> 16) + $c) & 0x0000FFFF;
return $c;
}