American Institute of Mathematical Sciences

Advanced
April  2018, 12(2): 401-432. doi: 10.3934/ipi.2018018

Numerical method for image registration model based on optimal mass transport

Yangang Chen 1, and  Justin W. L. Wan 2,

1. 

Department of Applied Mathematics, University of Waterloo, 200 University Avenue West, Waterloo, ON, N2L 3G1, Canada
2. 

David R. Cheriton School of Computer Science, University of Waterloo, 200 University Avenue West, Waterloo, ON, N2L 3G1, Canada

Received  May 2017 Revised  September 2017 Published  February 2018

Fund Project: The second author is supported by Natural Sciences and Engineering Research Council of Canada (NSERC).

This paper proposes a numerical method for solving a non-rigid image registration model based on optimal mass transport. The main contribution of this paper is to address two issues. One is that we impose a proper periodic boundary condition, such that when the reference and template images are related by translation, or a combination of translation and non-rigid deformation, the numerical solution gives the underlying transformation. The other is that we design a numerical scheme that converges to the optimal transformation between the two images. As an additional benefit, our approach can decompose the transformation into translation and non-rigid deformation. Our numerical results show that the numerical solutions yield good-quality transformations for non-rigid image registration problems.

Keywords: Image registration, mass transport, Monge-Ampère equation, periodic boundary condition, viscosity solution, Hamilton-Jacobi-Bellman (HJB) equation, monotonicity, finite difference.
Mathematics Subject Classification: Primary: 65N06, 65N22; Secondary: 35J96.
Citation: Yangang Chen, Justin W. L. Wan. Numerical method for image registration model based on optimal mass transport. Inverse Problems & Imaging, 2018, 12 (2) : 401-432. doi: 10.3934/ipi.2018018
References:
[1]

G. Barles and P. E. Souganidis, Convergence of approximation schemes for fully nonlinear second order equations, Asymptotic Anal., 4 (1991), 271-283.   Google Scholar

[2]

J. -D. Benamou, Y. Brenier and K. Guittet, The Monge-Kantorovitch mass transfer and its computational fluid mechanics formulation, Internat. J. Numer. Methods Fluids, 40 (2002), 21-30, ICFD Conference on Numerical Methods for Fluid Dynamics (Oxford, 2001). doi: 10.1002/fld.264.  Google Scholar

[3]

J.-D. Benamou, B. D. Froese and A. M. Oberman, Two numerical methods for the elliptic Monge-Ampère equation, M2AN Math. Model. Numer. Anal., 44 (2010), 737-758.  doi: 10.1051/m2an/2010017.  Google Scholar

[4]

K. Böhmer, On finite element methods for fully nonlinear elliptic equations of second order, SIAM J. Numer. Anal., 46 (2008), 1212-1249.  doi: 10.1137/040621740.  Google Scholar

[5]

S. C. Brenner, T. Gudi, M. Neilan and L.-y. Sung, $C^0$ penalty methods for the fully nonlinear Monge-Ampère equation, Math. Comp., 80 (2011), 1979-1995.  doi: 10.1090/S0025-5718-2011-02487-7.  Google Scholar

[6]

C. Broit, Optimal registration of deformed images. Google Scholar

[7]

L. G. Brown, A survey of image registration techniques, ACM Computing Surveys (CSUR), 24 (1992), 325-376.  doi: 10.1145/146370.146374.  Google Scholar

[8]

P. A. Browne, C. J. Budd, C. Piccolo and M. Cullen, Fast three dimensional r-adaptive mesh redistribution, J. Comput. Phys., 275 (2014), 174-196.  doi: 10.1016/j.jcp.2014.06.009.  Google Scholar

[9]

C. J. Budd and J. F. Williams, Moving mesh generation using the parabolic Monge-Ampère equation, SIAM J. Sci. Comput., 31 (2009), 3438-3465.  doi: 10.1137/080716773.  Google Scholar

[10]

L. A. Caffarelli, Boundary regularity of maps with convex potentials. II, Ann. of Math.(2), 144 (1996), 453-496.  doi: 10.2307/2118564.  Google Scholar

[11]

K. Y. Chan and J. W. Wan, Reconstruction of missing cells by a killing energy minimizing nonrigid image registration, in Engineering in Medicine and Biology Society (EMBC), 2013 35th Annual International Conference of the IEEE, IEEE, 2013,3000-3003. doi: 10.1109/EMBC.2013.6610171.  Google Scholar

[12]

R. Chartrand, B. Wohlberg, K. R. Vixie and E. M. Bollt, A gradient descent solution to the Monge-{K}antorovich problem, Appl. Math. Sci. (Ruse), 3 (2009), 1071-1080.   Google Scholar

[13]

Y. Chen and J. W. Wan, Monotone mixed narrow/wide stencil finite difference scheme for Monge-Ampère equation, arXiv preprint, arXiv: 1608.00644. Google Scholar

[14]

G. E. Christensen, Deformable Shape Models for Anatomy, PhD thesis, Washington University Saint Louis, Mississippi, 1994.  Google Scholar

[15]

M. G. Crandall, H. Ishii and P.-L. Lions, User's guide to viscosity solutions of second order partial differential equations, Bull. Amer. Math. Soc. (N.S.), 27 (1992), 1-67.  doi: 10.1090/S0273-0979-1992-00266-5.  Google Scholar

[16]

M. G. Crandall and P.-L. Lions, Viscosity solutions of Hamilton-Jacobi equations, Trans. Amer. Math. Soc., 277 (1983), 1-42.  doi: 10.1090/S0002-9947-1983-0690039-8.  Google Scholar

[17]

E. J. Dean and R. Glowinski, Numerical methods for fully nonlinear elliptic equations of the Monge-Ampère type, Comput. Methods Appl. Mech. Engrg., 195 (2006), 1344-1386.  doi: 10.1016/j.cma.2005.05.023.  Google Scholar

[18]

P. Dupuis, U. Grenander and M. I. Miller, Variational problems on flows of diffeomorphisms for image matching, Quarterly of Applied Mathematics, 56 (1998), 587-600.  doi: 10.1090/qam/1632326.  Google Scholar

[19]

X. Feng, R. Glowinski and M. Neilan, Recent developments in numerical methods for fully nonlinear second order partial differential equations, SIAM Rev., 55 (2013), 205-267.  doi: 10.1137/110825960.  Google Scholar

[20]

X. Feng and M. Neilan, Vanishing moment method and moment solutions for fully nonlinear second order partial differential equations, J. Sci. Comput., 38 (2009), 74-98.  doi: 10.1007/s10915-008-9221-9.  Google Scholar

[21]

B. Fischer and J. Modersitzki, Fast inversion of matrices arising in image processing, Numerical Algorithms, 22 (1999), 1-11.  doi: 10.1023/A:1019194421221.  Google Scholar

[22]

P. A. Forsyth and G. Labahn, Numerical methods for controlled Hamilton-Jacobi-Bellman PDEs in finance, Journal of Computational Finance, 11 (2007), 1pp. doi: 10.21314/JCF.2007.163.  Google Scholar

[23]

B. D. Froese, A numerical method for the elliptic Monge-Ampère equation with transport boundary conditions, SIAM J. Sci. Comput., 34 (2012), A1432-A1459.  doi: 10.1137/110822372.  Google Scholar

[24]

B. D. Froese and A. M. Oberman, Convergent finite difference solvers for viscosity solutions of the elliptic Monge-Ampère equation in dimensions two and higher, SIAM J. Numer. Anal., 49 (2011), 1692-1714.  doi: 10.1137/100803092.  Google Scholar

[25]

S. K. Godunov, A difference method for numerical calculation of discontinuous solutions of the equations of hydrodynamics, Mat. Sb. (N.S.), 47 (1959), 271-306.   Google Scholar

[26]

A. A. Goshtasby, 2-D and 3-D Image Registration: For Medical, Remote Sensing, and Industrial Applications, John Wiley & Sons, 2005. Google Scholar

[27]

S. Haker and A. Tannenbaum, Optimal mass transport and image registration, in Variational and Level Set Methods in Computer Vision, 2001. Proceedings. IEEE Workshop on, IEEE, 2001, 29-36. doi: 10.1109/VLSM.2001.938878.  Google Scholar

[28]

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.  doi: 10.1023/B:VISI.0000036836.66311.97.  Google Scholar

[29]

D. L. Hill, P. G. Batchelor, M. Holden and D. J. Hawkes, Medical image registration, Physics in Medicine and Biology, 46 (2001), R1. doi: 10.1088/0031-9155/46/3/201.  Google Scholar

[30]

M. Irani and S. Peleg, Improving resolution by image registration, CVGIP: Graphical Models and Image Processing, 53 (1991), 231-239.  doi: 10.1016/1049-9652(91)90045-L.  Google Scholar

[31]

M. Knott and C. S. Smith, On the optimal mapping of distributions, Journal of Optimization Theory and Applications, 43 (1984), 39-49.  doi: 10.1007/BF00934745.  Google Scholar

[32]

N. V. Krylov, The control of the solution of a stochastic integral equation, Teor. Verojatnost. i Primenen., 17 (1972), 111-128.   Google Scholar

[33]

K. Levenberg, A method for the solution of certain non-linear problems in least squares, Quart. Appl. Math., 2 (1944), 164-168.  doi: 10.1090/qam/10666.  Google Scholar

[34]

P. -L. Lions, Hamilton-Jacobi-Bellman equations and the optimal control of stochastic systems, in Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Warsaw, 1983), PWN, Warsaw, 1984,1403-1417.  Google Scholar

[35]

J. A. Maintz and M. A. Viergever, A survey of medical image registration, Medical Image Analysis, 2 (1998), 1-36.  doi: 10.1016/S1361-8415(01)80026-8.  Google Scholar

[36]

D. W. Marquardt, An algorithm for least-squares estimation of nonlinear parameters, J. Soc. Indust. Appl. Math., 11 (1963), 431-441.  doi: 10.1137/0111030.  Google Scholar

[37]

J. Modersitzki, Numerical Methods for Image Registration, Numerical Mathematics and Scientific Computation, Oxford University Press, New York, 2004, Oxford Science Publications.  Google Scholar

[38]

J. Modersitzki, FAIR: Flexible Algorithms for Image Registration, vol. 6 of Fundamentals of Algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2009. doi: 10.1137/1.9780898718843.  Google Scholar

[39]

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.  doi: 10.1137/080721522.  Google Scholar

[40]

A. M. Oberman, Wide stencil finite difference schemes for the elliptic Monge-Ampère equation and functions of the eigenvalues of the Hessian, Discrete Contin. Dyn. Syst. Ser. B, 10 (2008), 221-238.  doi: 10.3934/dcdsb.2008.10.221.  Google Scholar

[41]

V. I. Oliker and L. D. Prussner, On the numerical solution of the equation $(\partial^ 2z/\partial x^ 2)(\partial^ 2z/\partial y^ 2)-((\partial^ 2z/\partial x\partial y))^ 2 = f$ and its discretizations. Ⅰ, Numer. Math., 54 (1988), 271-293.  doi: 10.1007/BF01396762.  Google Scholar

[42]

S. Osher and C.-W. Shu, High-order essentially nonoscillatory schemes for Hamilton-Jacobi equations, SIAM J. Numer. Anal., 28 (1991), 907-922.  doi: 10.1137/0728049.  Google Scholar

[43]

K. Rohr, Landmark-based Image Analysis: Using Geometric and Intensity Models, vol. 21, Springer Science & Business Media, 2001. doi: 10.1007/978-94-015-9787-6.  Google Scholar

[44]

L.-P. Saumier, M. Agueh and B. Khouider, An efficient numerical algorithm for the $L^ 2$ optimal transport problem with periodic densities, IMA J. Appl. Math., 80 (2015), 135-157.  doi: 10.1093/imamat/hxt032.  Google Scholar

[45]

A. Sotiras, C. Davatzikos and N. Paragios, Deformable medical image registration: A survey, IEEE Transactions on Medical Imaging, 32 (2013), 1153-1190.  doi: 10.1109/TMI.2013.2265603.  Google Scholar

[46]

P. Thevenaz, U. E. Ruttimann and M. Unser, A pyramid approach to subpixel registration based on intensity, IEEE Transactions on Image Processing, 7 (1998), 27-41.  doi: 10.1109/83.650848.  Google Scholar

[47]

J.-P. Thirion, Image matching as a diffusion process: An analogy with maxwell's demons, Medical Image Analysis, 2 (1998), 243-260.  doi: 10.1016/S1361-8415(98)80022-4.  Google Scholar

[48]

E. F. Toro, Riemann Solvers and Numerical Methods for Fluid Dynamics: A Practical Introduction, Third edition. Springer-Verlag, Berlin, 2009.  Google Scholar

[49]

U. Trottenberg, C. W. Oosterlee and A. Schüller, Multigrid, Academic Press, Inc., San Diego, CA, 2001, With contributions by A. Brandt, P. Oswald and K. Stüben.  Google Scholar

[50]

A. Trouvé, Diffeomorphisms groups and pattern matching in image analysis, International Journal of Computer Vision, 28 (1998), 213-221.   Google Scholar

[51]

P. Viola and W. M. Wells Ⅲ, Alignment by maximization of mutual information, International Journal of Computer Vision, 24 (1997), 137-154.   Google Scholar

show all references

References:
[1]

G. Barles and P. E. Souganidis, Convergence of approximation schemes for fully nonlinear second order equations, Asymptotic Anal., 4 (1991), 271-283.   Google Scholar

[2]

J. -D. Benamou, Y. Brenier and K. Guittet, The Monge-Kantorovitch mass transfer and its computational fluid mechanics formulation, Internat. J. Numer. Methods Fluids, 40 (2002), 21-30, ICFD Conference on Numerical Methods for Fluid Dynamics (Oxford, 2001). doi: 10.1002/fld.264.  Google Scholar

[3]

J.-D. Benamou, B. D. Froese and A. M. Oberman, Two numerical methods for the elliptic Monge-Ampère equation, M2AN Math. Model. Numer. Anal., 44 (2010), 737-758.  doi: 10.1051/m2an/2010017.  Google Scholar

[4]

K. Böhmer, On finite element methods for fully nonlinear elliptic equations of second order, SIAM J. Numer. Anal., 46 (2008), 1212-1249.  doi: 10.1137/040621740.  Google Scholar

[5]

S. C. Brenner, T. Gudi, M. Neilan and L.-y. Sung, $C^0$ penalty methods for the fully nonlinear Monge-Ampère equation, Math. Comp., 80 (2011), 1979-1995.  doi: 10.1090/S0025-5718-2011-02487-7.  Google Scholar

[6]

C. Broit, Optimal registration of deformed images. Google Scholar

[7]

L. G. Brown, A survey of image registration techniques, ACM Computing Surveys (CSUR), 24 (1992), 325-376.  doi: 10.1145/146370.146374.  Google Scholar

[8]

P. A. Browne, C. J. Budd, C. Piccolo and M. Cullen, Fast three dimensional r-adaptive mesh redistribution, J. Comput. Phys., 275 (2014), 174-196.  doi: 10.1016/j.jcp.2014.06.009.  Google Scholar

[9]

C. J. Budd and J. F. Williams, Moving mesh generation using the parabolic Monge-Ampère equation, SIAM J. Sci. Comput., 31 (2009), 3438-3465.  doi: 10.1137/080716773.  Google Scholar

[10]

L. A. Caffarelli, Boundary regularity of maps with convex potentials. II, Ann. of Math.(2), 144 (1996), 453-496.  doi: 10.2307/2118564.  Google Scholar

[11]

K. Y. Chan and J. W. Wan, Reconstruction of missing cells by a killing energy minimizing nonrigid image registration, in Engineering in Medicine and Biology Society (EMBC), 2013 35th Annual International Conference of the IEEE, IEEE, 2013,3000-3003. doi: 10.1109/EMBC.2013.6610171.  Google Scholar

[12]

R. Chartrand, B. Wohlberg, K. R. Vixie and E. M. Bollt, A gradient descent solution to the Monge-{K}antorovich problem, Appl. Math. Sci. (Ruse), 3 (2009), 1071-1080.   Google Scholar

[13]

Y. Chen and J. W. Wan, Monotone mixed narrow/wide stencil finite difference scheme for Monge-Ampère equation, arXiv preprint, arXiv: 1608.00644. Google Scholar

[14]

G. E. Christensen, Deformable Shape Models for Anatomy, PhD thesis, Washington University Saint Louis, Mississippi, 1994.  Google Scholar

[15]

M. G. Crandall, H. Ishii and P.-L. Lions, User's guide to viscosity solutions of second order partial differential equations, Bull. Amer. Math. Soc. (N.S.), 27 (1992), 1-67.  doi: 10.1090/S0273-0979-1992-00266-5.  Google Scholar

[16]

M. G. Crandall and P.-L. Lions, Viscosity solutions of Hamilton-Jacobi equations, Trans. Amer. Math. Soc., 277 (1983), 1-42.  doi: 10.1090/S0002-9947-1983-0690039-8.  Google Scholar

[17]

E. J. Dean and R. Glowinski, Numerical methods for fully nonlinear elliptic equations of the Monge-Ampère type, Comput. Methods Appl. Mech. Engrg., 195 (2006), 1344-1386.  doi: 10.1016/j.cma.2005.05.023.  Google Scholar

[18]

P. Dupuis, U. Grenander and M. I. Miller, Variational problems on flows of diffeomorphisms for image matching, Quarterly of Applied Mathematics, 56 (1998), 587-600.  doi: 10.1090/qam/1632326.  Google Scholar

[19]

X. Feng, R. Glowinski and M. Neilan, Recent developments in numerical methods for fully nonlinear second order partial differential equations, SIAM Rev., 55 (2013), 205-267.  doi: 10.1137/110825960.  Google Scholar

[20]

X. Feng and M. Neilan, Vanishing moment method and moment solutions for fully nonlinear second order partial differential equations, J. Sci. Comput., 38 (2009), 74-98.  doi: 10.1007/s10915-008-9221-9.  Google Scholar

[21]

B. Fischer and J. Modersitzki, Fast inversion of matrices arising in image processing, Numerical Algorithms, 22 (1999), 1-11.  doi: 10.1023/A:1019194421221.  Google Scholar

[22]

P. A. Forsyth and G. Labahn, Numerical methods for controlled Hamilton-Jacobi-Bellman PDEs in finance, Journal of Computational Finance, 11 (2007), 1pp. doi: 10.21314/JCF.2007.163.  Google Scholar

[23]

B. D. Froese, A numerical method for the elliptic Monge-Ampère equation with transport boundary conditions, SIAM J. Sci. Comput., 34 (2012), A1432-A1459.  doi: 10.1137/110822372.  Google Scholar

[24]

B. D. Froese and A. M. Oberman, Convergent finite difference solvers for viscosity solutions of the elliptic Monge-Ampère equation in dimensions two and higher, SIAM J. Numer. Anal., 49 (2011), 1692-1714.  doi: 10.1137/100803092.  Google Scholar

[25]

S. K. Godunov, A difference method for numerical calculation of discontinuous solutions of the equations of hydrodynamics, Mat. Sb. (N.S.), 47 (1959), 271-306.   Google Scholar

[26]

A. A. Goshtasby, 2-D and 3-D Image Registration: For Medical, Remote Sensing, and Industrial Applications, John Wiley & Sons, 2005. Google Scholar

[27]

S. Haker and A. Tannenbaum, Optimal mass transport and image registration, in Variational and Level Set Methods in Computer Vision, 2001. Proceedings. IEEE Workshop on, IEEE, 2001, 29-36. doi: 10.1109/VLSM.2001.938878.  Google Scholar

[28]

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.  doi: 10.1023/B:VISI.0000036836.66311.97.  Google Scholar

[29]

D. L. Hill, P. G. Batchelor, M. Holden and D. J. Hawkes, Medical image registration, Physics in Medicine and Biology, 46 (2001), R1. doi: 10.1088/0031-9155/46/3/201.  Google Scholar

[30]

M. Irani and S. Peleg, Improving resolution by image registration, CVGIP: Graphical Models and Image Processing, 53 (1991), 231-239.  doi: 10.1016/1049-9652(91)90045-L.  Google Scholar

[31]

M. Knott and C. S. Smith, On the optimal mapping of distributions, Journal of Optimization Theory and Applications, 43 (1984), 39-49.  doi: 10.1007/BF00934745.  Google Scholar

[32]

N. V. Krylov, The control of the solution of a stochastic integral equation, Teor. Verojatnost. i Primenen., 17 (1972), 111-128.   Google Scholar

[33]

K. Levenberg, A method for the solution of certain non-linear problems in least squares, Quart. Appl. Math., 2 (1944), 164-168.  doi: 10.1090/qam/10666.  Google Scholar

[34]

P. -L. Lions, Hamilton-Jacobi-Bellman equations and the optimal control of stochastic systems, in Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Warsaw, 1983), PWN, Warsaw, 1984,1403-1417.  Google Scholar

[35]

J. A. Maintz and M. A. Viergever, A survey of medical image registration, Medical Image Analysis, 2 (1998), 1-36.  doi: 10.1016/S1361-8415(01)80026-8.  Google Scholar

[36]

D. W. Marquardt, An algorithm for least-squares estimation of nonlinear parameters, J. Soc. Indust. Appl. Math., 11 (1963), 431-441.  doi: 10.1137/0111030.  Google Scholar

[37]

J. Modersitzki, Numerical Methods for Image Registration, Numerical Mathematics and Scientific Computation, Oxford University Press, New York, 2004, Oxford Science Publications.  Google Scholar

[38]

J. Modersitzki, FAIR: Flexible Algorithms for Image Registration, vol. 6 of Fundamentals of Algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2009. doi: 10.1137/1.9780898718843.  Google Scholar

[39]

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.  doi: 10.1137/080721522.  Google Scholar

[40]

A. M. Oberman, Wide stencil finite difference schemes for the elliptic Monge-Ampère equation and functions of the eigenvalues of the Hessian, Discrete Contin. Dyn. Syst. Ser. B, 10 (2008), 221-238.  doi: 10.3934/dcdsb.2008.10.221.  Google Scholar

[41]

V. I. Oliker and L. D. Prussner, On the numerical solution of the equation $(\partial^ 2z/\partial x^ 2)(\partial^ 2z/\partial y^ 2)-((\partial^ 2z/\partial x\partial y))^ 2 = f$ and its discretizations. Ⅰ, Numer. Math., 54 (1988), 271-293.  doi: 10.1007/BF01396762.  Google Scholar

[42]

S. Osher and C.-W. Shu, High-order essentially nonoscillatory schemes for Hamilton-Jacobi equations, SIAM J. Numer. Anal., 28 (1991), 907-922.  doi: 10.1137/0728049.  Google Scholar

[43]

K. Rohr, Landmark-based Image Analysis: Using Geometric and Intensity Models, vol. 21, Springer Science & Business Media, 2001. doi: 10.1007/978-94-015-9787-6.  Google Scholar

[44]

L.-P. Saumier, M. Agueh and B. Khouider, An efficient numerical algorithm for the $L^ 2$ optimal transport problem with periodic densities, IMA J. Appl. Math., 80 (2015), 135-157.  doi: 10.1093/imamat/hxt032.  Google Scholar

[45]

A. Sotiras, C. Davatzikos and N. Paragios, Deformable medical image registration: A survey, IEEE Transactions on Medical Imaging, 32 (2013), 1153-1190.  doi: 10.1109/TMI.2013.2265603.  Google Scholar

[46]

P. Thevenaz, U. E. Ruttimann and M. Unser, A pyramid approach to subpixel registration based on intensity, IEEE Transactions on Image Processing, 7 (1998), 27-41.  doi: 10.1109/83.650848.  Google Scholar

[47]

J.-P. Thirion, Image matching as a diffusion process: An analogy with maxwell's demons, Medical Image Analysis, 2 (1998), 243-260.  doi: 10.1016/S1361-8415(98)80022-4.  Google Scholar

[48]

E. F. Toro, Riemann Solvers and Numerical Methods for Fluid Dynamics: A Practical Introduction, Third edition. Springer-Verlag, Berlin, 2009.  Google Scholar

[49]

U. Trottenberg, C. W. Oosterlee and A. Schüller, Multigrid, Academic Press, Inc., San Diego, CA, 2001, With contributions by A. Brandt, P. Oswald and K. Stüben.  Google Scholar

[50]

A. Trouvé, Diffeomorphisms groups and pattern matching in image analysis, International Journal of Computer Vision, 28 (1998), 213-221.   Google Scholar

[51]

P. Viola and W. M. Wells Ⅲ, Alignment by maximization of mutual information, International Journal of Computer Vision, 24 (1997), 137-154.   Google Scholar

Figure 1.  An example of image registration using the Neumann boundary condition. (a) Template image $T$. (b) Reference image $R$. (c) Underlying transformation between $T$ and $R$, which is a pure translation. (d) Transformation given by the Neumann boundary condition
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Standard 7-point stencil and wide stencil discretizations. (a) The stencil points of the discretization (15). (b) The stencil points of the discretization (17). (c) Wide stencil discretization: We apply a local coordinate rotation at the grid point $\mathbf{x}_{i, j}$ by the angle $\theta_{i, j}$. The grey dashed lines are the orthogonal axes $\{(\mathbf{e}_z)_{i, j}, (\mathbf{e}_w)_{i, j}\}$. The stencil length is $\sqrt{h}$ ($\sqrt{h}>h$). The grey stars are the stencil points $\mathbf{x}_{i, j}\pm\sqrt{h}(\mathbf{e}_z)_{i, j}$ and $\mathbf{x}_{i, j}\pm\sqrt{h}(\mathbf{e}_w)_{i, j}$. The unknowns at these stencil points are approximated by the bilinear interpolation from the neighboring points (black dots)
Figure Options

Download full-size image

Download as PowerPoint slide

3]. The figure shows that a square grid is severely deformed under $\phi$">Figure 3.  Optimal versus non-optimal transformations. (a) Constant images $R$ and $T$, where $\rho^T = \rho^R = 1$. (b) The optimal transformation $\phi^*$ obtained by our monotone numerical scheme. It is an identity mapping. The figure shows the deformed image of a square grid under $\phi^*$, which is the square grid itself. (c) The non-optimal transformation $\phi$ obtained by a non-monotone finite difference scheme in [3]. The figure shows that a square grid is severely deformed under $\phi$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Image registration using the periodic and Neumann boundary conditions, where $T$ and $R$ are related by translation. (a) Template image $T$. (b) Reference image $R$. (c) Transformed image $T_{\phi^*}$ under the periodic boundary condition. (d) Displacement of pixels from $T$ to $T_{\phi^*}$ under the periodic boundary condition, which is a pure translation. (e) A deformed grid obtained by applying the transformation $(\phi^*)^{-1}$ on a square grid. $(\phi^*)^{-1}$ is computed under the periodic boundary condition. The thick black lines show where the boundary of $\Omega = [0, 1]\times [0, 1]$ is moved to under $(\phi^*)^{-1}$. The color bar is the morphing magnitude $\mu$. The intensity of the color shows the degree of morphing effect under $(\phi^*)^{-1}$. (f) Displacement of pixels from $T$ to $T_{\phi^*}$ under the Neumann boundary condition. (g) A deformed grid obtained by applying the transformation $(\phi^*)^{-1}$ on a square grid. $(\phi^*)^{-1}$ is computed under the Neumann boundary condition
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  Image registration using the periodic and Neumann boundary conditions, where $T$ and $R$ are related by a combination of translation and dilation. (a) Template image $T$. (b) Reference image $R$. (c) Transformed image $T_{\phi^*}$ under the periodic boundary condition. (d1) Displacement of pixels from $T$ to $T_{\phi^*}$ under the periodic boundary condition. (d2) Decomposition of the displacement into a combination of translation component (green) and dilation component (red). (e) A deformed grid obtained by applying the transformation $(\phi^*)^{-1}$ on a square grid. $(\phi^*)^{-1}$ is computed under the periodic boundary condition. The thick black lines show where the boundary of $\Omega = [0, 1]\times [0, 1]$ is moved to under $(\phi^*)^{-1}$. The color bar is the morphing magnitude $\mu$. The intensity of the color shows the degree of morphing effect under $(\phi^*)^{-1}$. (f) Displacement of pixels from $T$ to $T_{\phi^*}$ under the Neumann boundary condition. (g) A deformed grid obtained by applying the transformation $(\phi^*)^{-1}$ on a square grid. $(\phi^*)^{-1}$ is computed under the Neumann boundary condition
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  Image registration using the periodic and Neumann boundary conditions, where $T$ and $R$ are related by a combination of translation and rotation. (a) Template image $T$. (b) Reference image $R$. (c) Transformed image $T_{\phi^*}$ under the periodic boundary condition. (d1) Displacement of pixels from $T$ to $T_{\phi^*}$ under the periodic boundary condition. (d2) Decomposition of the displacement into a combination of translation component (green) and local rotation component (red). (e) A deformed grid obtained by applying the transformation $(\phi^*)^{-1}$ on a square grid. $(\phi^*)^{-1}$ is computed under the periodic boundary condition. The thick black lines show where the boundary of $\Omega = [0, 1]\times [0, 1]$ is moved to under $(\phi^*)^{-1}$. The color bar is the morphing magnitude $\mu$. The intensity of the color shows the degree of morphing effect under $(\phi^*)^{-1}$. (f) Displacement of pixels from $T$ to $T_{\phi^*}$ under the Neumann boundary condition. (g) A deformed grid obtained by applying the transformation $(\phi^*)^{-1}$ on a square grid. $(\phi^*)^{-1}$ is computed under the Neumann boundary condition
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  Mass transport registration under periodic boundary condition. (a) Template image $T$. (b) Reference image $R$. (c) Transformed image $T_{\phi^*}$. (d) Difference between transformed image $T_{\phi^*}$ and $R$. (e) Pre-specified underlying transformation between $T$ and $R$. (f) Transformation given by the numerical scheme, which is a good approximation to the pre-specified underlying transformation in (e). (g) A deformed grid obtained by applying the transformation $(\phi^*)^{-1}$ on a square grid
Figure Options

Download full-size image

Download as PowerPoint slide

38]. (a) Transformed image $T_\phi$. (b) Difference between transformed image $T_\phi$ and $R$. (c) Transformation given by the empirical approach, consisting of a rigid pre-registration (green arrows) and a non-rigid elastic deformation (red arrows). (d) A deformed grid obtained by applying the transformation $\phi^{-1}$ on a square grid">Figure 8.  Empirical two-step registration, where $T$ and $R$ are the same as Figure 7(a)-(b). The registration is implemented by FAIR package [38]. (a) Transformed image $T_\phi$. (b) Difference between transformed image $T_\phi$ and $R$. (c) Transformation given by the empirical approach, consisting of a rigid pre-registration (green arrows) and a non-rigid elastic deformation (red arrows). (d) A deformed grid obtained by applying the transformation $\phi^{-1}$ on a square grid
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 9.  Medical image registration using the periodic boundary condition. (a) Template image $T$. (b) Reference image $R$. (c) Transformed image $T_{\phi^*}$. (d) Decomposition of the displacement into a combination of translation component (green) and non-rigid deformation component (red). (e) A deformed grid obtained by applying the transformation $(\phi^*)^{-1}$ on a square grid. $(\phi^*)^{-1}$ is computed under periodic boundary condition
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 10.  Medical image registration using the periodic boundary condition. (a) Template image $T$. (b) Reference image $R$. (c) Transformed image $T_{\phi^*}$. (d) Decomposition of the displacement into a combination of translation component (green) and non-rigid deformation component (red). (e) A deformed grid obtained by applying the transformation $(\phi^*)^{-1}$ on a square grid. $(\phi^*)^{-1}$ is computed under periodic boundary condition
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 11.  Image registration from Lena to Tiffany using the periodic boundary condition. (a) Template image $T$. (b) Reference image $R$. (c) Transformed image $T_{\phi^*}$. (d) Decomposition of the displacement into a combination of translation component (green) and non-rigid deformation component (red). (e) A deformed grid obtained by applying the transformation $(\phi^*)^{-1}$ on a square grid. $(\phi^*)^{-1}$ is computed under periodic boundary condition
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5(a) and Figure 5(b). (a) Difference between $T$ and $R$. (b) Difference between $T_{\phi}$ and $R$, where $T_{\phi}$ is a transformed image under rigid registration only (or, $T_{\phi}$ is a translation of $T$ to align with $R$). (c) Difference between unmorphed transformed image $T_{\phi^*}^{unmorph}$ and $R$ under the periodic boundary condition. (d) Difference between unmorphed transformed image $T_{\phi^*}^{unmorph}$ and $R$ under the Neumann boundary condition">Figure 12.  Image registration using the periodic and Neumann boundary conditions, where $T$ and $R$ are given in Figure 5(a) and Figure 5(b). (a) Difference between $T$ and $R$. (b) Difference between $T_{\phi}$ and $R$, where $T_{\phi}$ is a transformed image under rigid registration only (or, $T_{\phi}$ is a translation of $T$ to align with $R$). (c) Difference between unmorphed transformed image $T_{\phi^*}^{unmorph}$ and $R$ under the periodic boundary condition. (d) Difference between unmorphed transformed image $T_{\phi^*}^{unmorph}$ and $R$ under the Neumann boundary condition
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Modified Levenberg-Marquardt algorithm
1: Start with an initial guess $U^{(0)}=\frac{1}{2}(x^2+y^2)$.
2: Set $(c_1^{(-1)}, c_2^{(-1)})=(\infty, \infty)$, $\Pi \equiv [-\frac{1}{2}, \frac{1}{2}]\times[-\frac{1}{2}, \frac{1}{2}]$.
3: for $k = 0, 1, ...$ until convergence do
4:   if $(c_1^{(k-1)}, c_2^{(k-1)})\neq (0, 0)$ then
5:     $(c_1^{(k)}, c_2^{(k)}) = \underset{(c_1, c_2)\in \Pi} {\textrm{arg min}} \| R(U^{(k)} + c_1V_1 + c_2V_2) \|$.
6:     $U^{(k+\frac{1}{2})} = U^{(k)} + c_1^{(k)}V_1 + c_2^{(k)}V_2$.
7:   end if
8:   Compute $(a^{(k+\frac{1}{2})}, \theta^{(k+\frac{1}{2})})$ by (20).
9:   Compute $R^{(k+\frac{1}{2})}\equiv R(U^{(k+\frac{1}{2})})$ by (21).
10:   Compute $\mathbf{J}^{(k+\frac{1}{2})}\equiv\mathbf{J}[U^{(k+\frac{1}{2})}]$ by (22).
11:   Solve
$ \begin{array}{l} [\lambda I + (\mathbf{J}^{(k+\frac{1}{2})})^T \mathbf{J}^{(k+\frac{1}{2})}] E^{(k+\frac{1}{2})} \\ = -(\mathbf{J}^{(k+\frac{1}{2})})^T R^{(k+\frac{1}{2})}. \end{array} $
  for $E^{(k+\frac{1}{2})}$.
12:   $U^{(k+1)} = U^{(k+\frac{1}{2})} + E^{(k+\frac{1}{2})}$.
13: end for
Table Options

Download as excel

1: Start with an initial guess $U^{(0)}=\frac{1}{2}(x^2+y^2)$.
2: Set $(c_1^{(-1)}, c_2^{(-1)})=(\infty, \infty)$, $\Pi \equiv [-\frac{1}{2}, \frac{1}{2}]\times[-\frac{1}{2}, \frac{1}{2}]$.
3: for $k = 0, 1, ...$ until convergence do
4:   if $(c_1^{(k-1)}, c_2^{(k-1)})\neq (0, 0)$ then
5:     $(c_1^{(k)}, c_2^{(k)}) = \underset{(c_1, c_2)\in \Pi} {\textrm{arg min}} \| R(U^{(k)} + c_1V_1 + c_2V_2) \|$.
6:     $U^{(k+\frac{1}{2})} = U^{(k)} + c_1^{(k)}V_1 + c_2^{(k)}V_2$.
7:   end if
8:   Compute $(a^{(k+\frac{1}{2})}, \theta^{(k+\frac{1}{2})})$ by (20).
9:   Compute $R^{(k+\frac{1}{2})}\equiv R(U^{(k+\frac{1}{2})})$ by (21).
10:   Compute $\mathbf{J}^{(k+\frac{1}{2})}\equiv\mathbf{J}[U^{(k+\frac{1}{2})}]$ by (22).
11:   Solve
$ \begin{array}{l} [\lambda I + (\mathbf{J}^{(k+\frac{1}{2})})^T \mathbf{J}^{(k+\frac{1}{2})}] E^{(k+\frac{1}{2})} \\ = -(\mathbf{J}^{(k+\frac{1}{2})})^T R^{(k+\frac{1}{2})}. \end{array} $
  for $E^{(k+\frac{1}{2})}$.
12:   $U^{(k+1)} = U^{(k+\frac{1}{2})} + E^{(k+\frac{1}{2})}$.
13: end for
Table 2.  Sum of the squared differences before registration $\|\rho^T-\rho^R\|_{L_2(\Omega)}$, and after registration $\|\rho^{T_{\phi^*}}-\rho^R\|_{L_2(\Omega)}$. The values are computed for Examples 2-7 in Sections 6.3, 6.4 and 6.6. For each example, $\|\rho^R\|$ has been normalized to 1. The approach is the mass transport registration under the periodic boundary condition
ExamplesExample 2Example 3Example 4Example 5Example 6Example 7
$\|\rho^T-\rho^R\|_{L_2(\Omega)}$0.470.520.610.640.690.59
$\|\rho^{T_{\phi^*}}-\rho^R\|_{L_2(\Omega)}$0 $2\times 10^{-5}$ $1\times 10^{-3}$ $7\times 10^{-4}$ $9\times 10^{-4}$ $8\times 10^{-3}$
Table Options

Download as excel

ExamplesExample 2Example 3Example 4Example 5Example 6Example 7
$\|\rho^T-\rho^R\|_{L_2(\Omega)}$0.470.520.610.640.690.59
$\|\rho^{T_{\phi^*}}-\rho^R\|_{L_2(\Omega)}$0 $2\times 10^{-5}$ $1\times 10^{-3}$ $7\times 10^{-4}$ $9\times 10^{-4}$ $8\times 10^{-3}$
Table 3.  A summary of morphing effect at a point (or an infinitesimal element)
net flow of mass/pixelsarea change of a square elementchange of mass/pixels intensitymorphing magnitude $\mu$color of a square element
zeroinvarianceinvariance $\mu=0$white
inflowcompressedincrease $\mu>0$red
outflowexpandeddecrease $\mu < 0$blue
Table Options

Download as excel

net flow of mass/pixelsarea change of a square elementchange of mass/pixels intensitymorphing magnitude $\mu$color of a square element
zeroinvarianceinvariance $\mu=0$white
inflowcompressedincrease $\mu>0$red
outflowexpandeddecrease $\mu < 0$blue
Table 4.  The errors of the motion fields (26). The values are computed for Examples 2-5 in Sections 6.3 and 6.4. In each example, the mass transport registration under the periodic boundary condition is compared against either Neumann boundary condition or elastic registration
ExamplesExample 2Example 3Example 4Example 5
$\| \phi^*(\mathbf{x}) - \phi^*_{true}(\mathbf{x}) \|_{L_2(\Omega)}$ Periodic: $0$ Periodic: $0.0053$ Periodic: $0.066$ Mass transport, periodic: $0.0055$
Neumann: $0.056$Neumann: $0.056$Neumann: $0.088$Two-step empirical: $0.011$
Table Options

Download as excel

ExamplesExample 2Example 3Example 4Example 5
$\| \phi^*(\mathbf{x}) - \phi^*_{true}(\mathbf{x}) \|_{L_2(\Omega)}$ Periodic: $0$ Periodic: $0.0053$ Periodic: $0.066$ Mass transport, periodic: $0.0055$
Neumann: $0.056$Neumann: $0.056$Neumann: $0.088$Two-step empirical: $0.011$
Table 5.  Number of steps for convergence (residual tolerance $10^{-4}$), and CPU time for Example 3 with different image sizes. Here (ⅰ) corrections of translation kernels refer to Line 4-7 of Table 1, and (ⅱ) the primary nonlinear solver refers to Line 8-12 of Table 1. The experiments are run in MATLAB
ExampleExample 3
Image size100x100200x200400x400800x800
Number of steps for convergence5333
CPU time for corrections of translation kernels (sec)1.04.630259
CPU time for the primary nonlinear solver (sec)3.17.3581083
Total CPU time (sec)4.111.9881342
Table Options

Download as excel

ExampleExample 3
Image size100x100200x200400x400800x800
Number of steps for convergence5333
CPU time for corrections of translation kernels (sec)1.04.630259
CPU time for the primary nonlinear solver (sec)3.17.3581083
Total CPU time (sec)4.111.9881342
Table 6.  Number of steps for convergence (residual tolerance $10^{-4}$), and CPU time for nonlinear solver only for Examples 3-7 with the same image sizes. The experiments are run in MATLAB
ExamplesExample 3Example 4Example 5Example 6Example 7
Image size600x600
Number of steps for convergence33101019
CPU time for the primary nonlinear solver (sec)1471526686271613
Table Options

Download as excel

ExamplesExample 3Example 4Example 5Example 6Example 7
Image size600x600
Number of steps for convergence33101019
CPU time for the primary nonlinear solver (sec)1471526686271613
Table 7.  Residual versus the number of iteration $k$ for Example 5
The number of iteration $k$12345
Residual13821952.321.710.131
The number of iteration $k$678910
Residual0.02360.004929.50x10$^{-4}$3.42x10$^{-4}$9.41x10$^{-5}$
Table Options

Download as excel

The number of iteration $k$12345
Residual13821952.321.710.131
The number of iteration $k$678910
Residual0.02360.004929.50x10$^{-4}$3.42x10$^{-4}$9.41x10$^{-5}$
[1]

Adam M. Oberman. Wide stencil finite difference schemes for the elliptic Monge-Ampère equation and functions of the eigenvalues of the Hessian. Discrete & Continuous Dynamical Systems - B, 2008, 10 (1) : 221-238. doi: 10.3934/dcdsb.2008.10.221
[2]

Daniele Castorina, Annalisa Cesaroni, Luca Rossi. On a parabolic Hamilton-Jacobi-Bellman equation degenerating at the boundary. Communications on Pure & Applied Analysis, 2016, 15 (4) : 1251-1263. doi: 10.3934/cpaa.2016.15.1251
[3]

Jean-Claude Zambrini. On the geometry of the Hamilton-Jacobi-Bellman equation. Journal of Geometric Mechanics, 2009, 1 (3) : 369-387. doi: 10.3934/jgm.2009.1.369
[4]

Bian-Xia Yang, Shanshan Gu, Guowei Dai. Existence and multiplicity for Hamilton-Jacobi-Bellman equation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021130
[5]

Qi-Rui Li, Xu-Jia Wang. Regularity of the homogeneous Monge-Ampère equation. Discrete & Continuous Dynamical Systems, 2015, 35 (12) : 6069-6084. doi: 10.3934/dcds.2015.35.6069
[6]

Steven Richardson, Song Wang. The viscosity approximation to the Hamilton-Jacobi-Bellman equation in optimal feedback control: Upper bounds for extended domains. Journal of Industrial & Management Optimization, 2010, 6 (1) : 161-175. doi: 10.3934/jimo.2010.6.161
[7]

Shuyu Gong, Ziwei Zhou, Jiguang Bao. Existence and uniqueness of viscosity solutions to the exterior problem of a parabolic Monge-Ampère equation. Communications on Pure & Applied Analysis, 2020, 19 (10) : 4921-4936. doi: 10.3934/cpaa.2020218
[8]

Zhen-Zhen Tao, Bing Sun. A feedback design for numerical solution to optimal control problems based on Hamilton-Jacobi-Bellman equation. Electronic Research Archive, , () : -. doi: 10.3934/era.2021046
[9]

Xuhui Wang, Lei Hu. A new method to solve the Hamilton-Jacobi-Bellman equation for a stochastic portfolio optimization model with boundary memory. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021137
[10]

Zhijun Zhang. Optimal global asymptotic behavior of the solution to a singular monge-ampère equation. Communications on Pure & Applied Analysis, 2020, 19 (2) : 1129-1145. doi: 10.3934/cpaa.2020053
[11]

Luca Codenotti, Marta Lewicka. Visualization of the convex integration solutions to the Monge-Ampère equation. Evolution Equations & Control Theory, 2019, 8 (2) : 273-300. doi: 10.3934/eect.2019015
[12]

Bo Guan, Qun Li. A Monge-Ampère type fully nonlinear equation on Hermitian manifolds. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1991-1999. doi: 10.3934/dcdsb.2012.17.1991
[13]

Alessio Figalli, Young-Heon Kim. Partial regularity of Brenier solutions of the Monge-Ampère equation. Discrete & Continuous Dynamical Systems, 2010, 28 (2) : 559-565. doi: 10.3934/dcds.2010.28.559
[14]

Yahui Niu. Monotonicity of solutions for a class of nonlocal Monge-Ampère problem. Communications on Pure & Applied Analysis, 2020, 19 (11) : 5269-5283. doi: 10.3934/cpaa.2020237
[15]

Juhua Shi, Feida Jiang. The degenerate Monge-Ampère equations with the Neumann condition. Communications on Pure & Applied Analysis, 2021, 20 (2) : 915-931. doi: 10.3934/cpaa.2020297
[16]

Diego Maldonado. On interior $C^2$-estimates for the Monge-Ampère equation. Discrete & Continuous Dynamical Systems, 2018, 38 (3) : 1427-1440. doi: 10.3934/dcds.2018058
[17]

Haitao Yang, Yibin Chang. On the blow-up boundary solutions of the Monge -Ampére equation with singular weights. Communications on Pure & Applied Analysis, 2012, 11 (2) : 697-708. doi: 10.3934/cpaa.2012.11.697
[18]

Mengni Li. Global regularity for a class of Monge-Ampère type equations with nonzero boundary conditions. Communications on Pure & Applied Analysis, 2021, 20 (1) : 301-317. doi: 10.3934/cpaa.2020267
[19]

Shouchuan Hu, Haiyan Wang. Convex solutions of boundary value problem arising from Monge-Ampère equations. Discrete & Continuous Dynamical Systems, 2006, 16 (3) : 705-720. doi: 10.3934/dcds.2006.16.705
[20]

Barbara Brandolini, Carlo Nitsch, Cristina Trombetti. Shape optimization for Monge-Ampère equations via domain derivative. Discrete & Continuous Dynamical Systems - S, 2011, 4 (4) : 825-831. doi: 10.3934/dcdss.2011.4.825

2020 Impact Factor: 1.639

Tools

Metrics

  • PDF downloads (262)
  • HTML views (310)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences