bwdist - distance transforms |
dt = bwdist(img [,algorithm]) |
img |
Binary image containing one or more binary shapes. (foreground == 1, background == 0). The shapes may have any form. |
algorithm (see references) |
Listed below are the various algorithms available, together with the shortest string form accepted (for speed of use). This argument is CASE-INSENSITIVE. Some of the algorithms are faster than others, but this depends heavily on the size and content of the input. |
euclidean or euclid: the default fast exact euclidean algorithm. Currently, it is the same as the cuisenaire pmn bellow. (DEFAULT) |
cuisenaire pmn: very fast exact euclidean algorithm. It is based on propagation of multiple neighborhoods to build up an exact EDT. |
cuisenaire pmon: a variation of the latter that uses multiple oriented neighborhoods. It seems to be slightly slower, in general, but can be faster for some cases. |
cuisenaire psn4: a variation of the latter that uses only 4-neighborhood. This is faster but less precise. |
cuisenaire psn8: a variation of the latter that uses diagonal neighborhood after 4-neighborhood to improve the precision. This is faster than the full pmn algorithm, but less precise. It is a little slower than psn4 but considerably more precise. |
maurer or mau : very fast (and recent) exact euclidean algorithm, based on some dimensionality properties of Voronoi diagrams. Seems to be slightly slower than cuisenaire pmn, but can be faster for some cases. |
lotufo-zampirolli or lotufo-z: very fast exact euclidean algorithm. Seems to be slightly slower than maurer and cuisenaire, in general, but can be faster for some cases. |
IFT 8 or IFT: a fast algorithm using the euclidean metric. For large and thick shapes, there may be a few small errors, which are dispensable for most practical applications. |
IFT 4: the same algorithm but with 4-neighborhood propagation. This means that this method is about 2x faster but less precise. |
exact dilations or exact dil: will perform an exact euclidean algorithm that is slow for medium shapes, but it is always exact and reasonably fast for thin shapes. |
dt |
The distance transform of the image. When using the euclidean metric, it has the squared euclidean distances of any point of the image to the boundary of the object. |
Function bwdist computes the distance transform. For each foreground pixel (i.e. value 1) in the input image, the distance transform assigns a value that is the smallest distance between that pixel and the outer boundary of the object. |
Many different methods are provided for comparison purposes. If you are going to use bwdist extensively, you could test the algorithms to find the best one for your particular type of image. |
xset('auto clear', 'on'); // First, a simple example to illustrate the concept A = zeros(15,10); A(4:12,3:7)=1; A(4:5,3:4)=0 D = bwdist(A) D = sqrt(D) // Note how the values in D were calculated. // For each pixel p such that A(p)=1, D(p) is the minimum euclidean // distance of p and the 0-pixels (background). // ----------------------------------- // Now to a more interesting example // ----------------------------------- A = gray_imread(SIPDIR + 'images/escher.png'); imshow(A,2); D = bwdist(A); // method=='cuisenaire pmn' imshow(log(1+D),[]); // normalizes image to enhance visualization D = bwdist(A,'exact dilations'); imshow(log(1+D),[]); // To obtain an external EDT, simply invert the shape: B = 1-A; D = bwdist(B,'maurer'); imshow(log(1+D),[]); // To obtain an external+internal EDT, simply compute // the binary border of the shape and pass its negative // to bwdist: A = bwborder(A); A = 1-A; D = bwdist(A,'lotufo-zampirolli'); imshow(log(1+D),[]); // --------------------------------- // Other forms to visualize the DT // --------------------------------- // Wrapping (note the wavefronts of iso-distance) imshow(modulo(sqrt(D),10),[]) // Usual: D = bwdist(A); D = normal(sqrt(D),1000,1); imshow(D,hotcolormap(1000)); // There is also of DT application in the example for the "watershed" // function. xset('auto clear', 'off'); |
Cuisenaire: Cuisenaire, O and Macq, B, "Fast Euclidean Distance Transformation by Propagation Using Multiple Neighborhoods", Computer Vision and Image Understanding, no. 2, vol 76, 163--172, 76, 1999. |
Chapter 3 of "Distance transformations: fast algorithms and applications to medical image processing", Olivier Cuisenaire's Ph.D. Thesis, October 1999, Université catholique de Louvain, Belgium. |
Maurer: Maurer, C.R. and R. Qi and V. Raghavan, "A Linear Time Algorithm for Computing the Euclidean Distance Transform in Arbitrary Dimensions", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no. 2, pp. 265-270, february 2003. |
IFT: "Multiscale Skeletons by Image Foresting Transform and its Application to Neuromorphometry", A.X. Falcao, L. da F. Costa, B.S. da Cunha, Pattern Recognition, 2002. |
Lotufo-Zampirolli: R. Lotufo and F. Zampirolli, Fastmultidimensional parallel euclidean distance transform based on mathematical morphology, in T. Wu and D. Borges, editors, Proccedings of SIBGRAPI 2001, XIV Brazilian Symposium on Computer Graphics and Image Processing, pages 100-105. IEEE Computer Society, 2001. |
Exact Dilations: "Multiresolution shape representation without border shifting", L. da F. Costa, and L. F. Estrozi, Electronics Letters, no. 21, vol. 35, pp. 1829-1830, 1999. |
"Shape Analysis and Classification", L. da F. Costa and R.M. Cesar Jr., CRC Press. |
Ricardo Fabbri <rfabbri@if.sc.usp.br> |
The latest version of the Scilab Image Processing toolbox can be found at |
http://siptoolbox.sourceforge.net |
skel, thin |