Calendar - Weekly View

Abstract:  Computing mappings or correspondences between surfaces is an important tool for many applications in computer graphics, computer vision, medical imaging, morphology and related fields. Mappings of least angle distortion (conformal) and distance distortion (isometric) are of particular interest. The problem of finding conformal/isometric mappings between surfaces is typically formulated as a difficult non-convex optimization problem. Convex methods relax the non-convex optimization problem to a convex problem which can then be solved globally. The main issue then is whether the global solution of the convex problem is a good approximation for the original global solution. In this talk we will discuss two families of convex relaxations.

Conformal: We relax the problem of computing planar conformal mappings (Riemann mappings) to a simple convex problem which can be solved by solving a system of linear equations. We show that in this case the relaxation is exact- the solution of the convex problem is guaranteed to be the Riemann mapping!

Discrete isometric: for perfectly isometric asymmetric surfaces, the well known doubly-stochastic (DS) relaxation is exact. We generalize this result to the more challenging and important case of symmetric surfaces, once exactness is correctly defined for such problems. For non-isometric surfaces it is difficult to achieve exactness. Several relaxations have been proposed for such problems, where the more accurate relaxations are generally also more time consuming. We will describe two algorithm which strike a good balance between accuracy and efficiency: The DS++ algorithm, which is provably better than several popular algorithms but does not compromise efficiency, and the Sinkhorn-JA algorithm, which gives a first-order algorithm for efficiently solving the strong but high-dimensional JA relaxation. We utilize this algorithmic improvement to achieve state of the art results for shape matching and image arrangement.