Transform an image into a Quadtree
A fun experiment to discover a data structure
I recently discovered Quadtree and Octree data structures and I had to find an idea to experiment with them. The inspiration came from this nice gif on the Quadtree Wikipedia page.
I thought it was a cool little experiment to try and recreate it. I fired up Jupyter notebook and started to experiment with Python, numpy, and matlplotlib.
Quadtree
A quadtree is a special tree that defines each node as having four children. They are very useful to subdivide a 2D space by splitting it recursively in four quadrants. The Wikipedia page on the subject is very complete and offers a few examples of its use.
Load the image
Obviously, the first thing to do is to load the image and transform it into something I’ll be able to work with. Matplotlib has a cool method called imread that allows to load a file and transform it into a numpy.array object.
The image is a photo of Split, Croatia from user yokok on Flickr. The image is loaded into a three dimensional numpy array representing the height, width, and RGB value of each pixel. Using matplotlib you can simply call plt.imshow to display the image.
Split the image in 4
The next step in the algorithm is to be able to split the image into four “equal” parts. Of course, only images with a pair number of pixels on the height or width can be split into 4 exactly equal parts, but that doesn’t really matter for our algorithm. So let’s split Split.
As you can see, splitting the image into 4 isn’t too complicated, it uses array_split once in one direction, then on the other. You have to use a trick of using map to keep the correct dimensions.
Reconstruct the image back
When we’ll read the image from the quadtree, we’ll have to reconstruct a full image from the four split children.
We can do this easily by using numpy’s concatenate method it takes an axis parameter to determine on which axis to concatenate the array.
Calculate the mean color
Final tool in our toolbox that we need to construct our quadtree, for each node we’ll calculate the mean color. This color will be saved in the node and will be used to display intermediary images.
Again, numpy is a great help, simply configuring the mean method by defining which axis to use allows us to get the mean color.
Quadtree data structure
Finally, we get to the core of the algorithm. I define a Quadtree class and an insert method that allows to insert an image into the Quadtree and a show_image that displays the image at a specific level.
The quadtree structure is a recursive structure with each quadtree containing four other quatree (or none for the leaves).
Insert
The insert method is a method that will be called recursively. A level is passed, starting at 0 for the first node and adding one on each level. It allows us to know when traversing the tree at which level we are.
We save this level as well as the mean color calculated for the current level (for the whole image received). Finally, we save the resolution in order to recreate the image with the same resolution as the one passed.
We check if all the pixels in the image are equal. If that’s the case, we stop here, we’ll be able to recreate the image at the current level by recreating an image from the resolution with the mean color. We save that it’s a leave by setting a flag.
If we have different pixel colors, we create four child quadtree and insert the respective quarter to each tree by calling the insert method passing the current level + 1.
Show image
To reconstruct the image at a specific level, we simply need traverse the quadtree, concatenating each split back into an image that is sent back to the parent caller.
The stop condition of the recursive method call is that the current node level is the same as the one passed in the level parameter, or the current node is a leaf (final = true).
If that’s the case, we create an image of the stored resolution with the mean color.
Conclusion
This was a fun little project that allowed me to understand better how quadtree are built and used. It’s definitely not the fastest method to construct it neither the better way to store the quadtree. There seems to be solutions to store quadtrees in a “flat” manner (in an array) that is very efficient, but I haven’t found an algorithm or samples yet. I’ll probably study that further.
You can find the full Jupyter notebook on my GitHub at https://github.com/Gimly/image-quadtree/blob/master/Transform_image_into_quadtree.ipynb
Thanks for reading!
