Thinning algorithms based on quadtree and octree representations

Thinning is a critical pre-processing step to obtain skeletons for pattern analysis. Quadtree and octree are hierarchical data representations in image processing and computer graphics. In this paper, we present new 2-D area-based and 3-D surface-based thinning algorithms for directly converting quadtree and octree representations to skeletons. The computational complexity of our thinning algorithm for a 2-D or a 3-D image with each length N is respectively O(N-2) or O(N-3), which is more efficient than the existing algorithms of O(N-3) or O(N-4). Furthermore. our thinning algorithms can lessen boundary noise spurs and are suited for parallel implementation. (c) 2005 Elsevier Inc. All rights reserved.