c - 搜索图像模式

Question

我需要做一个程序来做到这一点：给定一个图像（5 * 5 像素），我必须搜索在另一个图像中存在多少这样的图像，由许多其他图像组成。也就是说，我需要在图像中搜索给定的模式。

使用的语言是 C。我必须使用并行计算来搜索 4 个角度（0º、90º、180º 和 270º）。

最好的方法是什么？

Answer 1

似乎直截了当。

• 创建 0°、90°、180° 和 270° 旋转的 4 个版本的图像。
• 启动四个线程，每个线程都有一个版本的图像。
• (0,0)对于从到的所有职位(width - 5, height - 5)
  • 将参考图像的 25 个像素与当前位置的 25 个像素进行比较
  • 如果使用某些指标它们足够相等，请报告结果。

Answer 2

使用归一化相关来确定模板的匹配。

@Daniel，Daniel 的解决方案非常适合利用您的多个 CPU。他没有提到有用的质量指标，我想建议一种在图像处理中非常常见的质量指标。

我建议使用归一化相关[1] 作为比较指标，因为它输出一个从 -1 到 +1 的数字。其中 0 表示没有相关性，如果两个模板相同，则输出 1，如果两个模板完全相反，则输出 -1。

计算归一化相关性后，您可以通过阈值测试或峰均值测试[2] 来测试是否找到了模板。

[1 - 脚注] 你如何实现归一化相关？它非常简单，只有两个 for 循环。一旦你有一个足够好的实现，你可以通过检查相同的图像是否让你得到 1 来验证你的实现。

[2 - 脚注] 你做最大（数组）/平均值（数组_无峰值）的比率。然后阈值以确保您具有良好的峰均比。

Answer 3

无需创建图像的另外三个版本，只需以不同方式处理它们或使用类似于我在此处创建的类的东西。更好的是，只需复制 5x5 矩阵并旋转它们。然后，您可以线性扫描图像以进行所有旋转（这是一件好事）。

这个问题不能很好地扩展到并行处理，因为瓶颈肯定是访问图像数据。让多个线程访问相同的数据会减慢速度，特别是如果线程“不同步”，即一个线程比其他线程更远地通过图像，因此其他线程最终重新加载第一个线程已丢弃的数据.

所以，我认为最有效的解决方案是创建四个线程来扫描 5 行图像，每次旋转一个线程。第五个线程一次加载一行图像数据并将该行传递给四个扫描线程中的每一个，等待所有四个线程完成，即加载一行图像，附加到五个行缓冲区，启动四个扫描线程，等待线程结束并重复，直到读取所有图像行。

Answer 4

5 * 5 = 25

25 位适合整数。

每个图像都可以编码为 4 个整数的数组。

迭代你的大图，（希望它不是太大），拉出所有 5 * 5 子图像，转换为 4 个整数的数组并进行比较。