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

 
 

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

Submitted by:  None
Submitted on:  Thu 06 Feb 2014 01:00:01 PM UTC  
 
Category: Octave Forge PackageSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Incorrect Result
Status: FixedAssigned to: None
Originator Name: Benjamin EltznerOriginator Email: -unavailable-
Open/Closed: ClosedRelease: other
Operating System: GNU/Linux

Add a New Comment (Rich MarkupRich Markup):
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission 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.

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>
Project 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>
Project 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>
Project 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:

Octave:

matlab:

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

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 File(s):
   
   
Comment:
   

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

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 11 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Mon 17 Mar 2014 11:21:40 PM UTCcarandraugStatusNone=>Fixed
      Open/ClosedOpen=>Closed
    Sat 15 Feb 2014 11:01:02 PM UTCNoneAttached File-=>Added normxcorr2.m, #30562
    Thu 06 Feb 2014 02:11:49 PM UTCcarandraugOriginator Name=>Benjamin Eltzner
      Originator Email=>-unavailable-
      Carbon-Copy-=>Added -unavailable-
    Thu 06 Feb 2014 02:01:08 PM UTCmtmillerCategoryNone=>Octave Forge Package
      Item GroupNone=>Incorrect Result
      Release3.6.4=>other
      Summarynormxcorr2 yields different result from matlab=>image package :normxcorr2 yields different result from matlab
    Thu 06 Feb 2014 01:00:01 PM UTCNoneAttached File-=>Added xcorr2coeff_alt.m, #30470

    Back to the top


    Powered by Savane 3.1-cleanup