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
2497387133 1487388912 2101309634 2147899407
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. 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. In the last few years, several new algorithms based on graph cuts have been developed to solve energy minimization problems in computer vision. Each of these techniques constructs a graph such that the minimum cut on the graph also minimizes the energy. Yet, because these graph constructions are complex and highly specific to a particular energy function, graph cuts have seen limited application to date. In this paper, we give a characterization of the energy functions that can be minimized by graph cuts. Our results are restricted to functions of binary variables. However, our work generalizes many previous constructions and is easily applicable to vision problems that involve large numbers of labels, such as stereo, motion, image restoration, and scene reconstruction. We give a precise characterization of what energy functions can be minimized using graph cuts, among the energy functions that can be written as a sum of terms containing three or fewer binary variables. We also provide a general-purpose construction to minimize such an energy function. Finally, we give a necessary condition for any energy function of binary variables to be minimized by graph cuts. Researchers who are considering the use of graph cuts to optimize a particular energy function can use our results to determine if this is possible and then follow our construction to create the appropriate graph. A software implementation is freely available. Graph cut is a popular technique for interactive image segmentation. However, it has certain shortcomings. In particular, graph cut has problems with segmenting thin elongated objects due to the ldquoshrinking biasrdquo. To overcome this problem, we propose to impose an additional connectivity prior, which is a very natural assumption about objects. We formulate several versions of the connectivity constraint and show that the corresponding optimization problems are all NP-hard. For some of these versions we propose two optimization algorithms: (i) a practical heuristic technique which we call DijkstraGC, and (ii) a slow method based on problem decomposition which provides a lower bound on the problem. We use the second technique to verify that for some practical examples DijkstraGC is able to find the global minimum.