Abstract
Deformable image registration is a field that has received considerable attention in the medical image analysis community. As a consequence, there is an important body of works that aims to tackle deformable registration. In this chapter we review one class of these techniques that use discrete optimization, and more specifically Markov Random Field models. We begin the chapter by explaining how one can formulate the deformable registration problem as a minimal cost graph problem where the nodes of the graph corresponds to the deformation grid, the graph connectivity encodes regularization constraints, and the labels correspond to 3D displacements. We then explain the use of discrete models in intensity-based volumetric registration. In the third section, we detail the use of Gabor-based attribute vectors in the context of discrete deformable registration, demonstrating the versatility of the graph-based models. In the last section of the chapter, the case of landmark-based registration is discussed. We first explain the discrete graphical model behind establishing landmark correspondences, and then continue to show how one can integrate it with the intensity-based model towards creating enhanced models that combine the best of both worlds.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
Fast-PD is available at http://cvc-komodakis.centrale-ponts.fr/.
- 2.
- 3.
DRAMMS is available at http://www.nitrc.org/projects/dramms/.
References
Amit, Y.: A nonlinear variational problem for image matching. SIAM Journal on Scientific Computing 15(1), 207–224 (1994)
Arsigny, V., Pennec, X., Ayache, N.: Polyrigid and polyaffine transformations: A novel geometrical tool to deal with non-rigid deformations – Application to the registration of histological slices. Medical Image Analysis 9(6), 507–523 (2005)
Ashburner, J.: A fast diffeomorphic image registration algorithm. NeuroImage 38(1), 95–113 (2007)
Ashburner, J., Friston, K.J.: Nonlinear spatial normalization using basis functions. Human Brain Mapping 7(4), 254–266 (1999)
Avants, B.B., Epstein, C.L., Grossman, M., Gee, J.C.: Symmetric diffeomorphic image registration with cross-correlation: evaluating automated labeling of elderly and neurodegenerative brain. Medical image analysis 12(1), 26–41 (2008)
Baumann, B.C., Teo, B.K., Pohl, K., Ou, Y., Doshi, J., Alonso-Basanta, M., Christodouleas, J., Davatzikos, C., Kao, G., Dorsey, J.: Multiparametric processing of serial mri during radiation therapy of brain tumors:finishing with flair?. International Journal of Radiation Oncology* Biology* Physics 81(2), S794 (2011)
Bay, H., Ess, A., Tuytelaars, T., Van Gool, L.: Speeded-up robust features (surf). Computer vision and image understanding 110(3), 346–359 (2008)
Beg, M.F., Miller, M.I., Trouvé, A., Younes, L.: Computing large deformation metric mappings via geodesic flows of diffeomorphisms. International Journal of Computer Vision 61(2), 139–157 (2005)
Betke, M., Hong, H., Thomas, D., Prince, C., Ko, J.P.: Landmark detection in the chest and registration of lung surfaces with an application to nodule registration. Medical Image Analysis 7(3), 265–281 (2003)
Bookstein, F.L.: Principal warps: Thin-plate splines and the decomposition of deformations. IEEE Transactions on Pattern Analysis and Machine Intelligence 11(6), 567–585 (1989)
Cachier, P., Mangin, J.F., Pennec, X., Rivière, D., Papadopoulos-Orfanos, D., Régis, J., Ayache, N.: Multisubject non-rigid registration of brain MRI using intensity and geometric features. In: International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 734–742 (2001)
Can, A., Stewart, C.V., Roysam, B., Tanenbaum, H.L.: A feature-based, robust, hierarchical algorithm for registering pairs of images of the curved human retina. Pattern Analysis and Machine Intelligence, IEEE Transactions on 24(3), 347–364 (2002)
Christensen, G.E., Johnson, H.J.: Consistent image registration. IEEE transactions on medical imaging 20(7), 568–82 (2001)
Christensen, G.E., Rabbitt, R.D., Miller, M.I.: Deformable templates using large deformation kinematics. IEEE Transactions on Image Processing 5(10), 1435–1447 (1996)
Chui, H., Rangarajan, A.: A new point matching algorithm for non-rigid registration. Computer Vision and Image Understanding 89(2-3), 114–141 (2003)
Chung, A.C., Wells III, W.M., Norbash, A., Grimson, W.E.L.: Multi-modal image registration by minimizing Kullback-Leibler distance. In: International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 525–532 (2002)
Da, X., Toledo, J.B., Zee, J., Wolk, D.A., Xie, S.X., Ou, Y., Shacklett, A., Parmpi, P., Shaw, L., Trojanowski, J.Q., et al.: Integration and relative value of biomarkers for prediction of mci to ad progression: Spatial patterns of brain atrophy, cognitive scores, apoe genotype and csf biomarkers. NeuroImage: Clinical 4, 164–173 (2014)
D’Agostino, E., Maes, F., Vandermeulen, D., Suetens, P.: A viscous fluid model for multimodal non-rigid image registration using mutual information. Medical Image Analysis 7(4), 565–575 (2003)
Davatzikos, C.: Spatial transformation and registration of brain images using elastically deformable models. Computer Vision and Image Understanding 66(2), 207–222 (1997)
Droske, M., Rumpf, M.: A variational approach to nonrigid morphological image registration. SIAM Journal on Applied Mathematics 64(2), 668–687 (2004)
Erus, G., Battapady, H., Satterthwaite, T.D., Hakonarson, H., Gur, R.E., Davatzikos, C., Gur, R.C.: Imaging patterns of brain development and their relationship to cognition. Cerebral Cortex p. bht425 (2014)
Fischer, B., Modersitzki, J.: Fast diffusion registration. AMS Contemporary Mathematics, Inverse Problems, Image Analysis, and Medical Imaging 313, 117–127 (2002)
Glaunès, J., Trouvé, A., Younes, L.: Diffeomorphic matching of distributions: A new approach for unlabelled point-sets and sub-manifolds matching. In: International Conference on Computer Vision and Pattern Recognition, pp. 712–718 (2004)
Glocker, B., Komodakis, N., Tziritas, G., Navab, N., Paragios, N.: Dense image registration through MRFs and efficient linear programming. Medical Image Analysis 12(6), 731–741 (2008)
Glocker, B., Sotiras, A., Komodakis, N., Paragios, N.: Deformable medical image registration: setting the state of the art with discrete methods. Annual Review of Biomedical Engineering 13, 219–244 (2011)
Hajnal, J.V., Hill, D.L., Hawkes, D.J. (eds.): Medical image registration. CRC Press, Boca Raton, FL (2001)
Hartkens, T., Hill, D.L.G., Castellano-Smith, A., Hawkes, D.J., Maurer, C.R., Martin, A., Hall, W., Liu, H., Truwit, C.: Using points and surfaces to improve voxel-based non-rigid registration. In: International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 565–572 (2002)
Heinrich, M.P., Jenkinson, M., Bhushan, M., Matin, T., Gleeson, F.V., Brady, S.M., Schnabel, J.A.: Mind: Modality independent neighbourhood descriptor for multi-modal deformable registration. Medical Image Analysis 16(7), 1423–1435 (2012)
Hellier, P., Barillot, C.: Coupling dense and landmark-based approaches for nonrigid registration. IEEE Transactions on Medical Imaging 22(2), 217–227 (2003)
Holden, M.: A review of geometric transformations for nonrigid body registration. IEEE Transactions on Medical Imaging 27(1), 111–128 (2008)
Hsieh, J.W., Liao, H.Y.M., Fan, K.C., Ko, M.T., Hung, Y.P.: Image registration using a new edge-based approach. Computer Vision and Image Understanding 67(2), 112–130 (1997)
Huang, X., Paragios, N., Metaxas, D.N.: Shape registration in implicit spaces using information theory and free form deformations. IEEE Transactions on Pattern Analysis and Machine Intelligence 28(8), 1303–1318 (2006)
Ingalhalikar, M., Parker, D., Ghanbari, Y., Smith, A., Hua, K., Mori, S., Abel, T., Davatzikos, C., Verma, R.: Connectome and maturation profiles of the developing mouse brain using diffusion tensor imaging. Cerebral Cortex p. bhu068 (2014)
Jian, B., Vemuri, B., Marroquin, J.: Robust nonrigid multimodal image registration using local frequency maps. In: Information Processing in Medical Imaging (IPMI), pp. 504–515 (2005)
Johnson, H.J., Christensen, G.E.: Consistent landmark and intensity-based image registration. IEEE Transactions on Medical Imaging 21(5), 450–461 (2002)
Kadir, T., Brady, M.: Saliency, scale and image description. International Journal of Computer Vision 45(2), 83–105 (2001)
Ke, Y., Sukthankar, R.: Pca-sift: A more distinctive representation for local image descriptors. In: Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on, vol. 2, pp. II–506. IEEE (2004)
Klein, A., Andersson, J., Ardekani, B.A., Ashburner, J., Avants, B., Chiang, M.C., Christensen, G.E., Collins, D.L., Gee, J., Hellier, P., et al.: Evaluation of 14 nonlinear deformation algorithms applied to human brain mri registration. Neuroimage 46(3), 786–802 (2009)
Komodakis, N., Tziritas, G.: Approximate labeling via graph cuts based on linear programming. IEEE transactions on pattern analysis and machine intelligence 29(8), 1436–53 (2007)
Komodakis, N., Tziritas, G., Paragios, N.: Performance vs computational efficiency for optimizing single and dynamic MRFs: Setting the state of the art with primal-dual strategies. Computer Vision and Image Understanding 112(1), 14–29 (2008)
Koutsouleris, N., Davatzikos, C., Borgwardt, S., Gaser, C., Bottlender, R., Frodl, T., Falkai, P., Riecher-Rössler, A., Möller, H.J., Reiser, M., et al.: Accelerated brain aging in schizophrenia and beyond: a neuroanatomical marker of psychiatric disorders. Schizophrenia bulletin p. sbt142 (2013)
Kwon, D., Lee, K., Yun, I., Lee, S.: Nonrigid image registration using dynamic higher-order mrf model. In: European Conference on Computer Vision, pp. 373–386 (2008)
Leordeanu, M., Hebert, M.: A spectral technique for correspondence problems using pairwise constraints. In: International Conference on Computer Vision, pp. 1482–1489 (2005)
Li, G., Guo, L., Liu, T.: Deformation invariant attribute vector for deformable registration of longitudinal brain MR images. Computerized Medical Imaging and Graphics 33(5), 273–297 (2009)
Li, H., Manjunath, B., Mitra, S.K.: A contour-based approach to multisensor image registration. Image Processing, IEEE Transactions on 4(3), 320–334 (1995)
Lindeberg, T.: Detecting salient blob-like image structures and their scales with a scale-space primal sketch: a method for focus-of-attention. International Journal of Computer Vision 11(3), 283–318 (1993)
Ling, H., Jacobs, D.: Deformation invariant image matching. In: The Tenth International Conference in Computer Vision (ICCV). Beijing, China. (2005)
Liu, J., Vemuri, B.C., Marroquin, J.L.: Local frequency representations for robust multimodal image registration. IEEE Transactions on Medical Imaging 21(5), 462–469 (2002)
Liu, J., Vemuri, B.C., Marroquin, J.L.: Local frequency representations for robust multimodal image registration. IEEE Transactions on Medical Imaging 21(5), 462–469 (2002)
Lowe, D.G.: Object recognition from local scale-invariant features. In: Computer vision, 1999. The proceedings of the seventh IEEE international conference on, vol. 2, pp. 1150–1157. Ieee (1999)
Lowe, D.G.: Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision 60(2), 91–110 (2004)
Maes, F., Collignon, A., Vandermeulen, D., Marchal, G., Suetens, P.: Multimodality image registration by maximization of mutual information. IEEE Transactions on Medical Imaging 16(2), 187–198 (1997)
Maintz, J.A., Viergever, M.A.: A survey of medical image registration. Medical Image Analysis 2(1), 1–36 (1998)
Modersitzki, J.: FAIR: Flexible algorithms for image registration. SIAM, Philadelphia (2009)
Narayanan, R., Fessler, J.A., Park, H., Meyer, C.R.: Diffeomorphic nonlinear transformations: a local parametric approach for image registration. In: International Conference on Information Processing in Medical Imaging, pp. 174–185 (2005)
Noblet, V., Heinrich, C., Heitz, F., Armspach, J.P.: Symmetric nonrigid image registration: application to average brain templates construction. In: Medical Image Computing and Computer-Assisted Intervention: MICCAI ’08, no. Pt 2 in LNCS, pp. 897–904 (2008)
Ou, Y., Akbari, H., Bilello, M., Da, X., Davatzikos, C.: Comparative evaluation of registration algorithms for different brain databases with varying difficulty: Results and Insights. IEEE Transactions on Medical Imaging (2014). doi:10.1109/TMI.2014.2330355
Ou, Y., Besbes, A., Bilello, M., Mansour, M., Davatzikos, C., Paragios, N.: Detecting mutually-salient landmark pairs with MRF regularization. In: International Symposium on Biomedical Imaging, pp. 400–403 (2010)
Ou, Y., Weinstein, S.P., Conant, E.F., Englander, S., Da, X., Gaonkar, B., Hsiao, M., Rosen, M., DeMichele, A., Davatzikos, C., Kontos, D.: Deformable registration for quantifying longitudinal tumor changes during neoadjuvant chemotherapy: In Press. Magnetic Resonance in Medicine (2014)
Ou, Y., Reynolds, N., Gollub, R., Pienaar, R., Wang, Y., Wang, T., Sack, D., Andriole, K., Pieper, S., Herrick, C., Murphy, S., Grant, P., Zollei, L.: Developmental brain adc atlas creation from clinical images. In: Organization for Human Brain Mapping (OHBM) (2014)
Ou, Y., Shen, D., Feldman, M., Tomaszewski, J., Davatzikos, C.: Non-rigid registration between histological and MR images of the prostate: A joint segmentation and registration framework. In: Computer Vision and Pattern Recognition workshop, 2009. CVPR 2009. IEEE Conference on, pp. 125–132 (2009)
Ou, Y., Sotiras, A., Paragios, N., Davatzikos, C.: DRAMMS: Deformable registration via attribute matching and mutual-saliency weighting. Medical Image Analysis 15(4), 622–639 (2011)
Perona, P., Malik, J.: Scale-space and edge detection using anisotropic diffusion. Pattern Analysis and Machine Intelligence, IEEE Transactions on 12(7), 629–639 (1990)
Postelnicu, G., Zollei, L., Fischl, B.: Combined volumetric and surface registration. IEEE Transactions on Medical Imaging 28(4), 508–522 (2009)
Roche, A., Malandain, G., Pennec, X., Ayache, N.: The correlation ratio as a new similarity measure for multimodal image registration. In: International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 1115–1124 (1998)
Rohr, K.: On 3d differential operators for detecting point landmarks. Image and Vision Computing 15(3), 219–233 (1997)
Rohr, K., Stiehl, H.S., Sprengel, R., Buzug, T.M., Weese, J., Kuhn, M.: Landmark-based elastic registration using approximating thin-plate splines. IEEE Transactions on Medical Imaging 20(6), 526–534 (2001)
Rueckert, D., Aljabar, P., Heckemann, R.A., Hajnal, J.V., Hammers, A.: Diffeomorphic registration using B-splines. In: International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 702–709 (2006)
Rueckert, D., Sonoda, L.I., Hayes, C., Hill, D.L.G., Leach, M.O., Hawkes, D.J.: Nonrigid registration using free-form deformations: application to breast MR images. IEEE Transactions on Medical Imaging 18(8), 712–721 (1999)
Satterthwaite, T.D., Elliott, M.A., Ruparel, K., Loughead, J., Prabhakaran, K., Calkins, M.E., Hopson, R., Jackson, C., Keefe, J., Riley, M., et al.: Neuroimaging of the philadelphia neurodevelopmental cohort. NeuroImage 86, 544–553 (2014)
Sederberg, T.W., Parry, S.R.: Free-form deformation of solid geometric models. ACM Siggraph Computer Graphics 20(4), 151–160 (1986)
Serpa, M.H., Ou, Y., Schaufelberger, M.S., Doshi, J., Ferreira, L.K., Machado-Vieira, R., Menezes, P.R., Scazufca, M., Davatzikos, C., Busatto, G.F., et al.: Neuroanatomical classification in a population-based sample of psychotic major depression and bipolar i disorder with 1 year of diagnostic stability. BioMed Research International 2014 (2014)
Shen, D.: Image registration by local histogram matching. Pattern Recognition 40(4), 1166–1172 (1997)
Shen, D., Davatzikos, C.: HAMMER: hierarchical attribute matching mechanism for elastic registration. IEEE transactions on Medical Imaging 21(11), 1421–39 (2002)
Sotiras, A., Davatzikos, C., Paragios, N.: Deformable medical image registration: a survey. IEEE Transactions on Medical Imaging 32(7), 1153–90 (2013)
Sotiras, A., Ou, Y., Glocker, B., Davatzikos, C., Paragios, N.: Simultaneous geometric–iconic registration. In: International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 676–683 (2010)
Sotiras, A., Paragios, N.: Discrete symmetric image registration. In: IEEE International Symposium on Biomedical Imaging (ISBI), pp. 342–345 (2012)
Szeliski, R.: Image alignment and stitching: A tutorial. Foundations and Trends®; in Computer Graphics and Vision 2(1), 1–104 (2006)
Tagare, H., Groisser, D., Skrinjar, O.: Symmetric non-rigid registration: A geometric theory and some numerical techniques. Journal of Mathematical Imaging and Vision 34(1), 61–88 (2009)
Thirion, J.P.: Image matching as a diffusion process: an analogy with Maxwell’s demons. Medical Image Analysis 2(3), 243–260 (1998)
Toews, M., Wells III, W.M.: Efficient and robust model-to-image alignment using 3d scale-invariant features. Medical image analysis 17(3), 271–282 (2013)
Torresani, L., Kolmogorov, V., Rother, C.: Feature correspondence via graph matching: Models and global optimization. In: European Conference on Computer Vision, pp. 596–609 (2008)
Tsin, Y., Kanade, T.: A correlation-based approach to robust point set registration. In: European Conference on Computer Vision, pp. 558–569 (2004)
Vercauteren, T., Pennec, X., Perchant, A., Ayache, N.: Symmetric log-domain diffeomorphic Registration: a demons-based approach. In: Medical Image Computing and Computer-Assisted Intervention: MICCAI’08, no. Pt 1 in LNCS, pp. 754–61 (2008)
Vercauteren, T., Pennec, X., Perchant, A., Ayache, N.: Diffeomorphic Demons: Efficient non-parametric image registration. NeuroImage 45(1, Supplement 1), S61–S72 (2009)
Viola, P., Wells III, W.M.: Alignment by maximization of mutual information. International Journal of Computer Vision 24(2), 137–154 (1997)
Wu, Y.T., Kanade, T., Li, C.C., Cohn, J.: Image registration using wavelet-based motion model. International Journal of Computer Vision 38(2), 129–152 (2000)
Yang, J., Shen, D., Davatzikos, C.: Diffusion tensor image registration using tensor geometry and orientation features. In: Medical Image Computing and Computer-Assisted Intervention (MICCAI), pp. 905–913 (2008)
Yi, Z., Zhiguo, C., Yang, X.: Multi-spectral remote image registration based on sift. Electronics Letters 44(2), 107–108 (2008)
Zanetti, M.V., Schaufelberger, M.S., Doshi, J., Ou, Y., Ferreira, L.K., Menezes, P.R., Scazufca, M., Davatzikos, C., Busatto, G.F.: Neuroanatomical pattern classification in a population-based sample of first-episode schizophrenia. Progress in Neuro-Psychopharmacology and Biological Psychiatry 43, 116–125 (2013)
Zhan, Y., Ou, Y., Feldman, M., Tomaszeweski, J., Davatzikos, C., Shen, D.: Registering histologic and mr images of prostate for image-based cancer detection. Academic Radiology 14(11), 1367–1381 (2007)
ZHANG, R.j., Zhang, J.q., Yang, C.: Image registration approach based on surf [j]. Infrared and Laser Engineering 1, 041 (2009)
Zitova, B., Flusser, J.: Image registration methods: a survey. Image and Vision Computing 21(11), 977–1000 (2003)
Acknowledgements
We would like to acknowledge Dr. Ben Glocker, from Imperial College London, whose work formed the basis of the subsequent works that are presented here.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer Science+Business Media New York
About this chapter
Cite this chapter
Sotiras, A., Ou, Y., Paragios, N., Davatzikos, C. (2015). Graph-based Deformable Image Registration. In: Paragios, N., Duncan, J., Ayache, N. (eds) Handbook of Biomedical Imaging. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-09749-7_18
Download citation
DOI: https://doi.org/10.1007/978-0-387-09749-7_18
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-09748-0
Online ISBN: 978-0-387-09749-7
eBook Packages: Computer ScienceComputer Science (R0)