Topology preserving operators in three-dimensional image processing

In image processing there is a class of operators which requires topology preservation. Thinning and shrinking are key examples of using such operators. Major problems related to the operators are the characterization, computation, and test of sufficient conditions which preserve topology. In the 2D cases, these problems are now well understood for both sequential and parallel operations. For example, "deleting only simple sets" preserves topology for reduction operators. These sufficient conditions could be characterized by using only the information in local neighborhoods, while parallel cases require larger local support since more than one point could change states simultaneously. To extend to 3D the solutions to these problems will be much more difficult due to the increase of sizes in the local neighborhood and image space. But it is harder to deal with 3D topology also because of 3D holes (a topological characteristic which does not exist in 2D). Lately, more sound research in these fields and growing demands in using 3D topology preserving operators for medical images motivate our interest in pursuing solutions to the problems. In our study, we tried to supplement the solutions for (26,6) connectivity on 3D rectangular grid by proposing a variety of new time-efficient computations of topological functions and concise topology preservation tests for parallel reduction operators. In addition, two new fast parallel thinning algorithms using fully parallel and 6-subiteration computational models are introduced. We further tried to investigate the use of the face-centered cubic (FCC) grid, which might have advantages in reducing kernel complexity, for topology preserving operators. The similar work on rectangular grid is extended to the FCC grid. As a result, new characterizations of simple points in FCC grid are given and proved for the (18,12) and (12,12) image definitions. Further, new time-efficient computations of topological functions for (18,12) connectivity are proposed, and new topology preservation tests for parallel reduction operators for (18,12), (12,18), and (12,12) connectivity are given. We also propose a new fast parallel thinning algorithm using 8-subiteration notions for (18,12) connectivity. Performance comparisons between the computation of topological functions are evaluated in terms of storage, execution time, and function coverage. We test all of our new and existing parallel thinning algorithms on a set of synthetic images and give some quantified and visual comparison.