在Numpy图像中找到子图像

Question

我有两个Numpy数组（3维uint8类型），它们是从PIL图像转换而来的。

我想找出第一个图像是否包含第二个图像，如果包含，则找出匹配点在第一个图像中左上角像素的坐标。

是否有一种纯粹使用Numpy的快速方法来实现，而不是使用（4！非常慢）纯Python循环？

2D示例：

a = numpy.array([
    [0, 1,  2,  3],
    [4, 5,  6,  7],
    [8, 9, 10, 11]
])
b = numpy.array([
    [2, 3],
    [6, 7]
])

如何做类似这样的事情？

position = a.find(b)

position 将会是 (0, 2)。

- Etienne Perot

Answer 1

我使用OpenCV 的matchTemplate 函数实现此功能。这里有一个优秀的Python绑定到OpenCV，它在内部使用numpy，因此图像只是numpy数组。例如，假设您有一个100x100像素的BGR文件testimage.bmp。我们在位置(30,30)取一个10x10的子图像并在原始图像中找到它。

import cv2
import numpy as np

image = cv2.imread("testimage.bmp")
template = image[30:40,30:40,:]

result = cv2.matchTemplate(image,template,cv2.TM_CCOEFF_NORMED)
print np.unravel_index(result.argmax(),result.shape)

输出：

(30, 30)

您可以选择多种算法来匹配模板和原始图像，cv2.TM_CCOEFF_NORMED只是其中之一。请参阅文档以获取更多详细信息，一些算法将匹配项表示为结果数组中的最小值，而其他算法则表示为最大值。警告：OpenCV默认使用BGR通道顺序，请注意，例如当您比较使用cv2.imread加载的图像和从PIL转换为NumPy的图像时。您始终可以使用cv2.cvtColor 在不同格式之间进行转换。

要查找所有置信度（confidence）大于给定阈值的匹配项，我使用类似以下内容从结果数组中提取匹配坐标：

match_indices = np.arange(result.size)[(result>confidence).flatten()]
np.unravel_index(match_indices,result.shape)

这将给出一个长度为2的数组元组，每个数组都是匹配坐标。

- PiQuer

---

非常完整的答案，谢谢~但我希望我能更改所选的答案，但我无法这样做。 - Etienne Perot

只是出于好奇，而不是想从tom10那里偷点声望，为什么您不能更改已接受的答案呢？我是stackoverflow的新手，但在我自己的第一个问题中，我发现我可以“切换”已接受的答案，并且meta.stackoverflow.com上的其他问题表明应该可以重新接受答案。 - PiQuer

由于我使用的帐户与当前帐户不同，因此我失去了登录到另一个帐户所使用的OpenID域的控制权，因此我无法登录并更改它。 - Etienne Perot

@PiQuer，'template = image[30:40,30:40,:] '这行代码是做什么的？ - Mark Corrigan

这个解决方案有没有运行负面测试？我尝试使用完全不同的图像在原始图像中查找它，但仍然返回（x，y）坐标。 - Rod Maniego

Answer 2

可以使用scipy的correlate2d，然后使用argmax找到互相关中的峰值。

这里有更完整的数学和思想解释以及一些示例。

如果想保持纯Numpy甚至不使用scipy，或者图像很大，则最好使用基于FFT的互相关方法。

编辑：问题明确要求使用纯Numpy解决方案。但如果可以使用OpenCV或其他图像处理工具，则显然更容易使用其中之一。 PiQuer在下面给出了一个示例，如果可以使用它，我建议使用它。

- tom10

---

你能否提供一个使用correlate2d和argmax在OP的示例中实现它的代码片段？ - Dr Xorile

Answer 3

我刚完成了针对N维数组的归一化互相关的独立实现。你可以从这里获取。

交叉相关可以直接使用scipy.ndimage.correlate进行计算，也可以根据输入大小使用scipy.fftpack.fftn/ifftn在频域中计算，取决于哪种方法更快。

- ali_m

---

抱歉误点了踩（使用移动设备）。如果您修改了问题，我会撤销我的踩。目前无法操作因为它已被锁定。 - funroll

Answer 4

您可以使用类似下面的regex实现将此问题简化为一个简单的字符串搜索，接受两个PIL.Image对象并查找needle在haystack中的坐标。这比逐像素搜索快127倍。

def subimg_location(haystack, needle):
    haystack = haystack.convert('RGB')
    needle   = needle.convert('RGB')

    haystack_str = haystack.tostring()
    needle_str   = needle.tostring()

    gap_size = (haystack.size[0] - needle.size[0]) * 3
    gap_regex = '.{' + str(gap_size) + '}'

    # Split b into needle.size[0] chunks
    chunk_size = needle.size[0] * 3
    split = [needle_str[i:i+chunk_size] for i in range(0, len(needle_str), chunk_size)]

    # Build regex
    regex = re.escape(split[0])
    for i in xrange(1, len(split)):
        regex += gap_regex + re.escape(split[i])

    p = re.compile(regex)
    m = p.search(haystack_str)

    if not m:
        return None

    x, _ = m.span()

    left = x % (haystack.size[0] * 3) / 3
    top  = x / haystack.size[0] / 3

    return (left, top)

- Ben

---

聪明！与引入OpenCV相比，它如此轻巧。但是你的代码有一个问题：任何通道值为10且不在目标范围内的值都会导致匹配失败，因为默认情况下“.”不匹配换行符。可以通过在正则表达式前缀中加入“(?s)”或使用“re.DOTALL”进行编译来解决这个问题。 - dhaffey

Answer 5

import cv2
import numpy as np

img = cv2.imread("brows.PNG")              #main image
gray_img = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)

template = cv2.imread("websearch.PNG", cv2.IMREAD_GRAYSCALE)      #subimage
w,h = template.shape[::-1]

result = cv2.matchTemplate(gray_img,template, cv2.TM_CCOEFF_NORMED)
loc = np.where(result >= 0.9)

for pt in zip(*loc[::-1]):
    cv2.rectangle(img, pt,(pt[0] + w,pt[1] +h), (0,255,0),3)

cv2.imshow("img",img)
cv2.waitKey(0)
cv2.destroyAllWindows()

- TincyThomas