×

An accelerated version of alternating direction method of multipliers for TV minimization in EIT. (English) Zbl 1480.94007

Summary: Existing total variation (TV) solvers that have been applied in electrical impedance tomography (EIT) smooth the TV function in order to cope with its non-differentiability around the origin, and thus imposes some numerical errors on the solution. Furthermore, these solvers require storage of Hessian, and are thus very impractical for large-scale computations, especially 3D EIT. These shortcomings were addressed by TV solvers that are based on first-order optimization methods. However, the application of these solvers to EIT remains scarce. In this manuscript, we propose an accelerated version of a gradient-based TV solver based on augmented Lagrangian and alternating direction method of multipliers, referred to as TVAL3, and apply it to EIT. The results demonstrate the superiority of the accelerated algorithm over existing TV solvers in EIT with regard to both accuracy and speed.

MSC:

94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
65N21 Numerical methods for inverse problems for boundary value problems involving PDEs

Software:

TwIST; RecPF; NESTA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Holder, D. S., Electrical impedance tomography: methods, history and applications, 3-64, (2004), Institute of Physics Publishing
[2] Bayford, R. H., Bioimpedance tomography (electrical impedance tomography), Annu. Rev. Biomed. Eng., 8, 63-91, (2006)
[3] Barber, D. C.; Brown, B. H., Errors in reconstruction of resistivity images using a linear reconstruction technique, Clin. Phys. Physiol. Meas., 9, 101-104, (1988)
[4] Abascal, J. F.P. J.; Arridge, S. R.; Atkinson, D.; Horesh, R.; Fabrizi, L.; Lucia, M. D.; Horesh, L.; Bayford, R. H.; Holder, D. S., Use of anisotropic modelling in electrical impedance tomography; description of method and preliminary assessment of utility in imaging brain function in the adult human head, NeuroImage, 43, 258-268, (2008)
[5] Adler, A.; Arnold, J. H.; Bayford, R.; Borsic, A.; Brown, B.; Dixon, P.; Faes, T. J.C.; Frerichs, I.; Gagnon, H.; Gaerber, Y.; Grychtol, B.; Hahn, G.; Lionheart, W. R.B.; Malik, A.; Patterson, R. P.; Stocks, J.; Tizzard, A.; Weiler, N.; Wolf, G. K., GREIT: a unified approach to 2D linear EIT reconstruction of lung images, Physiol. Meas., 30, 35-55, (2009)
[6] Balleza, M.; Calaf, N.; Feixas, T.; Gonzalez, M.; Anton, D.; Riu, P. J.; Casan, P., Measuring breathing pattern in patients with chronic obstructive pulmonary disease by electrical impedance tomography, Arch. Bronconeumol., 45, 320-324, (2009)
[7] Javaherian, A.; Soleimani, M., Compressed sampling for boundary measurements in three- dimensional electrical impedance tomography, Physiol. Meas., 34, 1133-1150, (2013)
[8] Kim, M. C.; Kim, S.; Kim, K. Y.; Lee, Y. J., Regularization methods in electrical impedance tomography technique for the two-phase flow visualization, Int. Commun. Heat Mass Transf., 28, 773-782, (2001)
[9] Tossavainen, O. P.; Vauhkonen, M.; Kolehmainen, V.; Kim, K. Y., Tracking of moving interfaces in sedimentation processes using electrical impedance tomography, Chem. Eng. Sci., 61, 7717-7729, (2006)
[10] Ijaz, U. Z.; Kim, J. H.; Khambampati, A. K.; Kim, M. C.; Kim, S.; Kim, K. Y., Concentration distribution estimation of fluid through electrical impedance tomography based on interacting multiple model scheme, Flow Meas. Instrum., 18, 47-56, (2007)
[11] Jin, B.; Maass, P., An analysis of electrical impedance tomography with applications to Tikhonov regularization, ESAIM COCV, 18, 4, 1027-1048, (2012) · Zbl 1259.49056
[12] Adler, A.; Guardo, R., Electrical impedance tomography: regularized imaging and contrast detection, IEEE Trans. Biomed. Eng., 15, 170-179, (1996)
[13] Borsic, A., Regularisation methods for imaging from electrical measurements, ph.D. thesis, (2002), Oxford Brooks university
[14] Lionheart, W. R.B., EIT reconstruction algorithms: pitfalls, challenges and recent developments, Physiol. Meas., 25, 125-142, (2004)
[15] Javaherian, A.; Movafeghi, A.; Faghihi, R., Reducing negative effects of quadratic norm regularization on image reconstruction in electrical impedance tomography, Appl. Math. Model., 37, 8, 5637-5652, (2013) · Zbl 1322.65073
[16] Santosa, F.; Symes, W. W., Linear inversion of band-limited reflection seismograms, SIAM J. Sci. Stat. Comput., 7, 4, 1307-1330, (1986) · Zbl 0602.73113
[17] Donoho, D. L., Compressed sensing, IEEE Trans. Inf. Theory, 52, 1289-1306, (2006) · Zbl 1288.94016
[18] Gehre, M.; Kluth, T.; Lipponen, A.; Jin, B.; Seppänen, A.; Kaipio, J. P.; Maass, P., Sparsity reconstruction in electrical impedance tomography: an experimental evaluation, J. Comput. Appl. Math., 236, 8, 2126-2136, (2012) · Zbl 1251.78008
[19] Jin, B.; Khan, T.; Maass, P., A reconstruction algorithm for electrical impedance tomography based on sparsity regularization, Int. J. Numer. Methods Eng., 89, 3, 337-353, (2012) · Zbl 1242.78016
[20] Javaherian, A.; Soleimani, M.; Moeller, K., A fast time-difference inverse solver for 3D EIT with application to lung imaging, Med. Biol. Eng. Comput., (2016)
[21] Javaherian, A.; Soleimani, M.; Moeller, K., Sampling of finite elements for sparse recovery in large scale 3D electrical impedance tomography, Physiol. Meas., 36, 1, 43-66, (2015)
[22] Cand‘es, E.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 2, 489-509, (2006) · Zbl 1231.94017
[23] Dobson, D. C.; Santosa, F., An image enhancement technique for electrical impedance tomography, Inverse Probl., 10, 317-334, (1994) · Zbl 0805.35149
[24] Van den Doel, K.; Ascher, U. M., Dynamic level set regularization for large distributed parameter estimation problems, (2007), University of British Columbia Vancouver · Zbl 1117.65147
[25] Van den Doel, K.; Ascher, U. M.; Leitao, A., Multiple level sets for piecewise constant surface reconstruction in highly ill-posed problems, (2009), University of British Columbia Vancouver · Zbl 1203.65087
[26] Chung, E. T.; Chan, T. F.; Tai, X. C., Electrical impedance tomography using level set representation and total variational regularization, J. Comput. Phys., 205, 357-372, (2005) · Zbl 1072.65143
[27] Soleimani, M.; Lionheart, W. R.B.; Dorn, O., Level set reconstruction of conductivity and permittivity from boundary electrical measurements using experimental data, Inverse Probl. Sci. Eng., 14, 193-210, (2006) · Zbl 1194.78011
[28] Rahmati, P.; Soleimani, M.; Pulletz, S.; Frerichs, I.; Adler, A., Level-set-based reconstruction algorithm for EIT lung images: first clinical results, Physiol. Meas., 33, 739-750, (2012)
[29] Rudin, L.; Osher, S.; Fatemi, E., Nonlinear total variation based noise removal algorithms, Physica D, 60, 259-268, (1992) · Zbl 0780.49028
[30] Acar, R.; Vogel, C. R., Analysis of bounded variation penalty methods for ill-posed problems, Inverse Probl., 10, 1217-1229, (1994) · Zbl 0809.35151
[31] Chan, T. F.; Golub, G. H.; Mulet, P., A nonlinear primal-dual method for total variation-based image restoration, SIAM J. Sci. Comput., 20, 6, 1964-1977, (1999) · Zbl 0929.68118
[32] Chan, T. F.; Zhou, H. M; Chan, R. H., A continuation method for total variation denoising problems, Proceedings of the SPIE symposium on Advanced Signal Processing: Algorithms, Architectures and Implementations, Vol 2563, (1995)
[33] Vogel, C. R.; Oman, M. E., Iterative methods for total variation denoising, SIAM J. Sci. Comput., 17, 227-238, (1996) · Zbl 0847.65083
[34] T.F. Chan and P. Mulet,Iterative Methods For Total Variation Restoration, UCLA CAM Technical Report 96-38, 1996. · Zbl 0938.65155
[35] Dobson, D. C.; Vogel, C. R., Convergence of an iterative method for total variation denoising, SIAM J. Numer. Anal., 43, 1779-1791, (1997) · Zbl 0898.65034
[36] Kolehmainen, V., Novel approaches to image reconstruction in diffusion tomography, ph.D. dissertation, (2001), Dept. Appl. Phys., Kuopio Univ. Kuopio, Finland
[37] Rondi, L.; Santosa, F., Enhanced electrical impedance tomography via the Mumford-Shah functional, ESAIM COCV, 6, 517-538, (2001) · Zbl 0989.35136
[38] Vogel, C. R., Nonsmooth regularization, (Engl, H. W.; Louis, A. K.; Rundell, W., Inverse Problems in Geophysical Applications, (1995), Philadelphia, PA SIAM) · Zbl 0857.00035
[39] Borsic, A.; Graham, B. M.; Adler, A.; Lionheart, W. R.B., In vivo impedance imaging with total variation regularization, IEEE Trans. Med. Imaging, 29, 1, 44-54, (2010)
[40] EIDORS 3.5, Electrical Impedance Tomography and Diffuse Optical Tomography Reconstruction Software, 2016.
[41] Goldfarb, D.; Yin, W., Second-order cone programming methods for total variation based image restoration, SIAM J. Sci. Comput., 27, 2, 622-645, (2005) · Zbl 1094.68108
[42] Cand‘es, E.; Tao, T., Decoding by linear programming,, IEEE Trans. Inf. Theory, 51, 12, 4203-4215, (2005) · Zbl 1264.94121
[43] Candès, E.; Tao, T., Near optimal signal recovery from random projections: universal encoding strategies, IEEE Trans. Inf. Theory, 52, 12, 5406-5425, (2006) · Zbl 1309.94033
[44] Candès, E.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 2, 489-509, (2006) · Zbl 1231.94017
[45] Bioucas-Dias, J.; Figueiredo, M., A new twist: two-step iterative thresholding algorithm for image restoration, IEEE Trans. Image Process., 16, 12, 2992-3004, (2007)
[46] Bioucas-Dias, J.; Figueiredo, M., Two-step algorithms for linear inverse problems with non-quadratic regularization, (Proceedings of the IEEE International Conference on Image Processing - ICIP2007, San Antonio, TX, USA, (2007))
[47] Chambolle, A., An algorithm for total variation minimization and applications, J. Math. Imaging Vis., 20, 89-97, (2004) · Zbl 1366.94048
[48] Becker, S.; Bobin, J.; Cand‘es, E., Nesta: A fast and accurate first-order method for sparse recovery, technical report, (2009), California Institute of Technology
[49] Nesterov, Yu., Smooth minimization of non-smooth functions, Math. Program. Ser. A, 103, 127-152, (2005) · Zbl 1079.90102
[50] Wang, Y.; Yang, J.; Yin, W.; Zhang, Y., A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imaging Sci., 1, 4, 248-272, (2008) · Zbl 1187.68665
[51] Li., C., An efficient algorithm for total variation regularization with applications to the single pixel camera and compressive sensing. master thesis, (2009), Rice University, Houston Texas
[52] http://www.caam.rice.edu/∼optimization/L1/TVAL3/.
[53] Barzilai, J.; Borwein, J. M., Two-point step size gradient methods, IMA J. Numer. Anal., 8, 141-148, (1988) · Zbl 0638.65055
[54] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 183-202, (2009) · Zbl 1175.94009
[55] Graham, B.; Adler, A., Electrode placement configuration for 3D EIT, Physiol. Meas., 28, 29-44, (2007)
[56] Bera, T. K.; Biswas, S. K.; Rajan, K.; Nagaraju, J., Improving image quality in electrical impedance tomography (EIT) using projection error propagation-based regularization (PEPR) technique: a simulation study, J. Electr. Bioimpedance, 2, 2-12, (2011)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.