2
$\begingroup$

Suppose I have two images that contain many objects that are identical, or nearly so. Specifically, say the objects are shifted and scaled, but by differing amounts, from one image to the other. Is there an efficient algorithm for matching the objects?

The prototypical example would be subsequent images from a video stream, where different objects move by a different amount relative to the camera, and we'd like to know which object went were. Coming from an astronomy, where the images are filled with point sources, one method of identifying them is to convolve the base image with the point spread function (the average point source) and look for peaks in the resulting convolution image. So, I imagine it should be possible to shift, rotate, and scale one image, compute the inner product of the results (i.e. multiply pixels, then sum them), and then look for points in the shift/rotate/scale space that are local maxima to say that something in the two images match at that point.

Can this, or something like it, be done efficiently? For instance, would it be more efficient or less efficient to locate candidate objects, cut them out, and then do the shift/rotate/scale space search than just doing it with the whole image (assuming most objects are a small shift/rotate/scale away from their prior position)?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ This is one of the classical problems in image processing known as registration. (It's not cheap, though -- people are still doing active research on this, as Google will happily tell you.) For the particular case of video, also search for optical flow. $\endgroup$ – Christian Clason Jun 15 '18 at 20:48
  • 1
    $\begingroup$ As commented, this is a classical problem often asked (including by myself), but as such, searching for the answer can so easily turn into a total waste of time and time-killer, in particular when trying to destill something which is applicable for actual work. I would encourage anyone of the community here to - if possible - provide some helpful (and practical) entry points, in particular for newcomers (and amateurs) to the field. I, for once, would love such an answer myself. $\endgroup$ – BmyGuest Jul 10 '18 at 8:22
2
$\begingroup$

I guess what you are referring to is the cross-correlation between the images. This is very good and efficient to find shifts, but not changes in scale and orientation. As you probably know, the cross-correlation simultaneously computes the inner product of one image with all possible shifts of the other, in time $O(n\log n)$, where $n$ is the number of pixels.

There is an article by Morgan McGuire An image registration technique for recovering rotation, scale and translation parameters that I've been meaning to study for some time but haven't gotten around yet. This does something similar, but also manages to capture changes in scale and rotations, in a time that essentially also is $O(n\log n)$.

A very different class of algorithms are feature matching algorithms, which analyze an image and identify special points in a way that is invariant under many different kinds of changes, like general projective transformations (including rotation, translation, scale), changes in lightness, etc. Some examples in OpenCV can be found here. One of the most famous (though not the most modern) is called SIFT, introduced by D. Lowe in Distinctive Image Features from Scale-Invariant Keypoints. This is likely much slower than the previous method.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Is the rotation/scale/translation recovering routine you've mentioned superior to the Log-Polar cited in my answer? (I've implemented that one and gave it a test. It works reasonably well within the bounds described in the publication.) Unfortunately (?) I did my coding in a specific scripting language for a specific image processing software called DigitalMicrograph, but if anyone is interested, I can make that code available. $\endgroup$ – BmyGuest Aug 1 '18 at 14:37
  • $\begingroup$ @BmyGuest Sorry, I have no idea which one would be superior... The objective of both seems to be the same. I would be interested in seeing your code. $\endgroup$ – doetoe Aug 1 '18 at 16:17
  • $\begingroup$ I've put the script on pastebin.com here $\endgroup$ – BmyGuest Aug 1 '18 at 20:51
  • $\begingroup$ @deotoe: Great, is it of any use to you? (If you need help with DigitalMicrograph or it's scripting language, just let me know. In fact, there is a DM-script tag for it over at the StackOverflow main site. $\endgroup$ – BmyGuest Aug 2 '18 at 18:19
2
$\begingroup$

Disclaimer: This is most likely not the most efficient, promising way to go about it.

When I was looking up the same topic from a similar interest (Analyzing microscopy images), I came across the following publication which peaked my interest, as it was rather straight forward to implement it in my coding environment:

Image Registration Using Log Polar Transform and Phase Correlation to Recover Higher Scale
JOURNAL OF PATTERN RECOGNITION RESEARCH 7 (2012) 90-105

Testing this out, it worked sort of fine within the limits described in the paper as well (a not too extensive scaling factor.) I think your question will depend enourmously on what application you have in mind, and what simplifications, assumptions, limitations are associated with it.

Edit: I did my tests with that algorithm in a scripting language within a scientific image/data processing software called DigitalMicrograph. If anyone is interested, I can make that script code available (just comment below). A free version of the software (with no timeout) can be downloaded from the Gatan Inc. webpage.

Improve this answer
$\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.