Image segmentation

Normalized Cut and Contour Continuity

License: GNU General Public License 3
Source code: cv-ncut.tar.gz

The C++ source code implements two segmentation algorithms:

• Jianbo Shi, Jitendra Malik: Normalized Cuts and Image Segmentation [1]
• Thomas Leung, Jitendra Malik: Contour continuity in region based image segmentation [2]

Normalized cut is a graph cut algorithm, that decomposes a graph by means of its edge weights, such that only edges with low weight are removed. By normalising all edge weights it is guaranteed that both parts of the graph are as large as possible. The nodes of the graph are the pixels of an image, while the edge weights represent the similarity of the pixels connected by the edge. The similarity may be calculated amongst others with the contour continuity algorithm. It does not only take account of existing contours within the image, but also of intuitive contours (e. g. Kanisza triangle). If two pixels are separated by a contour this will result in a high edge weight in the graph.

Documentation

The source archive contains a doc directory containing documentation in HTML and PDF format. The sources consist of four classes and an example application:

• NormalizedCut: This class takes a matrix as input. The matrix contains the edge weights of a graph. It calculates the eigenvectors and a threshold for decomposing the regions.
• ImageCalc: Encapsulates the calculation of similarity and the selection of the regions in the image.
• ContourContinuity: This calculates the orientation energy (contours and their continuation). It also calculates the similarity of pixel pairs depending on the contours between the two pixels.
• Segmentation: Encapsulates the whole segmentation process. It manages and calls the other classes. The segmentation is performed recursively, that’s why more than two regions may be separated.
• test.cpp: This file contains an exemplary main method. It could be called from command line by adding a picture and some other parameter values. The results could be saved to a file otherwise they will show in stdout.

The performance of both algorithms in the current implementation is very bad. Precise discussions on this topic, some example images and a description of the algorithms may be found in Richard Wolsch: Regionenbasierte Bildsegmentierung mit Kantenfortsetzung (laboratory course report in German) [3].