Dense image registration through MRFs and efficient linear programming☆
Introduction
Medical image analysis (Duncan and Ayache, 2000, Paragios et al., 2009) is an established domain in computational, mathematical and biological sciences. Recent advances on the acquisition side have made possible the visualization of human tissues as well as physiological and pathological indices related to them either occasionally or periodically. The ability to compare or fuse information across subjects with origins of different modalities is a critical and necessary component of computer aided diagnosis. The term used often to express this need is registration.
The registration problem often involves three aspects: (i) the transformation model, (ii) a similarity criterion and (iii) an optimization strategy.
Registration can be either global or local. Parametric models are often employed to address global registration with a small number of degrees of freedom, such as rigid or similarity. These models refer to a good compromise between performance and computational complexity. The registration problem in such a context is well posed since the number of variables to be determined is over-constrained from the number of observations. Dense image registration aims to go further and seeks individual correspondences between observations. The main goal is to determine relationships that locally express the correlation of the observations either for the same subject (acquisitions of different modalities or acquisitions of the same organ in time). Local alignment or dense/deformable registration is the term often considered to describe this task.
Deformable registration is one of the most challenging problems in medical imaging. The problem consists of recovering a local transformation that aligns two signals that have in general an unknown relationship both in the spatial domain and in the intensity domain. Several methods exist in the literature where specific measures are designed to account for this relationship and to optimize the transformation that brings these two signals together.
Local image alignment is often performed according to geometric or photometric criteria. Landmark-based methods (Hellier and Barillot, 2003, Rohr et al., 2003) are a classic example of geometric-driven registration. In such a setting, a number of anatomical key points (Pennec et al., 2000)/structures (segmented values) are identified both in the source and in the target image, and a transformation that aims to minimize the Euclidean distance between these structures is to be recovered. The main limitation of these methods is related to the selection and extraction of landmarks, while their main strength is the simplicity of the optimization process.
Iconic registration methods (Cachier et al., 2003) seek for “visual” correspondences between the source and the target image. Such a problem is tractable when one seeks registration for images from the same modality due to an explicit photometric correspondence of the image intensities. Sum of squared differences, sum of absolute differences, cross correlation (Hajnal et al., 2001) or distances on subspaces that involve both appearance and geometry (intensities, curvature and higher order image moments) (Davatzikos et al., 1996) have been considered. On the other hand, it becomes more challenging when seeking transformations between different modalities with a non-linear or only statistical relation of intensities (Hermosillo et al., 2002). The measures that have often been used were normalized mutual information (Maes et al., 1997), Kullback-Liebler divergence (Zollei et al., 2005) and correlation ratio (Roche et al., 1998) to define similarity1 between different modalities.
Once the similarity measure has been defined the next task consists of recovering the parameters that optimize the designed cost function. Parameters can be either searched or estimated. In the first case techniques like exhaustive search can be employed which are time consuming. On the other hand, one can use known optimization techniques, gradient-free or gradient-based to determine the optimal set of parameters starting from an initial guess (Klein et al., 2007). These methods require an important customization from one application to another since a correlation exists between the modalities/problem and the selection of the similarity measure. Furthermore, the optimization is often sub-optimal due the non-convexity of the designed cost functions. In particular when considering complex similarity functions defined on the continuous space, then the numerical approximation of the gradient in the discrete domain (image/volume plane) is very challenging leading to erroneous registration results.
The aim of our approach is to overcome both limitations present in all registration methods: dependency on the similarity measure selectionand on the initial conditions in a reasonable computation time.
In this article, we propose a novel technique that can be used either for inter or intramodal image registration. Towards satisfying the smoothness of the deformation field and reducing the dimensionality of the problem, we represent deformation through free form deformations (Sederberg and Parry, 1986). Our method reformulates registration as a Markov random field (MRF) optimization where a set of labels is associated with a set of deformations. Then we seek to attribute a label to each control point such that once the corresponding deformation has been applied, the similarity measure between the source and the target is optimal for all voxels. The optimization procedure is independent from the graph construction, and therefore any similarity measure can be used.
The remainder of this paper is organized as follows: In Section 2, we introduce the proposed registration framework, while in Section 3 we discuss the optimization aspects. Implementation details are given in Section 4 and experimental validation are part of Section 5. Section 6 concludes our paper.
Section snippets
Deformable registration
In order to introduce the concept of our approach (Glocker et al., 2007), we consider (without the loss of generality) the 2D image domain. Let us consider a source and a target image g. In general, these images are related with a non-linear transformation as well as a non-linear relation between intensities, that iswhere is the transformation and h is a non-linear operator explaining the changes of appearance between them. The most common way to
MRF optimization based on linear programming
For optimizing the resulting MRF, we seek to assign a label to each node , so that the MRF energy in (13) is minimized.2 To this end, a recently proposed method, called Fast-PD, will be used (Komodakis et al., 2007). This is an optimization technique, which builds upon principles drawn from the duality theory of linear programming in order to efficiently
Implementation details and parameter setting
In order to prove the concept of our framework, we implemented a deformable registration application in C++. We follow the widely used approach of multi-resolution registration in a course-to-fine manner. The control grid is successively refined by decreasing the grid point spacing by a factor of two while at the same time we use a Gaussian pyramid for the image data. In most applications three levels are sufficient. As mentioned before the deformation grid is reset after each optimization
Experiments on known and unknown deformations
Our framework currently contains a range of well-known similarity measures, namely the sum of absolute differences (SAD), the sum of squared differences (SSD), the normalized cross correlation (NCC) (Hajnal et al., 2001), the normalized mutual information (NMI) (Maes et al., 1997, Viola and Wells, 1997), the correlation ratio (CR) (Roche et al., 1998), and a measure involving an intensity-based and a geometric-based term which combines the sum of absolute differences and image gradient inner
Discussion
In this paper, we have proposed a novel framework for deformable image registration that bridges the gap between continuous deformations and optimal discrete optimization. Our method reformulates registration using an MRF definition, and recovers the optimal solution to the designed objective function through efficient linear programming. Towards capturing important deformations, we propose an incremental estimation of the deformation component. These objectives are met through a discrete
References (39)
- et al.
Iconic feature based nonrigid registration: the pasha algorithm
Computer Vision and Image Understanding
(2003) - et al.
Injectivity conditions of 2d and 3d uniform cubic b-spline functions
Graphical Models
(2000) - et al.
Spline-based elastic image registration: integration of landmark errors and orientation attributes
Computer Vision and Image Understanding
(2003) On the statistical analysis of dirty pictures (with discussion)
Journal of the Royal Statistical Society Series B
(1986)- et al.
Handbook of mathematical models in computer vision
Graph Cuts in Vision and Graphics: Theories and Applications
(2005) - et al.
The theory and practice of bayesian image labeling
International Journal of Computer Vision
(1990) - et al.
Image registration based on boundary mapping
IEEE Transactions on Medical Imaging
(1996) - et al.
Medical image analysis: progress over two decades and the challenges ahead
IEEE Transactions on Pattern Analysis and Machine Intelligence
(2000) Measurement of Image Velocity
(1992)- et al.
Flows in Networks
(1962)
Stochastic relaxation gibbs distributions and the bayesian restoration of images
IEEE Transactions on Pattern Analysis and Machine Intelligence
Coupling dense and landmark-based approaches for nonrigid registration
IEEE Transactions on Medical Imaging
Variational methods for multimodal image matching
International Journal Computer Vision
Cited by (385)
Hybrid unsupervised paradigm based deformable image fusion for 4D CT lung image modality
2024, Information FusionSMILE: Siamese Multi-scale Interactive-representation LEarning for Hierarchical Diffeomorphic Deformable image registration
2024, Computerized Medical Imaging and GraphicsR2Net: Efficient and flexible diffeomorphic image registration using Lipschitz continuous residual networks
2023, Medical Image AnalysisSymmetric pyramid network for medical image inverse consistent diffeomorphic registration
2023, Computerized Medical Imaging and GraphicsA segmentation-informed deep learning framework to register dynamic two-dimensional magnetic resonance images of the vocal tract during speech
2023, Biomedical Signal Processing and ControlGraph matching and registration
2023, Medical Image Analysis
- ☆
This work is partially supported by Siemens Medical Solutions, Germany and from the French ANR-Blanc grant SURF (2005–2008).