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.