Alpha divergences  based mass transport models for image matching problems

Pengwen Chen; Changfeng Gui

doi:10.3934/ipi.2011.5.551

Article Contents

2011, Volume 5, Issue 3: 551-590. Doi: 10.3934/ipi.2011.5.551

This issue Previous Article Direct electrical impedance tomography for nonsmooth conductivities Next Article Anisotropic total variation regularized $L^1$ approximation and denoising/deblurring of 2D bar codes

Alpha divergences based mass transport models for image matching problems

Pengwen Chen^1, and
Changfeng Gui^2,

1.
Department of Mathematics, National Taiwan University
2.
School of Mathematics, Hunan University, Changsha 410082

Received: April 30, 2009

Revised: May 31, 2010

Published: July 2011

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 49K99, 65K99.

Citation:

Related Papers

Cited by

References

[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.