Efficient Parallel Thinning of 3d Objects on the Body-centered Cubic Lattice

We consider thinning methods to extract one dimensional skeletons from discrete objects defined on the body-centered cubic (bcc) lattice. In Strand (2004), a condition has been given that guarantees the preservation of the object’s topology in such a thinning process. In this paper, we present stronger conditions that even allow the topological invariant point removal in a parallelized process. These conditions for -simplicity can be efficiently evaluated which leads to a very fast thinning process. We show that -simplicity is a new concept that cannot be obtained by adapting the checking plane conditions of Tsao and Fu to the bcc lattice.Furthermore, we introduce distance information and an optional pruning mechanism into the thinning process to improve the quality of the resulting skeletons. The presented results show that our method generates high quality skeletons that reproduce the symmetries of the models even under the condition of added noise and contain only very few spurious branches. The presented running times demonstrate the linear run-time behavior of our algorithm and the speedup that is achieved by the parallelization.