4

Here is a minimal example of what i try to do:

Create 3D matrix

a(:,:,1)=[
    1 2 3 4 1;
    2 3 7 1 4;
    3 7 6 0 9;
    0 3 2 8 1;
    1 4 3 1 1]

a(:,:,2)=[
    1 7 3 4 2;
    2 9 2 3 1;
    1 4 7 7 0;
    1 2 3 4 1;
    0 9 3 3 9]

a(:,:,3)=[
    9 4 0 3 5;
    1 2 3 4 1;
    2 0 2 3 1;
    1 4 2 1 1;
    2 5 7 8 1]

a(:,:,4)=[
    2 3 5 2 0
    0 0 0 0 8
    5 2 7 9 8
    2 4 1 1 0
    6 3 8 7 9]

a(:,:,5)=[
    3 5 1 4 6;
    3 2 8 0 0;
    0 2 1 0 4;
    5 4 5 5 6;
    9 5 9 9 5]

Create 3D template 

b(:,:,1)=[
    9 4 0;
    1 2 3;
    2 0 2]

b(:,:,2)=[
    2 3 5;
    0 0 0;
    5 2 7]

b(:,:,3)=[
    3 5 1;
    3 2 8;
    0 2 1]

Calculate Cross Correlation (3D cross-correlation in matlab). I think Cross Correlation is the same as convolution with the flipped template. Is that correct?

c=convn(a,b(end:-1:1,end:-1:1,end:-1:1));

Find subscripts of best matching

[x y z] = ind2sub(size(c),find(c==max(c(:))));
x=x-(size(b, 1) - 1)/2
y=y-(size(b, 2) - 1)/2
z=z-(size(b, 3) - 1)/2

I read that one has to subtract the half of the template size of the final coordinates but I don't have the link of the page with this information anymore. However, I think if one wouldn't do that returned coordinates are not the one of where the center of the template would be but on a corner of the template.

As result of my example I expect: x=2, y=2, z=4. Matlab tells me it's x=4, y=4, z=4. However, when changing the template to

b(:,:,1)=[
    9 2 3;  
    4 7 7;
    2 3 4]

b(:,:,2)=[
    2 3 4;
    0 2 3;
    4 2 1]

b(:,:,3)=[
    0 0 0;
    2 7 9;
    4 1 1]

I get the correct result (x=3, y=3, z=3).

What do I have to change to get always the correct result?

Community
  • 1
  • 1
nightlyop
  • 7,675
  • 5
  • 27
  • 36
  • Where have you read that one has to subtract the half of the timplate size of the final coordinates? Why is (3,3,3) the correct result? – NoDataDumpNoContribution Jun 20 '14 at 09:33
  • Why do you convolve with your template backwards `b(end:-1:1,end:-1:1,end:-1:1));` Why do you not do `1:end`? – kkuilla Jun 20 '14 at 09:48
  • Trilarion: As I've written: I don't remember. However if not doing you might get the coordinet of a corner of the template instead of the center but it should work anyway I think. What do you think? – nightlyop Jun 20 '14 at 10:00
  • kkuilla: Here is the link I've also posted above: http://stackoverflow.com/questions/12309509/3d-cross-correlation-in-matlab I've also watched https://www.youtube.com/watch?v=Ma0YONjMZLI and think flipping might be correct. Please correct me if I'm wrong. – nightlyop Jun 20 '14 at 10:01
  • Why do you expect the correct result to be `(x, y, z) = (2, 2, 4)`? It seems to me that you are doing the right thing and the maximum correlation is at `(4, 4, 4)` with a value of 354 compared to the value of 352 obtained at `2, 2, 4`. Also, instead of subtracting from the indices, you can just do `c = conv(..., 'same')`. – 3lectrologos Jun 20 '14 at 12:01
  • I expect the result to be in the center of the template when overlaying the template at the correct position. So shouldn't the maximum correlation be where the template matches exactly (at `(x, y, z) = (2, 2, 4)`) – nightlyop Jun 20 '14 at 14:53

1 Answers1

2

There are no error in your code

Your algorithm is correct! But unfortunately in your case the maximum of cross-correlation is located at (4, 4, 4) and not (2, 2, 4) as you would expect it to be.

This is because looking for the pattern of matrix B contained in the matrix A you found a similar one but with a much higher "intensity" at (4, 4, 4).

If you think pattern recognition in an image your situation is similar in trying to find circles in a image with a lot of intenisty variation. (example this question: Image processing to size bubbles in octave). In one of the answer proposed you can see that circles are found everywhere the image is very bright:

enter image description here

I think you are facing a similar issue here.

Community
  • 1
  • 1
vrleboss
  • 463
  • 4
  • 24
  • You're right. When I change the matrix 'a' a little i get the correct result. Thank you very much! Is there a possiblity to check the result automatically? Also I think the result might be better when using normalized cross correlation but how can i do that in 3D using convolution? – nightlyop Jun 25 '14 at 08:29
  • @vrleboss: I'm not sure how that question is similar to the problem here.. The code over there and the image you've shown are based on [circle detection using the Hough transform](https://en.wikipedia.org/wiki/Hough_transform#Circle_detection_process), not some kind of template-matching using [cross-correlation](https://en.wikipedia.org/wiki/Cross-correlation#Normalized_cross-correlation) as you've suggested. So that would be like using [`imfindcircles`](http://www.mathworks.com/help/images/ref/imfindcircles.html) from the Image Processing Toolbox, as opposed to convolution/correlation methods – Amro Jun 25 '14 at 09:41
  • @Amro totally agree with you. I was trying to find a good illustration to the problem of nightlyop but you're right this one is far from being ideal... I'll keep searching and update my answer – vrleboss Jun 25 '14 at 13:54