Quadtree Segmentation

1. PROJECT SYNTHESIS

The theme of my project is the quadtree segmentation. A quadtree is a tree whose nodes are either leaves of have four children. The algorithm implies a division of the image intro four regions –called children. If one child has more than one color it is further sub-divided into four quadrants. This is done for the compression of the image.

The program that I have used is Borland C++ Builder 6 because it is a rapid application development environment and because of the familiarity with C++ programming language that I have. The implemented solution is a top-down procedure.

The obtained result is the quadtree segmentation with two parameters that can be modified by the user in order to use the preferred thresholds for the size of the smallest block and the minimum difference for which an area is considered homogeneous.

The original element refers to the method of calculation of homogeneity of a region and the use of the recursive function.

Quadtree segmentation for coding of gray-level images is attractive for a number of reasons. One is the relative simplicity compared to other methods ,which makes it an attractive method. The adaptivity of the decomposition is another advantage. The algorithm allows to change the previously mentioned parameters in order to get the desired result. Another advantage refers to the compression property.

One limitation, but also a future development, is the applicability of the algorithm to color images.

2.ACTIVITIES PLANNING

Table 1. Main activities

3. THEORETICAL APPROACH

Quadtree decomposition is a simple technique for image representation at different resolution levels. This representation is successfully used in binary image compression algorithms.A natural gray-level image usually can be divided into different size regions with a variable amount of details and information. Such segmentation of the image is useful for efficient coding of image data. Quadtree decomposition is a powerful technique which divides the image into 2-D homogeneous (in the property of interest) regions, i.e., produces the segmentation. The decomposition builds a tree. Each tree node has four children and it is associated with a uniquely defined region of the image. It is obvious that the root is associated with the whole image.[Shus94].

As in Figure 1, when quadtree decomposition is used for image compression, the resulting tree is coded. The coding procedure includes coding of the tree structure information and coding of the leaf information. We can assign “1” to the parent node and “0” to the leaf. To each leaf a parameter (or parameters) that describes the intensity of the corresponding subimage will also be assigned. Obviously, the image pixels are always leaves, so the tree structure coding can be stopped one level before the bottom level.

Quadtrees are typically constructed by top-down or bottom-up methods, although other constructions are possible. It is well known, and also demonstrated by this simple Figure 1. Quadtree coding

example, that the bottom-up procedure is superior;

therefore it is preferred for usage in the suggested algorithm.

As seen in Figure 2, in top-down construction a judgement is first made as to whether the entire block can be represented by a single leaf or whether it must be divided into four subblocks. If the block is divided, then a binary decision is made for each subblock to determine whether it needs further division, and so on. Bottom-up construction , as in Figure 3, consists of binary decisions to merge, where construction begins with the smallest possible block size in the quadtree. If all relevant subblocks have been combined into a larger block, then a decision is made whether to combine the larger blocks into a yet larger block, and so on. Any arbitrary method could likewise determine the desired subdivided structure of an image block.[Sull94]

Figure 2. Top-down quadtree decomposition procedure

Figure 3. Bottom-up quadtree decomposition procedure

The implemented solution is a top-down procedure, that starts with the image as beeing the root node.