Affordable Access

Publisher Website

Minimal non-deletable sets and minimal non-codeletable sets in binary images

Theoretical Computer Science
Publication Date
DOI: 10.1016/j.tcs.2008.02.001
  • Digital Topology
  • Binary Image
  • Thinning
  • 4D
  • Deletable
  • Codeletable
  • Simple
  • Cosimple
  • Minimal Non-Deletable
  • Minimal Non-Simple
  • Polytopal Complex
  • Xel Complex
  • Computer Science


Abstract The concepts of strongly 8- deletable and strongly 4- deletable sets of 1s in binary images on the 2D Cartesian grid were introduced by Ronse in the mid-1980s to formalize the connectivity preservation conditions that parallel thinning algorithms are required to satisfy. In this paper we call these sets deletable and codeletable, respectively. To establish that a proposed parallel thinning algorithm for binary images on the 2D Cartesian grid preserves 8-(4-)connected foreground components and 4-(8-)connected background components, it is enough to prove that the set of 1s which are changed to 0s at each pass of the algorithm is always a deletable (codeletable) set. Ronse established results that are very useful in this context for proving that a finite set D of 1s is deletable or codeletable. In particular, he showed that D and its proper subsets are all codeletable in a binary image if each singleton and each pair of 8-adjacent pixels in D is codeletable. He further showed that D and its proper subsets are all deletable in a binary image if (1) each singleton and each pair of 4-adjacent pixels in D is deletable, and (2) no set of 2, 3, or 4 pairwise 8-adjacent pixels that is an 8-connected foreground component of the image is entirely contained in D . In the 1990s and early 2000s analogous results were obtained by Hall, Ma, Gau, and the author for binary images on the 2D hexagonal grid, the 3D Cartesian and face-centered cubic grids, and the 4D Cartesian grid. This paper extends the above-mentioned work to binary images on almost any polytopal complex whose union is n -dimensional Euclidean space, for n ≤ 4 . Our main results generalize and unify the corresponding results of the earlier work.

There are no comments yet on this publication. Be the first to share your thoughts.