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

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.

Related papers:

title: A Topological Characterization of Thinning
abstract: A large number of skeletonization algorithms for binary images use the method of thinning: successive layers of pixels are deleted from the figure until it becomes one pixel thick. In this paper we analyze the topological properties of the set D of pixels to be deleted from a figure F in order to get a skeleton. We characterize them by the concept of strong k -deletability ( k = 4 or 8). For individual pixels, strong k -deletability is equivalent to a more general property that we call k -deletability, which is well-known connectivity requirement assumed—at least implicity—in all existing thinning algorithms. We show then that a strongly k -deletable subset D of a figure F can be deleted by a succession of deletions of individual pixels p 1 ,..., p t , where each p i is k -deletable from F\{ p j ¶ j i }. This justifies our definition of strong deletability and shows that any topologically valid skeleton can be obtained by some thinning process.

title: Minimal test patterns for connectivity preservation in parallel thinning algorithms for binary digital images
abstract: In successive deletion stages of parallel thinning algorithms for binary digital images, one usually checks the preservation of connectivity by verifying that: (a) every removed pixel is individually deletable without modifying connectivity (well-known criteria, such as those of Rosenfeld and Yokoi, exist for that purpose); (b) every pair of 8-adjacent removed pixels is deletable without connectivity modification. In the case of the 8-connectivity for the figure (and the 4-connectivity for the background), two more patterns must be tested for connectivity preservation: an isolated triple or quadruple of mutually 8-adjacent pixels. In this paper we give a formal characterization of these patterns for testing connectivity preservation by what we call minimal non-x-deletable sets (x-MND sets), where x=4, 8 or {4,8} (the type of connectivity considered for the figure). A parallel thinning algorithm whose deletion stage cannot remove an x-MND set is guaranteed to preserve the connectivity properties of any figure. We show that an x-MND set consists in either (1) a single pixel; or (2) a pair of 8-adjacent pixels; or (3) an isolated triple or quadruple of mutually 8-adjacent pixels (for x=8 only).

title: Minimal Nonsimple Sets of Voxels in Binary Images on A Face-Centered Cubic Grid
abstract: One can prove that a specified parallel thinning algorithm always preserves the topology of the input binary image by verifying that no iteration of that algorithm can ever delete a minimal non-simple ("MNS") set of 1's of an image. For binary images on a 3D face-centered cubic ("FCC") grid, we determine which sets of voxels can be MNS, and also determine which of those sets can be MNS without being a component of the 1's. These two problems are complicated by the fact that there are (at least) three reasonable ways of defining connectedness for sets of 1's and 0's in a binary image on an FCC grid, since one can: (a) use 18-connectedness for sets of 1's and 12-connectedness for sets of 0's; (b) use 12-connectedness both for sets of 1's and for sets of 0's; (c) use 12-connectedness for sets of 1's and 18-connectedness for sets of 0's. We solve the two problems in all three cases. The analogous problems for binary images on Cartesian grids were first solved by Ronse (in the 2D case) and Ma (in the 3D case). However, our treatment of simple 1's and MNS sets is rather different from theirs, in that it is based on the attachment sets of 1's in binary images. This concept was introduced in an earlier paper [T. Y. Kong, "On topology preservation in 2-D and 3-D thinning,"  (1995) 813–844] and we use the same general approach to MNS sets as was used there. The voxels of an FCC grid are rhombic dodecahedra, which are rather more difficult to visualize and draw than the cubical voxels of a 3D Cartesian grid. An advantage of working with attachment sets is that such sets can be shown in a planar Schlegel diagram of a voxel, which is easy to draw.

title: Tests for connectivity preservation for parallel reduction operators
abstract: Connectivity preservation is a concern in the design of image processing algorithms for parallel reduction processes like thinning where connected components in 2-D images are reduced to medial axis approximations. Tests and proof techniques, which use local support for their computations, have been presented by Rosenfeld, Ronse and others to prove preservation of connectivity for reduction classes of thinning algorithms. In this paper the earlier Rosenfeld proof techniques are characterized as connectivity preservation tests for rectangular and hexagonal tessellations and simplified versions of these tests are developed. The later Ronse tests are characterized for rectangular and hexagonal tessellations; the Ronse test complexities are evaluated; and relevant equivalences are identified between the Rosenfeld and Ronse test forms. It is shown that forms of the Ronse tests for rectangular and hexagonal tessellations are derivable directly and simply from tests derived from the earlier Rosenfeld proof techniques. Arguments are given to establish under what operator support restrictions these tests are necessary and sufficient proofs for key connectivity preservation properties. Finally, a specific computer-based implementation of the Ronse test is described with extensions for reduction operators with larger supports and with reduction operators using subfields notions; and time performance results are given for this implementation.

title: Minimal Non-simple Sets in 4-Dimensional Binary Images with (8, 80)-Adjacency
abstract: We first give a definition of simple sets of 1’s in 4D binary images that is consistent with “(8,80)-adjacency”—i.e., the use of 8-adjacency to define connectedness of sets of 1’s and 80-adjacency to define connectedness of sets of 0’s. Using this definition, it is shown that in any 4D binary image every minimal non-simple set of 1’s must be isometric to one of eight sets, the largest of which has just four elements. Our result provides the basis for a fairly general method of verifying that proposed 4D parallel thinning algorithms preserve topology in our “(8,80)” sense. This work complements the authors’ earlier work on 4D minimal non-simple sets, which essentially used “(80,8)-adjacency”—80-adjacency on 1’s and 8-adjacency on 0’s.

title: On topology preservation in 3D thinning
abstract: Topology preservation is a major concern of parallel thinning algorithms for 2D and 3D binary images. To prove that a parallel thinning algorithm preserves topology, one must show that it preserves topology for all possible images. But it would be difficult to check all images, since there are too many possible images. Efficient sufficient conditions which can simplify such proofs for the 2D case were proposed by Ronse [ 1988, 69-79]. By Ronse′s results, a 2D parallel thinning algorithm can be proved to be topology preserving by checking a rather small number of configurations. This paper establishes sufficient conditions for 3D parallel thinning algorithms to preserve topology.

title: Lectures on Polytopes
abstract: Based on a graduate course given at the Technische Universitat, Berlin, these lectures present a wealth of material on the modern theory of convex polytopes. The clear and straightforward presentation features many illustrations, and provides complete proofs for most theorems. The material requires only linear algebra as a prerequisite, but takes the reader quickly from the basics to topics of recent research, including a number of unanswered questions. The lectures - introduce the basic facts about polytopes, with an emphasis on the methods that yield the results (Fourier-Motzkin elimination, Schlegel diagrams, shellability, Gale transforms, and oriented matroids) - discuss important examples and elegant constructions (cyclic and neighborly polytopes, zonotopes, Minkowski sums, permutahedra and associhedra, fiber polytopes, and the Lawrence construction) - show the excitement of current work in the field (Kalai's new diameter bounds, construction of non-rational polytopes, the Bohne-Dress tiling theorem, the upper-bound theorem), and nonextendable shellings) They should provide interesting and enjoyable reading for researchers as well as students.

title: Simple points, topological numbers and geodesic neighborhoods in cubic grids
abstract: We introduce the notion of geodesic neighborhood in order to define some topological numbers associated with a point in a three-dimensional cubic grid. For {6, 26} and {6, 18} connectivities, these numbers lead to a characterization of simple points which consists in only two local conditions.

title: A Boolean characterization of three-dimensional simple points
abstract: A simple point in a binary digital picture is a point belonging to the object whose removal does not change the basic connectivity features of the image. In this paper, we propose a Boolean characterization of three-dimensional simple points in cubic grids. This characterization requires the checking of 5 basic configurations in the neighborhood of the point considered.

title: Minimal Non-simple and Minimal Non-cosimple Sets in Binary Images on Cell Complexes
abstract: The concepts of weak component and simple 1 are generalizations, to binary images on the n-cells of n-dimensional cell complexes, of the standard concepts of “26-component” and “26-simple” 1 in binary images on the 3-cells of a 3D cubical complex; the concepts of strong component and cosimple 1 are generalizations of the concepts of “6-component” and “6-simple” 1 Over the past 20 years, the problems of determining just which sets of 1's can be minimal non-simple, just which sets can be minimal non-cosimple, and just which sets can be minimal non-simple (minimal non-cosimple) without being a weak (strong) foreground component have been solved for the 2D cubical and hexagonal, 3D cubical and face-centered-cubical, and 4D cubical complexes This paper solves these problems in much greater generality, for a very large class of cell complexes of dimension ≤4.

title: On the detection of simple points in higher dimensions using cubical homology
abstract: Simple point detection is an important task for several problems in discrete geometry, such as topology preserving thinning in image processing to compute discrete skeletons. In this paper, the approach to simple point detection is based on techniques from cubical homology, a framework ideally suited for problems in image processing. A (d-dimensional) unitary cube (for a d-dimensional digital image) is associated with every discrete picture element, instead of a point in /spl epsi//sup d/ (the d- dimensional Euclidean space) as has been done previously. A simple point in this setting then refers to the removal of a unitary cube without changing the topology of the cubical complex induced by the digital image. The main result is a characterization of a simple point p (i.e., simple unitary cube) in terms of the homology groups of the (3/sup d/-1) neighborhood of p for arbitrary, finite dimensions d.

title: Geometry of digital spaces
abstract: In the recently published Ref. 1 the author survey a number of aspects of the geometry of digital spaces. In this article we exemplify the approach of that book, by providing a self-contained proof of one of its final result which is to do with the correctness and the characterization of the output of a general purpose boundary-tracking algorithm.

title: A 3D 6-subiteration thinning algorithm for extracting medial lines
abstract: Thinning is a frequently used method for extracting skeletons in discrete spaces. This paper presents an efficient parallel thinning algorithm that directly extracts medial lines from elongated 3D binary objects (i.e., without creating medial surface). Our algorithm provides good results, preserves topology and it is easy to implement.

title: A Parallel 3D 12-Subiteration Thinning Algorithm
abstract: Thinning on binary images is an iterative layer by layer erosion until only the “skeletons” of the objects are left. This paper presents an efficient parallel thinning algorithm which produces either curve skeletons or surface skeletons from 3D binary objects. It is important that a curve skeleton is extracted directly (i.e., without creating a surface skeleton). The strategy which is used is called directional: each iteration step is composed of a number of subiterations each of which can be executed in parallel. One iteration step of the proposed algorithm contains 12 subiterations instead of the usual six. The algorithm makes easy implementation possible, since deletable points are given by 3×3×3 matching templates. The topological correctness for (26, 6) binary pictures is proved.

title: Characterisations of simply−connected finite polyhedra in 3−space
abstract: (i) Y is simply-connected (ii) The first (integral) homology group of Y is trivial (iii) The first (integral) Betti number of Y is zero (iv) The first (integral) cohomology group of Y is trivial (v) The Euler Characteristic of Y is equal to the number of components of S\ Y (vi) Y has one (and hence all six) of the Phragmen-Brouwer properties [6] (The Phragmen-Brouwer properties are listed in the Appendix.)

title: Strongly normal sets of contractible tiles in N dimensions
abstract: The second and third authors and others have studied collections of (usually) convex ''tiles''-a generalization of pixels or voxels-in R^2 and R^3 that have a property called strong normality (SN): for any tile P, only finitely many tiles intersect P, and any nonempty intersection of those tiles also intersects P. This paper extends basic results about strong normality to collections of contractible polyhedra in R^n whose nonempty intersections are contractible. We also give sufficient (and trivially necessary) conditions on a locally finite collection of contractible polyhedra in R^2 or R^3 for their nonempty intersections to be contractible.

title: Parallel Thinning Algorithms on 3D (18, 6) Binary Images
abstract: Thinning algorithms on binary images are used to generate skeletons that preserve the same connectivity structures as the objects in the original images. Two kinds of skeletons may be appropriate for 3D thinning algorithms: digital curves and digital surfaces. We propose two thinning algorithms on 3D (18, 6) binary images. One algorithm generates skeletons as digital curves and the other algorithm generates skeletons as digital surfaces. Both algorithms are 6-subiteration algorithms?in each iteration, they are applied alternatively to delete border voxels from each of the six directions, upper, lower, north, south, east, and west.

title: Surface skeletons in grids with non-cubic voxels
abstract: An algorithm for computing surface skeletons on the face-centered cubic (fcc) grid and the body-centered cubic (bcc) grid is presented. The fcc grid and the bcc grid are three-dimensional grids where the voxels are rhombic do-decahedra and truncated octahedra, respectively. The DT is used to generate the set of centres of maximal balls (CMBs) which are "anchor points" when constructing the skeleton. Simple points are used in order to make the skeleton topologically correct and CMBs to produce a fully reversible skeleton. Using only simple points and the CMBs generates a skeleton with a lot of branches. By using a set of additional conditions for removal and preservation of grid-points, most of these branches are merged into surfaces. For comparison, the algorithm is also implemented for the cubic grid.