Normalized Cut and Image Segmentation

Jianbo Shi and Jitendra Malik

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-97-940
May 1997

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1997/CSD-97-940.pdf

We propose a novel approach for solving the perceptual grouping problem in vision. Rather than focusing on local features and their consistencies in the image data, our approach aims at extracting the global impression of an image. We treat image segmentation as a graph partitioning problem and propose a novel global criterion, the normalized cut, for segmenting the graph. The normalized cut criterion measures both the total dissimilarity between the different groups as well as the total similarity within the groups. We show that an efficient computational technique based on a generalized eigenvalue problem can be used to optimize this criterion. We have applied this approach to segmenting static images as well as motion sequences and found results very encouraging.


BibTeX citation:

@techreport{Shi:CSD-97-940,
    Author = {Shi, Jianbo and Malik, Jitendra},
    Title = {Normalized Cut and Image Segmentation},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1997},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1997/5487.html},
    Number = {UCB/CSD-97-940},
    Abstract = {We propose a novel approach for solving the perceptual grouping problem in vision. Rather than focusing on local features and their consistencies in the image data, our approach aims at extracting the global impression of an image. We treat image segmentation as a graph partitioning problem and propose a novel global criterion, the normalized cut, for segmenting the graph. The normalized cut criterion measures both the total dissimilarity between the different groups as well as the total similarity within the groups. We show that an efficient computational technique based on a generalized eigenvalue problem can be used to optimize this criterion. We have applied this approach to segmenting static images as well as motion sequences and found results very encouraging.}
}

EndNote citation:

%0 Report
%A Shi, Jianbo
%A Malik, Jitendra
%T Normalized Cut and Image Segmentation
%I EECS Department, University of California, Berkeley
%D 1997
%@ UCB/CSD-97-940
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1997/5487.html
%F Shi:CSD-97-940