Elsevier

Medical Image Analysis

Volume 12, Issue 6, December 2008, Pages 731-741
Medical Image Analysis

Dense image registration through MRFs and efficient linear programming

https://doi.org/10.1016/j.media.2008.03.006Get rights and content

Abstract

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.

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 f:Ω=[1,N]×[1,M]R 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 isxΩg(x)=hf(T(x)),where T(x) 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 lpL to each node pG, 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)

  • Christensen, G.E., 1994. Deformable shape models for anatomy. PhD thesis. Washington...
  • S. Geman et al.

    Stochastic relaxation gibbs distributions and the bayesian restoration of images

    IEEE Transactions on Pattern Analysis and Machine Intelligence

    (1984)
  • Gerig, G., Jomier, M., Chakos, M., 2001. Valmet: a new validation tool for assessing and improving 3d object...
  • Glocker, B., Komodakis, N., Paragios, N., Glaser, C., Tziritas, G., Navab, N., 2007. Primal/dual linear programming and...
  • Glocker, B., Komodakis, N., Paragios, N., Tziritas, G., Navab, N., 2007. Inter and intra-modal deformable registration:...
  • Glocker, B., Paragios, N., Komodakis, N., Tziritas, G., Navab, N., 2008. Optical flow estimation with uncertainties...
  • P. Hellier et al.

    Coupling dense and landmark-based approaches for nonrigid registration

    IEEE Transactions on Medical Imaging

    (2003)
  • G. Hermosillo et al.

    Variational methods for multimodal image matching

    International Journal Computer Vision

    (2002)
  • Cited by (385)

    • Graph matching and registration

      2023, Medical Image Analysis
    View all citing articles on Scopus

    This work is partially supported by Siemens Medical Solutions, Germany and from the French ANR-Blanc grant SURF (2005–2008).

    View full text