Jelenlegi hely

2D Thinning Algorithms

Lifetime from: 
Lifetime to: 
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.

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.

Németh G, Palágyi K. Parallel Thinning Algorithms Based on Ronse's Sufficient Conditions for Topology Preservation. In: Wiederhold P, Barneva RP, editors. Progress in Combinatorial Image Analysis. Singapore: Scientific Research Publishing Inc.; 2010. 1. p. 183-194p.
Kardos P, Németh G, Palágyi K. An order-independent sequential thinning algorithm. In: Wiederhold P, Barneva RP, editors. Proceedings of the International Workshop on Combinatorial Image Analysis (IWCIA). Playa del Carmen, Mexico: Springer Verlag; 2009. 1. p. 162-175p.
Németh G, Palágyi K. 2D Parallel Thinning Algorithms Based on Isthmus-Preservation. In: Lončarić S, Ramponi G, Sersic D., editors. Proceedings of the International Symposium on Image and Signal Processing and Analysis (ISPA). Dubrovnik, Croatia: IEEE; 2011. 5. p. 585-590p.
Németh G, Palágyi K. Topology Preserving Parallel Thinning Algorithms. INTERNATIONAL JOURNAL OF IMAGING SYSTEMS AND TECHNOLOGY. 2011;21(1):37-44.
Kardos P, Palágyi K. Order-independent sequential thinning in arbitrary dimensions. In: Andreadis I, Zervakis M, editors. Signal and Image Processing and Applications (SIPA). Crete, Greek: IASTED - Acta Press; 2011. 1. p. 129-134p.
Kardos P, Palágyi K. On topology preservation for hexagonal parallel thinning algorithms. In: Aggarwal JK, Barneva RP, Brimkov V E, Koroutchev KN, Korutcheva ER, editors. Combinatorial Image Analysis (IWCIA). Madrid, Spain: Springer Verlag; 2011. 3. p. 31-42p. (Lecture Notes in Computer Science).
Kardos P, Palágyi K. Hexagonal parallel thinning algorithms based on sufficient conditions for topology preservation. In: Di Giamberardino P, Iacoviello D, Jorge R M N, Taveres JManuel RS, editors. Computational Modelling of Objects Represented in Images: Fundamentals, Methods and Applications III. London: CRC Press - Taylor and Frances Group; 2012. 6. p. 63-68p.
Kardos P, Palágyi K. On topology preservation for triangular thinning algorithms. In: Barneva RP, Brimkov V E, Aggarwal JK, editors. Combinatorial Image Analysis (IWCIA). Austin, TX, USA: Springer Verlag; 2012. 1. p. 128-142p. (Lecture Notes in Computer Science).