Dense elastic 3D shape matching

We propose a novel method for computing a geometrically consistent and spatially dense matching between two 3D shapes and by means of a convex relaxation. Rather than mapping points to points we match infinitesimal surface patches while preserving the geometric structures. In this spirit, we consider matchings between objects' surfaces as diffeomorphisms which are by definition geometrically consistent. Since such diffeomorphisms can be represented as closed surfaces in the product space, we are led to a minimal surface problem in a four-dimensional space. The proposed discrete formulation describes the search space with linear constraints which leads to a binary linear program. We propose an approximation approach to this potentially NP-hard problem. To overcome memory limitations, we also propose a multi-scale approach that refines a coarse matching until it reaches the finest level. As cost function for matching, we consider a thin shell energy, measuring the physical energy necessary to deform one shape into the other. Experimental results demonstrate that the proposed LP relaxation allows to compute high-quality matchings which reliably put into correspondence articulated 3D shapes. To our knowledge, this is the first solution to dense elastic surface matching which does not require an initialization and provides solutions of bounded optimality.