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 detail below:

  1. 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.

  2. 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 here.


To perform a direct correlation:

  1. Start FITSRegister and load test6.fits into both the file1 and file2 positions.

  2. Using the mouse, drag-select some small region in the second image:

  3. 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.

  4. 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.

  5. 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).

  6. 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:

  1. Load test6.fits into both the file1 and file2 positions.

  2. With the settings window selected, choose the 'Edit->Select All' menu item. This will select all of the image.

  3. 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:

    1. 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.
    2. 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.
    3. The magnitude of the complex result is computed.
    4. The result is shifted to the center of the mask used in (1).
    5. All values are rescaled so that the maximum is 1.

  4. Thus, cross correlation of a small sample (from any non-zero point) of an image and the whole image returns the image:

  5. Cross correlation of a larger sample and the whole image does not necessarily return a maximum value at the location of the subset:

  6. 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 detection.


Caveats:


İSky Coyote and Dr. Eliot Young, 2006