46
$\begingroup$

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: enter image description here


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

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. enter image description here

$\endgroup$
  • 1
    $\begingroup$ Are you looking for a solution for matching such dots, or for more complex pictures? How many dots could there be in the pictures? $\endgroup$ – user42 Oct 27 '11 at 14:44
  • $\begingroup$ Yeah, that's very important. If it's just dots of known size, you can optimize for that. If it's fiduciary markers that you have control over, you can optimize for that. Be more specific about what you're using this for. $\endgroup$ – endolith Oct 27 '11 at 16:23
  • $\begingroup$ For the problem that I'm working on it there are sets of points (each several hundred points) in which another smaller in size point set (say <100) is being sought. The demonstration above is so simplified and clear, however the real problem looks complicated. There is also an interest to find matches ranked based on undesired points exist among them. $\endgroup$ – Developer Oct 27 '11 at 17:05
  • 1
    $\begingroup$ Will there just be black and white dots? Are you getting them from a camera/scanner/something else? Binary values could make computations much faster. $\endgroup$ – endolith Oct 27 '11 at 18:31
  • $\begingroup$ Do you have a problem with finding the centres of the dots, or just with finding the miniature in the big picture knowing the positions of the dots? $\endgroup$ – user42 Oct 27 '11 at 18:42
17
$\begingroup$

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:

enter image description here

Target:

enter image description here

Cross-correlation:

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ That's right, for the problem being investigated there is no scaling but rotation can happen. Thanks for the link and answer. $\endgroup$ – Developer Oct 27 '11 at 17:10
  • $\begingroup$ @Developer: Well, this will work then, but there is probably a better way. If it's just a binary image the cross-correlation will be much faster though. (Is there such a thing as an FFT for binary signal?) Is the rotation arbitrary? You'd have to experiment with a set of rotation values that gives good results, like incrementing by 1 degree, or 5 degrees, etc. $\endgroup$ – endolith Oct 27 '11 at 18:30
  • 1
    $\begingroup$ Yes it is a binary problem. I also remember from somewhere that there was such a method to find a shorter signal modulated on a longer signal with different amplitudes. I remember regardless the complexity it was working very well showing pick points as the beginning points of the occurrences. Since the problem is in 2D it is not clear to me how to use similar concept. This is also complicated due to rotation which is applies in 2D. $\endgroup$ – Developer Oct 28 '11 at 0:45
  • 1
    $\begingroup$ Yeah, this becomes unfeasible when adding the freedom of rotation. This is why methods like RANSAC were developed. I think it helps to think outside of the DSP box on this one. $\endgroup$ – Matt M. Oct 28 '11 at 1:37
  • $\begingroup$ @MattM.: It works, it's just slow. :) $\endgroup$ – endolith Oct 28 '11 at 2:09
22
$\begingroup$

From a computer vision perspective: the basic problem is estimating a homography between your target point set and a subset of points in the large set. In your case, with rotation only, it will be an affine homography. You should look into the RANSAC method. It is designed to find a match in a set with many outliers. So, you are armed with two important keywords, homography and RANSAC.

OpenCV offers tools for computing these solutions, but you can also use MATLAB. Here is a RANSAC example using OpenCV. And another complete implementation.

A typical application might be to find a book cover in a picture. You have a picture of the book cover, and a photo of the book on a table. The approach is not to do template matching, but to find salient corners in each image, and compare those point sets. Your problem looks like the second half of this process - finding the point set in a big cloud. RANSAC was designed to do this robustly.

enter image description here

I guess cross-correlation methods can also work for you since the data is so clean. The problem is, you add another degree of freedom with rotation, and the method becomes very slow.

$\endgroup$
  • $\begingroup$ I added a bit more details in the question. I'll check deeply your links however a quick impression was they are different concepts! $\endgroup$ – Developer Oct 28 '11 at 0:41
  • 1
    $\begingroup$ Looks like it is indeed a RANSAC/homography problem :) $\endgroup$ – Matt M. Oct 28 '11 at 1:23
  • $\begingroup$ Well. It was a new concept to me. I'll try it as soon as possible. If I faced with difficulties I will share with you, great and supportive community members. $\endgroup$ – Developer Oct 28 '11 at 3:04
  • $\begingroup$ Simple Q: Is it possible/feasible to apply the RANSAC/homography method to 3D point cloud? $\endgroup$ – Developer Oct 29 '11 at 10:51
  • $\begingroup$ This is not a valid solution. The question unfortunately doesn't contain intensity information and therefore simple descriptor schemes would not work. The problem is rather more geometrical than that. $\endgroup$ – Tolga Birdal Jan 14 '17 at 12:55
3
$\begingroup$

Iif the pattern is sparse binary you can do simple covariance of coordinate vectors instead of images. Take coordinates of points in the sub-window sorted left-up, make a vector from all the coordinates and calculate covariance with vector made of coordinates of points of pattern sorted left-up. You can also use weights. After that make brute force nearest neighbor search for max covariance on some grid in the big window (and also grid in rotation angles). After finding approximate coordinates with search you can refine them with reweighted least square method.

PS Idea is, instead of working with image you can work with coordinates of non-zero pixels. Common nearest-neighbor search. You should do exhaustive search of all search space, both translational and rotational using some grid, that is some step in coordinate and rot angle. For each coordinate/angle you take subset of pixel in the window with center with that coordinate rotated to that angle, take their coordinates(rel to center) and compare them with coordinates of pixel of the pattern you seek. You should make sure that in both sets points sorted in the same way. You find coordinates with minimum difference(maximum covariance). After that rough match you can find precise match with some optimization method. Sorry I can not relay it more simple than that.

$\endgroup$
  • 1
    $\begingroup$ Would you give us an example with more explanation of your idea? Current version of your answer is confusing to me. $\endgroup$ – Developer Nov 1 '11 at 4:07
3
$\begingroup$

I am very surprised why no-one mentioned methods of Generalized Hough Transform family. They directly solve this particular problem.

Here is what I propose:

  1. Take the template and create the R-table, indexing the edges of the template. The edges I select are the following:

enter image description here

  1. Use the default OpenCV implementation of generalized Hough transform to obtain: enter image description here

where matching locations are marked. The same method would still be functional even if the edges reduce to a single point, because the method doesn't necessitate image intensities.

Moreover, handling rotations is very natural for Hough schemes. In fact, for 2D case, it is just an added dimension in the accumulator. In case you would want to go into details of making it really efficient M. Ulrich explains a lot of tricks in his paper.

$\endgroup$
1
$\begingroup$

This is a good application for geometric hashing. geometric hashing wikipedia page

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.