Add a New Comment (Rich Markup)

Comment Type & Canned Response: None None > Multiple Canned Responses Fixed in development Crash with no stack trace Already fixed in newer version Fixed in stable Bad description Bad description and crash Bad stack trace Obsolete version Duplicate and not fixed Duplicate and needs more info Duplicate and fixed Need info and old

( Jump to the original submission )

Closing as "Wont Fix". Thank you all.

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.

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.

Good idea. Please do it.

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?

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

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

adding package maintainers to cc

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.

(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

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.

Please enter the title of George Orwell's famous dystopian book (it's a date):

Follow 5 latest changes.

Copyright © 2022 Free Software Foundation, Inc. Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved. The Levitating, Meditating, Flute-playing Gnu logo is a GNU GPL'ed image provided by the Nevrax Design Team. Source Code

Powered by Savane 3.9