Objective: Deformable image registration is a fundamental problem in medical image analysis, with applications such as longitudinal studies, population modeling, and atlas based image segmentation. Registration is often phrased as an optimization problem, i.e., finding a deformation field that is optimal according to a given objective function. Discrete, combinatorial, optimization techniques have successfully been employed to solve the resulting optimization problem. Specifically, optimization based on @math -expansion with minimal graph cuts has been proposed as a powerful tool for image registration. The high computational cost of the graph-cut based optimization approach, however, limits the utility of this approach for registration of large volume images. Methods: Here, we propose to accelerate graph-cut based deformable registration by dividing the image into overlapping sub-regions and restricting the @math -expansion moves to a single sub-region at a time. Results: We demonstrate empirically that this approach can achieve a large reduction in computation time -- from days to minutes -- with only a small penalty in terms of solution quality. Conclusion: The reduction in computation time provided by the proposed method makes graph cut based deformable registration viable for large volume images. Significance: Graph cut based image registration has previously been shown to produce excellent results, but the high computational cost has hindered the adoption of the method for registration of large medical volume images. Our proposed method lifts this restriction, requiring only a small fraction of the computational cost to produce results of comparable quality.
As shown by @cite_16 , minimal graph cuts are a powerful tool for solving dicrete optimization problems arising in image analysis and computer vision. The use of minimal graph cuts for deformable image registration was, to our knowledge, first proposed by @cite_11 . The use of graph cuts in this context has been shown to produce excellent results, but the high computational cost associated with this method has limited its use in medical imaging. In recent years, the topic has since then been revisited by several authors. Heinrich @cite_10 , formulate a similar optimization problem, but then prune the graph to a tree on which the optimal labeling (to an approximation of the original problem) can be found by efficient belief propagation. @cite_0 @cite_7 proposed to accelerate graph-cut based image registration by partitioning the image into supervoxels to yield a sparse graph-based image representation. This reduces computation time, but the result is restricted by the assumption that the displacement field is constant within each supervoxel. @cite_12 @cite_1 consider optimization problems similar to that presented here, but use a linear programming solver to find optimal solutions.
@cite_7 @cite_1 @cite_0 @cite_16 @cite_10 @cite_12 @cite_11
2133774049 2497387133 2143516773 2016974693 2118961645 1487388912
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 im... This work revisits the concept of graph cuts as an efficient optimization technique in image registration. Previously, due to the computational burden involved, the use of graph cuts in this context has been mainly limited to 2D applications. Here we show how combining graph cuts with supervoxels, resulting in a sparse, yet meaningful graph-based image representation, can overcome previous limitations. Additionally, we show that a relaxed graph representation of the image allows for 'sliding' motion modeling and provides anatomically plausible estimation of the deformations. This is achieved by using image-guided filtering of the estimated sparse deformation field. We evaluate our method on a publicly available CT lung data set and show that our new approach compares very favourably with state-of-the-art in continuous and discrete image registration. Many tasks in computer vision involve assigning a label (such as disparity) to every pixel. A common constraint is that the labels should vary smoothly almost everywhere while preserving sharp discontinuities that may exist, e.g., at object boundaries. These tasks are naturally stated in terms of energy minimization. The authors consider a wide class of energies with various smoothness constraints. Global minimization of these energy functions is NP-hard even in the simplest discontinuity-preserving case. Therefore, our focus is on efficient approximation algorithms. We present two algorithms based on graph cuts that efficiently find a local minimum with respect to two types of large moves, namely expansion moves and swap moves. These moves can simultaneously change the labels of arbitrarily large sets of pixels. In contrast, many standard algorithms (including simulated annealing) use small moves where only one pixel changes its label at a time. Our expansion algorithm finds a labeling within a known factor of the global minimum, while our swap algorithm handles more general energy functions. Both of these algorithms allow important cases of discontinuity preserving energies. We experimentally demonstrate the effectiveness of our approach for image restoration, stereo and motion. On real data with ground truth, we achieve 98 percent accuracy. Deformable image registration is an important tool in medical image analysis. In the case of lung computed tomography (CT) registration there are three major challenges: large motion of small features, sliding motions between organs, and changing image contrast due to compression. Recently, Markov random field (MRF)-based discrete optimization strategies have been proposed to overcome problems involved with continuous optimization for registration, in particular its susceptibility to local minima. However, to date the simplifications made to obtain tractable computational complexity reduced the registration accuracy. We address these challenges and preserve the potentially higher quality of discrete approaches with three novel contributions. First, we use an image-derived minimum spanning tree as a simplified graph structure, which copes well with the complex sliding motion and allows us to find the global optimum very efficiently. Second, a stochastic sampling approach for the similarity cost between images is introduced within a symmetric, diffeomorphic B-spline transformation model with diffusion regularization. The complexity is reduced by orders of magnitude and enables the minimization of much larger label spaces. In addition to the geometric transform labels, hyper-labels are introduced, which represent local intensity variations in this task, and allow for the direct estimation of lung ventilation. We validate the improvements in accuracy and performance on exhale-inhale CT volume pairs using a large number of expert landmarks. 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. 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.