This document represents the final report for our project done for Prof. Gregory Dudek in Computer Graphics (308-557) course taught at McGill University. I have chosen the area of quad trees, and particularly the effect and advantages (and disadvantages) of depth on the image outputted after compression in the quad trees. The definifition of a picture is a two-dimensional array, where the elements of the array are black or white points; two-dimensional arrays are very widely used to represent different kind of pictures Here is an example of an image represented as a two-dimensional array. Each pixel is an element of the array.
Most of the time, the 'gif' and 'jpeg' standards provide performance hard to imitate , so we are going to test if even with less data stored we can have also a good picture . 2) Brief Overview a)Basic Algorithm Quad tree Decomposition consists in subdividing the image into blocks that are more homogeneous than the image itself. This technique works by dividing the square image into four equal-sized squared blocks. If block meets the criterion, it is not divided any further.If it does not meet the criterion (only black or only white value), it is subdivided again into four blocks, and the test criterion is applied to those blocks.
This process is repeated iteratively until each block meets the criterion. s 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 graph. 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 (graph). Graph: 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 dec mpose 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.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) References1 http://cs.ubc.ca/~pcarbo/cs251/welcome.html (picture representation using quadtrees)2 image compression using fixed length quadtree coding[Tsong wuu linDepartment of information and Computer science, Soochow University]3 http://ltswww.eplf.ch/pub_files/brigger/thesis_html/node21.html
