image processing - Point Pattern Recognition

Having two different size of sets of points (2D for simplicity) dispersed within two different size squares the question are that:

1- how to find any occurrence of the the small one through the large one?
2- Any idea on how to rank the occurrences as shown on the following figure?

Here is a simple demonstration of the question and a desired solution:

---

Update 1:
The following figure shows a bit more realistic view of the problem being investigated.

Regarding the comments the following properties apply:

• exact location of points are available


• exact size of points are available
  
  
  
  • size can be zero(~1) = only a point
  
  
  
  


• all points are black on a white background


• there is no gray-scale/anti-aliasing effect

Here is my implementation of the method presented by endolith with some small changes (I rotated target instead of source since it is smaller and faster in rotation). I accepted 'endolith's answer because I was thinking about that before. About RANSAC I have no experience so far. Furthermore the implementation of RANSAC requires lots of code.

Answer

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.

Source:

Target:

Cross-correlation:

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 *

import Image
import ImageOps

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')))

close('all')

figure()
imshow(target)
gray()
show()

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')

    figure()
    imshow(source)


    # This only finds a single peak.  Use something that finds multiple peaks instead:
    peak_x, peak_y = unravel_index(argmax(d),shape(d))


    figure()    
    plot(peak_y, peak_x,'ro')
    imshow(d)

    # Keep track of all these matches:
    print angle, peak_x, peak_y, d[peak_x,peak_y] / best_match

1-color bitmaps

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.

Point cloud

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.