Graph Connectivity in Sparse Subspace Clustering/Superpixels and Stereo

Behrooz Nasihatkon/Yuhang Zhang (NICTA/ANU)

COMPUTER VISION AND ROBOTICS SERIES

DATE: 2011-03-24
TIME: 16:00:00 - 17:00:00
LOCATION: NICTA - 7 London Circuit
CONTACT: JavaScript must be enabled to display this email address.

ABSTRACT:
Graph Connectivity in Sparse Subspace Clustering: Subspace Clustering is the task of clustering data lying on a mixture of different subspaces. This problem arises in many computer vision applications including motion segmentation, video shot segmentation, illumination invariant clustering, image segmentation, image representation and compression and also in other areas like linear hybrid systems identification. Sparse Subspace Clustering (SSC) is one of most recent approaches to subspace segmentation with many advantages over the previous techniques. In SSC a graph is constructed whose nodes are the data points and whose edges are inferred from the L1-sparse representation of each point by the others. For SSC it has been proved that if the points lie on a mixture of independent subspaces, the graphical structure of each subspace is disconnected from the others. This gives a way to segment data points lying on independent subspaces. However, the problem of connectivity within each subspace is still unanswered. This is important since a failure in connectivity causes over-segmentation. In this talk we discuss the problem of connectivity of the SCC graph in each subspace. Our analysis is built upon the connection between the sparse representation through L1-norm minimization and the geometry of convex polytopes mentioned by the compressed sensing community. Here, it is proved that the connectivity within each subspace holds for 2- and 3-dimensional subspaces. The claim of connectivity, even in generic configurations, is disproved for higher dimensional subspaces by giving some counterexamples.

Superpixels and Stereo: Binocular stereo is one of the fundamental problems in computer vision. We introduce some new algorithms for stereo matching. In particular, we incorporate superpixels into stereo. With the help of superpixels, we not only significantly improve the efficiency of stereo matching, but also obtain better accuracy at boundary and occlusion areas. A new algorithm for creating superpixels will also be covered.
BIO:
Mr Behrooz Nasihatkon is a PhD candidate at NICTA. Mr Yuhang Zhang is a PhD candidate at ANU.