Edited by author 04-12-2002 11:24 PM
Hi all, this paper by Yair Weiss is an overview of recent work in spectral segmentation methods. It will give a good introduction to the talk, but there is much more to discuss than just this paper. Recent work by Andrew Ng, Marina Meila, Ravi Kannan, and others is also interesting and relevant. Andrew Ng's paper especially makes nice arguments for the methods from the perspective of perfectly separated data.

Here are pointers to the papers referenced in Weiss' paper, and others of interest:

• Normalized cuts and image segmentation (Shi & Malik)
• Learning segmentation with random walks (Meila & Shi)
• A factorization approach to grouping (Perona & Freeman)
• On clusterings -- good, bad, and spectral (Kannan, Vempala, Vetta)
• Feature grouping by relocalisation of eigenvectors of the proximity matrix (Scott & Longuet-Higgins)
• On spectral clustering: analysis and an algorithm (Ng, Jordan, Weiss)
  

In Yair Weiss' paper there is at least one typo, in section 2.1. The phrase "between cluster affinity B is zero" should be "between cluster affinity *C* is zero".

The topic of this board still says "Mean Shift", due to a change in my choice of paper.

FYI, this paper was also presented Fall quarter in the cs291 course. Slides and other comments can be found on that web page:
http://www-cse.ucsd.edu/~sjb/classes/fa01/cse291/

One of the things that I think this paper does best is incorporate three papers. In general, I think papers tend to focus on a single paper and improve on that topic, adding in additional papers here and there, but mainly focusing on the one paper. This paper seems to be unbiased towards the time spent on these three papers. The result, is a paper that provides a fairly solid background and analysis for the topic at hand.

The one drawback of this sort of multi-paper approach is that conference papers tend to be limited in length. The paper had two key goals: show the connections between the three (or four) papers and their methodologies and results and present an improved algorithm which was a combination of two of these. I think the paper did a good part for the first goal, but I would have liked to see a bit more analysis and development of their combined algorithm and the experimental results.

Edited by author 04-16-2002 03:07 AM
How is the affinity matrix calculated (equation 1)? What is the definition of x_i and x_j ? Thanks.

Never mind. I got the idea after finding an illustrative picture at:
http://www-cse.ucsd.edu/~sjb/classes/fa01/cse291/eigen.ppt,
slide: "The structure of the affinity matrix"

Edited by author 04-16-2002 04:49 AM
I just read Andrew Ng's paper (/m1). Being concise and smooth in logic, Andrew's papers are always fun to read, even though I don't understand the gory details on his proofs of lemmas at the first time reading.

On the other hand, Yair Weiss's paper is more on the application of spectral algorithms in vision. It is nice review of converging progresses made in distant fields. But I just think this paper is a bit weak on the "unifying" effort. In another word, it did more pair-wise comparison but little on a common reference against which all 3 methods are compared.

Edited by author 04-16-2002 05:30 AM
Weiss begins Section 4, the discussion, with the following question: "Why do eigendecomposition methods for segmentation work?" Does he address this question anywhere in the paper? Or is this a question for future research? What is this paper supposed to be about anyway? Shouldn't a unifying view of methods based on eigenvectors of the "affinity matrix" at the very least describe what an "affinity matrix" is and why one might choose to find its eigenvectors (besides the fact that it seems to be a popular thing to do)?

Edited by author 04-16-2002 08:02 AM
Spectral partitioning algorithms are based on using eigenvalues of the affinity matrix of a graph.

For the case of an unweighted graph with n vertices.
The affinity matrix is a nxn matrix with the (i,j) entry

1 if vertices i and j are connected
and 0 if they are not connected.

This matrix is also referred to as the adjacency matrix.
The weighted generalization in which we associate weights with each edge in the graph instead of just 0 and 1 is referred to as the affinity matrix. It is called the affinity matrix since the edge weights are used to indicate similarity, higher magnitudes indicating high levels of similarity.

It is useful to read this paper independent of the computer vision background that it comes from .
For this purpose a very simple example is to consider a distribution of points in a two dimensional plane.

The affinity matrix is now calculated as:

exp(-d_ij^2/s^2)

here d_ij is the eucldeian distance between the points i and j.

s or sigma as its used in the paper is a measure of how sensitive you want to be to distances while constructing the affinity matrix.

I think the Ng & Jordan paper combined with the Shi and Malik paper serve as excellent background readings to make sense of this paper.

Image segmentation apears to be much more of an art than a science. Is there any established way to objectively evaluate the quality of segmentation? Also, it seems that all the algorithms presuppose a good representation of affinity. Is there research that evaluates the effectiveness of different affinity schemes?

To reply to Eric's question.

There is a distinction that has to be made between the two tasks of "clustering" and "perceptual grouping" or image segmentation.

Clustering by itself is just the task of detecting signification changes in a dataset and cutting it into pieces which are coherent within themselves and have a significant difference between them. The operation of clustering by itself does not provide for any sort of perceptually meaningful output.

The task of perceptual grouping (image segmentation) is much harder than clustering. Infact it consists of two tasks. One which involves defining measures of similarity between two parts of a scene and two actually using this information to divide the image scene into pieces.

So you are right when you say that all clustering presupposes a good affinity matrix, but then that is not all that surprising since, the clustering algorithm only interprets what you give it. Hence, garbage in garbage out holds for image segmentation also.

The task of objectively evaluating segmentation has seen some recent activity and is the focus of david martin's research at berkeley. He has collected a benchmark database of human segmentations of a collection of images and has defined metrics for comparing an arbitrary segmentation to these benchmark segmentations. You can find more information at

http://www.cs.berkeley.edu/~dmartin/research.html

The question of choosing cues or features which will result in good affinity schemes is a topic of a fair amount of research in psychology and vision science.
Some of the seminal work on this was done by the members of the gestalt psychology movement.

An excellent reference on this topic is the Vision Science book by Stephen Palmer.

There is finally the issue of choosing a distance metric to combine the various features to get a single scalar that represents the affinity between two points in the scene. An interesting study on this topic is

http://www-dbv.informatik.uni-bonn.de/abst...puzicha.iccv99.html

I think the authors accomplished their goal of presenting a unified view of segmentation using eigenvectors, even though the paper is short. They systematically analyze each main algorithm and then naturally come up with a way to get better results using a combination of the two schemes. This is good research. It would be interesting to see more experimental results, especially those that show the performance of the combined approach. They only run it on two images.

Edited by author 04-16-2002 06:20 PM
In reply to Joe's call for examples. I actually worked on a project for Serge in which I implemented the Shi and Malik algorithm for image segmentation. There is a sampling step involved that I don't believe is mentioned in the paper. Nevertheless, the segmentations are impression... for the most part. There are 30+ still examples and 3 short video shots.

dylan.ucsd.edu/~bleong

I agree with previous comments that the paper did provide a unified view of segmentation based on eigenvectors of one form or the other of the affinity matrix. I think the gain a deeper understanding about why and how these algorithms actually work one must read some of the papers suggested by Greg and Sameer. Without sufficient background knowledge i found the explanations presented in the paper weak. Then again, the point of the paper was not to explain why the algorithms work but rather to provide a unified view.

I also found that the paper was lacking the experimental results. Examining such results for all of the presented methods could give more insight into how these algorithms are different.

I been looking everywhere and haven’t bean able to find how I can make a Affinity Matrix or what it is…. I need it for image processing… and I would be wary glad if there is someone that can help me out..

I found a function that looks like this… But I can’t figure out how… x and y is working through a image…

aff(x,y)=exp{-((I(x)-I(y))^t*(I(x)-I(y))/2(standard DeviationI^2)}

Mattias Nilsson
Email: hqa3@hotmail.com

I been searching to find a clear description of mean shift algorithm. Is there any one who can brief me?
Niloo