Introduction

Segmentation of a complex scene into perceptually logical homogeneous regions is a fundamental step in the process of understanding visual information. This low-level task is often the first step in complex vision systems where the accuracy of the final scene interpretation strongly depends on the quality of provided segmentation. Partitioning an image into non-overlapping regions can be based on different homogeneity criteria, such as gray level, color or texture. Regardless of the attributes used, for an image segmentation algorithm to be broadly useful, the method should be non-parametric in the sense that it should not rely upon a priori knowledge, like number of segments or implicitly assumed shape [1]. The objective of a low-level segmentation should not aim to produce a final segmentation. Instead, it should use low-level attributes to suggest candidate partitions, while higher-level knowledge can be used to select among these for the further processing [2]. Externally, the algorithm should be operated with a small set of intuitively clear controlling parameters. These should be used to control low-level processing, based on task specific interpretations derived at higher levels [3]. Real time processing enforces constraints for the segmentation algorithm, making a computational complexity a central issue. The efficiency of the existing algorithms is still far from other low-level procedures such as edge detection [4]. Our motivation was to provide a computationally efficient low-level segmentation tool that can produce high quality segmentations.

The proposed segmentation algorithm relies on clustering of pixels in the feature space spanned by color coordinates. Clusters are represented by hills in the multidimensional color histogram estimated in two steps. Initial density is estimated by counting pixels which populate each cell in the discretized color space. Afterwards variable kernel density estimation [5] is applied to compensate the effect of scale variations in the input data. Revealed clusters of pixels are mapped to image segments, spatially continuous regions in the image.

The rest of the paper is organized as follows. The overview of the related work is given in Section 2. In Section 3 important concepts of density-based clustering and kernel density estimation are reviewed. In Section 4 we propose the general grid-based clustering technique. The image segmentation algorithm based on the technique introduced in Section 4 is proposed in Section 5, followed by evaluation results in Section 6. Conclusion is given in Section 7.