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 NP-hard 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.
In contrast to the continuous local optimisation methods, many vision problems can be formulated in a discrete manner such that they are amenable to solutions based on graph algorithms and dynamic programming (DP) @cite_29 . Since curves are intrinsically one-dimensional, various curve matching formulations can also be reduced to finding a shortest-path in a particular graph. Moreover, based on a recursive formulation using easier-to-solve subproblems, matching problems with templates that have a tree structure can frequently be tackled by DP. For a deformable matching of an open contour to a 2D image, a global solution based on DP has been proposed in @cite_49 . Also based on DP, in @cite_3 the authors present a method for solving the problem of deformably matching a 2D polygon to a 2D image for chordal graph polygons. In @cite_60 , the authors propose a globally optimal approach for matching a closed contour to a 2D image based on cycles in a product graph of the contour and the image. A related formulation that is also based on a product graph has recently been introduced in @cite_12 for deformable contour to 3D shape matching.
@cite_60 @cite_29 @cite_3 @cite_49 @cite_12
2150149968 2168311572 2173414649 2051800765
We propose a combinatorial solution to determine the optimal elastic matching of a deformable template to an image. The central idea is to cast the optimal matching of each template point to a corresponding image pixel as a problem of finding a minimum cost cyclic path in the three-dimensional product space spanned by the template and the input image. We introduce a cost functional associated with each cycle, which consists of three terms: a data fidelity term favoring strong intensity gradients, a shape consistency term favoring similarity of tangent angles of corresponding points, and an elastic penalty for stretching or shrinking. The functional is normalized with respect to the total length to avoid a bias toward shorter curves. Optimization is performed by Lawler's Minimum Ratio Cycle algorithm parallelized on state-of-the-art graphics cards. The algorithm provides the optimal segmentation and point correspondence between template and segmented curve in computation times that are essentially linear in the number of pixels. To the best of our knowledge, this is the only existing globally optimal algorithm for real-time tracking of deformable shapes. Optimization is a powerful paradigm for expressing and solving problems in a wide range of areas, and has been successfully applied to many vision problems. Discrete optimization techniques are especially interesting since, by carefully exploiting problem structure, they often provide nontrivial guarantees concerning solution quality. In this paper, we review dynamic programming and graph algorithms, and discuss representative examples of how these discrete optimization techniques have been applied to some classical vision problems. We focus on the low-level vision problem of stereo, the mid-level problem of interactive object segmentation, and the high-level problem of model-based recognition. We describe some techniques that can be used to represent and detect deformable shapes in images. The main difficulty with deformable template models is the very large or infinite number of possible nonrigid transformations of the templates. This makes the problem of finding an optimal match of a deformable template to an image incredibly hard. Using a new representation for deformable shapes, we show how to efficiently find a global optimal solution to the nonrigid matching problem. The representation is based on the description of objects using triangulated polygons. Our matching algorithm can minimize a large class of energy functions, making it applicable to a wide range of problems. We present experimental results of detecting shapes in medical images and images of natural scenes. We also consider the problem of learning a nonrigid shape model for a class of objects from examples. We show how to learn good models while constraining them to be in the form required by the matching algorithm. A novel deformable template is presented which detects the boundary of an open hand in a grayscale image without initialization by the user. A dynamic programming algorithm enhanced by pruning techniques finds the hand contour in the image in as little as 19 s on a Pentium 150 MHz. The template is translation- and rotation-invariant and accomodates shape deformation, significant occlusion and background clutter, and the presence of multiple hands.