Scientific Visualization and Computer Graphics > CS > JBI > FWN > RUG

Dense Skeletons for Image Coding

Skeletons, or medial axes, are powerful tools for encoding the topology and geometry of binary shapes. Efficient CPU and GPU algorithms exist to compute such skeletons. However, how can we extend their usage to continuous fields, such as grayscale images? This would open new ways for us to perform operations such as image analysis, compression, and matching.

From images to skeletons and back

We propose the following skeleton-based image representation pipeline: Given an input image, we

  • compute all its threshold sets Ti for all its gray values
  • select a subset of relevant threshold sets ti from Ti
  • extract the simplified skeletons Si of ti
  • the image is now encoded in the medial axis transforms MATi of Si
  • use MATi to process or reconstruct the image

Application: Image simplification

We applied the above method to produce simplified representations of natural images. Each threshold set is reconstructed by inflating its MAT. Reconstructions are drawn atop of each other, using linear interpolation to remove grayscale-banding effects.

The results combine image compression with image simplification: We obtain smaller images (in terms of bit count), but also simpler images (small-scale details are removed).

The left image below shows the lena image, reconstructed using only 100 of its 255 threshold sets. Grayvalue-banding is visible. The right image interpolates between consecutive reconstructed sets, yielding smoother transitions, but still keeping high-contrast features sharp.

Examples

More examples of image simplification are shown below. Note how our method keeps 'salient' image features such as sharp, high-contrast, corners, but removes small-scale soft features. Besides image compression, the effect is often similar to a hand-painting of the image.

Left: original(256KB) Right: simplified (102KB)

Left: original(256KB) Right: simplified (195KB)

Left: original(256KB) Right: simplified (57KB)

Left: original high-detail image Right: Painting-like effect

Software

The source code, and also a precompiled binary version of the dense skeleton image coding (Mac OS ) are available here.

Bibliography

Applications of the skeleton-based image coding are described in Van der Zwan et al. (2011).

The skeleton-based image coding method is described in detail in the MSc thesis of Yuri Meiburg (2011).