This Java applet is intended to illustrate the following three algorithms for image segmentation:
MS1, a mean-shift algorithm accelerated by using spatial discretisation (see reference [1]).
GBMS, the Gaussian blurring mean-shift algorithm (see reference [2]).
GBMSa, an accelerated version of GBMS (see reference [2]).
The basic idea underlying mean-shift algorithms is to define a density function (specifically, a Gaussian kernel density estimate) on the pixels of the image and iteratively move the pixels to the modes of the density function (in blurring mean-shift algorithms, the density is updated itself at each iteration). Each pixel is represented by a feature vector in a higher dimensional space (3D for greyscale, 5D for colour) of location (x,y) and intensity (z) or colour value (r,g,b). The feature vectors (pixels) that converge to the same mode are clustered into the same segment. For full details, see the references.
The applet panel below contains 3 panels horizontally:
Left panel: the loaded image.
Middle panel: the intermediate output of the algorithm, displayed as the feature space of position and value (3D for greyscale images, 5D for RGB images), projected on the position features (x,y) and enlarged to show the details more clearly.
Right panel: the segmented image (when the algorithm finishes), where each segment is plotted using an arbitrary colour.
The applet embedded in this web page can only load a predetermined set of images and cannot save the segmented image. You can download a standalone version of the Java applet that does not have these limitations.
To use the applet:
Load an image of dimensions less than or equal to 256×256 pixels.
Choose an algorithm from the drop down menu.
Modify the values of the user parameters (or keep the default ones).
Press GO! and watch the algorithm run.
Save the result or run it again with a different image, algorithm or values.
The runtime of the algorithms is quadratic on the number of pixels (a few seconds with a 64×64 image, a few minutes with a 128×128 image).
User parameters: the main parameter to change is σ, in order to obtain more or fewer segments.
σ: the kernel width in pixels of the kernel density estimate. It implicitly determines the number of segments (bigger σ ⇒ fewer segments).
Feature scale s: this controls the influence of the pixel location vs the intensity/colour values. If a pixel has 2D location (x,y) and intensity z (1D for greyscale image and 3D for colour image), then the algorithm uses a feature vector (x,y,s⋅z).
Radius r: the size of the neighbourhood used to compute mean-shift updates, defined as a square window of radius r pixels centred on each pixel. For example, r=3 means that to compute the mean-shift update for the pixel at location (5,7), all pixels with location (x,y) satisfying |x−5|≤3, |y−7|≤3 are considered as neighbours. A radius of 0 means every pixel in the image is considered a neighbour; this gives better results but is slower.
maxit (GBMS, GBMSa only): maximum number of iterations. The algorithms may stop earlier depending on the convergence criterion.
Discretisation level n (MS1 only): the size of the spatial grid in MS1. The larger the better the approximation to the exact mean-shift algorithm, but the slower.
References
Matlab software and animations are also available in the publications page.