I have developed a novel colour image segmentation routine, which uses non-parametric density estimation to achieve clustering of pixels in feature space. A colour image can be represented as three grey-scale images, showing for example the red, green and blue values for each pixel. A three-dimensional grey-level scattergram can therefore be plotted, where the red, green and blue values for each pixel in the original image are used as coordinates to plot points in the scattergram. If the original image contains regions with well-defined and distinct colours, then the points in the scattergram will be distributed in a number of well-defined clusters, centred around the coordinates given by the average colours of the regions. A three-dimensional data density map, showing peaks in the data density at the positions of the clusters, can be produced by convolving the data in the scattergram with a Gaussian kernel. Hill climbing on the data density function can then be used to assign each point in the scattergram to one of the peaks, effectively using the valleys in the density function as decision boundaries. If the peaks are labelled, and each point in the scattergram is assigned the label of the peak it was clustered onto during hill-climbing, then an image of these labels can be produced as output. All of the pixels in any coloured region in the original image will therefore be assigned the label of the peak that region produced in the density map, and so the image of labels shows the colour segmentation of the original image.

The main features of this technique are well-known, but I have introduced a number of novel refinements. Most importantly, I dealt with the problem of scale selection in a fully automatic, statistically motivated way. The traditional problem with this type of algorithm has been the definition of the correct scale for the segmentation i.e. how large a peak in the density function has to be for it to be considered a significant peak. If the scale is too small, then fluctuations due to noise will be counted as peaks, but if the scale is too large then small but salient peaks will be ignored. I solved this problem by computing the density function at a series of knot points, and by placing the knot points according to an estimate of the noise in the original image. Therefore the density function is smoothed at the scale of the measurement accuracy, eliminating peaks due to noise whilst not destroying salient peaks. The knot points divide the feature space into a set of Voronoi cells, and in order to perform the hill climbing in a sensible manner, a constraint is used that does not allow any step in the hill climbing to jump across intermediate cells.

The images above show the results of applying the colour segmentation routine to an image of coloured jellybeans obtained from the University of Southern California's Signal and Image Processing Institute website. The lower four images show the result of thresholding the segmentation to extract the labels assigned to the different colours of jellybeans.

You can read about the colour image segmentation routine in more detail in this paper, and see its application in a practical machine vision system in this one. Alternatively, download TINA and try it out for yourself.