Visualization and Graphics ➤ Interaction ➤ Dept ICS ➤ Faculty of Science ➤ UU

//webspace.science.uu.nl/~telea001/Site/TopBar

Robust Multiscale 2D Skeletonization

2D skeletonization refers to the process of computing so-called skeletons, or medial axes, from binary images, or shapes. In this context, skeletons are one-dimensional pixel-thin curve structures that are locally centered with respect to the shape. Skeletonization can also be performed on 3D shapes.

Although 2D skeletonization has been studied for decades, there are very few methods that can deliver a skeleton which is always pixel-thin, exactly centered with respect to the shape, connected, insensitive to shape noise (small-scale boundary perturbations), and handle all possible shape configurations (topology, size, thickness, and sampling resolution) in real-time.

Multiscale importance metric

We have designed a method with all above properties, based on a multiscale importance metric. This importance measures, for every shape pixel, the length of the boundary segment subtended by the pixel's so-called feature points (i.e. closest boundary points). By simply upper thresholding this metric, we detect the skeleton and retain all its branches corresponding to boundary features larger than a desired size, or scale.

Our skeletonization pipeline is simple (see above image). Given a shape (1), we initialize the importance to the boundary arc length parameterization (2). We propagate these values inside the shape using a modified Fast Marching Method algorithm (3) and compute the importance using finite-differences (4). The thresholded result delivers the skeleton (5). We call the entire technique the Augmented Fast Marching Method (AFMM). The AFMM computes distance transforms, feature transforms, and skeletons - all in one.

Feature preserving shape smoothing

Feature preserving shape smoothing eliminates small-scale noise in a shape but preserves large-scale features, such as salient edges and corners. To do this, traditional methods use various forms of scale-space methods, such as anisotropic diffusion weighted by curvature. However effective, such methods cannot typically distinguish between noise and features at the same scale, since curvature is a local property.

We approach this problem from a global angle: We use skeletons to determine if a shape detail is noise or feature, and smooth it accordingly. The image below reflects the idea: Curvature-based methods (middle) would smooth both the jaggies and corners of the noisy rectangle. Our method smoothes the jaggies but keeps the corners intact (right).

Using skeletons, achieving this perceptual saliency-preserving smoothing is very simple. We divide our AFMM importance metric described above by the distance transform. The result will be high within skeleton branches of corners and jaggies, average along skeleton branches of corners, and low along branches of jaggies. Thresholding the result disconnects the latter branches and leaves the former ones intact. We next inflate the thresholded skeleton, using the FMM, and obtain the shape without jaggies but with intact corners.

The image below shows several noisy shapes smoothed with our method. The bottom row shows progressive smoothing of a shape, done by using increasing thresholds.

We can use this method to assist in segmentation. In the image below, a noisy brain scan is segmented using a simple color-based method. This produces a noisy shape. Our method removes the small-scale wiggles but keeps the shape's main features.

And now a more extreme example: The very noisy image below (left) is both smoothed and cleaned up of specks and holes by our smoothing. The effect is similar to morphological dilation, erosion, and anisotropic smoothing, but we obtain it in a single pass. This also shows the high accuracy and robustness of our AFMM which has no problems with such shapes.

Generalized GPU-based skeletons

Traditionally, 2D skeletons use an Euclidean distance metric. But can we compute skeletons for non-Euclidean distances? And what are they like?

To answer this, we cast the AFMM into an OpenGL-based setting (this helped generalizing the distance metric). The key idea is simple (see image below, left): We draw a radial luminance texture centered at every pixel of a shape's boundary and accumulate the maximum of the result. This gives us the shape's distance transform (image below, right). Similarly, we accumulate the boundary parameterization to obtain the skeleton importance. The details are in this paper.

By changing the distance profile encoded by the texture, we can compute distance transforms and skeletons of any distance metric, even different ones at different shape points. The image below shows the distance transform (color-coded) and skeleton (black) of a room plan (white) for the Manhattan metric (left) and Euclidean metric (right). Far from the shape, Manhattan skeletons have branches at angles of 45 degrees. Interestingly, close to the shape, the two skeletons are quite similar.

Many variations are possible. The image below shows a Manhattan skeleton for a leaf (top-left) and Voronoi diagrams for the Euclidean metric (bottom-left), additive Euclidean metric (top-right), and multiplicative Euclidean metric (bottom-right). For these diagrams, the weights of the sides are indicated by the colored halo sizes.

Acknowledgements

The original idea of using the FMM to compute skeletons, as well as credits for insightful discussions, belongs to prof. dr. Martin Rumpf (Univ. of Bonn, Germany). Additional collaborators for applications include prof. dr. Sven Dickinson, prof. dr. Cristian Sminchisescu, dr. Robert Strzodka, and ir. Matthijs van Eede.

Software

The entire implementation of our AFMM is less than 500 lines of C++ code and works in real time on images up to 1000 by 1000 pixels.

The C++ source code for the AFMM is available here. This code compiles directly on Mac OS X. With minor changes, it can be made to compile on Linux and Windows.

Running the software

  • start AFMM.exe
  • give the name of a binary image in PGM format. Sample images are available in the DATA directory
  • press space in the graphics window to see the different datasets computed
  • for the skeleton, press + and - to increase/decrease the simplification level

Notice how the method is able to compute pixel-accurate skeletons even for extremely noisy images. Skeleton branches are correctly computed even for the smallest boundary perturbations.

Building the software

  • either use the Visual C++ 2008 project supplied
  • or write your own makefile; the software should compile with any recent C++ compiler and only requires OpenGL and (for visualization purposes)

Applications

We have successfully used our AFMM in many projects involving real-world image data, such as shape matching, vector field simplification, 3D centerline extraction, feature-preserving shape smoothing, and computing skeletons with non-Euclidean metrics. See publications 74, 43, 38, 32, and 27 here.