Thumbnail
Access Restriction
Subscribed

Author Gargantini, Irene
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Digital images ♦ Image encoding
Abstract A quadtree may be represented without pointers by encoding each black node with a quaternary integer whose digits reflect successive quadrant subdivisions. We refer to the sorted array of black nodes as the “linear quadtree” and show that it introduces a saving of at least 66 percent of the computer storage required by regular quadtrees. Some algorithms using linear quadtrees are presented, namely, (i) encoding a pixel from a 2n × 2>n array (or screen) into its quaternary code; (ii) finding adjacent nodes; (iii) determining the color of a node; (iv) superposing two images. It is shown that algorithms (i)-(iii) can be executed in logarithmic time, while superposition can be carried out in linear time with respect to the total number of black nodes. The paper also shows that the dynamic capability of a quadtree can be effectively simulated.
Description Affiliation: Univ. of Western Ontario, London, Ont., Canada (Gargantini, Irene)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 25
Issue Number 12
Page Count 6
Starting Page 905
Ending Page 910


Open content in new tab

   Open content in new tab
Source: ACM Digital Library