Good correlation images come from similar, high-contrast images.
Bad correlation images come from very different, or low-contrast images.
fftMatch determines the offset between two images. It does this by computing the sum of the product of the pixels of the two images at many different offsets. The offset which yields the largest sum is the best offset, and is printed out.
fftMatch can easily find offsets up to 1/4 the size of the input images, and performs a parabolic interpolation to estimate a sub-pixel offset between the images. It can deal with any LAS data format, and any aspect or size image (although it is most efficient with images whose size is a power of two).
It seems quite reliable in extensive testing; failing only for distant (more than 1/2 of the size of the image) or extremely low-contrast scenes. When it does fail, its confidence value is extremely low (below 30 percent); so you can double-check it by hand.
For small (under 4000 pixels square) scenes of the appropriate type, it is much faster and more accurate than hand matching.
fftMatch cannot handle scenes displaced by more than half the image. fftMatch only computes one offset for the entire image, so it ignores rotation, scaling, or warping of the images. fftMatch occasionally fails for very low-contrast or dissimilar scenes.
fftMatch can output a "correlation image". This image lets you double-check fftMatch's work.
The brightness of this image corresponds to the product of the two images at a given offset. A shift of zero pixels in all directions lies at the center of the image. Moving right or down in the correlation image corresponds to moving the second image to the right or down.
A "good" correlation image is unambigous-- it has one very bright peak (offset), with everything else dark. A "bad" correlation image does not clearly show a single offset-- it has many mottled bright regions, in several different places (offsets).
|
Good correlation images come from similar, high-contrast images. |
Bad correlation images come from very different, or low-contrast images. |
fftMatch tries to interpret the correlation image itself-- this is the source of its "confidence" value.
fftMatch is usually called by resolve, in turn called by register_ccsd or register_sic. It can also be profitably run alone.
fftMatch is designed to work with large images, having tens of millions
of pixels. Since even a 2000x2000 image might have 500x500 possible
offsets, performing this offset image matching in a straightforward way
(one offset at a time) would be very slow:
4 million pixels/image * 1 multiply/pixel/offset * 250,000 offsets=
1 trillion multiplications.
This would take a Cray T3E, at peak efficiency, about one minute.
But by using the Fast Fourier Transform (FFT), we can accomplish the
same result by FFT'ing the images, taking their product, and inverse-FFT'ing
the result. This does exactly the same thing and takes:
80 million multiply/FFT * 3 FFT = 240 million multiplications.
This takes my Pentium-166 about 20 seconds.
Thus, by using the FFT, we make the image matching go about 4,000 times faster. Hence, we call our matching program fftMatch.
Back to main interferometry page.
Last Updated: October 10, 1998
If you have any questions, please feel free to email olawlor@acm.org