python - Finding a subimage inside a Numpy image

Question

I have two Numpy arrays (3-dimensional uint8) converted from PIL images.

I want to find if the first image contains the second image, and if so, find out the coordinates of the top-left pixel inside the first image where the match is.

Is there a way to do that purely in Numpy, in a fast enough way, rather than using (4! very slow) pure Python loops?

2D example:

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

How to do something like this?

position = a.find(b)

position would then be (0, 2).

Answer 1

I'm doing this with OpenCV's matchTemplate function. There is an excellent python binding to OpenCV which uses numpy internally, so images are just numpy arrays. For example, let's assume you have a 100x100 pixel BGR file testimage.bmp. We take a 10x10 sub-image at position (30,30) and find it in the original.

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)

Output:

(30, 30)

You can choose between several algorithms to match the template to the original, cv2.TM_CCOEFF_NORMED is just one of them. See the documentation for more details, some algorithms indicate matches as minima, others as maxima in the result array. A word of warning: OpenCV uses BGR channel order by default, so be careful, e.g. when you compare an image you loaded with cv2.imread to an image you converted from PIL to numpy. You can always use cv2.cvtColor to convert between formats.

To find all matches above a given threshold confidence, I use something along the lines of this to extract the matching coordinates from my result array:

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

This gives a tuple of arrays of length 2, each of which is a matching coordinate.