Spectral Matting

by Anat Levin, Alex Rav-Acha and Dani Lischinski

This work is an extension of the previous paper. The idea is that since a graph with k components has k zero-valued eigenvalues, we could use the subspace of the smallest eigenvalues of a graph as an approximation of the subspace of zero-valued eigenvalues in ideal cases. The problem is that although we can get the subspace, the basis might not be the one for matting. And in practice we usually find a lot of eigen vectors and only select a smaller basis in the subspace for matting component. The last step is to combine several matting components to get the final matting matrix.

Then take a look at how to select a suitable basis. The objective should describe the sparsity of the components and we have several constraints. This is a non-convex optimization and it is solved with Newton method (taking the constraints into account) with an initial value of k-means. The combination of matting components will be comparatively easy, since we don't have many components and a brute-force search will do us good.

A Closed Form Solution to Natural Image Matting

by Anat Levin, Dani Lischinski and Yair Weiss

Matting is an interesting problem, which is very useful in digital image processing. The digital photos could be interpreted with a layer of foreground (including the subject) and another of background. The matting problem is that we have to decide a foreground image and a background image and the probability of each pixel belonging to foreground (something like an alpha channel). It is different from image segmentation (something like a soft-classifier) though. But it can also be solved with spectral clustering.

The idea is quite simple. The probability ci at pixel i is a linear combination of the intensity of each channel (RGB). Therefore c_i = a_i^r I_i^r + a_i^g I_i^g + a_i^b I_i^b + b. So we have to minimize their sum of squared residue with a regularizer of e a². This could be formulated with a quadratic form of a graph's Laplacian matrix. Therefore, given some constraints (e.g. users' input), the matting problem could be solve as an eigen value problem.

A New Approach to Data Driven Clustering

by Arik Azran, Zoubin Ghahramani

Well, on seeing Ghahramani, I guess it's no easy job @@ At first I was curious why their starting point resembles a lot from the paper on diffusion map. But soon I knew I was wrong. The first author is a Ph.D. student whose advisor is the second author. I wonder when I can publish a paper like he did in the top conferences. Sigh~ Maybe never.

Like diffusion map, they show us a Markov random walk model on a graph of samples. Then they notice the similarity of distributions starting at each sample can help clustering. They propose a clustering algorithm analogous to K-means(the proposed version minimizes KL divergence instead of L² norm). The optimization problem can be solved as K-means, yielding an local minima. I thought they might stop here, but they didn't.

Careful readers notice that the number of clusters, K and the time t for random walk are not determined yet. So the following part deals with these two parameters. Given K, learn t. It's an easy problem. If the distribution matrix should be maximally preserved, low rank approximation will take the leading eigen values and we abandon the rest when the gap between them is maximized.

Then how can we obtain the desired parameters from data? Well, it's not that difficult. With the similar idea, when some gap is maximized while we don't know which K.

But then, is it possible to formulate a hierarchical clustering algorithm with this random walk? Well, use the gap size as the plausibility for the partition. Choose the smallest number of plausible clusters(big gap and few clusters). And do partition and recursively carry out the algorithm.

A piece of fresh work needs few references.