Connected component labeling with linear octree

摘要

The representation and manipulation of 3D objects are important for applications such as computer graphics, pattern recognition, robotics and medical imaging. As a consequence, a considerable amount of research is being carried out in data structures for 3D representation. Among these structures, the linear octree is a hierarchical pointerless representation, which stores object elements as a list of codes. Several algorithms have been proposed for linear octrees, including computation of topological properties and connected components labeling. In this paper, we are concerned with this last operation. However, the techniques we use are not limited to this case. We first introduce a new search technique, which does not make use of neighbor finding techniques that require the location of a nearest common ancestor. Instead, we use a table of pointers in the list. The computational cost of our algorithm has an order of O(N), where N is the number of elements in the list. The memory requirements of the pointer's table is of order O(n), for an 8n volume. In the second part of the paper, we come to the connected component labeling. Instead of the usual label using n digits, we use a hierarchical labeling, which creates a tree within each component. Its advantages are threefold. Firstly, we do not use an equivalence table. Secondly, in this particular case, our neighbor finding technique requires only O(1) pointers instead of O(n). But its main feature is a memory requirement of order O(N) for the labels, instead of Θ(n × N).