# 2D Thinning Algorithms

2008
2012
Short description:
Thinning is a frequently used method for skeletonization by modeling the fire-front propagation. We proposed some sequential and parallel 2D thinning algorithms capable of producing topologically correct skeletons.
Description:

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.

Publications:
Parallel Thinning Algorithms Based on Ronse's Sufficient Conditions for Topology Preservation, , Progress in Combinatorial Image Analysis, May 2010, Singapore, p.183 - 194, (2010)
An order-independent sequential thinning algorithm, , Proceedings of the International Workshop on Combinatorial Image Analysis (IWCIA), Nov 2009, Number 5852, Playa del Carmen, Mexico, p.162 - 175, (2009)
2D Parallel Thinning Algorithms Based on Isthmus-Preservation, , Proceedings of the International Symposium on Image and Signal Processing and Analysis (ISPA), Sep 2011 , Dubrovnik, Croatia, p.585 - 590, (2011)
Topology Preserving Parallel Thinning Algorithms, , INTERNATIONAL JOURNAL OF IMAGING SYSTEMS AND TECHNOLOGY, Feb 2011, Volume 21, Issue 1, p.37 - 44, (2011)
2D parallel thinning and shrinking based on sufficient conditions for topology preservation, , ACTA CYBERNETICA-SZEGED, 2011, Volume 20, Issue 1, Szeged, p.125 - 144, (2011)
Order-independent sequential thinning in arbitrary dimensions, , Signal and Image Processing and Applications (SIPA), June 2011, Crete, Greek, p.129 - 134, (2011)
On topology preservation for hexagonal parallel thinning algorithms, , Combinatorial Image Analysis (IWCIA), May 2011, Number 6636, Madrid, Spain, p.31 - 42, (2011)
Hexagonal parallel thinning algorithms based on sufficient conditions for topology preservation, , Computational Modelling of Objects Represented in Images: Fundamentals, Methods and Applications III, 2012, London, p.63 - 68, (2012)
On topology preservation for triangular thinning algorithms, , Combinatorial Image Analysis (IWCIA), Nov 2012, Number 7655, Austin, TX, USA, p.128 - 142, (2012)
Kategória:
Skeletonization