![](https://csdnimg.cn/release/download_crawler_static/4224065/bg4.jpg)
transforming (6) into a standard eigensystem and showing
the corresponding condition is satisfied there. Rewrite (6) as
D
ÿ
1
2
D ÿ WD
ÿ
1
2
zz zz; 7
where zz D
1
2
yy. One can easily verify that zz
0
D
1
2
1 is an
eigenvector of (7) with eigenvalue of 0. Furthermore,
D
ÿ
1
2
D ÿ WD
ÿ
1
2
is symmetric positive semidefinite since
D ÿ W, also called the Laplacian matrix, is known to be
positive semidefinite [18]. Hence, zz
0
is, in fact, the smallest
eigenvector of (7) and all eigenvectors of (7) are perpendi-
cular to each other. In particular, zz
1
, the second smallest
eigenvector, is perpendicular to zz
0
. Translating this state-
ment back into the general eigensystem (6), we have:
1) yy
0
1 is the smallest eigenvector with eigenvalue of 0
and 2) 0 zz
T
1
zz
0
yy
T
1
D1, where yy
1
is the second smallest
eigenvector of (6).
Now, recall a simple fact about the Rayleigh quotient [11]:
Let A be a real symmetric matrix. Under the constraint that
xx is orthogonal to the j-1 smallest eigenvectors xx
1
; ...;xx
jÿ1
,
the quotient
xx
T
Axx
xx
T
xx
is minimized by the next smallest
eigenvector xx
j
and its minimum value is the corresponding
eigenvalue
j
.
As a result, we obtain:
zz
1
arg:min
zz
T
zz
0
0
zz
T
D
ÿ
1
2
D ÿ WD
ÿ
1
2
zz
zz
T
zz
8
and, consequently,
yy
1
arg:min
yy
T
D10
yy
T
D ÿ Wyy
yy
T
Dyy
: 9
Thus, the second smallest eigenvector of the generalized
eigensystem (6) is the real valued solution to our normal-
ized cut problem. The only reason that it is not necessarily
the solution to our original problem is that the second
constraint on yy that yyi takes on two discrete values is not
automatically satisfied. In fact, relaxing this constraint is
what makes this optimization problem tractable in the first
place. We will show in Section 3 how this real valued
solution can be transformed into a discrete form.
A similar argument can also be made to show that the
eigenvector with the third smallest eigenvalue is the real
valued solution that optimally subpartitions the first two
parts. In fact, this line of argument can be extended to show
that one can subdivide the existing graphs, each time using
the eigenvector with the next smallest eigenvalue. How-
ever, in practice, because the approximation error from the
real valued solution to the discrete valued solution
accumulates with every eigenvector taken and all eigen-
vectors have to satisfy a global mutual orthogonality
constraint, solutions based on higher eigenvectors become
unreliable. It is best to restart solving the partitioning
problem on each subgraph individually.
It is interesting to note that, while the second smallest
eigenvector yy of (6) only approximates the optimal normal-
ized cut solution, it exactly minimizes the following
problem:
inf
yy
T
D10
P
i
P
j
yyiÿyyj
2
w
ij
P
i
yyi
2
di
; 10
in real-valued domain, where diDi; i.Roughly
speaking, this forces the indicator vector yy to take similar
values for nodes i and j that are tightly coupled (large w
ij
).
In summary, we propose using the normalized cut
criterion for graph partitioning and we have shown how
this criterion can be computed efficiently by solving a
generalized eigenvalue problem.
3THE GROUPING ALGORITHM
Our grouping algorithm consists of the following steps:
1. Given an image or image sequence, set up a
weighted graph G V; E and set the weight on
the edge connecting two nodes to be a measure of
the similarity between the two nodes.
2. Solve D ÿ Wxx Dxx for eigenvectors with the
smallest eigenvalues.
3. Use the eigenvector with the second smallest
eigenvalue to bipartition the graph.
4. Decide if the current partition should be subdivided
and recursively repartition the segmented parts if
necessary.
The grouping algorithm, as well as its computational
complexity, can be best illustrated by using the following
example.
3.1 Example: Brightness Images
Fig. 2 shows an image that we would like to segment. The
steps are:
1. Construct a weighted graph G V; E by taking
each pixel as a node and connecting each pair of
pixels by an edge. The weight on that edge should
reflect the likelihood that the two pixels belong to
one object. Using just the brightness value of the
pixels and their spatial location, we can define the
graph edge weight connecting the two nodes i and j
as:
w
ij
e
ÿ
kFF
i
ÿFF
j
k
2
2
2
I
e
ÿ
kXX
i
ÿXX
j
k
2
2
2
X
if kXXiÿXXjk
2
<r
0 otherwise:
8
<
:
11
2. Solve for the eigenvectors with the smallest eigen-
values of the system
D ÿ Wyy Dyy: 12
As we saw above, the generalized eigensystem in
(12) can be transformed into a standard eigenvalue
problem of
D
ÿ
1
2
D ÿ WD
ÿ
1
2
xx xx: 13
Solving a standard eigenvalue problem for all
eigenvectors takes On
3
operations, where n is the
number of nodes in the graph. This becomes
impractical for image segmentation applications
where n is the number of pixels in an image.
SHI AND MALIK: NORMALIZED CUTS AND IMAGE SEGMENTATION 891