This paper introduces a Quadtree image segmentation technique to be used for image annotation. The proposed method is able to efficiently divide the image in homogeneous segments by merging adjacent regions using border and color information. Our method is highly efficient and provides segmentations of acceptable performance; the segments generated with the proposed technique can be used for automatic image annotation and related tasks (e.g., object recognition). A benefit of our proposal is that it allows us finishing the segmentation at any time by controlling the desired level of the detail for the segmentation; hence, the method is suitable for time restricted scenarios. We compare the performance of an image annotation technique trained on hand labeled images and tested in images segmented with different segmentation algorithms. We found that the best results were obtained when the annotation method was tested in images segmented with the quadtree formulation. Our results give evidence of the efficiency and effectiveness of the proposed method.
Although it is possible to annotate images without a previous segmentation, in general region-level
image annotation results in labels of better quality [
The proposed method for image segmentation is a simplified quadtree technique based on the following guidelines: recursively divide the image using a quadtree approach, merge homogeneous and similar quadtrees’ regions based on borders and color information, process and discard large image regions as fast as possible, prefer detection of large objects, avoid noise in result segments and provide any-time segmentation. Our proposal implements the mentioned guidelines by dividing the segmentation process in five steps: (1) edge detection, (2) border processing, (3) color discretization, (4) quadtree scanning and (5) segmentation enhancement. Although our formulation is intended for automatic image annotation usage, it can be used for other tasks that require a fast segmentation implementation. We present preliminary results on the application of the proposed segmentation algorithm in the task of image annotation. Experimental results show that the proposed technique can be very useful for this task and motivates research in several directions.
The rest of this paper is organized as follows. The next section presents background information on quadtree image segmentation. Section 3 introduces the proposed method. Section 4 describes the experimental settings we adopted for the evaluation of the proposed segmentation method. Section 5 reports experimental results obtained from our formulation. Finally, Section 6 presents some conclusions and outlines future work directions. 2
This section presents background segmentation on quadtree image segmentation that will be helpful for understanding the rest of the paper. 2.1
According to T. Pavlidis the segmentation of an image I into a set of regions S = fS1; : : : ; Skg should
satisfy the following four main rules [
Si \ S j = f ; 8i 6= j
8Si; P(Si) = true
P(Si [ S j) = f alse; 8i 6= j; Siad jacentS j
(1)
(2)
(3)
(4)
where P(X ) represents the fulfilment of the homogeneous predicate under X . However, achieving
this type of segmentation involves many difficulties. The main issues are due to borders, textures and
illumination changes that make hard to distinguish where objects start and end. Moreover,
segmenting an image is a highly subjective process. Therefore, it is difficult to make everybody agree on one
segmentation or another. Aside these difficulties, most image segmentation algorithms are very time
consuming. For these reasons there is a research trend on image annotation that studies annotation
methods that avoid the use image segmentation [
L. T. Lan and A. Boucher presented a simplified image segmentation process called Weak
Segmentation [
This section describes the proposed technique for image segmentation, which is based on the idea of Dividing the image following a quadtree structure and merging similar adjacent regions. The proposed algorithm for simplified quadtree image segmentation requires the specification of three parameters i) minimum object size (mos), ii) minimum quad size (mqs) and iii) homogeneity threshold (ht). These parameters can be adjusted by the user according to their own needs, although below we provide default values for those parameters. The proposed formulation is divided into the following five stages: (1) edge detection, (2) border processing, (3) color discretization, (4) quadtree scanning and (5) segmentation enhancement. Figure 2 shows the implementation design model. The rest of this section provides a detailed description of each step. 3.1
The first step consists of detecting borders of objects in the image. Borders are important for image
segmentation because they can provide information about object contours. In our proposal, border
information has a crucial influence over the final segmentation results. There exist many border detection
algorithms that provide very good results but they are complex and time consuming. Therefore, we
decided to use the Sobel operator which is a simple and straight forward method to detect image borders [
Border selection consists of building an image that contains only the most relevant borders obtained from step 1. Border relevance is measured by its continuity and length. To be able to evaluate these measures, we first apply the connected components algorithm to the Sobel result and then we calculate the area of each component. We keep all the components whose area suggest the they belong to an object that reaches the mos parameter entered to the algorithm. We call this image Constraints Image. 3.3
Color discretization creates a 6-bit color copy of the image. 2 bits per each RGB component. We choose this small number to speed ups histograms calculations as normalizing and comparing. 3.4
The main step of our method is the quadtree segmentation part, which is described in this section. A quadtree scanning of the image is the core step of the segmentation. The image is divided into four regions, and each of these regions is compared with their adjacent 4 neighbors using a comparison operator. If two regions are evaluated as similar they are merged. Regions that are not merged with any other region are divided in four new regions and the same comparison operation with their new neighbors is done. This process is performed recursively until there are no more regions to divide or the region size has reached the mqs parameter.
The comparison operator takes two adjacent regions and considers the Constraints Image built in step 2. It counts pixel borders on each region and use predefined rules to check if there is a border compatibility between these regions. If no border compatibility is found the operator evaluates them as non similar, otherwise it constructs color histograms for each region and then normalize and eliminate noise in them. Next, it calculates the Euclidean distance between these histograms. If this distance is less than the ht parameter, the regions are evaluated as similar. Regions merged during this step give the shape of the segmentation result. Regions that could not been assigned to any segment due to absence of homogeneity or similarity are ignored and left out of the final segmentation result. This behavior helps our algorithm to produce more homogeneous (noise free) segments.
Due to the progressive approach of this segmentation procedure, we can take advantage of the parameter mqs to shorten the segmentation time according to our needs, although we will always have an approximation to the final segmentation result. This is a desirable property of segmentation methods for time restricted applications such as video processing or CBIR. Figure 3 depicts the quadtree processing of a sample image, it also shows how can different values for the mqs parameter support anytime segmentation. 3.5
The final step of the proposed methodology is the enhancement of segmentation result described in last section. Segmentation enhancement attempts to improve segmentation results in two steps. First, it applies the comparison operator to all segments that intersected during step 4 and merge them accordingly. Second, it looks for segments that do not meet the mos parameter and merges them with the most similar adjacent segment that does. Figure 4 shows an example of image segmentation using our proposal. 3.6
The complexity of the whole process of our proposal is O(N) = N pN, where N = w h is the number
of pixels of the image. Where the complexity of each step of the proposed methodology is as follows: (1)
7 N; (2) 4N; (3) N; (4) 2log4(N 1)6N +C, with C the number of operations required to divide a quadtree;
(5) 2K + K2 + N with K the number of segments found. A segmentation algorithm with complexity of
O(N) = N pN can be considered efficient as most segmentation algorithms are of order O(N2) and
higher [
This section describes the experimental setting we adopted for the evaluation of the proposed segmentation method. The goal of our experiments is: 1) to evaluate the segmentation performance of the proposed method and 2) to evaluate the performance of an annotation method with segments generated with our segmentation technique in terms of segmentation and annotation accuracy.
For the evaluation of the segmentation performance and efficiency we considered three datasets of
images. The first one consists of 18 heterogeneous manually selected images; the second one consists
of 100 randomly selected images from the Berkeley Segmentation Dataset [
The annotation performance was evaluated with a dataset consisting of 500 images taken from the
SAIAPR TC-12 [
The evaluation process for image annotation is as follows. For each set of segmentation results given by each segmentation algorithm for the 500 images, we take each image and match their automatically produced segments with the corresponding manually produced segments. Then we check if the annotation in both segments is the same; more specifically, we estimate the percentage of pixels that were correctly labeled. Intuitively, images receive points for each correct annotation, maximum grade for a perfectly annotated image is 1. The points given for each correct annotation are weighted according to segment’s size. This means that if an image has 3 annotations in its manually annotated version, and one annotation corresponds to a segment that occupies 75% of the total image area, then that segment will give 0.75 points in case it is correctly annotated. The execution time that spent each algorithm to segment the 500 images was also recorded.
Our testing environment was an AMD Turion 64 bits 1.6GHz 1GB RAM laptop running Windows XP. The reason for this choice was that we wanted to assure the performance of our proposal within a common and accessible environment. 5
Sample segmentation results obtained with the proposed method are shown Figure 5. From this figure we can see that segmentations produced with the proposed method are more accurate than those generated with normalized cuts. It is common for normalized cuts to partition regions that belong to the same object in more than a single region, the proposed method, on the other hand, correctly identifies homogeneous segments. One should note that, as stated above, segmentation is a highly subjective process, hence evaluating the quality of segmentations produced with different methods is a subjective task as well. Nevertheless, we believe the segmentations produced with our method provide very useful information about the objects present in the image.
From Table 1 we can see that the Quadtree Segmentation Algorithm produced segments that were
annotated 50% better than those produced with grid segmentation and 35% better than those generated
with normalized cuts. In addition, our proposal segments about 17 times faster than normalized cuts.
Despite the fact that the proposed method was less efficient than the grid approach, the 50% improvement
makes worthwhile using our method. Whereas the improvement over the grid approach is somewhat
expected, the improvement over the normalized cuts technique is an important result, as normalized cuts
has been the most used image segmentation algorithm in the context of automatic image annotation [
We introduced a simple and efficient method for image segmentation, which resulted very helpful for image annotation, as evidenced by experimental results. This is specially true for images with big objects and simple textures. The any time segmentation feature of our proposal in combination with its order of complexity makes it attractive to be used in time restricted environments. For the experiments reported in this paper, parameters were set by trial an error, it would be interesting to develop methods that automatically can tune parameters according the type of images. Future work also includes improving the selection of relevance borders and extending the color and texture features used in the comparison operator, this in order to improve the segmentation results in particular for complex images. The multilevel annotation taking advantage of the hierarchical nature of quadtree is also encouraging. In addition, a parallel implementation of the algorithm can be done in order speed even more our formulation.