图像比较-快速算法

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

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

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

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

关键点匹配

比选择100个随机点好得多，而是选择100个重要点。
图像的某些部分比其他部分（尤其是在
边缘和拐角处）具有更多信息，而这些正是您要用于智能图像
匹配的部分。Google的“ 关键点
提取 ”和
“ 关键点匹配 ”，
您会发现很多关于该主题的学术论文。如今，SIFT
关键点可以
说是最受欢迎的，因为它们可以匹配不同比例，
旋转和光照下的图像。一些SIFT实现可以在
这里找到。

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

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

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

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

对于纹理方向直方图，我们首先
对图像执行边缘检测。每个边缘点都有一个法线向量，该向量指向
垂直于边缘的方向。我们将法线向量的角度量化为
0和PI之间的6个桶中的一个（由于边缘具有180度对称性，因此将
-PI和0之间的角度转换为0和PI之间的角度）。计算
每个方向上的边缘点数量后，我们得到了
代表纹理方向的未归一化直方图，我们通过将每个存储桶除以
图像中的边缘点总数来对其进行归一化。

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

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

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

对于绿色直方图中的每个存储桶，对其他直方图重复上述 *** 作，
然后将所有结果相加。结果越小，匹配越好。
对数据库中的所有图像重复上述 *** 作，结果最小的匹配
获胜。您可能希望有一个阈值，在该阈值之上算法将
得出结论，未找到匹配项。

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

第三种方法可能比其他两种方法快得多，这是使用
语义文本
森林（PDF）。这
涉及提取简单的关键点并使用收集决策树
对图像进行分类。这比简单的SIFT关键点匹配要快，因为
它避免了昂贵的匹配过程，并且关键点比
SIFT 简单得多，因此关键点提取要快得多。但是，它保留了SIFT
方法对旋转，缩放和照明的不变性，
这是直方图方法所缺少的重要功能。

更新：

我的错误–语义Texton Forests论文不是专门针对图像
匹配，而是针对区域标签。进行匹配的原始论文是
：使用随机
树进行关键点识别。此外，以下论文继续
发展这些思想并代表了最先进的技术（c。2010）：

使用随机蕨类进行快速关键点识别 -比Lepetit 06更快，更可扩展