행렬 곱셈을 사용하여 numpy 템플릿 매칭

Question

이미지를 따라 템플릿을 이동하여 템플릿을 이진 이미지 (흑백 만)와 일치 시키려고합니다. 그리고 템플릿과 이미지 사이의 최소 거리를이 최소 거리가 발생한 해당 위치로 되돌립니다. 예를 들면 :

IMG :

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] 

하지만 이미 너무 느리고 약 4.5 초가 걸리는 I 필요한 크기 (250 × 100 화상 중에서 500 X 200 픽셀 사이 및 템플릿)의 이미지

. 그리고 나는 똑같은 일이 행렬 곱셈을 사용하여 훨씬 빨리 수행 될 수 있다는 것을 안다. (matlab에서 이것은 im2col과 repmat을 사용하여 수행 할 수 있다고 생각한다.) 누구든지 파이썬/numpy 그것을 어떻게 날 설명 할 수 있습니까?

btw. 나는 정확히 내가 필요로하는 것을 수행하는 opencv matchTemplate 함수가 있다는 것을 알고 있지만, 나중에 코드를 약간 수정해야 할 필요가 있기 때문에 완전히 이해하고 변경할 수있는 솔루션을 선호 할 것입니다.

감사합니다.

편집 : 누구나 나를 opencv가 0.2 초 이내에 어떻게하는지 설명 할 수 있다면 그것은 또한 좋을 것입니다. 나는 소스 코드를 간략하게 살펴 봤지만, 그런 것들은 항상 나에게 상당히 복잡해 보인다.

EDIT2 : 사이 썬 코드

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에 numpy와 함께 Cython을 통합하는 데 유용한 자습서가 있습니다.

EDIT : Cython 코드로 빠른 테스트를 수행했으며 100x200 템플릿으로 500x400 img의 경우 15 초를 실행했습니다. 몇 가지 개조 (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)] 

Answer 2

한 가지 가능한 방법은 (무력 또는 FFT 될 수있는) 회선을 통해입니다. 행렬 곱셈 AFAIK는 작동하지 않습니다. 템플릿으로 데이터를 컨버전해야합니다. 최대 값을 찾으십시오 (제대로 작동하려면 크기 조정이 필요합니다).

xs=np.array([[0,1,0],[0,0,1],[0,1,1]])*1. 
ys=np.array([[0,1],[1,1]])*1. 
print scipy.ndimage.convolve(xs,ys,mode='constant',cval=np.inf) 
>>> array([[ 1., 1., inf], 
     [ 0., 2., inf], 
     [ inf, inf, inf]]) 

print scipy.signal.fftconvolve(xs,ys,mode='valid') 
>>> array([[ 1., 1.], 
      [ 0., 2.]])