使用矩阵乘法的 numpy 模板匹配

Question

我试图通过沿图像移动模板来将模板与二值图像（仅黑白）匹配。并返回模板和图像之间的最小距离，该图像具有该最小距离确实发生的对应位置。例如：

图片：

0 1 0
0 0 1
0 1 1

模板：

0 1
1 1

该模板与位置 (1,1) 处的图像最佳匹配，然后距离将为 0。到目前为止，事情并不太困难，我已经得到了一些可以解决问题的代码。

def match_template(img, template):
    mindist = float('inf')
    idx = (-1,-1)
    for y in xrange(img.shape[1]-template.shape[1]+1):
        for x in xrange(img.shape[0]-template.shape[0]+1):
        #calculate Euclidean distance
        dist = np.sqrt(np.sum(np.square(template - img[x:x+template.shape[0],y:y+template.shape[1]])))
        if dist < mindist:
            mindist = dist
            idx = (x,y)
    return [mindist, idx]

但是对于我需要的大小的图像（500 x 200 像素之间的图像和 250 x 100 之间的模板）这已经需要大约 4.5 秒，这太慢了。而且我知道使用矩阵乘法可以更快地完成同样的事情（在 matlab 中我相信这可以使用 im2col 和 repmat 完成）。谁能解释我如何在 python/numpy 中做到这一点？

顺便提一句。我知道有一个 opencv matchTemplate 函数可以完全满足我的需要，但是由于我稍后可能需要更改代码，因此我更喜欢我完全理解并且可以更改的解决方案。

谢谢！

编辑：如果有人能解释我 opencv 如何在不到 0.2 秒的时间内做到这一点，那也很棒。我对源代码进行了简短的查看，但这些东西在我看来总是很复杂。

编辑2：Cython代码

import numpy as np
cimport numpy as np

DTYPE = np.int
ctypedef np.int_t DTYPE_t

def match_template(np.ndarray img, np.ndarray template):
    cdef float mindist = float('inf')
    cdef int x_coord = -1
    cdef int y_coord = -1
    cdef float dist
    cdef unsigned int x, y
    cdef int img_width = img.shape[0]
    cdef int img_height = img.shape[1]
    cdef int template_width = template.shape[0]
    cdef int template_height = template.shape[1]
    cdef int range_x = img_width-template_width+1
    cdef int range_y = img_height-template_height+1
    for y from 0 <= y < range_y:
        for x from 0 <= x < range_x:
            dist = np.sqrt(np.sum(np.square(template - img[ x:<unsigned int>(x+template_width), y:<unsigned int>(y+template_height) ]))) #calculate euclidean distance
            if dist < mindist:
                mindist = dist
                x_coord = x
                y_coord = y
    return [mindist, (x_coord,y_coord)]

img = np.asarray(img, dtype=DTYPE)
template = np.asarray(template, dtype=DTYPE)
match_template(img, template)

Answer 1

可能有一种奇特的方法可以使用纯 numpy/scipy 魔法来完成此操作。但直接使用 Cython 来完成这项工作可能会更容易（并且当您将来查看代码时更容易理解）。http://docs.cython.org/src/tutorial/numpy.html有一个关于将 Cython 与 numpy 集成的很好的教程。

编辑：我用你的 Cython 代码做了一个快速测试，它用 100x200 模板运行了大约 15 秒的 500x400 图片。经过一些调整（消除 numpy 方法调用和 numpy 边界检查），我将其缩短到了 3 秒以内。这对你来说可能还不够，但它显示了可能性。

import numpy as np
cimport numpy as np
cimport cython
from libc.math cimport sqrt

DTYPE = np.int
ctypedef np.int_t DTYPE_t

@cython.boundscheck(False)
def match_template(np.ndarray[DTYPE_t, ndim=2] img, np.ndarray[DTYPE_t, ndim=2] template):
    cdef float mindist = float('inf')
    cdef int x_coord = -1
    cdef int y_coord = -1
    cdef float dist
    cdef unsigned int x, y
    cdef int img_width = img.shape[0]
    cdef int img_height = img.shape[1]
    cdef int template_width = template.shape[0]
    cdef int template_height = template.shape[1]
    cdef int range_x = img_width-template_width+1
    cdef int range_y = img_height-template_height+1
    cdef DTYPE_t total
    cdef int delta
    cdef unsigned int j, k, j_plus, k_plus
    for y from 0 <= y < range_y:
        for x from 0 <= x < range_x:
            #dist = np.sqrt(np.sum(np.square(template - img[ x:<unsigned int>(x+template_width), y:<unsigned int>(y+template_height) ]))) #calculate euclidean distance
            # Do the same operations, but in plain C
            total = 0
            for j from 0 <= j < template_width:
                j_plus = <unsigned int>x + j
                for k from 0 <= k < template_height:
                    k_plus = <unsigned int>y + k
                    delta = template[j, k] - img[j_plus, k_plus]
                    total += delta*delta
            dist = sqrt(total)
            if dist < mindist:
                mindist = dist
                x_coord = x
                y_coord = y
    return [mindist, (x_coord,y_coord)]