April 2025
Quadtree Image Compression Algorithm
Implementation of Divide and Conquer for Image Compression
A Java-based application developed as part of IF2211 Algorithm Strategy course, focusing on image compression using the Quadtree method. This divide-and-conquer approach recursively divides images into smaller blocks based on color similarity.
The program implements five error metrics to determine block homogeneity and supports GIF visualization of the compression process, providing an educational tool to understand how quadtree structures adapt to different image areas.
Key Features
- Implemented five error metrics: Variance, Mean Absolute Deviation (MAD), Max Pixel Difference, Entropy, and SSIM
- Developed GIF visualization feature to illustrate the compression process step-by-step
- Applied divide and conquer algorithm for efficient recursive image partitioning
- Designed modular architecture with separate classes for different error metrics and compression controllers
- Optimized compression quality by focusing on detailed image sections while reducing memory usage for uniform areas
Error Metrics Implemented
Variance
Measures color variation within image blocks
Mean Absolute Deviation (MAD)
Calculates average absolute deviation from mean color
Max Pixel Difference
Finds maximum color difference between pixels
Entropy
Measures information content and color distribution
SSIM
Structural Similarity Index for perceptual quality assessment
GIF Visualization
Step-by-step compression process animation
Technical Implementation
Algorithm: Divide and Conquer approach that recursively partitions images into quadrants based on color homogeneity thresholds.
Data Structure: Quadtree implementation where each node represents an image region with four children for sub-regions.
Optimization: SSIM metric provides the most stable threshold (0-1) for target compression percentage control.