图像比较 - 快速算法

Question

我正在寻找创建一个基本图像表，然后将任何新图像与该表进行比较，以确定新图像是否与基本图像完全(或接近)重复。

例如:如果您想将同一图像的存储量减少 100 次，您可以存储它的一份副本并提供指向它的引用链接。当输入新图像时，您想与现有图像进行比较以确保它不是重复的...想法？

我的一个想法是缩小到一个小的缩略图，然后随机选择 100 个像素位置并进行比较。

Answer 1

以下是解决此问题的三种方法(还有许多其他方法)。

第一种是计算机视觉中的标准方法，即关键点匹配。这可能需要一些背景知识来实现，并且可能很慢。

第二种方法仅使用基本图像处理，并且可能比第一种方法更快，并且易于实现。然而，它在可理解性方面的收获却缺乏鲁棒性——在缩放、旋转或变色的图像上匹配失败。

第三种方法既快速又可靠，但可能是最难实现的。

关键点匹配

比选择 100 个随机点更好的是选择 100 个重要点。图像的某些部分比其他部分具有更多信息(尤其是在边缘和角落)，而这些正是您想要用于智能图像匹配的部分。谷歌“ keypoint extraction”和“ keypoint matching”，你会发现很多关于这个主题的学术论文。这些天， SIFT keypoints可以说是最受欢迎的，因为它们可以匹配不同比例、旋转和光照下的图像。可以找到一些 SIFT 实现 here .

关键点匹配的一个缺点是简单实现的运行时间:O(n^2m)，其中 n 是每个图像中的关键点数，m 是数据库中的图像数。一些聪明的算法可能会更快地找到最接近的匹配，比如四叉树或二进制空间分区。

替代解决方案:直方图方法

另一个不太稳健但可能更快的解决方案是为每个图像构建特征直方图，并选择直方图最接近输入图像直方图的图像。我作为本科生实现了这个，我们使用了 3 个颜色直方图(红色、绿色和蓝色)，以及两个纹理直方图，方向和比例。我将在下面提供详细信息，但我应该注意，这仅适用于匹配与数据库图像非常相似的图像。使用此方法重新缩放、旋转或变色的图像可能会失败，但裁剪等小的更改不会破坏算法

计算颜色直方图很简单——只需选择直方图桶的范围，并为每个范围计算该范围内具有颜色的像素数。例如，考虑“绿色”直方图，假设我们为直方图选择 4 个桶:0-63、64-127、128-191 和 192-255。然后对于每个像素，我们查看绿色值，并在适当的桶中添加一个计数。当我们完成计数后，我们将每个桶的总数除以整个图像中的像素数，以获得绿色 channel 的归一化直方图。

对于纹理方向直方图，我们首先对图像进行边缘检测。每个边缘点都有一个法向量，指向垂直于边缘的方向。我们将法向量的角度量化为 0 和 PI 之间的 6 个桶之一(由于边缘具有 180 度对称，我们将 -PI 和 0 之间的角度转换为 0 和 PI 之间)。在计算出每个方向的边缘点数量后，我们得到了一个表示纹理方向的未归一化直方图，我们通过将每个桶除以图像中边缘点的总数对其进行归一化。

为了计算纹理尺度直方图，对于每个边缘点，我们测量到下一个具有相同方向的最近边缘点的距离。例如，如果边缘点 A 的方向为 45 度，则算法沿该方向行走，直到找到另一个方向为 45 度(或在合理偏差范围内)的边缘点。在计算每个边缘点的距离后，我们将这些值转储到直方图中，并通过除以边缘点的总数对其进行归一化。

现在每个图像有 5 个直方图。要比较两个图像，您需要获取每个直方图桶之间差异的绝对值，然后对这些值求和。例如，要比较图像 A 和 B，我们将计算

|A.green_histogram.bucket_1 - B.green_histogram.bucket_1| 

对于绿色直方图中的每个桶，并对其他直方图重复，然后总结所有结果。结果越小，匹配越好。对数据库中的所有图像重复，结果最小的匹配获胜。您可能希望有一个阈值，高于该阈值，算法会得出未找到匹配项的结论。

第三选择 - 关键点 + 决策树

第三种方法可能比其他两种方法快得多是使用 semantic texton forests (PDF)。这涉及提取简单的关键点并使用集合决策树对图像进行分类。这比简单的 SIFT 关键点匹配要快，因为它避免了代价高昂的匹配过程，而且关键点比 SIFT 简单得多，因此关键点提取要快得多。然而，它保留了 SIFT 方法对旋转、缩放和光照的不变性，这是直方图方法所缺乏的一个重要特征。

更新 :

我的错误——Semantic Texton Forests 论文并不是专门关于图像匹配，而是区域标签。做匹配的原论文是这样的: Keypoint Recognition using Randomized Trees .此外，以下论文继续发展思想并代表最先进的技术(c. 2010):

Fast Keypoint Recognition using Random Ferns - 比 Lepetit 06

更快、更具可扩展性

BRIEF: Binary Robust Independent Elementary Features - 不那么健壮但非常快 - 我认为这里的目标是在智能手机和其他手持设备上进行实时匹配