You are here

3D Thinning Algorithms

Lifetime from: 
1997
Lifetime to: 
2012
Short description: 
The thinning is an iterative layer by layer erosion until only the "skeletons" of the objects are left. We proposed various 3D thinning algorithms capable of extracting medial lines or medial surfaces as well.
Description: 

Skeleton is a region-based shape descriptor which summarizes the general form of objects/shapes. An illustrative definition of the skeleton 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.

There are two types of 3D thinning algorithms: the curve--thinning type is used to extract medial lines or centerlines, while a surface--thinning type produces medial surfaces. We proposed various 3D thinning algorithms capable of extracting medial lines or medial surfaces as well.

Examples of different types of skeletal shape features in 3D:


The original object (left), its medial surface (middle), and its medial lines (right).

Publications: 
Palágyi K. A 3D parallel shrinking algorithm. ACTA CYBERNETICA-SZEGED. 2001;15(2):201-211.
Palágyi K, Kuba A. A parallel 3D 12-subiteration thinning algorithm. GRAPHICAL MODELS AND IMAGE PROCESSING. 1999;61(4):199-221.
Palágyi K, Kuba A. A hybrid thinning algorithm for 3D medical images. CIT JOURNAL OF COMPUTING AND INFORMATION TECHNOLOGY. 1998;6(2):149-164.
Palágyi K. A 3-subiteration surface-thinning algorithm. In: Kropatsch WG, Kampel M, Hanbury A, editors. Computer Analysis of Images and Patterns. Vienna, Austria: Springer Verlag; 2007. 6. p. 628-635p. (Lecture Notes in Computer Science).
Palágyi K. A subiteration-based surface-thinning algorithm with a period of three. In: Hamprecht FA, Schnorr C, Jähne B, editors. Pattern Recognition. Heidelberg, Germany: Springer Verlag; 2007. 2. p. 294-303p. (Lecture Notes on Computer Science).
Palágyi K. A 3D 3-subiteration thinning algorithm for medial surfaces. LECTURE NOTES IN COMPUTER SCIENCE. 2000;1953:406-418.
Palágyi K, Kuba A. Directional 3D thinning using 8 subiterations. LECTURE NOTES IN COMPUTER SCIENCE. 1999;1568:325-336.
Palágyi K. A 3D fully parallel surface-thinning algorithm. THEORETICAL COMPUTER SCIENCE. 2008;406(1-2):119-135.
Palágyi K, Németh G. Fully Parallel 3D Thinning Algorithms based on Sufficient Conditions for Topology Preservation. In: Brlek S, Reutenauer C, Provençal X, editors. Proceedings of Discrete Geometry for Computer Imagery (DGCI). Montreal, Quebec, Canada: Springer Verlag; 2009. 4. p. 481-492p.
Németh G, Kardos P, Palágyi K. Topology Preserving 3D Thinning Algorithms using Four and Eight Subfields. In: Campilho A, Kamel M, editors. Proceedings of the International Conference on Image Analysis and Recognition (ICIAR). Vol 6111. Póvoa de Varzim, Portugal: Springer Verlag; 2010. 3. p. 316-325p. (Lecture Notes in Computer Science; vol 6111).
Németh G, Kardos P, Palágyi K. Topology preserving 2-subfield 3D thinning algorithms. In: Zagar B, Kuijper A, Sahbi H, editors. Proceedings of the International Conference on Signal Processing, Pattern Recognition and Applications (SPPRA). Innsbruck, Austria: IASTED ACTA Press; 2010. 3. p. 310-316p.
Németh G, Kardos P, Palágyi K. A family of topology-preserving 3d parallel 6-subiteration thinning algorithms. In: Aggarwal JK, Barneva RP, Brimkov V E, Koroutchev KN, Korutcheva ER, editors. Combinatorial Image Analysis (IWCIA). Madrid, Spain: Springer Verlag; 2011. 1. p. 17-30p. (Lecture Notes in Computer Science).
Palágyi K, Németh G, Kardos P. Topology Preserving Parallel 3D Thinning Algorithms. In: Brimkov V E, Barneva RP, editors. Digital Geometry Algorithms. Springer-Verlag; 2012. 1. p. 165-188p. (Lecture Notes in Computational Vision and Biomechanics).
Kardos P, Palágyi K. Isthmus-based Order-Independent Sequential Thinning. In: Petrou M, Sappa AD, Triantafyllidis A G, editors. IASTED International Conference on Signal Processing, Pattern Recognition and Applications (SSPRA). Crete, Greek: IASTED ACTA Press; 2012. 2. p. 28-34p.
Kardos P, Palágyi K. On Order–Independent Sequential Thinning. In: , editor. IEEE International Conference on Cognitive Infocommunications (CogInfoCom). Kosice, Slovakia : IEEE; 2012. 1. p. 149-154p.
Németh G, Palágyi K. 3D Parallel Thinning Algorithms Based on Isthmuses. In: Blanc-Talon J, Philips W, Popescu D, Scheunders P, Zemčík P, editors. Advanced Concepts for Intelligent Vision Systems (ACIVS). Vol 7517. Brno, Czech Republic: Springer Verlag; 2012. 3. p. 325-335p. (LNCS; vol 7517).
Kategória: 
Skeletonization