Posted by
Michael Schmid on
Aug 27, 2017; 6:37pm
URL: http://imagej.273.s1.nabble.com/Help-with-Image-Stitching-using-Phase-Correlation-tp5019275p5019282.html
Hi Michael,
here is another way to see it:
When working with Fourier transforms, you have to consider your image
periodically repeated in x and y, up to inifinity:
(again ASCII painting, to be viewed with fixed font)
...
-------------------
| | | |
... | A | A | A | ...
| | | |
-------------------
| | | |
... | A | A | A | ...
| | | |
-------------------
...
So when calculating the correlation between A and B, both 512x512 pxl,
you cannot distinguish between a shift by -10 and +502 pixels; for the
periodically repeated images it is the same.
In a correlation calculated without FFT, the area where the images do
not overlap does not contribute. In a correlation calculated with the
FFT, there is no region where the images do not overlap; there is always
overlap with the periodic continuation.
If the images have less than 1/2 overlap, it is therefore better to use
smaller images (e.g. 256x256 on the right side of A and 256x265 on the
left side of B) and do the correlation with them. This makes it faster
and also makes it less likely that you get some spurious maximum from
the periodic repetitions where you do not want to check for overlap. Of
course, you have to roughly know how the images are displaced with
respect to each other, or you try with different subimages and see where
you get the best correlation. If the overlap is smaller, you can try
smaller subimages than half the image size.
For best results, one should do it iteratively, and in the second
iteration use only these parts of the image that actually overlap
according to the first result. To fill up the 2^n size needed for the
FFT, it would be best to have some smooth extrapolation taking the
periodic boundary conditions into account.
Concerning the implementation in ImageJ:
If you do Process>FFT>FD Math and correlate A with B (and do the inverse
transform), the maximum is in the center (x = y = 256 for 512-pxl
images) if the images are the same.
The maximum shifted to the left of center if image A is shifted with
respect to B to the left by up to 256 pixels. If A is shifted to the
left by more than 256 pixels, the maximum jumps to the right border of
the correlation output -- also the autocorrelation calculated by the FFT
has periodic boundary conditions.
You can use 'swap quadrants' to get the maximum for non-shifted images
from the center to (0,0), but still mind the periodic boundary
conditions: Now a displacement by one pixel to the left will put the
maximum to (511, 0).
Michael
________________________________________________________________
On 2017-08-26 12:53, Michael Ellis wrote:
> I am trying to learn about image stitching using cross correlation.
>
> Let say that I have two images A and B that I am trying to stitch.
>
> (you may need to switch to fixed width font to make these little text
> pictures work for you)
>
> ------- -------
> | | | |
> | A | and | B |
> | | | |
> ------- -------
>
> Considering a shift just in the X dimension, the maximum shift which
> would still have a smallest overlap would be if B is shifted (slightly
> less than) the width of A to the right of A,
> or if B is shifted (slightly less than) the width of B to the left of
> A.
>
> --------------
> | || |
> | A || B |
> | || |
> --------------
> --------------
> | || |
> | B || A |
> | || |
> --------------
>
> Let A and B both be exactly 512 by 512 pixels, that is of equal size
> and a power of 2 in both X and Y, so the images will need no padding
> when their FHT transform is created.
>
> This means that the FFT(A) and FFT(B) are also exactly 512x512.
> Further, using the FFDMath to calculate the inverse transform of the
> Correlation between FFT(A) and FFT(B) results in an image also of
> 512x512.
>
> But, since in our case the shift could be anywhere in the range from
> -511 to + 511, how can this be represented by the location of maxima
> drawn from an image with an X and Y size of 512?
>
> I have tried padding both my images to a size which is the next larger
> power of two, and for my test data this does resolve the larger
> shifts, however this hits performance dramatically and I suspect is
> not the best way to handle this.
>
> Anyone able to point me in the right direction? I understand enough of
> the mathematics to know that my grasp on the underlying maths of
> Fourier transforms is very rudimentary and shaky, so I am looking for
> practical advice on how to utilise the plugins in core ImageJ.jar to
> best solve the problem of aligning two images.
>
> Many thanks — Michael Ellis
>
> --
> ImageJ mailing list:
http://imagej.nih.gov/ij/list.html--
ImageJ mailing list:
http://imagej.nih.gov/ij/list.html