MB: a coherent collection of 2D parallel thinning algorithms

Antoine Manzanera (1) , Thierry Bernard (2)

1 RV - Robotique et Vision
2 UEI - Unité d'Électronique et d'informatique

We present new thinning algorithms to compute the digital skeletons of binary 2D images. Starting from a physical characterization of the thinning process, we show that the mere incorporation of discrete topology preservation conditions leads to the Boolean definition of different parallel thinning algorithms, depending on the topological and metrical properties that can be basically desired in the square grid. The complete Boolean definition of every algorithm is provided through a coherent set of removing and non-removing conditions. For every algorithm, logic minimization is addressed, and the implementation on a Boolean cellular automata grid is proposed. Beyond the implementation, we stress the advantages of Boolean concision in terms of complexity reduction. Some results are shown and discussed.

Keywords: Thinning algorithm; Digital Skeleton

Domains: Computer Science [cs]; Image Processing [eess.IV]; Computer Science [cs]; Computational Geometry [cs.CG]

Antoine Manzanera, Thierry Bernard. MB: a coherent collection of 2D parallel thinning algorithms. [Research Report] ENSTA ParisTech. 2002. ⟨hal-01222700⟩