I am trying to match a template with a binary image (only black and white) by shifting the template along the image. And return the minimum distance between the template and the image with the corresponding position on which this minimum distance did occur. For example:
0 1 0 0 0 1 0 1 1
0 1 1 1
This template matches the image best at position (1,1) and the distance will then be 0. So far things are not too difficult and I already got some code that does the trick.
def match_template(img, template): mindist = float('inf') idx = (-1,-1) for y in xrange(img.shape-template.shape+1): for x in xrange(img.shape-template.shape+1): #calculate Euclidean distance dist = np.sqrt(np.sum(np.square(template - img[x:x+template.shape,y:y+template.shape]))) if dist < mindist: mindist = dist idx = (x,y) return [mindist, idx]
But for images of the size I need (image among 500 x 200 pixels and template among 250 x 100) this already takes approximately 4.5 seconds, which is way too slow. And I know the same thing can be done much quicker using matrix multiplications (in matlab I believe this can be done using im2col and repmat). Can anyone explain me how to do it in python/numpy?
btw. I know there is an opencv matchTemplate function that does exactly what I need, but since I might need to alter the code slightly later on I would prefer a solution which I fully understand and can alter.
edit: If anyone can explain me how opencv does this in less than 0.2 seconds that would also be great. I have had a short look at the source code, but those things somehow always look quite complicated to me.
edit2: Cython code
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 cdef int img_height = img.shape cdef int template_width = template.shape cdef int template_height = template.shape 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)