Thread Subject: cross correlation

hi,

I have a question. I have a sequence of TEM pictures which are not alligned due to heating up of the sample. I am trying to write a programme that automatically shifts these pictures. I am using the cross correlation function of matlab for this. But because the pictures are quite big I reduced the size of the pictures first to make it faster. After I found the maximum, I have a good estimate of what the shift is. Then I want to use the cross correlation function again on the original image, only then with the bounderies I found in my first, reduced picture, estimation. Is this possible in Matlab?

ps. I can't just use a subwindow of the original image because there are a lot of black spaces in the pictures, always on different places.

Hope you can help me.
Greetings Rudy

Rudy,

If I understand your question correctly, you want to:

- cross correlate two downsized images to get a first guess of the shift
- Use the first guess to improve the speed of cross-correlation on the full-size images

Presumably the ideal outcome would be an improvement in the speed of your cross-correlation, whilst still getting the same accuracy as using cross-correlation from the full size image?

Firstly, it would have helped that you described the problem a bit clearer, giving exact function names (I presume you're using xcorr2?) and perhaps an example of your current code.

Assuming that my interpretation is right, there are a few different answers/comments that are relevant:

---
1. No, as it's not possible to directly provide xcorr2 with an initial guess (see help xcorr2).

---
2. It is possible to indirectly provide a guess: The best bet would probably be to round your initial guess to the nearest number of pixels, then use the circshift() function to move your second full-size image by that amount. Then submit your first image and the moved second image to xcorr2. Add whatever shift you get as a result to the input guessed shift.

---
3. NUMBER 2 PROBABLY WON'T HELP... If anything, it'll be slower due to the additional overhead of shifting the image. The problem is that the majority of processing overhead for a cross correlation isn't in the peak finding routine (IF IT IS, THEN YOU NEED TO FIND A BETTER PEAK FINDING ROUTINE!!!!) - the majority of overhead is in the FFT, conjugation, multiply, and IFFT process which is the core algorithm of a cross correlation. Thus, if you do use the full size image at any stage, you will have to accept that overhead regardless of your initial guess. You can find out which bits of your code are taking the longest time using the profiler and/or the tic/toc functions.

---
4. If you're desperate for speed, have a fairly recent NVIDIA graphics card, and are certain you want to use a full-res image, you could write you're own cross correlation algorithm, which would go something like this:

  % Load images:
  A = double(imread('A.jpg'))
  B = bouble(imread('B.jpg'))

  % Normalise if necessary
  % insert normalisation here if you want it...
  % see help('xcorr') for a good explanation

  % Take FFTs
  S = fft2(A)
  T = fft2(B)

  % Conjugate T and multiply with S
  T = S.*conjg(T)

  % Take IFFT
  C = ifft2(T)

  % Find CC peak
  % Use your own peak finding algorithm,
  % or one here on the FEX (there are loads)
  % to find the maximum peak location,
  % which represents your image shift.

NOTE that this won't be any faster than xcorr2 (probably slower) unless you have a reasonable NVIDIA card. if you do, however, search for and install the 'Matlab plug-in for CUDA' which overloads Matlab's FFT and IFFT functions to do the processing on the graphics card. This will give you a 10x - 14x speed increase.

NOTE also that you may need to circshift() the FFTs and cast complex C to real. I can't remember, and don't have MATLAB in front of me so can't find out!

---
5 I know you said you can't use subwindows, but if you were fairly sure that your subwindows were bigger than the black spots, it wouldn't matter.

---
6. I don't know the ins-and-outs of your sample preparation, but I'd say there's a good possibility that your sample expands as well as shifting. In that case, a windowed cross-correlation could be much more effective than a whole-image correlation, even if you only divide your image into 4 quarters.

Hope this helps!

Tom Clark

Thank you for your quick reply. You understood my problem correctly. You have given me an idea with the subwindow thing. The pictures I have are that of crystal growth, so the first pictures of the sequence are 90% black or so. I will now try to find the subwindow containing the highest value (guaranteeing that there is always something in this window) and will do the Xcorr2 function on that window. I think this will work.

Again thanks for the reply

No worries, good luck!

Tom Clark

"rudy blabla" <r_schuitema@hotmail.com> wrote in message <h73dh3$had$1@fred.mathworks.com>...
> Thank you for your quick reply. You understood my problem correctly. You have given me an idea with the subwindow thing. The pictures I have are that of crystal growth, so the first pictures of the sequence are 90% black or so. I will now try to find the subwindow containing the highest value (guaranteeing that there is always something in this window) and will do the Xcorr2 function on that window. I think this will work.
>
> Again thanks for the reply