相似图片搜索原理

时间:2021-02-20 17:05:16

给定一张图片,怎样在互联网上找出和它近似的图片?

可以使用Google的相似图片搜索功能,匹配程度相当高。

那么,计算机是采用怎样的技术判定两张图片的相似程度的呢?方法有很多。

在这里,我们从图片的轮廓和色彩两方面入手,做一个简单的算法实现,重在原理呈现。


轮廓篇

  图片的轮廓是判断图片相似性的最主要影响因素,那么怎样确定图片的主要轮廓呢?实际上,若将图片转化为黑白图后再观察就容易的多,黑白交界处就是所谓轮廓。

如需得到黑白图,首先排除色相干扰,将RGB转化为灰度,生成灰度值矩阵。

但是灰度值中包含的噪音较多,因此最好再做一次离散余弦变换,并只保留其中的低频部分,这样可以提高不少精确度。经过变换后得到的依然是一个灰度值矩阵

那么哪些像素点转化为黑点,哪些转化为白点呢?我们需要确定一个阈值,比阈值大的转化为白点,比阈值小的转化为黑点。它必须保证阈值以上的灰度值分布要尽可能地紧密,阈值以下的灰度值分布也要尽可能地紧密,同时阈值以上值的总体分布和阈值以下值的总体分布两者之间要尽可能疏远,这样才能使轮廓精确。

这时,我们将DCT后的灰度值矩阵中的每个数字与阈值做比较大小,便得到了一个0-1特征矩阵。

用平均值做阈值其实是一种不精确的方法,有一种比较好的方法叫做Otsu’s method

再从特征矩阵转化到哈希码,这个就很简单了。

如果我们把待比较的图片压缩到相同的尺寸,同时保证组合生成哈希码的顺序相同,则得到的哈希码即为轮廓指纹,两者的海明距离越小则两张图片轮廓构成越相似


色彩篇

  色彩是图片的重要特征,我们可以把图片中不同颜色的像素点总数统计出来,作为相似搜索的判据。上述信息若转化为直方图就很直观。  

每种颜色都是由红绿蓝按照不同的比例混合而成的,一共有256^3种颜色,但是这个数据量太大。我们可以将256分成4段:0-6364-127128-191192-255,这样所有的颜色被归类到4^3=64种。准备一个大小为64map容器,64种颜色各自对应一个键,这样就可以统计了。最后,我们可以依次取出map中的值,按正比例转化到0-F的十六进制数,再串联起来就得到了64位哈希码。

如果把待比较的图片压缩到相同的尺寸,再使map中的键排列保持一致,则得到的哈希码即为色彩指纹,两者的海明距离越小则两张图片色彩构成越相似


    用Java实现后进行了比较简单的测试,发现这两个方法综合起来用,对缩放和一些“淡妆”滤镜的识别度比较好,因此可以胜任简单的原图-缩略图和原图-PS图互相查找。同时,误差也是存在的。我个人的观点,在压缩图片的那一部分,变形导致损失的信息较大,乃是误差的根源。

    经过旋转处理的原图和裁剪掉外围的原图,都被判定为和原图相差很大。这就暴露了鲁棒性上的不足。我认为在原理不变的前提下,此一类原图变形问题是可以通过修正原有算法在一定程度上解决的。

    而面对用google搜图得到的近似图(事实上肉眼也证实确实是近似图),这个算法就真的不够用了。我想要达到接近肉眼的识别能力,一个仅仅在信号数据层面进行处理的算法是不够的。