- Each region divided into 4 quadrants
- Examine if all black or white
- Quadrant with black + white = =grey
- Grey quadrants are subdivided until sub-quadrants are all black or white only
- A unique string of symbols (b,w) to code the tree
- Each g is followed by 4 symbols or four groups of symbols
graph1:
As we can see here we can see how we can obtain only black or white quadrants with a decomposition of gray pixel.
Level 0 Level 1 Level 2 Level 3
Graph2:
So every time we have a gray scale picture we can produce a resulting quadtree as follow (quadtree of a smaller image).
b)Storage of image using pbm format
I choose to use the pbm format because PBM is a portable bitmap format having a very simple definition. The first two lines are composed by a number for identifying the file type (for pbm it is P1), and a second line containing comments.Then the third line contain a width and height for the next line composed of 0’s ,1’s and spaces .
Graph3: pbm file format
P1
# basic.pbm //graph3 example
24 7
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0
0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0
0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 0
0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2) Implementation
My Implementation consist in fact in taking a bpm file , then using “FileInputStream” I manage to read exclusively the list of 1’s and to put them in the array Image[][], which later I will put in its corresponding quadtree.
Then, in order to show the effect of the depth on the resulting image I have a Max_depth which correspond to the maximum depth that my quadtree is going to have. I have an “infinite” maximum depth; the resulting image will be identical to the first one because we will be to decompose the gray pixels until having the exact representation of “black” and white corresponding to them”. But if we have a fixed maximum depth we will have obviously some information because the decomposition of the grey pixel will not be accurate enough.
Graph4:
Example of a quadtree where the maximum is restrained.
3) Results and testing
a) Simple images
As we have seen previously the quadtree is particularly efficient when the image we are decomposing has large areas where we can find the same value(0 or 1) which permit to compress effectively because we will save one value instead of many more.
This is why we can use quadtree in specific areas such as cartography as we can see in graph5.
*Graph5:
Decomposition of a map.
As we can see here, when trying to have information about delimitation between ocean and land, we are interested only by the borders that is why the tree will be deep were you have color difference. And in the other areas the quadtree algorithm will be very efficient and close to the original picture with a depth not high at all.
*here instead of having black and white in my “all_equal”method I have 4 colors
b) Complex images
When we apply quadtree to more accurate pictures, I mean here pictures that contain many different borders and shapes, the algorithm will have to go very deep in the tree, so the compression will not be efficient and almost equal to the bpm format.
When we try to restrict the depth all the borders between the different contours will not be very visible and accurate as the original picture not compressed (graph5).
Graph6:
Quadtree compression on complex pictures and effect of tree depth.
This picture is outputted when we restrict the depth at a high level. The algorithm cannot decompose the grey pixel as black or white,
And when we recompose the picture the result is blurry
In this case the algorithm goes a little deeper in the decomposition of the gray pixel.
Picture used as input.
Pbm file are not as good as jpeg or gif.
4) Conclusion
In this paper, we have tested the effectiveness of the quadtree compression algorithm on different kind of pictures. The algorithm permits to store a whole quadrant (part of the picture) as if it was storing one pixel. The result show that for simple picture, pictures containing large areas with the same color this method of compression permitted to achieve a very good compression scheme, whereas for complex images, in order to store all the necessary data, the recursive algorithm had to go very deep until decomposing every gray value in black or white values. Thus in this case, the algorithm is not very effective because we have to restrain the max depth in order not to run out of memory (for those cases an iterative algorithm could be implemented in order to solve this problem).
5) References
1 (picture representation using quadtrees)
2 image compression using fixed length quadtree coding[Tsong wuu linDepartment of information and Computer science, Soochow University]
3
