Operations on Images Using Quad Trees
- 1 April 1979
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. PAMI-1 (2), 145-153
- https://doi.org/10.1109/tpami.1979.4766900
Abstract
A quad tree for representing a picture is a tree in which successively deeper levels represent successively finer subdivisions of picture area. An algorithm is given for superposing N quad trees in time proportional to the total number of nodes in the trees. Warnock-type algorithms are then presented for building the quad tree for the picture of the boundary of a polygon, and for coloring the interior of such a polygon. These algorithms take O(v + p + q) time, where v is the number of polygon vertices, p is the polygon perimeter, and q is a resolution parameter. When the resolution q is fixed, these algorithms are asymptotically optimal.Keywords
This publication has 6 references indexed in Scilit:
- Raster scan approaches to computer graphicsComputers & Graphics, 1977
- Computer animation surveyComputers & Graphics, 1977
- The Use of Algorithms of Piecewise Approximations for Picture Processing ApplicationsACM Transactions on Mathematical Software, 1976
- Pictorial feature distortion in a pyramidComputer Graphics and Image Processing, 1976
- Picture Segmentation by a Tree Traversal AlgorithmJournal of the ACM, 1976
- Experiments on picture representation using regular decompositionComputer Graphics and Image Processing, 1976