Article Contents
Article Contents

# Alpha divergences based mass transport models for image matching problems

• Registration methods could be roughly divided into two groups: area-based methods and feature-based methods. In the literature, the Monge-Kantorovich (MK) mass transport problem has been applied to image registration as an area-based method. In this paper, we propose to use Monge-Kantorovich (MK) mass transport model as a feature-based method. This novel image matching model is a coupling of the MK problem with the well-known alpha divergence from the probability theory. The optimal matching scheme is the one which minimizes the weighted alpha divergence between two images. A primal-dual approach is employed to analyze the existence and uniqueness/non-uniqueness of the optimal matching scheme. A block coordinate method, analogous to the Sinkhorn matrix balancing method, can be used to compute the optimal matching scheme. We also derive a distance function for image morphing. Similar to elastic distances proposed by Younes, the geodesic under this distance function has an explicit expression.
Mathematics Subject Classification: Primary: 49K99, 65K99.

 Citation:

•  [1] R. D. Anderson and V. L. Klee, Jr., Convex functions and upper semi-continuous collecti ons, Duke Math. J., 19 (1952), 349-357.doi: 10.1215/S0012-7094-52-01935-2. [2] Jean-David Benamou and Yann Brenier, A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem, Numer. Math., 84 (2000), 375-393. [3] D. P. Bertsekas, "Nonlinear Programming," Athena Scientific, 2003. [4] P. J. Besl and N. D. McKay, A method for registration of 3-d shapes, IEEE Trans. Pattern Anal. Mach. Intell., 14 (1992), 239-256.doi: 10.1109/34.121791. [5] F. L. Bookstein, Principal warps: Thin-plate splines and the decomposition of deformations, IEEE Trans. Pattern Anal. Mach. Intell., 11 (1989), 567-585.doi: 10.1109/34.24792. [6] Alberto Borobia and Rafael Cantó, Matrix scaling: A geometric proof of Sinkhorn's theorem, Linear Algebra Appl., 268 (1998), 1-8. [7] Yann Brenier, Polar factorization and monotone rearrangement of vector-valued functions, Comm. Pure Appl. Math., 44 (1991), 375-417. [8] P. Chen, A novel kernel correlation model with the corrrespondence estimation, JMIV, 39 (2011), 100-120. [9] H. Chui and A. Rangarajan, A feature registration framework using mixture models, IEEE workshop on MMBIA, (2000), 190-197. [10] _____, A new algorithm for non-rigid point matching, CVIU, 89 (2003), 114-141. [11] I. L. Dryden and K. V. Mardia, "Statistical Shape Analysis," Wiley Series in Probability and Statistics: Probability and Statistics, John Wiley & Sons, Ltd., Chichester, 1998. [12] L. C. Evans and W. Gangbo, Differential equations methods for the Monge-Kantorovich mass transfer problem, Mem. Amer. Math. Soc., 137 (1999), viii+66 pp. [13] Lawrence C. Evans, Partial differential equations and Monge-Kantorovich mass transfer, Current developments in mathematics, 1997, (Cambridge, MA), Int. Press, Boston, MA, (1999), 65-126. [14] _____, "Partial Differential Equations," Second edition, Graduate Studies in Mathematics, 19, American Mathematical Society, Providence, RI, 2010. [15] Lawrence C. Evans and Ronald F. Gariepy, "Measure Theory and Fine Properties of Functions," Studies in Advanced Mathematics, CRC Press, Boca Raton, FL, 1992. [16] Olivier Faugeras and Gerardo Hermosillo, Well-posedness of two nonrigid multimodal image registration methods, SIAM J. Appl. Math., 64 (2004), 1550-1587. [17] Wilfrid Gangbo, An elementary proof of the polar factorization of vector-valued functions, Arch. Rational Mech. Anal., 128 (1994), 381-399. [18] A. L. Gibbs and F. E. Su, On choosing and bounding probability metrics, Intl. Stat. Rev., 7 (2002), 419-435. [19] J. Glaunes, A. Trouve and L. Younes, Diffeomorphic matching of distributions: A new approach for unlabelled point-sets and sub-manifolds matching, CVPR, 2 (2004), 712-718. [20] S. Granger and X. Pennec, Multi-scale EM-ICP: A fast and robust approach for surface registration, ECCV, 4 (2002), 418-432. [21] S. Haker, L. Zhu, A. Tannenbaum and S. Angenent, Optimal mass transport for registration and warping, International Journal of Computer Vision, 60 (2004), 225-240. [22] Roger A. Horn and Charles R. Johnson, "Matrix Analysis," Cambridge University Press, Cambridge, 1985. [23] B. Jian and B. C. Vemuri, A robust algorithm for point set registration using mixture of Gaussians, ICCV, 2 (2005), 1246-1251. [24] S. C. Joshi and M. I. Miller, Landmark matching via large deformation diffeomorphism, IEEE Image Proc., 9 (2000), 1357-1370. [25] Jürgen Jost and Xianqing Li-Jost, "Calculus of Variations," Cambridge Studies in Advanced Mathematics, 64, Cambridge University Press, Cambridge, 1998. [26] Thomas Kaijser, Computing the Kantorovich distance for images, J. Math. Imaging Vision, 9 (1998), 173-191. [27] L. V. Kantorovich, On the transfer of masses, Dokl. Akad. Nauk. SSSR, 37 (1942), 227-229. [28] M. Kass, A. Witkin and D. Terzopoulos, Snake: Active contour models, International Journal of Computer Vision, 1 (1988), 321-331.doi: 10.1007/BF00133570. [29] M. Leordeanu and M. Hebert, A spectral technique for correspondence problems using pairwise constraints, ICCV, (2005), 1482-1489. [30] B. Luo and E. R. Hancock, A unified framework for alignment and correspondence, Computer Vision and Image Understanding, 92 (2003), 26-55.doi: 10.1016/S1077-3142(03)00097-3. [31] B. Ma, R. Narayanan, H. Park, A. O. Hero, P. H. Bland and C. R. Meyer, Comparing pairwise and simultaneous joint registrations of decorrelating interval exams using entropic graphs, Information Processing in Medical Imaging, 4584 (2008), 270-282.doi: 10.1007/978-3-540-73273-0_23. [32] Robert J. McCann, Existence and uniqueness of monotone measure-preserving maps, Duke Math. J., 80 (1995), 309-323. [33] G. McNeil and S. Vijayakumar, A probabilistic approach to robust shape matching, IEEE ICIP, (2006), 937-940. [34] M. I. Miller and L. Younes, Group actions, homeomorphism, matching: A general framework, Int. J. Comput. Vis., 41 (2001), 61-84.doi: 10.1023/A:1011161132514. [35] O. Museyko, M. Stiglmayr, K. Klamroth and G. Leugering, On the application of the Monge-Kantorovich problem to image registration, SIAM J. Imaging Sci., 2 (2009), 1068-1097. [36] Yurii A. Neretin, On Jordan angles and the triangle inequality in Grassmann manifolds, Geom. Dedicata, 86 (2001), 81-92. [37] J. Rabin, J. Delon and Y. Gousseau, A statistical approach to the matching of local features, SIAM J. Imaging Sci., 2 (2009), 931-958. [38] Svetlozar T. Rachev, "Probability Metrics and the Stability of Stochastic Models," Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics, John Wiley & Sons, Ltd., Chichester, 1991. [39] A. Rényi, On measures of entropy and infromation, Proc. 4th Berkeley Symp. Math. Stat. and Prob., Vol. 1, Univ. California Press, Berkeley, Calif., (1961), 547-561. [40] R. Tyrrell Rockafellar, "Convex Analysis," Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. [41] Y. Rubner, C. Tomasi and L. J. Guibas, The earth mover's distance as a metric for image retrieval, Int. J. Comput. Vis., 40 (2000), 99-121.doi: 10.1023/A:1026543900054. [42] G. L. Scott and H. C. Longuet-Higgins, An algorithm for associating the features of two images, Proceedings of the Royal Society London: Biological Sciences, 244 (1991), 21-26. [43] T. Sebastian, P. Klein and B. Kimia, On aligning curves, IEEE Trans. Pattern Anal. Mach. Intell., 5 (2003), 116-125.doi: 10.1109/TPAMI.2003.1159951. [44] I. K. Sethi and R. Jain, Finding trajectories of feature points in a monocular image sequence, IEEE Trans. Pattern Anal. Mach. Intell., 9 (1987), 56-73.doi: 10.1109/TPAMI.1987.4767872. [45] Richard Sinkhorn, A relationship between arbitrary positive matrices and doubly stochastic matrices, Ann. Math. Statist., 35 (1964), 876-879.doi: 10.1214/aoms/1177703591. [46] D. W. Thompson, "On Growth and Form," Cambridge University Press, Cambridge, 1917. [47] A. Trouve, Diffeomorphism groups and pattern matching in image analysis, Int. J. Comput. Vis., 28 (1998), 213-221.doi: 10.1023/A:1008001603737. [48] Y. Tsin and T. Kanade, A correlation-based approach to robust point set registration, ECCV, 3 (2004), 558-569. [49] Zhuowen Tu, Songfeng Zheng and Alan Yuille, Shape matching and registration by data-driven EM, Computer Vision and Image Understanding, 109 (2008), 290-304. [50] S. Ullman, "The Interpretation of Visual Motion," MIT Press, Cambridge, MA, 1979. [51] Grace Wahba, "Spline Models for Observational Data," CBMS-NSF Regional Conference Series in Applied Mathematics, 59, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. [52] F. Wang, B. C. Vemuri, A. Rangarajan and S. J. Eisenschenk, Simultaneous nonrigid registration of multiple point sets and atlas construction, IEEE PAMI, 30 (2008), 2011-2022. [53] J. Warga, Minimizing certain convex functions, J. Soc. Indust. Appl. Math., 11 (1963), 588-593.doi: 10.1137/0111043. [54] W. M. Wells, Statistical approaches to feature-based object recognition, International Journal of Computer Vision, 22 (1997), 63-98.doi: 10.1023/A:1007923522710. [55] M. Werman, S. Peleg and A. Rosenfeld, A distance metric for multi-dimensional histograms, Comp. Vis. Graphics Image Proc., 32 (1985), 328-336.doi: 10.1016/0734-189X(85)90055-6. [56] Laurent Younes, Computable elastic distances between shapes, SIAM J. Appl. Math., 58 (1998), 565-586 (electronic). [57] Laurent Younes, Peter W. Michor, Jayant Shah and David Mumford, A metric on shape space with explicit geodesics, Atti Accad. Naz. Lincei Cl. Sci. Fis. Mat. Natur. Rend. Lincei (9) Mat. Appl., 19 (2008), 25-57. [58] Z. Zhang, Iterative point matching for registration of free-form curves and surfaces, International Journal of Computer Vision, 13 (1994), 119-152. [59] L. Zhu, Y. Yang, S. Haker and A. Tannenbaum, An image morphing technique based on optimal mass preserving mapping, IEEE Trans. Image Processing, 16 (2007), 1481-1495. [60] C. L. Zitnick and T. Kanade, A cooperative algorithm for stereo matching and occlusion detection, IEEE Trans. Pattern Anal. Mach. Intell., 22 (2000), 675-684.doi: 10.1109/34.865184. [61] B. Zitova and J. Flusser, Image registration methods: A survey, Image and Vis. Compu., 21 (2003), 977-1000.doi: 10.1016/S0262-8856(03)00137-9.