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

 
 

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

Submitted by:  Anders Höglund <andersh>
Submitted on:  Wed 16 Mar 2022 11:13:22 AM UTC
 
Category:  Octave Forge Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  None Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * other Operating System:  * Any
* Mandatory Fields

Add a New Comment (Rich Markup)
   

Comment Type & Canned Response:
       

 

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>
Project 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 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 project members can vote.

     

     

     

     

    Follow 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-03-16 hardy Carbon-Copy- => Added avinoam
        Carbon-Copy- => Added carandraug

    Back to the top


    Powered by Savane 3.9