Results

The evaluation of the FHS algorithm is divided in two subsections. The segmentations provided by the proposed method are subjectively evaluated and compared to the segmentations generated by other well known segmentation algorithms. Results are given in subsection 6.1.

While the subjective evaluation can demonstrate the ability of the algorithm to produce quality segmentations on some images and give coarse insight into the algorithm properties, if the algorithm is going to be used in an automated system, the objective numerical results on large dataset are desired [33]. The extensive experimental evaluation is performed and results are given in subsection 6.2.

Subjective evaluation

FHS technique was applied to the images from the Berkeley segmentation Dataset (BSD) [32] and other images collected by authors. The segmentations provided by the FHS algorithm are shown in Fig. 2. For larger value of the parameter $h_0$ less detailed segmentations are obtained. Variable bandwidth ensures that details in different scales are perceived for both values of $h_0$. Segmented areas in Fig. 2(g) and Fig. 2(h) are shown with segments smaller than the predefined size merged with the most similar neighbour.

The segmentations obtained by the proposed algorithm are compared to the segmentations generated by other well known segmentation algorithms in Fig. 3. The methods used in the comparison include two color-based techniques, namely the Mean Shift segmentation [1] and the Efficient Graph-Based segmentation [4]. Results are also compared with the JSEG algorithm [20] which incorporates texture information in segmentation process and the Gradient Network Method (GNM) [21] which generates final segmentation based on color gradients. The results demonstrate the ability of all algorithms to produce correct segmentations. The FHS algorithm can provide eligible segmentations for an ample parameter range, with details on finer scale perceived for smaller values of $h_0$. Smaller $h_0$ should be used if the FHS algorithm is going to be implemented as the color quantization preprocessing step of a segmentation technique which builds up final segmentation upon preprocessed over-segmented image [21].

Experimental evaluation

The FHS method is evaluated with respect to the quality of provided segmentation and efficiency of the algorithm. Our aim is to show that the proposed method is comparable in quality with other widely adopted low-level segmentation techniques, while running times are several times faster. Proposed method is compared with two existing segmentation methods based on same attributes. In the Mean Shift (MS) segmentation algorithm [1], widely adopted in the vision community, MS procedure [23,24] is implemented in the five-dimensional joint spatial-range domain. The multivariate kernel is defined as the product of two radially symmetric kernels controlled by the spatial bandwidth $h_s$ and the range bandwidth $h_r$. MS algorithm is integrated into the Edge Detection and Image Segmentation (EDISON) system [34], with source code available at http://www.caip.rutgers.edu/riul/.

Efficient Graph-Based Image Segmentation algorithm [4] is created with the intention to provide computationally efficient approach which can be used in wide range of computer vision tasks, which is consistent with our motivation. The algorithm uses adaptive thresholding criterion based on the degree of variability in the neighboring regions of the image, and single controlling parameter $\kappa$ defining the scale of observation. The algorithm runs in time nearly linear in the number of graph edges. Source code of the algorithm is available at http://people.cs.uchicago.edu/~pff/segment/.

Methodology

The evaluation database is the BSD dataset [32] which contains 300 images of complex natural scenes. For each image several ground truth (GT) segmentations are available. The BSD collection is divided into training and testing data sets. As non of the evaluated algorithms has learning strategy implemented, algorithms are evaluated on all images. For the assessment of the quality of provided segmentations we adopt the evaluation methodology proposed in the work of Pantofaru and Herbert [33]. The performance measure is the Normalized Probabilistic Rand index ($NPR$) [35], quantifying the degree of agreement of an algorithmically generated segmentation with a set of manually created GT segmentations. The $NPR$ index is computed from the Probabilistic Rand index ($PR$) [36] by normalization with respect to its expected value. The expected values are modeled using all of the ground truth data, not just the data for the particular image, with no assumptions on the number and the size of regions in the segmentation. The normalization step facilitates meaningful comparison of scores between segmentations of different granularity of the same image, as well as across segmentations of different images.

Results

The evaluation results are summarized in Fig. 4 and Fig. 5. Each algorithm is evaluated for a reasonable set of parameters settled in [33]. In all plots, the label 'MSE' refers to the mean shift based algorithm as implemented in the EDISON system, with parameters values taken from $h_s \in [4, 16]$ and $h_r \in [4, 16]$. The label 'EGB' refers to the efficient graph-based segmentation algorithm with $\kappa \in [25, 300]$. The fixed bandwidth $h_0 \in [4, 16]$ for the 'FHS' algorithm is taken from the same set of values as the range bandwidth of the MSE algorithm.

The quality of the segmentations provided by each algorithm is presented in Fig. 4. Plot (a) shows the maximal $NPR$ index of each image for each algorithm. Indices are plotted in increasing order for a particular algorithm, thus the same index may not represent the same image across the algorithms. Plot (b) represents maximal $NPR$ index distribution. Best results are achieved by the MSE algorithm, followed by the FHS algorithm. Results achieved by the MSE and the FHS are roughly the same in the mean $NPR$ index achieved for all parameter combinations, presented in plot (c). Better stability with respect to the parameter choice is confirmed in the distribution of the standard deviation shown in plot (d), with more left-biased standard deviation of the FHS when compared to other two algorithms. Stability with respect to the parameter choice is achieved by implementing variable bandwidth. Moreover, the MSE algorithm has two controlling parameters thus it is reasonable to expect higher reception to mutual influences of parameters. For the majority of images all algorithms have the ability to produce segmentations of the acceptable quality with above-zero maximal $NPR$ index. The EGB algorithm demonstrates the lowest performance, with below-zero maximal $NPR$ index for several images.

In order to estimate efficiency of the evaluated algorithms, series of experiments are conducted measuring algorithm running time for different parameters and image resolutions. All tests are carried out on the same architecture with equal run-time conditions ensured. Results are presented in Fig. 5. Plots (a), (b) and (c) show run-time of all three algorithms in the logarithmic scale. Average running time on all images in the BSD collection is shown, with axes on all three plots kept constant to facilitate comparison. Run-time of the FHS algorithm decreases for higher $h_0$ as this parameter determines discretization of the feature space. For $h_0 > 4$ the FHS algorithm runs faster than the EGB algorithm, which is not sensitive to the parameter $\kappa$. Complexity of the MSE algorithm results in longer running times than the other two algorithms.

Running times for images of different resolutions are shown in plot (d). Algorithms are applied on ten images of each resolution and average running times are presented in log-log scale. Controlling parameters for each algorithm are taken to be values for which the particular algorithm scores the best performance on the BSD collection. Running times of all algorithms are nearly linear with the size of the input data. FHS is the fastest algorithm which is consistent with efficiency achieved on the BSD collection and theoretical complexity analysis.