GPU accelerated reconstruction of Electrical Impedance Tomography Images through Simulated Annealing

GPU accelerated reconstruction of Electrical Impedance Tomography Images through Simulated Annealing

Martins, T. C.; Kian, J. M.; Yabuki, D. K.; Tsuzki, M. S. G.

Full Article:

EIT image reconstruction may be performed by a Simulated Annealing algorithm that minimizes the differences between the superficial impedance behavior of a virtual body simulated using the Finite Element Method and real data acquired on a physical body. The evaluation of objective functions - that involve solving FEM linear systems - is responsible for the majority of the process computational cost. This work presents a strategy for implementing the Preconditioned Conjugate Gradient algorithm on a GPU in order to benefit from its massive parallel computing capacities. This strategy takes in account the specificities of the EIT reconstruction through SA. It involves heavy preprocessing to identify the computations that may be performed in parallel. Initial results show that this strategy greatly improves not only on sequential approaches, but also on other generic GPU approaches.

EIT image reconstruction may be performed by a Simulated Annealing algorithm that minimizes the differences between the superficial impedance behavior of a virtual body simulated using the Finite Element Method and real data acquired on a physical body. The evaluation of objective functions - that involve solving FEM linear systems - is responsible for the majority of the process computational cost. This work presents a strategy for implementing the Preconditioned Conjugate Gradient algorithm on a GPU in order to benefit from its massive parallel computing capacities. This strategy takes in account the specificities of the EIT reconstruction through SA. It involves heavy preprocessing to identify the computations that may be performed in parallel. Initial results show that this strategy greatly improves not only on sequential approaches, but also on other generic GPU approaches.

Palavras-chave:

DOI: 10.5151/meceng-wccm2012-18111

Referências bibliográficas

• [1] Klaus-Jürgen Bathe. Finite Element Procedures (Part 1-2). Prentice Hall, 1995. ISBN 0133014584.
• [2] M. T. Clay and T. C. Frree. Weighted regularization in electrical impedance tomography with applications to accute cerebral stroke. IEEE Transactions on Medical Imaging, 21: 629–637, 2002.
• [3] Lawrence C. Evans. Partial Differential Equations: Second Edition (Graduate Studies in Mathematics), volume 19 of Graduate Series in Mathematics. American Mathematical Society, Province, Rhode Island, 2nd edition, 2010. ISBN 0821849743.
• [4] B. M. Eyüboglu, B. H. Brown, and D. C. Barber. In vivo imaging of cardiac related impedance changes. IEEE Engineering Med. Biol. Mag., 8:39–45, 1989.
• [5] Greg N. Frederickson and Communicated David Gries. On linear-time algorithms for five-coloring planar graphs. Inform. Process. Lett, pages 219–224, 1984.
• [6] Gene H. Golub and Charles F. Van Loan. Matrix Computations. The Johns Hopkins University Press, Baltimore and London, third edition, 199.
• [7] Gaël Guennebaud, Benoît Jacob, et al. Eigen v2. http://eigen.tuxfamily.org, 2010.
• [8] C. N. L. Herrera, M. F. M. Vallejo, F. S. Moura, J. C. C. Aya, and R. G. Lima. Electrical impedance tomography algorithm using simulated annealing search method. In Proceedings of International Congress Of Mechanical Engineering, Bras´ilia, 2007. ABCM.
• [9] P. Hua, E. J. Woo, J. G. Webster, and W. J. Tompkins. Finite element modeling of electrode-sking contact impedance in electrical impedance tomography. IEEE Transactions on Biomedical Engineering, 40:335–343, 1993.
• [10] T. J. Kao, D. Isaacson, J. C. Newell, and G. J. Saulnier. A 3d reconstruction algorithm for eit using a handheld probe for breast cancer detection. Physiological Measurements, 27: S1–S11, 2006.
• [11] David B. Kirk and Wen-mei W. Hwu. Programming Massively Parallel Processors: A Hands-on Approach. Morgan Kaufmann, 2010. ISBN 0123814723.
• [12] S. Kirkpatrick, C. D. Gellat, and M. P. Vecchi. Optimization by simulated annealing. Science, 220:671–680, 1983.
• [13] T.C. Martins, E.D.L.B. Camargo, R. G. Lima, M. B. P. Amato, and M. S. G. Tsuzuki. Electrical impedance tomography reconstruction through simulated annealing with incomplete evaluation of the objective function. In Proceedings of the 33rd Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBS 11), Boston, 2011. IEEE EMBS.
• [14] Lu´is Augusto Motta Mello, C´icero Ribeiro de Lima, Marcelo Britto Passos Amato, Raul Gonzalez Lima, and Em´ilio Carlos Nelli Silva. Three-dimensional electrical impedance tomography: a topology optimization approach. IEEE transactions on biomedical engineering, 55(2 Pt 1):531–40, 2008.
• [15] G´erard Meurant. The Lanczos and Conjugate Gradient Algorithms: From Theory to Finite Precision Computations. Society for Industrial and Applied Mathematics, 2006.
• [16] Rajib Nath, Stanimire Tomov, Tingxing ”Tim” Dong, and Jack Dongarra. Optimizing symmetric dense matrix-vector multiplication on GPUs. In Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’11, pages 6:1–6:10, New York, NY, USA, 2011. ACM. ISBN 978-1-4503-0771-0.
• [17] CUDA CUBLAS Library. nVidia Corporation, August 2010.
• [18] Jonathan R Shewchuk. An Introduction to the Conjugate Gradient Method Without the Agonizing Pain. Technical report, Carnegie Mellon University, Pittsburgh, PA, USA, March 1994. URL http://www.cs.cmu.edu/˜quake-papers/ painless-conjugate-gradient.pdf.
• [19] F. C. Trigo, R. Gonzales-Lima, and M. B. P. Amato. Electrical impedance tomography using the extended kalman filter. IEEE Transactions on Biomedical Engineering, 51: 72–81, 2004.

Como citar:

Martins, T. C.; Kian, J. M.; Yabuki, D. K.; Tsuzki, M. S. G.; "GPU accelerated reconstruction of Electrical Impedance Tomography Images through Simulated Annealing", p-762-779. In: In Proceedings of the 10th World Congress on Computational Mechanics [= Blucher Mechanical Engineering Proceedings, v. 1, n. 1]. São Paulo: Blucher, 2014.
ISSN 23580828, DOI 10.5151/meceng-wccm2012-18111