bugGNU Octave - Bugs: bug #46160, image package: normxcorr2 returns...

 
 

bug #46160: image package: normxcorr2 returns complex values sometimes

Submitter:  Hartmut <hardy>
Submitted:  Thu 08 Oct 2015 08:00:42 PM UTC
   
 
Category:  Octave Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Inaccurate Result
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * other Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Mon 08 Feb 2016 12:21:57 AM UTC, comment #7: 

Thank you. I have pushed your patch http://hg.code.sf.net/p/octave/image/rev/5820f8878176

Carnë Draug <carandraug>
Group Member
Mon 25 Jan 2016 07:12:15 PM UTC, comment #6: 

Here is a small PATCH that fixes this issue and also incorporates the discussed improvement of the help string.

(file #36163)

Hartmut <hardy>
Wed 21 Oct 2015 07:47:51 PM UTC, comment #5: 

@Hartmut  (comment #3):
I agree, one of your checks should be added, to avoid negative
number due to machine precision.

Regarding comment #4:  "Returns the the cross-correlation": only
one "the" is needed.

Avinoam Kalma <avinoam>
Group Member
Wed 21 Oct 2015 06:43:23 PM UTC, comment #4: 

If someone fixes this, could you please also change the first sentence in the doc string. It reads currently:


     Returns the the cross-correlation coefficient of matrices TEMPLATE
     and IMG, a matrix of the same size as IMG with values ranging
     between -1 and 1.


This is incorrect, since the resulting matrix is BIGGER than the image, because the image is padded. This behavior is totally fine and Matlab compatible, just the doc string is misleading here. How about this one instead:


     Returns the the cross-correlation coefficient of matrices TEMPLATE
     and IMG, a matrix of (roughly) the same size as IMG with values ranging
     between -1 and 1.

    [... the rest of the doc string ... somewhere at the end finally:]

    The size of the cross-correlation matrix is slightly bigger than IMG
    because the input image is padded during the process.


Hartmut <hardy>
Wed 21 Oct 2015 06:34:48 PM UTC, comment #3: 

I made up my mind, since Matlab probably needs to do the same here. What do you think about a small patch like this:


b(find(b < 0)) = 0;


or even only


b(b < 0) = 0;


(@Avoniam: I think checking for b>-10*eps is unnecessary, since b should never be negative normally, the only way it can get negative is machine precision.)

We should do this right after the line that does the difference (currently after line 64). I don't know which version is faster, or wich one better supports Nd images. But I would support to include one ore the other version into normxcorr2.m  to fix this issue.

Hartmut <hardy>
Sun 11 Oct 2015 07:23:25 PM UTC, comment #2: 

I think that I don't like the idea of eliminating small negative values with a find command, as you suggested, because it costs calculation time without really doing something. Couldn't we try to avoid the numerically instable subtraction in line 64 at all?

Why must there be a minus sign at all in line 64? For 2d images, shouldn't it be enough to calculate b in the same way that a is calculated one line below? Something similar to this:


 b = sumsq (b(:)) .* some_size_term;


But since I do not fully understand what the original term does with Nd images, I hesitate to suggest an easy fix, here.

But if there is no more elegant way to solve this, I should probably accept the find command instead of keeping the current behavior :(

Hartmut <hardy>
Fri 09 Oct 2015 06:51:32 AM UTC, comment #1: 

In this examples, after line 64 b(77) = -4*eps, and than
in line 66 sqrt(a*b) is computed, so it become complex.

What about inserting something like


 b(find(b > -10*eps & b < 0)) = 0;


after line 64. It will zero negative small terms of b.

Avinoam Kalma <avinoam>
Group Member
Thu 08 Oct 2015 08:00:42 PM UTC, original submission:  

This happens with the latest Octave (version 4.0.0) and the latest image package (version 2.4.1). Here is a little script to show the behavior:


clear;
a =  [ 252  168   50   1    59;
       114    0    0   0    0]./255;
b = [1  171  255  255  255  255  240   71  131  254   255  255  255;
    0       109  254  255  255  233   59    0  131  254  255   255  255;
   76       13  195  253  194   34    0   19  217  255  255   255  255;
  110       0    0    0    0    0    3  181  255  255  255  255   255;
  153       0    0    0    0    2  154  254  255  255  255  255   255]./255;
c = normxcorr2(a,b);
max(imag(c(:)))


As you can see, there is a small imaginary part (~1e-8 ... 1e-9) in the result c in this case. Unfortunatelly, this unexpected complex valued result can spoil the following calculations :(

The source of this behavior seems to be somewhere in line 64 of normxcorr2.m

  b = convn (b.^2, a1) .- convn (b, a1).^2 ./ (prod (size (a)));


For the above listed sample values, the result of this code line becomes slightly negative (~ -eps), and in the following code lines the square root of this negative number will be returned (~ sqrt(-eps)).

Unfortunatelly, I don't understand good enough what this line 64 does. It looks fancy to me, probably because it can also deal with ND-images. Could someone with more insight maybe fix this?

Hartmut <hardy>

 

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

Attach Files:
   
   
Comment:
   

Attached Files

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by avinoam (Posted a comment)
  • -email is unavailable- added by hardy (Submitted the item)
  •  

    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 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2016-02-08 carandraug StatusNone Fixed
        Open/ClosedOpen Closed
        Release4.0.0 other
    2016-01-25 hardy Attached File- Added normxcorr2_nonimaginary.patch, #36163

    Back to the top

    Powered by Savane 3.13-d3ae.
    Corresponding source code