Project $3$: Image Processing

Topic: QuadTree & Circular Queue

DUE: Sunday, March $31,11$:$59$pm

Extra Credit for Early Submission!

Introduction

The QuadTree data structure is a special type of tree where the inner nodes have exactly four

children. The goal of this tree is to divide a $2$D space into four quadrants and have each child

represent one of them. Each quadrant can further divide into four smaller quadrants and so forth

according to the level of detail we want to achieve. But not all the partitions need to have the same

level of detail, i$.$e$.$ some leafs can be deeper than others. So$,$ in practice, the quadtree is usually not a

perfect tree. Figure $1$ depicts an example of a quadtree that does the minimum partitioning required in

order for each point in space $($A$,$ B$,$ C$,$ D$,$ E$,$ F$)$ to be represented by a distinct leaf.

Quadtrees have various applications in domains like image processing, spatial indexing, collision

detection, storing of sparse data, and others. This project is inspired by the use of quadtrees in image

processing but you don$$t need to have a background on this topic. All you need to know is described in

this document.

Figure $1$: QuadTree partioning