A breadth-first quadtree coding scheme for multicolored spatial data

Henry Ker Chang Chang*, Cheng Kuan Tso

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review


In this paper, we apply the newly developed linear quadtree coding technique 2DTE to construct a single multicolored quadtree for a multicolored thematic map. The proposed 2DTE technique is designed on the basis of a Morton sequence, template matching, and the breadth-first traversal order. With the Morton sequence, we can generate the quaternary codes for various functions of a multicolored thematic map; the decision of decomposition is derived using the concept of template matching. The performance, in terms of memory space and time complexity, for the proposed 2DTE technique is analyzed and compared using an agricultural image of four objects. The result of a single multicolored quadtree derived by the breadth-first traversal order is compared with that of a set of linear quadtrees based on Gargantini's method. The experimental results show that the proposed method has an advantage of obvious memory space reduction over the result of Gargantini's method. Besides, theoretic analysis is derived from an image of size 2n × 2n, where n is the resolution parameter and there are 2n × 2n colors. The proposed method needs 8n × 4n-1 bits to encode whereas Gargantini's method needs 12n × 4n-1 bits. The feasibility of the proposed scheme therefore can be verified by the performance comparisons.

Original languageEnglish
Pages (from-to)139-143
Number of pages5
JournalComputers and Geosciences
Issue number2
StatePublished - 03 1996
Externally publishedYes


  • Linear quadtree
  • Multicolored spatial data
  • Two-dimensional template-based encoding (2DTE)


Dive into the research topics of 'A breadth-first quadtree coding scheme for multicolored spatial data'. Together they form a unique fingerprint.

Cite this