An augmented lagrangian method for solving a new variational model based on gradients similarity measures and high order regulariation for multimodality registration

Anis Theljani; Ke Chen

doi:10.3934/ipi.2019016

Article Contents

2019, Volume 13, Issue 2: 309-335. Doi: 10.3934/ipi.2019016

This issue Previous Article Incorporating structural prior information and sparsity into EIT using parallel level sets Next Article Propagation of boundary-induced discontinuity in stationary radiative transfer and its application to the optical tomography

An augmented lagrangian method for solving a new variational model based on gradients similarity measures and high order regulariation for multimodality registration

Anis Theljani and
Ke Chen^,

Department of Mathematical Sciences and EPSRC Liverpool Centre for Mathematics in Healthcare, The University of Liverpool, Liverpool L69 7ZL, UK

^* Corresponding author: Ke Chen http://www.liverpool.ac.uk/~cmchenke
^* Corresponding author: Ke Chen http://www.liverpool.ac.uk/~cmchenke

Received: February 28, 2018

Revised: September 30, 2018

Published: March 2019

Both authors are supported by the UK EPSRC grant EP/N014499/1.

Abstract Full Text(HTML) Figure(12) / Table(3) Related Papers Cited by

Abstract

In this work we propose a variational model for multi-modal image registration. It minimizes a new functional based on using reformulated normalized gradients of the images as the fidelity term and higher-order derivatives as the regularizer. We first present a theoretical analysis of the proposed model. Then, to solve the model numerically, we use an augmented Lagrangian method (ALM) to reformulate it to a few more amenable subproblems (each giving rise to an Euler-Lagrange equation that is discretized by finite difference methods) and solve iteratively the main linear systems by the fast Fourier transform; a multilevel technique is employed to speed up the initialisation and avoid likely local minima of the underlying functional. Finally we show the convergence of the ALM solver and give numerical results of the new approach. Comparisons with some existing methods are presented to illustrate its effectiveness and advantages.

Keywords:

Mathematics Subject Classification: Primary: 65M32, 35Q68, 94A08; Secondary: 65M22, 35G15.

Citation:

Full Text(HTML)

Figure 1. Example of Reference and Template images where $ \nabla_n T\cdot \nabla_n R = 0 $ (or one of $ \nabla_n T, \ \nabla_n R $ is zero) a.e in $ \Omega $

Download: Full-size image PowerPoint slide

Figure 2. Three examples of the triangle inequality for triangles with sides $ X $, $ Y $ and $ Z $. The left example shows a case where $ |Z| $ is much less than the sum $ |X| +|Y| $ of the other two sides, and the right example shows a case where $ |Z| $ is only slightly less than $ |X| +|Y| $

Download: Full-size image PowerPoint slide

Figure 3. Example of a multilevel representation of images

Download: Full-size image PowerPoint slide

Figure 4. Example 1: Comparison of three different models. Clearly only Our Model works while NGF, MI fail completely

Download: Full-size image PowerPoint slide

Figure 5. Example 2: Comparison of different models to register T-1 and T2-MRI images. New Model performs the best

Download: Full-size image PowerPoint slide

Figure 6. Example 3: Registration of a second pair of MRI images (T1 and T2). New Model performs the best

Download: Full-size image PowerPoint slide

Figure 7. Comparison of $ 3 $ different models to register the MRI images fin Fig. 6. Example 3 zoomed in the red squares (see Fig. 6): From left to right; Zooms in the reference $ R $ and the registered $ T(\mathbf u) $ using New model, NGF and MI, respectively.

Download: Full-size image PowerPoint slide

Figure 8. Example 4: High-b- and Low-b-value Diffusion-weighted MRIs (of $ 256\times 256 $) using different models. New Model performs the best

Download: Full-size image PowerPoint slide

Figure 9. Example 5: a pair of MRI images of higher resolution $ 512\times 512 $ by $ 3 $ different models. New Model and MI perform identically, both better than NGF

Download: Full-size image PowerPoint slide

Figure 10. Left: Log scale plot of the residual errors for $ \mathbf u $ versus ALM iteration numbers for examples 2-5. Right: Plot of the error $ S_{er} $ values versus ALM iteration numbers for examples 2-5

Download: Full-size image PowerPoint slide

Figure 11. Left: Log scale plot of the distance D_m versus ALM iteration numbers for examples 2-5

Download: Full-size image PowerPoint slide

Figure 12. Example 6: Registering a PET image to an MRI vimage. New model performs better than others in this example

Download: Full-size image PowerPoint slide

Table 1. Run time comparison for all models for the pair of MRI images in Fig. 6

	Resolution
	$64 \times 64$	$128 \times 128$	$256 \times 256$	$512 \times 512$
Time (s) for New Model	29.836	49.931	117.342	272.578
Time (s) for MI Model	14.794	21.437	48.881	76.398
Time (s) for NGF Model	22.003	42.845	100.961	264.388

| Show Table

DownLoad: CSV

Table 2. Registration results of the different models for processing Examples 1-6. The errors are computed using formula (38), (40) and (39). Here, #N is the ratio of the number of pixels where $\nabla_n T\cdot \nabla_n R \neq 0$ over the total number of pixels, whereas #G is the ratio of number pixels where GF(T, R)+TM(T, R) ≠ 0 over the total number of pixels.

Compared Models			NGF			New Model
	#G	#N	GF_er	NGF_er	MI_er	GF_er	NGF_er	MI_er
Ex 1	0.2%	.02%	0.540	0.964	0.446	0.032	0.932	0.993
Ex 2	49%	24%	0.636	0.640	1.170	0.247	0.756	1.206
Ex 3	49%	23%	0.336	0.491	1.265	0.238	0.389	1.290
Ex 4	49%	20%	0.901	0.856	1.150	0.674	0.800	1.184
Ex 5	43%	37%	0.741	0.656	1.163	0.454	0.623	1.178
Ex 6	48%	23%	0.952	0.957	1.187	0.801	0.920	1.341

Compared Models			MI
	#G	#N	GF_er	NGF_er	MI_er	Note:
Ex 1	0.2%	.02%	0.370	0.97	0.381	for GF_er and NGF_er, the smaller the better.
Ex 2	49%	24%	0.490	0.879	1.193	for GF_er and NGF_er, the smaller the better.
Ex 3	49%	23%	0.463	0.579	1.265	But for MI_er, The larger the better.
Ex 4	49%	20%	0.765	0.849	1.154
Ex 5	43%	37%	0.454	0.631	1.163
Ex 6	48%	23%	0.836	0.970	1.254

| Show Table

DownLoad: CSV

Table 3. Registration results for $ \frac{\alpha_1}{\lambda} $-dependence tests of New Model for processing Example 3. The relative errors are computed using the normalized gradient fitting formula (38). In all cases, we set $ \alpha = 0.01\alpha_1 $

$\frac{\alpha_1}{\lambda}$	0.1	0.05	0.025	0.017	0.0125	0.01	0.0075	0.005
Error	0.238	0.237	0.237	0.236	0.237	0.237	0.238	0.24

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	E. Bae, J. Shi and X.-C. Tai, Graph cuts for curvature based image denoising, IEEE Transactions on Image Processing, 20 (2011), 1199-1210. doi: 10.1109/TIP.2010.2090533.
[2]	M. Burger, J. Modersitzki and L. Ruthotto, A hyperelastic regularization energy for image registration, SIAM Journal on Scientific Computing, 35 (2013), 132-148. doi: 10.1137/110835955.
[3]	Y. M. Chen, J. L. Shi, M. Rao and J. S. Lee, Deformable multi-modal image registration by maximizing renyi's statistical dependence measure, Inverse Problems and Imaging, 9 (2015), 79-103. doi: 10.3934/ipi.2015.9.79.
[4]	N. Chumchob, Vectorial total variation-based regularization for variational image registration, IEEE Transactions on Image Processing, 22 (2013), 4551-4559. doi: 10.1109/TIP.2013.2274749.
[5]	N. Chumchob and K. Chen, Improved variational image registration model and a fast algorithm for its numerical approximation, Numerical Methods for Partial Differential Equations, 28 (2012), 1966-1995. doi: 10.1002/num.20710.
[6]	N. Chumchob, K. Chen and C. Brito-Loeza, A fourth-order variational image registration model and its fast multigrid algorithm, Multiscale Modeling & Simulation, 9 (2011), 89-128. doi: 10.1137/100788239.
[7]	M. Droske and W. Ring, A mumford-shah level-set approach for geometric image registration, SIAM journal on Applied Mathematics, 66 (2006), 2127-2148. doi: 10.1137/050630209.
[8]	J. Feydy, B. Charlier, F. V. Vialard and G. Peyre, Optimal transport for diffeomorphic registration, International Conference on Medical Image Computing and Computer-Assisted Intervention, MICCAI 2017: Medical Image Computing and Computer Assisted Intervention - MICCAI, (2017), 291-299, https://arXiv.org/abs/1706.05218v1. doi: 10.1007/978-3-319-66182-7_34.
[9]	B. Fischer and J. Modersitzki, Fast diffusion registration, Contemp. Math., 313 (2002), 117-129. doi: 10.1090/conm/313/05372.
[10]	B. Fischer and J. Modersitzki, Curvature based image registration, Journal of Mathematical Imaging and Vision, 18 (2003), 81-85. doi: 10.1023/A:1021897212261.
[11]	B. Fischer and J. Modersitzki, Ill-posed medicine - an introduction to image registration, Inverse Problems, 24 (2008), 034008, 16 pp. doi: 10.1088/0266-5611/24/3/034008.
[12]	E. Haber and J. Modersitzki, Numerical methods for volume preserving image registration, Inverse Problems, 20 (2004), 1621-1638. doi: 10.1088/0266-5611/20/5/018.
[13]	E. Haber and J. Modersitzki, Image registration with guaranteed displacement regularity, International Journal of Computer Vision, 71 (2007), 361-372. doi: 10.1007/s11263-006-8984-4.
[14]	S. Henn, A multigrid method for a fourth-order diffusion equation with application to image processing, SIAM Journal on Scientific Computing, 27 (2005), 831-849. doi: 10.1137/040611124.
[15]	E. Hodneland, A. Lundervold, J. Rørvik and A. Z. Munthe-Kaas, Normalized gradient fields for nonlinear motion correction of dce-mri time series, Computerized Medical Imaging and Graphics, 38 (2014), 202-210.
[16]	W. Hu, Y. Xie, L. Li and W. Zhang, A total variation based nonrigid image registration by combining parametric and non-parametric transformation models, Neurocomputing, 144 (2014), 222-237. doi: 10.1016/j.neucom.2014.05.031.
[17]	M. Ibrahim, K. Chen and C. Brito-Loeza, A novel variational model for image registration using gaussian curvature, Geometry, Imaging and Computing, 1 (2014), 417-446. doi: 10.4310/GIC.2014.v1.n4.a2.
[18]	L. König and J. Rühaak, A fast and accurate parallel algorithm for non-linear image registration using normalized gradient fields, in Biomedical Imaging (ISBI), 2014 IEEE 11th International Symposium on, IEEE, 2014,580-583.
[19]	D. Loeckx, P. Slagmolen, F. Maes, D. Vandermeulen and P. Suetens, Nonrigid image registration using conditional mutual information, IEEE Transactions on Medical Imaging, 29 (2010), 19-29.
[20]	F. Maes, A. Collignon, D. Vandermeulen, G. Marchal and P. Suetens, Multimodality image registration by maximization of mutual information, IEEE Transactions on Tedical Imaging, 16 (1997), 187-198. doi: 10.1109/42.563664.
[21]	A. Mang and G. Biros, An inexact Newton-Krylov algorithm for constrained diffeomorphic image registration, SIAM Journal on Imaging Sciences, 8 (2015), 1030-1069. doi: 10.1137/140984002.
[22]	A. Mang and G. Biros, Constrained $h^1$-regularization schemes for diffeomorphic image registration, SIAM Journal on Imaging Sciences, 9 (2016), 1154-1194. doi: 10.1137/15M1010919.
[23]	J. Modersitzki, FAIR: Flexible Algorithms for Image Registration, SIAM, 2009. doi: 10.1137/1.9780898718843.
[24]	F. P. Oliveira and J. M. R. Tavares, Medical image registration: A review, Computer Methods in Biomechanics and Biomedical Engineering, 17 (2014), 73-93. doi: 10.1080/10255842.2012.670855.
[25]	K. Papafitsoros, C. B. Schoenlieb and B. Sengul, Combined first and second order total variation inpainting using split bregman, Image Processing On Line, 3 (2013), 112-136. doi: 10.5201/ipol.2013.40.
[26]	J. P. Pluim, J. A. Maintz and M. A. Viergever, Mutual-information-based registration of medical images: A survey, IEEE Transactions on Medical Imaging, 22 (2003), 986-1004. doi: 10.1109/TMI.2003.815867.
[27]	C. Pöschl, J. Modersitzki and O. Scherzer, A variational setting for volume constrained image registration, Inverse Problems and Imaging, 4 (2010), 505-522. doi: 10.3934/ipi.2010.4.505.
[28]	T. Rohlfing, C. R. Maurer, D. A. Bluemke and M. A. Jacobs, Volume-preserving nonrigid registration of mr breast images using free-form deformation with an incompressibility constraint, IEEE transactions on medical imaging, 22 (2003), 730-741. doi: 10.1109/TMI.2003.814791.
[29]	G. Roland and L. T. Patrick, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, SIAM, 1989. doi: 10.1137/1.9781611970838.
[30]	J. Rühaak, L. König, M. Hallmann, N. Papenberg, S. Heldmann, H. Schumacher and B. Fischer, A fully parallel algorithm for multimodal image registration using normalized gradient fields, in Biomedical Imaging (ISBI), 2013 IEEE 10th International Symposium on, IEEE, 2013,572-575.
[31]	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.
[32]	X.-C. Tai, J. Hahn and G. J. Chung, A fast algorithm for Euler's elastica model using augmented lagrangian method, SIAM Journal on Imaging Sciences, 4 (2011), 313-344. doi: 10.1137/100803730.
[33]	P. Viola and W. M. Wells Ⅲ, Alignment by maximization of mutual information, International Journal of Computer Vision, 24 (1997), 137-154.
[34]	C. Wu and X. C. Tai, Augmented lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and high order models, SIAM Journal on Imaging Sciences, 3 (2010), 300-339. doi: 10.1137/090767558.
[35]	C. Wu, J. Zhang and X.-C. Tai, Augmented Lagrangian method for total variation restoration with non-quadratic fidelity, Inverse Problems and Imaging, 5 (2011), 237-261. doi: 10.3934/ipi.2011.5.237.
[36]	C. Xing and P. Qiu, Intensity-based image registration by nonparametric local smoothing, IEEE Transactions on Pattern Analysis and Machine Intelligence, 33 (2011), 2081-2092.
[37]	M. Yashtini and S. H. Kang, A fast relaxed normal two split method and an effective weighted TV approach for E1uler's elastica image inpainting, SIAM Journal on Imaging Sciences, 9 (2016), 1552-1581. doi: 10.1137/16M1063757.
[38]	W. Yilun, Y. Junfeng, Y. Wotao and Z. Yin, A new alternating minimization algorithm for total variation image reconstruction, SIAM Journal on Imaging Sciences, 1 (2008), 248-272. doi: 10.1137/080724265.
[39]	J. Zhang and K. Chen, Variational image registration by a total fractional-order variation model, Journal of Computational Physics, 293 (2015), 442-461. doi: 10.1016/j.jcp.2015.02.021.
[40]	J. Zhang, K. Chen and B. Yu, An improved discontinuity-preserving image registration model and its fast algorithm, Applied Mathematical Modelling, 40 (2016), 10740-10759. doi: 10.1016/j.apm.2016.08.009.
[41]	J. Zhang, K. Chen and B. Yu, A novel high-order functional based image registration model with inequality constraint, Mathematics with Applications, 72 (2016), 2887-2899. doi: 10.1016/j.camwa.2016.10.018.
[42]	X. Zhou, Weak lower semicontinuity of a functional with any order, Journal of Mathematical Analysis and Applications, 221 (1998), 217-237. doi: 10.1006/jmaa.1997.5881.
[43]	W. ZHU, X.-C. TAI and T. CHAN, Augmented lagrangian method for a mean curvature based image denoising model, Imaging, 7 (2013), 1409-1432. doi: 10.3934/ipi.2013.7.1409.
[44]	W. Zhu, X.-C. Tai and T. Chan, Image segmentation using euler's elastica as the regularization, Journal of Scientific Computing, 57 (2013), 414-438. doi: 10.1007/s10915-013-9710-3.