Normalized Cuts Segmentation Code, for MATLAB

Code written by: Timothee Cour (INRIA), Stella Yu (Boston College), Jianbo Shi (UPENN)
(c) 2004 University of Pennsylvania, Computer and Information Science Department.

This is a Matlab/C++ implementation of Normalized Cuts for image segmentation and Data Clustering.

Download

download Ncuts code (ncut_9.zip)   new (January 22, 2010): release of all c++ source mex files compatible with matlab R2009b.

This software is made publicly for research use only. It may be modified and redistributed under the terms of the GNU General Public License.

see also linear time multiscale normalized cut image segmentation.

Citation

Normalized Cuts and Image Segmentation, Jianbo Shi and Jitendra Malik, IEEE Transactions on Pattern Analysis and Machine Intelligence(PAMI) 2000

Description 

Data Clustering with Normalized Cuts

Demo step by step

Given a weighted graph, W, find a graph partition with Normalized Cuts. 
image segmentation
eigenvectors
Image Segmentation with Normalized Cuts

Demo step by step

Given an input image I, construct a pixel-pixel pair-wise similarity matrix W based on Intervening Contours. Output the image segmentation with Normalized Cuts.

Installation instructions

Make sure you have Matlab (it was tested under R2009b but should probably work in other versions as well). Certain functions might require the Matlab Image Processing Toolbox.

1) After you unzipped the files to mydir,
   put the Current Directory in Matlab to mydir

2) In the matlab command prompt,
   type compileDir_simple to compile the mex files (ignore the error on the C++ non-mex file; needs to be done once)

Synopsis

demoNcutImage

script that shows a demo of image segmentation

demoNcutClustering

script that shows a demo of point cloud clustering

NcutImage

given image "I", segment it into "nbSegments" segments
    [SegLabel,NcutDiscrete,NcutEigenvectors,NcutEigenvalues,W]= NcutImage(I,nbSegments);

ICgraph

compute Intervening Contour based pixel similarity matrix W
    W = ICgraph(I);

ncutW

Given a similarity graph "W", computes Ncut clustering on the graph into "nbSegments" groups;
    [NcutDiscrete,NcutEigenvectors,NcutEigenvalues] = ncutW(W,nbSegments);
 

Release notes

2010, January 22: release version 9: release of all c++ source mex files compatible with matlab R2009b
2006, May 04: release version 8: fixed incompatibility issues with new matlab
2004, June 18: release version 7: initial release

Maintained by Timothee Cour, timothee dot cour at gmail dot com
Last updated: January 22, 2010.