2D Thinning Algorithms

An illustrative definition of the skeleton (i.e., a region-based shape descriptor) is given using the prairie-fire analogy: the object boundary is set on fire and the skeleton is formed by the loci where the fire fronts meet and extinguish each other.

Thinning is a frequently used method for making an approximation to the skeleton in a topology--preserving way. It is based on a digital simulation of the fire front propagation: the border points of a binary object that satisfy certain topological and geometric constraints are deleted in iteration steps. The entire process is then repeated until only the "skeleton" is left.

Sequential thinning algorithms use contour tracking: they scan border points and remove the actual one if it is not designated a skeletal point. They may produce various skeletons for different visiting orders. We proposed a new 2-dimensional sequential thinning algorithm, which produces the same result for arbitrary visiting orders and it is capable of extracting maximally thinned skeletons.

Parallel thinning algorithms use parallel reduction operators that delete all points satisfying their deletion condition simultaneously. We proposed a new family of parallel thinning algorithms that is based on Ronse’s sufficient conditions for topology preservation. The strategy which is used is called fully parallel, which means that the same parallel operator is applied at each iteration step.