Thumbnail
Access Restriction
Subscribed

Author Samet, Hanan
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Skeletons ♦ Shape ♦ Size ♦ Quadtrees ♦ Medial axis transforms
Abstract As printedQuadtree skeletons are exact representations of the image andare used because they are observed to yield space efficiently and adecreased sensitivity to shifts in contrast with the quadtree. TheQMAT can be used as the underlying representation when solving mostproblems that can be solved by using a quadtree. An algorithm ispresented for the computation of the QMAT of a given quadtree byonly examining each BLACK node's adjacent and abuttingneighbors.Corrected Abstract (published as corrigendum in CACM 27, 2(February 1984) p. 151)The skeletal and medial axis transform concepts used intraditional image processing representations are adapted to thequadtree representation. The result is the definition of of a newdata structure termed the Quadtree Medial Axis Transform (QMAT). AQMAT results in a partition of the image into a set of nondisjointsquares having sides whose lengths are sums of powers of 2 ratherthan, as is the case with quadtrees, a set of disjoint squareshaving sides of lengths which are powers of 2. The motivation isnot to study skeletons for the usual purpose of obtainingsapproximations of the image. Instead, quadtree skeletons are exactrepresentations of the image and are used because they are observedto yield space efficiency and a decreased sensitvity to shifts incontrast with the quadtree. The QMAT can be used as the underlyingrepresentation when solving most problems that can be solved byusing a quadtree. An algorithm is presented for the computation ofthe QMAT of a given quadtree by only examining each BLACK node'sadjacent and abutting neighbors. Analysis of the algorithm revealsan average execution time proportional to the complexity of theimage, i.e., the number of BLACK blocks.
Description Affiliation: Univ. of Maryland, College Park (Samet, Hanan)
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 26
Issue Number 9
Page Count 14
Starting Page 680
Ending Page 693


Open content in new tab

   Open content in new tab
Source: ACM Digital Library