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 T_i for all its gray values
select a subset of relevant threshold sets t_i from T_i
extract the simplified skeletons S_i of t_i
the image is now encoded in the medial axis transforms MAT_i of S_i
use MAT_i 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.