[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;
}