Lossy image compression using a QuadTree data structure with adaptive spatial subdivision.
The project was developed as a course project for the Algorithms and Data Structures discipline. The main goal was to investigate how a QuadTree can be used to represent an image with controllable quality loss.
A QuadTree recursively divides a two-dimensional region into four subregions.
For image compression, the algorithm analyzes each region of the image and calculates:
- the average RGB color of the region;
- the average Euclidean color error between the pixels and the average color.
If the average error is greater than a specified THRESHOLD, the region is divided into four quadrants and processed recursively.
If the error is within the threshold, the region is represented by a single color — its average color.
This produces an adaptive representation: areas with relatively uniform colors require fewer nodes, while detailed areas are subdivided more deeply.
Image
│
calculate average
region color
│
calculate average error
│
┌─────────┴─────────┐
│ │
error <= THRESHOLD error > THRESHOLD
│ │
▼ ▼
store one color split into 4
for the region subregions
│
┌──────────────┼──────────────┐
▼ ▼ ▼ ▼
Top-Left Top-Right Bottom-Left Bottom-Right
│ │ │ │
└──────────────┴──────────────┴──────────────┘
│
recurse
The image is first converted into a square whose side length is a power of two. This makes recursive subdivision into four equal regions straightforward.
For each region:
1. Calculate the average RGB color.
2. Calculate the average Euclidean distance
between every pixel and the average color.
3. Compare the error with THRESHOLD.
error <= THRESHOLD
→ create a leaf node representing the region
error > THRESHOLD
→ divide the region into four quadrants
→ recursively process each quadrant
The color distance is calculated in RGB space:
The average error for a region is:
where:
- (N) is the number of pixels in the region;
- (C_i) is the color of a pixel;
- (C_{avg}) is the average color of the region.
The resulting QuadTree stores the average color in each node and recursively stores four child nodes when further subdivision is required.
The decompression process traverses the tree recursively.
If a node has no children, its color is used to reconstruct the corresponding image region.
If a node has children, the algorithm recursively processes its four quadrants.
QuadTree
│
├── leaf
│ └── fill region with node color
│
└── internal node
├── top-left
├── top-right
├── bottom-left
└── bottom-right
│
recurse
This reconstructs an approximation of the original image according to the selected THRESHOLD.
Only a few examples are included here to keep the README compact.
Higher THRESHOLD values allow more regions to be represented by a single color, resulting in stronger compression and greater visual distortion.
The main data structure is a QuadTree node.
Conceptually, each node contains:
Node
├── color
├── topLeft
├── topRight
├── bottomLeft
└── bottomRight
A leaf node represents a homogeneous-enough image region using a single average color.
An internal node represents a region that requires further subdivision and contains four child nodes.
This structure allows the representation to adapt to the spatial complexity of the image.
- C++
- Qt types —
QImage,QColor,QSize,QPoint - Recursive algorithms
- QuadTree data structure
- RGB color representation
Qt is used primarily for image handling and several utility/data types. The core of the project is the algorithm and data structure implementation, rather than Qt application development.
This project was developed as a university course project for the Algorithms and Data Structures discipline in 2023.
The task was to investigate an approach to efficient image representation with possible quality loss using a QuadTree.
The project combines implementation of the data structure with an experimental evaluation of how the compression threshold affects the resulting representation and reconstruction error.
The project demonstrates an adaptive lossy image representation based on a QuadTree.
Instead of applying the same level of detail to the entire image, the algorithm recursively subdivides only those regions whose color variation exceeds the selected threshold. This allows the resulting representation to preserve more detail in visually complex areas while using a coarser representation for relatively uniform regions.
The experimental results show the expected relationship between the THRESHOLD, representation size, and reconstruction error, illustrating the main trade-off of the proposed approach.