Resumen de Algoritmos Paralelos de Reconstrucción de Imágenes TAC sobre Arquitecturas Heterogéneas

Liubov Alexandrovna Flores

• Algoritmos Paralelos de Reconstrucción de Imágenes TAC sobre Arquitecturas Heterogéneas TESIS DOCTORAL Presentada por: Liubov Alexandrovna Flores Dirigida por: Prof. Vicente Vidal Gimeno Prof. Gumersindo Verdú Martín Resumen Introducción La tomografía axial computarizada (TAC) o tomografía de rayos-X es una técnica fundamental en el diagnóstico médico basado en imagen, que también tiene numerosas aplicaciones industriales. En TAC, las imágenes que corresponden a cortes interiores de un objeto, se obtienen a partir de las proyecciones tomadas por un escáner. Este procedimiento se denomina reconstrucción de imágenes tomográficas. Los avances tecnológicos y teóricos han promovido un interés continuo al desarrollo de los diferentes métodos de reconstrucción y sus implementaciones. Desde el comienzo del desarrollo de escáneres ha sido importante reducir el tiempo de escaneo, disminuir en la medida de lo posible el número de rotaciones necesario para realizar una prueba TAC, mejorar la calidad de imagen y reducir el tiempo de reconstrucción. La motivación de este trabajo es la investigación de los algoritmos de reconstrucción de imagen existentes, el diseño de nuevos algoritmos, sus eficientes implementaciones paralelas, y su adaptación a la reducción de vistas y como consecuencia a la reducción de dosis radiactiva en pacientes. Desarrollo teórico En medicina, el diagnóstico basado en imágenes TAC es fundamental para la determinación de anormalidades a través de diferentes valores de atenuación de la energía de rayos-X, las cuales, frecuentemente, son difíciles de ser distinguidas por los radiólogos. Se han desarrollado diferentes técnicas de reconstrucción de imagen. En este trabajo analizamos y comparamos métodos analíticos e iterativos para resolver de forma eficiente el problema de reconstrucción. Hoy, en la práctica, el proceso de reconstrucción de imagen se basa en algoritmos analíticos entre los cuales, el algoritmo de retroproyección filtrada 'filtered backprojection' (FBP) es el más conocido. Este algoritmo se usa para implementar la Transformada de Radon inversa que es una herramienta matemática cuya utilización principal en Ingeniería Biomédica es la reconstrucción de imágenes TAC. Desde el comienzo del desarrollo de escáneres ha sido importante reducir el tiempo de escaneo, mejorar la calidad de imagen y reducir el tiempo de reconstrucción. La tecnología de hoy ofrece potentes sistemas con varios procesadores y núcleos que posibilitan reducir el tiempo invertido en la reconstrucción de imágenes. En este trabajo se analiza el algoritmo FBP basado en la Transformada de Radon inversa y su relación con la Transformada de Fourier con el objetivo de optimizar su cálculo aprovechando al máximo los recursos del sistema. Este algoritmo se basa en proyecciones paralelas y se destaca por su simplicidad y robustez, y permite extender los resultados a una variedad de situaciones. En muchas aplicaciones el conjunto de proyecciones necesarias para la reconstrucción puede ser incompleto por razones físicas. Entonces, la única posibilidad es realizar una reconstrucción aproximada. En estas condiciones, las imágenes reconstruidas por los algoritmos analíticos en dos o tres dimensiones son de baja calidad y con muchos artefactos. Los métodos iterativos son más adecuados para la reconstrucción de imágenes cuando se dispone de un menor número de proyecciones en condiciones más ruidosas. Su uso puede ser importante para el funcionamiento en escáneres portátiles en condiciones de urgencia en cualquier lugar. Sin embargo, en la práctica, estos métodos son menos usados por su alto coste computacional. En este trabajo presentamos el estudio y diversas implementaciones paralelas que permiten bajar el coste computacional de tales métodos iterativos como SART, MLEM y LSQR. Los métodos iterativos se han convertido en un tópico de gran interés para muchos vendedores de sistemas de TAC clínicos por su capacidad de resolver el problema de reconstrucción con un número limitado de proyecciones. Esto proporciona la posibilidad de reducir la dosis radiactiva en los pacientes durante el proceso de adquisición de datos. Al mismo tiempo, en la reconstrucción aparecen artefactos no deseados. Para resolver el problema en forma efectiva y eficiente, hemos adaptado el método LSQR con el método de filtrado 'Soft Threshold Filtering' y el algoritmo de aceleración 'Fast Iterative Shrinkage-thresholding Algorithm' para TAC. La eficiencia y fiabilidad del método nombrado LSQR-STF-FISTA se presenta en este trabajo. Los métodos de reconstrucción de imágenes se analizan mediante la reconstrucción a partir de proyecciones simuladas y reales, comparando la calidad de imagen reconstruida con el objetivo de obtener conclusiones respecto a los métodos usados. Basándose en este estudio, concluimos que los métodos iterativos son capaces de reconstruir imágenes con el conjunto limitado de proyecciones con un bajo coste computacional. Conclusiones En esta tesis hemos analizado métodos de reconstrucción analítica e iterativa de imágenes TAC por proyecciones. El estudio, análisis de la implementación secuencial y paralela de los algoritmos de reconstrucción y los resultados obtenidos nos llevan a las siguientes conclusiones: Los algoritmos analíticos basados en la Transformada de Fourier son rápidos y permiten la reconstrucción de imágenes de buena calidad en condiciones óptimas de las proyecciones. En condiciones de ruido y en caso de un conjunto de datos incompleto, los métodos iterativos son superiores a los métodos analíticos. Los algoritmos de reconstrucción son paralelizables y permiten explotar las características de las arquitecturas modernas de sistemas como sistemas multi-cores y many-cores. La paralelización de los algoritmos permite la reducción de tiempo de reconstrucción de imágenes TAC. En sistemas multi-cores, los tiempos óptimos se consiguen al llevar a cabo el proceso de reconstrucción en forma paralela con el número de procesos iguales al número de núcleos o procesadores del sistema. En métodos iterativos, la matriz del sistema contiene la información de la imagen a reconstruir y la forma de generar la matriz afecta a la calidad de la imagen. La estructura de bloques simétricos en la matriz de sistema permite generar y almacenar 1/8 parte de toda la matriz y reutilizarla en el proceso de reconstrucción extendiéndola al rango completo de 0-360 grados. De esta forma, se puede reducir la utilización de memoria del sistema y el tiempo de reconstrucción. El conjunto de datos en el proceso de reconstrucción es muy grande, especialmente en 3D y 4D. Por esta razón y porque las operaciones básicas de computo son de tipo píxel/vóxel, las arquitecturas modernas masivamente paralelas, basadas en GPUs, son las más apropiadas. Comparando los métodos iterativos clásico SART y LSQR, se observa que el número de operaciones en el proceso de reconstrucción de una imagen es del mismo orden. Sin embargo, SART requiere muchas más iteraciones para la reconstrucción comparado con LSQR. En consecuencia, el tiempo de reconstrucción se eleva. El método iterativo LSQR es capaz de reconstruir la imagen con pocas iteraciones y tiene un costo muy bajo. En esta tesis se propone el método LSQR combinado con la técnica de filtración STF y aceleración FISTA para la reconstrucción de imágenes. Se muestra que la combinación óptima de estos métodos permite preservar la estructura del objeto y acelerar el proceso de reconstrucción. El método LSQR-STF-FISTA es eficaz en resolver el problema de reconstrucción con un menor número de proyecciones. La reducción de vistas en el proceso de adquisición de datos es importante en TAC porque permite reducir la dosis de radiación a pacientes. La capacidad de los métodos iterativos de reconstruir una imagen con un conjunto incompleto de proyecciones puede ser utilizada en la práctica en escáneres portátiles que pueden ser usadas en condiciones extremas. Bibliografía Stanley R. Deans. The Radon Transform and Some of Its Applications. Dover Publications, INC. Mineola, New York, 2007. Will A. Kalender. Computed Tomography. Publicis Corporate Publishing, Erlangen, Germany, 2005. Rafael C. Gonzáles, Richard E. Woods. Digital Image processing. Prentice Hall, 3rd edition, 2008. A. C. Kak and Malcolm Slaney, Principles of Computerized Tomographic Imaging, Society of Industrial and Applied Mathematics. chapter 07, 2001. Herman, G. T. Fundamentals of computerized tomography: Image reconstruction from projections. 2nd ed. Springer, 2009. Gordon, R; Bender, R; Herman, GT. Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and x-ray photography. Journal of Theoretical Biology. Vol. 29(3):471-81, 1970. Geman, S., McClure, D. E. Statistical methods for tomographic image reconstruction. Bull Int Stat Inst. Vol. 52(4):521, 1987. De Man, B. Iterative Reconstruction for Reduction of Metal Artifacts in Computed Tomography. ISBN 90-5682-300-0, 2001. Langan, D.; Claus, B.; Edic, P.; Vaillant, R.; De Man, B.; Basu, S.; Iatrou, M. An iterative algorithm for soft tissue reconstruction from truncated flat panel projections. Medical Imaging: Physics of Medical Imaging. Edited by Flynn, Michael J.; Hsieh, Jiang. Proceedings of the SPIE. Vol. 6142: 749-757, 2006. K. Lange and R. Carson. EM reconstruction algorihtms for emission and transmission tomography. J. Comput. Assist. Tomogr. Vol. 8:306-316, 1984. G. Wang, H.Yu, and B. De Man. An outlook on X-ray CT research and development. Medical Physics. Vol. 35(3):1051-1064, 2008. B. M Crawford and G. T Herman. Low-dose, large-angled cone-beam helical CT data reconstruction using algebraic reconstruction techniques. Image and Vision Comp. Vol. 25:78-94, 2007. J. Nuyts, B. De Man, P. Dupont, M. Defrise, P. Suetens, and L. Mortelmans. Iterative reconstruction for helical CT: A simulation study. Phys. Med. Biol. Vol. 43:729-737, 1998. G. Wang, M. W. Vannier, and P. C. Cheng. Iterative X-ray cone beam tomography for metal artifact reduction and local region reconstruction. Microscopy and Microanalysis. Vol. 5(1):58-65, 1999. A. H. Andersen. Algebraic reconstruction in CT from limited views. IEEE Trans. Med. Imaging. Vol. 8(1), 1989. G. Wang, D. Snyder, J. O'Sullivan, and M. Vannier. Iterative deblurring for CT metal artifact reduction. IEEE. Trans. Med. Imaging. Vol. 15(5):657-663, 1996. N. Sinha and J. T. W. Yeow. Carbon nanotubes for biomedical applications. IEEE Trans. Nano. Vol. 4(2):180-196, 2005. J. Ni, X. Li, T. He, and G. Wang. Review of parallel computing techniques for computed tomography image reconstruction. Current Med. Imaging Reviews. Vol. 2(4):405-414, 2006. Stone, S., Haldar, J., Tsao, S., Hwu, W., Sutton, B., & Liang, Z. Accelerating advanced MRI reconstructions on GPUs. Journal of Parallel and Distributed Computing. Vol. 68(10): 1307-1318, 2008. Johnson, C., & Sofer, A. A data-parallel algorithm for iterative tomographic image reconstruction. Frontiers of Massively Parallel Computation. pp 126-137, 1999. Pratx, G., Chinn, G., Olcott, P., & Levin, C. Fast, Accurate and Shift-Varying Line projections for Iterative Reconstruction Using the GPU. IEEE Transactions on Medical Imaging. Vol 28(3): 435-445, 2009. Jang, B., Kaeli, D., Do, S., & Pien, H. Multi GPU implementation of iterative tomographic reconstruction algorithms. Biomedical Imaging: From Nano to Macro. pp 185-188, 2009. Flores, Liubov A.; Vicent Vidal; Mayo Nogueira, Patricia; Ródenas Escribá,Francisco De Asís; Verdú Martín, Gumersindo Jesús; Iterative reconstruction of CT images with PETSc. The 4th International Conference on BioMedical Engineering and Informatics. The 4th International Congress on Image and Signal Processing. (ISSN 978-1-4244-9350-0). pp 343-346, 2011. D. J. Brenner, E. J. Hall, and D. Phil. Computed tomography: An increasing source of radiation exposure. N. Engl. J. of Med. Vol. 357:2277-84, 2007. E. Stephen, P. F. Butler, K. E. Applegate, S. B. Birnbaum, L. F. Brateman, J. M. Hevezi, F. A. Mettler, R. L. Morin, M. J. Pentecost, G. G. Smith, K. J. Strauss, and R. K. Zeman. American college of radiology white paper on radiation dose in medicine. J. Am. Coll Radiol . Vol. 4:272-284, 2007. Jersey Chen, Andrew J. Einstein, Reza Fazel, Harlan M. Krumholz,Yongfei Wang, Joseph S. Ross, Henry H. Ting,Nilay D. Shah, y Brahmajee K. Nallamothu. Cumulative Exposure to Ionizing Radiation from Diagnostic and Therapeutic Cardiac Imaging Procedures: A Population-Based Analysis. J Am Coll Cardiol. Vol. 56(9): 702-74, 2010. A.B. de Gonzalez and S. Darby. Risk of cancer from diagnostic X-rays: estimates for the UK and 14 other countries. The Lancet, Vol. 363(9406): 345-351, 2004. D. J. Brenner and E. J. Hall. Current concepts:computed tomography-an increasing source of radiation exposure. The New England Journal of Medicine. Vol. 357(22):2277-2284, 2007. O. W. Linton and F. A. Mettler Jr. National conference on dose reduction in CT, with an emphasis on pediatric patients. American Journal of Roentgenology. Vol. 181, no. 2, pp. 321-329, 2003. Gitta Kutyniok. Theory and Applications of Compressed Sensing. GAMM-Mitteilungen, 10 July 2013. G.H. Chen, J. Tang, and S. Leng. Prior image constrained compressed sensing (PICCS): a method to accurately reconstruct dynamic CT images from highly undersampled projection data sets. Medical Physics. Vol. 35(2): 660-663, 2008. H. Yu and G. Wang. Compressed sensing based interior tomography. Physics in Medicine and Biology. Vol. 54(9): 2791-2805, 2009. L. I. Rudin, S. Osher, and E. Fatemi. Nonlinear total variation based noise removal algorithms. Physica D. Vol. 60(4): 259-268, 1992. G. T. Herman and R. Davidi. Image reconstruction from a small number of projections. Inverse Problems. Vol. 24(4), Article ID 045011, 17 pages, 2008. G. Wang and M. Jiang. Ordered-subset simultaneous algebraic reconstruction techniques (OS-SART). Journal of X-Ray Science and Technology. Vol. 12(3): 169-177, 2004. Liubov Flores, Vicente Vidal, Estíbaliz Parcero, and Gumersindo Verdú. Aplication of LSQR and Thresholding for CT Imaging with Few Projections. PLOSONE, in revision. M.J. Flynn. Some computer organisations and their effectiveness, IEEE Trans. On Computers, Vol. c-21(9): 948-960, 1972. Aad J. van der Steen. Overview of recent supercomputers. HPC Research, August 2008. http://www.nvidia.com/content/PDF/fermiwhite papers/NVIDIA Fermi Compute Architecture Whitepaper.pdf L.Dagum, R.Menon. OpenMP: an industry standard API for shared-memory programming. Computational Science & Engineering, IEEE. R. L. Siddon. Fast calculation of the exact radiological path for a threedimensional CT array. Med Phys. Vol. 12: 252-255, 1986. Cibeles Mora Mora. Métodos de reconstrucción volumétrica algebraica de imágenes tomográficas. Tesis PhD, 2008. Andersen, A. & Kak, A. Simultaneous algebraic reconstruction technique (SART): A superior implementation of the ART algorithm. Ultrasonic Imaging. Vol. 6: p. 81-94, 1986. L.A. Shepp and Y. Vardi. Maximum Likelihood Reconstruction for Emission Tomography. IEEE Transactions on Medical Imaging. Vol. 1(2), 1982. C.C. Paige and M.A. Saunders. The Algorithm LSQR:Sparse linear equations and least square problems. ACM Trans. Math. Soft.Vol. 8(2), 1982. G.H. Golub and W. Kahan. Calculating the singular values and pseudoinverse of a matrix. SIAM J. Numer. Anal.Vol. 2: 205-224, 1965. Beister, M., Kolditz, & Kalender, W. Iterative reconstruction methods in X-ray CT. Physica Medica-European Journal of Medical Physics. Vol. 28: 94-108, 2012. Zhao, X., Hu, J., & Yang, Y. GPU based iterative cone-beam CT reconstruction using empty space skipping technique. Journal of X-Ray science and Technology. Vol. 21: 53-69, 2013. Flores, L., Vidal, V., Mayo, P., Rodenas, F., & Verdú, G. CT image reconstruction based on GPUs. Procedia Computer Science. Vol. 18: 1412-1420, 2013. Wang G.,Yu H. & De Man B. An outlook on X-ray CT research and development. Medical Physics. Vol. 35(3): 1051-1064, 2008. Donoho, D. Compressed sensing. IEEE Transactions on Information Theory. Vol. 52: 1289-1306, 2006. Candès, E., Romberg, J., & Tao, T. Stable signal recovery from incomplete and inaccurate measurements. Communication on Pure and Applied Mathematics. Vol. 59: 1207-1223, 2006. Yu, H., & Wang, G. A soft-threshold filtering approach for reconstruction from a limited number of projections. Physics in Medicine and Biology. vol. 55: 3905-3916, 2010. Yu, W., & Zeng, L. A novel weighted total difference based image reconstruction algorithm for few-view computed tomography. PLos ONE. Vol. 9(10): 1-10, 2014.