nivance / Image Similarity
Programming Languages
Projects that are alternatives of or similar to Image Similarity
ImageSimilarity
计算图片相似度的应用很广泛，如google、baidu、360等搜索引擎以图搜图的功能就是其典型应用。下面介绍介绍两种算法：
感知哈希算法（Perceptual hash algorithm）
那这种技术的原理是什么呢？根据Neal Krawetz博士的解释，原理非常简单易懂。我们可以用一个快速算法，就达到基本的效果。这里的关键技术叫做感知哈希算法（Perceptual hash algorithm），它的作用是对每张图片生成一个"指纹"（fingerprint）字符串，然后比较不同图片的指纹。结果越接近，就说明图片越相似。下面是一个最简单的实现：
- 第一步，缩小尺寸。将图片缩小到8x8的尺寸，总共64个像素。这一步的作用是去除图片的细节，只保留结构、明暗等基本信息，摒弃不同尺寸、比例带来的图片差异。
- 第二步，简化色彩。将缩小后的图片，转为64级灰度。也就是说，所有像素点总共只有64种颜色。
- 第三步，计算平均值。计算所有64个像素的灰度平均值。
- 第四步，比较像素的灰度。将每个像素的灰度，与平均值进行比较。大于或等于平均值，记为1；小于平均值，记为0。
- 第五步，计算哈希值。将上一步的比较结果，组合在一起，就构成了一个64位的整数，这就是这张图片的指纹。组合的次序并不重要，只要保证所有图片都采用同样次序就行了。
得到指纹以后，就可以对比不同的图片，看看64位中有多少位是不一样的。在理论上，这等同于计算汉明距离（Hamming distance）。如果不相同的数据位不超过5，就说明两张图片很相似；如果大于10，就说明这是两张不同的图片。
具体的代码实现，可以参见Wote用python语言写的imgHash.py。代码很短，只有53行。使用的时候，第一个参数是基准图片，第二个参数是用来比较的其他图片所在的目录，返回结果是两张图片之间不相同的数据位数量（汉明距离）。
这种算法的优点是简单快速，不受图片大小缩放的影响，缺点是图片的内容不能变更。如果在图片上加几个文字，它就认不出来了。所以，它的最佳用途是根据缩略图，找出原图。
代码可参考本项目ImagePHash.java。
实际应用中，往往采用更强大的pHash算法和SIFT算法，它们能够识别图片的变形。只要变形程度不超过25%，它们就能匹配原图。这些算法虽然更复杂，但是原理与上面的简便算法是一样的，就是先将图片转化成Hash字符串，然后再进行比较。
直方图
直方图算法是对源图像与要筛选的图像进行直方图数据采集，对采集的各自图像直方图进行归一化再使用巴氏系数算法对直方图数据进行计算，最终得出图像相似度值，其值范围在[0, 1]之间0表示极其不同，1表示极其相似（相同）。
算法步骤大致可以分为两步，根据源图像与候选图像的像素数据，生成各自直方图数据。第二步：使用第一步输出的直方图结果，运用巴氏系数（Bhattacharyya coefficient）算法，计算出相似程度值。
-
第一步：直方图计算 直方图分为灰度直方图与RGB直方图，对于灰度图像直方图计算十分简单，只要初始化一个大小为256的直方图数组H，然后根据像素值完成频率分布统计，假设像素值为124，则H[124] += 1, 而对于彩色RGB像素来说直方图表达有两种方式，一种是单一直方图，另外一种是三维直方图，三维直方图比较简单明了，分别对应RGB三种颜色，定义三个直方图HR,HG, HB, 假设某一个像素点P的RGB值为(4, 231,129), 则对于的直方图计算为HR[4] += 1,HG[231] += 1, HB[129] += 1, 如此对每个像素点完成统计以后，RGB彩色直方图数据就生成了。 而RGB像素的单一直方图SH表示稍微复杂点，每个颜色的值范围为0 ~ 255之间的，假设可以分为一定范围等份，当8等份时，每个等份的值范围为32， 16等份时，每个等份值范围为16，当4等份时候，每个等份值的范围为64，假设RGB值为(14, 68, 221), 16等份之后，它对应直方图索引值(index)分别为: (0, 4, 13), 根据计算索引值公式:index = R + G16 + B1616 对应的直方图index = 0 + 416 + 13 * 16 * 16， SH[3392] += 1如此遍历所有RGB像素值，完成直方图数据计算。
-
第二步：巴氏系数计算，计算公式如下：
。其中p, p’分别代表源与候选的图像直方图数据，对每个相同i的数据点乘积开平方以后相加得出的结果即为图像相似度值（巴氏系数因子值），范围为0到1之间。
代码可参考本项目ImageHistogram.java。
本项目的两种算法因为都存在一定的误判，所以可以两种方法结合在一起使用，提高准确率。
参考资料：