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
Our method also works directly for color images. The figure below shows such an image (a), reduced to a painting-like view by (b) the method of Papari et al. and by (c) our dense-skeleton method. We see that (b) and (c) are very similar -- with the added value that our method is far faster, and simpler, than (b).
Application: Image compression
If we can simplify images, it means we can also compress them! Our method produces results that are competitive with JPEG, see details here.
Implementation
Our method is very fast -- seconds or less for a high-resolution image. This is thanks to our underlying GPU-based skeletonization method.
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).
A more refined analysis of the behavior of image skeletons is described in the MSc thesis of Maarten Terpstra (2017).
A detailed quantitative evaluation of how dense skeletons can be used to compress images is given by Wang et al.