skeletonization, thinning, Medial Axis Transform

[skl,dt,lbl] = skel(img [,side, algorithm])

- img
- Binary image containing one or more binary shapes. (foreground == 1, background == 0), One-pixel-wide regions are ignored (temporary limitation).
- side
- 'interior'
- if only internal skeleton is desired (DEFAULT)
- 'exterior'
- if only external skeleton is desired
- 'both'
- if the background and foreground skeleton must be computed at the same time

- algorithm
- 'fast euclidean'
- (DEFAULT) will perform a fast O(n) algorithm using the Euclidean metric. For large and thick shapes, there may be a few small errors, which are dispensible for most practical applications.
- 'exact euclidean'
- will perform an exact euclidean algorithm that is very much slower.

- skl
- The multiscale skeleton image. This is a grayscale image, which may be thresholded to yield a skeleton with varying levels of detail. The greater the threshold, the cleaner is the skeleton. A threshold level of 5 will give a usual skeleton similar to the one obtained by popular thinning methods.
- dt
- The euclidean distance transform of the image. It has the squared euclidean distances of any point of the image to the object.
- lbl
- Label image. This is the discrete Voronoi Diagram of the boundary pixels of the considered object. Is is a grayscale image indicating the region of influence of each boundary pixel.

Function skel performs skeletonization (thinning) of a binary object. The resulting medial axis is multi-scale, meaning that it can be progressively pruned to eliminate detail. This pruning is done by thresholding the output skeleton image.

The algorithm computes skeletons that are guaranteed to be connected over all scales of simplification. The skeletons are computed using the Euclidean metric. This has the advantage to produce high-quality, isotropic and well-centered skeletons in the shape. However the exact algorithm is computationally intensive.

The radius of the maximal balls associated with the skeleton points are stored in the distance transform output image.

initial_dir = PWD; chdir (SIPDIR + 'images'); xset('auto clear', 'on'); im=gray_imread('escher.png'); imshow(im,2); [skl,dt,vor] = skel(im); // Fine detail sklt = (skl >= 5); imshow(im+sklt,[]); // Less detail sklt = (skl >= 20); imshow(im+sklt,[]); // The Distance Transform imshow(sqrt(dt),[]); // The Influence zones or Voronoi diagram of the boundary pixels imshow(vor+1,rand(max(vor)+1,3)); // each region maps to a random color // Let's see if computation is really fast stacksize('max'); big = mogrify(im,['-sample','1000x']); size(big) skl = skel(big); imshow(big + (skl >= 50),[]); xset('auto clear', 'off'); chdir(initial_dir); |

**The result of the preceding example, less detail (left) and more detail (right):**

**The Influence or Voronoi regions of each boundary pixel (a.k.a. a label map), and the distance map:**

For the fast Euclidean algorithm: "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.

For the exact Euclidean algorithm:

"Multiresolution shape representation without border shifting", L. da F. Costa, 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.

`skel`

.- Ricardo Fabbri <ricardofabbri (AT) users DOT sf DOT net>

http://siptoolbox.sourceforge.net

- thin
- reconstruction (not done yet...)