PukiWiki contents have been moved into SONOTS Plugin (20070703)

Project: Normalized Cuts and Image Segmentation

Table of Contents


An Image Segmentation technique based on Graph Theory, Normalized Graph Cut.


The report is available at fileNcutImageSegment.pdf

First Edition: Oct 2006 Last Modified: Oct 2006
Tag: Scientific ComputerVision Segmentation Matlab

Fundermental Idea

Refer [1]

Math Equation or Algorithm [1]

Given an image sequence I. Construct a weighted graph G = (V,E) whose each node is each pixel of the image I. Let N be the number of nodes (pixels), i.e., |V|.

Step 1

Construct an \text{NxN} symmetric similarity matrix W as:

w_{ij} = exp{\frac{- ||F(i)-F(j)||^2_2}{\sigma_I^2}} * \left{ exp{\frac{- ||X(i)-X(j)||^2_2}{\sigma_X^2}} \text{ if} ||X(i)-X(j)||_2 < r\\0 \text{                    otherwise.}\right. \text{   (11)}

where \mathbf{X}(i) is the spatial location of node i, i.e., the coordinates in the original image I, and F(i) is a feature vector defined as:

  1. F(i)=1 for segmenting point sets,
  2. F(i)=I(i), the intensity value, for segmenting brightness (gray scale) images,
  3. F(i) = [v,u \cdot s \cdot \sin(h), v \cdot s \cdot \cos(h)](i), where h,s,v are the HSV values, for color segmentation,
  4. F(i) - [|I * f_1|,....,|I * f_n|](i), where the f_i are DOOG filters at various scales and orientations, for texture segmentation.

Let \mathbf{d}_{i} = \textstyle \sum_{j} w_{ij} be the total connection from node i to all other nodes.
Construct an \text{NxN} diagonal matrix D with \mathbf{d} on its diagonal.

Step 2.

Solve (D - W)\mathbf{y} = \lambda D \mathbf{y} (12) generalized eigensystem and get a eigenvector with the second smallest eigenvalue. Fortunately, matlab has a function, eigs, to solve eigensystem.

Step 3

Use the eigenvector to bipartition the graph. In the ideal case, the eigenvector should only take on two discreate values, and the signs tell us exactly how to partition the graph (A =\{ V_i | \mathbf{y}_i > 0 \}, B = \{ V_i | \mathbf{y}_i <= 0 \}).

However, \mathbf{y} is relaxed to take real values, therefore, we need to choose a splitting point. There are several ways such as

  1. Take 0
  2. Take median
  3. Search a splitting point which results in that Ncut(A, B) is minimized.

The splitting point which minimizes Ncut value can be found by repeating calculation of

\frac{\mathbf{y}^T(D - W)\mathbf{y}}{\mathbf{y}^T D \mathbf{y}} \text{           (5)}

where \mathbf{y} = (\mathbf{1} + \mathbf{x}) - b (\mathbf{1} - \mathbf{x}) where b = k / ( 1 - k ) where

\textstyle k = \frac{\sum_{x_i > 0} \mathbf{d}_i}{\sum_i \mathbf{d}_i}

where \mathbf{x} is an N dimensional indicator vector, x_i = 1 if node i is in A and -1, otherwise. The optimal splitting point is generally around the mean value of the obtained eigenvector. Fortunately, matlab has a function, fminsearch, for this purpose.

Step 4

Repeat bipartition recursively. Stop if Ncut value is larger than a prespecified threshold value (Large Ncut value means that there is no clear partition point any more). Furthermore, stop if the total number of nodes in the partition is smaller than a prespecified threshold value (this is another criteria added newly to the paper's algorithm.)

Source Codes

If anything which is not listed here is required, try to see

Experiments and Results

Gray Scale Image

Code to call NcutSegment.m

Input Image (100x67) [4]




Color Image


Input Image (100x67) [4]





Input Image (160x160) [3]


Results by the program provided by Dr. Shi [3]

Time took: 77.6793 seconds


Results by my program

Time took: 22.664045 seconds




My program worked reasonably fast for small images (e.g., 100 x 64), but it worked impractically for large images (e.g., 481 x 321). In particular, the calculation of eigen vectors and weight matrix required a lot of time, therefore, more efficient algorithm to compute them, and efficient tricks for memory management is required (they requires much of memory). Of course, we should consider implementing in low level languages such as C and using matlab mex, or running on powerful machines to shorten computation time, too.

My program worked faster than the program provided by Dr. Shi although his program is implemented by C and using matlab mex. It is probably because the Dr. Shi's program is more complicated or my matlab trick for fast computation worked well.

In order to obtain desired results, I had to carefully choose parameters. This is another optimization issue which must be solved in the future.

I again had to carefully choose parameters so that eigs function does not return errors on computation. I will look at the computation of eigenvectors if I have a chance.