bugGNU Octave - Bugs: bug #41480, image package :normxcorr2 yields...

 
 

bug #41480: image package :normxcorr2 yields different result from matlab

Submitter:  None
Submitted:  Thu 06 Feb 2014 01:00:01 PM UTC
   
 
Category:  Octave Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Fixed Assigned to:  None
Originator Name:  Benjamin Eltzner Originator Email:  -email is unavailable-
Open/Closed:  * Closed Release:  * other
Operating System:  * GNU/Linux Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Mon 17 Mar 2014 11:21:40 PM UTC, comment #7: 

I have pushed that change to the image package:

https://sourceforge.net/p/octave/image/ci/e9c18bff13be86a0d067969c2a3dcfc405edb0b2/

I have signed that commit with your name and email. As per the emails we changed in private, I then made some further modifications to make it work with N dimensional images and follow Octave coding guidelines, expanded documentation a bit, and added tests.

https://sourceforge.net/p/octave/image/ci/0ed283edee13a5c562b51521a457d5d996fcf022/

For future reference, there's some machine precision error that creeps in, so even if the template is within the image, the normalized cross correlation may not have any 1.


total = 0;
for i=1:100
  a = rand (10);
  c = normxcorr2 (a(5:7,5:7), a);
  if (c(7,7) == 1)
    total++;
  endif
endfor


The condition there will fail around half of the times. However, I asked someone to test this in Matlab and they're not doing any better than us here.

Carnë Draug <carandraug>
Group Member
Sat 08 Mar 2014 12:16:18 AM UTC, comment #6: 

This is a reminding poke I was encouraged to issue. :-)

Anonymous
Sat 15 Feb 2014 11:01:02 PM UTC, comment #5: 

I finally got down to adjusting the tests. The bolstered up file is appended.

There is a remaining problem of principle: How to behave at the boundaries? Matlab is not a role model here, as it fails
normxcorr2(tmplt,-img) == -normxcorr2(tmplt,img)

The "correct" behaviour would be to only consider the overlapping parts of template and image and only subtract the differences of these overlapping parts in all three places. However, I could not find a clever way to achieve this without interpreted loops, which would be unacceptable. I went for the next-to-ideal solution from my point of view, which consists in centring the whole image (line 39 in the appended file) which makes sure that images that differ only by a constant offset yield the same normalized cross correlation with the same template.

I hope you find my reasoning acceptable although the result is that in some cases the function will yield different results than matlab near the boundary (for example, my version ensures
normxcorr2(tmplt,-img) == -normxcorr2(tmplt,img) ).

Also note that I have the function issue a warning, if the template is larger than the image (as this most likely happens by mistake). I hope this is acceptable for Octave.

(file #30562)

Anonymous
Fri 07 Feb 2014 01:40:03 PM UTC, comment #4: 

The deviation is not simply a matter of scaling. The normalized cross correlation used in matlab is as defined in this article, formula (2):

http://scribblethink.org/Work/nvisionInterface/nip.pdf

This means, they use "centered 2nd moments" whereas the current implementation in Octave uses "uncentered 2nd moments". Because the cross correlation itself is given by the "uncentered mixed 2nd moment", the correlation coefficient (or normalized cross correlation) is not simply given by a scaled cross correlation. I suppose that the nomenclature creating the false impression that these two quantities were related more closely is rather unfortunate.

(I will have a look at the tests when I have some more time.)

Anonymous
Fri 07 Feb 2014 12:56:58 PM UTC, comment #3: 

I was aware that normxcorr2 was returning different values than Matlab's but my understanding was that this was a matter of different methods to normalize. Is this correct?

I am very interested in having a Matlab compatible version in the image package. However, could you please add some minimum input check and test blocks like what already exists in xcorr2? test blocks are the %! at the bottom of the file.

Finally, the copyright of the whole thing will be assign to you only, since it's no longer based on the work done in xcorr2.

Carnë Draug <carandraug>
Group Member
Thu 06 Feb 2014 03:59:12 PM UTC, comment #2: 

Originally, I thought, that xcorr2 was wrong, because it calculates (upcoming abuse of mathematical notation) <ab> and not (<ab> - <a><b>) as I expected. However, as Matlab does the same, it turns out I was mistaken. (So you actually understood me correctly and I was wrong then.)

normxcorr2 in Matlab calculates
(<ab> - <a><b>) / sqrt( (<a^2> - <a>^2)(<b^2> - <b>^2) ).
xcorr2(.,.,"coeff") in Octave currently calculates
<ab> / sqrt( <a^2><b^2> ).
(Again, mind the abuse of notation.)

Anonymous
Thu 06 Feb 2014 02:01:08 PM UTC, comment #1: 

Thanks for reporting and clarifying your bug report over what you had posted to the mailing list. On the list it seemed like you were suggesting that xcorr2 is wrong, but perhaps it's the normxcorr2 function in the image package that needs tweaking.

As Carnë said on the mailing list, the xcorr2 function in Matlab has no options, those are Octave extensions to have feature parity with the xcorr function.

Perhaps this bug should be addressed by changing normxcorr2, and leaving xcorr2 as it is now. If xcorr2 (..., "coeff") is equivalent to xcorr (..., "coeff"), then it should be normxcorr2 that is fixed to be Matlab compatible if that's what's happening here.

Mike Miller <mtmiller>
Group Member
Thu 06 Feb 2014 01:00:01 PM UTC, original submission:  

In Octave, normxcorr2(b,a) = xcorr2(a,b,"coeff") yields different results from the corresponding matlab function.

Example:


I1 = [17  24   1   8  15
      23   5   7  14  16
       4   6  13  20  22
      10  12  19  21   3
      11  18  25   2   9];

 I2 = [8   1   6
       3   5   7
       4   9   2];


Octave:


>>> normxcorr2(I2,I1)
ans =

   0.11847   0.40482   0.57568   0.28310   0.36871   0.58190   0.23694
   0.34173   0.73907   0.50847   0.47886   0.70345   0.65064   0.29440
   0.55586   0.55445   0.58357   0.86717   0.80696   0.70386   0.48815
   0.43382   0.46527   0.86184   0.85369   0.88917   0.57327   0.44587
   0.44634   0.67240   0.80942   0.89965   0.67134   0.54880   0.54640
   0.54589   0.59350   0.72946   0.58994   0.51489   0.56853   0.31844
   0.35541   0.33415   0.46358   0.34730   0.56910   0.16062   0.47388

>>> xcorr2(I1,I2,"coeff")
ans =

   0.11847   0.40482   0.57568   0.28310   0.36871   0.58190   0.23694
   0.34173   0.73907   0.50847   0.47886   0.70345   0.65064   0.29440
   0.55586   0.55445   0.58357   0.86717   0.80696   0.70386   0.48815
   0.43382   0.46527   0.86184   0.85369   0.88917   0.57327   0.44587
   0.44634   0.67240   0.80942   0.89965   0.67134   0.54880   0.54640
   0.54589   0.59350   0.72946   0.58994   0.51489   0.56853   0.31844
   0.35541   0.33415   0.46358   0.34730   0.56910   0.16062   0.47388


matlab:


>> normxcorr2(I2,I1)

ans =

   -0.4108   -0.0198    0.3791   -0.2491   -0.1202    0.4424   -0.1369
   -0.1786    0.5409   -0.2540   -0.2876    0.1927    0.2119   -0.3070
    0.2647   -0.1667   -0.5097    0.4875    0.0346    0.0207   -0.0455
    0.0058   -0.4321    0.3851    0.2236    0.3851   -0.3321    0.0054
   -0.0898    0.0285    0.0346    0.4875   -0.5097   -0.1686    0.3119
    0.3150    0.0516    0.1444   -0.2254   -0.2513    0.3038   -0.1351
    0.1369   -0.1790   -0.0662   -0.2105    0.4124   -0.4579    0.4108



Appended to this bug report is a function, that yields:


>>> xcorr2coeff_alt(I1,I2)
ans =

 Columns 1 through 6:

  -0.4107919  -0.0198289   0.3790535  -0.2491009  -0.1202259   0.4424397
  -0.1785776   0.5409279  -0.2539863  -0.2875655   0.1926779   0.2119488
   0.2646599  -0.1666714  -0.5097419   0.4874667   0.0345582   0.0207020
   0.0058150  -0.4320922   0.3850770   0.2236068   0.3850770  -0.3320513
  -0.0897610   0.0285326   0.0345582   0.4874667  -0.5097419  -0.1685608
   0.3149997   0.0516398   0.1443996  -0.2253609  -0.2513123   0.3038059
   0.1369306  -0.1790197  -0.0661733  -0.2105287   0.4124105  -0.4578508

 Column 7:

  -0.1369306
  -0.3069852
  -0.0454723
   0.0054447
   0.3119203
  -0.1350676
   0.4107919


which is, up to rounding, the same as the matlab function yields (where arguments are interchanged, as the normxcorr2-wrapper interchanges arguments as stated and illustrated above). I would be glad if the corresponding 8 lines of code would be integrated in Octave (and I appologize for the poor coding style).

Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #30562:  normxcorr2.m added by None (3KiB - text/x-objcsrc)
file #30470:  xcorr2coeff_alt.m added by None (1KiB - text/x-objcsrc)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by carandraug (Benjamin Eltzner - Original person that reported the bug)
  • -email is unavailable- added by mtmiller (Posted a comment)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 11 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2014-03-17 carandraug StatusNone Fixed
        Open/ClosedOpen Closed
    2014-02-15 None Attached File- Added normxcorr2.m, #30562
    2014-02-06 carandraug Originator Name Benjamin Eltzner
        Originator Email -email is unavailable-
        Carbon-Copy- Added -email is unavailable-
    2014-02-06 mtmiller CategoryNone Octave Package
        Item GroupNone Incorrect Result
        Release3.6.4 other
        Summarynormxcorr2 yields different result from matlab image package :normxcorr2 yields different result from matlab
    2014-02-06 None Attached File- Added xcorr2coeff_alt.m, #30470

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code