bugGNU Octave - Bugs: bug #34893, conv2 produces different results...

 
 

bug #34893: conv2 produces different results for shape 'valid' depending on the orientation of matrix B

Submitter:  Nitzan Arazi <nitnit>
Submitted:  Thu 24 Nov 2011 09:11:38 PM UTC
   
 
Category:  None Severity:  4 - Important
Priority:  6 Item Group:  Regression
Status:  Fixed Assigned to:  None
Originator Name:  Nitzan Arazi Open/Closed:  * Closed
Release:  * 3.6.1 Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Sun 13 May 2012 04:20:14 PM UTC, comment #17: 

This is about to go into a stable release... I'm closing this report, and I hope I got it right.

Jordi Gutiérrez Hermoso <jordigh>
Group Member
Thu 03 May 2012 09:34:32 PM UTC, comment #16: 

I have pushed the following to the stable branch. I added a test too:

http://hg.savannah.gnu.org/hgweb/octave/rev/ad1d7a53b1ca

This seems to fix the problem for me. Since this is for the stable branch and I'm unsure of this code, I would appreciate independent confirmation before closing this bug report.

Jordi Gutiérrez Hermoso <jordigh>
Group Member
Sun 22 Apr 2012 03:11:47 AM UTC, comment #15: 

I'd like to add a little bit more to my previous comment.
Both algorithms, scattering and gathering, are right ways to compute convolutions, and if you want to make the results exactly same, you may need to convert either one to use the same algorithm with the other one, as computing floating-point numbers actually depends on the order of computation.
Previously, I think the order of two different computation luckily matched and produced the same results, as *conv2i computed convolution in a wrong (reversed) way.

Thanks,
Sunghyun

Sunghyun Cho <sodomau>
Sun 22 Apr 2012 02:54:42 AM UTC, comment #14: 


Hi.
I took a look a little bit more.
It seems like *conv2o and *conv2i use different algorithms for computing convolution.
*conv2o uses scattering, and *conv2i uses gathering, and this can result in small difference in computation of floating-point numbers.
Hope this helps.

Sunghyun Cho <sodomau>
Sat 21 Apr 2012 03:17:35 PM UTC, comment #13: 

After some analysis, it appears that Sunghyun Cho's patch is not correct, since it breaks this case:


      x = rand(100);
      y = ones(5);
      A = conv2(x,y)(5:end-4,5:end-4);
      B = conv2(x,y,"valid");


With the patch, A and B are only approximately equal. Without it, they're exactly equal.

However, I think I'm slowly starting to understand the convoluted (haha) conv2 code. I will attempt another fix, but probably not for the 3.6.2 release.

Jordi Gutiérrez Hermoso <jordigh>
Group Member
Tue 17 Apr 2012 06:54:38 PM UTC, comment #12: 

Awesome, thanks Sunghyun. Your fix works. It needs to also be applied to all other *conv2.f files. I also need to write some tests for this bug (actually, we should have probably written tests even before we had a fix for it). Attached is your fix applied to all other Fortran functions that need it. I need to hurry up to get this into the 3.6.2 bugfix release, which is due in a day or two.

(file #25673)

Jordi Gutiérrez Hermoso <jordigh>
Group Member
Tue 17 Apr 2012 11:54:41 AM UTC, comment #11: 

As mentioned on the mailing list I attach a changeset of a patch by Sunghyun Cho <sodomau@gmail.com>. After making the change make test reports no changes and the following cases (which failed before) now succeed:


> conv([1:5].',[1:2].','valid')
ans =

    4
    7
   10
   13

> conv([1:5],[1:2],'valid')
ans =

    4    7   10   13

> conv2([1:5;1:5],[1:2],'valid')
ans =

    4    7   10   13
    4    7   10   13

> conv2([1:5;1:5].',[1:2].','same')
ans =

    4    4
    7    7
   10   10
   13   13
   10   10

> conv2([1:5;1:5],[1:2],'same')
ans =

    4    7   10   13   10
    4    7   10   13   10


(file #25669)

Carnë Draug <carandraug>
Group Member
Tue 13 Mar 2012 12:52:35 PM UTC, comment #10: 

Oops, sorry, I posted to the wrong bug report.

Jordi Gutiérrez Hermoso <jordigh>
Group Member
Tue 13 Mar 2012 12:48:54 PM UTC, comment #9: 

Thanks Marco. This is much more convenient for me to analyse and apply.

Attached is a modified version of your patch. I made the following changes:

1) The commit message has a one-line description including the number of the bug you're squashing.

2) Individual files you touched get their changes separately enumerated. If there a particular C or C++ function you changed, the general format is

  • file.cc (class1::function1): Made change foo. (class2::function2): Made change bar.


I omitted the parenthetical function names here because your changes aren't inside any C or C++ function.

3) Don't use norm or max(abs(...)) or similar for the assert function The assert function already has a 3-argument calling form for testing both absolute and relative error, and this form produces a more informative diagnostic when it fails.


I hope it's clear that these are improvements. The format of the commit message is important. In source tarballs, we generate changelogs from the commit messages using the "hg log --style changelog" command, and so the style of the commit messages has to match accordingly.

If you agree that these changes are correct, I will push my version of the patch. When you pull from Savannah, it will appear to you that you have a duplicate patch in your local repository, because you will have both your patch and my version.
I will explain later how to handle this situation.

(file #25355)

Jordi Gutiérrez Hermoso <jordigh>
Group Member
Sun 26 Feb 2012 04:45:13 PM UTC, comment #8: 

I'm raising the priority of this bug to Important so that it will be a blocker for the future 3.8 release.  Octave doesn't seem to be using the Fortran library correctly when given the 'valid' argument to conv2.

Rik <rik5>
Group administrator
Thu 09 Feb 2012 06:43:20 AM UTC, comment #7: 

Okay, I've fixed the conv() on the development branch to support 'valid'.  The changeset is here (http://hg.savannah.gnu.org/hgweb/octave/rev/12c70d00c04e).

I'm re-titling the bug report to reflect the last remaining issue.

Rik <rik5>
Group administrator
Wed 08 Feb 2012 06:50:15 AM UTC, comment #6: 

On Matlab 2011b:

conv (1:2, 1:5, 'valid')

ans =

   Empty matrix: 1-by-0

conv (1:5, 1:3, 'valid')

ans =

    10    16    22

Nitzan Arazi <nitnit>
Sun 05 Feb 2012 11:28:51 PM UTC, comment #5: 

With a little help I can finish off issue 1.

Can someone run the following in Matlab:


conv (1:2, 1:5, 'valid')
conv (1:5, 1:3, 'valid')



Rik <rik5>
Group administrator
Tue 17 Jan 2012 10:29:32 PM UTC, comment #4: 

I have confirmed these results on the latest available Mercurial tip.  This bug report is for 3 different issues:

1) conv() does not support the shape 'valid'
2) conv2 produces different results for shape 'valid' depending on the orientation of matrix B.
3) conv2 picks the wrong part of the convolution for shape 'same'

I have already coded a patch for item 3.  Alas, it will probably not make it in to release 3.6.0.

Issue 2 is caused by some deep problem involving how Octave is calling Fortran code.  I'm not touching that problem for now.

For issue 1, I would like to see the Matlab's interpretation of the following two commands.  If the original reporter, or someone else, can supply that then I can finish off issue 1 as well.


conv (1:2, 1:5, 'valid')
conv (1:5, 1:3, 'valid')



Rik <rik5>
Group administrator
Thu 24 Nov 2011 11:56:58 PM UTC, comment #3: 

Actually, conv2.cc is in the DLD-FUNCTIONS and
it does provide 'valid'.  conv.m is in scripts/polynomical
and does not handle 'valid'.

The current distribution gives:
octave:1> conv([1:5].',[1:2].','valid')
error: conv: SHAPE argument must be "full" or "same"
error: called from:
error:   /d/src/octave/hg/octave/scripts/polynomial/conv.m at line 55, column 5

but it also gives:
octave:1> conv2([1:5;1:5],[1:2],'valid')
ans =

    5    8   11   14
    5    8   11   14

octave:2>

But, it would be good to start from the above results,
not 3.4.2 or 3 which
were used in reporting this problem.

Michael Godfrey <godfrey>
Group Member
Thu 24 Nov 2011 11:43:55 PM UTC, comment #2: 

The first step should be to implement 'valid' which
is not currently provided.  This should be considered
as a Matlab compatibility requirement.

Michael Godfrey <godfrey>
Group Member
Thu 24 Nov 2011 09:18:09 PM UTC, comment #1: 

I think this is pretty easy to patch. It's just an m-script. Do you want to try it yourself? It could be good for your first patch.

Jordi Gutiérrez Hermoso <jordigh>
Group Member
Thu 24 Nov 2011 09:11:38 PM UTC, original submission:  

I have encountered the following erroneous cases with conv and conv2 with Mingw builds versions 3.4.2 and 3.4.3.

Case A:

conv([1:5].',[1:2].','valid')

ans =

    1
    4
    7
   10
   13
   10

while the expected output is:

ans =
    4
    7
   10
   13

Similarily

conv([1:5],[1:2],'valid')

ans =

    1    4    7   10   13   10

while the expected output is:

ans =

    4    7   10   13

Case B:

conv2([1:5;1:5],[1:2],'valid')

ans =

    5    8   11   14
    5    8   11   14

while the expected output is:

ans =

    4    7   10   13
    4    7   10   13

conv2([1:5;1:5].',[1:2].','valid')
output is OK.

Case C:

conv2([1:5;1:5].',[1:2].','same') % second input var has even number of elements

ans =

    1    1
    4    4
    7    7
   10   10
   13   13

while the expected output (as output by m****b) is

ans =

    4    4
    7    7
   10   10
   13   13
   10   10

Similarily


conv2([1:5;1:5],[1:2],'same')

ans =

    1    4    7   10   13
    1    4    7   10   13

while the expected output is:

ans =

    4    7   10   13   10
    4    7   10   13   10

If second input var has odd number of elements, output is OK.

Note: m****b docs defines indices of the second input var as
as floor(([mb nb]+1)/2)
where mb nb are the col and row dimensions of the second input var.

Nitzan Arazi <nitnit>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #25673:  fix-conv2.diff added by jordigh (3KiB - text/x-diff)
file #25669:  conv2.diff added by carandraug (749B - text/x-patch)
file #25355:  logm-2.diff added by jordigh (3KiB - text/x-diff)

 

Depends on the following items: None found

Digest:
   bug dependencies.

 

Carbon-Copy List
  • -email is unavailable- added by sodomau (Posted a comment)
  • -email is unavailable- added by carandraug (Updated the item)
  • -email is unavailable- added by carandraug (Sunghyun Cho posted a fix on the mailing list for this bug)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by godfrey (Posted a comment)
  • -email is unavailable- added by jordigh (Posted a comment)
  • -email is unavailable- added by nitnit (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 14 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2013-03-28 mtmiller Dependencies- bugs #38605 is dependent
    2012-05-13 jordigh StatusConfirmed Fixed
        Open/ClosedOpen Closed
        Release3.4.3 3.6.1
    2012-04-17 jordigh Attached File- Added fix-conv2.diff, #25673
    2012-04-17 jordigh Item GroupIncorrect Result Regression
    2012-04-17 carandraug Attached File- Added conv2.diff, #25669
        Carbon-Copy- Added -email is unavailable-
    2012-03-13 jordigh Attached File- Added logm-2.diff, #25355
    2012-02-26 rik5 Severity3 - Normal 4 - Important
    2012-02-09 rik5 Priority5 - Normal 6
        Operating SystemMicrosoft Windows Any
        SummaryUnexpected and inconsistent conv/conv2 results conv2 produces different results for shape 'valid' depending on the orientation of matrix B
    2012-01-17 rik5 StatusNone Confirmed

    Back to the top

    Powered by Savane 3.13-d3ae.
    Corresponding source code