## Project: Normalized Cuts and Image Segmentation

Table of Contents |

## Abstract

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

**The report is available at NcutImageSegment.pdf**

Tag: Scientific ComputerVision Segmentation Matlab

## Fundermental Idea

Refer [1]

## Math Equation or Algorithm [1]

Given an image sequence . Construct a weighted graph whose each node is each pixel of the image . Let be the number of nodes (pixels), i.e., .

### Step 1

Construct an symmetric similarity matrix as:

where is the spatial location of node , i.e., the coordinates in the original image , and is a feature vector defined as:

- for segmenting point sets,
- , the intensity value, for segmenting brightness (gray scale) images,
- , where are the HSV values, for color segmentation,
- , where the are DOOG filters at various scales and orientations, for texture segmentation.

Let be the total connection from node to all other nodes.

Construct an diagonal matrix with on its diagonal.

### Step 2.

Solve (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 (, ).

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

- Take 0
- Take median
- 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

where where where

where is an N dimensional indicator vector, if node 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

- cvpr:project/NcutImageSegment/NcutImageSegment.m
- cvpr:project/NcutImageSegment/NcutComputeW.m
- cvpr:project/NcutImageSegment/NcutPartition.m
- cvpr:project/NcutImageSegment/NcutValue.m

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]

Results

### Color Image

Code

Input Image (100x67) [4]

Results

### Comparison

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

Code

## Discussions

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.

## References

- [1] Jianbo Shi and Jitendra Malik, "Normalized Cuts and Image Segmentation," IEEE Transactions on PAMI, Vol. 22, No. 8, Aug. 2000. http://www.cs.berkeley.edu/~malik/papers/SM-ncut.pdf
- [2] Graph Based Image Segmentation Tutorial http://www.cis.upenn.edu/~jshi/GraphTutorial/
- [3] MATLAB Normalized Cuts Segmentation Code http://www.cis.upenn.edu/~jshi/software/
- [4] D. Martin and C. Fowlkes and D. Tal and J. Malik, "A Database of Human Segmented Natural Images and its Application to Evaluating Segmentation Algorithms and Measuring Ecological Statistics", Proc. 8th Int'l Conf. Computer Vision, vol. 2, pp. 416-423, July 2001. http://www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/
- [5] Norm (mathematics) http://en.wikipedia.org/wiki/Norm_%28mathematics%29 (2-norm ||x||_2 equals to Euclidean distance.)