Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> Until recently, artificial intelligence researchers have frowned upon the application of probability propagation in Bayesian belief networks that have cycles. The probability propagation algorithm is only exact in networks that are cycle-free. However, it has recently been discovered that the two best error-correcting decoding algorithms are actually performing probability propagation in belief networks with cycles. <s> BIB001 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> In this paper we address the problem of minimizing a large class of energy functions that occur in early vision. The major restriction is that the energy function's smoothness term must only involve pairs of pixels. We propose two algorithms that use graph cuts to compute a local minimum even when very large moves are allowed. The first move we consider is an /spl alpha/-/spl beta/-swap: for a pair of labels /spl alpha/,/spl beta/, this move exchanges the labels between an arbitrary set of pixels labeled a and another arbitrary set labeled /spl beta/. Our first algorithm generates a labeling such that there is no swap move that decreases the energy. The second move we consider is an /spl alpha/-expansion: for a label a, this move assigns an arbitrary set of pixels the label /spl alpha/. Our second algorithm, which requires the smoothness term to be a metric, generates a labeling such that there is no expansion move that decreases the energy. Moreover, this solution is within a known factor of the global minimum. We experimentally demonstrate the effectiveness of our approach on image restoration, stereo and motion. <s> BIB002 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> In this paper we propose a novel approach to define task-driven regularization constraints in deformable image registration using learned deformation priors. Our method consists of representing deformation through a set of control points and an interpolation strategy. Then, using a training set of images and the corresponding deformations we seek for a weakly connected graph on the control points where edges define the prior knowledge on the deformation. This graph is obtained using a clustering technique which models the co-dependencies between the displacements of the control points. The resulting classification is used to encode regularization constraints through connections between cluster centers and cluster elements. Additionally, the global structure of the deformation is encoded through a fully connected graph on the cluster centers. Then, registration of a new pair of images consists of displacing the set of control points where on top of conventional image correspondence costs, we introduce costs that are based on the relative deformation of two control points with respect to the learned deformation. The resulting paradigm is implemented using a discrete Markov Random Field which is optimized using efficient linear programming. Promising experimental results on synthetic and real data demonstrate the potential of our approach. <s> BIB003 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> Non-rigid image registration is an ill-posed yet challenging problem due to its supernormal high degree of freedoms and inherent requirement of smoothness. Graph-cuts method is a powerful combinatorial optimization tool which has been successfully applied into image segmentation and stereo matching. Under some specific constraints, graph-cuts method yields either a global minimum or a local minimum in a strong sense. Thus, it is interesting to see the effects of using graph-cuts in non-rigid image registration. In this paper, we formulate non-rigid image registration as a discrete labeling problem. Each pixel in the source image is assigned a displacement label (which is a vector) indicating which position in the floating image it is spatially corresponding to. A smoothness constraint based on first derivative is used to penalize sharp changes in displacement labels across pixels. The whole system can be optimized by using the graph-cuts method via alpha-expansions. We compare 2D and 3D registration results of our method with two state-of-the-art approaches. It is found that our method is more robust to different challenging non-rigid registration cases with higher registration accuracy. <s> BIB004 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> We propose a novel MRF-based model for deformable image matching. Given two images, the task is to estimate a mapping from one image to the other maximizing the quality of the match. We consider mappings defined by a discrete deformation field constrained to preserve 2D continuity. We pose the task as finding MAP configurations of a pairwise MRF. We propose a more compact MRF representation of the problem which leads to a weaker, though computationally more tractable, linear programming relaxation -the approximation technique we choose to apply. The number of dual LP variables grows linearly with the search window side, rather than quadratically as in previous approaches. To solve the relaxed problem (suboptimally), we apply TRW-S (Sequential Tree-Reweighted Message passing) algorithm [13, 5]. Using our representation and the chosen optimization scheme, we are able to match much wider deformations than was considered previously in global optimization framework. We further elaborate on continuity and data terms to achieve more appropriate description of smooth deformations. The performance of our technique is demonstrated on both synthetic and real-world experiments. <s> BIB005 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> A new framework is presented for both understanding and developing graph-cut-based combinatorial algorithms suitable for the approximate optimization of a very wide class of Markov random fields (MRFs) that are frequently encountered in computer vision. The proposed framework utilizes tools from the duality theory of linear programming in order to provide an alternative and more general view of state-of-the-art techniques like the alpha-expansion algorithm, which is included merely as a special case. Moreover, contrary to alpha-expansion, the derived algorithms generate solutions with guaranteed optimality properties for a much wider class of problems, for example, even for MRFs with nonmetric potentials. In addition, they are capable of providing per-instance suboptimality bounds in all occasions, including discrete MRFs with an arbitrary potential function. These bounds prove to be very tight in practice (that is, very close to 1), which means that the resulting solutions are almost optimal. Our algorithms' effectiveness is demonstrated by presenting experimental results on a variety of low-level vision tasks, such as stereo matching, image restoration, image completion, and optical flow estimation, as well as on synthetic problems. <s> BIB006 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> In this paper we propose a novel approach for automatic segmentation of cartilage using a statistical atlas and efficient primal/dual linear programming. To this end, a novel statistical atlas construction is considered from registered training examples. Segmentation is then solved through registration which aims at deforming the atlas such that the conditional posterior of the learned (atlas) density is maximized with respect to the image. Such a task is reformulated using a discrete set of deformations and segmentation becomes equivalent to finding the set of local deformations which optimally match the model to the image. We evaluate our method on 56 MRI data sets (28 used for the model and 28 used for evaluation) and obtain a fully automatic segmentation of patella cartilage volume with an overlap ratio of 0.84 with a sensitivity and specificity of 94.06% and 99.92%, respectively. <s> BIB007 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> An efficient registration algorithm working on non-rigid 3D objects is presented. We formulate the registration as a discrete labe ling problem on MRFs model whose energy can be minimized by optimization techniques in the literature. Due to the huge search range in three-dimensional space, previous approaches produces a vast amount of labels for a node in the MRFs graph. To reduce the number of labels, we decompose a node into three nodes so that the labels in each node represent just one-dimensional displacement. This procedure introduces a factor node with a clique potential of size three, defining ternary interaction between the decomposed nodes. We convert the factor node into pairwise interactions and adopt the tree-r eweighted message passing technique, which guarantees the convergence of lower bound of the energy function. In experiments we use clinical and synthetically deformed 3D medical images. Result shows the proposed method enhances computational efficiency without loss of accuracy. <s> BIB008 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> In this paper we introduce a novel method to address minimization of static and dynamic MRFs. Our approach is based on principles from linear programming and, in particular, on primal-dual strategies. It generalizes prior state-of-the-art methods such as @a-expansion, while it can also be used for efficiently minimizing NP-hard problems with complex pair-wise potential functions. Furthermore, it offers a substantial speedup - of a magnitude 10 - over existing techniques, due to the fact that it exploits information coming not only from the original MRF problem, but also from a dual one. The proposed technique consists of recovering pair of solutions for the primal and the dual such that the gap between them is minimized. Therefore, it can also boost performance of dynamic MRFs, where one should expect that the new pair of primal-dual solutions is closed to the previous one. Promising results in a number of applications, and theoretical, as well as numerical comparisons with the state of the art demonstrate the extreme potentials of this approach. <s> BIB009 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> In this paper, we introduce a novel and efficient approach to dense image registration, which does not require a derivative of the employed cost function. In such a context, the registration problem is formulated using a discrete Markov random field objective function. First, towards dimensionality reduction on the variables we assume that the dense deformation field can be expressed using a small number of control points (registration grid) and an interpolation strategy. Then, the registration cost is expressed using a discrete sum over image costs (using an arbitrary similarity measure) projected on the control points, and a smoothness term that penalizes local deviations on the deformation field according to a neighborhood system on the grid. Towards a discrete approach, the search space is quantized resulting in a fully discrete model. In order to account for large deformations and produce results on a high resolution level, a multi-scale incremental approach is considered where the optimal solution is iteratively updated. This is done through successive morphings of the source towards the target image. Efficient linear programming using the primal dual principles is considered to recover the lowest potential of the cost function. Very promising results using synthetic data with known deformations and real data demonstrate the potentials of our approach. <s> BIB010 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> In this paper, we propose a nonrigid registration method using the Markov Random Field (MRF) model with a higher-order spatial prior. The registration is designed as finding a set of discrete displacement vectors on a deformable mesh, using the energy model defined by label sets relating to these vectors. This work provides two main ideas to improve the reliability and accuracy of the registration. First, we propose a new energy model which adopts a higher-order spatial prior for the smoothness cost. This model improves limitations of pairwise spatial priors which cannot fully incorporate the natural smoothness of deformations. Next we introduce a dynamicenergy model to generate optimal displacements. This model works iteratively with optimal data cost while the spatial prior preserve the smoothness cost of previous iteration. For optimization, we convert the proposed model to pairwise MRF model to apply the tree-reweighted message passing (TRW). Concerning the complexity, we apply the decomposedscheme to reduce the label dimension of the proposed model and incorporate the linear constrained node (LCN) technique for efficient message passings. In experiments, we demonstrate the competitive performance of the proposed model compared with previous models, presenting both quantitative and qualitative analysis. <s> BIB011 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> Non-rigid image registration is widely used in medical image analysis and image processing. It remains a challenging research problem due to its smoothness requirement and high degree of freedoms in the deformation process. In [1], a method is proposed to solve non-rigid image registration via graph-cuts algorithm by modeling the registration process as a discrete labeling problem. A displacement label (vector) is assigned to each pixel in the source image to indicate the corresponding position in the floating image. The whole system is then optimized by using the graph-cuts algorithm via alpha-expansions [2]. As the initial point is not required for the graph-cuts algorithm, the method proposed by [1] is a single-level registration. In this paper, rather single-level, we enable multi-level non-rigid image registration using graph-cuts by passing the deformation field of the current resolution level to the successive finer one. By applying the proposed multi-level registration method, the number of labels used in each level is greatly reduced due to lower image resolution being used in coarser levels. Therefore, the speed of the registration process is improved. We compare our results with the original single-level version, DEMONS and FFD. It is found that our method improves the speed of non-rigid image registration by 50% and meanwhile maintains similar robustness and registration accuracy with the single-level version. <s> BIB012 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> In this paper we propose a novel framework to unite a population to an optimal (unknown) pose through their mutual deformation. The registration criterion comprises three terms, the first imposes compactness on appearance of the registered population at the pixel level, the second tries to minimize the individual distances between all possible pairs of images, while the last is a regularization one imposing smoothness on the deformation fields. The problem is reformulated as a graphical model that consists of hidden (deformation fields) and observed variables (intensities). A novel deformation grid-based scheme is proposed that guarantees the diffeomorphism of the deformation and is computationally favorably compared to standard deformation methods. Towards addressing important deformations we propose a compositional approach where the deformations are recovered through the sub-optimal solutions of successive discrete MRFs by using efficient linear programming. Promising experimental results using real 2D data demonstrate the potentials of our approach. <s> BIB013 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> Segmentation is one of the most critical problems in medical imaging. State-of-the art methods often are based on prior knowledge that can either encode geometry, appearance or both. Despite enormous work in the field, the mainstream is based on the concept of case-to-case segmentation. In this paper, we introduce the notion of mutual population segmentation using discrete optimization where results from a given example influence results for the rest of the examples towards improving the overall segmentation performance. The aim is to combine prior knowledge along with consistency through the simultaneous segmentation of the whole population. This is achieved through their mutual deformation towards the atlas, while being constrained through a simultaneous all-to-all deformable diffeomorphic registration. Promising results demonstrate the potentials of the method. <s> BIB014 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> In this paper, we consider the problem of stereo matching using loopy belief propagation. Unlike previous methods which focus on the original spatial resolution, we hierarchically reduce the disparity search range. By fixing the number of disparity levels on the original resolution, our method solves the message updating problem in a time linear in the number of pixels contained in the image and requires only constant memory space. Specifically, for a 800 × 600 image with 300 disparities, our message updating method is about 30× faster (1.5 second) than standard method, and requires only about 0.6% memory (9 MB). Also, our algorithm lends itself to a parallel implementation. Our GPU implementation (NVIDIA Geforce 8800GTX) is about 10× faster than our CPU implementation. Given the trend toward higher-resolution images, stereo matching using belief propagation with large number of disparity levels as efficient as the small ones makes our method future-proof. In addition to the computational and memory advantages, our method is straightforward to implement1. <s> BIB015 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> In this paper, we propose a novel method for the spatial normalization of diffusion tensor images. The proposed method takes advantage of both the diffusion information and the spatial location of tensor in order to define an appropriate metric in a probabilistic framework. A registration energy is defined in a Reproducing Kernel Hilbert Space (RKHS), encoding the image dissimilarity and the regularity of the deformation field in both the translation and the rotation space. The problem is reformulated as a graphical model where the latent variables are the rotation and the translation that should be applied to every tensor and the observed variables are the tensors themselves. Efficient linear programming is used to minimize the resulting energy. Quantitative and qualitative results on a manually annotated dataset of diffusion tensor images demonstrate the potential of the proposed method. <s> BIB016 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> Optical imaging is an efficient mean to measure biological signal. However, it can suffer from low spatial and temporal resolution while animal deformable displacements could also degrade significantly the localization of the measurements. In this paper, we propose a novel approach to perform fusion of cinematic flow and optical imaging towards enhancement of the biological signal. To this end, fusion is reformulated as a population (all vs. all) registration problem where the two (being spatially aligned) signals are registered in time using the same deformation field. Implicit silhouette and landmark matching are considered for the cinematic images and are combined with global statistical congealing-type measurements of the optical one. The problem is reformulated using a discrete MRF, where optical imaging costs are expressed in singleton (global) potentials, while smoothness constraints as well as cinematic measurements through pair-wise potentials. Promising experimental results demonstrate the potentials of our approach. <s> BIB017 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> We propose a framework for intensity-based registration of images by linear transformations, based on a discrete Markov random field (MRF) formulation. Here, the challenge arises from the fact that optimizing the energy associated with this problem requires a high-order MRF model. Currently, methods for optimizing such high-order models are less general, easy to use, and efficient, than methods for the popular second-order models. Therefore, we propose an approximation to the original energy by an MRF with tractable second-order terms. The approximation at a certain point p in the parameter space is the normalized sum of evaluations of the original energy at projections of p to two-dimensional subspaces. We demonstrate the quality of the proposed approximation by computing the correlation with the original energy, and show that registration can be performed by discrete optimization of the approximated energy in an iteration loop. A search space refinement strategy is employed over iterations to achieve sub-pixel accuracy, while keeping the number of labels small for efficiency. The proposed framework can encode any similarity measure is robust to the settings of the internal parameters, and allows an intuitive control of the parameter ranges. We demonstrate the applicability of the framework by intensity-based registration, and 2D–3D registration of medical images. The evaluation is performed by random studies and real registration tasks. The tests indicate increased robustness and precision compared to corresponding standard optimization of the original energy, and demonstrate robustness to noise. Finally, the proposed framework allows the transfer of advances in MRF optimization to linear registration problems. <s> BIB018 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> In this paper, we introduce a novel approach to bridge the gap between the landmark-based and the iconic-based voxel-wise registration methods. The registration problem is formulated with the use of Markov Random Field theory resulting in a discrete objective function consisting of thee parts. The first part of the energy accounts for the iconic-based volumetric registration problem while the second one for establishing geometrically meaningful correspondences by optimizing over a set of automatically generated mutually salient candidate pairs of points. The last part of the energy penalizes locally the difference between the dense deformation field due to the iconic-based registration and the implied displacements due to the obtained correspondences. Promising results in real MR brain data demonstrate the potentials of our approach. <s> BIB019 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> We present a new energy model for optical flow estimation on discrete MRF framework. The proposed model yields discrete analog to the prevailing model with diffusion tensor-based regularizer, which has been optimized by variational approach. Inspired from the fact that the regularization process works as a convolution kernel filtering, we formulate the difference between original flow and filtered flow as a smoothness prior. Then the discrete framework enables us to employ a robust penalizer less concerning convexity and differentiability of the energy function. In addition, we provide a new kernel design based on the bilateral filter, adaptively controlling intensity variance according to the local statistics. The proposed kernel simultaneously addresses over-segmentation and over-smoothing problems, which is hard to achieve by tuning parameters. Involving a complex graph structure with large label sets, this work also presents a strategy to efficiently reduce memory requirement and computational time to a tolerable state. Experimental result shows the proposed method yields plausible results on the various data sets including large displacement and textured region. <s> BIB020 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> We present a graph-cuts based method for non-rigid medical image registration on brain magnetic resonance images. In this paper, the non-rigid medical image registration problem is reformulated as a discrete labeling problem. Based on a voxel-to-voxel intensity similarity measure, each voxel in the source image is assigned a displacement label, which represents a displacement vector indicating which position in the floating image it is spatially corresponding to. In the proposed method, a smoothness constraint based on the first derivative is used to penalize sharp changes in the adjacent displacement labels across voxels. The image registration problem is therefore modeled by two energy terms based on intensity similarity and smoothness of the displacement field. These energy terms are submodular and can be optimized by using the graph-cuts method via @[email protected]?expansions, which is a powerful combinatorial optimization tool and capable of yielding either a global minimum or a local minimum in a strong sense. Using the realistic brain phantoms obtained from the Simulated Brain Database, we compare the registration results of the proposed method with two state-of-the-art medical image registration approaches: free-form deformation based method and demons method. In addition, the registration results are also compared with that of the linear programming based image registration method. It is found that the proposed method is more robust against different challenging non-rigid registration cases with consistently higher registration accuracy than those three methods, and gives realistic recovered deformation fields. <s> BIB021 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> Discrete optimization offers attractive capabilities for non-rigid medical image registration. Based on previous work on stereo vision with large displacement spaces, we propose a novel non-rigid registration method. The main idea to minimize the computational burden to constant time complexity is to reduce the search space hierarchically from coarse to fine levels. The large search space helps us to avoid local minima in the optimization scheme. We apply our method to a number of challenging registration tasks. Our approach compares very favourably against state-of-the-art registration methods. <s> BIB022 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> While image alignment has been studied in different areas of computer vision for decades, aligning images depicting different scenes remains a challenging problem. Analogous to optical flow, where an image is aligned to its temporally adjacent frame, we propose SIFT flow, a method to align an image to its nearest neighbors in a large image corpus containing a variety of scenes. The SIFT flow algorithm consists of matching densely sampled, pixelwise SIFT features between two images while preserving spatial discontinuities. The SIFT features allow robust matching across different scene/object appearances, whereas the discontinuity-preserving spatial model allows matching of objects located at different parts of the scene. Experiments show that the proposed approach robustly aligns complex scene pairs containing significant spatial differences. Based on SIFT flow, we propose an alignment-based large database framework for image analysis and synthesis, where image information is transferred from the nearest neighbors to a query image according to the dense scene correspondence. This framework is demonstrated through concrete applications such as motion field prediction from a single image, motion synthesis via object transfer, satellite image registration, and face recognition. <s> BIB023 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> This review introduces a novel deformable image registration paradigm that exploits Markov random field formulation and powerful discrete optimization algorithms. We express deformable registration as a minimal cost graph problem, where nodes correspond to the deformation grid, a node's connectivity corresponds to regularization constraints, and labels correspond to 3D deformations. To cope with both iconic and geometric (landmark-based) registration, we introduce two graphical models, one for each subproblem. The two graphs share interconnected variables, leading to a modular, powerful, and flexible formulation that can account for arbitrary image-matching criteria, various local deformation models, and regularization constraints. To cope with the corresponding optimization problem, we adopt two optimization strategies: a computationally efficient one and a tight relaxation alternative. Promising results demonstrate the potential of this approach. Discrete methods are an important new trend in medical image registration, as they provide several improvements over the more traditional continuous methods. This is illustrated with several key examples where the presented framework outperforms existing general-purpose registration methods in terms of both performance and computational complexity. Our methods become of particular interest in applications where computation time is a critical issue, as in intraoperative imaging, or where the huge variation in data demands complex and application-specific matching criteria, as in large-scale multimodal population studies. The proposed registration framework, along with a graphical interface and corresponding publications, is available for download for research purposes (for Windows and Linux platforms) from http://www.mrf-registration.net. <s> BIB024 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> A general-purpose deformable registration algorithm referred to as "DRAMMS" is presented in this paper. DRAMMS bridges the gap between the traditional voxel-wise methods and landmark/feature-based methods with primarily two contributions. First, DRAMMS renders each voxel relatively distinctively identifiable by a rich set of attributes, therefore largely reducing matching ambiguities. In particular, a set of multi-scale and multi-orientation Gabor attributes are extracted and the optimal components are selected, so that they form a highly distinctive morphological signature reflecting the anatomical and geometric context around each voxel. Moreover, the way in which the optimal Gabor attributes are constructed is independent of the underlying image modalities or contents, which renders DRAMMS generally applicable to diverse registration tasks. A second contribution of DRAMMS is that it modulates the registration by assigning higher weights to those voxels having higher ability to establish unique (hence reliable) correspondences across images, therefore reducing the negative impact of those regions that are less capable of finding correspondences (such as outlier regions). A continuously-valued weighting function named "mutual-saliency" is developed to reflect the matching uniqueness between a pair of voxels implied by the tentative transformation. As a result, voxels do not contribute equally as in most voxel-wise methods, nor in isolation as in landmark/feature-based methods. Instead, they contribute according to the continuously-valued mutual-saliency map, which dynamically evolves during the registration process. Experiments in simulated images, inter-subject images, single-/multi-modality images, from brain, heart, and prostate have demonstrated the general applicability and the accuracy of DRAMMS. <s> BIB025 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> There are two main issues that make nonrigid image registration a challenging task. First, voxel intensity similarity may not be necessarily equivalent to anatomical similarity in the image correspondence searching process. Second, during the imaging process, some interferences such as unexpected rotations of input volumes and monotonic gray-level bias fields can adversely affect the registration quality. In this paper, a new feature-based nonrigid image registration method is proposed. The proposed method is based on a new type of image feature, namely, uniform spherical region descriptor (USRD), as signatures for each voxel. The USRD is rotation and monotonic gray-level transformation invariant and can be efficiently calculated. The registration process is therefore formulated as a feature matching problem. The USRD feature is integrated with the Markov random field labeling framework in which energy function is defined for registration. The energy function is then optimized by the α-expansion algorithm. The proposed method has been compared with five state-of-the-art registration approaches on both the simulated and real 3-D databases obtained from the BrainWeb and Internet Brain Segmentation Repository, respectively. Experimental results demonstrate that the proposed method can achieve high registration accuracy and reliable robustness behavior. <s> BIB026 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> Image registration is in principle a symmetric problem. Nonetheless, most intensity-based non-rigid algorithms are asymmetric. In this paper, we propose a novel symmetric deformable registration algorithm formulated in a Markov Random Fields framework where both images are let to deform towards a common domain that lies halfway between two image domains. A grid-based deformation model is employed and the latent variables correspond to the displacements of the grid-nodes towards both image domains. First-order interactions between the unknown variables model standard smoothness priors. Efficient linear programming is consider to recover the optimal solution. The discrete nature of our algorithm allows the handling of both mono- and multi-modal registration problems. Promising experimental results demonstrate the potentials of our approach. <s> BIB027 </s> Deformable Medical Image Registration: A Survey <s> 1) Graph-Based Methods: <s> Recently, researchers have demonstrated that "loopy belief propagation" -- the use of Pearl's polytree algorithm in a Bayesian network with loops -- can perform well in the context of error-correcting codes. The most dramatic instance of this is the near Shannon-limit performance of "Turbo Codes" -- codes whose decoding algorithm is equivalent to loopy belief propagation in a chain-structured Bayesian network. ::: ::: In this paper we ask: is there something special about the error-correcting code context, or does loopy propagation work as an approximate inference scheme in a more general setting? We compare the marginals computed using loopy propagation to the exact ones in four Bayesian network architectures, including two real-world networks: ALARM and QMR. We find that the loopy beliefs often converge and when they do, they give a good approximation to the correct marginals. However, on the QMR network, the loopy beliefs oscillated and had no obvious relationship to the correct posteriors. We present some initial investigations into the cause of these oscillations, and show that some simple methods of preventing them lead to the wrong results. <s> BIB028
The first class of methods is based on the max-flow min-cut principle [416] that states that the maximum amount of flow that can pass from the source to the sink is equal to the minimum cut that separates the two terminal nodes. The two terminal nodes are defined as source and sink depending on the direction of their edges. The cost of a cut is given by the sum of the weights of the edges that were removed. Greig et al.  showed how to calculate the exact maximum a posteriori estimation for the case of the Ising model through a single graph cut computation. Boykov et al. BIB002 proposed the -expansion algorithm that extended  to the multi-label case. This algorithm starts from an initial labeling and then checks every label to see if the energy may be decreased by allowing any set of nodes to change their label to the one under study. The optimal labeling at each iteration is estimated by performing a single graph cut. In medical image registration, -expansion is the optimizer used by Tang and Chung BIB004 , So et al. BIB012 - BIB021 and Liao and Chung BIB026 . The authors constructed a graph the size of the image assuming a 6-connectivity scheme and densely sampled the solution space resulting in a large set of candidate solutions. The size of the graph as well as the large label set resulted in important computational times. 2) Belief Propagation Methods: Belief propagation (BP) methods  constitute the second class of methods. These methods are based on local message exchange between the nodes of the graph and then backtracking to recover the best solution to the problem. Belief propagation methods can provide an exact inference for chain and tree-structured graphs. In the case of graphs that contain loops, Loopy Belief propagation methods have been shown to converge to satisfactory solutions BIB001 , BIB028 . A drawback related to the messages is the large storage requirement when a large set of solutions is involved. Yang et al. BIB015 proposed a constant space BP method that does not depend on the number of labels. The basic idea of the method was to a apply a coarse-to-fine strategy to the solution space so that the overall complexity remains constant. The numbers of labels decreased from coarser to finer levels by keeping only the ones for whose the cost was the smallest. Heinrich et al. BIB022 applied this technique in a discrete registration setting to recover respiratory motion. Shekhovtsov et al. BIB005 proposed an efficient MRF deformation model for nonrigid image matching by decomposing the original grid graph into two isomorphic layers. The nodes of each layer modeled the displacement along each axis. Nodes placed at corresponding positions in each layer were connected with an edge that modeled the data matching term. Intra-layer edges encoded the regularization term. This decomposition reduced the number of operations required to update the messages. Lee et al. extended this model to the case BIB008 . The graph was decomposed into three layers and ternary interactions were used to model the data cost. Liu et al. BIB023 used the decomposed model BIB005 along with loopy BP to match SIFT-descriptors along the flow vectors. Kwon et al. proposed a similar approach that matches dense local descriptors using a higher-order smoothness prior  . 3) Linear-Programming Approaches: The last class of methods comprises techniques that are based on Linear Programming. These approaches aim to solve an LP relaxation of the original problem that is in general -hard. Komodakis et al. BIB006 , BIB009 cast the original problem as a linear integer program and proposed a method (FastPD) that takes into account the primal and dual LP relaxations. Glocker et al. BIB010 , BIB024 used FastPD to infer the displacements of a grid-based deformation model in image registration. Hard constraints on the set of solutions, imposed through the construction of the label set, enforced the diffeomorphic property on the deformation field despite the use of a simple firstorder regularization term. Glocker et al. extended this method to tackle atlas-based registration in BIB007 , and to knowledge-based registration with the use of learned pairwise relations in BIB003 . Ou et al. BIB025 used it to solve feature-based registration, while Sotiras et al. to solve diffusion tensor registration BIB016 and symmetric iconic registration BIB027 . Sotiras et al. used this optimizer to tackle group-wise registration BIB013 , BIB014 . Savinaud et al. extended this method to multi-channel images BIB017 . These methods modeled the registration problem with the use of an -layer graph where intra-layer edges encoded a smoothing term and inter-layer edges encoded the data matching term. Zikic et al. BIB018 tackled linear registration by using FastPD to perform inference in a graph where each node encoded a different parameter of the transformation, while the edges relating them modeled their interactions. TRW-S or sequential tree-reweighted message passing is also based on an LP relaxation. The algorithm aims to solve the dual of the relaxation that provides a lower bound of the optimal MRF energy. The goal is to maximize the lower bound that is given by a convex combination of trees. Shekhovtsov et al. BIB005 used it to optimize their efficient decomposed MRF deformation model. Kwon et al. BIB011 used TRW-S to perform inference in a factor graph that models higher-order spatial smoothness constraints for image registration. Sotiras et al. used it to perform hybrid registration BIB019 . Lee et al. BIB020 used TRW-S to solve the optical flow estimation problem based on an adaptive convolution kernel prior.