Normalized Cuts and Image Segmentation.
AbstractWe 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 the results to be very encouraging.
Introduction
Nearly launched the Gestalt approach which laid out the
importance of perceptual grouping and organization in visual perception. For our purposes,
the problem of grouping can be well motivated by considering the set of points shown in the
figure (1).

Figure

1: How many groups?
Typically a human observer will perceive four objects in the image-a circular ring with
a cloud of points inside it, and two loosely connected clumps of points on its right. However
this is not the unique partitioning of the scene. One can argue that there are three objects-
the two clumps on the right constitute one dumbbell shaped object. Or there are only two
objects, a dumb bell shaped object on the right, and a circular galaxy like structure on the
left. If one were perverse, one could argue that in fact every point was a distinct object.
This may seem to be an artificial example, but every attempt at image segmentation
ultimately has to confront a similar question-there are many possible partitions of the domain
D of an image into subsets D i (including the extreme one of every pixel being a separate
entity). How do we pick the "right" one? We believe the Bayesian view is appropriate- one
wants to find the most probable interpretation in the context of prior world knowledge. The
difficulty, of course, is in specifying the prior world knowledge-some of it is low level such
as coherence of brightness, color, texture, or motion, but equally important is mid- or high-level
knowledge about symmetries of objects or object models.
This suggests to us that image segmentation based on low level cues can not and should
not aim to produce a complete final "correct" segmentation. The objective should instead be
to use the low-level coherence of brightness, color, texture or motion attributes to sequentially
come up with hierarchical partitions. Mid and high level knowledge can be used to either
confirm these groups or select some for further attention. This attention could result in
further repartitioning or grouping. The key point is that image partitioning is to be done
from the big picture downwards, rather like a painter first marking out the major areas and
then filling in the details.
Prior literature on the related problems of clustering, grouping and image segmentation
is huge. The clustering community[12] has offered us agglomerative and divisive algorithms;
in image segmentation we have region-based merge and split algorithms. The hierarchical
divisive approach that we advocate produces a tree, the dendrogram. While most of these
ideas go back to the 70s (and earlier), the 1980s brought in the use of Markov Random
Fields[10] and variational formulations[17, 2, 14]. The MRF and variational formulations also
exposed two basic questions (1) What is the criterion that one wants to optimize? and (2) Is
there an efficient algorithm for carrying out the optimization? Many an attractive criterion
has been doomed by the inability to find an effective algorithm to find its minimum-greedy
or gradient descent type approaches fail to find global optima for these high dimensional,
nonlinear problems.
Our approach is most related to the graph theoretic formulation of grouping. The set
of points in an arbitrary feature space are represented as a weighted undirected graph
E), where the nodes of the graph are the points in the feature space, and an edge is
formed between every pair of nodes. The weight on each edge, w(i; j), is a function of the
similarity between nodes i and j.
In grouping, we seek to partition the set of vertices into disjoint sets
where by some measure the similarity among the vertices in a set V i is high and across
different sets V i ,V j is low.
To partition a graph, we need to also ask the following questions:
1. What is the precise criterion for a good partition?
2. How can such a partition be computed efficiently?
In the image segmentation and data clustering community, there has been much previous
work using variations of the minimal spanning tree or limited neighborhood set approaches.
Although those use efficient computational methods, the segmentation criteria used in most
of them are based on local properties of the graph. Because perceptual grouping is about
extracting the global impressions of a scene, as we saw earlier, this partitioning criterion
often falls short of this main goal.
In this paper we propose a new graph-theoretic criterion for measuring the goodness of
an image partition- the normalized cut. We introduce and justify this criterion in section 2.
The minimization of this criterion can be formulated as a generalized eigenvalue problem;
the eigenvectors of this problem can be used to construct good partitions of the image and
the process can be continued recursively as desired(section 2.1) Section 3 gives a detailed
explanation of the steps of our grouping algorithm. In section 4 we show experimental results.
The formulation and minimization of the normalized cut criterion draws on a body of results
from the field of spectral graph theory(section 5). Relationship to work in computer vision is
discussed in section 6, and comparison with related eigenvector based segmentation methods
is represented in section 6.1. We conclude in section 7.
Grouping as graph partitioning
A graph E) can be partitioned into two disjoint sets, A; B,
by simply removing edges connecting the two parts. The degree of dissimilarity between
these two pieces can be computed as total weight of the edges that have been removed. In
graph theoretic language, it is called the cut:
w(u; v): (1)
The optimal bi-partitioning of a graph is the one that minimizes this cut value. Although
there are exponential number of such partitions, finding the minimum cut of a graph is a
well studied problem, and there exist efficient algorithms for solving it.
Wu and Leahy[25] proposed a clustering method based on this minimum cut criterion.
In particular, they seek to partition a graph into k-subgraphs, such that the maximum cut
across the subgroups is minimized. This problem can be efficiently solved by recursively
finding the minimum cuts that bisect the existing segments. As shown in Wu & Leahy's
work, this globally optimal criterion can be used to produce good segmentation on some of
the images.
However, as Wu and Leahy also noticed in their work, the minimum cut criteria favors
cutting small sets of isolated nodes in the graph. This is not surprising since the cut defined
in (1) increases with the number of edges going across the two partitioned parts. Figure
(2) illustrates one such case. Assuming the edge weights are inversely proportional to the
better cut

Figure

2: A case where minimum cut gives a bad partition.
distance between the two nodes, we see the cut that partitions out node n 1 or n 2 will have a
very small value. In fact, any cut that partitions out individual nodes on the right half will
have smaller cut value than the cut that partitions the nodes into the left and right halves.
To avoid this unnatural bias for partitioning out small sets of points, we propose a new
measure of disassociation between two groups. Instead of looking at the value of total edge
weight connecting the two partitions, our measure computes the cut cost as a fraction of the
total edge connections to all the nodes in the graph. We call this disassociation measure the
normalized cut (Ncut):
(2)
u2A;t2V w(u; t) is the total connection from nodes in A to all nodes
in the graph, and assoc(B; V ) is similarly defined. With this definition of the disassociation
between the groups, the cut that partitions out small isolated points will no longer have
small Ncut value, since the cut value will almost certainly be a large percentage of the total
connection from that small set to all other nodes. In the case illustrated in figure 2, we see
that the cut 1 value across node n 1 will be 100% of the total connection from that node.
In the same spirit, we can define a measure for total normalized association within groups
for a given partition:
where assoc(A; are total weights of edges connecting nodes within A
and B respectively. We see again this is an unbiased measure, which reflects how tightly on
average nodes within the group are connected to each other.
Another important property of this definition of association and disassociation of a partition
is that they are naturally related:
Hence the two partition criteria that we seek in our grouping algorithm, minimizing the
disassociation between the groups and maximizing the association within the group, are
in fact identical, and can be satisfied simultaneously. In our algorithm, we will use this
normalized cut as the partition criterion.
Unfortunately minimizing normalized cut exactly is NP-complete, even for the special
case of graphs on grids. The proof, due to C. Papadimitriou, can be found in appendix A.
However, we will show that when we embed the normalized cut problem in the real value
domain, an approximate solution can be found efficiently.
2.1 Computing the optimal partition
Given a partition of nodes of a graph, V, into two sets A and B, let x be an
dimensional indicator vector, x node i is in A, and \Gamma1 otherwise. Let
be the total connection from node i to all other nodes. With the definitions x and d we can
rewrite Ncut(A; B) as:
Let D be an N \Theta N diagonal matrix with d on its diagonal, W be an N \Theta N symmetrical
matrix with
, and 1 be an N \Theta 1 vector of all ones. Using the
fact 1+xand 1\Gammaxare indicator vectors for respectively, we can rewrite
as:
k1 T D1
can then further expand the above equation as:
Dropping the last constant term, which in this case equals 0, we get
Letting
, and since
Setting is easy to see that
since
Putting everything together we have,
with the condition y(i) 2 f1; \Gammabg and y T
Note that the above expression is the Rayleigh quotient[11]. If y is relaxed to take on
real values, we can minimize equation (5) by solving the generalized eigenvalue system,
(D
However, we have two constraints on y, which come from the condition on the corresponding
indicator vector x. First consider the constraint y T We can show this constraint
on y is automatically satisfied by the solution of the generalized eigensystem. We will do so
by first transforming equation (6) into a standard eigensystem, and show the corresponding
condition is satisfied there. Rewrite equation (6) as
y. One can easily verify that z
1 is an eigenvector of equation (7)
with eigenvalue of 0. Furthermore,
2 is symmetric positive semidefinite,
since (D \Gamma W), also called the Laplacian matrix, is known to be positive semidefinite[18].
Hence z 0 is in fact the smallest eigenvector of equation (7), and all eigenvectors of equation
are perpendicular to each other. In particular, z 1 the second smallest eigenvector is
perpendicular to z 0 . Translating this statement back into the general eigensystem (6), we
have
1 is the smallest eigenvector with eigenvalue of 0, and
1, where y 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 x is orthogonal to the
smallest eigenvectors x 1 the quotient x T Ax
x T x is minimized by the next smallest
eigenvector x j , and its minimum value is the corresponding eigenvalue - j .
As a result, we obtain:
z
z
and consequently,
Thus the second smallest eigenvector of the generalized eigensystem (6) is the real valued
solution to our normalized cut problem. The only reason that it is not necessarily the
solution to our original problem is that the second constraint on y that y(i) 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 sub-partitions the first two parts. In fact
this line of argument can be extended to show that one can sub-divide the existing graphs,
each time using the eigenvector with the next smallest eigenvalue. However, in practice
because the approximation error from the real valued solution to the discrete valued solution
accumulates with every eigenvector taken, and all eigenvectors 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 y of (6) only approximates
the optimal normalized cut solution, it exactly minimizes the following problem:
in real-valued domain, where Roughly speaking, this forces the indicator
vector y to take similar values for nodes i and j that are tightly coupled(large w ij ).
In summary, we propose using the normalized cut criteria for graph partitioning, and we
have shown how this criteria can be computed efficiently by solving a generalized eigenvalue
problem.
3 The grouping algorithm
Our grouping algorithm consists of the following steps:
1. Given an image or image sequence, set up a weighted graph E), and set the
weight on the edge connecting two nodes being a measure of the similarity between
the two nodes.
2. Solve (D \Gamma eigenvectors with the smallest eigenvalues.
3. Use the eigenvector with second smallest eigenvalue to bipartition the graph.
4. Decide if the current partition should be sub-divided, 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 two examples.
3.1 Example 1: Point Set Case
Take the example illustrated in figure 3. Suppose we would like to group points on the 2D
plane based purely on their spatial proximity. This can be done through the following steps:
1. Define a weighted graph E), by taking each point as a node in the graph, and
connecting each pair of nodes by a graph edge. The weight on the graph edge connecting
node i and j is set to be w(i; is the Euclidean distance between
the two nodes, and oe x controls the scale of the spatial proximity measure. oe x is set to be 2.0
which is 10% of the height of the point set layout. Figure 4 shows the weight matrix for the
weighted graph constructed.
Figure

3: A point set in the plane.

Figure

4: The weight matrix constructed for the point set in (3), using spatial proximity as
the similarity measure. The points in figure (3), are numbered as: 1-90, points in the circular
ring in counter-clockwise order, 90-100, points in the cluster inside the ring, 100-120, and
120-140, the upper and lower clusters on the right respectively. Notice that the non-zero
weights are mostly concentrated in a few blocks around the diagonal. The entries in those
square blocks are the connections within each of the clusters.
2. Solve for the eigenvectors with the smallest eigenvalues of the system
(D
or equivalently the eigenvectors with the largest eigenvalues of the system
This can be done by using a generalized eigenvector solver, or by first transforming the
generalized eigenvalue system of (11) or (12) into standard eigenvector problems of
or
with
y, and solve it with a standard eigenvector solver.
Either way, we will obtain the solution of the eigenvector problem as shown in figure 5.
3. Partition the point set using the eigenvectors computed. As we have shown, the eigenvector
with the second smallest eigenvalue is the continuous approximation to the discrete
bi-partitioning indicator vector that we seek. For the case that we have constructed, the
eigenvector with the second smallest eigenvalue(figure 5.3) is indeed very close to a discrete
one. One can just partition the nodes in the graph based on the sign of their values in the
eigenvector. Using this rule, we can partition the point set into two sets as shown in figure
6.
To recursively subdivide each of the two groups, we can either 1) rerun the above procedure
on each of the individual groups, or 2) using the the eigenvectors with the next smallest
eigenvalues as approximation to the sub-partitioning indicator vectors for each of the groups.
We can see that in this case, the eigenvector with the third and the fourth smallest eigenvalue
are also good partitioning indicator vectors. Using zero as the splitting point, one can partition
the nodes based on their values in the eigenvector into two halves. The sub-partition
of the existing groups based on those two subsequent eigenvectors are shown in figure 7.
In this case, we see that the eigenvectors computed from system (11) are very close to the
discrete solution that we seek. The second smallest eigenvalue is very close to the optimal
eigenvector
eigenvalue
-0.2
-0.050.10.2
-0.06
-0.06
-0.06
Figure

5: Subplot (1) plots the smallest 10 eigenvalues of the generalized eigenvalue system
(11). Subplot (2) - (6) shows the eigenvectors corresponding the the 5 smallest eigenvalues
of the system. Note the eigenvector with the smallest eigenvalue (2) is a constant as shown
in section 2, and eigenvector with the second smallest eigenvalue (3) is an indicator vector: it
takes on only positive values for points in the two clusters to the right. Therefore, using this
eigenvector, we can find the first partition of the point set into two clusters: the points on
the left with the ring and the cluster inside, and points on the right with the two dumb bell
shaped clusters. Furthermore, note that the eigenvectors with the third smallest eigenvalue,
subplot (3) and the fourth smallest eigenvalue, subplot(4), are indicator vectors which can
be used to partition apart the ring set with the cluster inside of it, and the two clusters on
the right.
Figure

Partition of the point set using the eigenvector with the second smallest eigenvalue.
Figure

7: Sub-partitioning of the point sets using the eigenvectors with the third and fourth
smallest eigenvalues.
normalized cut value. For the general case, although we are not necessarily this lucky,
there is a bound on how far the second smallest eigenvalue can deviate from the optimal
normalized cut value, as we shall see in section 5. However, there is little theory on how
close the eigenvector is to the discrete form that the normalized cut algorithm seeks. In our
experience, the eigenvector computed is quite close to the desired discrete solution.
3.2 Example 2: Brightness Images
Having studied an example of point set grouping, we turn our attention to the case of static
image segmentation based on brightness and spatial features. Figure 8 shows an image that
we would like to segment.

Figure

8: A gray level image of a baseball game.
Just as in the point set grouping case, we have the following steps for image segmentation:
1. Construct a weighted graph, 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
of 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 two nodes i and j as:
\GammakF (i)\GammaF (j)k 2oe I
e
\GammakX (i)\GammaX (j)k2

Figure

9 shows the weight matrix W associated with this weighted graph.
nr
(b)
n=nr * nc
n=nr * nc
(c)
(a)
(d)

Figure

9: The similarity measure between each pair of pixels in (a) can be summarized in a
n \Theta n weight matrix W, shown in (b), where n is the number of pixels in the image. Instead
of displaying W itself, which is very large, two particular rows, i 1 and i 2 of W are shown in
(c) and (d). Each of the rows, is the connection weights from a pixel to all other pixels in
the image. The two rows,i 1 and i 2 are reshaped into the size of the image, and displayed.
The brightness value in (c) and (d) reflects the connection weights. Note that W contains
large number of zeros or near zeros, due to the spatial proximity factor.
2. Solve for the eigenvectors with the smallest eigenvalues of the system
(D
As we saw above, the generalized eigensystem in (16) can be transformed into a standard
eigenvalue problem of
Solving a standard eigenvalue problem for all eigenvectors takes O(n 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. Fortunately, our graph partitioning has the
following properties: 1) the graphs often are only locally connected and the resulting eigensystem
are very sparse, 2) only the top few eigenvectors are needed for graph partitioning,
and 3) the precision requirement for the eigenvectors is low, often only the right sign bit is re-
quired. These special properties of our problem can be fully exploited by an eigensolver called
the Lanczos method. The running time of a Lanczos algorithm is O(mn) +O(mM(n))[11],
where m is the maximum number of matrix-vector computations required, and M(n) is the
cost of a matrix-vector computation of Ax, where
. Note that sparse
structure in A is identical to that of the weight matrix W. Due to the sparse structure in the
weight matrix W, and therefore A, the matrix- vector computation is only of O(n), where
n is the number of the nodes.
To see why this is the case, we will look at the cost of the inner product of one row of A
with a vector x. Let y
. For a fixed i, A ij is only nonzero if node j is in
a spatial neighborhood of i. Hence there are only a fixed number of operations required for
each A i \Delta x, and the total cost of computing Ax is O(n). Figure 10 is graphical illustration
of this special inner product operation for the case of the image segmentation.
Furthermore, it turns out that we can substantially cut down additional connections from
each node to its neighbors by randomly selecting the connections within the neighborhood
for the weighted graph as shown in figure 11. Empirically, we have found that one can remove
up to 90% of the total connections with each of the neighborhoods when the neighborhoods
are large, without effecting the eigenvector solution to the system.
nr
w(i,j)00

x
y
x y
A

Figure

10: The inner product operation between A(i; and x, of dimension n, is a convolution
operation in the case of image segmentation.
(a)
(b)

Figure

11: Instead of connecting a node i to all the nodes in its neighborhood (indicated by
the shaded area in (a)), we will only connect i to randomly selected nodes(indicated by the
open circles in (b)).
Putting everything together, each of the matrix-vector computations cost O(n) operations
with a small constant factor. The number m depends on many factors[11]. In our experiments
on image segmentation, we observed that m is typically less than O(n 1

Figure

12 shows the smallest eigenvectors computed for the generalized eigensystem with
the weight matrix defined above.
(1) (2) (3)
eigenvalue

Figure

12: Subplot (1) plots the smallest eigenvectors of the generalized eigenvalue system
(11). Subplot (2) - (9) shows the eigenvectors corresponding the 2nd smallest to the 9th
smallest eigenvalues of the system. The eigenvectors are reshaped to be the size of the
image.
3. Once the eigenvectors are computed, we can partition the graph into two pieces using
the second smallest eigenvector. In the ideal case, the eigenvector should only take on two
discrete values, and the signs of the values can tell us exactly how to partition the graph.
However, our eigenvectors can take on continuous values, and we need to choose a splitting
point to partition it into two parts. There are many different ways of choosing such splitting
point. One can take 0 or the median value as the splitting point, or one can search for the
splitting point such that the resulting partition has the best Ncut(A; B) value. We take
the latter approach in our work. Currently, the search is done by checking l evenly spaced
possible splitting points, and computing the best Ncut among them. In our experiments, the
values in the eigenvectors are usually well separated, and this method of choosing a splitting
point is very reliable even with a small l. Figure 13 shows this process.
4. After the graph is broken into two pieces, we can recursively run our algorithm on the
two partitioned parts. Or equivalently, we could take advantage of the special properties of
the other top eigenvectors as explained in previous section to subdivide the graph based on
those eigenvectors. The recursion stops once the Ncut value exceeds certain limit.
We also impose a stability criterion on the partition. As we saw earlier, and as we see in
the eigenvectors with the 7-9th smallest eigenvalues(figure(12.7-9)), sometimes an eigenvector
can take on the shape of a continuous function rather that the discrete indicator function that
we seek. From the view of segmentation, such an eigenvector is attempting to subdivide an
image region where there is no sure way of breaking it. In fact, if we are forced to partition
the image based on this eigenvector, we will see there are many different splitting points
which have similar Ncut values. Hence the partition will be highly uncertain and unstable.
In our current segmentation scheme, we simply choose to ignore all those eigenvectors which
have smoothly varying eigenvector values. We achieve this by imposing a stability criterion
which measures the degree of smoothness in the eigenvector values. The simplest measure is
based on first computing the histogram of the eigenvector values, and then computing the
ratio between the minimum and maximum values in the bins. When the eigenvector values
are continuously varying, the values in the histogram bins will stay relatively the same, and
the ratio will be relatively high. In our experiments, we find that simple thresholding on the
ratio described above can be used to exclude unstable eigenvectors. We have set that value
to be 0.06 in all our experiments.

Figure

14 shows the final segmentation for the image shown in figure 8.
-0.2
-0.10.10.30.50.7(d)
(b)
(a)
(c)

Figure

13: The eigenvector in (a) is a close approximation to a discrete partitioning indicator
vector. Its histogram, shown in (b), indicates that the values in the eigenvector cluster around
two extreme values. (c) and (d) shows the partitioning results with different splitting points
indicated by the arrows in (b). The partition with the best normalized cut value is chosen.
(a) (b) (c)
(d) (e) (f)

Figure

14: (a) shows the original image of size 80 \Theta 100. Image intensity is normalized to
lie within 0 and 1. Subplot (b) - (h) shows the components of the partition with Ncut value
less than 0.04. Parameter setting: oe I = 0:1, oe
3.3 Recursive 2-way Ncut
In summary, our grouping algorithm consists of the following steps:
1. Given a set of features, set up a weighted graph E), compute the weight on
each edge, and summarize the information into W, and D.
2. Solve (D \Gamma eigenvectors with the smallest eigenvalues.
3. Use the eigenvector with second smallest eigenvalue to bipartition the graph by finding
the splitting point such that Ncut is maximized,
4. Decide if the current partition should be sub-divided by checking the stability of the
cut, and make sure Ncut is below pre-specified value. Recursively repartition the
segmented parts if necessary.
The number of groups segmented by this method is controlled directly by the maximum
allowed Ncut.
3.4 Simultanous K-way cut with multiple eigenvectors
One drawback of the recursive 2-way cut is its treatment of the oscillatory eigenvectors. The
stability criteria provides us from cutting oscillatory eigenvectors, but it also prevents us
cutting the subsequent eigenvectors which might be perfect partitioning vectors. Also the
approach is computationally wasteful; only the second eigenvector is used whereas the next
few small eigenvectors also contain useful partitioning information.
Instead of finding the partition using recursive 2-way cut as described above, one can
use the all the top eigenvectors to simultanously obtain a K-way partition. In this method,
the n top eigenvectors are used as n dimensional indicator vectors for each pixel. In the
first step, a simple clustering algorithm, such as the k-means algorithm, is used to obtain an
over-segmentation of the image into k 0 groups. No attempt is made to identify and exclude
oscillatory eigenvectors-they exarcabete the oversegmentation, but that will be dealt with
subsequently.
In the second step, one can proceed in the following two ways:
1. Greedy pruning: iteratively merge two segments at a time until only k segments are
left. At each merge step, those two segments are merged that minimize the k-way
Ncut criterion defined as:
where A i is the ith subset of whole set V.
This computation can be efficiently carried out by iteratively updating the compacted
weight matrix W c , with W c (i;
2. Global recursive cut. From the initial k 0 segments we can build a condensed graph
segment A i corresponds to a node V c
i of the graph. The
weight on each graph edge W c (i; j) is defined to be the total edge
weights from elements in A i to elements in A j . From this condensed graph, we then
recursively bi-partition the graph according the Ncut criteria. This can be carried
out either with the generalized eigenvalue system as in section 3.3, or with exhaustive
search in the discrete domain. Exhaustive search is possible in this case since k 0 is
small, typically k 0 - 100.
We have experimented with this simultanous k-way cut method on our recent test images.
However, the results presented in this paper are all based on the recursive 2-way partitioning
algorithm outlined in the previous subsection 3.3.
4 Experiments
We have applied our grouping algorithm to image segmentation based on brightness, color,
texture, or motion information. In the monocular case, we construct the graph E)
by taking each pixel as a node, and define the edge weight w ij between node i and j as the
product of a feature similarity term and spatial proximity term:
\GammakF (i)\GammaF (j)k 2oe I
e
\GammakX (i)\GammaX (j)k 2oe X if
where X(i) is the spatial location of node i, and F (i) is a feature vector based on intensity,
color, or texture information at that node defined as:
in the case of segmenting point sets,
I(i), the intensity value, for segmenting brightness images,
are the HSV values, for color
segmentation,
where the f i are DOOG filters at various scales and
orientations as used in[16], in the case of texture segmentation.
Note that the weight any pair of nodes i and j that are more than r pixels apart.
We first tested our grouping algorithm on spatial point sets similar to the one shown in
figure (2). Figure (15) shows a point set and the segmentation result. As we can see from
the figure, the normalized cut criterion is indeed able to partition the point set in a desirable
way as we have argued in section (2).

Figure

15: (a) Point set generated by two Poisson processes, with densities of 2.5 and 1.0
on the left and right clusters respectively, (b) 4 and \Theta indicates the partition of point set
in (a). Parameter settings: oe

Figures

(16), (17), (18), and (19) shows the result of our segmentation algorithm on various
brightness images. Figure (16), (17) are synthetic images with added noise. Figure (18)
and (19) are natural images. Note that the "objects" in figure (19) have rather ill-defined
c
a

Figure

image showing a noisy "step" image. Intensity varies from 0 to
1, and Gaussian noise with shows the eigenvector with the
second smallest eigenvalue, and subplot (c) shows the resulting partition.
a b c d

Figure

17: (a) A synthetic image showing three image patches forming a junction. Image
intensity varies from 0 to 1, and Gaussian noise with oe = 0:1 is added. (b)-(d) shows the
top three components of the partition.
a b c d

Figure

(a) shows a 80x100 baseball scene, image intensity is normalized to lie within
0 and 1. (b)-(h) shows the components of the partition with Ncut value less than 0.04.
Parameter setting: oe I = 0.01, oe 5.
a b c d

Figure

19: (a) shows a 126x106 weather radar image. (b)-(g) show the components of the
partition with Ncut value less than 0.08. Parameter setting: oe I = 0:005, oe
boundaries which would make edge detection perform poorly. Figure (20) shows the segmentation
on a color image, reproduced in gray scale in these transactions. The original image
and many other examples can be found at web site http://www.cs.berkeley.edu/~jshi/Grouping.
Note that in all these examples the algorithm is able to extract the major components
of scene, while ignoring small intra-component variations. As desired, recursive partitioning
can be used to further decompose each piece.
a b c

Figure

20: (a) shows a 77x107 color image. (b)-(e) show the components of the partition
with Ncut value less than 0.04. Parameter settings: oe I = 0.01, oe 5.

Figure

shows preliminary results on texture segmentation for a natural image of
a zebra against a background. Note that the measure we have used is orientation-variant,
and therefore parts of the zebra skin with different stripe orientation should be marked as
separate regions.
In the motion case, we will treat the image sequence as a spatiotemporal data set. Given
an image sequence, a weighted graph is constructed by taking each pixel in the image sequence
as a node, and connecting pixels that are in the spatiotemporal neighborhood of each
other. The weight on each graph edge is defined as:
e
\Gammad
a b
c d

Figure

21: (a) shows an image of a zebra. The remaining images show the major components
of the partition. The texture features used correspond to convolutions with DOOG
filters[16] at 6 orientations and 5 scales.
where d(i; j) is the "motion distance" between two pixels i and j. Note that X i in this case
represents the spatial-temporal position of pixel i.
To compute this "motion distance", we will use a motion feature called motion profile.
By motion profile we seek to estimate the probability distribution of image velocity at each
pixel. Let I t (X) denote a image window centered at the pixel at location X 2 R 2 at time
t. We denote by P i (dx) the motion profile of an image patch at node i, I t (X i ), at time t
corresponding to another image patch I t+1 (X i +dx) at time t can be estimated
by first computing the similarity S i (dx) between I t (X i ) and I t+1 (X i +dx), and normalizing
it to get a probability distribution:
There are many ways one can compute similarity between two image patches; we will use a
measure that is based on the sum of squared differences(SSD):
ssd
local neighborhood of image patch I t (X i ). The "motion distance"
between two image pixels is then defined as one minus the cross-correlation of the motion
profiles:
dx
In figure (22) and (23) we show results of the normalized cut algorithm on a synthetic
random dot motion sequence and a indoor motion sequence respectively. For more elaborate
discussion on motion segmentation using normalized cut, as well as how to segment and
track over long image sequences, readers might want to refer to our paper[21].
4.1 Computation time
As we saw from section 3.2, the running time of the normalized cut algorithm is O(mn),
where n is the number of pixels, and m is the number of steps Lanczos takes to converge. On
the 100 \Theta 120 test images shown here, the normalized cut algorithm takes about 2 minutes
on a Intel Pentium 200MHz machines.

Figure

22: Row (a) of this plot shows the six frames of a synthetic random dot image
sequence. Row (b) shows the outlines of the two moving patches in this image sequence.
The outlines shown here are for illustration purposes only. Row (1)-(3) shows the top three
partitions of this image sequence that have Ncut values less than 0.05. The segmentation
algorithm produces 3D space-time partitions of the image sequence. Cross-sections of those
partitions are shown here. The original image size is 100 \Theta 100, and the segmentation is
computed using image patches(superpixels) of size 3 \Theta 3. Each image patch is connected to
other image patches that are less than 5 superpixels away in spatial distance, and 3 frames
away in temporal distance.

Figure

23: Subimage (a) and (b) shows two frames of an image sequence. Segmentation
results on this two frame image sequence are shown in subimage (1) to (5). Segments in (1)
and (2) correspond to the person in the foreground, and segments in (3) to (5) correspond to
the background. The reason that the head of the person is segmented away from the body is
that although they have similar motion, their motion profiles are different. The head region
contains 2D textures and the motion profiles are more peaked, while in the body region the
motion profiles are more spread out. Segment (3) is broken away from (4) and (5) for the
same reason.
An multi-resolution implementation can be used to reduce this running time further on
larger images. In our current experiments, with this implementation, the running time on a
300 \Theta 400 image can be reduced to about 20 seconds on Intel Pentium 300MHz machines.
Furthermore, the bottle neck of the computation, a sparse matrix-vector multiplication step,
can be easily parallelized taking advantage of future computer chip designs.
In our current implementation, the sparse eigenvalue decomposition is computed using
the LASO2 numerical package developed by D. Scott.
4.2 Choice of graph edge weight
In the examples shown here, we used an exponential function of the form of
on the weighted graph edge with feature similarity of d(x). The value of oe is typically set to
of the total range of the feature distance function d(x). The exponential weighting
function is chosen here for its relatively simplicity as well as neutrality, since the focus of this
paper is on developing a general segmentation procedure, given a feature similarity measure.
We found this choice of weight function is quite adequate for typical image and feature
spaces. Section 6.1 shows the effect of using different weighting functions and parameters on
the output of the normalized cut algorithm.
However, the general problem of defining feature similarity incorporating a variety of cues
is not a trivial one. The grouping cues could be of different abstraction levels and types, and
they could be in conflict with each other. Furthermore, the weighting function could vary
from image region to image region, particularly in a textured image. Some of these issues
are addressed in [15].
5 Relationship to Spectral Graph Theory
The computational approach that we have developed for image segmentation is based on
concepts from spectral graph theory. The core idea to use matrix theory and linear algebra
to study properties of the incidence matrix, W and the Laplacian matrix, D \Gamma W, of the
graph and relate them back to various properties of the original graph. This is a rich area
of mathematics, and the idea of using eigenvectors of the Laplacian for finding partitions of
graphs can be traced back to Cheeger[4], Donath & Hoffman[7], and Fiedler[9]. This area has
also seen contributions by theoretical computer scientists[1, 3, 22, 23]. It can be shown that
our notion of normalized cut is related by a constant factor to the concept of conductance
in[22].
For a tutorial introduction to spectral graph theory, we recommend the recent monograph
by Fan Chung[5]. In this monograph, Chung[5] proposes a "normalized" definition of the
Laplacian, as
. The eigenvectors for this "normalized" Laplacian, when
multiplied by
2 , are exactly the generalized eigenvectors we used to compute normalized
cut. Chung points out that the eigenvalues of this "normalized" Laplacian relate well to
graph invariants for general graph in ways that eigenvalues of the standard Laplacian has
failed to do.
Spectral graph theory provides us some guidance on the goodness of the approximation
to the normalized cut provided by the second eigenvalue of the normalized Laplacian. One
way is through bounds on the normalized Cheeger constant[5] which in our terminology can
be defined as
The eigenvalues of (6) are related to the Cheeger constant by the inequality[5]:
G
Earlier work on spectral partitioning used the second eigenvectors of the Laplacian of the
graph defined as D \Gamma W to partition a graph. The second smallest eigenvalue of D \Gamma W is
sometimes known as the Fiedler value. Several results have been derived relating the ratio
cut, and the Fiedler value. A ratio cut of a partition of V , which in fact is
the standard definition of the Cheeger constant, is defined as cut(A;V \GammaA)
. It was shown that
if the Fiedler value is small, partitioning graph based on the Fiedler vector will lead to good
ratio cut[1][23]. Our derivation in section 2.1 can be adapted (by replacing the matrix D in
the denominators by the identity matrix I) to show that the Fiedler vector is a real valued
solution to the problem of minAaeV cut(A;V \GammaA)
, which we can call the average cut.
Although average cut looks similar to the normalized cut, average cut does not have the
important property of having a simple relationship to the average association, which can be
analogously defined as assoc(A;A)
Consequently, one can not simultaneously
minimize the disassociation across the partitions, while maximizing the association within
the groups. When we applied both techniques to the image segmentation problem, we found
that the normalized cut produces better results in practice. There are also other explanations
why the normalized cut has better behavior from graph theoretical point of view, as pointed
out by Chung[5].
As far as we are aware, our work, first presented in[20], represents the first application
of spectral partitioning to computer vision or image analysis. There is however one application
area that has seen substantial application of spectral partitioning-the area of parallel
scientific computing. The problem there is to balance the workload over multiple processors
taking into account communication needs. One of the early papers is [18]. The generalized
eigenvalue approach was first applied to graph partitioning by [8] for dynamically balancing
computational load in a parallel computer. Their algorithm is motivated by [13]'s paper on
representing a hypergraph in a Euclidean Space.
5.1 A physical interpretation
As one might expect, a physical analogy can be set up for the generalized eigenvalue system
(6) that we used to approximate the solution of normalized cut. We can construct a spring-mass
system from the weighted graph by taking graph nodes as physical nodes and graph
edges as springs connecting each pair of nodes. Furthermore, we will define the graph edge
weight as the spring stiffness, and the total edge weights connecting to a node as its mass.
Imagine what would happen if we were to give a hard shake to this spring-mass system
forcing the nodes to oscillate in the direction perpendicular to the image plane. Nodes that
have stronger spring connections among them will likely oscillate together. As the shaking
become more violent, weaker springs connecting to this group of node will be over-stretched.
Eventually the group will "pop" off from the image plane. The overall steady state behavior
of the nodes can be described by its fundamental mode of oscillation. In fact, it can be
shown that the fundamental modes of oscillation of this spring mass system are exactly the
generalized eigenvectors of (6).
ij be the spring stiffness connecting nodes i and j. Define K to be the n \Theta n stiffness
matrix, with K(i;
. Define the diagonal n \Theta n mass matrix M
as
Let x(t) be the n \Theta 1 vector describing the motion of each node. This
spring-mass dynamic system can be described by:
Assuming the solution take the form of the steady state solutions of
this spring-mass system satisfy:
analogous to equation (6) for normalized cut.
Each solution pair describes a fundamental mode of the spring-mass
system. The eigenvectors v k give the steady state displacement of the oscillation in each
mode, and the eigenvalues ! 2
k give the energy required to sustain each mode of oscillation.
Therefore, finding graph partitions that have small normalized cut values is, in effect, the
same as finding a way to "pop" off image regions with minimal effort.
6 Relationship to other graph theoretic approaches to
image segmentation
In the computer vision community, there has been some been previous work on image segmentation
formulated as a graph partition problem. Wu&Leahy[25] use the minimum cut
criterion for their segmentation. As mentioned earlier, our criticism of this criterion is that it
tends to favor cutting off small regions which is undesirable in the context of image segmen-
tation. In an attempt to get more balanced partitions, Cox et.al. [6] seek to minimize the
ratio cut(A;V \GammaA)
some function of the set A. When weight(A) is
taken to the be the sum of the elements in A, we see that this criterion becomes one of the
terms in the definition of average cut above. Cox et. al. use an efficient discrete algorithm
to solve their optimization problem assuming the graph is planar.
Sarkar & Boyer[19] use the eigenvector with the largest eigenvalue of the system
-x for finding the most coherent region in an edge map. Using a similar derivation as
in section (2.1), we can see that the first largest eigenvector of their system approximates
, and the second largest eigenvector approximates minAaeV;BaeV assoc(A;A)
However, the approximation is not tight, and there is no guarantee that
As we should see later in the section , this situation can happen quite often in practice. Since
this algorithm is essentially looking for clusters that have tight within-grouping similarity,
we will call this criteria average association.
6.1 Comparison with related eigenvector based methods
The normalized cut formulation has certain resemblance to the average cut, the standard
spectral graph partitioning, as well as average association formulation. All these three algorithms
can be reduced to solving certain eigenvalue systems. How are they related to each
other?

Figure

summarizes the relationship between these three algorithms. On one hand, both
the normalized cut and the average cut algorithm are trying to find a "balanced partition"
of a weighted graph, while on the other hand, the normalized association and the average
association are trying to find "tight" clusters in the graph. Since the normalized association
is exactly the normalized cut value, the normalized cut formulation seeks a balance
between the goal of clustering and segmentation. It is, therefore, not too surprising to see
that the normalized cut vector can be approximated with the generalized eigenvector of
(D well as that of
Judging from the discrete formulations of these three grouping criterion, it can be seen
that the average association, assoc(A;A)
, has a bias for finding tight clusters. Therefore
it runs the risk of becoming too greedy in finding small but tight clusters in the data.
This might be perfect for data that are Gaussian distributed. However for typical data in
the real world that are more likely to be made up of a mixture of various different types of
Wx='l x (D-W)
or
Average cut
Normalized Cut
or
Discrete
formulation
Continuous
solution
|A|
|B|
|A|
|B| asso(B,V)
Average association
Finding clumps Finding splits

Figure

24: Relationship between normalized cut and other eigenvector based partitioning
techniques. Compared to the average cut and average association formulation, normalized
cut seeks a balance between the goal of finding clumps and finding splits.
distributions, this bias in grouping will have undesired consequences, as we shall illustrate
in the examples below.
For average cut, cut(A;B)
, the opposite problem arises - one can not ensure the
two partitions computed will have tight within-group similarity. This becomes particularly
problematic if the dissimilarity among the different groups varies from one to another, or if
there are several possible partitions all with similar average cut values.
To illustrate these points, let us first consider a set of randomly distributed data in
1D shown in figure 25. The 1D data is made up by two subsets of points, one randomly
distributed from 0 to 0.5, and the other from 0.65 to 1.0. Each data point is taken as a node
in the graph, and the weighted graph edge connecting two points is defined to be inversely
proportional to the distance between two nodes. We will use three monotonically decreasing
weighting functions, defined on the distance function, d(x), with different
rate of fall-off. The three weighting functions are plotted in figure 26(a), 27(a), and 28(a).
The first function,
0:1
, plotted in figure 26(a), has the fastest decreasing rate
among the three. With this weighting function, only close-by points are connected, as shown
in the graph weight matrix W plotted in figure 26(b). In this case, average association fails
to find the right partition. Instead it focuses on finding small clusters in each of the two
main subgroups.
The second function, plotted in figure 27(a), has the slowest decreasing
rate among the three. With this weighting function, most points have some non-trivial
connections to the rest. To find a cut of the graph, a number of edges with heavy weights
have to be removed. In addition, the cluster on the right has less within-group similarity
comparing with the cluster on the left. In this case, average cut has trouble deciding on
where to cut.
The third function,
0:2 , plotted in figure 28(a), has a moderate decreasing
rate. With this weighting function, the nearby point connections are balanced against far-away
point connections. In this case, all three algorithms performs well with normalized cut
producing a clearer solution than the two other methods.
These problems illustrated in figure 26, 27 and 28, in fact are quite typical in segmenting
real natural images. This is particularly true in the case of texture segmentation. Different
Figure

25: A set of randomly distributed points in 1D. The first 20 points are randomly
distributed from 0.0 to 0.5, and the remaining 12 points are randomly distributed from 0.65
to 1.0. Segmentation result of these points with different weighting functions are show in
figure 26, 27, and 28.
texture regions often have very different within-group similarity, or coherence. It is very
difficult to pre-determine the right weighting function on each image region. Therefore it is
important to design a grouping algorithm that is more tolerant to a wide range of weighting
functions. The advantage of using normalized cut becomes more evident in this case. Figure
29 illustrates this point on a natural texture image shown previously in figure 21.
7 Conclusion
In this paper, we developed a grouping algorithm based on the view that perceptual grouping
should be a process that aims to extract global impressions of a scene and provides
a hierarchical description of it. By treating the grouping problem as a graph partitioning
problem, we proposed the normalized cut criteria for segmenting the graph. Normalized
cut is an unbiased measure of disassociation between sub-groups of a graph, and it has the
nice property that minimizing normalized cut leads directly to maximizing the normalized
association which is an unbiased measure for total association within the sub-groups. In
finding an efficient algorithm for computing the minimum normalized cut, we showed that
a generalized eigenvalue system provides a real valued solution to our problem.
0.1Average Cut:
(D
-0.2
-0.10.10.3
Average Association:
-0.4
-0.3
-0.2
-0.4
-0.3
-0.2

Figure

weighting function with fast rate of fall-off:
0:1
, shown in subplot
(a) in solid line. The dotted lines show the two alternative weighting functions used in
figure 27 and 28. Subplot (b) shows the corresponding graph weight matrix W . The two
columns (1) and (2) below show the first, and second extreme eigenvectors for the Normalized
cut(row 1), Average cut(row 2), and Average association(row 3). For both normalized cut,
and average cut, the smallest eigenvector is a constant vector as predicted. In this case, both
normalized cut and average cut perform well, while the average association fails to do the
right thing. Instead it tries to pick out isolated small clusters.
Average Cut:
(D
-0.50.5Average Association:
-0.4
-0.20.2
Figure

27: A weighting function with slow rate of fall-off: shown in subplot
(a) in solid line. The dotted lines show the two alternative weighting functions used in figure
26 and 28. Subplot (b) shows the corresponding graph weight matrix W . The two columns
(1) and (2) below show the first, and second extreme eigenvectors for the Normalized cut(row
1), Average cut(row 2), and Average association(row 3). In this case, both normalized cut
and average association give the right partition, while the average cut has trouble deciding
on where to cut.
Average Cut:
(D
-0.4
-0.20.2Average Association:
-0.4
-0.20.2

Figure

28: A weighting function with medium rate of fall-off:
0:2 , shown in
subplot (a) in solid line. The dotted lines show the two alternative weighting functions used
in figure 26 and 28. Subplot (b) shows the corresponding graph weight matrix W . The two
columns (1) and (2) below show the first, and second extreme eigenvectors for the Normalized
cut(row 1), Average cut(row 2), and average association(row 3). All these three algorithms
perform satisfactorily in this case, with normalized cut producing a clearer solution than the
other two cuts.
(b) (c)
50 100 150 200 250 300 350100200
50 100 150 200 250 300 350100200
(d) (e)
50 100 150 200 250 300 350100200
50 100 150 200 250 300 350100200

Figure

29: Normalized cut and average association result on the zebra image in figure
21. Subplot (a) shows the second largest eigenvector of approximating the
normalized cut vector. Subplot (b) - (e) shows the first to fourth largest eigenvectors of
approximating the average association vector, using the same graph weight
matrix. In this image, pixels on the zebra body have, on average, lower degree of coherence
than the pixels in the background. The average association, with its tendency to find tight
clusters, partitions out only small clusters in the background. The normalized cut algorithm,
having to balance the goal of clustering and segmentation, finds the better partition in this
case.
A computational method based on this idea has been developed, and applied to segmentation
of brightness, color, and texture images. Results of experiments on real and synthetic
images are very encouraging, and illustrate that the normalized cut criterion does indeed
satisfy our initial goal of extracting the "big picture" of a scene.

Acknowledgment

This research was supported by (ARO)DAAH04-96-1-0341, and an NSF Graduate Fellowship
to J. Shi. We thank Christos Papadimitriou for supplying the proof of NP-completeness for
normalized cuts on a grid. In addition, we wish to acknowledge Umesh Vazirani and Alistair
for discussions on graph theoretic algorithms and Inderjit Dhillon and Mark Adams
for useful pointers to numerical packages. Thomas Leung, Serge Belongie, Yeir Weiss and
other members of the computer vision group at U.C. Berkeley provided much useful feedback
on our algorithm.



--R


Visual Reconstruction.
Eigenvalues and graph bisection: an average-case analysis
A lower bound for the smallest eigenvalue of the laplacian.
Spectral Graph Theory.
regions: a technique for image segmentation.
Lower bounds for the partitioning of graphs.
An improved spectral bisection algorithm and its application to dynamic load balancing.
A property of eigenvectors of nonnegative symmetric matrices and its applications to graph theory.
Stochastic relaxation
Matrix computations.
Algorithms for Clustering Data.
A representation of hypergraphs in the euclidean space.
Constructing simple stable descriptions for image partitioning.
Textons, contours and regions: Cue integration in image segmentation.
Preattentive texture discrimination with early vision mecha- nisms
Optimal approximations by piecewise smooth functions
Partitioning sparse matrices with eigenvectors of graphs.
Quantitative measures of change based on feature organiza- tion: Eigenvalues and eigenvectors
Normalized cuts and image segmentation.
Motion segmentation and tracking using normalized cuts.
Approximative counting
Disk packings and planar separators.
Laws of organization in perceptual forms(partial translation).
An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation.
--TR

--CTR
Jaehwan Kim , Seungjin Choi, Semidefinite spectral clustering, Pattern Recognition, v.39 n.11, p.2025-2035, November, 2006
Lakshman Prasad , Alexei N. Skourikhine, Vectorized image segmentation via trixel agglomeration, Pattern Recognition, v.39 n.4, p.501-514, April, 2006
Segmentation of Vector Field Using Green Function and Normalized Cut, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.106, October 22-24,
Fei Ma , Mariusz Bajger , John P. Slavotinek , Murk J. Bottema, Two graph theory based methods for identifying the pectoral muscle in mammograms, Pattern Recognition, v.40 n.9, p.2592-2602, September, 2007
Qiankun Zhao , Prasenjit Mitra , C. Lee Giles, Image annotation by hierarchical mapping of features, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
Dan Kushnir , Meirav Galun , Achi Brandt, Fast multiscale clustering and manifold identification, Pattern Recognition, v.39 n.10, p.1876-1891, October, 2006
Xiaofeng Zhang , William K. Cheung , C. H. Li, Graph-Based Abstraction for Privacy Preserving Manifold Visualization, Proceedings of the 2006 IEEE/WIC/ACM international conference on Web Intelligence and Intelligent Agent Technology, p.94-97, December 18-22, 2006
Stella X. Yu , Jianbo Shi, Segmentation Given Partial Grouping Constraints, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.2, p.173-183, January 2004
Richard Nock , Frank Nielsen, Statistical Region Merging, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.11, p.1452-1458, November 2004
Mikhail Belkin , John Goldsmith, Using eigenvectors of the bigram graph to infer morpheme identity, Proceedings of the ACL-02 workshop on Morphological and phonological learning, p.41-47, July 11, 2002
Arik Azran , Zoubin Ghahramani, A new approach to data driven clustering, Proceedings of the 23rd international conference on Machine learning, p.57-64, June 25-29, 2006, Pittsburgh, Pennsylvania
Robert Jenssen , Deniz Erdogmus , Kenneth E. Hild, II , Jose C. Principe , Torbjrn Eltoft, Information cut for clustering using a gradient descent approach, Pattern Recognition, v.40 n.3, p.796-806, March, 2007
Steven J. Simske , Jordi Arnabat, User-directed analysis of scanned images, Proceedings of the ACM symposium on Document engineering, November 20-22, 2003, Grenoble, France
S. H. Srinivasan, Spectral matching of bipartite graphs, Design and application of hybrid intelligent systems, IOS Press, Amsterdam, The Netherlands,
Laurent Favreau , Lionel Reveret , Christine Depraz , Marie-Paule Cani, Animal gaits from video: comparative studies, Graphical Models, v.68 n.2, p.212-234, March 2006
Volker Roth , Julian Laub , Motoaki Kawanabe , Joachim M. Buhmann, Optimal Cluster Preserving Embedding of Nonmetric Proximity Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.12, p.1540-1551, December
Dengyong Zhou , Jiayuan Huang , Bernhard Schlkopf, Learning from labeled and unlabeled data on a directed graph, Proceedings of the 22nd international conference on Machine learning, p.1036-1043, August 07-11, 2005, Bonn, Germany
Huan Wang , Shuicheng Yan , Thomas Huang , Xiaoou Tang, Maximum unfolded embedding: formulation, solution, and application for image clustering, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA
Inderjit Dhillon , Yuqiang Guan , Brian Kulis, A fast kernel-based multilevel algorithm for graph clustering, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Laurent Favreau , Lionel Reveret , Christine Depraz , Marie-Paule Cani, Animal gaits from video, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France
Vincent. S. Tseng , Ja-Hwung Su , Bo-Wen Wang , Yu-Ming Lin, Web image annotation by fusing visual features and textual information, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea
Xiaofei He , Deng Cai , Wanli Min, Statistical and computational analysis of locality preserving projection, Proceedings of the 22nd international conference on Machine learning, p.281-288, August 07-11, 2005, Bonn, Germany
Qiankun Zhao , Tie-Yan Liu , Sourav S. Bhowmick , Wei-Ying Ma, Event detection from evolution of click-through data, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
Wen Wu , Jie Yang, SmartLabel: an object labeling tool using iterated harmonic energy minimization, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA
Kai Zhang , Ivor W. Tsang , James T. Kwok, Maximum margin clustering made practical, Proceedings of the 24th international conference on Machine learning, p.1119-1126, June 20-24, 2007, Corvalis, Oregon
Laurent Guigues , Herv Le Men , Jean-Pierre Cocquerez, The hierarchy of the cocoons of a graph and its application to image segmentation, Pattern Recognition Letters, v.24 n.8, p.1059-1066, May
Bernd Fischer , Joachim M. Buhmann, Bagging for Path-Based Clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.11, p.1411-1415, November
Chris Ding , Xiaofeng He, Linearized cluster assignment via spectral ordering, Proceedings of the twenty-first international conference on Machine learning, p.30, July 04-08, 2004, Banff, Alberta, Canada
Wei Xu , Xin Liu , Yihong Gong, Document clustering based on non-negative matrix factorization, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada
Peter Gorniak , Deb Roy, Understanding complex visually referring utterances, Proceedings of the HLT-NAACL workshop on Learning word meaning from non-linguistic data, p.14-21, May 31,
Yang , Da-You Liu, A heuristic clustering algorithm for mining communities in signed networks, Journal of Computer Science and Technology, v.22 n.2, p.320-328, March 2007
Bernd Fischer , Joachim M. Buhmann, Path-Based Clustering for Grouping of Smooth Curves and Texture Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.4, p.513-518, April
David M. Blei , Michael I. Jordan, Modeling annotated data, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada
Wei Xu , Yihong Gong, Document clustering by concept factorization, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom
Inderjit S. Dhillon , Yuqiang Guan , Brian Kulis, Kernel k-means: spectral clustering and normalized cuts, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
Huaijun Qiu , Edwin R. Hancock, Graph matching and clustering using spectral partitions, Pattern Recognition, v.39 n.1, p.22-34, January, 2006
Dianxun Shuai , Yumin Dong , Qing Shuai, A new data clustering Generalized cellular automata, Information Systems, v.32 n.7, p.968-977, November, 2007
Unsupervised relation disambiguation using spectral clustering, Proceedings of the COLING/ACL on Main conference poster sessions, p.89-96, July 17-18, 2006, Sydney, Australia
Amy McGovern , Lisa Friedland , Michael Hay , Brian Gallagher , Andrew Fast , Jennifer Neville , David Jensen, Exploiting relational structure to understand publication patterns in high-energy physics, ACM SIGKDD Explorations Newsletter, v.5 n.2, December
Rmer Rosales , Kannan Achan , Brendan Frey, Learning to cluster using local neighborhood structure, Proceedings of the twenty-first international conference on Machine learning, p.87, July 04-08, 2004, Banff, Alberta, Canada
Dirk Walther , Ueli Rutishauser , Christof Koch , Pietro Perona, Selective visual attention enables learning and recognition of multiple objects in cluttered scenes, Computer Vision and Image Understanding, v.100 n.1-2, p.41-63, October 2005
Brian Kulis , Sugato Basu , Inderjit Dhillon , Raymond Mooney, Semi-supervised graph clustering: a kernel approach, Proceedings of the 22nd international conference on Machine learning, p.457-464, August 07-11, 2005, Bonn, Germany
Xifeng Yan , X. Jasmine Zhou , Jiawei Han, Mining closed relational graphs with connectivity constraints, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Arik Azran, The rendezvous algorithm: multiclass semi-supervised learning with Markov random walks, Proceedings of the 24th international conference on Machine learning, p.49-56, June 20-24, 2007, Corvalis, Oregon
Long , Zhongfei (Mark) Zhang , Philip S. Yu, Co-clustering by block value decomposition, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
zgr imek , Alicia P. Wolfe , Andrew G. Barto, Identifying useful subgoals in reinforcement learning by local graph partitioning, Proceedings of the 22nd international conference on Machine learning, p.816-823, August 07-11, 2005, Bonn, Germany
Kai Zhang , James T. Kwok, Block-quantized kernel matrix for fast spectral embedding, Proceedings of the 23rd international conference on Machine learning, p.1097-1104, June 25-29, 2006, Pittsburgh, Pennsylvania
Gina-Anne Levow, Unsupervised and semi-supervised learning of tone and pitch accent, Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, p.224-231, June 04-09, 2006, New York, New York
P. Merchn , A. Adn, Exploration trees on highly complex scenes: A new approach for 3D segmentation, Pattern Recognition, v.40 n.7, p.1879-1898, July, 2007
Sridhar Mahadevan, Adaptive mesh compression in 3D computer graphics using multiscale manifold learning, Proceedings of the 24th international conference on Machine learning, p.585-592, June 20-24, 2007, Corvalis, Oregon
Steven J. Simske , Scott C. Baggs, Digital capture for automated scanner workflows, Proceedings of the 2004 ACM symposium on Document engineering, October 28-30, 2004, Milwaukee, Wisconsin, USA
Yuxin Peng , Chong-Wah Ngo, Clip-based similarity measure for hierarchical video retrieval, Proceedings of the 6th ACM SIGMM international workshop on Multimedia information retrieval, October 15-16, 2004, New York, NY, USA
Hany Farid, Exposing digital forgeries in scientific images, Proceeding of the 8th workshop on Multimedia and security, September 26-27, 2006, Geneva, Switzerland
Mustafa Ozden , Ediz Polat, A color image segmentation approach for content-based image retrieval, Pattern Recognition, v.40 n.4, p.1318-1325, April, 2007
Xiaoli Zhang Fern , Carla E. Brodley, Solving cluster ensemble problems by bipartite graph partitioning, Proceedings of the twenty-first international conference on Machine learning, p.36, July 04-08, 2004, Banff, Alberta, Canada
Juliana F. Camapum Wanderley , Mark H. Fisher, Spatial-feature parametric clustering applied to motion-based segmentation in camouflage, Computer Vision and Image Understanding, v.85 n.2, p.144-157, February 2002
Nathan A. Carr , John C. Hart, Two algorithms for fast reclustering of dynamic meshed surfaces, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France
Xin-Jing Wang , Wei-Ying Ma , Lei Zhang , Xing Li, Iteratively clustering web images based on link and attribute reinforcements, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore
Tatsuya Ishihara , Hironobu Takagi , Takashi Itoh , Chieko Asakawa, Analyzing visual layout for a non-visual presentation-document interface, Proceedings of the 8th international ACM SIGACCESS conference on Computers and accessibility, October 23-25, 2006, Portland, Oregon, USA
Andrea Torsello , Edwin R. Hancock, Graph embedding using tree edit-union, Pattern Recognition, v.40 n.5, p.1393-1405, May, 2007
Cheng Bing , Zheng Nanning , Wang Ying , Zhang Yongping , Zhang Zhihua, Color image segmentation based on edge-preservation smoothing and soft C-means clustering, Machine Graphics & Vision International Journal, v.11 n.2/3, p.183-194, 2002
Peter Gorniak , Deb Roy, A visually grounded natural language interface for reference to spatial scenes, Proceedings of the 5th international conference on Multimodal interfaces, November 05-07, 2003, Vancouver, British Columbia, Canada
J. Jeon , V. Lavrenko , R. Manmatha, Automatic image annotation and retrieval using cross-media relevance models, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada
Kannan , Santosh Vempala , Adrian Vetta, On clusterings: Good, bad and spectral, Journal of the ACM (JACM), v.51 n.3, p.497-515, May 2004
Xiaofei He , Deng Cai , Haifeng Liu , Jiawei Han, Image clustering with tensor representation, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore
Xiang Ji , Wei Xu, Document clustering with prior knowledge, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA
Miguel . Carreira-Perpin, Fast nonparametric clustering with Gaussian blurring mean-shift, Proceedings of the 23rd international conference on Machine learning, p.153-160, June 25-29, 2006, Pittsburgh, Pennsylvania
Igor Malioutov , Regina Barzilay, Minimum cut model for spoken lecture segmentation, Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL, p.25-32, July 17-18, 2006, Sydney, Australia
Dengyong Zhou , Christopher J. C. Burges, Spectral clustering and transductive learning with multiple views, Proceedings of the 24th international conference on Machine learning, p.1159-1166, June 20-24, 2007, Corvalis, Oregon
J. P. Lewis , Nickson Fong , Xie XueXiang , Seah Hock Soon , Tian Feng, More optimal strokes for NPR sketching, Proceedings of the 3rd international conference on Computer graphics and interactive techniques in Australasia and South East Asia, November 29-December 02, 2005, Dunedin, New Zealand
Xin Zheng , Deng Cai , Xiaofei He , Wei-Ying Ma , Xueyin Lin, Locality preserving clustering for image database, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA
Tomer Hertz , Aharon Bar-Hillel , Daphna Weinshall, Boosting margin based distance functions for clustering, Proceedings of the twenty-first international conference on Machine learning, p.50, July 04-08, 2004, Banff, Alberta, Canada
Natasha Gelfand , Leonidas J. Guibas, Shape segmentation using local slippage analysis, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France
Munirathnam Srikanth , Joshua Varner , Mitchell Bowden , Dan Moldovan, Exploiting ontologies for automatic image annotation, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil
Jingrui He , Hanghang Tong , Mingjing Li , Wei-Ying Ma , Changshui Zhang, Multiple random walk and its application in content-based image retrieval, Proceedings of the 7th ACM SIGMM international workshop on Multimedia information retrieval, November 10-11, 2005, Hilton, Singapore
Sameer Agarwal , Kristin Branson , Serge Belongie, Higher order learning with graphs, Proceedings of the 23rd international conference on Machine learning, p.17-24, June 25-29, 2006, Pittsburgh, Pennsylvania
Jian Yao , Zhonefei Zhang, Hierarchical shadow detection for color aerial images, Computer Vision and Image Understanding, v.102 n.1, p.60-69, April 2006
Long Quan , Ping Tan , Gang Zeng , Lu Yuan , Jingdong Wang , Sing Bing Kang, Image-based plant modeling, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
Nicolas Loeff , Cecilia Ovesdotter Alm , David A. Forsyth, Discriminating image senses by clustering with multimodal features, Proceedings of the COLING/ACL on Main conference poster sessions, p.547-554, July 17-18, 2006, Sydney, Australia
Yining Deng , b. s. Manjunath, Unsupervised Segmentation of Color-Texture Regions in Images and Video, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.8, p.800-810, August 2001
Greg Hamerly , Charles Elkan, Alternatives to the k-means algorithm that find better clusterings, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
Jia Li , James Z. Wang, Automatic Linguistic Indexing of Pictures by a Statistical Modeling Approach, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.9, p.1075-1088, September
Yixin Chen , James Z. Wang , Robert Krovetz, Content-based image retrieval by clustering, Proceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval, November 07-07, 2003, Berkeley, California
Bin Gao , Tie-Yan Liu , Guang Feng , Tao Qin , Qian-Sheng Cheng , Wei-Ying Ma, Hierarchical Taxonomy Preparation for Text Categorization Using Consistent Bipartite Spectral Graph Copartitioning, IEEE Transactions on Knowledge and Data Engineering, v.17 n.9, p.1263-1273, September 2005
Jennifer Neville , David Jensen, Leveraging relational autocorrelation with latent group models, Proceedings of the 4th international workshop on Multi-relational mining, p.49-55, August 21-21, 2005, Chicago, Illinois
Deng Cai , Zheng Shao , Xiaofei He , Xifeng Yan , Jiawei Han, Mining hidden community in heterogeneous social networks, Proceedings of the 3rd international workshop on Link discovery, p.58-65, August 21-25, 2005, Chicago, Illinois
Ying Liu , Dengsheng Zhang , Guojun Lu , Wei-Ying Ma, A survey of content-based image retrieval with high-level semantics, Pattern Recognition, v.40 n.1, p.262-282, January, 2007
Xiaobin Li , Zheng Tian, Optimum cut-based clustering, Signal Processing, v.87 n.11, p.2491-2502, November, 2007
Mezaris , Ioannis Kompatsiaris , Michael G. Strintzis, Region-based image retrieval using an object ontology and relevance feedback, EURASIP Journal on Applied Signal Processing, v.2004 n.1, p.886-901, 1 January 2004
Tijl De Bie , Nello Cristianini, Fast SDP Relaxations of Graph Cut Clustering, Transduction, and Other Combinatorial Problems, The Journal of Machine Learning Research, 7, p.1409-1436, 12/1/2006
Yining Deng , b. s. Manjunath, Unsupervised Segmentation of Color-Texture Regions in Images and Video, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.8, p.800-810, August 2001
Sagi Katz , Ayellet Tal, Hierarchical mesh decomposition using fuzzy clustering and cuts, ACM Transactions on Graphics (TOG), v.22 n.3, July
Cem Unsalan , Kim L. Boyer, A Theoretical and Experimental Investigation of Graph Theoretical Measures for Land Development in Satellite Imagery, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.4, p.575-589, April 2005
Shigeru Owada , Frank Nielsen , Takeo Igarashi, Volume catcher, Proceedings of the 2005 symposium on Interactive 3D graphics and games, April 03-06, 2005, Washington, District of Columbia
Vincent S. Tseng , Chon-Jei Lee , Ja-Hwung Su, Classify By Representative Or Associations (CBROA): a hybrid approach for image classification, Proceedings of the 6th international workshop on Multimedia data mining: mining integrated media and complex data, p.61-69, August 21-21, 2005, Chicago, Illinois
James Z. Wang , Jia Li, Learning-based linguistic indexing of pictures with 2--d MHMMs, Proceedings of the tenth ACM international conference on Multimedia, December 01-06, 2002, Juan-les-Pins, France
Aleix M. Martnez , Pradit Mittrapiyanuruk , Avinash C. Kak, On combining graph-partitioning with non-parametric clustering for image segmentation, Computer Vision and Image Understanding, v.95 n.1, p.72-85, July 2004
Mikhail Belkin , Partha Niyogi, Semi-Supervised Learning on Riemannian Manifolds, Machine Learning, v.56 n.1-3, p.209-239
Jingrui He , Mingjing Li , Hong-Jiang Zhang , Hanghang Tong , Changshui Zhang, Manifold-ranking based image retrieval, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA
Fernando De la Torre , Takeo Kanade, Discriminative cluster analysis, Proceedings of the 23rd international conference on Machine learning, p.241-248, June 25-29, 2006, Pittsburgh, Pennsylvania
Desmond J. Higham , Gabriela Kalna , Milla Kibble, Spectral clustering and its use in bioinformatics, Journal of Computational and Applied Mathematics, v.204 n.1, p.25-37, July, 2007
Inderjit S. Dhillon, Co-clustering documents and words using bipartite spectral graph partitioning, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.269-274, August 26-29, 2001, San Francisco, California
Jia-Yu Pan , Hyung-Jeong Yang , Christos Faloutsos , Pinar Duygulu, Automatic multimedia cross-modal correlation discovery, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
Bin Gao , Tie-Yan Liu , Xin Zheng , Qian-Sheng Cheng , Wei-Ying Ma, Consistent bipartite graph co-partitioning for star-structured high-order heterogeneous data co-clustering, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Tilman Lange , Joachim M. Buhmann, Combining partitions by probabilistic label aggregation, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Long , Zhongfei (Mark) Zhang , Xiaoyun W , Philip S. Yu, Spectral clustering for multi-type relational data, Proceedings of the 23rd international conference on Machine learning, p.585-592, June 25-29, 2006, Pittsburgh, Pennsylvania
Chris H. Q. Ding, Analysis of gene expression profiles: class discovery and leaf ordering, Proceedings of the sixth annual international conference on Computational biology, p.127-136, April 18-21, 2002, Washington, DC, USA
Eyal Amir , Robert Krauthgamer , Satish Rao, Constant factor approximation of vertex-cuts in planar graphs, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Desmond J. Higham, Unravelling small world networks, Journal of Computational and Applied Mathematics, v.158 n.1, p.61-74, 1 September
Gang Wu , Edward Y. Chang , Navneet Panda, Formulating context-dependent similarity functions, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore
Deng Cai , Xiaofei He , Zhiwei Li , Wei-Ying Ma , Ji-Rong Wen, Hierarchical clustering of WWW image search results using visual, textual and link information, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA
Xiaofei He , Deng Cai , Ji-Rong Wen , Wei-Ying Ma , Hong-Jiang Zhang, Clustering and searching WWW images using link and page layout analysis, ACM Transactions on Multimedia Computing, Communications, and Applications (TOMCCAP), v.3 n.2, p.10-es, May 2007
Andrea Torsello , Dzena Hidovic-Rowe , Marcello Pelillo, Polynomial-Time Metrics for Attributed Trees, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.7, p.1087-1099, July 2005
Ravikrishna Kolluri , Jonathan Richard Shewchuk , James F. O'Brien, Spectral surface reconstruction from noisy point clouds, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France
Xiaofei He , Shuicheng Yan , Yuxiao Hu , Partha Niyogi , Hong-Jiang Zhang, Face Recognition Using Laplacianfaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.3, p.328-340, March 2005
Adrian Barbu , Song-Chun Zhu, Generalizing Swendsen-Wang to Sampling Arbitrary Posterior Probabilities, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.8, p.1239-1253, August 2005
Gl Nildem Demir , A. Sima Uyar , Sule Gndz gdc, Graph-based sequence clustering through multiobjective evolutionary algorithms for web recommender systems, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England
Samuel Gerber , Tolga Tasdizen , Ross Whitaker, Robust non-linear dimensionality reduction using successive 1-dimensional Laplacian Eigenmaps, Proceedings of the 24th international conference on Machine learning, p.281-288, June 20-24, 2007, Corvalis, Oregon
Long , Zhongfei (Mark) Zhang , Xiaoyun Wu , Philip S. Yu, Relational clustering by symmetric convex coding, Proceedings of the 24th international conference on Machine learning, p.569-576, June 20-24, 2007, Corvalis, Oregon
J. J. Steil , M. Gtting , H. Wersing , E. Krner , H. Ritter, Adaptive scene dependent filters for segmentation and online learning of visual objects, Neurocomputing, v.70 n.7-9, p.1235-1246, March, 2007
Zhuowen Tu , Song-Chun Zhu, Image Segmentation by Data-Driven Markov Chain Monte Carlo, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.5, p.657-673, May 2002
Yixin Chen , James Z. Wang, A Region-Based Fuzzy Feature Matching Approach to Content-Based Image Retrieval, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.9, p.1252-1267, September 2002
Long , Xiaoyun Wu , Zhongfei (Mark) Zhang , Philip S. Yu, Unsupervised learning on k-partite graphs, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
Byoung-Ki Jeon , Yun-Beom Jung , Ki-Sang Hong, Image segmentation by unsupervised sparse clustering, Pattern Recognition Letters, v.27 n.14, p.1650-1664, 15 October 2006
Xiaojun Qi , Yutao Han, Incorporating multiple SVMs for automatic image annotation, Pattern Recognition, v.40 n.2, p.728-741, February, 2007
Chris H. Q. Ding , Xiaofeng He , Hongyuan Zha, A spectral method to separate disconnected and nearly-disconnected web graph components, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.275-280, August 26-29, 2001, San Francisco, California
Anthony Hoogs , Roderic Collins , Robert Kaucic , Joseph Mundy, A Common Set of Perceptual Observables for Grouping, Figure-Ground Discrimination, and Texture Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.4, p.458-474, April
Bin Gao , Tie-Yan Liu , Tao Qin , Xin Zheng , Qian-Sheng Cheng , Wei-Ying Ma, Web image clustering by consistent utilization of visual features and surrounding texts, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore
Ian H. Jermyn , Hiroshi Ishikawa, Globally Optimal Regions and Boundaries as Minimum Ratio Weight Cycles, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.10, p.1075-1088, October 2001
Joes Staal , Stiliyan N. Kalitzin , Max A. Viergever, A Trained Spin-Glass Model for Grouping of Image Primitives, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.7, p.1172-1182, July 2005
Antonio Robles-Kelly , Edwin R. Hancock, A Riemannian approach to graph embedding, Pattern Recognition, v.40 n.3, p.1042-1056, March, 2007
Felipe P. Bergo , Alexandre X. Falco , Paulo A. Miranda , Leonardo M. Rocha, Automatic Image Segmentation by Tree Pruning, Journal of Mathematical Imaging and Vision, v.29 n.2-3, p.141-162, November  2007
Yi Liu , Rong Jin , Joyce Y. Chai, A statistical framework for query translation disambiguation, ACM Transactions on Asian Language Information Processing (TALIP), v.5 n.4, p.360-387, December 2006
Charless Fowlkes , Serge Belongie , Fan Chung , Jitendra Malik, Spectral Grouping Using the Nystrm Method, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.2, p.214-225, January 2004
Exploiting relationships for object consolidation, Proceedings of the 2nd international workshop on Information quality in information systems, June 17-17, 2005, Baltimore, Maryland
Yixin Chen , James Z. Wang, Image Categorization by Learning and Reasoning with Regions, The Journal of Machine Learning Research, 5, p.913-939, 12/1/2004
Yizhou Yu , Johnny T. Chang, Shadow Graphs and 3D Texture Reconstruction, International Journal of Computer Vision, v.62 n.1-2, p.35-60, April-May 2005
Neil Lawrence, Probabilistic Non-linear Principal Component Analysis with Gaussian Process Latent Variable Models, The Journal of Machine Learning Research, 6, p.1783-1816, 12/1/2005
Richard C. Wilson , Edwin R. Hancock , Bin Luo, Pattern Vectors from Algebraic Graph Theory, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.7, p.1112-1124, July 2005
Qi-Xing Huang , Simon Flry , Natasha Gelfand , Michael Hofer , Helmut Pottmann, Reassembling fractured objects by geometric matching, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
Alper Yilmaz , Mubarak Shah, Matching actions in presence of camera motion, Computer Vision and Image Understanding, v.104 n.2, p.221-231, November 2006
Peter Orbanz , Joachim M. Buhmann, Nonparametric Bayesian Image Segmentation, International Journal of Computer Vision, v.77 n.1-3, p.25-45, May       2008
Kobus Barnard , Quanfu Fan , Ranjini Swaminathan , Anthony Hoogs , Roderic Collins , Pascale Rondot , John Kaufhold, Evaluation of Localized Semantics: Data, Methodology, and Experiments, International Journal of Computer Vision, v.77 n.1-3, p.199-217, May       2008
Matthias Heiler , Christoph Schnrr, Natural Image Statistics for Natural Image Segmentation, International Journal of Computer Vision, v.63 n.1, p.5-19, June      2005
Kilian Q. Weinberger , Lawrence K. Saul, Unsupervised Learning of Image Manifolds by Semidefinite Programming, International Journal of Computer Vision, v.70 n.1, p.77-90, October   2006
Okan Arikan, Compression of motion capture databases, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
Ying Zhao , George Karypis , Usama Fayyad, Hierarchical Clustering Algorithms for Document Datasets, Data Mining and Knowledge Discovery, v.10 n.2, p.141-168, March     2005
Kobus Barnard , Pinar Duygulu , David Forsyth , Nando de Freitas , David M. Blei , Michael I. Jordan, Matching words and pictures, The Journal of Machine Learning Research, 3, 3/1/2003
Gaurav Harit , Santanu Chaudhury, Clustering in video data: Dealing with heterogeneous semantics of features, Pattern Recognition, v.39 n.5, p.789-811, May, 2006
Jitendra Malik , Serge Belongie , Thomas Leung , Jianbo Shi, Contour and Texture Analysis for Image Segmentation, International Journal of Computer Vision, v.43 n.1, p.7-27, June 2001
Fast Approximate Energy Minimization via Graph Cuts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.11, p.1222-1239, November 2001
Tao Li , Sheng Ma , Mitsunori Ogihara, Document clustering via adaptive subspace iteration, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom
Zhuowen Tu , Song-Chun Zhu, Parsing Images into Regions, Curves, and Curve Groups, International Journal of Computer Vision, v.69 n.2, p.223-249, August    2006
Long Quan , Jingdong Wang , Ping Tan , Lu Yuan, Image-Based Modeling by Joint Segmentation, International Journal of Computer Vision, v.75 n.1, p.135-150, October   2007
Frdric Cao , Pablo Mus , Frdric Sur, Extracting Meaningful Curves from Images, Journal of Mathematical Imaging and Vision, v.22 n.2-3, p.159-181, May       2005
Lior Wolf , Amnon Shashua, Feature Selection for Unsupervised and Supervised Inference: The Emergence of Sparsity in a Weight-Based Approach, The Journal of Machine Learning Research, 6, p.1855-1887, 12/1/2005
Mohan Sridharan , Peter Stone, Structure-based color learning on a mobile robot under changing illumination, Autonomous Robots, v.23 n.3, p.161-182, October   2007
Ying Zhao , George Karypis, Empirical and Theoretical Comparisons of Selected Criterion Functions for Document Clustering, Machine Learning, v.55 n.3, p.311-331, June 2004
Han , Hongyuan Zha , C. Lee Giles, Name disambiguation in author citations using a K-way spectral clustering method, Proceedings of the 5th ACM/IEEE-CS joint conference on Digital libraries, June 07-11, 2005, Denver, CO, USA
Keiji Yanai , Nikhil V. Shirahatti , Prasad Gabbur , Kobus Barnard, Evaluation strategies for image understanding and retrieval, Proceedings of the 7th ACM SIGMM international workshop on Multimedia information retrieval, November 10-11, 2005, Hilton, Singapore
Asaad Hakeem , Mubarak Shah, Learning, detection and representation of multi-agent events in videos, Artificial Intelligence, v.171 n.8-9, p.586-605, June, 2007
Francis R. Bach , Michael I. Jordan, Learning Spectral Clustering, With Application To Speech Separation, The Journal of Machine Learning Research, 7, p.1963-2001, 12/1/2006
Andrea Torsello , Antonio Robles-Kelly , Edwin R. Hancock, Discovering Shape Classes using Tree Edit-Distance and Pairwise Clustering, International Journal of Computer Vision, v.72 n.3, p.259-285, May       2007
Zhuowen Tu , Xiangrong Chen , Alan L. Yuille , Song-Chun Zhu, Image Parsing: Unifying Segmentation, Detection, and Recognition, International Journal of Computer Vision, v.63 n.2, p.113-140, July      2005
Ana L. N. Fred , Anil K. Jain, Combining Multiple Clusterings Using Evidence Accumulation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.6, p.835-850, June 2005
Kobus Barnard , Matthew Johnson, Word sense disambiguation with pictures, Artificial Intelligence, v.167 n.1-2, p.13-30, September 2005
Hoiem , Alexei A. Efros , Martial Hebert, Recovering Surface Layout from an Image, International Journal of Computer Vision, v.75 n.1, p.151-172, October   2007
Ali Shokoufandeh , Spiros Mancoridis , Trip Denton , Matthew Maycock, Spectral and meta-heuristic algorithms for software clustering, Journal of Systems and Software, v.77 n.3, p.213-223, September 2005
Laurent Guigues , Jean Pierre Cocquerez , Herv Men, Scale-Sets Image Analysis, International Journal of Computer Vision, v.68 n.3, p.289-317, July      2006
Song Wang , Toshiro Kubota , Jeffrey Mark Siskind , Jun Wang, Salient Closed Boundary Extraction with Ratio Contour, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.4, p.546-561, April 2005
Martin H. C. Law , Mario A. T. Figueiredo , Anil K. Jain, Simultaneous Feature Selection and Clustering Using Mixture Models, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.9, p.1154-1166, September 2004
Ulrike Luxburg, A tutorial on spectral clustering, Statistics and Computing, v.17 n.4, p.395-416, December  2007
Luminita A. Vese , Tony F. Chan, A Multiphase Level Set Framework for Image Segmentation Using the Mumford and Shah Model, International Journal of Computer Vision, v.50 n.3, p.271-293, December 2002
Robert Hanek , Michael Beetz, The Contracting Curve Density Algorithm: Fitting Parametric Curve Models to Images Using Local Self-Adapting Separation Criteria, International Journal of Computer Vision, v.59 n.3, p.233-258, September-October 2004
Jacob Feldman, Perceptual Grouping by Selection of a Logically Minimal Model, International Journal of Computer Vision, v.55 n.1, p.5-25, October
Jens Keuchel , Christoph Schnrr , Christian Schellewald , Daniel Cremers, Binary Partitioning, Perceptual Grouping, and Restoration with Semidefinite Programming, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.11, p.1364-1379, November
Dirk Walther , Christof Koch, 2006 Special Issue: Modeling attention to salient proto-objects, Neural Networks, v.19 n.9, p.1395-1407, November, 2006
Fernando De La Torre , Michael J. Black, A Framework for Robust Subspace Learning, International Journal of Computer Vision, v.54 n.1-3, p.117-142, August-September
Bodo Rosenhahn , Thomas Brox , Joachim Weickert, Three-Dimensional Shape Knowledge for Joint Image Segmentation and Pose Tracking, International Journal of Computer Vision, v.73 n.3, p.243-262, July      2007
Graph Cuts and Efficient N-D Image Segmentation, International Journal of Computer Vision, v.70 n.2, p.109-131, November  2006
Lawrence K. Saul , Sam T. Roweis, Think globally, fit locally: unsupervised learning of low dimensional manifolds, The Journal of Machine Learning Research, 4, p.119-155, 12/1/2003
John P. Eakins, Retrieval of still images by content, Lectures on information retrieval, Springer-Verlag New York, Inc., New York, NY, 2001
Daniel Cremers , Mikael Rousson , Rachid Deriche, A Review of Statistical Approaches to Level Set Segmentation: Integrating Color, Texture, Motion and Shape, International Journal of Computer Vision, v.72 n.2, p.195-215, April 2007
Ritendra Datta , Jia Li , James Z. Wang, Content-based image retrieval: approaches and trends of the new age, Proceedings of the 7th ACM SIGMM international workshop on Multimedia information retrieval, November 10-11, 2005, Hilton, Singapore
Alper Yilmaz , Omar Javed , Mubarak Shah, Object tracking: A survey, ACM Computing Surveys (CSUR), v.38 n.4, p.13-es, 2006
Axel Pinz, Object categorization, Foundations and Trends in Computer Graphics and Vision, v.1 n.4, p.255-353, December 2005
graph partitioning;image segmentation;grouping