Abstract
We propose a combinatorial solution for the problem of
non-rigidly matching a 3D shape to 3D image data. To
this end, we model the shape as a triangular mesh and allow each triangle of this mesh to be rigidly transformed to
achieve a suitable matching to the image. By penalising
the distance and the relative rotation between neighbouring triangles our matching compromises between image and
shape information. In this paper, we resolve two major
challenges: Firstly, we address the resulting large and NPhard combinatorial problem with a suitable graph-theoretic
approach. Secondly, we propose an efficient discretisation
of the unbounded 6-dimensional Lie group SE(3). To our
knowledge this is the first combinatorial formulation for
non-rigid 3D shape-to-image matching. In contrast to existing local (gradient descent) optimisation methods, we obtain solutions that do not require a good initialisation and
that are within a bound of the optimal solution. We evaluate the proposed method on the two problems of non-rigid
3D shape-to-shape and non-rigid 3D shape-to-image registration and demonstrate that it provides promising results