比较两幅图像的算法

阅读文章: “使用模型更新的协方差跟踪 关于黎曼流形上的方法》(2006)。 IEEE 计算机视觉与模式识别。

使用本文提供的技术，我成功地检测到了从相邻网络摄像头捕捉到的图像中的重叠区域。我的协方差矩阵由 Sobel，canny 和 SUSAN 方面/边缘检测输出，以及原始的灰度像素组成。

实际上，这远没有看起来那么简单: ——尼克的建议是个好建议。

首先，请记住，任何有价值的比较方法基本上都是通过将图像转换成不同的形式来工作的——这种形式可以更容易地挑选出相似的特征。通常，这些东西读起来不会很轻松。


我能想到的最简单的例子之一就是简单地使用每个图像的颜色空间。如果两个图像的颜色分布非常相似，那么可以合理地确定它们显示的是相同的内容。至少，您可以有足够的确定性来标记它，或者进行更多的测试。在颜色空间中比较图像也会抵制旋转、缩放和一些裁剪。当然，它不会抵抗图像的大幅修改或重新着色(甚至一个简单的色相变化都会有些棘手)。

Http://en.wikipedia.org/wiki/rgb_color_space
Http://upvector.com/index.php?section=tutorials&subsection=tutorials/colorspace

另一个例子涉及到霍夫变换。这种转换实际上是将图像分解为一组线条。然后你可以在每张图片中选择一些“最强”的线条，看看它们是否对齐。您还可以做一些额外的工作来尝试补偿旋转和缩放——在这种情况下，因为比较几行图像比对整个图像做同样的工作计算量小得多——所以不会那么糟糕。

Http://homepages.inf.ed.ac.uk/amos/hough.html
Http://rkb.home.cern.ch/rkb/an16pp/node122.html
Http://en.wikipedia.org/wiki/hough_transform

如果你愿意考虑一个完全不同的方法来检测你的图像的非法拷贝，你可以考虑 水印。(由1.4开始)

... 将版权信息插入数字对象而不损失质量。无论何时数字对象的版权受到质疑，都会提取这些信息以确定合法的所有者。还可以将原始买家的身份和版权持有人的身份一起编码，从而可以追踪任何未经授权的复制品。

虽然这也是一个复杂的领域，但是有一些技术允许水印信息通过粗略的图像修改来保持: (从1.9开始)

任何合理强度的信号转换都无法消除水印。因此，一个愿意去除水印的盗版者将不会成功，除非他们过于贬低文件的商业利益。

当然，常见的问题是实施这种方法: “ ... ... 非常具有挑战性”，但是如果你成功了，你会对图像是否是拷贝有很高的信心，而不是百分比的可能性。

这只是一个建议，可能行不通，我已经准备好接受这个建议了。

这将产生假阳性，但希望不是假阴性。

1. 调整两幅图像的大小，使它们大小相同(我假设宽度与长度的比率在两幅图像中是相同的)。

2. 用无损数据压缩算法(例如 gzip)压缩两幅图像的位图。

3. 查找具有相似文件大小的文件对。例如，您可以根据文件大小的相似程度对每对文件进行排序，然后检索顶部的 X。

正如我所说，这肯定会产生假阳性，但希望不是假阴性。您可以在5分钟内实现它，而 Porikil 等。可能需要大量的工作。

我相信，如果你愿意将这种方法应用到每一个可能的方向和负面的版本，一个良好的开始图像识别(具有良好的可靠性)是使用特征脸: http://en.wikipedia.org/wiki/Eigenface

另一个想法是将两幅图像转换成它们各自组成部分的向量。一个很好的方法是创建一个在 x * y 维度下运行的向量(x 是图像的宽度，y 是高度) ，每个维度的值应用于(x，y)像素值。然后运行 K- 最近邻居的一个变体，它有两个类别: 匹配和不匹配。如果它足够接近原始图像，它将适合匹配类别，如果不那么它不会。

K 最近的邻居(KNN)可以在这里找到，也有其他很好的解释在网络上: http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

KNN 的好处是，与原始图像比较的变量越多，算法就越精确。缺点是首先需要映像目录来训练系统。

这些只是我对这个问题的一些想法，从来没有尝试过，但是我喜欢思考这样的问题！

在你开始之前

考虑正常化的图片，如果一个是比其他更高的分辨率，考虑选择其中之一是一个压缩版本的其他，因此缩小分辨率可能会提供更准确的结果。

考虑扫描图像的各个前瞻性区域，这些区域可以代表图像的缩放部分以及各种位置和旋转。如果其中一个图像是另一个图像的扭曲版本，那么问题就变得棘手了，这些就是你应该识别和妥协的限制。

Matlab 是测试和评估图像的优秀工具。

测试算法

您应该测试(至少)一个大型的人工分析测试数据集，其中匹配是预先知道的。例如，如果在测试数据中有1,000个图像，其中5% 匹配，那么现在就有了一个相当可靠的基准测试。在测试数据中发现10% 阳性的算法不如发现4% 阳性的算法好。然而，一个算法可能找到所有的匹配，但也有一个很大的20% 的假阳性率，所以有几种方法来评价您的算法。

测试数据的设计应该尽可能涵盖您希望在现实世界中找到的动力学类型。

值得注意的是，每个有用的算法必须比随机猜测执行得更好，否则它对我们毫无用处！

然后，你可以将你的软件以一种可控的方式应用到现实世界中，并开始分析它产生的结果。这种软件项目可以无止境地进行下去，你总是可以做出一些调整和改进，重要的是在设计它的时候要记住这一点，因为它很容易落入永无止境的项目的陷阱。

彩色水桶

使用两张图片，扫描每个像素并计算颜色，例如你可能有“桶”:

white
red
blue
green
black

(显然，计数器的分辨率会更高)。每找到一个“红色”像素，就增加红色计数器。每个桶可以代表光谱的颜色，分辨率越高越准确，但你应该试验一个可接受的差异率。

一旦你有你的总数，比较它的总数为第二个形象。您可能会发现，每个图像都有一个相当独特的足迹，足以识别匹配。

边缘检测

用 边缘检测怎么样。
_{(来源: 维基百科)}

与两个类似的图片边缘检测应该为您提供一个可用的和相当可靠的独特足迹。

拍摄两张照片，并应用边缘检测。也许测量边缘的平均厚度，然后计算图像可以缩放的概率，如果必要的话可以重新缩放。下面是一个应用 Gabor 滤波器(一种边缘检测)在不同旋转的例子。

比较图片的像素，计算匹配和不匹配的像素。如果它们在一定的误差阈值内，那么就有匹配项。否则，您可以尝试将分辨率降低到某个特定点，并观察匹配的概率是否有所提高。

兴趣范围

有些图像可能具有独特的感兴趣的片段/区域。这些区域可能与图像的其余部分形成了很强的对比，并且是在其他图像中搜索以找到匹配的一个很好的项目。以下图为例:

_{(来源: Meetthegimp.org)}

蓝色的建筑工人是一个感兴趣的区域，可以用作搜索对象。可能有几种方法可以从这个感兴趣的区域提取属性/数据，并使用它们来搜索数据集。

如果您有多于2个感兴趣的区域，则可以测量它们之间的距离。举个简单的例子:

_{(来源: [西班牙语])}

我们有三个明确的兴趣区域。区域1和2之间的距离可以是200像素，区域1和3400像素之间的距离和区域2和3200像素之间的距离。

搜索其他图像，寻找相似的感兴趣区域，标准化距离值，看看是否有潜在的匹配。这种技术可以很好地工作旋转和缩放图像。感兴趣的区域越多，匹配的概率随着每个距离测量匹配而增加。

考虑数据集的上下文非常重要。例如，如果您的数据集是现代艺术，那么感兴趣的区域将工作得非常好，因为感兴趣的区域可能是 设计的成为最终图像的基本部分。不过，如果你处理的是建筑工地的图像，有关地区可能会被非法复印机解释为丑陋，可能会被大幅裁剪/编辑掉。记住数据集的共同特征，并尝试利用这些知识。

变形

变形两个图像是通过一系列步骤将一个图像变成另一个图像的过程:

压缩比是一个非常快速和合理有效的方法来确定两组数据的相似程度。阅读有关 压缩是怎么工作的将给你一个很好的想法，为什么这可以是如此有效。对于一个快速发布的算法来说，这可能是一个很好的起点。

透明度

同样，我不确定透明度数据是如何存储的某些图像类型，如 gif png 等，但这将是可提取的，并将作为一个有效的简化剪切，以比较您的数据集透明度。

反向信号

图像只是一个信号。如果你播放一个来自扬声器的噪音，而你在另一个扬声器中以完全同步的音量播放相反的噪音，它们会相互抵消。

_{(来源: Themotorreport.com.au)}

反转图像，并添加到您的其他图像。重复缩放/循环位置，直到找到一个足够的像素为白色(或黑色)的结果图像？我将把它称为中性画布) ，以便为您提供正匹配或部分匹配。

然而，考虑两个相等的图像，除了其中一个有明亮的效果:

_{(来源: McBurrz.com)}

反转其中一个，然后将其添加到另一个将不会导致一个中立的画布，这是我们的目标。然而，当比较两个原始图像的像素时，我们可以清楚地看到两者之间的关系。

我已经很多年没有研究过颜色了，我不确定颜色光谱是否是线性的，但是如果你确定了两张图片之间颜色差异的平均因子，你可以用这个值来标准化数据，然后再用这种技术进行处理。

树木数据结构

一开始这些似乎不适合这个问题，但我认为他们可以工作。

您可以考虑提取图像的某些属性(例如颜色箱)并生成 霍夫曼树或类似的数据结构。你也许可以比较两棵树的相似性。这对于摄影数据来说不是很好的工作，例如对于大光谱的颜色，但是卡通或者其他减少色彩的图像这可能是有效的。

这可能行不通，但这是个主意。Trie 数据结构非常擅长存储词典，例如字典。这是一个前缀树。也许有可能建立一个图像相当于一个词典，(再次我只能想到颜色)来构建一个尝试。如果你把一张300x300的图像缩小成5x5的正方形，然后把每个5x5的正方形分解成一系列的颜色，你就可以从得到的数据中构建一个尝试。如果一个2x2的正方形包含:

FFFFFF|000000|FDFD44|FFFFFF

我们有一个相当独特的 trie 代码，扩展了24个级别，增加/减少级别(IE 减少/增加我们的子平方的大小)可能会产生更准确的结果。

比较树木应该相当容易，并可能提供有效的结果。

更多想法

我无意中发现了一篇关于 卫星地图的分类的有趣的论文摘要，概述如下:

所考虑的纹理度量包括: 共生矩阵、灰度差、纹理-色调分析、傅里叶谱特征以及 Gabor 滤波器。特别是在采用单一频带进行分类时，一些傅里叶特征和一些 Gabor 滤波器被认为是很好的选择。

也许值得更详细地研究这些度量，尽管其中一些可能与您的数据集无关。

还有其他事情要考虑

可能有很多关于这类事情的论文，所以阅读其中的一些应该会有所帮助，尽管它们可能是非常技术性的。在计算机领域，这是一个极其困难的领域，许多人试图做类似的事情，却花费了许多毫无结果的工作时间。保持简单并建立在这些想法的基础上将是最好的方法。创建一个比随机匹配率更好的算法应该是一个相当困难的挑战，而且要开始改进这个算法确实开始变得相当难以实现。

每个方法可能都需要进行彻底的测试和调整，如果您有任何关于您将要检查的图片类型的信息，这将是有用的。例如广告，其中许多都含有文本，因此文本识别将是一种简单且可能非常可靠的寻找匹配的方法，尤其是与其他解决方案相结合时。如前所述，尝试利用数据集的公共属性。

结合可供选择的测量和技术，每个都可以有一个加权投票(取决于他们的有效性)将是一种方法，您可以创建一个系统，产生更准确的结果。

如果使用多个算法，正如本答案开头所提到的，一个人可能会发现所有的阳性，但有20% 的假阳性率，将有兴趣研究其他算法的性质/优点/弱点，因为另一个算法可能有效地消除从另一个返回的假阳性。

小心不要陷入试图完成永无止境的项目，祝你好运！

按照你所描述的形式，这个问题很棘手。你认为复制、粘贴图像的一部分到另一个较大的图像作为复制？等等。

我们宽泛地称之为重复的东西可能很难被算法识别出来。 你的副本可以是:

1. 一模一样
2. 近乎精确的副本。(图像等的次要编辑)
3. 感性的复制品(相同的内容，但不同的视角，相机等)

第一和第二个问题比较容易解决，第三个问题非常主观，仍然是一个研究课题。 我可以为1号和2号提供一个解决方案。 两种解决方案都使用了优秀的图像哈希库: < a href = “ https://github.com/JohannesBuchner/imagehash”rel = “ nofollow norefrer”> https://github.com/johannesbuchner/imagehash

1. 一模一样 使用感知散列度量可以找到精确的副本。 Phash 库很擅长这个，我经常用它来清理 训练资料。 用法(来自 github 站点)非常简单:

from PIL import Image
import imagehash


# image_fns : List of training image files
img_hashes = {}


for img_fn in sorted(image_fns):
hash = imagehash.average_hash(Image.open(image_fn))
if hash in img_hashes:
print( '{} duplicate of {}'.format(image_fn, img_hashes[hash]) )
else:
img_hashes[hash] = image_fn

2. 几乎完全相同的复制品 在这种情况下，您必须设置一个阈值，并比较它们之间的距离的散列值 这必须通过对图片内容的反复试验来完成。

from PIL import Image
import imagehash


# image_fns : List of training image files
img_hashes = {}
epsilon = 50


for img_fn1, img_fn2 in zip(image_fns, image_fns[::-1]):
if image_fn1 == image_fn2:
continue


hash1 = imagehash.average_hash(Image.open(image_fn1))
hash2 = imagehash.average_hash(Image.open(image_fn2))
if hash1 - hash2 < epsilon:
print( '{} is near duplicate of {}'.format(image_fn1, image_fn2) )

如果您退一步，这是更容易解决，如果您水印的主图像。 您将需要使用一个水印方案，以嵌入一个代码到图像。退一步说，与一些人建议的一些低级方法(边缘检测等)相比，水印方法更优越，因为:

它能抵抗信号处理攻击 信号增强-锐化，对比度等。 过滤-中间，低通，高通等。 加性噪声-高斯，均匀等。 有损数据压缩-JPEG、 MPEG 等。

它能抵抗几何攻击 仿射变换 扣减资料-裁剪、剪裁等。 随机局部失真 翘曲

对水印算法做一些研究，你就会走上解决问题的正确道路 注意: 您可以使用 斯特马克数据集对您的方法进行基准测试。它是这种类型应用程序的公认标准。

一个想法:

1. 使用关键点检测器寻找图像中某些点的尺度和变换不变描述符(例如 SIFT、 SurF、 GLOH 或 LESH)。
2. 尝试从两个图像中使用相似的描述符对齐关键点(如全景拼接) ，如果需要，允许一些图像变换(如缩放和旋转，或弹性拉伸)。
3. 如果许多关键点对齐良好(存在这样的转换，关键点对齐误差较低; 或者转换“能量”较低，等等) ，您可能会有类似的图像。

步骤2并非微不足道。特别是，您可能需要使用一个智能算法来查找其他图像上最相似的关键点。点描述符通常是非常高维的(比如100个参数) ，并且有许多点可以查看。Kd-tree 在这里可能很有用，hash 查找不能很好地工作。

变种:

• 检测边缘或其他特征而不是点。

如果你正在运行 Linux，我建议你使用两种工具:

是一个命令行程序，可以自动纠正旋转、缩放和其他失真(它主要用于合成 HDR 照片，但也适用于视频帧和其他文档)。更多信息: < a href = “ http://Hugin.sourceforge.net/docs/Manual/Align _ image _ stack.html”rel = “ nofollow norefrer”> http://hugin.sourceforge.net/docs/manual/align_image_stack.html