bugGNU Octave - Bugs: bug #62192, [octave forge](image) bwdist gives...

 
 

bug #62192: [octave forge](image) bwdist gives incorrect result in rare cases

Submitter:  Anders Höglund <andersh>
Submitted:  Wed 16 Mar 2022 11:13:22 AM UTC
   
 
Category:  Octave Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Wont Fix 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

Thu 18 Aug 2022 05:51:24 AM UTC, comment #8: 


Closing as "Wont Fix".
Thank you all.

Avinoam Kalma <avinoam>
Group Member
Fri 12 Aug 2022 11:29:06 AM UTC, comment #7: 

I have now pushed a change that includes both a note in the help text as an extra note in the source code that points to the more precise algorithm:

   https://hg.code.sf.net/p/octave/image/rev/d27bfddae1a4

If noone has an objection, this bug report could then be CLOSED.

Hartmut <hardy>
Mon 08 Aug 2022 06:13:47 PM UTC, comment #6: 

could also add a TODO: or FIXME: comment in the code mentioning the two algorithms and/or a link to this report if we think that achieving accuracy and matlab agreement is worth setting as an eventual goal.

Nicholas Jankowski <nrjank>
Group Member
Mon 08 Aug 2022 04:46:27 AM UTC, comment #5: 


Good idea.
Please do it.

Avinoam Kalma <avinoam>
Group Member
Sun 07 Aug 2022 12:18:38 PM UTC, comment #4: 

I think we should just add a little note to the help string of bwdist and then close this bug report, maybe a note like this:


Note: This implementation of bwdist follows the algorithm of Per-Erik Danielsson from 1980 (see source code for details). It gives fast and good results, but they can slightly differ from the theoretically correct result and from the Matlab result. Distance deviations are much smaller than a fraction of a single pixel.


We have the xtest (and its reference to this bug report) already in place, and it is unlikely that someone re-implements the Maurer algorithm for Octave soon, given that our current results are very good already.

Any objections?

Hartmut <hardy>
Wed 25 May 2022 05:04:04 AM UTC, comment #3: 

Indeed, Octave used the Algorithm proposed by Per-Erik Danielsson,

“Euclidean distance mapping”, in Computer Graphics and Image Processing, Volume 14, Issue 3, 1980, Pages 227-248,
https://doi.org/10.1016/0146-664X(80)90054-4. (https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.322.7605&rep=rep1&type=pdf),

while MATLAB uses the algorithm of C. R. Maurer, Rensheng Qi and V. Raghavan, "A linear time algorithm for computing exact Euclidean distance transforms of binary images in arbitrary dimensions," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no. 2, pp. 265-270, Feb. 2003, doi: 10.1109/TPAMI.2003.1177156.
https://ieeexplore.ieee.org/document/1177156 (paywall).
 
In the paper of  Ricardo Fabbri, Luciano Da F. Costa, Julio C. Torelli, and Odemir M. Bruno. 2008. "2D Euclidean distance transform algorithms: A comparative survey". ACM Comput. Surv. 40, 1, Article 2 (February 2008), 44 pages. DOI:https://doi.org/10.1145/1322432.1322434
(https://rfabbri.github.io/stuff/fabbri-EDT-survey-ACMCSurvFeb2008.pdf), the authors write, regarding Danielsson algorithm: “Although it is simple and efficient, it is not exact"

Meanwhile, I have added a xtest to the code: http://hg.code.sf.net/p/octave/image/rev/02de12903c73

Avinoam Kalma <avinoam>
Group Member
Wed 16 Mar 2022 05:45:32 PM UTC, comment #2: 

Matlab (current online version) also gives the correct result "57.9741" for the test code in comment #0.

Hartmut <hardy>
Wed 16 Mar 2022 05:41:09 PM UTC, comment #1: 

adding package maintainers to cc

Hartmut <hardy>
Wed 16 Mar 2022 11:13:22 AM UTC, original submission:  

Tested with Octave 6.4.0 on Ubuntu with image from repository as well as Octave 4.4.0 on Debian with image 2.10.0


pkg load image
a = zeros(200,200);
a(158,100) = 1;
a(141,141) = 1;
a(156,115) = 1;
d = bwdist(a);

d(100,100)
% Gives ans =  57.983
% Expected 57.974

sqrt((141-100)**2 + (141-100)**2)
% Gives ans =  57.983

sqrt((156-100)**2 + (115-100)**2)
% Gives ans =  57.974


bwdist finds the shortest distance from 100,100 to be to the pixel at 141,141 while the actual shortest distance is to the pixel at 156,115.

The algorithm is based on the assumption that the closest pixel can be found among the closest pixel of the surrounding eight points even though the distance might need to be recalculated.  This is not true in the discrete case as the above example illustrates.

I have no idea if there are any other algorithm that is as fast as the current one but always give correct results.  The error is fairly small so a better fix might be to add to the documentation that there might be a small error in rare cases.  As far as I am concerned, the current implementation suffices for my application.

Anders Höglund <andersh>

 

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

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by nrjank (Posted a comment)
  • -email is unavailable- added by avinoam (Posted a comment)
  • -email is unavailable- added by hardy (Posted a comment)
  • -email is unavailable- added by hardy
  • -email is unavailable- added by hardy
  • -email is unavailable- added by andersh (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 5 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-08-18 avinoam StatusIn Progress Wont Fix
        Open/ClosedOpen Closed
    2022-08-08 avinoam StatusNone In Progress
    2022-03-16 hardy Carbon-Copy- Added avinoam
        Carbon-Copy- Added carandraug

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code