logo标签列表

在大图中寻找小图的快速算法？

.netalgorithmimage-processingimage
16

如何以最快的方式检查小图片是否在大图片中？

(缩放后的图片:)

enter image description here 需要找到的图片: enter image description here

我有一个解决方案，但它非常慢：

  • 我循环遍历大图中的每个像素（x，y），并比较小图的像素（0,0）（颜色值）。
  • 如果像素相同，我会迭代小图片并将其与更大的图片进行比较。 如果失败，则返回到大图片扫描循环。

这种方法需要约7秒钟才能在1600x1200照片中找到一个50x50的图像。

也许您知道更好的算法？ 我知道一款软件可以在不到一秒钟内完成此操作。

考虑字符串匹配。现在有多种快速字符串匹配算法可供使用。请参阅http://en.wikipedia.org/wiki/String_searching_algorithm。 - Captain Giraffe
1
@Captain 将其简化为字符串匹配并不是一件容易的事情。我正在处理大量与字符串匹配有关的工作，但我没有看到明显且高效的简化方法（我有一些想法，但它们并不明显）。 - Konrad Rudolph
@Konrad 我在想，无论是针还是草堆，每个字符串只有一行像素，但您可能非常正确，这可能是不容易的。 - Captain Giraffe
1
你的算法不应该那么慢。我怀疑你没有直接访问两个图像缓冲区（而是调用了一些GetPixel()函数）。如果你不确定如何做到这一点，请发布你的代码+2张图片，我们可以提供帮助。 - Tom Sirgedas
你每次这样做都会得到一个全新的图像，还是你正在处理一系列大部分相同的帧？如果是后者，像四叉树这样的东西可以使其更加高效。 - Nick Johnson
4个回答
6
为了澄清Aasmund的回答。您需要对目标图像进行卷积（哈尔小波变换也可以），从而获得结果。然后，您需要对源图像进行卷积，并尝试找到潜在的候选结果。大多数情况下，它会指向正确的方向，并且需要比较少的信息来进行比较。 - Red Knight
快速傅里叶变换的运行时间不是 ~O(N Log N) 比线性搜索更大吗？如果您在同一张大图片上进行重复搜索，这将非常有用。 - Louis Ricci
@Red Knight和Aasmund - 如果您使用FFT进行卷积，那么如何确定目标图像和源图像是否匹配？我觉得这类似于其他人建议的字符串匹配。 - O_O
1
@LastCoder：一维“线性”搜索的时间复杂度为_O(n*m)_，其中_m_是模式的长度 - 因此，除非_m_非常小，否则FFT更好。 - Aasmund Eldhuset
3
因为我已经有一段时间没做这种事情了，所以我对细节有点生疏，但是：卷积操作（无论实现方式如何）需要两张图像作为输入，并生成一张新的图像，其中位置_(x, y)上的亮度表示如果第二个图像的角落放在第一个图像的(x, y)_位置上，它们匹配得有多好。因此，你可以简单地找到最亮的像素，这将告诉你需要移动图像的程度。 - Aasmund Eldhuset
1

您的算法最坏情况下为 O(hA*wA*hB*wB)，其中hA、wA、hB和wB分别是大图像A和小图像B的高度和宽度。

这个算法的最坏情况应该是O((wA+wB)*hA*hB)

它基于字符串匹配，工作原理如下：

  • 使用字符串匹配每次在图像A的每一行中查找图像B的每一行。
    • 每次匹配时，在数组matched_row中存储三元组(rA，cA，rB)，其中(rA，cA)表示文件B的rB行在图像A中的起始点。
  • 现在，您首先按cA，然后按rA，最后按rB对matched_row进行排序。

  • 现在，您遍历数组，如果匹配了5行的图像B，则会得到以下结果：

        (12, 5, 0), (13, 5, 1), (14, 5, 2), (15, 5, 3), (15, 5, 4)
现在我们只需将 stringB 与 stringA 进行匹配即可。-- 你能解释一下吗？stringB 包含了虚拟字符，我觉得这不行。 - Tom Sirgedas
1
1
如果您知道像素值将是精确的，那么这只是字符串匹配问题的一个特例。有许多快速的字符串匹配算法，我会从Boyer-Moore或Knuth-Morris-Pratt开始。
当与Simone的结合使用时，这个答案非常好。 - JBentley
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接