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 2949291209 2397509712 2017444115
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. We propose a convex-concave programming approach for the labeled weighted graph matching problem. The convex-concave programming formulation is obtained by rewriting the weighted graph matching problem as a least-square problem on the set of permutation matrices and relaxing it to two different optimization problems: a quadratic convex and a quadratic concave optimization problem on the set of doubly stochastic matrices. The concave relaxation has the same global minimum as the initial graph matching problem, but the search for its global minimum is also a hard combinatorial problem. We therefore construct an approximation of the concave problem solution by following a solution path of a convex-concave problem obtained by linear interpolation of the convex and concave formulations, starting from the convex relaxation. This method allows to easily integrate the information on graph label similarities into the optimization problem, and therefore to perform labeled weighted graph matching. The algorithm is compared with some of the best performing graph matching methods on four datasets: simulated graphs, QAPLib, retina vessel images and handwritten chinese characters. In all cases, the results are competitive with the state-of-the-art. A novel multi-criteria optimization framework for matching of partially visible shapes in multiple images using joint geometric graph embedding is proposed. The proposed framework achieves matching of partial shapes in images that exhibit extreme variations in scale, orientation, viewpoint and illumination and also instances of occlusion; conditions which render impractical the use of global contour-based descriptors or local pixel-level features for shape matching. The proposed technique is based on optimization of the embedding distances of geometric features obtained from the eigenspectrum of the joint image graph, coupled with regularization over values of the mean pixel intensity or histogram of oriented gradients. It is shown to obtain successfully the correspondences denoting partial shape similarities as well as correspondences between feature points in the images. A new benchmark dataset is proposed which contains disparate image pairs with extremely challenging variations in viewing conditions when compared to an existing dataset [18]. The proposed technique is shown to significantly outperform several state-of-the-art partial shape matching techniques on both datasets. A terrain-based underwater navigation using sonar bathymetric profiles is presented. It deals with matching high-resolution local depth maps against a large on-board reference map. The matching algorithm locates the local depth map within the a priori known larger map to determine the absolute position and heading of the vehicle. Two separate approaches for this problem are presented. The first uses a contour-based representation of depth maps. Contours are extracted from both local and reference maps. Invariant attributes under rigid plane transformation are associated with each contour point, so that the problem is reduced to a point-based matching algorithm: given two point sets, find correspondences and estimate transformation between the two sets. We shall particularly focus on the formalism of partial differential equations, which is used to smooth depth maps in a morphologically invariant way and to obtain anisotropic contours. The second approach is also based on a correspondence algorithm. Here, ...