Skeletonization Benchmark
Introduction
In the past decade (or more), tens of different algorithms have been published for the extraction of 2D skeletons or medial axes, 3D surface skeletons, and 3D curve skeletons. However, to date, few if any benchmarks exist for comparing the quality of such methods. As such, deciding whether a (new) skeletonization method fits its purpose is, in practice, quite hard.
Objectives
To assist such an assessment, we propose a skeletonization benchmark. The benchmark consists of the following ingredients:
- for 2D skeletonization: a set of 2D binary images
- for 3D skeletonization: a set of 3D shapes, both in polygonal and volumetric formats
Shape selection
The shapes included in this benchmark have been selected to match several criteria:
- known: shapes frequently used in skeletonization literature
- public: shapes present in well-known repositories, such as Aim@Shape, McGill's shape benchmark, and Stanford scan repository (among others)
- complex: shapes have challenging structures, such as
- highly variable amounts of noise
- high surface detail
- zero and higher genus
- natural (smooth) and synthetic (faceted) objects
- variate: shapes from various sources (3D laser scanning, 3D contouring of volume scanning, CAD/CAM modeling)
- relevant: shapes suitable for skeletonization, i.e. described by surfaces which are
- closed
- orientable
- having no duplicate vertices (for mesh representations)
- having tubular symmetry (for curve skeleton) and planar symmetry (for surface skeletons)
Repository
For simplicity, we store all shapes in easy-to-read, accessible, file formats. Three representations are used:
- image: 2D shapes are represented in PGM binary image format, with white for foreground, and black for background.
- surface: 3D shapes are represented in PLY format. Only triangle primitives are used. All properties except vertex coordinates are ignored.
- volume: 3D shapes are represented in the binvox volume format.
By providing three representation types, we aim to cover 2D skeletonization methods (typically, these assume image inputs), and 3D mesh-based and voxel-based skeletonization methods.
2D Image shapes
The first set of test images provided below serves as a benchmark for 2D skeletonization methods. The set includes both natural and synthetic shapes, with and without (multiple) holes, varying thickness, and smooth and noisy boundaries. Image resolutions range between 2002 and 10002 pixels. All images are in PGM grayscale format, with black for the shape foreground and white for the shape background.
- Download here the set of 2D test shapes
3D Mesh shapes
The second set of test shapes provided below serves as a benchmark for 3D surface and curve skeletonization methods. The set includes both natural and synthetic shapes, with and without (multiple) hopes, varying thickness, and smooth and noisy boundaries. Shapes are provided in PLY triangle-mesh format. All meshes have been cleaned to ensure a consistent orientation, closeness, no duplicate or T vertices, and no degenerate faces. Each file describes a single connected shape. Mesh resolutions range between a few thousand vertices and over a million vertices. Some meshes are uniformly (densely) sampled, while others are highly non-uniform. All meshes can be visually examined using MeshLab.
- Download below the set of 3D test mesh shapes:
- After downloading all files, rename files 3dmeshes_file1.zip up to and including 3dmeshes_file9.zip to 3dmeshes_file.z01 .. 3dmeshes_file.z09 respectively. Leave the master file 3dmeshes_file.zip as it is. Next, execute
zip -F 3dmeshes_file.zip --out 3dmeshes.zipunzip 3dmeshes.zip
The above command create (and unzip) a single large 290MB ZIP archive containing around 125 3D mesh models from the ten ZIP parts.
3D Volumetric shapes
Software
Besides shapes, we also provide (pointers to) a number of 2D and 3D skeletonization algorithm implementations. These methods can be readily used on the corresponding image, mesh, and volumetric shapes provided above. By providing these implementations, we aim to give everybody a quick and easy way for comparing existing (and new) skeletonization methods with earlier such methods.
Note: The list of algorithms provided here is, of course, not exhaustive. It was determined based on methods that are
- available: in either source code or executable format, publicly redistributable
- simple: easy to install and run by a typical end-user
- complete: are self-contained, i.e., provide all code required to run them
- scalable: handle images of at least 5002 pixels or 3D shapes of at least 10K polygons or 3003 voxels in (tens of) seconds on a typical PC
- robust: were successfully tested by us by running them on a wide variety of third-party input shapes
The skeletonization software links follow below:
- thinvox: Curve skeletonization based on thinning (Windows/Linux source)
- Reniers et al.: Geodesic-based curve and surface skeleton extraction for 3D voxel models (Windows binary and source)
- IMA Integer medial axis for 3D surface skeletons (Linux source code; original from authors; our version).
- AFMM: 2D skeleton extraction from binary images (Windows/Linux binary and source)
- CUDASkel: CUDA-accelerated version of AFMM (Linux binary and source)
- Siddiqi et al. Hamilton-Jacobi 3D curve and surface skeletons (Linux source)
- Gorgon: Iterative thinning process (Windows binary)
- Liu et al.: Robust thinning (Windows binary)
- Au et al.: Curve skeleton extraction for 3D mesh models (Windows binary executable)
- Cao et al.: Curve skeleton extraction for 3D mesh models (Linux source code).
- MCF: Mean curvature curve-skeletons (Windows/Linux/Mac source code).
- MCF-CGAL: Mean curvature curve-skeletons with CGAL library (Windows/Linux/Mac (source code).
Evolution
We are continuously investing effort to refine the proposed benchmark by adding new shapes, refining the proposed shapes, and adding (pointers to) new 2D and 3D skeletonization software. Be sure to visit this page frequently to get the latest version of our benchmark.