Thinning algorithms based on quadtree and octree representations

Wai Tak Wong, Frank Y. Shih, Te Feng Su

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


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(N2) or O(N3), which is more efficient than the existing algorithms of O(N3) or O(N4). Furthermore, our thinning algorithms can lessen boundary noise spurs and are suited for parallel implementation.

Original languageEnglish (US)
Pages (from-to)1379-1394
Number of pages16
JournalInformation sciences
Issue number10
StatePublished - Mar 20 2006

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence


  • Image representation
  • Octree
  • Quadtree
  • Skeleton
  • Thinning


Dive into the research topics of 'Thinning algorithms based on quadtree and octree representations'. Together they form a unique fingerprint.

Cite this