Qihui Zhu's Homepage

We introduce a novel topological formulation for contour grouping. Our grouping criterion, called untangling cycles, exploits the inherent topological 1D structure of salient contours to extract them from the otherwise 2D image clutter. The key insight is that a pronounced 1D contour should have a clear ordering of edgels, to which all graph edges adhere, and no long range entanglements persist. Finding the contour grouping by optimizing these topological criteria is challenging. We introduce a novel concept of circular embedding to encode this combinatorial task. Our solution leads to computing the dominant complex eigenvectors/ eigenvalues of the random walk matrix of the contour grouping graph. We demonstrate major improvements over state-of-the-art approaches on challenging real images. [More...]

Resolving local ambiguities is an important issue for shape from shading (SFS). Pixel ambiguities of SFS can be eliminated by propagation approaches. However, patch ambiguities still exist. Therefore, we formulate the global disambiguation problem to resolve these ambiguities. Intuitively, it can be interpreted as flipping patches and adjusting heights such that the result surface has no kinks. Checking exponentially many possible configurations is intractable. Alternatively, we find a surface satisfying global integrability constraint. To encode the constraint, we introduce a graph formulation called configuration graph. Searching the solution on this graph can be reduced to a Max-cut problem and its solution is computable using semidefinite programming (SDP) relaxation. [More...]

In many areas of science and engineering, the problem arises how to discover low dimensional representations of high dimensional data. Finding low dimensional embedding can be written as semidefinite programs (SDPs) with low rank constraints. It has been observed that low rank solutions emerge naturally by computing high variance or maximal trace solutions. We show how to solve very large problems of this type by a matrix factorization of the graph Laplacian that leads to much smaller SDPs. We illustrate the approach on localization in large scale sensor networks, where optimizations involving tens of thousands of nodes can be solved in just a few minutes. [More...]