Intelligent visualisatieframework

Intelligent visualisatieframework BACHELOR INFORMATICA

10 Juni 2013 Student

Begeleider

Cédric Blom

Robert Belleman

Samenvatting Voor het maken van visualisaties zijn een aantal systemen beschikbaar. Deze systemen hebben gemeen dat ze gebruikersinput nodig hebben om een visualisatie te kunnen maken. Dat heeft ruimte geboden voor de ontwikkeling van een nieuw systeem. Hier wordt een “intelligent visualisatie-framework” geïntroduceerd dat met behulp van plug-ins, op basis van alleen een ingevoerd bestand, automatisch intelligente visualisatiesuggesties kan geven. Voor het framework zijn een aantal plug-ins ontwikkeld waarmee automatische visualisatie op basis van een bestand mogelijk gemaakt wordt. De plug-ins zijn getest met verschillende soorten bestanden als invoer. De software heeft voor ieder bestand uit de test aantoonbaar goede visualisaties opgeleverd. Op basis van de goede resultaten van deze test is de conclusie getrokken dat het framework gebruikt kan worden om, met behulp van plugins, intelligente visualisatiesuggesties te geven. Het systeem kan wetenschappers tijd besparen en helpen in het onderzoek, doordat het niet langer nodig is om ingewikkelde visualisatie-pipelines samen te stellen.

1

2

Inhoudsopgave Hoofdstuk 1 Introductie................................................................................................................ 5 1.1

Inleiding ................................................................................................................................... 5

1.2

Specificatie .............................................................................................................................. 6

Hoofdstuk 2 VTK........................................................................................................................... 7 2.1

Architectuur en conventies ..................................................................................................... 7

2.2

Visualisatie-pipeline ................................................................................................................ 8

2.3

Grafische pipeline .................................................................................................................... 8

Hoofdstuk 3 Clustering ................................................................................................................. 9 3.1

Algemeen................................................................................................................................. 9

3.2

Mahalanobis distance............................................................................................................ 10

Hoofdstuk 4 Implementatie ........................................................................................................ 13 4.1

Framework ............................................................................................................................ 13

4.1.1

Beslisboom .................................................................................................................... 13

4.1.2

Clustering....................................................................................................................... 14

4.2

Image datavisualisatie ........................................................................................................... 15

Hoofdstuk 5 Experimenten ......................................................................................................... 19 5.1

Methode ................................................................................................................................ 19

5.2

Resultaten.............................................................................................................................. 20

5.2.1

Visualisaties ................................................................................................................... 20

5.2.2

Overzicht........................................................................................................................ 22

Hoofdstuk 6 Conclusie en discussie ............................................................................................. 23 Referenties ................................................................................................................................ 25 : Plug-in schrijven ........................................................................................................ I Knoop plug-ins ..................................................................................................................................... II Kant plug-ins ........................................................................................................................................ II Blad plug-ins ....................................................................................................................................... III Beslisboom configuratiebestand instellen ......................................................................................... III : Visualisaties van rasterafbeeldingen, verkregen met de software ............................. V

3

4

Hoofdstuk 1

Introductie 1.1 Inleiding Visualisatie is het in beelden zichtbaar maken van informatie die in onderliggende data ligt opgeslagen. De techniek heeft sinds de komst van de computer en de toename van de beschikbare rekencapaciteit een flinke groei gekend. Door de ontwikkelingen is het mogelijk geworden om visualisaties te maken van complexe (bijvoorbeeld hoogdimensionaal) en zeer grote hoeveelheden data. Daardoor kan informatie in beelden worden omgezet uit data die voorheen niet of nauwelijks toegankelijk waren. [1] Hoewel het vakgebied als zodanig nog niet zo lang bestaat, is het concept van visualisatie al eeuwen oud. Het is bekend dat de oude Egyptenaren (200 voor Chr.) een voorloper van het coördinatenstelsel hadden voor de aanleg van dorpen en steden. Het duurde tot het begin van de 17e eeuw voordat analytische coördinatenstelsels (Descartes en Fermat) bekend werden. Dit was ook de eeuw waarin theorieën over meetfouten, schattingen en kansen tot ontwikkeling kwamen. Deze technieken hebben in de 18e eeuw bijgedragen aan het ontstaan van nieuwe datarepresentaties, zoals isolijnen (isocontours) en thematische kaarten. In deze eeuw raakte men ook bekend met grafieken, maar deze technieken kwamen pas echt tot bloei in de 19e eeuw. Alle methoden voor het maken van statistische grafieken, zoals we ze nu nog kennen, zijn in deze eeuw uitgevonden. [2] Het begin van de 20e eeuw was niet heel goed voor de ontwikkeling van de visualisatietechnologie, maar daar kwam met de komst van de computer verandering in. Er ontstond een heel nieuw vakgebied: datavisualisatie (computergraphics), dat zich bezig hield met het visualiseren van data met behulp van computers. Visualisatie heeft een heel nieuwe wending genomen. Onder visualisatie verstaan we niet langer alleen kaarten en grafieken, maar ook interactieve 3-D weergaven en visualisaties van hoog dimensionale data. Deze studie is gericht op de nieuwe vorm van datavisualisatie (met behulp van computers). [2] Er zijn een aantal frameworks en toolkits geschreven voor het maken van computervisualisaties. Voorbeelden zijn: VTK, SCIRun, IRIS Explorer, AVS, Vis5D en Paraview. VTK (Visualization ToolKit) is een toolkit voor het maken van met name 3-D visualisaties. VTK vereist de programmering van een visualisatie-pipeline. Omdat VTK ondersteuning biedt voor verschillende programmeertalen hoeft de pipeline niet per se in de moedertaal (C++) van de toolkit geschreven te worden. VTK biedt de mogelijkheid om voort te bouwen op bestaande modulen of nieuwe modulen te schrijven (meer over VTK in Hoofdstuk 2). De andere visualisatiepakketten zijn voorzien van een grafische interface. Sommige visualisatie-toolkits, zoals SCIRun bieden naast de grafische interface ook een mogelijkheid om nieuwe visualisatiemodulen voor de software te programmeren. Met VTK, SCiRun, IRIS Explorer en AVS kunnen modulen gecombineerd worden in een pipeline om nieuwe visualisatie-effecten te verkrijgen. Met paraview kunnen verschillende visualisaties over elkaar gelegd worden om nieuwe effecten te verkrijgen. Vis5D geeft een verzameling visualisaties die in- of uitgeschakeld kunnen worden. Voor dit onderzoek is vanwege de flexibiliteit en het grote aanbod aan modulen gekozen om VTK als basis te gebruiken voor een nieuw visualisatie-framework. [1] [3] [4]

5

Hoewel er een aantal systemen is waaruit gekozen kan worden voor het maken van datavisualisaties, zijn slechts een paar daarvan geschikt om visualisatie- en analyse technieken toe te voegen. Er zijn nog minder visualisatie systemen, toolkits en frameworks waarmee nieuwe visualisatie applicaties gebouwd kunnen worden (Alexander G. Gee et al.). Dit heeft ruimte geboden voor onderzoek naar systemen waarbij het delen en integreren van visualisatietechnieken eenvoudig is. In het onderzoek van Alexander G. Gee et al. wordt uit de voeten gedaan hoe een dergelijk systeem genaamd “Universal Visualization Platform” (UVP) gemaakt kan worden [5]. Deze studie, naar een “intelligent visualisatie-framework”, gaat verder. De hiervoor beschreven systemen hebben gebruikersinput nodig om een visualisatie te kunnen maken. Dat heeft ruimte geboden voor de ontwikkeling van een nieuw systeem. Een systeem dat het niet alleen mogelijk maakt om nieuwe analyse- en visualisatietechnieken toe te voegen, maar dat ook intelligent is. Hier wordt een framework geïntroduceerd dat met behulp van plug-ins, op basis van alleen een ingevoerd bestand, automatisch intelligente visualisatiesuggesties kan geven. Het systeem kan wetenschappers tijd besparen en helpen in het onderzoek, doordat het niet langer nodig is om ingewikkelde visualisatie-pipelines samen te stellen. Tegelijkertijd biedt het framework de mogelijkheid om nieuwe visualisatietechnologieën toe te voegen en oude technologieën verder te ontwikkelen. In dit onderzoek draait alles om de vraag: “Kan een framework ontworpen worden dat met behulp van plug-ins intelligente visualisatiesuggesties kan geven op basis van ingevoerde rasterafbeeldingen of eventuele andere bestanden?” [1] [5]

1.2 Specificatie Deze studie is onderdeel van een breder onderzoek dat is gericht op het vinden van een intelligente visualisatietoepassing. Een toepassing die op basis van alleen een bestand (met een willekeurig formaat) intelligente visualisatiesuggesties kan geven. Een deel van dat onderzoek is gericht op het ontwikkelen van een framework waarmee een dergelijke toepassing gemaakt kan worden. Dit software project is te verdelen in een aantal modulen, waaronder: het schrijven van een framework, het ontwikkelen van plug-ins voor intelligente visualisatiesuggesties en de ontwikkeling van een grafische gebruikersinterface. Deze studie omvat het schrijven van het framework. De studie omvat ook de ontwikkeling van plug-ins voor het automatisch visualiseren van 2-D en 3-D rasterafbeeldingen. De studie beperkt zich tot het visualiseren van de in Tabel 1 genoemde gegevensbronnen. De ontwikkeling van een gebruikersinterface is geen onderdeel van deze studie. Het framework is gebaseerd op VTK. De software moet zo worden geschreven dat die optimaal werkt en eenvoudig aan te passen is aan individuele wensen van experts op het gebied van visualisatie.

6

Hoofdstuk 2

VTK Het framework kan gezien worden als een laag bovenop VTK. Het levert gereedschappen zoals ondersteuning van plug-ins en technieken voor het maken van intelligente visualisatiebeslissingen (zie paragraaf 4.1). Het framework is zo ontworpen dat iedere combinatie van plug-ins uiteindelijk tot een VTKpipeline moet leiden. Omdat VTK zo’n cruciale rol speelt in dit framework en VTK niet bij iedereen bekend hoeft te zijn, is besloten om dit hoofdstuk te wijden aan een inleiding op deze toolkit. Voor meer informatie over VTK is het boek “The Visualization Toolkit” (Will Schroeder et al.) aan te raden. [6]

2.1 Architectuur en conventies VTK is een object-georiënteerde toolkit geschreven in de programmeertaal C++. De toolkit stelt plugins beschikbaar waarmee VTK ook gebruikt kan worden in programmeertalen zoals: Tcl, Java of Python. In VTK wordt onderscheid gemaakt tussen twee typen objecten: data-objecten en procesobjecten. Een data-object is als een archiefkast waarin belangrijke informatie opgeslagen kan worden. Een data-object kan bijvoorbeeld de informatie over een voxelafbeelding bevatten. De data-objecten hebben een heel gestructureerd ontwerp. Het is aan te raden om hoofdstuk 5 “Basic Data Representation” uit het boek “The Visualization Toolkit” (Will Schroeder et al.) te lezen om meer te weten te komen over de interne data-object representaties van VTK. De data-objecten worden gemaakt en bewerkt door procesobjecten. Procesobjecten kunnen gezien worden als werkers met een bepaalde taak. Een procesobject kan bijvoorbeeld een data-object van een afbeelding lezen, een contour berekenen en een nieuw data-object aanmaken waarin de contour van de afbeelding is opgeslagen. Door meerdere procesobjecten aan elkaar te schakelen ontstaat een pipeline. Een pipeline begint met één of meer procesobjecten die data-objecten produceren. Op de data-objecten worden door procesobjecten achter elkaar operaties uitgevoerd, daarmee wordt uiteindelijk een visualisatie verkregen. De pipeline vormt de ruggengraad van VTK. Een VTK-pipeline kan worden opgedeeld in een visualisatiepipeline en een grafische pipeline. Deze kunnen verder worden verdeeld in verschillende pipeline componenten. De visualisatie-pipeline en de grafische pipeline en hun componenten worden in meer detail besproken in paragraaf 2.2 en 2.3. Het is belangrijk om te weten dat niet iedere willekeurige volgorde van procesobjecten een functionele pipeline oplevert. Sommige procesobjecten hebben een specifiek soort data-object nodig als invoer. Andere procesobjecten produceren data-objecten die niet door alle andere procesobjecten gelezen kunnen worden. Om het gebruik van VTK zo makkelijk mogelijk te maken zijn er verschillende conventies gemaakt. Functie- en klassennamen zijn CamelCase. Klassennamen beginnen allemaal met de uitgang vtk-, waarna een beschrijvende naam voor de klasse volgt. Functies beginnen met een hoofdletter. Voor functie- en klassennamen worden geen afkortingen gebruikt tenzij deze algemeen bekend zijn. Alle klassenvariabelen zijn private of protected en kunnen alleen benaderd worden met Set() en Get()

7

functies. Meer informatie over VTK conventies is te vinden in het boek “The Visualization Toolkit” (Will Schroeder et al.). [1] [6]

2.2 Visualisatie-pipeline Met de visualisatie-pipeline kunnen data-objecten worden aangepast voordat ze op het scherm getoond worden. Het eerste component van een visualisatie-pipeline is een source-object. Er zijn twee typen source-objecten: vtkSources en vtkReaders. vtkSources maken nieuwe data-objecten aan, zonder dat daarvoor een gegevensbron nodig is. vtkCubeSource() produceert bijvoorbeeld een dataobject dat een kubus representeert. vtkReaders zetten gegevensbronnen om naar een interne dataobject representatie. De twee typen source-objecten hebben met elkaar gemeen dat ze data-objecten maken. De data-objecten kunnen bewerkt worden met vtkFilters (tweede component van de visualisatie-pipeline). vtkFilters hebben als invoer één of meer data-objecten en produceren één of meer data-objecten. Enkele voorbeelden van wat vtkFilters kunnen doen zijn: sub-sampling, contour bepalen, dataobjecten samenvoegen, de doorsnede van twee data-objecten bepalen, scalaire waarden aanpassen, etc. Door meerdere vtkFilters aan elkaar te schakelen kunnen speciale effecten verkregen worden. De visualisatie-pipeline eindigt met een vtkMapper. Deze zetten data-objecten om naar data-objectrepresentaties die geschikt zijn voor de grafische pipeline. [1] [6]

2.3 Grafische pipeline De grafische pipeline zet data-objecten om naar een beeld op het scherm. Daarbij zijn verschillende objecten betrokken. Een aantal van die objecten kunnen automatisch aangemaakt worden, zoals vtkCamera’s en vtkLights. De grafische pipeline is beter te overzien wanneer het in twee stukken wordt opgedeeld. In het eerste stuk wordt een scène (of voorstelling) opgebouwd. In het tweede stuk wordt de scène op het beeld geprojecteerd. Om de scène te kunnen maken zijn ten eerste vtkActors nodig. Zoals de naam al aangeeft is de vtkActor als een soort acteur op een set. De vtkActor kan ergens in de scène geplaatst worden. Het is mogelijk om de vtkActors een kleur te geven of om instellingen voor transparantie van de vtkActor aan te passen. De data voor een vtkActor is afkomstig van een vtkMapper (zie paragraaf 2.2). Als de vtkActors geplaatst zijn kunnen er lichten (vtkLights) en camera’s (vtkCamera’s) op de scène gericht worden. Het tweede stuk van de grafische pipeline begint met de aanmaak van een vtkRenderer-object. Alle vtkActors en vtkLights moeten worden meegegeven aan een vtkRenderer-object. Verder moet er één vtkCamera, de actieve camera, aan het vtkRenderer-object worden meegegeven. Het vtkRenderer-object maakt een beeld van de scène gezien vanaf de positie en oriëntatie van de actieve camera. Als er geen actieve camera is ingesteld creëert het vtkRenderer-object automatisch een vtkCamera, dat geldt ook voor vtkLights. Tot slot moet de vtkRenderer worden meegegeven aan een vtkRenderWindow-object. Dit object maakt een venster aan dat op het scherm getoond wordt. In dit venster wordt het beeld, dat met het vtkRenderer-object verkregen is, getoond. Het vtkRenderWindow-object zorgt er voor dat dit beeld naar de verhoudingen van het venster geschaald wordt. [1] [6]

8

Hoofdstuk 3

Clustering Het geïmplementeerde framework maakt gebruikt van een clusteringtechniek (zie paragraaf 4.1.2). De clusteringtechniek die gebruikt wordt is een variant op K-Means, waarbij de Mahalanobis distance als afstandmaat wordt gebruikt. Om een indruk te krijgen van de overwegingen die ten grondslag liggen aan de keuze voor de clusteringtechniek is in onderstaand stuk een algemene introductie op het gebied van clustering gegeven. Een deel van de techniek is gebaseerd op de Mahalanobis distance. Omdat deze techniek niet bij iedereen bekend hoeft te zijn gaat het tweede deel van deze paragraaf over de Mahalanobis distance en hoe deze gebruikt kan worden in combinatie met clustering.

3.1 Algemeen Clustering is het groeperen (clusteren) van objecten (observaties, data of feature vectoren) op basis van hun kenmerken. De belangstelling voor clustertechnieken is breed. [7] Daarom is in de loop der jaren veel onderzoek gedaan naar clustertechnieken. In tegenstelling tot andere statistische technieken (zoals regressie analyse en ANOVA) bestaat er voor clustering niet zoiets als een beste oplossing voor een probleem. Dit heeft geleid tot een wildgroei aan clustertechnieken, er zijn letterlijk honderden clusteralgoritmen gedocumenteerd. Deze clusteralgoritmen kunnen worden onderverdeeld in vier hoofdcategorieën: hierarchical methods, partitioning methods, overlapping methods en ordination methods. Hierarchical methods leggen een rangorde tussen punten aan. Hierarchical methods zijn op te delen in agglomerative methods (bottom up) en divisive methods (top down). Bij agglomerative methods worden punten net zo lang samengevoegd totdat alle punten in de hoogste rangorde tot één cluster behoren. Een divisive method doet precies het omgekeerde, alle punten worden tot één cluster gerekend, deze worden net zo lang opgedeeld totdat er n clusters zijn. Partitioning methods verdelen puntenverzamelingen in één keer in n verschillende clusters. In tegenstelling tot hierarchical methods is er dus geen rangorde. Partitioning methods zijn in te delen op basis van vijf kenmerken. Het eerste kenmerk is de manier waarop initiële clusters gekozen worden, dat kan willekeurig (K-means) of handmatig (de gebruiker specificeert de clusters). Het tweede kenmerk is het aantal keer dat het algoritme herhaald wordt om de clusters te berekenen. Sommige methoden berekenen de clusters in één keer terwijl anderen het algoritme een aantal keer moeten herhalen. Het derde kenmerk is de maat die gebruikt wordt om clusters van elkaar te scheiden (dit kan een afstandsmaat zijn, zoals: Euclidean distance en Mahalanobis distance, maar het kan ook een correlatiemaat zijn). Het vierde en vijfde kenmerk zijn of het aantal clusters van te voren vast ligt of dat dit variabel is en de methode waarmee met uitbijters omgegaan wordt. Overlapping methods verdelen de puntenverzameling ook in een aantal clusters, maar in tegenstelling tot partitioning methods kunnen punten in meerdere clusters tegelijk ingedeeld worden. Vaak werken overlapping methods met kansmodellen die aangeven hoe groot de kans is dat een bepaald punt tot een cluster behoort. [7] [8]

9

Ordination methods zijn technieken waarmee de dimensionaliteit van data veranderd (meestal verlaagd) kan worden. Deze technieken rekenen niet zelf uit waar clusters gevormd kunnen worden, dit wordt overgelaten aan de onderzoeker. Vaak worden ordination methods daarom gebruikt in een combinatie met een andere clustering techniek. De ordination method wordt dan gebruikt om de complexiteit van het probleem te verkleinen. [8]

3.2 Mahalanobis distance De Mahalanobis distance is een afstandsmaat die rekening houdt met de correlatie in de data, omdat het gebruik maakt van de inverse variantie-covariantiematrix. Dit is het best aanschouwelijk te maken met een afbeelding en een voorbeeld. In Figuur 1.a is een cluster in ℝ2 weergegeven (blauwe punten). De cirkels geven schematisch de Euclidische afstand gemeten vanaf het middelpunt van het cluster aan. In de figuur is ook een oranje vierkant en een groene driehoek getekend. We kunnen ons afvragen welk punt het dichtst bij het centrum van het cluster ligt. Gemeten in Euclidische afstand is dit het oranje vierkant. Dit is gevoelsmatig misschien een verkeerde beslissing, omdat het cluster zich veel meer uitrekt in de richting van de groene driehoek. In Figuur 1.b is dezelfde situatie weergegeven. De lijnen in de figuur geven hierin echter schematisch de Mahalanobis afstand gemeten vanaf het middelpunt van het cluster aan. Aan de ellipsen in de figuur is te zien dat de Mahalanobis afstand tot de groene driehoek kleiner is dan de afstand tot het oranje vierkant. [9]

(a)

(b)

Figuur 1: Verschil tussen Euclidische afstand en Mahalanobis afstand tot het middelpunt van een cluster (blauwe punten). (a) De ellipsen geven schematisch de Euclidische afstand tot het middelpunt van het cluster weer. (b) De ellipsen geven schematisch de Mahalanobis afstand tot het middelpunt van het cluster weer. (Spreidingsgrafieken gemaakt met Wolfram Mathematica 9.0.1.0. Data afkomstig uit [9]).

De Mahalanobis afstand van een punt x tot het middelpunt µ met een inverse variantie-covariantiematrix Σ-1 is gedefinieerd als: 𝑀𝐷 = √(𝑥 − 𝜇)𝑇 Σ−1 (𝑥 − 𝜇) De functie heeft veel overeenkomsten met de Euclidische afstand tot het middelpunt dat gedefinieerd is als: 𝐸𝐷 = √(𝑥 − 𝜇)𝑇 (𝑥 − 𝜇) De Mahalanobis afstand is de Euclidische afstand in een ander coördinatenstelsel dat gedefinieerd wordt door Σ-1. Dit nieuwe coördinatenstelsel is gecorrigeerd voor de correlatie in de data van het cluster. [9] [10]

10

De Mahalanobis afstand kan gebruikt worden in combinatie met clusteringstechnieken zoals K-Nearest Neighbour (kNN) of K-Means. Een punt wordt dan toebedeeld aan het cluster waarvan de Mahalanobis distance tussen het middelpunt (of in geval van kNN een punt in het cluster) en het punt het kortst is. [11]

11

12

Hoofdstuk 4

Implementatie In deze sectie wordt ingegaan op het globale softwareontwerp. Er wordt niet ingegaan op de implementatiedetails. De sectie geeft echter een vrij compleet beeld van de richting van het onderzoek. De software bestaat uit twee onderdelen: een framework en plug-ins. Het framework is een gereedschapskist voor het schrijven van software waarmee, uit gegevensbronnen van diverse soort, automatisch visualisaties gegenereerd kunnen worden. De plug-ins zijn stukken software die geschreven zijn voor het analyseren of visualiseren van een specifieke gegevensbron. De plug-ins kunnen gebruik maken van de gereedschappen die het framework biedt. In de onderstaande paragraaf wordt het softwareontwerp van het framework besproken. In de paragraaf: “Image datavisualisatie” wordt de implementatie van plug-ins voor het visualiseren van image data besproken. Raadpleeg Appendix A voor het schrijven van nieuwe plug-ins.

4.1 Framework Het framework kan worden opgedeeld in een beslisboom en clusteringscomponenten. De beslisboom biedt een methode voor het maken van voorgeprogrammeerde beslissingen en visualisaties, terwijl de clustercomponenten bedoeld zijn om dynamisch beslissingen te maken op basis van terugkoppeling met de gebruiker. Hoewel de beslisboom, de clustercomponenten en de plug-ins ieder een eigen functie hebben is het niet mogelijk om ze helemaal los van elkaar te zien. In het onderstaande stuk worden de implementaties van de beslisboom en de clusteringtechnieken achtereenvolgens besproken, maar noodgedwongen zullen de delen soms naar elkaar verwijzen en worden de plug-ins bij deze uitleg betrokken.

4.1.1 Beslisboom De beslisboom bestaat uit drie onderdelen: de knopen (nodes), de kanten (edges) en de bladeren (leafs). De samenhang van knopen, kanten en bladeren bepaalt hoe de beslisboom er uit ziet. De beslisboom wordt vastgelegd in een xml-bestand. Niet iedere volgorde van knopen, kanten en bladeren is geldig. Een beslisboom is geldig wanneer hij voldoet aan de volgende regels: een beslisboom begint bij één knoop, knopen kunnen niet direct met elkaar verbonden worden (er moet altijd één kant tussen zitten), de beslisboom eindigt bij de bladeren (een beslisboom is dus niet geldig als er een pad is dat niet eindigt met een blad), tussen een knoop en een blad zit altijd precies één kant en kanten zijn nooit direct verbonden met andere kanten (er zit altijd een knoop tussen). Ieder onderdeel in de beslisboom heeft zijn eigen taak: knopen maken beslissingen, kanten stellen vectoren samen en bladeren stellen “Visualization Toolkit (VTK) pipelines” samen. De knopen beslissen op basis van één of meerdere gegevensbronnen. Een beslissing bestaat uit het kiezen van één of meerdere kanten die met de knoop verbonden zijn. Die kanten worden vervolgens in de volgorde waarin de keuze gemaakt is uitgevoerd. Kanten hebben de vrijheid om (een deel van) een vector samen te stellen. De vector wordt gebruikt voor clustering, hierover zal later meer worden verteld. Kanten leiden naar nieuwe knopen of eindigen in een blad. Een blad stelt een VTK-pipeline samen. De uitvoer van een VTK-pipeline zorgt voor een visualisatie. Omdat knopen de mogelijkheid hebben om meer dan één kant te kiezen, kan het voorkomen dat de beslisboom uiteindelijk tot meer dan één VTK-pipeline leidt

13

dus tot meerdere visualisaties Dit kan gezien worden als een voorselectie van pipelines die ieder een goede visualisatie opleveren. De gebruiker heeft dan de mogelijkheid om te kiezen welke pipeline het beste is. De knopen, kanten en bladeren worden ingevuld met plug-ins. Knopen, kanten en bladeren hebben drie verschillende soorten plug-ins. Elke soort is gebonden aan de taakomschrijving die gegeven is in de vorige alinea. De controle daarop wordt gedaan door het framework. Het framework zorgt er ook voor dat de plug-ins geladen en op het juiste moment uitgevoerd worden. Verder heeft het framework een reader voor het lezen van het xml-bestand waarin de structuur van de beslisboom opgeslagen ligt. Tenslotte regelt het framework de interactie met de gebruiker. De samenwerking tussen plug-ins en het framework bepaalt uiteindelijk welke pipelines gekozen worden. Om beurten krijgt het framework of de plug-ins de controle over het programma. Als het programma start laadt het framework een dialoogvenster waarmee de gebruiker een gegevensbestand kan kiezen. Na de keuze laadt het framework het xml-bestand met de structuur van de beslisboom. Uit het xml-bestand kan het framework opmaken wat de eerste knoop is en welke kanten verbonden zijn met die knoop. De plug-in die bij de knoop hoort wordt ingeladen. Aan deze plug-in wordt de locatie van het door de gebruiker gekozen bestand en de naam van het bestand meegegeven. Het framework geeft ook de lijst met kanten door aan de plug-in. Vervolgens wordt de controle over het programma doorgegeven aan de plug-in. De plug-in van de knoop kan het bestand laden en analyseren. Op basis van de analyse van het bestand moet deze plug-in een selectie maken uit de lijst kanten. Daarnaast brengt hij een rangorde aan in de kanten. Het framework voorziet in een techniek waarmee de plug-in gegevens kan doorgeven aan opvolgende plug-ins. De knoop kan dus gegevens doorgeven aan zijn kanten. Als de plug-in klaar is neemt het framework de controle weer over. Het framework zal in rangorde de plug-in van een kant starten. De plug-in van de kant krijgt van het framework de vector van de voorafgaande kant. Indien het de eerste kanten na de eerste knoop betreffen zijn dit lege vectoren. De kant krijgt de controle en kan de vector verder uitbouwen met behulp van de gegevens van de voorgaande knoop. De kant kan gegevens doorgeven aan de volgende knoop of aan het blad. Als hij daarmee klaar is wordt de vector en de controle weer teruggegeven aan het framework. Het framework start de volgende knoop of als het eind van een pad bereikt is het blad. Betreft het een knoop dan wordt het bovenstaande herhaald. Is het einde van het pad bereikt dan wordt de controle overgedragen aan het blad. Het blad krijgt de gegevens en maakt daaruit een VTK-pipeline. Daarna neemt het framework de controle weer over en gaat naar de volgende kant in de eerder aangelegde rangorde en voert het hele bovenbeschreven proces opnieuw uit totdat alle VTK-pipelines gecreëerd zijn.

4.1.2 Clustering De clustering is bedacht om visualisatiecategorieën dynamisch te kunnen bepalen uit gegevensbronnen. Van een gegevensbron wordt een vector berekend. De vector bevat alleen numerieke waarden en geeft een uniek label aan iedere gegevensbron. De vector kan gezien worden als een punt in ℝ𝑛 , waarbij n de dimensie van de vector is. De software zal proberen om vectoren in te delen in clusters, waarbij ieder cluster een visualisatiecategorie voorstelt. Als dat lukt, zal de visualisatie-pipeline die bij de categorie hoort uitgevoerd worden op de gegevensbron. De visualisatie wordt getoond en de gebruiker krijgt de kans om de visualisatie aan te passen. Als de vector niet aan een cluster toebedeeld kan worden of als de gebruiker aangeeft ontevreden te zijn over de visualisatie (door een wijziging aan te brengen aan de getoonde visualisatie) wordt van de vector een nieuw cluster gemaakt.

14

Het indelen van vectoren in clusters gebeurd op basis van de Mahalanobis distance. Een vector wordt toebedeeld aan het cluster waarvan de Mahalanobis distance tussen het middelpunt en de vector het kortst is. Naast de Mahalanobis distance wordt ook de grootte van een cluster gebruikt om vectoren in te delen. Een groot cluster ontstaat doordat daar vaak vectoren aan toegevoegd worden. Vectoren worden alleen aan een cluster toegevoegd als een gebruiker niets aan de voorgestelde pipeline verandert, dus impliciet aangeeft tevreden te zijn met de indeling van de vector. De a priori kans dat een vector toebedeeld moet worden aan een groot cluster is dus groter dan aan een klein cluster. Het framework is voorzien van een techniek om met de a priori kans om te gaan. Dit werkt als volgt: aan ieder vector in een cluster wordt een zekere massa toegekend. Iedere vector draagt met zijn massa bij aan een “zwaartekrachtveld” rondom de cluster. Doordat er meer massa is, is het “zwaartekrachtveld” van grote clusters groter dan dat van kleine clusters. De “zwaartekracht” van een cluster neemt af met het kwadraat van de afstand die gemeten wordt vanuit het middelpunt van de cluster. Een vector die tussen meerdere clusters inligt wordt tot die cluster gerekend waarvan de massa gedeeld door het kwadraat van de Mahalanobis distance het grootst is. Tot dusver is uitgegaan van een framework met twee onafhankelijke componenten: de beslisboom (statisch) en de clusteringsalgoritmen (dynamisch). Het framework is echter zo ontworpen dat statische en dynamische componenten simultaan gebruikt kunnen worden. De balans tussen statische en dynamische componenten wordt volledig bepaald door de plug-ins. Er zijn twee dingen nodig om statische en dynamische componenten simultaan te kunnen gebruiken. Ten eerste moet van een gegevensbron een vector berekend kunnen worden. Ten tweede is er een techniek nodig om de pipeline die met clustering verkregen wordt te kunnen combineren met de pipeline die uit de beslisboom verkregen wordt. De berekening van de vectoren vindt plaats in de kanten van de beslisboom. Zoals in de voorgaande paragraaf is uitgelegd wordt de invulling van een kant gegeven door een plug-in. De plug-in bepaalt wat er in de vector moet komen. Omdat kanten altijd volgen na knopen kan de samenstelling van de vectoren aangepast worden aan de beslissingen die genomen worden. Het combineren van de clustering en beslisboom pipelines vindt plaats in de bladeren van de beslisboom. Het framework biedt een techniek waarmee een VTK pipeline op een willekeurige plaats onderbroken kan worden. Het gat in de pipeline kan dan later worden opgevuld met de pipeline die met behulp van clustering wordt verkregen. Op deze manier kan bijvoorbeeld het begin en einde van een pipeline samengesteld worden met behulp van statische beslissingen terwijl het middenstuk op een dynamische manier ingevuld wordt.

4.2 Image datavisualisatie Met de software worden plug-ins voor het automatisch visualiseren van data van pixel- (2D) en voxelafbeelding (3D) meegeleverd. In deze paragraaf zal het globale ontwerp van deze plug-ins besproken worden. Figuur 2 is een overzicht van alle plug-ins die betrokken zijn bij de automatische visualisatie van rasterafbeeldingen. De plug-ins zijn gerangschikt in de volgorde waarop ze in de beslisboom staan (zie paragraaf Beslisboom).

15

PixelVectorEd ge.py

FileDecisi onNode. py

ImageDe cisionNo de.py

PixelPipeline Leaf.py

VoxelDec isionNod e.py

ExtremaVol umeRenderi ngPipelineL eaf.py VolumeR endering Decision Node.py

LineVolume RenderingPi pelineLeaf.p y

ContouringP ipelineLeaf.p y

DefaultVolu meRenderin gPipelineLea f.py

PassVectorEd ge.py Figuur 2: Overzicht van alle plug-ins die betrokken zijn bij het automatisch visualiseren van image data. Ellipsen met een lichtblauwe kleur stellen knopen voor, rechthoeken met een donkerblauwe kleur stellen kanten voor en de groene rechthoeken met de twee ronden hoeken stellen bladeren voor.

De meest linker knoop (FileDecisionNode.py) in het diagram is de eerste plug-in die gestart wordt. Van het framework ontvangt deze knoop de locatie en de naam van een bestand dat door de gebruiker is geselecteerd (zie paragraaf Beslisboom). De plug-in gebruikt de extensie van het bestand om te bepalen hoe het gelezen moet worden. Voor het lezen van het bestand gebruikt de plug-in een VTK-reader. Als het bestand gelezen is wordt bepaald of het een rasterafbeelding is, in dat geval zal de kant voor het visualiseren van rasterafbeeldingen gestart worden. Van sommige bestanden wordt standaard aangenomen dat het rasterafbeeldingen zijn. Op andere bestanden wordt eerst een analyse gedaan. De analyse bestaat uit het opvragen van een “VTK dataset type”. Datasets van type structured grid worden als rasterafbeelding aangemerkt. In Tabel 1 is een overzicht van alle bestandsformaten die door de FileDecisionNode plug-in ondersteund worden. Alle bestandsformaten waarop extra analyse plaats vindt zijn rood gekleurd. Van DICOM afbeeldingen wordt zowel een pixel- als een voxelafbeelding gemaakt. De voxelafbeelding wordt verkregen door het stapelen van alle DICOM afbeeldingen die binnen de opgegeven bestandslocatie gevonden kunnen worden. Tabel 1: Overzicht van alle bestandsformaten die door afbeeldingvisualisatie (sub)beslisboom ondersteund worden. In rood de bestandsformaten die niet altijd afbeelding data bevatten.

Bestandsformaat DICOM VTK JPEG

BMP

16

Omschrijving Digital Imaging and Communications in Medicine, voor opslag van medische beeldinformatie. [12] Dit formaat wordt gebruikt door de Visualization Toolkit om visuele data, afkomstig uit zeer diverse gegevensbronnen, op te slaan. [6] Formaat voor opslag van gecomprimeerde pixelafbeeldingen. JPEG compressie geeft (als een op DCT gebaseerde methode wordt gebruikt) verlies van beeldinformatie. Het formaat heeft geen kanaal voor transparantie waarden. [13] Formaat voor niet-gecomprimeerde pixelafbeeldingen. Het formaat ondersteund RGB kleuren. [14]

PNG

TIFF

Formaat voor opslag van gecomprimeerde pixelafbeeldingen. PNG heeft compressie zonder verlies van beeldinformatie, ondersteund RGB kleuren en heeft een alpha kanaal voor transparantie waarden. [12] [15] [16] Flexibel bestandsformaat voor opslag van pixelafbeeldingen. Het formaat ondersteund verschillende vormen van compressie. TIFF kan RGB kleuren aan. [12] [16]

Als de FileDecisionNode.py plug-in klaar is wordt via een PassVectorEdge.py kant de knoop ImageDecisionNode.py gestart. Kanten die gebruik maken van de PassVectorEdge.py plug-in worden overgeslagen. De ImageDecisionNode.py plug-in is de eerste knoop na FileDecisionNode.py en wordt daarom gestart. Deze knoop maakt zijn beslissing op basis van de dimensionaliteit van de rasterafbeelding. Voor 2D rasterafbeeldingen (pixelafbeelding) wordt de PixelVectorEdge.py gestart. 3D rasterafbeeldingen worden verder geanalyseerd door de VoxelDecisionNode.py knoop. Voor rasterafbeeldingen met hogere dimensionaliteit is (nog) geen plug-in beschikbaar. De PixelVectorEdge.py kant maakt een histogram van de scalaire waarden van de pixels. Het aantal klassen waarin het histogram wordt verdeeld kan worden ingesteld in een configuratiebestand (plugin.ini). Het histogram wordt samen met de maximale en minimale scalaire waarden aan een vector toegevoegd. Deze vector wordt door het PixelPipelineLeaf.py blad voor clustering gebruikt. Het blad produceert een pipeline waarvan het begin en einde gedefinieerd zijn. Het middenstuk moet worden ingevuld met het cluster resultaat. Wanneer het begin en einde van de pipeline direct met elkaar verbonden worden ontstaat er een pipeline waarmee de afbeelding zonder wijzigingen getoond kan worden. De VoxelDecisionNode.py knoop bepaalt uit twee technieken voor voxelafbeelding visualisatie, volumerendering en contouring, welke als eerste uitgevoerd moet worden. Om dit te bepalen maakt de knoop een histogram van de scalaire waarden van de voxels. Een statistische techniek die Freedman Diaconis is genoemd (naar de bedenkers David A. Freedman en Persi Diaconis), wordt gebruikt om de klassebreedte van het histogram te bepalen. De verdeling van het histogram bepaalt welke van de twee technieken als eerste wordt uitgevoerd. De software maakt onderscheid tussen twee histogramverdelingscategorieën: een lineair verband of een polynomiaal verband waarbij tenminste één maximum gevonden kan worden. De verdeling wordt als lineair beschouwd wanneer de correlatie een threshold overschrijdt of wanneer het histogram geen maximum heeft. De threshold kan worden ingesteld in een configuratiebestand (plugin.ini). Bij een lineaire verdeling wordt contouring uitgevoerd voordat volume rendering gestart wordt. Alle andere verdelingen hebben tenminste één maximum. De software maakt onderscheid tussen verdelingen met twee maxima of minder en verdelingen met meer dan twee maxima. Bij verdelingen met twee maxima of minder wordt contouring toegepast voordat volume rendering wordt uitgevoerd. In alle overgebleven situaties wordt volume rendering eerst uitgevoerd. De VolumeRenderingDecisionNode.py knoop kiest uit drie volume rendering configuraties de beste. De pipelines voor de drie volume rendering configuraties zijn geprogrammeerd in de bladeren: ExtremaVolumeRenderingPipelineLeaf.py, LineVolumeRenderingPipelineLeaf.py en DefaultVolumeRenderingPipelineLeaf.py. Alle drie de configuraties resulteren in een 3D grijstinten afbeelding. Voxels met de kleinste scalaire waarden worden zwart ingekleurd, voxels met de grootste scalaire waarden wit en de grijstinten daartussen worden bepaald met lineaire interpolatie. De bladeren gaan echter verschillend om met de configuraties voor de opaciteit van de voxels. De DefaultVolumeRenderingPipelineLeaf maakt de voxels met de middelste scalaire waarden het meest opaak, voxels met een scalaire waarde die afwijkt van de middelste waarde worden minder opaak. De overige bladeren bepalen de opaciteit

17

op basis van de verdeling van een histogram van de scalaire waarden. LineVolumeRenderingPipelineLeaf geeft voxels met scalaire waarden die het meest voorkomen de kleinste opaciteit, terwijl voxels met scalaire waarden die het minst voorkomen erg opaak gemaakt worden. ExtremaVolumeRenderingPipelineLeaf bepaalt de opaciteit op basis van de pieken en de minima in het histogram. Het blad berekent het oppervlakte onder de pieken en bepaalt de gemiddelde scalaire waarden die bij de pieken en minima horen. Alle voxels met een scalaire waarde gelijk aan de scalaire waarde van een minimum worden volledig transparant gemaakt. De logaritme van de oppervlakten onder de pieken bepalen de opaciteit van de andere voxels. Grote oppervlakten betekenen een lage opaciteit en kleine oppervlakten een grote opaciteit. ExtremaVolumeRenderingPipelineLeaf wordt alleen uitgevoerd als het histogram in de verdelingscategorie polynomiaal verband met minstens één maximum valt. LineVolumeRenderingPipelineLeaf wordt alleen uitgevoerd als het histogram onder de categorie lineair verband valt en het verband stijgend of dalend is. DefaultVolumeRenderingPipelineLeaf wordt altijd uitgevoerd. De software is met een plug-in voor contouring voorzien: ContouringPipelineLeaf.py. Dit blad gebruikt de middelste scalaire waarde als grenswaarde voor contouring. Het is mogelijk om dit in een later stadium met meerdere plug-ins uit te breiden.

18

Hoofdstuk 5

Experimenten 5.1 Methode De experimenten zijn bedoeld om de software te toetsen aan de onderzoeksvraag. Om antwoord te kunnen geven op de onderzoeksvraag zijn plug-ins nodig waarmee intelligente visualisatiesuggesties gegeven kunnen worden voor tenminste rasterafbeeldingen. Voor dit onderzoek zijn de plug-ins gebruikt die in paragraaf 4.2 zijn beschreven. Om aan te tonen dat deze plug-ins in staat zijn om visualisatiesuggesties te doen is een testverzameling samengesteld bestaande uit diverse rasterafbeeldingen, waaronder tenminste één bestand voor ieder type dat beschreven wordt in Tabel 1. De lijst met bestandsnamen is gegeven in Tabel 2. De plug-ins zijn in staat om visualisatiesuggesties te geven als de software tenminste één suggestie geeft voor ieder bestand uit de lijst. Tabel 2: Lijst van alle bestanden die gebruikt zijn voor het experiment.

Bestandsformaat DICOM VTK (alleen voxelafbeeldingen) JPEG BMP PNG TIFF

Bestandsnamen 2729/100.dcm t/m 2729/256.dcm I0000003.vtk, obj_394.vtk, mummy.128.vtk, knee.vtk en sphere16.vtk RIP_Q10.jpg lenna.bmp transparent_dice.png marbles.TIF

Om een antwoord te kunnen geven op de vraag of de visualisatiesuggesties ook intelligent zijn, is het volgende experiment bedacht. De software wordt gebruikt om, voor ieder bestand dat in Tabel 2 gegeven is, visualisatiesuggesties te verkrijgen. De visualisatiesuggesties worden beoordeeld op twee punten. Ten eerste of de visualisatie de structuur van “het object” zichtbaar maakt. De visualisatie kan teveel of juist te weinig informatie weergeven, waardoor het moeilijker wordt om de “hoofdstructuur” van “het object” te zien. Het tweede punt waarop beoordeeld wordt is of de visualisatie alle “belangrijke” details toont. Voor beide punten geldt dat de beoordelingscriteria afhankelijk zijn van wat er getoond wordt. Bijvoorbeeld, op een afbeelding van een röntgenscan van een mens moet het mogelijk zijn om tenminste de huid en het botweefsel te zien, terwijl het voor een 3D model van een kubus voldoende is om alleen de buitenkant te kunnen zien. Iedere visualisatiesuggestie krijgt één van de volgende drie beoordelingen: plus (+), nul (0) of min (-).   

+ structuur EN details goed zichtbaar. 0 structuur OF details goed zichtbaar. - structuur EN details NIET goed zichtbaar.

Wanneer bij ieder bestand tenminste één suggestie verkregen wordt met een + beoordeling wordt gesteld dat de software in staat is om intelligente suggesties te geven. Daarbij moet vermeld worden dat pixelweergaven van pixelafbeeldingen altijd met een + beoordeeld worden.

19

Naast de beoordeling zullen in de resultaten ook een aantal afbeeldingen van visualisatiesuggesties getoond en besproken worden. Afbeeldingen van de overige visualisatiesuggesties kunnen in Appendix B gevonden worden. Met de getoonde afbeeldingen moet het mogelijk zijn om een objectief beeld te vormen van de mogelijkheden van de software.

5.2 Resultaten 5.2.1 Visualisaties Figuur 3 toont de visualisatiesuggesties die zijn verkregen door de software te draaien met als invoer de DICOM-afbeelding 129.dcm uit de testverzameling. In Figuur 3.a is een pixel weergave van de DICOM-afbeelding. Dit is de eerste suggestie die de software geeft. De weergave laat duidelijk de contouren van een fles zien. De pijl met nummer 1 laat zien dat de fles gevuld is met een vloeistof. De pijl met nummer 2 laat zien dat er in de vloeistof een foetus zit. Goed te zien is dat de pixelweergave geen inzicht geeft in de ruimtelijke structuur. Zoals het figuur laat zien is de kracht van de pixelweergave dat details in een dergelijke vloeistofomgeving zichtbaar worden. De voxelweergaven (Figuur 3.b en c), die verkregen zijn door het stapelen van verschillenden DICOMafbeeldingen waarna volume rendering (DefaultVolumeRenderingPipelineLeaf.py en ExtremaVolumeRenderingPipelineLeaf.py) is toegepast, geven ruimtelijke beelden. De techniek geeft de voxels verschillende kleur- en opaciteitwaarden, waardoor dwars door fysieke objecten, vloeistoffen en gassen heen gekeken kan worden en tegelijkertijd het onderscheid tussen de verschillende structuren gemaakt kan blijven worden. De pijl met nummer 1 laat zien dat door de wand van het glas in Figuur 3.b en c nog duidelijk het oppervlakte van de vloeistof te zien is. De rendering instellingen van Figuur 3.b en c zijn verschillend, waardoor in Figuur 3.b de foetus zichtbaar is (aangegeven met pijl 2) terwijl Figuur 3.c slechts de vloeistof toont. Ook heeft Figuur 3.c meer ruis/korreligheid dan Figuur 3.b. De laatste visualisatiesuggestie (Figuur 3.d) is verkregen met behulp van contouring (ContouringPipelineLeaf.py). De fles is veel scherper afgebeeld dan de flessen die met volume rendering zijn verkregen. Contouring geeft bovendien een zeer goed ruimtelijk beeld van het object. Het is echter lastig om met contouring verschillende structuren tegelijk weer te geven; in Figuur 3.d is daardoor alleen de wand van de fles zichtbaar.

20

1

2

(d)

(a)

1

2

(b)

(c)

Figuur 3: Visualisatiesuggesties voor DICOM-afbeeldingen (129.dcm). (a) Pixelafbeelding visualisatie van het geselecteerde DICOM bestand, met 1. oppervlakte vloeistof en 2. foetus. (b) 3D visualisatie van DICOM-afbeeldingen gemaakt m.b.v. volume rendering (middelste scalaire waarde is meest opaak gemaakt), met 1. oppervlakte vloeistof en 2. Foetus. (c) 3D visualisatie van DICOM-afbeeldingen gemaakt m.b.v. volume rendering (opaciteit waarden zijn verkregen met een geavanceerde analyse techniek), met 1. oppervlakte vloeistof. (d) 3D visualisatie van DICOM-afbeeldingen gemaakt m.b.v contouring.

Figuur 4 is een ander voorbeeld, dat is verkregen door de software te draaien met als invoer de VTKvoxelafbeelding obj_394.vtk uit de testverzameling. Op de pixelweergave na zijn voor het koraal dezelfde visualisatietechnieken gebruikt als voor de fles. Op de volume rendering afbeeldingen (Figuur 4.a en b) zijn de contouren van een schaal of bak te zien waarin het koraal vermoedelijk werd bewaard. De binnenkant van het koraal bestaat voornamelijk uit de mesoglea (doorzichtige, geleiachtige substantie aan de binnenkant van het koraal) die op de volume rendering afbeeldingen als een constante grijze half-transparante kleur gevisualiseerd is, waardoor er geen verschil is met de epidermis (buitenste cellaag) van het koraal. In Figuur 4c is te zien dat de contouring weergave even rijk is aan details,

21

een scherpere afbeelding oplevert en een beter ruimtelijk beeld geeft van het koraal dan de volume rendering weergaven.

(a)

1

(b)

(c)

Figuur 4: Visualisatiesuggesties voor een VTK-voxelafbeelding (obj_394.vtk). (a) Visualisatie gemaakt m.b.v. volume rendering, waarbij de middelste scalaire waarde het meest opaak is gemaakt. (b) Visualisatie gemaakt m.b.v. volume rendering (opaciteit waarden zijn verkregen met een geavanceerde analyse techniek). (c) Visualisatie gemaakt m.b.v. contouring.

Wanneer een pixelafbeelding, uit de testverzameling, als invoer wordt gebruikt, produceert de software een pipeline waarvan het begin en einde gedefinieerd zijn (PixelPipelineLeaf.py). Als visualisatiesuggestie geeft de software een pixelweergave van de afbeelding, die verkregen is door het begin en einde van de pipeline direct met elkaar te verbinden.

5.2.2 Overzicht In Tabel 3 zijn, voor verschillende rasterafbeeldingen uit de testverzameling, de resultaten van de vier voxel technieken vergeleken. Voor ieder bestand is er tenminste één techniek met een + beoordeeld. Volume rendering met extrema-analyse heeft een lage score, terwijl de “standaard” volume rendering techniek een hoge score behaalt (sphere16.vtk wordt als een aparte categorie beschouwd). Merk op dat voor sphere16.vtk de “standaard” volume rendering techniek een lage score krijgt, terwijl deze techniek voor de andere bestanden juist een goed resultaat geeft. De visualisatiesuggesties voor de DICOM-afbeelding 129.dcm zijn in Figuur 3 weergegeven. De suggesties voor het VTK-bestand obj_394.vtk staan in Figuur 4. Afbeeldingen van de overige visualisatiesuggesties staan in Appendix B. Tabel 3: Vergelijking van de resultaten, die verkregen zijn door vier verschillende voxel visualisatie technieken toe te passen op een aantal rasterafbeeldingen. + structuur en details goed zichtbaar, 0 structuur of details goed zichtbaar, - structuur en details zijn niet zichtbaar.

Volume rende- Volume rende- Volume rende- Contouring ring, standaard ring, lijnanalyse ring, extremaanalyse 129.dcm I0000003.vtk obj_394.vtk mummy.128.vtk knee.vtk sphere16.vtk

22

+ + 0 + + -

n.v.t n.v.t n.v.t n.v.t n.v.t 0

0 + 0 n.v.t

0 + 0 0 +

Hoofdstuk 6

Conclusie en discussie Het framework kan gebruikt worden om, met behulp van plug-ins, intelligente visualisatiesuggesties te geven, op basis van ingevoerde rasterafbeeldingen. De in de Resultaten en Appendix B getoonde afbeeldingen bewijzen dat de software in staat is om, op basis van rasterafbeeldingen van diverse bestandsformaten, visualisatiesuggesties te geven. Op basis van de in de Methode gestelde criteria kan aangetoond worden dat de software ook intelligente visualisatiesuggesties geeft. In Tabel 3 is te zien dat voor ieder bestand tenminste een visualisatie techniek met een plus (+) beoordeeld is. Dit betekent dat de software in staat is om voor ieder bestand uit de testverzameling tenminste één visualisatie te geven waarop duidelijk de structuur en details van de afbeelding te zien zijn. Alle visualisatietechnieken zijn gebaseerd op universele eigenschappen van afbeeldingen, daarom is te verwachten dat de software ook voor rasterafbeeldingen die niet in de testverzameling zitten visualisatiesuggesties kan geven die goed bruikbaar zijn. De volume rendering met lijnanalyse en de volume rendering met extrema-analyse zijn gebaseerd op informatietheorie. De data wordt geanalyseerd met behulp van een kleurenhistogram (histogram van de scalaire waarden van de voxels). Scalaire waarden die veel voorkomen geven een grote piek in het histogram, maar hebben een lage entropie en worden daarom transparant gemaakt. De entropie van scalaire waarden die weinig voorkomen hebben juist een hoge entropie en worden daarom opaak gemaakt. De volume rendering met extrema-analyse zorgt er daarnaast nog voor dat voxels met een scalaire waarde die bij een minima in het histogram horen volledig transparant gemaakt worden. Deze volume rendering techniek gaat er vanuit dat de gemiddelde scalaire waarden, van weefsels/structuren van een zelfde soort, gelijk zijn. Als de afbeelding een weefsel/structuur bevat van een noemenswaardige grote zullen er dus veel voxels zijn met gemiddeld een zelfde scalaire waarde, waardoor er een piek in het histogram ontstaat. De minima worden daarom als ruis beschouwd en weggefilterd. [17] [18] De “standaard” volume rendering en de contouring techniek zijn gebaseerd op “the gray world assumption”, die zegt dat in een afbeelding waarin de verschillende kleuren in voldoende mate voorkomen de gemiddelde kleur grijs is. De voxel afbeeldingen hebben geen kleur maar een scalair, daarom wordt de middelste scalaire waarde van het totale bereik als “het gemiddelde grijs” aangemerkt. Beide technieken gaan uit van een gemiddelde afbeelding. De “standaard” volume rendering techniek corrigeert de voxelafbeelding voor de gemiddelde afbeelding, door de opaciteit van de voxels in te stellen op basis van een grove benadering van een normaal verdeling met als gemiddelde de “grijs” scalair. Voxels met een scalaire waarde die in de gemiddelde afbeelding weinig voorkomen worden transparant gemaakt terwijl de voxels met een veel voorkomende scalaire waarde opaak gemaakt worden. De contouring techniek moet een grenswaarde voor de contour instellen en kiest daarom voor de veel voorkomende grijs scalair. [19] [20] De “standaard” volume rendering techniek is minder geschikt voor het visualiseren van onnatuurlijke afbeeldingen. Deze afbeeldingen voldoen vaak niet aan de normaal verdeling van de gemiddelde afbeelding. Dat de “standaard” volume rendering techniek minder goed werkt voor het visualiseren van

23

onnatuurlijke afbeeldingen is ook af te leiden uit de resultaten, omdat de “standaard” volume rendering techniek een slecht resultaat geeft bij het visualiseren van sphere16.vtk (zie Tabel 3). Deze afbeelding bestaat maar uit twee typen voxels, namelijk: voxels met een scalaire waarde van nul en voxels met de hoogste scalaire waarden. De scalaire waarden van deze afbeelding zijn dus niet normaal verdeeld rondom de “grijs” scalair. De volume rendering met extrema-analyse scoort laag (zie Tabel 3). De afbeeldingen zijn vaak grofkorrelig en niet optimaal afgesteld. Het lijkt er op dat de grofkorreligheid komt omdat voxels met een scalaire waarde gelijk aan de scalaire waarden van de minima in het histogram niet helemaal transparant moeten worden gemaakt zoals dat nu gebeurt, of dat zo is moet vervolgonderzoek uitwijzen. Sommige plaatjes worden met deze techniek erg transparant of juist erg opaak. Dit doet denken aan een nog niet optimale afstelling. Mogelijk zou vooraf een waarde voor de gemiddelde opaciteit gekozen kunnen worden. Door dit gekozen gemiddelde af te trekken van het berekende gemiddelde en alle voxels met dit verschil te corrigeren zou de transparantie bijgesteld kunnen worden. Verder onderzoek moet de waarde van deze techniek aantonen. Een alternatief is de techniek te vervangen door oppervlakte detectie op basis van Canny edge. Canny edge is een techniek om de randen in een 2D afbeelding te vinden. Zoals Christian Bähnisch et al. in hun onderzoek aantonen kan Canny edge worden omgeschreven naar een efficiënte oppervlakte detector. De prestaties van de detector kunnen worden geoptimaliseerd door het algoritme uit te voeren op de GPU (Kohei Ogawa et al.). Door 3D Canny edge toe te passen op een voxelafbeelding wordt een voxelbeeld verkregen waarin oppervlakten scalaire waarden groter dan nul krijgen en de achtergrond scalaire waarden gelijk aan nul. Zo’n scalaire waarde geeft aan hoe groot het verschil is tussen de scalaire waarde van een voxel en die van zijn directe buren, in de originele afbeelding. Door alle oppervlakten transparant te maken is het mogelijk om in een afbeelding alle belangrijke structuren te zien. De sterkte van de transparantie kan eventueel gebaseerd worden op waarde van de verschilvector. Verder onderzoek moet de waarde van deze techniek aantonen. [21] [22] Het framework is alleen voorzien van plug-ins voor het visualiseren van voxel afbeeldingen. Toekomstig onderzoek kan bestaan uit het ontwikkelen en onderzoeken van nieuwe plug-ins voor het visualiseren van bijvoorbeeld grafiek data. Zoals is besproken is er ook ruimte voor onderzoek naar het verbeteren van de bestaande rasterafbeelding visualisatie plug-ins. Deze plug-ins zijn nog niet voorzien van een techniek voor het visualiseren van rasterafbeeldingen met hogere dimensionaliteit dan 3. Toekomstig onderzoek kan dus ook bestaan uit het ontwikkelen van plug-ins voor het visualiseren van hoog dimensionale rasterafbeeldingen.

24

Referenties

[1] C. D. Hansen en C. R. Johnson, The Visualization Handbook, Burlington: Elsevier, 2005. [2] M. Friendly, „A Brief History of Data Visualization,” in Handbook of Data Visualization, Springer Berlin Heidelberg, 2008, pp. 15-56. [3] I. Bitter, R. Van Uitert, I. Wolf, L. Ibáñez en J.-M. Kuhnigk, „Comparison of Four Freely Available Frameworks for Image Processing and Visualization That Use ITK,” Transactions on Visualization and Computer Graphics, vol. 13, nr. 3, pp. 483-493, 2007. [4] S. G. Parker en C. R. Johnson, „Scirun: A Scientific Programming Environment for Computational Steering,” Conference on Supercomputing, pp. 1-20, 1995. [5] A. G. Gee, H. Li, M. Yu, M. B. Smrtic en U. Cvek, „Universal visualization platform,” The International Society for Optical Engineering, 2005. [6] W. Schroeder, K. Martin en B. Lorensen, The Visualization Toolkit, 2e red., New Jersey: Prentice Hall PTR, 1998. [7] A. Jain, M. Murty en P. Flynn, „Data Clustering: A Review,” ACM Computing Surveys, vol. 31, 1999. [8] G. W. Milligan en M. C. Cooper, „Methodology Review: Clustering Methods,” Applied Psychological Measurement, vol. 11, pp. 329-354, 1987. [9] R. De Maesschalck, D. Jouan-Rimbaud en D. Massart, „The Mahalanobis distance,” Chemometrics and Intelligent Laboratory Systems, nr. 50, pp. 1-18, 2000. [10] P. Mahalanobis, „On the generalized distance in statistics,” Journ. Asiat. Soc. Bengal, vol. II, nr. 1, pp. 49-55, 1936. [11] B. Vandeginste, D. Massart, L. Buydens, S. De Jong, P. Lewi en J. Smeyers-Verbeke, Handbook of Chemometrics and Qualimetrics: Part B, Amsterdam: Elsevier, 1998. [12] R. Graham, R. Perriss en A. Scarsbrook, „DICOM demystified: A review of digital file formats,” Clinical Radiology, nr. 60, 2005. [13] G. K. Wallace, „The JPEG still picture compression standard,” Transactions on Consumer Electronica, vol. 1, nr. 38, 1992. [14] „msdn,” Microsoft, [Online]. Available: us/library/dd183377(v=vs.85).aspx. [Geopend 2 Juni 2013].

http://msdn.microsoft.com/en-

[15] G. Roelofs. [Online]. Available: http://www.libpng.org/pub/png/. [Geopend 2013 Juni 2].

25

[16] J. Ziv en A. Lempel, „A universal algorithm for sequential data compression,” Transactions on information theory, vol. 23, nr. 3, pp. 337-343, 1977. [17] C. Shannon, „A Mathematical Theory of Communication,” The Bell System Technical Journal, nr. 27, pp. 379–423, 623–656, 1948. [18] E. T. Jaynes, „Information Theory and Statistical Mechanics,” vol. 4, nr. 106, 1957. [19] G. Buchsbaum, „A spatial processor model for object color perception,” J. Franklin Inst., nr. 310, p. 1–26, 1980. [20] F. Gasparini en R. Schettini, „Color balancing of digital photos using simple image statistics,” Pattern Recognition, nr. 37, p. 1201 – 1217, 2004. [21] C. Bähnisch, P. Stelldinger en U. Köthe, „Fast and Accurate 3D Edge Detection for Surface Reconstruction,” Lecture Notes in Computer Science, nr. 5748, 2009. [22] K. Ogawa, Y. Ito en K. Nakano, „Efficient Canny Edge Detection using a GPU,” Networking and Computing (ICNC), pp. 279-280, 2010.

26

: Plug-in schrijven Alle plug-ins hebben dezelfde structuur. Een plug-in bestaat uit een python bestand met daarin tenminste één knoop, kant of blad klasse. De klasse heeft tenminste een __init__ functie waarmee de klasse geïnitialiseerd kan worden, en een execute functie waarmee het programma van de plug-in gestart kan worden. Dit programma eindigt afhankelijk van het type plug-in met het retourneren van een verzameling kanten, een vector of een pipeline. Stappen voor het schrijven van een plug-in: 1. Het schrijven van een plug-in begint door het kiezen van het type plug-in. Er zijn drie typen plugins die corresponderen met de gelijknamige klasse typen: knoop, kant en blad. Knoop plug-ins maken beslissingen, kant plug-ins stellen vectoren samen en blad plug-ins stellen pipelines samen (zie paragraaf 4.1). 2. De tweede stap is het kopiëren van een interface klasse in een python bestand. Ieder type plug-in heeft zijn eigen interface klasse (zie Tabel 4). Vul zelf een klasse naam in voor . 3. De derde stap is het aanvullen van de __init__ functie. Als voor een correcte uitvoer van de plug-in extra functie parameters nodig zijn, kunnen deze voor *args en **kwargs geplaatst worden (de plug-in moet dan wel na een kant volgen die deze parameters door stuurt, de plug-in kan dus niet meer als root in de beslisboom gebruikt worden). In de initialisatie functie kunnen de parameters opgeslagen worden als klasse variabele, voor later gebruik. De __init__ functie mag niets retourneren. 4. De vierde en laatste stap is het invullen van de execute functie. Wat de code doet kan zelf bepaald worden. De functie kan gebruik maken van de variabelen die in de __init__ functie zijn gezet, kan hulp functies en klassen aanroepen en kan gebruik maken van functionaliteiten van het framework door deze te importeren. De execute functie is slechts gebonden aan een regel: het moet eindigen met het retourneren van een lijst kanten (of een enkele kant), een vector of een pipeline. Wat de execute functie retourneert hangt af van het type plug-in. Een knoop retourneert een lijst kanten (of een enkele kant), een kant retourneert een vector en een blad retourneert een pipeline. Met het retourneren van deze informatie kan direct invloed worden uitgeoefend op de verdere loop van het programma. Tabel 4: Interface klassen voor het schrijven van plu-ins.

Plug-in type Knoop plug-in

Interface klasse from lib.tree.Implementation import DecisionNode class (DecisionNode): def __init__(self, edges, filename, *args, **kwargs): pass

Kant plug-in

def execute(self): pass from lib.tree.Implementation import VectorEdge, Vector class (VectorEdge): def __init__(self, node, vector, *args, **kwargs): pass

I

Blad plug-in

def execute(self): pass from lib.tree.Implementation import PipelineLeaf, Pipeline, SubPipeline class (PipelineLeaf): def __init__(self, *args, **kwargs): pass def execute(self): pass

Een aantal regels zijn specifiek voor een type plug-in. Alle klassen worden aangeroepen met een aantal standaard parameters, maar deze parameters zijn niet voor elke klasse hetzelfde. Hoe de parameters gebruikt kunnen worden is voor iedere parameter anders. Verder is het niet mogelijk om zomaar een lijst kanten, een vector of een pipeline te retourneren. Iedere soort heeft zijn eigen regels waar niet van mag worden afgeweken. In het onderstaande stuk worden per plug-in type de regels besproken die daarvoor gelden.

Knoop plug-ins Knoop plug-ins krijgen standaard twee parameters mee. Een dictionary met kanten (edges) en de bestandslocatie (filename) van een door de gebruiker geselecteerd bestand (dit is het bestand waarvoor de gebruiker visualisatiesuggesties wil krijgen). Uit de dictionary met kanten moet een deelverzameling gemaakt worden. De deelverzameling kan bestaan uit een enkele kant of uit een lijst van kanten, maar mag niet leeg zijn. De deelverzameling bepaald wat de eerst volgende kant in de beslisboom is die wordt uitgevoerd. Als de deelverzameling uit meer dan een kant bestaat worden deze in rangorde uitgevoerd (zie paragraaf 4.1). De kanten kunnen uit de dictionary gehaald worden met een key. Deze key wordt in het configuratie bestand van de beslisboom vastgelegd (zie paragraaf Beslisboom configuratiebestand instellen). De kanten zijn objecten en hebben een speciale functie setInitArguments waarmee de parameters, die de desbetreffende kant bij initialisatie mee krijgt, ingesteld kunnen worden. De functie kan gebruikt worden alsof het een __init__ functie van een klasse is.

Kant plug-ins Kant plug-ins krijgen standaard twee parameters mee. Een knoop object (node) en een vector (vector) die ook leeg kan zijn. De knoop is het eerst volgende object dat uitgevoerd zal worden. Dit object wordt meegegeven om vanuit de kant parameters door te kunnen geven aan de knoop (optioneel). Hiervoor wordt een speciale functie setInitArguments gebruikt. De werking van deze functie is uitgelegd in de vorige paragraaf. De vector bestaat uit alle data die er door voorgaande kanten ingestopt zijn. Als er geen voorgaande kanten zijn of als er nooit data aan de vector is toegevoegd, is de vector leeg. Vector objecten zijn voorzien van een functie addFeatures, waarmee bestaande vectoren van extra data kunnen worden voorzien. Door een lijst of tuple met getallen mee te geven aan deze functie kan de vector worden uitgebreid met nieuwe data. Er kan ook een nieuwe vector worden aangemaakt. Een nieuwe vector wordt verkregen door een instantie van de Vector klasse aan te maken. Door een lijst of tuple met getallen mee te geven bij het instantiëren van de vector, wordt deze direct van data voorzien. Kanten moeten een vector retourneren, als dit een nieuwe vector is gaat de oude vector verloren.

II

Blad plug-ins Blad plug-ins krijgen standaard geen parameters mee. Het pipeline object dat het blad dient te retourneren moet zelf worden aangemaakt. Pipeline objecten worden verkregen door een nieuwe instantie van de Pipeline klasse aan te maken. Bij de instantiatie van dit object moet een lijst van SubPipeline objecten en een vtkRenderer object worden meegegeven. De lijst met SubPipeline objecten mag ook leeg gelaten worden. Het vtkRenderer object moet verbonden zijn met een VTK-pipeline. Deze pipeline wordt gebruikt voor het visualiseren van een door de gebruiker aangewezen bestand. Als een deel van de pipeline nog niet bekend is, bijvoorbeeld omdat dat deel met clustering verkregen moet worden, kan de pipeline opgebroken worden. Daarvoor zijn de SubPipeline objecten ontwikkeld. Een SubPipeline object kan geïnstantieerd worden met een VTK-pipeline object zoals een vtkFilter, maar kan ook zonder parameters geïnstantieerd worden. De subpipeline simuleert alle functies van het object waarmee het geïnstantieerd is. Als de subpipeline niet geïnstantieerd is met een object, wordt iedere functie aanroep gesimuleerd. In het onderstaande stuk zal ook de term leeg SubPipeline object gebruikt worden, voor dit laatste type SubPipeline object. SubPipeline objecten kunnen in de meeste gevallen gewoon behandeld worden alsof het VTKpipeline objecten zijn, maar er zijn een paar addertjes onder het gras. SubPipeline objecten kunnen niet direct met gewone VTK-pipeline objecten verbonden worden, dit komt omdat VTK de SubPipeline objecten niet herkend. Gelukkig zijn alle SubPipeline objecten voorzien van een functie getVtkObject, waarmee het VTK-pipeline object, waarmee de subpipeline geïnstantieerd is, verkregen kan worden. Een ander punt waar rekening mee gehouden moet worden is dat SubPipeline objecten alle functie aanroepen opslaan en dus niet direct uitvoeren. Dit heeft twee consequenties, namelijk: de SubPipeline objecten zijn niet up-to-date (functies als Update worden niet direct uitgevoerd) en het is niet mogelijk om variabelen op te vragen van de SubPipeline objecten. Tot slot is het belangrijk om functie aanroepen van lege SubPipeline objecten goed te controleren. Lege SubPipeline objecten zijn bedoeld om het begin of einde van een ontbrekend stuk pipeline te simuleren. Omdat dit deel van de pipeline later wordt ingevuld is niet bekend door welk VTK-pipeline object het begin of einde gedefinieerd wordt. Daarom accepteren lege SubPipeline objecten iedere functie aanroep die ze wordt aangeboden, zonder te controleren of ze correct zijn. Als de VTK-pipeline (met of zonder subpipeline onderbrekingen) samengesteld is, moet deze nog aan een Pipeline object worden toegevoegd. Dit wordt gedaan bij de initialisatie van het Pipeline object. Zoals eerder vermeld moeten daaraan twee parameters worden meegegeven. De eerste parameter, de lijst met SubPipeline objecten, moet bestaan uit alle lege SubPipeline objecten die zijn aangemaakt. Deze kunnen dan later “gevuld” worden met een echt VTK-pipeline object. Zodra een lege SubPipeline object “gevuld” is, worden automatisch alle functie aanroepen die, naar dit object en naar het hiermee verbonden object, gedaan zijn in volgorde uitgevoerd op de echte VTK-pipeline objecten. Hierdoor kan uiteindelijk de VTK-pipeline worden voltooid. Zoals eerder is aangegeven moet aan het Pipeline object ook een instantie van een vtkRenderer object worden meegegeven. Het renderer object wordt gebruikt om de visualisatie op het scherm te krijgen.

Beslisboom configuratiebestand instellen Als de plug-ins geschreven zijn moeten deze nog aan de beslisboom worden toegevoegd. Dit kan gedaan worden door een XML-bestand, waarin de configuratie van de beslisboom is opgeslagen, aan te passen. In dit bestand mogen drie typen tags gebruikt worden. Er is dus een tag voor ieder plug-in type: <node> voor knoop plug-ins, <edge> voor kant plug-ins en voor blad plug-ins. Iedere tag krijgt tenminste twee attributen mee: filename voor de bestandnaam van de plug-in en

III

classname voor de naam van de klasse waarin de uitvoerbare code van de plug-in staat. <edge> tags moeten ook voorzien zijn van een key attribuut. De key attribuut is een sleutel waarmee de kant vanuit een knoop plug-in geselecteerd kan worden (zie paragraaf Knoop plug-ins). Tot slot kan aan iedere tag ook een labelattribuut worden meegegeven. Deze tag is optioneel, maar kan nuttig zijn als de plug-in later herkend moet worden. Als de tag is samengesteld hoeft deze alleen nog maar op de juiste plaats in de hiërarchie van het XML-bestand geplaatst te worden.

IV

: Visualisaties van rasterafbeeldingen, verkregen met de software

(a)

(b)

(c)

Figuur 5:Visualisatiesuggesties voor mummy.128.vtk. (a) Visualisatie gemaakt m.b.v. volume rendering, waarbij de middelste scalaire waarde het meest opaak is gemaakt. (b) Visualisatie gemaakt m.b.v. volume rendering (opaciteit waarden zijn verkregen met een geavanceerde analyse techniek). (c) Visualisatie gemaakt m.b.v. contouring.

(a)

(b)

(c)

Figuur 6: Visualisatiesuggesties voor knee.vtk. (a) Visualisatie gemaakt m.b.v. volume rendering, waarbij de middelste scalaire waarde het meest opaak is gemaakt. (b) Visualisatie gemaakt m.b.v. volume rendering (opaciteit waarden zijn verkregen met een geavanceerde analyse techniek). (c) Visualisatie gemaakt m.b.v. contouring.

V

(a)

(b)

(c) Figuur 7:Visualisatiesuggesties voor I0000003.vtk. (a) Visualisatie gemaakt m.b.v. volume rendering, waarbij de middelste scalaire waarde het meest opaak is gemaakt. (b) Visualisatie gemaakt m.b.v. volume rendering (opaciteit waarden zijn verkregen met een geavanceerde analyse techniek). (c) Visualisatie gemaakt m.b.v. contouring.

VI

(a)

(b)

(c)

Figuur 8: Visualisatiesuggesties voor sphere16.vtk. (a) Visualisatie gemaakt m.b.v. contouring. (b) Visualisatie gemaakt m.b.v. volume rendering,, waarop een lijnanalyse techniek is toegepast voor het bepalen van de opaciteit instellingen. (c) Visualisatie gemaakt m.b.v. volume rendering, waarbij de middelste scalaire waarde het meest opaak is gemaakt.

(a)

(b)

(c)

(d)

Figuur 9: Visualisatiesuggesties voor: (a) RIP_Q10.jpg, (b) lenna.bmp, (c) transparent_dice.png en (d) marbles.TIF

VII