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.
small
image will appear in thelarge
image always in its original size and exactly with its original values? Or you need to deal with variable sizesmall
images that might beinterpolated
and handleillumination
variations? I mean, you mentionexact match
, is it really exact?PNG
format? I ask beauseJPEG
s undergo quantisation and lossy compression and things that are apparently identical can differ in their internal representation.