UNIVERSIDADE DE LISBOA FACULDADE DE CIÊNCIAS DEPARTAMENTO DE FÍSICA Implementa¸c˜ao de Algoritmos de Reconstru¸c˜ao de Imagens de Tomoss´ıntese Utilizando Processamento Paralelo em GPU Carlos Pereira Duarte Mestrado Integrado em Engenharia Biom´edica e Biof´ısica Radia¸c˜oes em Diagn´ostico e Terapia Disserta¸c˜ao orientada por: Prof. Doutor Nuno Matela 2016 Agradecimentos A primeira pessoa a quem devo agradecer ´e claramente o meu orientador, o Professor Doutor Nuno Matela, pela sua disponibilidade e ajuda em todos os momentos deste trabalho. Mesmo quando ainda n˜ao tinha tema para a disserta¸c˜ao e precisava de ori- enta¸c˜ao, foi a sua sugest˜ao e colaborac¸˜ao que me levaram a escolher este projecto e a realizar este trabalho. De todos os professores com quem lidei ao longo do meu percurso acad´emico, nenhum apresentou tanta disponibilidade e paciˆencia para com os alunos como o professor Matela. Sem o seu contributo n˜ao me teria sido poss´ıvel escrever esta disserta¸c˜ao. Umapessoaquetamb´emfoiindispens´avel, esemaqual, estetrabalhon˜aoseriaposs´ıvel, foi o Pedro Ferreira. Ele deu in´ıcio ao projecto no qual trabalhei, e auxiliou-me em todas as etapas do seu desenvolvimento. Tamb´em pela sua disponibilidade e amizade lhe agrade¸co. Um agradecimento especial tamb´em para o professor Pedro Medeiros, da Faculdade de CiˆenciaseTecnologiasdaUniversidadeNova, pelasuadisponibilidadeeaconselhamento na vertente inform´atica e de programa¸c˜ao em GPU, que me ajudaram bastante na fase inicial do trabalho. Tenho tamb´em que agradecer aos professores e investigadores do IBEB, que me recebe- ram durante este est´agio, com especial agradecimento ao professor Alexandre Andrade, que me auxiliou em diversas situa¸c˜oes e me incentivou a n˜ao desistir do curso de Enge- nharia Biom´edica e a terminar esta disserta¸c˜ao. Aqui tamb´em deixo um agradecimento a todos os professores da Faculdade de Ciˆencias que me ajudaram ao longo de todo o curso, e que me permitiram adquirir os conhecimentos e as bases necess´arias a realizar este trabalho. Gostaria tamb´em de agradecer `a minha fam´ılia, pelo apoio e dedica¸c˜ao que sempre demonstraram. Aos meus colegas e amigos, que me acompanharam nos u´ltimos anos e comquempartilheimuitosmomentosdetrabalhoeestudomastamb´emdedescontrac¸c˜ao e divers˜ao. Finalmente devo agradecer `a minha namorada, a pessoa mais importante na minha vida, que tem feito parte do meu percurso acad´emico desde o in´ıcio e sem a qual n˜ao teria conseguido terminar este trabalho. i Resumo O cancro da mama ´e o tipo de cancro com maior incidˆencia no g´enero feminino, sendo consideradoumdosmaioresemaisimportantesproblemasdesau´depu´blica`aescalaglo- bal. Amamografia´eat´ecnicadeimagemm´edicareferˆenciaparaorastreioediagn´ostico do cancro da mama, no entanto tem associada algumas limitac¸˜oes bem conhecidas: ele- vada taxa de falsos-negativos (at´e 66% em mulheres sintom´aticas) e falsos-positivos (at´e 60%). Estes dados est˜ao sobretudo relacionados com o efeito da sobreposic¸˜ao de tecidos na imagem e tˆem vindo a gerar grande controv´ersia na comunidade m´edica e cient´ıfica, no que diz respeito ao uso da mamografia como t´ecnica de rastreio, principalmente em mulheres mais jovens (< 50 anos). A DBT (Digital Breast Tomosynthesis) ´e uma t´ecnica radiol´ogica tridimensional que produz uma pilha de imagens paralelas que representam as v´arias profundidades do te- cido mam´ario, reduzindo assim o efeito de sobreposi¸c˜ao. Existe actualmente evidˆencia da redu¸c˜ao das taxas de falsos negativos e de falsos positivos associados `a utilizac¸˜ao da DBT como t´ecnica de rastreio, quando comparadas a`s da mamografia digital (FFDM - Full-Field Digital Mammography), sobretudo em mulheres com tecido mam´ario mais denso. As imagens s˜ao reconstru´ıdas a partir de projec¸c˜oes bidimensionais recorrendo a algoritmos computacionais. Estes algoritmos tˆem um papel fundamental no processo de reconstruc¸˜ao, sobretudo em contexto cl´ınico, uma vez que h´a a necessidade de im- plementar um processo que seja simultaneamente preciso e r´apido. Actualmente os algoritmos mais utilizados para reconstruir imagens DBT em ambiente cl´ınico s˜ao os anal´ıticos, por apresentarem rapidez e simplicidade de execu¸c˜ao. Os algoritmos itera- tivos tˆem, no entanto, demonstrado produzir imagens de melhor qualidade. O seu uso cl´ınico ´e actualmente rejeitado devido ao seu elevado tempo de reconstruc¸˜ao e exigˆencia computacional. As capacidades computacionais das unidades de processamento gr´afico (GPU - Graphi- cal Processing Units), nomeadamente a capacidade de c´alculo paralelo intensivo, foram j´a utilizadas por v´arios grupos de investiga¸c˜ao para a optimizac¸˜ao destes algoritmos iterativos. Um destes estudos foi desenvolvido no Instituto de Biof´ısica e Engenharia Biom´edica (IBEB), na Faculdade de Ciˆencias da Universidade de Lisboa, e consiste na implementa¸c˜ao heterog´enea (CPU+GPU) do processo de reconstru¸c˜ao de imagens DBT com algoritmos iterativos. Na GPU ´e executada um dos blocos mais exigentes de todo o algoritmo (o c´alculo da matriz de sistema), por interm´edio da linguagem de programa¸c˜ao CUDA (Compute Unified Device Architecture). Esta implementa¸c˜ao apre- senta, no entanto, algumas falhas, que se reflectem em ligeiras alterac¸˜oes nas imagens, quando comparadas com as imagens reconstru´ıdas pelo processo puramente sequencial iii (CPU). O trabalho realizado na presente dissertac¸˜ao visa a correcc¸˜ao destas falhas, de modo a eliminar as diferen¸cas observadas nas imagens reconstru´ıdas, e a aplicac¸˜ao da abordagem heterog´enea a outros blocos do algoritmo, de forma a optimizar ainda mais o processo de reconstruc¸˜ao. Palavras-chave: Tomoss´ıntese, Algoritmos Iterativos de Reconstru¸c˜ao, Computa¸c˜ao em GPU, CUDA. iv Abstract Breastcanceristhemostprevalenttypeofcancerinwomen,consideredoneofthelargest and most relevant public health problems worldwide. Mammography is the state-of-the- artmedicalimagingtechniqueforscreeninganddiagnosisofbreastcancer, buthassome limitations: high rates of both false-positive and false-negative (up to 66 % and up to 60 %, respectively). This is mainly a result of the overlapping-tissue effect, a fact that has been generating great controversy in the medical-scientific community regarding the use of mammography as a screening technique, especially in younger women (< 50 years). DBT (Digital Breast Tomosynthesis) is a three-dimensional x-ray technique that produ- ces a parallel stack of images representing various depths of the breast volume, thereby reducing the overlapping effect. This technique has shown a reduction in false-negative andfalse-positiverates,whencomparedwithFFMD(Full-FieldDigitalMammography), especially in dense breasts. Images are reconstructed from two-dimensional projections using computer algorithms. These algorithms have a central role in the reconstruction process, especially in clinical context, since it is desirable to implement a process both accurate and fast. Currently the most popular algorithms in clinical setting are analy- tical, because of their fast and simple execution process. However, iterative algorithms have shown to produce better quality images. The problem is they require a lot of com- putational capability and thus take more time to reconstruct, making them unattractive to clinical implementation. The computational capabilities of GPUs (Graphical Processing Units), namely inten- sive parallel computing, have been used by several research groups to optimize these iterative algorithms. One of these studies was developed at the Institute of Biophysics and Biomedical Engineering (IBEB), here at the Faculty of Sciences, and consists of heterogeneous implementation (CPU + GPU) of the DBT image reconstruction process with iterative algorithms. The GPU executes one of the heaviest blocks of the entire reconstruction process (the system matrix calculation), using CUDA (Compute Unified Device Architecture). Still, this implementation has some flaws, which are reflected in slightdifferencesbetweenthereconstructedimagesandtheoriginalones(imagesrecons- tructed by the purely sequential process). My work aims at correcting these flaws in order to eliminate the image errors. Moreover, I intend to generalize this heterogeneous approach to another algorithm blocks, in order to further optimize the reconstruction process. Keywords: Digital Breast Tomosynthesis, Iterative Reconstruction Algorithms, GPU Computing, CUDA. v ´ Indice Agradecimentos i Resumo iii Abstract v ´Indice vii Lista de Figuras ix Lista de Tabelas xi Acr´onimos xiii 1 Introdu¸c˜ao 1 1.1 Apresenta¸c˜ao da Dissertac¸˜ao . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Enquadramento/Contextualiza¸c˜ao . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Objectivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Fisiologia e Patologia da Mama 7 2.1 Anatomia e Fisiologia da Mama . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Cancro da Mama . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 Imagiologia do Cancro da Mama 13 3.1 Mamografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1.1 Princ´ıpios F´ısicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.1.2 Geometria do Equipamento . . . . . . . . . . . . . . . . . . . . . . 17 3.1.3 Cl´ınica e Dosimetria . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1.4 Detectores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 Tomoss´ıntese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2.1 Processo de Aquisic¸˜ao . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2.2 Dosimetria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2.3 Reconstru¸c˜ao de Imagens em Tomoss´ıntese . . . . . . . . . . . . . 24 3.2.3.1 Algoritmos de Reconstru¸c˜ao . . . . . . . . . . . . . . . . 28 SART . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 OS-EM e ML-EM . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2.4 C´alculo da Matriz de Sistema . . . . . . . . . . . . . . . . . . . . . 31 4 Computa¸c˜ao em GPU 37 4.1 Contextualiza¸c˜ao Hist´orica . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.2 Programa¸c˜ao em GPU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.3 CUDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.3.1 Biblioteca Thrust . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 vii 5 Metodologia 47 5.1 Sistema DBT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.2 Implementa¸c˜ao Sequencial . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.3 Implementa¸c˜ao Heterog´enea . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.4 Correc¸c˜ao da Implementac¸˜ao Heterog´enea . . . . . . . . . . . . . . . . . . 59 6 Resultados e Discuss˜ao 65 6.1 Avaliac¸˜ao das Imagens Reconstru´ıdas. . . . . . . . . . . . . . . . . . . . . 65 6.2 Avaliac¸˜ao do Tempo de Reconstru¸c˜ao . . . . . . . . . . . . . . . . . . . . 66 7 Considera¸c˜oes Finais 69 Referˆencias 73 viii