opencv - Determine if an image exists within a larger image, and if so, find it, using Python

Question

I need a Python program that I am working on to be able to take a small image, determine if it exists inside a larger image, and if so, report its location. If not, report that. (In my case, the large image will be a screenshot, and the small image an image that may or may not be on the screen, in an HTML5 canvas.) Looking on line, I found out about template matching in OpenCV, which does have excellent Python bindings. I tried the following, based on very similar code I found on line, using numpy as well:

import cv2
import numpy as np
image = cv2.imread("screenshot.png")
template = cv2.imread("button.png")
result = cv2.matchTemplate(image,template,cv2.TM_CCOEFF_NORMED)
StartButtonLocation = np.unravel_index(result.argmax(),result.shape)

This doesn't do what I need it to do, because it ALWAYS returns a point in the larger image; the point where the match is closest, no matter how terrible a match it is. I want something that finds an exact, pixel for pixel match of the smaller image in the larger image, and if none exists, raises an exception, or returns False, or something like that. And, it needs to be fairly quick. Does anyone have a good idea about how to do this?

Answer 1

I will propose an answer that works fast and perfectly if you are looking for exact match both in size and in image values.

The idea is to calculate a brute force search of the wanted h x w template in a larger H x W image. The bruteforce approach would consist in looking at all the possible h x w windows over the image and check for pixel by pixel correspondence within the template. This however is very computationally expensive, but it can be accelerated.

im = np.atleast_3d(im)
H, W, D = im.shape[:3]
h, w = tpl.shape[:2]

By using the smart integral images one can calculate really fast the sum inside of a h x w window starting at every pixel. An integral image is a summed area table (cumulative summed array), that can be calculated with numpy really fast as:

sat = im.cumsum(1).cumsum(0)

and it has really nice properties, such as the calculation of the sum of all the values within a window with only 4 arithmetic operations:

Thus, by calculating the sum of the template and matching it with the sum of h x w windows over the integral image, it is easy to find a list of "possible windows" where sum of inside values is the same as the sum of the values in the template (a quick approximation).

iA, iB, iC, iD = sat[:-h, :-w], sat[:-h, w:], sat[h:, :-w], sat[h:, w:]
lookup = iD - iB - iC + iA

The above is a numpy vectorization of the operation of shown in the image for all the possible h x w rectangles over the image (thus, really quick).

This will reduce a lot the number of possible windows (to 2 in one of my tests). The last step, would be to check for exact matches with the template:

posible_match = np.where(np.logical_and.reduce([lookup[..., i] == tplsum[i] for i in range(D)]))
for y, x in zip(*posible_match):
    if np.all(im[y+1:y+h+1, x+1:x+w+1] == tpl):
        return (y+1, x+1)

Note that here y and x coordinates correspond to the A point in the image, which is the previous row and column to the template.

Putting all together:

def find_image(im, tpl):
    im = np.atleast_3d(im)
    tpl = np.atleast_3d(tpl)
    H, W, D = im.shape[:3]
    h, w = tpl.shape[:2]

    # Integral image and template sum per channel
    sat = im.cumsum(1).cumsum(0)
    tplsum = np.array([tpl[:, :, i].sum() for i in range(D)])

    # Calculate lookup table for all the possible windows
    iA, iB, iC, iD = sat[:-h, :-w], sat[:-h, w:], sat[h:, :-w], sat[h:, w:] 
    lookup = iD - iB - iC + iA
    # Possible matches
    possible_match = np.where(np.logical_and.reduce([lookup[..., i] == tplsum[i] for i in range(D)]))

    # Find exact match
    for y, x in zip(*possible_match):
        if np.all(im[y+1:y+h+1, x+1:x+w+1] == tpl):
            return (y+1, x+1)

    raise Exception("Image not found")

It works with both grayscale and color images and runs in 7ms for a 303x384 color image with a 50x50 template.

A practical example:

>>> from skimage import data
>>> im = gray2rgb(data.coins())
>>> tpl = im[170:220, 75:130].copy()

>>> y, x = find_image(im, tpl)
>>> y, x
(170, 75)

And to ilustrate the result:

Left original image, right the template. And here the exact match:

>>> fig, ax = plt.subplots()
>>> imshow(im)
>>> rect = Rectangle((x, y), tpl.shape[1], tpl.shape[0], edgecolor='r', facecolor='none')
>>> ax.add_patch(rect)

And last, just an example of the possible_matches for the test:

The sum over the two windows in the image is the same, but the last step of the function filters the one that doesn't exactly match the template.