Octave 4.0.3: normxcorr2 producing unexpected result

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Octave 4.0.3: normxcorr2 producing unexpected result

Manuel Reiter
Hi,

I'm running Octave 4.0.3 from Debian jessie backports on a Raspberry Pi 3. Im currently following a computer vision course on Udacity and came across the following unexpected behaviour of normxcorr2 (from the image package):

---snip

>> s = [-1 0 0 1 1 1 0 -1 -1 0 1 0 0 -1];
>> t = [1 1 0];
>> x = normxcorr2(t,s)
x =

 Columns 1 through 10:

   1.00000  -0.50000  -0.50000  -1.00000  -0.50000       Inf   1.00000   0.86603   0.50000  -1.00000

 Columns 11 through 16:

  -0.86603   0.50000   0.50000   1.00000  -0.50000  -0.50000

---snip

I would have expected a vector of length 18 with a max value of 1.0 at position 7 where the template actually occurs in the pattern. I also don't understand why there's a value of 'Inf' in the result, while the documentation states that values should range from -1 to 1. I have the feeling that I'm missing something obvious here but I really fail to see what that might be. Any help or hints greatly appreciated. Thanks in advance!

Greetings,

  Manuel
_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Octave 4.0.3: normxcorr2 producing unexpected result

Hartmut
Hey Manual,

it is nice to hear that the Octave image toolbox is being used for a computer vision course on Udacity.

Your image input s is 14 elements long, and your template t is 3 elements long. So the result of normxcorr2 has a correct length of 14+3-1=16 elements. This is because of the padding done in the underlying convn function [1].

The maximum correlation value is to be expected at position 6+1 then, when the center element of the template fits the pattern in the image (padded by 1 element on both sides). But there are also other positions with maximum correlation (of value 1), because the image is normalized before doing the correlation.

The inf value in the output occurs at a position where the variance of the corresponding image part becomes zero, in your case this is [1 1 1]. This result might be expected because of the definition of the "normalized cross correlation", but Matlab deals with this special case by returning a zero value instead [2]. I have therefore filed a bug report for this [3]. As a quick fix you could easily change the code of your normxcorr2.m file for now, as described there.

I hope this helps.

    Hartmut


[1] http://de.mathworks.com/help/matlab/ref/convn.html
[2] http://de.mathworks.com/help/images/ref/normxcorr2.html
[3] https://savannah.gnu.org/bugs/index.php?50122
oli
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Octave 4.0.3: normxcorr2 producing unexpected result

oli
I'm having the same issue. The expected values for the correlation are:



But I am getting this as well:

 Columns 1 through 8:

   1.00000  -0.50000  -0.50000  -1.00000  -0.50000       Inf   1.00000   0.86603

 Columns 9 through 16:

   0.50000  -1.00000  -0.86603   0.50000   0.50000   1.00000  -0.50000  -0.50000

I used the workaround mentioned here to replace Inf by 0.


 Columns 1 through 8:

   1.00000  -0.50000  -0.50000  -1.00000  -0.50000  0.00000   1.00000   0.86603

 Columns 9 through 16:

   0.50000  -1.00000  -0.86603   0.50000   0.50000   1.00000  -0.50000  -0.50000

According to this output, we can see there are maximums at indexes 1, 7 and 14. Strangely, `[val index] = max(c)` returns index 7 instead of 1 or 14.

I really feel there is a bug somewhere....
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Octave 4.0.3: normxcorr2 producing unexpected result

Kire Pudsje
 Columns 1 through 8:

   1.00000  -0.50000  -0.50000  -1.00000  -0.50000  0.00000   1.00000
0.86603

According to this output, we can see there are maximums at indexes 1, 7 and
14. Strangely, `[val index] = max(c)` returns index 7 instead of 1 or 14.

I really feel there is a bug somewhere....

Remember that we are dealing with floating points here, so 1.000.... != 1.000.....
If we subtract eg x(7) from x(1) we get
ans =  -1.1102e-016


_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Octave 4.0.3: normxcorr2 producing unexpected result

Hartmut
In reply to this post by oli
Hey Oli,

the result of Octave's normxcorr2 (when using the previously mentioned patch in [1]) is fully Matlab compatible, except for the outer two numbers on each side. Where does your "expected result" come from? The values of normalized correlation coefficients should stay between -1 and 1.

The remaining issue seems to only concern border pixels, you can follow the discussion under [2] if you like.

Regarding the result max that you mentioned: I think this should be only due to (inavoidable) numerical inaccuracies. By the way, the Matlab result of your max command is the very same as Octave's for your example.

So I can't "feel" a major bug here, any more. Only the (minor problem) of the border pixels remains, and it is taken care of in [2].

So, have fun with Octave in your Udacity course. (By the way, your Udacity link is login protected, I cannot read it.)

     Hartmut


[1] https://savannah.gnu.org/bugs/?50122
[2] https://savannah.gnu.org/bugs/?50151
oli
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Octave 4.0.3: normxcorr2 producing unexpected result

oli
Thanks Hartmut,

The "expected result" comes from this video taken from the Computer Vision course on Udacity: https://youtu.be/9hN3MeCavP4?t=79

Any idea what might have produced this result?

Only the (minor problem) of the border pixels remains, and it is taken care of in [2]. 

Great.


On Tue, Mar 28, 2017 at 12:30 PM, Hartmut [via Octave] <[hidden email]> wrote:
Hey Oli,

the result of Octave's normxcorr2 (when using the previously mentioned patch in [1]) is fully Matlab compatible, except for the outer two numbers on each side. Where does your "expected result" come from? The values of normalized correlation coefficients should stay between -1 and 1.

The remaining issue seems to only concern border pixels, you can follow the discussion under [2] if you like.

Regarding the result max that you mentioned: I think this should be only due to (inavoidable) numerical inaccuracies. By the way, the Matlab result of your max command is the very same as Octave's for your example.

So I can't "feel" a major bug here, any more. Only the (minor problem) of the border pixels remains, and it is taken care of in [2].

So, have fun with Octave in your Udacity course. (By the way, your Udacity link is login protected, I cannot read it.)

     Hartmut


[1] https://savannah.gnu.org/bugs/?50122
[2] https://savannah.gnu.org/bugs/?50151


If you reply to this email, your message will be added to the discussion below:
http://octave.1599824.n4.nabble.com/Octave-4-0-3-normxcorr2-producing-unexpected-result-tp4681543p4682651.html
To unsubscribe from Octave 4.0.3: normxcorr2 producing unexpected result, click here.
NAML



--
- Oli

Oli Lalonde
http://www.syskall.com <-- connect with me!
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Octave 4.0.3: normxcorr2 producing unexpected result

Hartmut
Hey Oli,

I think the author in this video (and Udacity course) is just using a slightly outdated version of the Octave image package. Before image package version 4.2.0 (released in April 2015) the results of normxcorr2 were buggy and Matlab incompatible  (and not staying in the interval between -1 and 1). For details of this change see [1].

    Hartmut

[1] https://savannah.gnu.org/bugs/?41480
oli
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Octave 4.0.3: normxcorr2 producing unexpected result

oli
Ok thanks! I'll link to this conversation in the course forum in case anyone else is wondering.

On Wed, Mar 29, 2017 at 12:02 PM, Hartmut [via Octave] <[hidden email]> wrote:
Hey Oli,

I think the author in this video (and Udacity course) is just using a slightly outdated version of the Octave image package. Before image package version 4.2.0 (released in April 2015) the results of normxcorr2 were buggy and Matlab incompatible  (and not staying in the interval between -1 and 1). For details of this change see [1].

    Hartmut

[1] https://savannah.gnu.org/bugs/?41480


If you reply to this email, your message will be added to the discussion below:
http://octave.1599824.n4.nabble.com/Octave-4-0-3-normxcorr2-producing-unexpected-result-tp4681543p4682670.html
To unsubscribe from Octave 4.0.3: normxcorr2 producing unexpected result, click here.
NAML



--
- Oli

Oli Lalonde
http://www.syskall.com <-- connect with me!
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Octave 4.0.3: normxcorr2 producing unexpected result

supr8sung
In reply to this post by Manuel Reiter
Actually I'm also facing the same problem so can you please help in figuring this out.
Udacity is using
function index=find_template_1D(t,s)
      c=normxcorr2(t,s);
      [maxValue rawIndex]=max(c);
      index=rawIndex-size(t,2)+1;
endfunction

but still i'm getting index value as 4
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Octave 4.0.3: normxcorr2 producing unexpected result

Hartmut
This result looks mostly alright to me. For details please see the above discussion. Here follows a shorter summary.

Octave code:

clear
pkg load image                        % using image 2.6.1 release
s = [-1 0 0 1 1 1 0 -1 -1 0 1 0 0 -1]
t = [1 1 0]
x = normxcorr2(t,s);
x(~isfinite(x))=0                       % to fix inf values (bug 50151)
[maxVal maxRawIndex] = max(x)

The resulting output is (slightly rounded):
x = 1 -0.5 -0.5 -1 -0.5 0 1 0.87 0.5 -1 -0.87 0.5 0.5 1 -0.5 -0.5
maxVal = 1
maxRawIndex = 7

The maxRawIndex could equally well be 1 or 14 instead of this 7. Those are all the positions where x has the value 1 (the position 7 seems to be closest to 1 because of machine precision).

The index 7 position corresponds to "1 1 0" in s, and the index 14 position corresponds to "0 0 -1" in s. Both have the same maximum normalized cross correlation to t. The index position 1 is just an artifact of padding the borders (those padded borders are also currently not perfectly Matlab compatible).

This raw index can the be transferred to the index in the original array s if you like. The way you do this in the function find_template_1D seems slightly wrong to me. You might do something like "index = rawIndex-(length(t)-1)/2". Then you will get the center element in s that corresponds to your matching substring. This value would then be 6 and would properly correspond to the part "1 1 0" in s.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Octave 4.0.3: normxcorr2 producing unexpected result

supr8sung
I think this won't be giving us the correct value for t=[1 1 1]........


Supreet Singh

On Tue, Apr 18, 2017 at 11:34 PM, Hartmut [via Octave] <[hidden email]> wrote:
This result looks mostly alright to me. For details please see the above discussion. Here follows a shorter summary.

Octave code:

clear
pkg load image                        % using image 2.6.1 release
s = [-1 0 0 1 1 1 0 -1 -1 0 1 0 0 -1]
t = [1 1 0]
x = normxcorr2(t,s);
x(~isfinite(x))=0                       % to fix inf values (bug 50151)
[maxVal maxRawIndex] = max(x)

The resulting output is (slightly rounded):
x = 1 -0.5 -0.5 -1 -0.5 0 1 0.87 0.5 -1 -0.87 0.5 0.5 1 -0.5 -0.5
maxVal = 1
maxRawIndex = 7

The maxRawIndex could equally well be 1 or 14 instead of this 7. Those are all the positions where x has the value 1 (the position 7 seems to be closest to 1 because of machine precision).

The index 7 position corresponds to "1 1 0" in s, and the index 14 position corresponds to "0 0 -1" in s. Both have the same maximum normalized cross correlation to t. The index position 1 is just an artifact of padding the borders (those padded borders are also currently not perfectly Matlab compatible).

This raw index can the be transferred to the index in the original array s if you like. The way you do this in the function find_template_1D seems slightly wrong to me. You might do something like "index = rawIndex-(length(t)-1)/2". Then you will get the center element in s that corresponds to your matching substring. This value would then be 6 and would properly correspond to the part "1 1 0" in s.


If you reply to this email, your message will be added to the discussion below:
http://octave.1599824.n4.nabble.com/Octave-4-0-3-normxcorr2-producing-unexpected-result-tp4681543p4682907.html
To unsubscribe from Octave 4.0.3: normxcorr2 producing unexpected result, click here.
NAML

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Octave 4.0.3: normxcorr2 producing unexpected result

Hartmut
When you use t = [1 1 1] you will get only 0s as result. And this is also correct.

Reason:The normalized cross correlation is also normalized to the standard deviation of s and t. So in places where s or t have a standard deviation of 0 (like t in your case, try std(t) ) you will get an undefined result. Matlab decided to return a 0 value is this case. For the definition of the normalized cross correlation as well as for this Matlab behavior, see [1].

If you want so search for image templates that are fully flat (i.e. with a standard deviation zero) than you should probably be using something different, but not normxcorr2. You might want to try corrcoef (in future Octave version 4.4) for your 1-D example, your just use stdfilt or rangefilt on real 2D images.

     Hartmut


[1] Matlab help page of normxcorr2:
     Defintion: https://de.mathworks.com/help/images/ref/normxcorr2.html#bvibmz_-5
     Dealing with std=0: https://de.mathworks.com/help/images/ref/normxcorr2.html#bvh5vek-3
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Octave 4.0.3: normxcorr2 producing unexpected result

supr8sung
I think this worked thanks.....


Supreet Singh

On Wed, Apr 19, 2017 at 12:30 AM, Hartmut [via Octave] <[hidden email]> wrote:
When you use t = [1 1 1] you will get only 0s as result. And this is also correct.

Reason:The normalized cross correlation is also normalized to the standard deviation of s and t. So in places where s or t have a standard deviation of 0 (like t in your case, try std(t) ) you will get an undefined result. Matlab decided to return a 0 value is this case. For the definition of the normalized cross correlation as well as for this Matlab behavior, see [1].

If you want so search for image templates that are fully flat (i.e. with a standard deviation zero) than you should probably be using something different, but not normxcorr2. You might want to try corrcoef (in future Octave version 4.4) for your 1-D example, your just use stdfilt or rangefilt on real 2D images.

     Hartmut


[1] Matlab help page of normxcorr2:
     Defintion: https://de.mathworks.com/help/images/ref/normxcorr2.html#bvibmz_-5
     Dealing with std=0: https://de.mathworks.com/help/images/ref/normxcorr2.html#bvh5vek-3


If you reply to this email, your message will be added to the discussion below:
http://octave.1599824.n4.nabble.com/Octave-4-0-3-normxcorr2-producing-unexpected-result-tp4681543p4682910.html
To unsubscribe from Octave 4.0.3: normxcorr2 producing unexpected result, click here.
NAML

Loading...