关于识别相似图像的算法探讨

作者：caocao（网络隐士），http://www.caocao.name，http://www.caocao.mobi
转载请注明来源：http://www.iteye.com/topic/149776

有的网站允许用户上传照片、海报之类的图片，作为开发人员不可避免就会遇到这样的状况，就是用户上传上来的图片很大一部分是重复的或者相似的。为此隐士想就此探讨一下实现识别相似图像的算法。

如果有这样的算法，它应该具备哪些特性呢？隐士以为主要的特性有：
1、可以辨别完全一样的图像。
2、可以辨认镜像、旋转、平移、缩放、比例失真、加边的图像。
3、可以辨认图像内部部分区域。
4、可以辨认偏色、过曝、欠曝、模糊、噪点。
5、可以辨认水印。
6、可以辨认被轻微PS的图像。
7、误认率必须相当低。
8、辨认图像的时候不扫描其他图像，仅仅根据对其他图像提取的特征数据就能够辨认出来。

看来是要求颇多哦，闲话不多说，请看下面的图，假设存在这样的算法，隐士希望只要输入一个浮点数作为最小相似度M，所有与输入图像相似度大于等于M的都会被列出来。图中01.jpg是输入图像，其余都是和输入图像相似的图像，其顺序按相似度倒序排列。


貌似效果还不错，基本实现了需求，下面隐士谈谈思路。由需求可知第一步是提取图像的特征数据：
1、整个文件的Hash码，用来辨认完全一样的图像。
2、旋转角度不敏感数据，这是用来抗旋转、镜像的。
3、宽高比例不敏感数据，这是用来抗缩放、比例失真的。
4、偏色不敏感数据，这是用来抗偏色、过曝、欠曝的。
5、整体轮廓数据，这是用来抗加边、模糊、噪点、水印、轻微PS的。

通过索引这些特征数据来进行复杂运算后得到一个综合的相似度即可实现不扫描其余图像而快速识别图像。由于算法还不是很成熟，希望对此感兴趣的看官和隐士共同探讨这样的算法。隐士的MSN: nethermit#hotmail。com。

评论

14 楼 caocao 2008-04-01  

corvallis 写道

说错了。用SIFT的feature直接计算distance怎么样

corvallis 写道

全部转成黑白的再比？
你这个和很popular的SIFT加cascade的decision tree 比， 有什么优势？

SIFT算法我详细研究过，不过没有采用，原因是不同的图出来的点数量可以差很多，不同的点虽然校正了，但也很难逐点比较，距离可以算，但是距离一样很难逐个比较。

13 楼 corvallis 2008-03-29  

说错了。用SIFT的feature直接计算distance怎么样

corvallis 写道

全部转成黑白的再比？
你这个和很popular的SIFT加cascade的decision tree 比， 有什么优势？

caocao 写道

rubynroll 写道

无论是面积还是颜色直方图，在对付楼主列出来的图像都有问题。
例如那个蓝色笔画污染，还有绿色块，以及那个色温变化的图像都会有问题的....

说得对，颜色直方图无法对付偏色的图像，而且图片旋转后的直方图会大变样，因为边角补齐的像素基本都是纯色的。
我这个算法主要考虑的是整体上点与点之间的关系，对颜色也不是很敏感的，类似围棋里看一片棋子的势，围棋高手看大片的棋子能够评价出优劣，我这个算法有点评价图像整体的“势”的意味，所以可以用很少的一些数字来概括一幅图。优点是图与图之间的比较只需要在这些数字间进行运算，缺点是无法区分小块区域的细微不同，不过这个缺点也是优点，因为需求就是要容许小块被PS。

12 楼 corvallis 2008-03-29  

全部转成黑白的再比？
你这个和很popular的SIFT加cascade的decision tree 比， 有什么优势？

caocao 写道

rubynroll 写道

无论是面积还是颜色直方图，在对付楼主列出来的图像都有问题。
例如那个蓝色笔画污染，还有绿色块，以及那个色温变化的图像都会有问题的....

说得对，颜色直方图无法对付偏色的图像，而且图片旋转后的直方图会大变样，因为边角补齐的像素基本都是纯色的。
我这个算法主要考虑的是整体上点与点之间的关系，对颜色也不是很敏感的，类似围棋里看一片棋子的势，围棋高手看大片的棋子能够评价出优劣，我这个算法有点评价图像整体的“势”的意味，所以可以用很少的一些数字来概括一幅图。优点是图与图之间的比较只需要在这些数字间进行运算，缺点是无法区分小块区域的细微不同，不过这个缺点也是优点，因为需求就是要容许小块被PS。

11 楼 caocao 2008-03-28  

rubynroll 写道

无论是面积还是颜色直方图，在对付楼主列出来的图像都有问题。
例如那个蓝色笔画污染，还有绿色块，以及那个色温变化的图像都会有问题的....

说得对，颜色直方图无法对付偏色的图像，而且图片旋转后的直方图会大变样，因为边角补齐的像素基本都是纯色的。
我这个算法主要考虑的是整体上点与点之间的关系，对颜色也不是很敏感的，类似围棋里看一片棋子的势，围棋高手看大片的棋子能够评价出优劣，我这个算法有点评价图像整体的“势”的意味，所以可以用很少的一些数字来概括一幅图。优点是图与图之间的比较只需要在这些数字间进行运算，缺点是无法区分小块区域的细微不同，不过这个缺点也是优点，因为需求就是要容许小块被PS。

10 楼 rubynroll 2008-03-25  

无论是面积还是颜色直方图，在对付楼主列出来的图像都有问题。
例如那个蓝色笔画污染，还有绿色块，以及那个色温变化的图像都会有问题的....

9 楼 maweifeng 2008-03-14  

一般来说，基于颜色直方图来判别就差不多了。

8 楼 shellkk 2008-03-13  

rubynroll 写道

指点不敢当，共同探讨吧。
我对你的“旋转角度不敏感数据”提取相当感兴趣，如果仅仅考虑到90,180,270这几种情况倒还好办，如果是旋转30度呢？我能想到的就是特征点之间的相对仰角和距离了是两种“旋转角度不敏感数据”，其它我还真想不到。如果以图像中心点展开提取特征点，虽然可以比较容易提取“旋转角度不敏感数据”，但是如果对图像进行偏移处理就会导致检测失败....所以我觉得这个部分比较难...不知楼主是否可以透露一二？

  有一些基本的旋转不变量的，面积就是最简单的一个，其余的忘了，可以去查查计算机视觉的书

7 楼 fengzl 2008-03-12  

能介绍一下怎么个做法就更好了

6 楼 caocao 2007-12-25  

rubynroll 写道

指点不敢当，共同探讨吧。
我对你的“旋转角度不敏感数据”提取相当感兴趣，如果仅仅考虑到90,180,270这几种情况倒还好办，如果是旋转30度呢？我能想到的就是特征点之间的相对仰角和距离了是两种“旋转角度不敏感数据”，其它我还真想不到。如果以图像中心点展开提取特征点，虽然可以比较容易提取“旋转角度不敏感数据”，但是如果对图像进行偏移处理就会导致检测失败....所以我觉得这个部分比较难...不知楼主是否可以透露一二？

这个我是这样做的，不管图片如何旋转、镜像，总可以从图片中计算出几个平面，其法线方向的仰角是不变的（这里有一个假设，偏移角度不太大，如果角度太大，边角补齐的像素会大大影响该平面的计算），如果进行平移处理，那么仰角会变，会随平移距离渐渐增大而慢慢偏离原仰角，算相似度就有着落了。
这算法对于90,180,270加水平、垂直镜像超级准确，而且没有提取特征点。当然，仅仅这个是不够的，还需要融入其他好几套算法，不然误认率会有点高。

5 楼 rubynroll 2007-12-24  

指点不敢当，共同探讨吧。
我对你的“旋转角度不敏感数据”提取相当感兴趣，如果仅仅考虑到90,180,270这几种情况倒还好办，如果是旋转30度呢？我能想到的就是特征点之间的相对仰角和距离了是两种“旋转角度不敏感数据”，其它我还真想不到。如果以图像中心点展开提取特征点，虽然可以比较容易提取“旋转角度不敏感数据”，但是如果对图像进行偏移处理就会导致检测失败....所以我觉得这个部分比较难...不知楼主是否可以透露一二？

4 楼 caocao 2007-12-24  

rubynroll 写道

从图像的评分值来看，楼主的算法已经不是“理论上可行”了，而是“非常实用”了。没做过图像识别的人可能会认为这个算法很简单，其实实现起来是非常困难的。

楼主的算法描述其实很模糊，例如“旋转角度不敏感数据”，“偏色不敏感数据”和“整体轮廓数据”，这个绝对不是简单的对图像进行取样，从效果来看，这个数据的选取应当是非常之有效。

我曾经做过2年的图像识别算法方面的开发，说实在的，对楼主的算法准确程度非常的惊讶！不过，楼主只列出了“识别相似图像”的评分，我倒是很想看看你的算法对“识别不相似图像”的评分，例如把图中的MM换成另一个人，不是用PS替换另一个人，而是在相似背景实景用另外一个人做同样姿势拍摄，如果评分马上能降低到0.2以下，那么我认为这个算法就是非常成功的了。

谢谢rubynroll的指点。很遗憾，背景、人物衣着、动作全都相似在这个算法里相似度是很高的，因为还没有加入识别核心区域的东西。这个算法只是抽取了很少的一些数字存库，以后的比对只是对这些数字运算，貌似很难照顾到图像的细节部分，除非算法的抽象层次提到很高，未来再努力。
对于其他不相似图片来说，误判率基本1-5%，这样已经大大减轻审核图片人员的工作量了。

另，我也有你说的那种背景、人物衣着、动作全都相似的识别算法，但是要扫描原图进行比对，所以无法加入这套算法，扫描原图的性能相当差，如果图片大一点，扫一下都要好几秒。

3 楼 rubynroll 2007-12-24  

从图像的评分值来看，楼主的算法已经不是“理论上可行”了，而是“非常实用”了。没做过图像识别的人可能会认为这个算法很简单，其实实现起来是非常困难的。

楼主的算法描述其实很模糊，例如“旋转角度不敏感数据”，“偏色不敏感数据”和“整体轮廓数据”，这个绝对不是简单的对图像进行取样，从效果来看，这个数据的选取应当是非常之有效。

我曾经做过2年的图像识别算法方面的开发，说实在的，对楼主的算法准确程度非常的惊讶！不过，楼主只列出了“识别相似图像”的评分，我倒是很想看看你的算法对“识别不相似图像”的评分，例如把图中的MM换成另一个人，不是用PS替换另一个人，而是在相似背景实景用另外一个人做同样姿势拍摄，如果评分马上能降低到0.2以下，那么我认为这个算法就是非常成功的了。

2 楼 caocao 2007-12-24  

JAVA_ED 写道

这感觉有些象以前线性代数里的相似矩阵 C~-1*A*C=B
并且这里的C是可子替换的 C=c1*c2*c3... 同样c1~-1A*C1=B
比如A图片经过左旋转90度,切边并转换绿色后, 可以与B图片相同或近似
主要是识别应该还是对图象大部分区域的识别, 相似的图象至少在大部分区域应该拥有
很大的相似程度, 另外还有一个可以称为核心区域,比如说图中MM的脸,如果脸部
有很大的区别, 即使图中其他部分都近似相同,我们也不会将图片识别为同一张,
因为潜意识中你会认为这根本就是2张不同的图片, C在这里是不存在的,所以这
取决于你算法的需求.

我没有做过类似的东西, 感觉LZ的算法应该能满足一般的识别需求了

嗯，有点类似相似矩阵，不过相似矩阵貌似运算量太大。我这里只是抽取了一些整数、浮点数来进行运算，并不敢奢求进行相似变换的那一系列矩阵。

核心区域识别是一个很好的切入点，有些论文叫证据法，我这个需求里不需要这个特性，因为要识别轻微PS的图像。我这个算法算是智商比较低的那种，属于蛮力型，核心区域识别技术含量就高了很多，以后研究研究，多谢指点 。

1 楼 JAVA_ED 2007-12-22  

引用

貌似效果还不错，基本实现了需求，下面隐士谈谈思路。由需求可知第一步是提取图像的特征数据：
1、整个文件的Hash码，用来辨认完全一样的图像。
2、旋转角度不敏感数据，这是用来抗旋转、镜像的。
3、宽高比例不敏感数据，这是用来抗缩放、比例失真的。
4、偏色不敏感数据，这是用来抗偏色、过曝、欠曝的。
5、整体轮廓数据，这是用来抗加边、模糊、噪点、水印、轻微PS的。

这感觉有些象以前线性代数里的相似矩阵 C~-1*A*C=B
并且这里的C是可子替换的 C=c1*c2*c3... 同样c1~-1A*C1=B
比如A图片经过左旋转90度,切边并转换绿色后, 可以与B图片相同或近似
主要是识别应该还是对图象大部分区域的识别, 相似的图象至少在大部分区域应该拥有
很大的相似程度, 另外还有一个可以称为核心区域,比如说图中MM的脸,如果脸部
有很大的区别, 即使图中其他部分都近似相同,我们也不会将图片识别为同一张,
因为潜意识中你会认为这根本就是2张不同的图片, C在这里是不存在的,所以这
取决于你算法的需求.

我没有做过类似的东西, 感觉LZ的算法应该能满足一般的识别需求了