This is not the best solution, but it's a solution. I'd like to learn of better techniques:
If they were not going to be rotated or scaled, you could use a simple cross-correlation of the images. There will be a bright peak wherever the small image occurs in the large image.
You can speed up cross-correlation by using an FFT method, but if you're just matching a small source image with a large target image, the brute-force multiply-and-add method is sometimes (not usually) faster.
The two bright spots are the locations that match.
But you do have a rotation parameter in your example image, so that won't work by itself. If only rotation is allowed, and not scaling, then it is still possible to use cross-correlation, but you need to cross-correlate, rotate the source, cross-correlate it with the entire target image, rotate it again, etc. for all rotations.
Note that this will not necessarily ever find the image. If the source image is random noise, and the target is random noise, you won't find it unless you search at exactly the right angle. For normal situations, it will probably find it, but it depends on the image properties and the angles you search in.
This page shows an example of how it would be done, but doesn't give the algorithm.
Any offset where the sum is above some threshold is a match. You can calculate the goodness of the match by correlating the source image with itself and dividing all your sums by this number. A perfect match will be 1.0.
This will be very computationally heavy, though, and there are probably better methods for matching patterns of dots (which I would like to know about).
Quick Python example using grayscale and FFT method:
from __future__ import division
from pylab import *
source_file = 'dots source.png'
target_file = 'dots target.png'
# Load file as grayscale with white dots
target = asarray(ImageOps.invert(Image.open(target_file).convert('L')))
source_Image = ImageOps.invert(Image.open(source_file).convert('L'))
for angle in (0, 180):
source = asarray(source_Image.rotate(angle, expand = True))
best_match = max(fftconvolve(source[::-1,::-1], source).flat)
# Cross-correlation using FFT
d = fftconvolve(source[::-1,::-1], target, mode='same')
# This only finds a single peak. Use something that finds multiple peaks instead:
peak_x, peak_y = unravel_index(argmax(d),shape(d))
# Keep track of all these matches:
print angle, peak_x, peak_y, d[peak_x,peak_y] / best_match
For 1-color bitmaps, this would be much faster, though. Cross-correlation becomes:
- Place source image over target image
- Move source image by 1 pixel
- bitwise-AND all overlapping pixels
- sum all the 1s
Thresholding a grayscale image to binary and then doing this might be good enough.
If the source and target are both patterns of dots, a faster method would be to find the centers of each dot (cross-correlate once with a known dot and then find the peaks) and store them as a set of points, then match source to target by rotating, translating, and finding the least squares error between nearest points in the two sets.