The Vision Lab
Real-time iteratieve tomografische reconstructie op basis van GPU computing
Projectomschrijving voor aanvraag “IWT Specialisatiebeurs eerste termijn”, ingediend door Sander van der Maar
14 september 2007
Promotor Co-promotor
B
Prof. Dr. Jan Sijbers Dr. Kees Joost Batenburg
Sander van der Maar Campus Drie Eiken D.N. Universiteitsplein 1 B-2610 Wilrijk T +32 (0)3 820 24 49 v +32 (0)3 820 22 45 k
[email protected] m http://www.ua.ac.be/main.aspx?c=sander.vandermaar
Inhoudsopgave 1 Probleemstelling
1
2 Doelstellingen
2
3 Projectbeschrijving 3 3 3.1 Situering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Introductie tot GPU computing . . . . . . . . . . . . . . . . . . . . . . . . . 3 3.3 Introductie van iteratieve reconstructie algoritmen . . . . . . . . . . . . . . . 5 3.4 Taakbeschrijving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.4.1 Taak 1: Verkorten van de scan- en rekentijd. . . . . . . . . . . . . . . 7 3.4.2 Taak 2: Ontwikkeling van iteratieve algoritmen voor zeer grote datasets. 8 3.4.3 Taak 3: Ontwikkelen van een code-generator voor GPU-gebaseerde 9 iteratieve reconstructie algoritmen. . . . . . . . . . . . . . . . . . . . 4 Planning
10
5 Toepassingsmogelijkheden
11
Bibliography
12
1
Probleemstelling
Transmissie tomografie is nauwelijks meer weg te denken in medische en industriële toepassingen. Bij deze techniek kunnen beelden worden gereconstrueerd op basis van een groot aantal projecties, opgenomen vanuit verschillende hoeken. Momenteel worden algoritmen als filtered back-projection en het Feldkamp-algoritme [6] standaard gebruikt. Hoewel ze computationeel efficiënt geïmplementeerd kunnen worden, hebben deze algoritmen enkele belangrijke nadelen. Vooreerst zijn zeer veel projecties vereist om een nauwkeurige reconstructie te berekenen. Daarnaast zijn dergelijke algoritmen zeer gevoelig voor ruis en is het niet mogelijk om voorkennis over het object tijdens het reconstrueren te gebruiken [?]. Dit project richt zich op iteratieve algoritmen voor tomografie, waarbij het beeld in stappen wordt gereconstrueerd. Dergelijke algoritmen hebben minder te kampen met de vermelde nadelen. Anderzijds dienen de volgende problemen te worden aangepakt om het gebruik van iteratieve algoritmen in de praktijk haalbaar te maken: Lange scantijd. Het grote aantal projecties dat momenteel vereist is om een beeld van acceptabele kwaliteit te reconstrueren heeft rechtstreeks tot gevolg dat de opnametijd vaak aanzienlijk is. Voor tal van toepassingen is het van belang de scantijd zo klein mogelijk te houden. Bij medische toepassingen resulteert een kleine opnametijd in een verhoging van het patiëntcomfort en laat het de studie van dynamische processen toe. Wegens de relatie tussen op opnametijd en het aantal opgenomen projecties leidt een reductie van dit laatste eveneens tot een vermindering van de totale X-stralendosis. Ook in de industrie, waar tomografie wordt gebruikt voor kwaliteitscontrole, is een korte scantijd belangrijk, omdat er dan meer objecten kunnen worden gecontroleerd in dezelfde tijd. Lange rekentijd. Hoewel het gebruik van iteratieve reconstructie algoritmen leidt tot een grotere nauwkeurigheid van reconstructies, zijn deze algoritmen langzamer dan nietiteratieve methoden. Voor het gebruik van iteratieve algoritmen in praktische toepassingen, is een korte rekentijd essentieel. In de industrie wil men graag zo snel mogelijk kunnen reageren op productiefouten. Ook bij medische toepassingen is een korte rekentijd belangrijk. De arts wil immers zo snel mogelijk zijn diagnose kunnen stellen. Grote hoeveelheid benodigd geheugen. Wanneer beelden met een zeer hoge spatiale resolutie worden gereconstrueerd, is de benodigde geheugengrootte gigantisch: veel te groot voor het direct aanspreekbare geheugen. In de praktijk wordt vaak van cone-beam tomografie toegepast, waarbij een kegelvormige X-stralenbundel wordt gebruikt voor het opnemen van de projectiebeelden. Vooral bij deze vorm van tomografie vormt het beschikbare werkgeheugen een belangrijke beperking, aangezien het niet mogelijk is de 3D reconstructietaak op te splitsen in het reconstrueren van een aantal twee dimensionale snedes. Het ontwikkelen van nieuwe iteratieve reconstructie algoritmen neemt veel tijd in beslag en is foutgevoelig. Hoewel er een grote verscheidenheid is aan iteratieve reconstructie algoritmen, maken de meeste van deze algoritmen gebruik van dezelfde basisoperaties. Toch kost het vaak veel tijd om deze methoden te implementeren, zeker als daarbij gebruik wordt gemaakt van nieuwe hardware. Ook het veranderen van een huidige implementatie is erg tijdrovend tijd en foutgevoelig.
–1–
2
Doelstellingen
Het hoofddoel van dit project is het ontwikkelen van iteratieve, tomografische algoritmen die minder projecties en minder rekentijd vereisen. Het reconstrueren van 3D volumes met behulp van iteratieve algoritmen vergt zeer veel rekenkracht. Om de reconstructietijd te verkorten zal gebruik worden gemaakt van grafische hardware. De processor van een grafische kaart, de Graphical Processing Unit (GPU), bestaat uit veel kleine rekeneenheden. Deze eenheden zijn geoptimaliseerd voor de operaties die worden gebruikt tijdens het weergeven van een beeldframe. De basisoperaties van een iteratief tomografisch algoritme zijn heel geschikt om op de GPU te worden uitgevoerd. Doordat een groot aantal berekeningen parallel kan worden uitgevoerd, kan er veel snelheidswinst worden behaald. Hierdoor komt zelfs real-time tomografie binnen handbereik. De mate van succes zal gemeten kunnen worden a.h.v. de snelheidswinst en de kwaliteit van de reconstructie. De volgende doelstellingen zullen centraal staan: Verkorten van de scan- en rekentijd. Door gebruik te maken van iteratieve, tomografische algoritmen zal het aantal benodigde projecties worden verminderd. Daarmee wordt niet alleen de stralingsdosis teruggebracht, maar ook in veel gevallen de scantijd. Discrete tomografische algoritmen zijn ideaal voor het reconstrueren van objecten waarvan bekend is dat ze uit een zeer beperkt aantal verschillende materialen opgebouwd zijn. Totale Variatie Minimalisatie lijdt eveneens tot goede reconstructies bij problemen waarbij bekend is dat het object uit grote, relatief egale vlakken bestaat, zelfs wanneer slechts een klein aantal projecties wordt gebruikt. In beide gevallen vormt de benodigde rekentijd een probleem. Door het gebruik van GPUs zal deze verminderd worden, zodat de reconstructietijd beduidend korter zal zijn dan voor traditionele reconstructie algoritmen. Hierdoor lijkt zelfs real-time tomografie mogelijk te zijn. Ontwikkeling van iteratieve algoritmen voor zeer grote datasets. Er zullen algoritmen worden ontwikkeld waarbij rekening wordt gehouden met het feit dat bij GPUs niet alle data zich in het snelste geheugen (cache) bevindt. Een deel van de benodigde data zal vanaf andere locaties geladen moeten worden (videogeheugen, werkgeheugen, harde schijf). Hierbij zal worden getracht communicatie met langzaam geheugen zoveel mogelijk te vermijden. De nieuwe algoritmen moeten geschikt zijn voor het reconstrueren van volumes die uit meer dan 109 voxels bestaan. Ontwikkelen van een code-generator voor GPU-gebaseerde iteratieve reconstructie algoritmen. Bij veel iteratieve reconstructie algoritmen voldoet de iteratiestap aan een sjabloon: de eerste stap bestaat uit het berekenen van de projectie van het huidige beeld. Vervolgens wordt het verschil berekend tussen de berekende en gemeten projecties. Als laatste wordt het huidige beeld aangepast op basis van dit verschil. In dit project zal een code-skelet geschreven worden waarmee op eenvoudige wijze iteratieve algoritmen kunnen worden geïmplementeerd. Er zal een code-generator worden ontwikkeld om het implementatieproces op de GPU te automatiseren. Zelfs een relatief onervaren programmeur zal dan snel nieuwe reconstructie algoritmen kunnen ontwikkelen, waarin hij slechts de routines hoeft aan te passen waar zijn algoritme afwijkt van het standaardmodel.
–2–
3
Projectbeschrijving
3.1
Situering
Dit project zal worden uigevoerd binnen de onderzoeksgroep Visielab van de Universiteit Antwerpen (UA). Hierbij zal worden samengewerkt met de high-perfomance computing groep van Dr. Ir. Bart Kienhuis van het Leiden Institute for Advanced Computer Science (LIACS), SkyScan (producent van micro-CT scanners) en de afdeling radiologie van het Universitair Ziekenhuis Antwerpen (UZA). • In het Visielab wordt onderzoek gedaan naar beeldverwerking, reconstructie en visualisatie. Er is veel expertise aanwezig op het gebied van tomografische algoritmen. Met de recente aanwerving van Joost Batenburg (in 2006 verkozen tot “onderzoeker van het jaar” door de faculteit Wiskunde en Natuurwetenschappen van de universiteit Leiden) en enkele doctorandi, is er een deelgroep ontstaan met als doel het ontwikkelen van nieuwe beeldverwerkings- en reconstructie algoritmen voor tomografie. • Bart Kienhuis van het LIACS, de informatica-faculteit van de Universiteit Leiden, werkt al jaren actief samen met Joost Batenburg (co-promotor van dit project). Binnen deze samenwerking is ook het afstudeerproject van de aanvrager (het implementeren van SART op de IBM Cell) uitgevoerd. De groep van Dr. Kienhuis heeft veel ervaring met het programmeren van nieuwe hardware. • SkyScan produceert hoge resolutie µCT-scanners en is marktleider in hun domein. Dit bedrijf is ontstaan als spin-off van het Visielab. Er bestaat nog steeds een actieve samenwerking tussen SkyScan en het Visielab op diverse beeldverwerkingsgebieden. SkyScan heeft veel expertise op het gebied van cone-beam reconstructie, wat een zeer grote meerwaarde kan bieden voor dit project. De door hen gebruikte scanners bezitten een enorme resolutie (tot wel 8000 bij 8000 pixels) en ze zijn daarom zeer gebaat bij de ontwikkeling van een snel iteratief tomografisch algoritme. • Via de samenwerking met het UZA kunnen nieuwe technieken en ontwikkelingen getoetst worden met data uit medische toepassingen.
3.2
Introductie tot GPU computing
Bij het uitvoeren van moderne 3D computerspellen moet een groot aantal keer per seconde een 3D model worden weergegeven op het scherm. Daarbij moeten de punten (“vertices”) die het model omschrijven vanuit de 3D wereld op het 2D scherm geprojecteerd worden. Hiervoor zijn operaties nodig als vector-met-matrix vermenigvuldiging en het schalen van afbeeldingen. Tot ongeveer 1998 werden al deze operaties uitgevoerd op de hoofdprocessor (CPU). Vanaf 1998 werden nieuwe computers vaak uitgerust met grafische kaarten die deze berekeningen overnamen. De processor die verantwoordelijk is voor de grafische berekeningen op deze kaarten wordt “GPU” genoemd: Graphical Processing Unit. Het verplaatsen van de berekeningen van de hoofdprocessor naar gespecialiseerde hardware ontlastte de CPU, zodat deze gebruikt kon worden voor andere taken. Voor het snel uitvoeren van 3D visualisatie taken maakt de GPU gebruik van grootschalig parallelisme. De GPU bevat een –3–
groot aantal (tientallen tot meer dan honderd) relatief simpele parallele processoren, die gelijktijdig kunnen werken. Vanaf 2003 werd het mogelijk voor programmeurs om de berekeningen te wijzigen die door de grafische kaart worden uitgevoerd. De compacte stukjes programmacode die men door de GPU kan laten uitvoeren worden “shaders” genoemd. Er zijn twee soorten shaders: vertex-shaders en pixel-shaders. De eerste worden gebruikt om de posities van de vertices aan te passen (bijvoorbeeld bij een wapperende vlag) en de laatste om de kleur van een pixel te veranderen (bijvoorbeeld bij het berekenen van reflecties). Grafische kaarten hadden rond 2003 veel minder vertex-shaders dan pixelshaders. Vertex shaders zijn relatief complex: ze hebben random access tot het video geheugen, terwijl pixel-shaders slechts een klein gedeelte van het videogeheugen kunnen lezen en slechts naar een vaste locatie kunnen schrijven. Hoewel grafische kaarten oorspronkelijk ontwikkeld zijn voor visualisatie-toepassingen (met name 3D games), begonnen programmeurs deze kaarten geleidelijk aan ook te gebruiken voor andere rekenproblemen, zoals grootschalige simulaties. Simulaties van vloeistofstromingen, deeltjessystemen en van aandelenkoersen bleken zeer geschikt te zijn om op de GPU te worden uitgevoerd, vanwege het parallele karakter van de berekeningen. Daarnaast blijkt ook tomografie zeer goed te kunnen worden opgesplitst in simpele, parallele berekeningen die goed werken op de kleine shader-modules. Omdat de kaarten hier eigenlijk niet voor bedoeld zijn, moesten de berekeningen worden “vermomd” als grafische operaties. Dit betekende dat er onderscheid moest worden gemaakt tussen de stappen die door de vertex shaders worden gedaan en welke door de pixel shaders. Hierdoor nam het implementeren van niet-grafische algoritmen veel tijd in beslag. In de zomer van 2006 lanceerde Microsoft in samenwerking met GPU fabrikanten een nieuwe shader-architectuur: Shader Model 4.0 [3]. Dit model legt vast welke functionaliteit moet worden geïmplementeerd door een videokaart. Binnen het raamwerk van deze nieuwe standaard bestaat er geen verschil meer tussen vertex- en pixel-shaders: er is sprake van een unified shader model. Alle shaderprogramma’s hebben lees/schrijf toegang tot het volledige videogeheugen. Daardoor werd de GPU nog beter bruikbaar voor niet-grafische problemen. Ook tomografische reconstructie algoritmen kunnen volgens dit model nog beter op de GPU worden uitgevoerd, omdat nu alle processing units het volledige videogeheugen aan kunnen spreken. Een volgende stap om grafische kaarten om te vormen naar volwaardige parallele highperformance computers werd genomen in juni 2007: nVidia bracht het CUDA platform uit (“Computer Unified Device Architecture”) [5]. Sindsdien hoeven de berekeningen niet langer meer omgeschreven te worden naar grafische operaties (zoals het aanspreken van de hardware via Direct3D alsof het een computerspel zou zijn). Via CUDA kan de hardware direct worden aangesproken vanuit een C-programma. De rekenkracht van de GPUs is de laatste jaren enorm toegenomen, zelfs in vergelijking met de eveneens sterke toename van de snelheid van CPUs; zie Figuur 1. Dit is een gevolg van het feit dat het toegenomen aantal transistoren op GPUs wordt gebruikt voor het verhogen van het aantal rekeneenheden. Ook bij CPUs is deze trend inmiddels zichtbaar, maar het aantal kernen is bij hier nog steeds beperkt (vier of minder). In de literatuur zijn reeds diverse voorbeelden bekend van succesvolle implementaties van reconstructie algoritmen op de GPU [?, 1], waarbij versnellingen van 11 keer worden bereikt ten opzichte van CPU-implementaties. Deze versnelling werd gehaald op hardware waar nog een onderscheid wordt gemaakt tussen vertex-shaders en pixel-shaders. Een nog grotere verbetering valt te verwachten op nieuwere hardware waarbij alle processing units –4–
Figuur 1: Vergelijking tussen rekenkracht van GPUs en CPUs als volwaardige rekenelementen kunnen werken.
3.3
Introductie van iteratieve reconstructie algoritmen
Er bestaan veel verschillende iteratieve reconstructie algoritmen (bv. ART, SART, SIRT, ML-EM, DART). Toch hebben deze algoritmen veel overeenkomsten. Bij de meeste iteratieve algoritmen voor tomografie bestaat een iteratiestap uit drie basisoperaties: projectie, berekening van het verschil tussen deze projectie en de gemeten projectiedata en terugprojectie van dit verschil. Bij de projectiestap worden de projecties van de huidige reconstructie in één of meer richtingen berekend. De projectie van een beeld kan op twee verschillende manieren worden berekend. Een pixel driven algoritme itereert over de pixels in het te reconstrueren beeld en telt de projecties van alle pixels bij elkaar op, om op die manier de projecties te vormen. Een ray driven algoritme itereert over de detectorelementen. Voor elk detectorelement wordt een gewogen som berekend van alle pixels die op de bijbehorende lijn liggen. Na het berekenen van de projectie wordt het verschil berekend tussen de berekende en de gemeten projectie. Vervolgens wordt dit verschil teruggeprojecteerd op het beeld. Hierbij wordt voor elk detectorelement het berekende projectieverschil verdeeld over de pixels die op de bijbehorende lijn liggen. Als voorbeeld zullen we hier het SART algoritme (Simultaneous Algebraic Reconstruction Technique) nader bespreken. Het reconstructieprobleem wordt hier gemodeleerd als een groot stelsel lineaire vergelijkingen: Wx = p
(1)
Stel dat het te reconstrueren beeld uit n × n pixels bestaat en dat in totaal langs m lijnen de projectie wordt gemeten. De matrix W = (wij ) heeft dan n2 kolommen en m rijen. De waarde van wij komt overeen met de lengte van straal i binnen pixel j, zie Figuur 2. De structuur van de matrix W is afhankelijk van de opname-geometrie van de scanner: “parallel beam” (een parallele stralenbundel), “fan beam” (een divergente bundel in één vlak) of “cone beam” (een driedimensionale kegelvormige bundel). De vector x heeft n2 elementen die overeen komen met de pixels van het te reconstrueren beeld. De vector p heeft m
–5–
Figuur 2: De waarde van element van W komt overeen met de lengte van de doorsnede tussen een straal en een pixel elementen die overeen komen met de gemeten projectiewaarden. Vanwege de grootte van matrix W is expliciete inversie niet mogelijk. De matrix W is opgebouwd uit blokken die overeenkomen met de verschillende projectiehoeken. Het SART algoritme werkt als volgt. Bij elke iteratie wordt x geprojecteerd, door te vermenigvuldigen met een deelmatrix W0 van de matrix W die overeenkomt met één van de projectiehoeken: q = W0 x
(2)
Zij p0 een deelvector van p, die overeenkomt met de betreffende projectiehoek. De projectiefout e wordt als volgt berekend: e = p0 − q
(3)
Door de projectiefout nu “terug te projecteren” op de pixels van de reconstructie, zal de projectiefout voor de gekozen projectie nul worden. Laat βi de totale lengte van lijn i zijn. Dan worden de pixels worden als volgt bijgewerkt: xt+1 = xtj + j
eti wij βi
(4)
Door dit proces meerdere malen te herhalen voor elk van de projectierichtingen kan een reconstructie worden berekend van het oorspronkelijk object. Dit algoritme is goed gedocumenteerd in [8], waar men ook andere ieteratieve tomografische algoritmen kan terugvinden. Een vaak gebruikte techniek is om de waarden van matrix W niet van te voren in het geheugen op te slaan, maar pas uit te rekenen wanneer deze gebruikt worden. Dit verkleint het gebruikte geheugen en ook het aantal leesacties dat benodigd is tijdens het uitvoeren van het algoritme, maar vergroot het aantal berekeningen dat uitgevoerd moet worden gedurende een reconstructie. Deze techniek zal gebruikt worden bij het ontwikkelen van reconstructie algoritmen voor de GPU, omdat bij deze hardware de geheugengrootte beperkt is en het relatief lang duurt om het geheugen aan te spreken.
–6–
3.4
Taakbeschrijving
De uitvoering van dit project zal worden onderverdeeld in drie taken, waarvan sommige weer uit deeltaken zijn opgebouwd. In deze sectie zal de inhoud van elk van de taken nader worden toegelicht. 3.4.1
Taak 1: Verkorten van de scan- en rekentijd.
Taak 1.1: Literatuurstudie en verkenning hardware en programmeeromgeving In de literatuur is al veel bekend over het gebruik van GPUs voor niet-grafische problemen. Hoewel de technieken die gebruikt worden voor het uitvoeren van berekeningen op grafische hardware van probleem tot probleem verschillen, zal in eerste instantie een breed spectrum aan problemen nader worden bestudeerd. Bijzondere aandacht zal worden besteed aan het werk van K. Mueller en F. Xu [?, 7], die al eerder positieve resultaten hebben geboekt bij het gebruik van GPU computing voor tomografische reconstructie algoritmen. Hoewel ze daarbij geen gebruik hebben gemaakt van het Unified Shader Model, laat hun werk wel zien hoe tomografische algoritmen geïmplementeerd kunnen worden op GPUs. Op basis van deze artikelen zullen reeds enkele reconstructie algoritmen worden geïmplementeerd. In de volgende fase van het project (zie Taak 1.2) zal deze implementatie worden gebruikt voor een vergelijkende studie tussen algoritmen, die al dan niet gebruik maken van het Unified Shader Model. Verder zal CUDA worden bestudeerd, evenals enkele alternatieve ontwikkelomgevingen voor GPU computing. Taak 1.2: Ontwikkeling van voorwaartse en terugprojectie operaties op basis van het Unified Shader Model Deze taak zal deels uit onderzoek en deels uit implementatie bestaan. Van de drie eerder genoemde stappen (projectie, bepalen van de projectiefout en terugprojectie) vereisen het voorwaarts- en terugprojecteren veruit het meeste rekenkracht. Gelukkig kunnen juist deze stappen zeer goed parallelliseerd worden. Door het gebruik van GPUs kan een grote snelheidswinst worden behaald. Er zal worden onderzocht hoe de GPU elementen het beste met elkaar kunnen communiceren en hoe de stappen van de voorwaartse en terugprojectie operaties dienen te worden verdeeld over de hardware zodat er een zo groot mogelijke snelheidswinst zal worden behaald. De code die tijdens de vorige taak is geschreven (als herimplementatie op basis van reeds beschikbare literatuur) zal nu gebruikt worden om een vergelijking te kunnen maken tussen de methoden die al dan niet gebruik maken van het Unified Shader Model. In eerste instantie zal worden gewerkt aan 2D reconstructie problemen (parallel beam, fan beam). In een latere fase (zie Taak 1.4) zullen de ontwikkelde concepten worden uitgebreid naar 3D cone heam reconstructies. Taak 1.3: Discrete tomografie en Totale Variatie Minimalisatie m.b.v. GPU computing In deze deeltaak zal worden onderzocht hoe een tweetal iteratieve reconstructie algoritmen m.b.v. de GPU kan worden uitgevoerd. Daarbij zal gebruik worden gemaakt van de voorwaartse- en terugprojectieoperaties die in Taak 1.2 zijn ontwikkeld.
–7–
Ten eerste zal een GPU implementatie worden ontwikkeld van het DART algoritme (Discrete Algebraic Reconstruction Technique) [4], een recent ontwikkeld algoritme voor discrete tomografie. Discrete tomografie kan worden gebruikt als het gescande object uit slechts enkele materialen bestaat (of weefsels), die elk een specifieke grijswaarde hebben in de reconstructie. Door deze voorkennis te gebruiken in het reconstructie algoritme kan een nauwkeurige reconstructie worden berekend op basis van een klein aantal projecties. Het DART algoritme kan worden beschouwd als een uitbreiding van iteratieve algoritmen voor continue tomografie, waarbij tussen opeenvolgende iteraties een aantal extra stappen wordt uitgevoerd (segmentatie, smoothing en het vastzetten van interne pixels). In elke iteratie zal een deel van de pixels een vaste waarde krijgen, die niet kan veranderen. De backprojection operatie zal hieraan moeten worden aangepast. Een ander iteratief reconstructie algoritme dat goed werkt met slechts weinig projecties is Totale Variatie Minimalisatie. Dit algoritme minimaliseert het totale verschil tussen aangrenzende pixels en werkt daarom goed bij het reconstrueren van objecten waarvan bekend is dat ze uit grote, relatief gladde gebieden bestaan. Taak 1.4: Uitbreiding naar cone-beam tomografie Bij het ontwikkelen van forward- en backprojection operaties voor de GPU (zie Taak 1.2) werd in eerste instantie uitgegaan van een “parallel beam” of “fan beam” geometrie. In deze taak zullen de ontwikkelde concepten worden uitgebreid naar de “cone beam” geometrie, zie Figuur 3. Bij een “cone beam” opstelling wordt een kegelvormige stralenbundel gebruikt. Doordat een straal nu meerdere snedes van het object doorkruist kunnen de snedes, in tegenstelling tot “parallel beam” en “fan beam”, niet meer onafhankelijk worden gereconstrueerd. Er zullen gespecialiseerde forward- en backprojectie-operaties worden ontwikkeld voor “cone beam” tomografie. Het DART en het “Totale Variatie Minimalisatie” reconstructie algoritme zullen worden aangepast. 3.4.2
Taak 2: Ontwikkeling van iteratieve algoritmen voor zeer grote datasets.
Wanneer cone beam tomografie wordt toegepast op datasets uit de medische en wetenschappelijke praktijk, is het direct aanspreekbare videogeheugen van de GPU vaak niet groot genoeg; niet alleen omdat de projecties zeer groot zijn (tot wel 8000 × 8000 pixels), maar vooral omdat alle voxels in het geheugen opgeslagen moeten worden. In deze taak zullen technieken worden ontwikkeld om te kunnen voldoen aan de extra eisen die hierom aan de algoritmen worden gesteld. Om de later behaalde resultaten in een kader te kunnen plaatsen, worden eerst enkele eenvoudige oplossingen ontwikkeld: • Het verdelen van de reconstructie over twee grafische kaarten. Op deze manier kunnen twee GPUs gezamenlijk de oplossing berekenen en kunnen reconstructies twee keer groter zijn dan bij het gebruik van één grafische kaart. • Een eenvoudige cache implementeren. Voor het algoritme lijkt al het geheugen willekeurig aanspreekbaar, maar een extra “laag” tussen het algoritme en het geheugen draagt er zorg voor dat aangesproken gegevens die zich nog niet in het videogeheugen bevinden daarheen worden gekopieerd.
–8–
Figuur 3: Cone-beam opstelling. Net als bij parallel-beam draait het projector-detectorpaar om het object heen. De stralen divergeren zodat een projectie beïnvloed wordt door het volledige object. Onderzoek zal worden gedaan naar methoden om de berekeningen op te splitsen, waarbij telkens slechts een deel van de data in het snelle, maar relatief kleine videogeheugen hoeft te worden opgeslagen. 3.4.3
Taak 3: Ontwikkelen van een code-generator voor GPU-gebaseerde iteratieve reconstructie algoritmen.
Zoals reeds in sectie 3.3 werd besproken bestaan de iteraties van de meeste iteratieve reconstructie algoritmen uit drie stappen: projectie, foutberekening en terugprojectie. Dit zorgt ervoor dat implementaties van die algoritmen veel programmacode gemeen hebben. De code voor efficiente voorwaarste en terugprojectie en efficient geheugengebruik (Taak 2) kan bij elk van deze algoritmen gebruikt worden. Door het automatisch genereren van de code, is de ontwikkeltijd korter en is het proces minder foutgevoelig. Dankzij deze generator is het mogelijk om snel nieuwe algoritmen te creëren die op GPUs kunnen worden uitgevoerd. Hierdoor zal het relatief eenvoudig worden om diverse nieuwe vormen van voorkennis te gebruiken die niet in DART en Totale Variatie Minimalisatie worden gebruikt. Hierbij valt bijvoorbeeld te denken aan het reconstrueren van objecten die gegarandeerd geen gaten bevatten en het reconstrueren aan de hand van een sjabloon.
–9–
4
Planning
Hieronder wordt een planning gegeven van de taken die gespecificeerd zijn in de projectbeschrijving. 1.1 Literatuurstudie en verkenning hardware en programmeeromgeving (4 mnd): Literatuurstudie (2 mnd) Implementatie methoden uit literatuur (1 mnd) Bestuderen CUDA (1 mnd) 1.2 Ontwikkeling van voorwaartse en terugprojectie operaties op basis van het Unified Shader Model (5 mnd): Ontwikkelen projectie mbv. CUDA (3 mnd) Doen van vergelijkende studie tussen methoden uit de literatuur en die volgens het Unified Shader Model (2 mnd) 1.3 Discrete tomografie en Totale Variatie Minimalisatie m.b.v. GPU computing (8 mnd): Ontwikkelen van DART algoritme op GPU (4 mnd) Schrijven van Totale Variatie Minimalizatie algoritme voor GPU (4 mnd) 1.4 Uitbreiding naar cone-beam tomografie (8 mnd): Modeleren reguliere cone beam voorwaartse- en terugprojecties (3 mnd) Ontwikkelen 3D DART en TV-min reconstructie algoritmen (5 mnd) 2
Ontwikkeling van iteratieve algoritmen voor zeer grote datasets (10 mnd): Implementeren methode waarbij dataset wordt verdeeld over twee GPUs (1 mnd) Uitwerken en verwezenlijken caching-methode (2 mnd) Ontwikkelen algoritmen die rekening houden met geheugenkarakteristieken (5 mnd) Mogelijk maken werkelijke data in te laden (2 mnd)
3
Ontwikkelen van een code-generator voor GPU-gebaseerde iteratieve reconstructie algoritmen (8 mnd): Generator tot punt brengen waar al bekende algoritmen kunnen worden gegenereerd (2 mnd) Mogelijk maken om nieuwe algoritmen te kunnen creëren (3 mnd) Programma gebruiken voor ontwikkelen van nieuwe reconstructie algoritmen (3 mnd)
•
Schrijven doctoraalthesis. (5 mnd)
–10–
5
Toepassingsmogelijkheden
Het snel kunnen scannen en reconstrueren van objecten heeft tal van toepassingen in de medische praktijk, in de industrie en in de wetenschap. • In medische toepassingen zorgt een vermindering van het aantal projecties voor een verlaging van de ontvangen stralingsdosis. Een patiënt kan tijdens een CT angiograaf van het hart een stralingsdosis van wel 13 milliSievert ontvangen; dit in vergelijking met de maximaal toegestane dosis van 500 milliSievert per jaar [?]. Bij een reductie van het aantal benodigde projecties, zal de stralingsdosis verminderen. • Het gebruik van minder projecties leidt in veel gevallen tot een kortere scantijd. Als dynamische (bijv. bewegende) objecten worden gescand, zal een kortere scantijd de kwaliteit van de reconstructie ten goede komen, omdat minder bewegingsartifacten worden geïntroduceerd. Een korte scantijd zal ook het patiëntcomfort ten goede komen. • Door het gebruik van de GPU zal naast de scantijd ook de reconstructietijd worden verkort. Hierdoor zal de reconstructie sneller beschikbaar zijn. Dit zorgt ervoor dat een patiënt niet later terug hoeft te komen wanneer het beeld gereconstrueerd is, maar nog tijdens hetzelfde bezoek met de behandelend arts het onderzoek kan bespreken. Hierdoor kan snel gereageerd worden op nieuwe informatie, zodat indien nodig diezelfde dag nog vervolgonderzoek kan worden verricht. • Tomografie wordt ook gebruikt als onderdeel van het onderzoek bij proefdieren. Doordat de stralingsdosis wordt verlaagd worden deze minder belast. Dit zorgt voor een minder negatieve bijverschijnselen bij een gelijk aantal scans en maakt het tevens mogelijk het aantal scans per tijdseenheid te verhogen. • In de industrie wordt tomografische reconstructie onder andere gebruikt bij de kwaliteitscontrole van geproduceerde goederen. Hierbij geldt dat een verkorte scan- en reconstructietijd leidt tot een snellere doorvoer. Een verkorte reconstructietijd zorgt er verder voor dat er snel kan worden ingegrepen als er fouten worden ontdekt. • Het Antwerpse bedrijf DiamCAD maakt reconstructies van een diamant voor en tijdens deze geslepen wordt. Door de reconstructietijd te verlagen zal men bij dit bedrijf vaker kunnen scannen zodat de kwaliteit van het slijpproces verhoogd wordt. • In de materiaalwetenschap wordt veelvuldig gebruik gemaakt van elektronentomografie (tomografie m.b.v. een elektronenmicroscoop) om de 3D structuur van materialen te onderzoeken. Omdat de elektronenbundel het preparaat kan beschadigen is het wenselijk het aantal projecties zo klein mogelijk te houden. Door [?] het aantal projecties tijdens een scan te verminderen, wordt de levensduur van het bestudeerde object vergroot.
–11–
Referenties [1] Mueller, K., Xu F., and Neophytou N.: Why do GPUs work so well for acceleration of CT? SPIE Electronic Imaging, 2007. [2] Xu, F., Mueller K.: Real-time 3D computed tomographic reconstruction using commodity graphics hardware. Phys. Med. Biol. 52, 3405Ű-3419 (2007). [3] Blythe D.: The Direct3D 10 system ACM Transactions on Graphics (TOG) 3, 724–734 (2006). [4] Batenburg K.J., Sijbers J.: DART: a fast heuristic algebraic reconstruction algorithm for discrete tomography TP-L5.2, Biomedical Imaging III: Tomography, 2007. [5] nVidia Corp.: “NVIDIA CUDA Compute Unified Device Architecture – Programming Guide” June 2007. [6] Feldkamp L.A., Davis L.C., Kress J.W.: Practical cone-beam algorithm J. Opt. Soc. Am. A, 1, 2007. [7] Mueller, K., Yagel, R.: Rapid 3-D Cone-Beam Reconstruction with the Simultaneous Algebraic Reconstruction Technique (SART) Using 2-D Texture Mapping Hardware IEEE Transactions on Medical Imaging, 12, 2000. [8] Kak A.C., Slaney M.: “Principles of Computerized Tomographic Imaging,” Society of Industial and Applied Mathematics, 2001
