FITSRegister Update 11/04/06 - Cross Correlation
Sky Coyote, 4 Nov 2006
I have just added the ability to perform cross-correlations on subsets of two images.
This computation can be performed by two different methods. Both will be discussed in
- Direct: This involves taking a subset of an image (the 'domain'), and taking another, larger, subset of another image (the 'range'),
and then repeatedly shifting the first subimage over the second and computing the normalized parametric correlation coefficent
of the two at each overlapping point.
- Fourier transform: This involves taking a subset of an image (again, the 'domain'), and then masking that subset by making it the
same size as the second image (the entire 'range') but with all pixels outside of the subset equal to zero. Then the Fourier cross-correlation is
computed for both images as 'rotate(|iFT(FT*(im1)xFT(im2))|, sub_center_x, sub_center_y)', which provides a similar (in some cases), but not usually the same,
result as the direct method.
The direct method is used to determine feature registration between images. The only advantage to using the Fourier method is speed when
correlating large image subsets, otherwise the direct method would
be used exclusively. Hardware dedicated to performing the direct method would obviate the need for the Fourier method.
To use the correlation features, download the new FITSRegister app here:
PPC | Intel. This is not yet available from the main website.
To use the examples shown below, download the test images
To perform a direct correlation:
- Start FITSRegister and load test6.fits into both the file1 and file2 positions.
- Using the mouse, drag-select some small region in the second image:
- In the settings window, click the 'X-correlate' button. You will then see the 'Cross Correlation' window:
The window shows the correlation as a table and as an image, with the maximum value marked in red. In this case,
the maximum value of 1 is at the center of the result, indicating an identical fit at no shift. The 'Cross Correlation'
window can be resized, and the vertical bar between the table and plot can also be moved. The calculation performed
in a direct correlation is the normalized parametric correlation coefficient:
This is the same calculation performed by FITSFlow, and ranges from 1 to -1.
- Next, load test6.d0.fits into the file2 position. This image is the same as test6.fits, shifted down and to the right
by 10 pixels.
- Set the 'Shift H' and 'Shift V' fields to 15, and then click the 'X-correlate button'. The new result will be displayed in the
table and image, showing a maximum value for (-10, 10).
- The cross correlation is performed in the following order: the subset of the currently visible image (either file1 or file2),
correlated with the extended subset (by shift h and shift v) of the other image. To perform the above correlation in the opposite
order, click the Swap button to show the file1 image, and then click X-correlate again. In this case, the result will have its
maximum at (10, -10).
To perform a Fourier correlation:
- Load test6.fits into both the file1 and file2 positions.
- With the settings window selected, choose the 'Edit->Select All' menu item. This will select all of the image.
- In the 'Cross Correlation' window, click the Method:FFT button, then click 'X-correlate'. This will perform and display the
autocorrelation of the image:
The Fourier correlation is normalized so that the maximum value is 1. All results are non-negative. Since there is some dispute about
what is meant by a Fourier cross correlation, here are the exact steps that are being performed:
- The selected subset of the visible image (file1 or file2) is masked, rather than extracted. That is, all pixels outside
the selection rectangle are set to zero, and the resulting masked image is full-size and unshifted.
- Two forward transforms (exponent -1), a conjugate, a multiply, and one backward transform (exponent 1) are performed to
yield iFT(FT*(mask1) x FT(im2)), where * is the conjugate of the transform of the masked image, and x is complex multiplication.
All transforms are full complex, using FFTW. No pre or post scaling is performed.
- The magnitude of the complex result is computed.
- The result is shifted to the center of the mask used in (1).
- All values are rescaled so that the maximum is 1.
- Thus, cross correlation of a small sample (from any non-zero point) of an image and the whole image returns the image:
- Cross correlation of a larger sample and the whole image does not necessarily return a maximum value at the location
of the subset:
- As the sample is made larger, the maximum value does move to the location of the subset, becoming the autocorrelation when
the sample equals the entire image:
The primary difference between the direct and Fourier methods is that the direct method normalizes every image sample (of both images)
before the shifted multiplication is performed, while the Fourier method does not (and cannot). Therefore, while the direct correlation
of an image subset with itself will always produce a peak value of 1 at the location of an exact match, this is not the case for the
Fourier method. For example, consider the sifting property demonstrated in (4) above, which produces the maximum value at the actual
maximum of the image, not at the point sample location. This difference limits the utility of the Fourier method for image feature
- The direct method is much slower than the Fourier method for large subsets and shifts. While you can perform direct
correlations using large subsets and shifts (e.g. select the entire image and set the shifts = 1/2 image size to get an autocorrelation),
this may take several minutes or more to compute, and cannot be aborted once started.
- The shift fields only apply to the direct method. Full size images (one masked) are always used in the Fourier methd. I could
perform the Fourier calculation using smaller subsets, if desired, but one has to ask why, when in this case the direct method is
usually preferable. Nevertheless, let me know if you would like to perform Fourier correlations on image subsets as well.
- The Fourier method performs a cyclical correlation; that is: the left and right, and top and bottom, edges of the images wrap during
shifting. The direct method performs unwrapped shifts, using values of zero when outside of the image edges.
- The Fourier method I am using may not be the same as is performed by IDL. Please carefully review the steps listed in (3) above.
If you would like an alternative set of calculations performed, please let me know, and I can add them (e.g. 'IDL compatibility mode').
İSky Coyote and Dr. Eliot Young, 2006