"Quad-generated images"
This program shows the visualization of an "image compression" algorithm.
This algorithm divides the image into squares (or rectangles). Starting with a square of the same size of the image, it calculates:
- The average color: Adding up each R, G, B and A component separately for each pixel, and dividing by the total amount of pixels in the square.
- The error: Difference between the averaged color and the R, G, B, A component for each pixel.
Then, the algorithm will find the square with the highest error (The least refined). Such square will be divided into four sub-squares, halving its size, and again, calculating the average color and error of each sub-square.
The algorithm will be repeated N times until all the squares have an error of 0.
This algorithm can be implemented by using both a Quadtree structure (as it was first implemented), or an Ordered Sets (as it is implemented on master branch). The differences are in the insertion and search times:
- Finding the rectangle with the highest error: The Quadtree has to iterate through every child, what requires N iterations (and not log(N) as could be expected from a tree). The Ordered Set, since its ordered, the lastest element in the structure will be the desired rect, is constant.
- Inserting the sub-rectangles in the structure: The Quadtree only needs to insert the sub-squares as leafs, what is constant, but the Ordered Set needs to insert AND sort every sub-rectangle by its error, and it takes 4*log(N) iterations.
Precompiled versions for Windows and Linux
Take note that SDL2 and SDL2_image dependencies must be installed first by running the following commands:
$ sudo apt-get install libsdl2-dev
$ sudo apt-get install libsdl2-image-dev
Clone the repo and make.
$ git clone https://github.com/Dibad/Qart
$ cd Qart
$ make
View of the iterative process with every quadtree outlined (Stopped after 4029 iterations, with 12088 squares created).
And a view of the same process but without outlines.
This project idea was shared by Michael Fogleman, so please check his fantastic implementation in Python. Link to his repository