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.
Labelling problems are ubiquitous in computer vision and appear both in continuous and discrete settings @cite_17 . The popular Markov Random Field (MRF) framework offers a Bayesian treatment thereof @cite_18 . Also, linear programming relaxations of MRFs have been studied @cite_14 . The continuous approaches to multi-labelling include various convex relaxations @cite_38 @cite_5 @cite_56 @cite_20 , multi-labelling problems with total variation regularisation of functions with values on manifolds @cite_46 , as well as sublabel-accurate convex relaxations @cite_9 @cite_36 . Among the discrete multi-labelling methods are the previously-mentioned graph-cuts, which can be used to find global solutions for certain binary labelling problems, including problems with submodular pairwise costs @cite_44 . For a sub-class of multi-labelling problems a global solution can also be found @cite_44 . This sub-class includes pairwise costs that are convex in terms of totally ordered labels @cite_25 . In addition, efficient algorithms for finding local optima of general multi-labelling problems have been proposed @cite_26 @cite_6 , which even have theoretical optimality guarantees. A more detailed description of the energy functions that can be optimised using graph-cuts is given in @cite_33 @cite_55 @cite_44 .
@cite_38 @cite_18 @cite_14 @cite_26 @cite_33 @cite_36 @cite_9 @cite_55 @cite_6 @cite_56 @cite_44 @cite_5 @cite_46 @cite_25 @cite_20 @cite_17
1981238278 2110306576 2162366888 2022767198
We consider the problem of optimizing multilabel MRFs, which is in general NP-hard and ubiquitous in low-level computer vision. One approach for its solution is to formulate it as an integer linear programming and relax the integrality constraints. The approach we consider in this paper is to first convert the multi-label MRF into an equivalent binary-label MRF and then to relax it. The resulting relaxation can be efficiently solved using a maximum flow algorithm. Its solution provides us with a partially optimal labelling of the binary variables. This partial labelling is then easily transferred to the multi-label problem. We study the theoretical properties of the new relaxation and compare it with the standard one. Specifically, we compare tightness, and characterize a subclass of problems where the two relaxations coincide. We propose several combined algorithms based on the technique and demonstrate their performance on challenging computer vision problems. This paper addresses the problem of exactly inferring the maximum a posteriori solutions of discrete multi-label MRFs or CRFs with higher order cliques. We present a framework to transform special classes of multi-label higher order functions to submodular second order Boolean functions (referred to as Fs 2), which can be minimized exactly using graph cuts and we characterize those classes. The basic idea is to use two or more Boolean variables to encode the states of a single multi-label variable. There are many ways in which this can be done and much interesting research lies in finding ways which are optimal or minimal in some sense. We study the space of possible encodings and find the ones that can transform the most general class of functions to Fs 2. Our main contributions are two-fold. First, we extend the subclass of submodular energy functions that can be minimized exactly using graph cuts. Second, we show how higher order potentials can be used to improve single view 3D reconstruction results. We believe that our work on exact minimization of higher order energy functions will lead to similar improvements in solutions of other labelling problems. Markov Random Fields (MRFs) are ubiquitous in low- level computer vision. In this paper, we propose a new approach to the optimization of multi-labeled MRFs. Similarly to a-expansion it is based on iterative application of binary graph cut. However, the number of binary graph cuts required to compute a labelling grows only logarithmically with the size of label space, instead of linearly. We demonstrate that for applications such as optical flow, image restoration, and high resolution stereo, this gives an order of magnitude speed-up, for comparable energies. Iterations are performed by "fusion" of solutions, done with QPBO which is related to graph cut but can deal with non- submodularity. At convergence, the method achieves optima on a par with the best competitors, and sometimes even exceeds them. Multilabel problems are of fundamental importance in computer vision and image analysis. Yet, finding global minima of the associated energies is typically a hard computational challenge. Recently, progress has been made by reverting to spatially continuous formulations of respective problems and solving the arising convex relaxation globally. In practice this leads to solutions which are either optimal or within an a posteriori bound of the optimum. Unfortunately, in previous methods, both run time and memory requirements scale linearly in the total number of labels, making these methods very inefficient and often not applicable to problems with higher dimensional label spaces. In this paper, we propose a reduction technique for the case that the label space is a continuous product space and the regularizer is separable, i.e., a sum of regularizers for each dimension of the label space. In typical real-world labeling problems, the resulting convex relaxation requires orders of magnitude less memory and c...