Spline Medial Axis Transforms for Binary Images

Skeletons and Medial Axis Transforms (MATs) are a dual representation for binary shapes. Using efficient skeletonization methods, MATs can be computed with pixel accuracy and in real-time on the CPU or GPU. Suitably simplified, such MATs can be used to represent any binary images at a user-selected accuracy level. However, manipulating and even storing skeletons as pixel-chains is cumbersome and can be expensive.

We solve this problem by replacing the pixel-chain representation of skeletons and MATs with splines. Our computation pipeline has the following steps:

• extract the MAT from a binary image
• simplify the MAT to e.g. remove irrelevant/noisy branches
• segment the MAT into separate pixel chains
• fit one spline per pixel-chain

This delivers Spline-based Medial Axis Transform (SMAT), an accurate and compact representation of the initial binary shape. The shape can be reconstructed from its SMAT by rasterizing the splines and next applying the well-known union-of-balls property of MATs.

Quality and Compression Ratio

The image below shows several binary shapes (from simple to complex) in black outline, and their SMAT reconstructions in blue. The two are virtually identical, as also indicated by the very high MS-SSIM similarity metric. The compression ratio (CR) tells how many times smaller the SMAT representation is as compared to the raw initial binary image. We see that SMAT saves a lot of space while accurately capturing the shape!

Applications

Skeletons as splines allows many applications such as interactively editing shapes by manipulating their spline control points, as shown in the example below.

Code

SMAT is written in C++ and fully open source (available here).

References

J. Wang, J. Kosinka, A. Telea (2021) Spline-based medial axis transform representation of binary images Computers and Graphics (98), 165-176