Portland State University. Department of Electrical Engineering
Dr. F. Badi'i
Date of Award
Master of Science (M.S.) in Electrical and Computer Engineering
Electrical and Computer Engineering
1 online resource (88 p.)
Trees (Graph theory) -- Data processing, Image processing -- Digital techniques, Parallel processing (Electronic computers)
Image representation plays an important role in image processing applications, which usually. contain a huge amount of data. An image is a two-dimensional array of points, and each point contains information (eg: color). A 1024 by 1024 pixel image occupies 1 mega byte of space in the main memory. In actual circumstances 2 to 3 mega bytes of space are needed to facilitate the various image processing tasks. Large amounts of secondary memory are also required to hold various data sets.
In this thesis, two different operations on the quadtree are presented.
There are, in general, two types of data compression techniques in image processing. One approach is based on elimination of redundant data from the original picture. Other techniques rely on higher levels of processing such as interpretations, generations, inductions and deduction procedures (1, 2). One of the popular techniques of data representation that has received a considerable amount of attention in recent years is the quadtree data structure. This has led to the development of various techniques for performing conversions and operations on the quadtree.
Klinger and Dyer (3) provide a good bibliography of the history of quadtrees. Their paper reports experiments on the degree of compaction of picture representation which may be achieved with tree encoding. Their experiments show that tree encoding can produce memory savings. Pavlidis  reports on the approximation of pictures by quadtrees. Horowitz and Pavidis  show how to segment a picture using traversal of a quadtree. They segment the picture by polygonal boundaries. Tanimoto  discusses distortions which may occur in quadtrees for pictures. Tanimoto [18, p. 27] observes that quadtree representation is particularly convenient for scaling a picture by powers of two. Quadtrees are also useful in graphics and animation applications [19, 20] which are oriented toward construction of images from polygons and superpositiofis of images. Encoded pictures are useful for display, especially if encoding lends itself to processing.
Naderi, Ramin, "Quadtree-based processing of digital images" (1986). Dissertations and Theses. Paper 3590.