Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-17T17:51:57.175Z Has data issue: false hasContentIssue false
  • English
  • Français

A Fourth-Order Compact Finite Difference Scheme for Higher-Order PDE-Based Image Registration

Published online by Cambridge University Press:  10 November 2015

Sopida Jewprasert ,
Noppadol Chumchob  and
Chantana Chantrapornchai
Sopida Jewprasert
Affiliation:
Department of Mathematics, Faculty of Science, Silpakorn University, Nakorn Pathom 73000, Thailand
Noppadol Chumchob*
Affiliation:
Department of Mathematics, Faculty of Science, Silpakorn University, Nakorn Pathom 73000, Thailand Centre of Excellence in Mathematics, CHE, SiAyutthaya Rd., Bangkok 10400, Thailand
Chantana Chantrapornchai
Affiliation:
Department of Computer Engineering, Faculty of Engineering, Kasetsart University, Bangkok 10900, Thailand
*
*Corresponding author. Email addresses:[email protected] (S. Jewprasert), [email protected](N. Chumchob), [email protected](C. Chantrapornchai)
Get access

Abstract

Image registration is an ill-posed problem that has been studied widely in recent years. The so-called curvature-based image registration method is one of the most effective and well-known approaches, as it produces smooth solutions and allows an automatic rigid alignment. An important outstanding issue is the accurate and efficient numerical solution of the Euler-Lagrange system of two coupled nonlinear biharmonic equations, addressed in this article. We propose a fourth-order compact (FOC) finite difference scheme using a splitting operator on a 9-point stencil, and discuss how the resulting nonlinear discrete system can be solved efficiently by a nonlinear multi-grid (NMG) method. Thus after measuring the h-ellipticity of the nonlinear discrete operator involved by a local Fourier analysis (LFA), we show that our FOC finite difference method is amenable to multi-grid (MG) methods and an appropriate point-wise smoothing procedure. A high potential point-wise smoother using an outer-inner iteration method is shown to be effective by the LFA and numerical experiments. Real medical images are used to compare the accuracy and efficiency of our approach and the standard second-order central (SSOC) finite difference scheme in the same NMG framework. As expected for a higher-order finite difference scheme, the images generated by our FOC finite difference scheme prove significantly more accurate than those computed using the SSOC finite difference scheme. Our numerical results are consistent with the LFA analysis, and also demonstrate that the NMG method converges within a few steps.

Keywords

65F1065M5568U10Curvature image registrationfourth-order compact finite difference schemelocal Fourier analysisnonlinear multi-grid methodnonlinear biharmonic equation
Type
Research Article
Information
East Asian Journal on Applied Mathematics , Volume 5 , Issue 4 , November 2015 , pp. 361 - 386
Copyright
Copyright © Global-Science Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Agarwal, R.P. and Wang, Y.M., Some recent developments of the Numerov's method, Comput. Math. Appl. 42, 561–592 (2001).Google Scholar
[2]Altas, I., Dym, J., Gupta, M.M. and Manohar, R.P., Multigrid solution of automatically generated high-order discretizations for the biharmonic equation, SIAM J. Sc. Comput. 19, 1575–1585 (1998).Google Scholar
[3]Badshahand, N.Chen, K., Multigrid method for the Chan-Vese model in variational segmentation, Comm. Comput. Phys. 4, 294–316 (2008).Google Scholar
[4]Badshah, N. and Chen, K., On two multigrid algorithms for modelling variational multiphase image segmentation, IEEE Trans. Image Proc. 18, 1097–1106 (2009).Google Scholar
[5]Bajcsy, R. and Kovačič, S., Multiresolution elastic matching, Comput. Vision Graph. Image Proc. 46, 1–21 (1989).Google Scholar
[6]Briggs, W.L., Henson, V.E. and McCormick, S.F., A Multigrid Tutorial (2nd Edition). SIAM Publications, Philadelphia (2000).Google Scholar
[7]Brito-Loeza, C. and Chen, K., Multigrid method for a modified curvature driven diffusion model for image inpainting, JCM 26, 856–875 (2008).Google Scholar
[8]Brito-Loeza, C. and Chen, K., Fast numerical algorithms for Euler's Elastica digital inpainting model, Int. J. Mod. Math. 5, 157–182 (2010). 2010.Google Scholar
[9]Brito-Loeza, C. and Chen, K., Multigrid algorithm for high order denoising, SIAM J. Imaging Sci. 3, 363–389 (2010).Google Scholar
[10]Broit, C., Optimal registration of deformed images. PhD thesis, University of Pennsylvania (1981).Google Scholar
[11]Bröker, O., Grote, M. J., Mayer, C. and Reusken, A., Robust parallel smoothing for multigrid via sparse approximate inverses, SIAM J. Sci. Comput. 23, 1396–1417 (2001).Google Scholar
[12]Chan, T.F. and Chen, K., On a nonlinear multigrid algorithm with primal relaxation for the image total variation minimisation, Num. Algorithms 41, 387–411 (2006).Google Scholar
[13]Chan, T.F. and Chen, K., An optimization-based multilevel algorithm for total variation image denoising, Multiscale Mod. Sim. 5, 615–645 (2006).CrossRefGoogle Scholar
[14]Chumchob, N., Vectorial total variation-based regularization for variational image registration, IEEE Trans. Image Proc. 22, 4551–4559 (2013).Google Scholar
[15]Chumchob, N. and Chen, K., A variational approach for discontinuity-preserving image registration, East-West J. Math. Special volume, 266–282 (2010).Google Scholar
[16]Chumchob, N. and Chen, K., A robust multigrid approach for variational image registration models, J. Comput. Appl. Math. 236, 653–674 (2011).Google Scholar
[17]Chumchob, N. and Chen, K., Improved variational image registration model and a fast algorithm for its numerical approximation, Num. Meth. Partial Diff. Eq. 28, 1966–1995 (2012).Google Scholar
[18]Chumchob, N., Chen, K. and Brito, C., A fourth order variational image registration model and its fast multigrid algorithm, SIAM J. Multiscale Mod. Sim. 9, 89–128 (2011).Google Scholar
[19]Dehghan, M. and Mohebbi, A., Multigrid solution of high order discretisation for three-dimensional biharmonic equation with Dirichlet boundary conditions of second kind, Appl. Math. Comput. 180, 575–593 (2006).Google Scholar
[20]Ehrlich, L.W., Solving the biharmonic equation as coupled finite difference equations, SIAM J. Num. Anal. 8, 278–287 (1971).CrossRefGoogle Scholar
[21]Evans, D.J. and Mohanty, R.K., Block iterative methods for the numerical solution of two-dimensional non-linear biharmonic equations, Int. J. Comput. Math. 69, 371–390 (1998).Google Scholar
[22]Schauf, C.F., Henn, S. and Witsch, K., Multigrid based total variation image registration, Comput. Visual Sci. 11, 101–113 (2008).Google Scholar
[23]Fischer, B. and Modersitzki, J., Fast diffusion registration, Contemporary Math. 313, 117–129 (2002).Google Scholar
[24]Fischer, B. and Modersitzki, J., Curvature-based image registration, J. Math. Imaging Vision 18, 81–85 (2003).Google Scholar
[25]Fischer, B. and Modersitzki, J., A unified approach to fast image registration and a new curvature based registration technique, Linear Alg. Appl. 380, 107–124 (2004).Google Scholar
[26]Gao, S., Zhang, L., Wang, H., de, R. Crevoisier, Kuban, D.D., Mohan, R. and Dong, L., A deformable image registration method to handle distended rectums in prostate cancer radiotherapy, Med. Phys. 33, 3304–3312 (2006).Google Scholar
[27]Ge, Y., Multigrid method and fourth-order compact difference discretization scheme with unequal mesh sizes for 3D Poisson equation, J. Comput. Phys. 229, 6381–6391 (2010).Google Scholar
[28]Haber, E., Horesh, R. and Modersitzki, J., Numerical optimization for constrained image registration, Num. Linear Alg. Appl. 17, 343–359 (2010).Google Scholar
[29]Haber, E. and Modersitzki, J., A multilevel method for image registration, SIAM J. Sci. Comput. 27, 1594–1607 (2006).Google Scholar
[30]Hackbusch, W., Multi-Grid Methods and Applications. Springer-Verlag Berlin Heidelberg New York (1985).Google Scholar
[31]Hajnal, J.V., Hill, D.L.G. and Hawkes, D.J., Medical Image Registration, The Biomedical Engineering Series, CRC Press (2001).Google Scholar
[32]Hamilton, S., Benzi, M. and Haber, E., New multigrid smoothers for the Oseen problem Num. Linear Algebra Appl. 17, 557–576 (2010).Google Scholar
[33]Henn, S., A multigrid method for a fourth-order diffusion equation with application to image processing, SIAM J. Sci. Comput. 27, 831–849 (2005).Google Scholar
[34]Henn, S., A full Curvature-based algorithm for image registration, J. Math. Imaging Vision 24, 195–208 (2006).Google Scholar
[35]Henn, S., A translation and rotation invariant Gauss-Newton like scheme for image registration, BIT Num. Math. 46, 325–344 (2006).CrossRefGoogle Scholar
[36]Henn, S. and Witsch, K., Iterative multigrid regularization techniques for image matching, SIAM J. Sci. Comput. 23, 1077–1093 (2001).Google Scholar
[37]Henn, S. and Witsch, K., Image registration based on multiscale energy information, Multiscale Mod. Sim. 4, 584–609 (2005).Google Scholar
[38]Henn, S. and Witsch, K., A variational image registration approach based on curvature scale space, LNCS 3459, 143–154 (2005).Google Scholar
[39]Hömke, L., A multigrid method for anisotropic PDE in elastic image registration, Num. Linear Algebra Appl. 13, 215–229 (2006).Google Scholar
[40]Köstler, H., Ruhnau, K. and Wienands, R., Multigrid solution of the optical flow system using a combined diffusion- and curvature-based regularizer, Num. Linear Algebra Appl. 15, 201–218 (2008).Google Scholar
[41]Larrey-Ruiz, J., Verdú-Monedero, R. and Morales-Sánchez, J., A Fourier domain framework for variational image registration, J. Math. Imaging Vision 32, 57–72 (2008).CrossRefGoogle Scholar
[42]Bauer, L. and Riessl, E.L., Block five diagonal matrices and the fast numerical solution of the biharmonic equation, Math. Comput. 26, 311–326 (1972).Google Scholar
[43]Maintz, J.B.A. and Viergever, M.A., A survey of medical image registration, Med. Image. Anal. 2, 1–36 (1998).Google Scholar
[44]Modersitzki, J., Numerical Methods for Image Registration, Oxford (2004).Google Scholar
[45]Modersitzki, J., FAIR: Flexible Algorithms for Image Registration, SIAM Publications, Philadelphia (2009).Google Scholar
[46]Mohanty, R.K., A new high accuracy finite difference discretization for the solution of 2D nonlinear biharmonic equations using coupled approach, Num. Meth. Partial Diff. Eq. 26, 931–944 (2010).Google Scholar
[47]Mohanty, R.K. and Pandey, P. K., Difference methods of order two and four for systems of mildly nonlinear biharmonic problems of second kind in two space dimensions, Num. Meth. Partial Diff. Eq. 12, 707–717 (1996).Google Scholar
[48]Seynaeve, B., Rosseel, E., Nicolaï, B. and Vandewalle, S.. Fourier mode analysis of multigrid methods for partial differential equations with random coefficients, J. Comput. Phys. 224, 132–149 (2007).Google Scholar
[49]Smith, J., The coupled equation approach to the numerical solution of the biharmonic equation by finite differences, SIAM J. Num. Anal. 7, 104–111 (1970).Google Scholar
[50]Stephenson, J.W., Single cell discretization of order two and four for biharmonic problems, J. Comput. Phys. 55, 65–80 (1984).Google Scholar
[51]Stürmer, M., Köstler, H. and Rüde, U., A fast full multigrid solver for applications in image processing, Num. Linear Algebra Appl. 15, 187–200 (2008).Google Scholar
[52]Tian, Z.F. and Yu, P.X., An efficient compact difference scheme for solving the streamfunction formulation of the incompressible Navier-Stokes equations, J. Comput. Phys. 230, 6404–6419 (2011).Google Scholar
[53]Trottenberg, U., Oosterlee, C. and Schüller, A., Multigrid, Academic Press (2001).Google Scholar
[54]Verdú-Monedero, R., Larrey-Ruiz, J. and Morales-Sanchez, J., Frequency implementation of the Euler-Lagrange equations for variational image registration, IEEE Signal Proc. Lett. 15, 321–324 (2008).Google Scholar
[55]Wesseling, R., An Introduction to Multigrid Methods, Edwards, Philadelphia (2004).Google Scholar
[56]Wienands, R. and Joppich, W., Practical Fourier Analysis for Multigrid Method, Chapman & Hall/CRC (2005).Google Scholar
[57]Zikic, D., Wein, W., Khamene, A., Clevert, D.A. and Navab, N., Fast deformable registration of 3D—ultrasound data using a variational approach, LNCS 4190, 915–923 (2006).Google Scholar