Segmentation of 3D volume models in virtual reality

Treball Final de Grau Menció en ciències de la computació Segmentation of 3D volume models in virtual reality Oriol Vidal Teruel Director Pere Pau Vázquez Alcocer [email protected]c.edu Tutora Eva Monclús Lahoya [email protected]c.edu Alumne Oriol Vidal Teruel [email protected] January 18, 2021 Resum La visualització mèdica és un camp d’estudi molt important per a millorar el coneixement i la diagnosi sobre les diferents patologies que pateixen tota classe d’organismes, amb especial èmfasi a la humanitat. La recerca de tècniques de gràfics per computador destinades a l’avenç d’aquest camp és molt àmplia, i ha tractat diferents aspectes d’aquest procés de visualització. La segmentació és una tècnica que permet separar regions d’interès contingudes en un model volumètric més gran, oferint així una oportunitat de millorar la visualització i inspecció d’aquestes regions. L’alt rendiment que ofereixen les targetes gràfiques desenvolupades els últims anys ha permès implementar tècniques que treballen sobre models volumètrics amb resultats més ràpids, que ha permès millorar de la interacció amb les aplicacions de visualització. La realitat virtual es presenta com a un camp que ha evolucionat molt els últims anys, oferint un canvi de paradigma en la interacció amb les aplicacions. En aquest projecte implementarem algorismes de segmentació en una aplicació de visualització de models volumètrics que permet la interacció en un entorn de realitat virtual. i Resumen La visualización médica es un campo de estudio muy importante para mejorar el conocimiento y la diagnosis sobre las diferentes patologías que sufren toda clase de organismos, con especial énfasis en la humanidad. La búsqueda de técnicas de gráficos por computador destinadas al avance de este campo es muy amplia, y ha tratado diferentes aspectos de este proceso de visualización. La segmentación es una técnica que permite separar regiones de interés contenidas en un modelo volumétrico mayor, ofreciendo así una oportunidad de mejorar la visualización e inspección de estas regiones. El alto rendimiento que ofrecen las tarjetas gráficas desarrolladas en los últimos años ha permitido implementar técnicas que trabajan sobre modelos volumétricos con resultados más rápidos, que ha permitido mejorar la interacción con las aplicaciones de visualización. La realidad virtual se presenta como un campo que ha evolucionado mucho en los últimos años, ofreciendo un cambio de paradigma en la interacción con las aplicaciones. En este proyecto implementaremos algoritmos de segmentación en una aplicación de visualización de modelos volumétricos que permite la interacción en un entorno de realidad virtual. ii Abstract Medical visualization is a very important field of study to improve knowledge and diagnosis about the different pathologies that all kinds of organisms suffer from, with special emphasis on humanity. The search for computer graphics techniques aimed at advancing this field is very broad, and has addressed different aspects of this visualization process. Segmentation is a technique that allows to separate regions of interest contained in a larger volumetric model, thus offering an opportunity to improve the visualization and inspection of these regions. The high performance offered by graphics cards developed in recent years has allowed the implementation of techniques that work on volumetric models with faster results, which has improved the interaction with display applications. Virtual reality is presented as a field that has evolved a lot in recent years, offering a paradigm shift in interaction with applications. In this project we will implement segmentation algorithms in a volumetric model visualization application that allows interaction in a virtual reality environment. iii Índex Índex de figures vii Índex de taules x 1 Introducció i contextualització 1 1.1 Introducció ........................................ 1 1.2 Formulació del problema ................................. 2 1.3 Actors implicats ..................................... 3 1.4 Definició de conceptes fonamentals ........................... 4 1.4.1 Visualització de models volumètrics ...................... 4 1.4.2 Segmentació .................................... 5 1.4.2.1 GPU vs. CPU ............................. 6 1.4.2.2 Implementacions per GPU ...................... 6 1.4.3 Realitat virtual .................................. 8 2 Abast del projecte 10 2.1 Objectius ......................................... 10 2.2 Obstacles ......................................... 11 2.3 Riscos ........................................... 12 3 Desenvolupament del projecte 12 3.1 Visualització de models volumètrics ........................... 13 3.2 Segmentació per CPU .................................. 13 3.2.1 Formulació del problema ............................. 14 3.2.1.1 Segmentació per llindar desenvolupat a la CPU ........... 14 3.2.1.2 Region Growing basat en threshold ................. 15 3.2.2 Integració a Unity3D ............................... 16 iv 3.2.3 Anàl·lisi de rendiment ............................. 20 3.3 Segmentació per GPU .................................. 24 3.3.1 Formulació del problema ............................. 24 3.3.1.1 Render to Texture ........................... 24 3.3.1.2 Compute Shaders i Compute Buffers ................. 25 3.3.1.3 Region Growing diffusion-based .................... 28 3.3.2 Implementació .................................. 29 3.3.2.1 Implementació amb Compute Shaders ................ 30 3.3.2.2 Implementació amb Render to texture ................ 32 3.3.2.3 Segmentació per creixement de regió basada en difusió ....... 32 3.3.3 Anàl·lisi de rendiment ............................. 36 3.4 Interacció ......................................... 39 3.4.1 Formulació del problema ............................. 39 3.4.2 Implementació .................................. 41 3.4.2.1 Metàfores d’interacció ......................... 41 3.4.2.2 Altres .................................. 43 3.5 Resultats ......................................... 46 3.6 Conclusions i treball futur ................................ 52 4 Gestió del projecte 53 4.1 Metodologia i rigor .................................... 53 4.1.1 Metodologia .................................... 53 4.1.2 Seguiment ..................................... 53 4.2 Planificació temporal ................................... 54 4.2.1 Tasques ...................................... 54 4.3 Recursos .......................................... 60 4.3.1 Recursos humans ................................. 60 4.3.2 Recursos materials ................................ 60 v 4.4 Gestió del risc ....................................... 61 4.5 Gestió econòmica ..................................... 63 4.5.1 Pressupost .................................... 63 4.5.1.1 Recursos humans (RH) ........................ 63 4.5.1.2 Cost genèric (CG) ........................... 63 4.5.1.3 Contingència .............................. 65 4.5.1.4 Imprevistos ............................... 66 4.5.1.5 Pressupost inicial del projecte .................... 66 4.5.2 Control ...................................... 67 4.6 Sostenibilitat i compromís social ............................ 68 4.6.1 Autoavaluació ................................... 68 4.6.2 Impacte econòmic ................................ 69 4.6.3 Impacte ambiental ................................ 69 4.6.4 Impacte social .................................. 70 Referències 71 Apèndix 73 A Diagrama de Gantt .................................... 73 vi Índex de figures 1 Usuari provant una aplicació de visualització de models volumètrics a un entorn de realitat virtual immersiu. ................................ 2 2 Visualització de models volumètrics ........................... 3 3 Procés de visualització de models volumètrics. Font: Herrera, 2020.......... 4 4 Funcionament de l’algorisme de raycasting. Font: Engel, 2006............. 5 5 Arquitectura d’una GPU ................................. 7 6 Segmentació per threshold ................................ 7 7 Interfície de segmentació ................................. 9 8 Dispositius de RV ..................................... 9 9 HTC Vive ......................................... 10 10 Fil d’execució de l’aplicació original ........................... 13 11 Segmentació en tres parts d’un model d’un crani. ................... 16 12 Exemple d’execució d’un region growing basat en threshold ............. 17 13 Pipeline segmentació per CPU. ............................. 18 14 Editor personalitzat de Unity3D ............................ 19 15 Integració de la funcionalitat de segmentació ..................... 19 16 Exemple de les limitacions de la segmentació per threshold .............. 20 17 Model volumètric d’un queixal, segmentat. ....................... 21 18 Gràfic del Profiler de Unity. ............................... 21 19 Profiler de Unity3D. ................................... 21 20 Temps d’execució de la segmentació per threshold a la CPU ............. 22 21 Temps d’execució d’un region growing basat en threshold a la CPU. ........ 22 22 Partició d’una textura 3D d’un model volumètric en llesques. ............ 25 23 Relació entre el nombre de grups de threads i la mida dels grups. .......... 27 24 Pipeline de la funcionalitat de segmentar regions d’interès d’un model volumètric. . 30 25 Compute shader que implementa la segmentació per llindar d’un vòxel. ....... 31 vii 26 Mètode per configurar i executar un compute shader mitjançant l’API de Unity3D. 32 27 Pas de paràmetres al fragment shader.......................... 33 28 Implementació de la segmentació per llindar a un fragment shader.......... 34 29 Pipeline de la segmentació per region growing diffusion-based a la GPU. ...... 35 30 Rendiment del còmput de la segmentació per threshold amb un compute shader.. . 36 31 Temps d’execució de la segmentació per regió basada en difusió. Compute shader . 37 32 Temps d’execució de la segmentació per threshold utilitzant un fragment shader.. 38 33 Temps d’execució de la segmentació per regió basada en difusió. Fragment shader.38 34 Inspecció d’un model volumètric en un entorn de RV immersiu. ........... 39 35 Mapa de botons del controlador del dispositiu de RV immersiu HTC Vive. ..... 40 36 Esquema d’interacció de la nostra aplicació. ...................... 40 37 Esquema de la metàfora d’interacció. .......................... 41 38 Inspecció d’un model volumètric fent ús d’una metàfora d’interacció. ........ 42 39 Inspecció d’un model volumètric per posar-hi llavors. ................. 43 40 Interacció amb una metàfora de segmentació que implementa un pla de clipping.. 44 41 Màquina d’estats de la metàfora de segmentació que implementa un pla de clipping.45 42 Posada de llavors a un model volumètric mitjançant la metàfora del pla de clipping.45 43 Test: Interacció amb el pla de clipping. ......................... 46 44 Test: Plantat de llavors. ................................. 47 45 Test: Creixement de la segmentació 1. ......................... 48 46 Test: Creixement de la segmentació 2. ......................... 49 47 Test: Creixement de la segmentació 3. ......................... 50 48 Test: Creixement de la segmentació 4. ......................... 51 49 Diagrama de Gantt, part 1. ............................... 73 50 Diagrama de Gantt, part 2. ............................... 74 51 Diagrama de Gantt, part 3. ............................... 74 52 Diagrama de Gantt, part 4. ............................... 75 viii volumètric, sobretot en una aplicació de diagnosi mèdica, ja que generalment els valors que es llegeixen dels models són valors de densitat (intensitats). És per això que durant el procés de visualització s’utilitzen les funcions de transferència, les quals assignen un color i opacitat a cada píxel del model volumètric en funció d’unes propietats concretes. Figura 4: Funcionament de l’algorisme de raycasting. Font: Engel, 2006. 1.4.2 Segmentació La segmentació (o etiquetatge) d’imatges és el procés de dividir una imatge en regions que no es creuen, de manera que cada regió sigui homogènia respecte a algun criteri de similitud predefinit (Schenke, Wünsche i Denzler, 2005). Les aplicacions de la segmentació van des de la visió per computador fins a l’anàl·lisi d’imatges mèdiques, que generalment implica un conjunt de dades d’imatges en 3D (segmentació de volum). És possible categoritzar els mètodes de segmentació en tres classes: •Els mètodes basats en píxels (pixel-based methods) classifiquen cada píxel basant-se en el seu valor característic utilitzant histogrames o altres mesures d’informació global. •Els mètodes basats en la frontera (edge-based methods) utilitzen informació de les arestes i funcions de càlcul de cost mínim per poder determinar i delimitar regions homogènies. •Els mètodes basats en regió (region-based methods) construeixen els límits dels objectes utilitzant criteris predefinits de similitud per determinar quins píxels han de pèrtanyer a una 5 certa regió. En el marc d’aquest projecte es desenvoluparà una versió clàssica basada en regió, ja que es presenta com un algorisme bàsic però útil per a treballar amb estructures anatòmiques de difícil accés, a més, tenint en compte que el projecte del qual partim no disposa de cap eina de segmentació, és adient incorporar els algorismes més bàsics i versàtils encara que existeixin d’altres molt més sofisticats per segmentar estructures anatòmiques concretes, ja es que vol disposar de quelcom d’un abast més ampli. Més endavant se’n donaran més detalls. 1.4.2.1 GPU vs. CPU Les GPU programables ofereixen un major poder computacional que les CPU ja que han estat dissenyades explícitament per al processament simultàni de múltiples primitives, que poden ser tractades paral·lelament amb independència. Per altra banda, les GPU ofereixen un conjunt més reduït d’instruccions i els shaders estan més limitats alhora de prendre i treballar amb memòria i informació global, que a més poden veure’s obligats a haver d’accedir-hi vàries vegades, fet que pot suposar una pèrdua de rendiment. Molts algorismes de segmentació es basen en calcular dinàmicament estadístiques de les imatges, díficil d’implementar a la GPU. N’és un exemple l’ús d’histogrames de les imatges, que requereixen construir una taula amb el nombre de píxels per cada valor de gris en un interval d’interès. Un mètode senzill per aconseguir això és llegir el valor de gris d’un píxel i incrementar un comptador corresponent al valor de gris a la taula. Això requereix fer escriptures a memòria, que suposa una forma de dispersament de memòria i és impossible fer-ho des d’un fragment processor. És per aquest motiu entre d’altres (Schenke, Wünsche i Denzler, 2005), que molts algorismes estan dissenyats híbridament per portar els càlculs complicats per a una GPU a la CPU. 1.4.2.2 Implementacions per GPU En aquest punt és important saber quins mètodes basats en GPU exsiteixen. Sabem que estan dissenyats per oferir solucions basades íntegrament en GPU que ofereixen una millora important respecte a les solucions basades íntegrament en CPU. Conèixer quins són, com funcionen i les limitacions que presenten en ajudarà a enfocar la nostra implementació i a valorar si és necessària o pot ser útil una implementació híbrida d’aquests amb la CPU. A Smistad et al. (2015) es defineixen els paràmetres per avaluar l’eficiència d’un algorisme implementat per GPU. Sense entrar en detall per no excedir l’extensió del document, aquests paràmetres són el (I) paral·lelisme de dades, el (II) nombre de threads, la (III) divergència de branques, l’ (IV) ús de memòria i la (V) sincronització. A la figura 5es pot veure de forma genèrica l’arquitectura d’una GPU. 6 Figura 5: Disposició general d’una GPU i la seva jerarquia de memòria. Font: Smistad et al., 2015 Generalment, un algorisme obtindrà un bon rendiment de la GPU si és data parallel, té molts threads, no té molta divergència de branques, utilitza menys memòria de la total de la GPU i si utilitza la mínima sincronització possible. A continuació es presenten dos mètodes molt populars a la literatura per la seva simplicitat, la qualitat dels resultats que ofereixen i el seu rendiment. La segmentació per threshold (veure figura 6) consisteix en renderitzar o descartar cada vòxel basant-se en el seu valor d’intensitat utilitzant un o més thresholds. Aquest mètode és completament data parallel, ja que cada vòxel es classifica independentment dels altres, i no requereix de sincronització. El nombre de threads que calen equival al nombre de píxels o vòxels. Encara que presenti divergència de branques, el mètode és massa simple, i l’ús de memòria que fa és baix, ja que només necessita espai per guardar la segmentació resultant (Smistad et al., 2015). Figura 6: Segmentació per threshold d’un escaneig per CT. La intensitat de cada vòxel del volum d’entrada és comparada amb el valor de llindar. Si aquest és major que el valor de threshold el vòxel és segmentat com a part del vas sanguini. La segmentació resultant s’utilitza per generar el volum 3D que se li presenta a l’usuari. Font: Smistad et al., 2015. Un altre mètode de segmentació molt popularitzat és el seeded region growing. Aquest mètode comença amb un conjunt de píxels llavor que són coneguts de pertànyer a un objecte d’interès. A partir d’aquestes llavors, les regions que contenen l’objecte d’interès s’aniran extenent pels píxels veïns si aquests satisfan alguns criteris predefinits. Aquest mètode és similar a la cerca en amplada, 7 i és especialment útil quan el fons i la regió d’interès tenen intensitats de píxels que es sobreposen, i estan separats en l’espai per un mur o una altra regió. Un exemple és una CT de tòrax, on els vòxels de les vies respiratòries i de la parènquima tenen una intensitat baixa, i estan separades per un teixit de sang amb intensitat alta. Region growing permet la paral·lelització de dades, ja que tots els píxels al voltant de la vora de la regió a segmentar són evaluats amb la mateixa instrucció. Per altra banda, a mesura que la vora creix, el nombre de threads canvia. Això és problemàtic perquè modificar el nombre de threads típicament implica tornar a carregar el kernel4, fet que suposa llegir valors de la memòria global un altre cop. Això introdueix divergència de branques, a més, es necessita sincronització, que també limita la velocitat. L’ús de memòria és baix (2N), ja que necessita les dades d’entrada i la informació de la segmentació resultant (Smistad et al., 2015). Per conduir el lector al següent apartat, volem destacar que la segmentació té dos objectius fonamentals segons Preim i Botha (2013): (I) identificar els objectes rellevants, és a dir, reconèixer diferents parts particulars d’una estructura anatòmica; (II) aquests objectes han d’estar ben delimitats, és a dir, els seus contorns han d’especificar-se amb molt bona precisió. El reconeixement (I) és una tasca que generalment les persones poden realitzar amb millors resultats que les màquines, mentre que la delimitació (II) és una tasca on la precisió n’és un tret essencial. D’aquesta manera el repte de la segmentació és saber combinar la destresa de l’usuari amb el potencial d’un ordinador. Els diferents mètodes exposats depenen de paràmetres definits per l’usuari per al seu funcionament. Els articles consultats, més enllà d’explicar l’algorisme, proposen mètodes d’interacció amb els volums per tal de poder definir bé aquests paràmetres i obtenir bons resultats. Tots aquests mètodes d’interacció requereixen a l’usuari interactuar amb el volum a través d’una pantalla i marcar els paràmetres de l’usuari a través d’un punter controlat amb el ratolí. Aquesta interacció pot arribar a ser feixuga quan es pretén segmentar objectes o regions que presenten una topologia més complexa o que intersecten amb altres objectes. A la figura 7es poden veure algunes aplicacions proposades pels articles amb els quals ens basarem per a la implementació de la segmentació, més detallat a la següent secció. 1.4.3 Realitat virtual La RV és una simulació interactiva per computador des del punt de vista del participant, a la qual se substitueix o s’augmenta la informació sensorial que rep. Els elements bàsics que han d’estar presents a qualsevol sistema de RV són el modelatge digital en 3D, la visualització interactiva, la interacció implícita i la immersió sensorial (Department of Computer Science, 2020). Els dispositius de RV es poden classificar en dues classes: semi-immersius o immersius. Els primers 4Denominem kernel a un conjunt d’instruccions que s’han d’executar sobre una única dada. 8 (a) Font: Schenke, Wünsche i Denzler, 2005 (b) Font: Sherbondy, Houston i Napel, 2003 Figura 7: Exemples d’interfície que es proposen als articles corresponents. En aquestes propostes la interacció es realitza sobre les imatges mèdiques (interacció 2D). Volem avaluar com realitzar la segmentació directament sobre un model volumètric 3D, i per tant haurem d’adaptar la interfície dissenyada originalment a un entorn 3D. disposen d’una o més pantalles estèreo que simulen la presència d’objectes en un entorn des del punt de vista de l’usuari. Els segons consisteixen en disposar les pantalles davant dels ulls de l’usuari, de manera que cada ull veu una imatge lleugerament diferent, creant un efecte estereoscòpic. Les figures 8.a i 8.b mostren un sistema de RV immersiu i semi-immersiu, respectivament. (a) Sistema de RV immersiu. (b) Sistema de RV semi-immersiu. Figura 8: (a) Dispositiu de RV immersiu HTC Vive que disposa el centre de recerca ViRVIG. (b) Sistema semi-immersiu en anatomia humana, del ViRVIG. Font: (Department of Computer Science, 2020). 9 En el marc d’aquest projecte, l’eina de RV ja mencionada HTC Vive que utilitzarem es tracta d’un dispositiu de RV immersiu. Aquest consta d’un monitor muntat al cap (HMD - head mounted display), que és el principal dispositiu de sortida de les dades, i permet veure l’entorn de RV. També disposa d’un o més comandaments que funcionen com a dispositius d’entrada juntament amb l’HMD, que també envia informació a l’aplicació com la posició i orientació del cap (veure imatge 8a). Tota la interacció amb l’entorn virtual es pot fer amb la gesticulació de braços i mans. A més, l’usuari també es pot moure per l’entorn per tenir punts de vista des de l’interior del model, per exemple. Els comandaments també ofereixen botons i altres elements de control, com un gallet, un joystick, etc. A la figura 9es pot veure amb més detalls els components del dispositiu de RV HTC Vive. Figura 9: Lot estàndard del dispositiu immersiu HTC Vive. Font: H. Corporation, 2020 L’avenç i millora dels sistemes de RV (veure secció 1.4.3) dels últims anys ha portat al mercat eines d’immersió d’ús genèric i fàcilment adquiribles gràcies a la reducció de costos de la producció. Com s’ha comentat anteriorment, el centre de recerca ViRVIG disposa d’un entorn de RV creat amb el motor gràfic Unity3D i que utilitza el dispositiu HTC Vive, que permet carregar i interactuar amb models volumètrics creats a partir d’imatges mèdiques. Pensem que podem mirar d’aprofitar aquestes eines per oferir als usuaris una millor experiència d’interacció amb els volums per a poder realitzar la segmentació, i comprovar si utilitzar un dispositiu de RV pot aportar més comoditat alhora de tractar amb els models a segmentar. És un fet que haurem d’avaluar la nostra proposta i comparar-la amb les que ja existeixen, que utilitzen tècniques d’interacció en 2D. 2 Abast i obstacles 2.1 Objectius i subobjectius L’objectiu d’aquest TFG és dotar l’aplicació del grup de recerca ViRVIG de tècniques bàsiques de segmentació de forma interactiva en un entorn de RV immersiu. Els mètodes seleccionats són dels més bàsics i utilitzats per qualsevol aplicació orientada a la inspecció i edició de models volumètrics, si més no, la versió per CPU de la segmentació per threshold i el region growing basat en threshold. És per aquest motiu que tenir a disposició aquests mètodes pot ser molt útil per 10 a futures investigacions dutes a terme pel grup de recerca en el mateix marc que descriu aquest projecte. Volem implementar els dos algorismes de segmentació de volums esmentats a secció anterior (1.4.2.2) i integrar-los al projecte ja en producció, partint de la solució per a la visualització de models volumètrics en un entorn de RV controlat amb el dispositiu HTC Vive (Sànchez, 2017). Concretament, es donarà una solució de seeded region growing basat en difusió implementada a la GPU publicada a Sherbondy, Houston i Napel (2003), i una solució híbrida que utilitza segmentació per threshold i un seeded region growing, també presentada per ser implementada íntegrament a la GPU (Schenke, Wünsche i Denzler, 2005), ja que pensem que són mètodes que poden ser útils com a eina de segmentació interactiva en un entorn de RV. Durant el procés d’implementació, s’adaptaran les solucions descrites per ser executades híbridament entre la CPU i GPU, de manera que es tindran més models per comparar-ne l’eficiència. Un cop es tinguin les solucions funcionals, es plantejarà aprofundir en adaptar o modificar la interacció del projecte actual per facilitar (si és necessari) la tasca de segmentació. Concloem aquest apartat oferint un llistat que formalitza el què acabem de comentar: •Objectius –Seeded region growing per difusió implementat a la GPU. –Seeded region growing basat en threshold implementat a la GPU. •Subobjectius –Adaptar les implementacions de forma híbrida (CPU - GPU). –Oferir millores d’interacció amb l’aplicació, si escau. 2.2 Obstacles Un dels problemes amb els que ens podem trobar és que, el motor gràfic i el dispositiu de RV utilitzats són productes de llicència privada. Això dificulta l’abstracció d’informació d’altres articles que proposen solucions similars, ja que poden treballar amb altre software que utilitzi APIs diferents, fet que pot canviar la representació del model de dades i l’enfoc de les implementacions. A part dels dos algorismes que s’implementaran en aquest projecte, existeixen altres solucions per la tasca de segmentació. Això provoca una gran diversitat d’implementacions que podem trobar fent més recerca, moltes d’elles pensades per segmentar estructures més específiques, mentre que nosaltres pretenem oferir una solució genèrica i adaptable a cada problema. Així doncs optarem per prendre els algorismes més populars i referenciats i adaptar-los a l’entorn sobre el qual treballarem. 11 Aquest projecte requereix de l’ús de material proveït pel grup de recerca ViRVIG per a les proves amb l’entorn de RV. La situació d’emergència sanitària actual no és prou estable com per garantir la total llibertat d’ús d’aquest material. El projecte desenvolupat al motor Unity3D ofereix un mode de simulació sense RV que, encara que no pot oferir els mateixos resultats, servirà per comprovar la funcionalitat dels mètodes a implementar. 2.3 Riscos Serà molt important tenir cura amb la implementació de les solucions, ja que com s’ha mencionat, region growing és un algorisme costós. Es tindrà molt en compte els detalls per tal de d’obtenir solucions en temps real i poder realitzar més proves fàcilment i poder afegir, si són necessàries, les millores d’interacció. Cal tenir en compte que les aplicacions que s’executen en entorns de RV requereixen una velocitat de refresc mínim de 60 fps (Sànchez, 2017) per tal que l’experiència de l’usuari sigui bona, ja que l’alta latència pot implicar marejos. Un altre risc amb el què ens podem trobar és que, malgrat la pujada de popularitat dels sistemes de RV, aquests han anat molt destinats a l’entreteniment, de manera que metges i estudiants no solen trobar-se amb aquestes eines alhora de treballar. Això pot provocar que encara que per nosaltres sigui fàcil fer proves d’interacció amb la solució proposada, aquesta tingui una corba d’aprenentatge més llarga, i no pugui suposar una solució eficaç per la comunitat a la que va destinada. Intentarem poder realitzar proves d’usabilitat amb agents externs per comprovar l’efectivitat de la interacció. 3 Desenvolupament del projecte Aquesta secció conté tots els detalls de la implementació de la solució presentada fins ara. S’han identificat tres topics centrals que utilitzarem per explicar tot el procés de desenvolupament de l’aplicació. Concretament, a 3.2 i3.3 es donaran detalls dels algorismes de segmentació implementats per ser executats íntegrament a la CPU i a la GPU, respectivament. A 3.4 es donaran detalls de les dues metàfores d’interacció que s’han implementat per provar l’aplicació. A cada secció es donarà una definició formal del problema que estem tractant (3.2.1,3.3.1 i3.4.1, respectivament) i s’explicarà com l’hem implementat a l’entorn gràfic de Unity3D (3.2.2,3.3.2 i 3.4.2, respectivament). Per la part de la implementació dels algorismes (3.2 i3.3) també es donaran detalls de proves de rendiment que ens han permès avaluar l’escalabilitat de la nostra aplicació. Començarem, però, explicant els aspectes més importants de l’aplicació de la qual partim, explicada amb més detall a Sànchez (2017), ja que el seu enteniment ha estat molt important per poder implementar la nostra solució. 12 3.1 Visualització de models volumètrics L’aplicació core d’aquest projecte compleix la tasca de visualitzar (renderitzar) el model volumètric que un usuari ha escollit. L’algorisme de visualització és un Muli-pass Raytracing que es realitza íntegrament a la GPU. Aquest consisteix en un fragment shader on s’envia tota la informació necessària per poder assignar a cada vòxel del volum una opacitat i un color utilitzant un algorisme de raycasting (Engel, 2006) que consulta una funció de transferència per obtenir aquests valors. La figura 10 mostra el pipeline simplificat de l’aplicació original. Figura 10: Fil principal d’execució de l’aplicació. Podem veure que les dades d’entrada són el model volumètric (fitxer *.asset) i la funció de transferència (fitxer *.plt). El fitxer VolumeRenderer.cs gestiona el model de dades de l’aplicació (textura d’intensitats del volum, informació de la segmentació i funció de transferència), i el fitxer VolumeRaytraceEffect.cs gestiona la lògica que s’enviarà als shaders que aplicaran l’algorisme de raycasting per visualitzar el model volumètric. Font: Herrera, 2020. Per interès d’aquest projecte, l’aplicació ofereix la possibilitat de visualitzar informació de segmentació del model volumètric si es carrega un Asset de Unity (Unity Software Inc., 2016) que conté l’etiquetatge dels vòxels del volum. En aquest cas, el pipeline comentat a la figura 10 assigna un shader (fitxer Raytrace-Segmentation.shader de la figura 10) que renderitzarà el vòxel segons l’etiqueta de segmentació. Aquest nou shader rep una segona textura 3D amb les etiquetes de cada vòxel (valors entre 0 i 255, normalitzats) i una textura 2D on cada posició conté els colors associats a les etiquetes corresponents (l’etiqueta 254 està reservada per indicar l’"absència de segmentació"). Així doncs, l’usuari podrà visualitzar les regions d’interès marcades per l’Asset de segmentació. Per la nostra part, ens podrem centrar en la tasca que ens pertoca sense perill de trencar la implementació original a l’hora d’integrar la nostra solució. 3.2 Segmentació per CPU L’ús de la CPU per a la implementació i execució d’algorismes de segmentació ha estat un pas essencial per iniciar el desenvolupament. La caracterització iterativa dels algorismes presentats fa que sigui senzill obtenir una primera versió de cada un d’ells, que ens ha ajudat a entendre el 13 seu funcionament (i les seves limitacions) i el model de dades que té l’aplicació de visualització de models volumètrics que estem utilitzant. 3.2.1 Formulació del problema Ens disposem a explicar amb més detall els dos algorismes de segmentació implementats en aquest TFG. Les característiques principals que es detallen sobre els algorismes a 3.2.1.1 i3.2.1.2 s’obviaran a la secció d’implementacions per GPU, que es centrarà en introduir els canvis que apareixen alhora de portar la implementació per a ser-hi executada (per a més informació, vés a 3.3). 3.2.1.1 Segmentació per llindar desenvolupat a la CPU Tal com s’explica a la secció 1.4.2.2, la segmentació per llindar (threshold) consisteix en decidir si un vòxel pertany o no a una estructura d’interès en funció de si el seu valor d’intensitat compleix uns requisits marcats per un o més valors de llindar. A la literatura hem trobat que existeixen diferents mètodes basats en threshold que es diferencien els uns dels altres en com relacionen els valors de threshold i els valors d’intensitat dels vòxels. Per exemple, a la figura 6es seleccionen aquells vòxels que tenen un valor d’intensitat major que el valor de threshold. En canvi, per altres models volumètrics o objectes d’interès ens podria interessar fer l’operació inversa. Pel nostre projecte, hem decidit treballar amb un rang de valors de threshold, de manera que es pugui treballar amb models volumètrics que presentin més de dos rangs d’intensitat, i poder així seleccionar aquelles regions d’interès que no presenten els valors d’intensitat més alts ni més baixos. És ben cert que ens podem trobar amb que alguns vòxels que pertanyen a una certa regió tinguin valors d’intensitat que són estrictament més grans o petits que els valors màxim o mínim de threshold, respectivament. Això sol passar sobretot quan aquests vòxels es troben a les fronteres entre dues o més regions d’interès. Per oferir més flexibilitat a l’algorisme davant d’aquest problema, es sol afegir una tolerància τal valor o valors de threshold. Pel nostre cas, aquesta tolerància serà un percentatge que indicarà quant més gran ha de ser el valor de threshold màxim i quant més petit ha de ser el valor mínim, respecte els valors originals. D’aquesta manera, la funció per decidir si cal etiquetar o no un vòxel serà la següent: _segmID(voxel) =      _selectedID _V olumeIntensity(voxel)∈[thresholdmin −τ, thresholdMAX +τ] _emptyID otherwise (1) La seva senzillesa limita el seu ús a certes modalitats d’imatges mèdiques (com la CT) i a estructures ressaltades prèviament per contrast (com el cas de la figura 6) o per segmentar regions d’interès 14 Figura 17: Model volumètric d’un queixal amb resolució 256x256x256, del qual se n’ha segmentat l’arrel mitjançant un region growing basat en threshold. Figura 18: Gràfic del Profiler de Unity. Figura 19: Un gràfic que mostra una trama del consum de CPU i GPU durant un conjunt de frames. Podem veure un pic quan s’està executant un algorisme de segmentació. 21 Figura 20: Temps d’execució de la segmentació per threshold a la CPU de models volumètrics de diferents resolucions. Elaboració pròpia. Figura 21: Temps d’execució d’un region growing basat en threshold a la CPU de models volumètrics de diferents resolucions. Elaboració pròpia. 22 La informació recopilada fins ara mostra que region growing es presenta no només com un algorisme més sofisticat sinó que més eficient que la segmentació per threshold, que encara que sigui més trivial, el fet d’haver de recórrer sempre tot el volum el fa més lent. De totes maneres, region growing tampoc escala bé quan augmentem el nombre de vòxels a visitar, i totes les proves d’execució dels algorismes per CPU han comportat una congelació del refresc de l’aplicació d’entre 10 i 15 segons. Concloem doncs, afirmant la inviabilitat d’implementat algorismes de segmentació per la GPU. A la següent secció veurem que com la GPU millora els temps d’execució. 23 3.3 Segmentació per GPU Com ja s’ha comentat a la secció 1.4, la capacitat de paral·lelització de les targetes gràfiques les converteix en una eina molt potent alhora de realitzar un nombre molt gran d’operacions si aquestes permeten, evidentment, el càlcul simultani. Com que les característiques fonamentals dels algorismes s’han explicat a la secció 3.2, aquí ens centrarem en explicar els conceptes claus per a portar les seves implementacions a la GPU (apartats 3.3.1.1 i3.3.1.2) i la difusió de Perona i Malik (Sherbondy, Houston i Napel, 2003) per al region growing, una variant més costosa però que ofereix millors resultats i més flexibilitat per decidir com creix la segmentació (3.3.1.3), ja que es presenta com un mètode que permet fer una segmentació interactiva. 3.3.1 Formulació del problema L’objectiu de portar la implementació dels algorismes de segmentació a la GPU és aconseguir etiquetar els vòxels en paral·lel, ja que com hem vist, el nombre d’iteracions i el pas d’informació de la CPU a la GPU és el què en penalitza els temps d’execució (de l’ordre de 10 a 15 segons amb la millor targeta gràfica que disposàvem al Centre de Realitat Virtual). Per altra banda, ens interessa treballar sense trencar el pipeline de l’aplicació original (veure figura 10). Primer veurem la solució que hem trobat a la literatura sobre com modificar la destinació d’un fragment shader per guardar-ne la sortida a una textura (3.3.1.1), després veurem l’ús de Compute Shaders (3.3.1.2) per simular aquesta tècnica com a solució a les complicacions que hem trobat al llarg del desenvolupament a l’haver d’utilitzar l’API de Unity3D per redireccionar la sortida de fragment shaders. 3.3.1.1 Render to Texture Aquest és el nom amb el que popularment es refereix a renderitzar una escena (o un determinat objecte) a una textura, en comptes de fer-ho directament a un dispositiu de sortida de la targeta gràfica. Aquesta tècnica consta de tres tasques: crear la textura on volem renderitzar;renderitzarhi alguna cosa; utilitzar-la (en el nostre cas, pel pipeline de visualització). Les diferents APIs que ens permeten configurar el pipeline de renderitzat de les GPU ofereixen versions diferents de la mateixa funcionalitat. Per exemple, a OpenGL cal crear un frame buffer (glGenFramebuffers(1,&fbo)) i assignar-lo com a actiu (glBindFramebuffer(GL_FRAMEBUFFER, fbo)) i crear una textura i assignar-la al frame buffer (glFramebufferTexture()) (Vries, 2021). DirectX ofereix una amigable interfície per obtenir el mateix procediment (CreateRenderTargetV iew()) (Soft, 2015). En el marc de la nostra aplicació volem projectar l’etiqueta de segmentació de cada píxel en una textura 3D, però sabem que la sortida d’un fragment shader només correspon a valors per un espai 24 (viewport) 2D, de manera que cal adaptar el procediment comentat per a renderitzar a la textura 3D llesca a llesca. La figura 22 mostra com podem concebre una textura 3D com a un conjunt de llesques (slices) de textures 2D. Figura 22: Partició d’una textura 3D d’un model volumètric en llesques. Veiem que podem concebre les llesques en qualsevol dimensió. Font: Benassarou et al., 2005. L’algorisme 3mostra la idea a seguir per aplicar la tècnica render to texture a una textura 3D. L’objectiu és que per cada slice de la textura 3D on volem renderitzar (el render target), cridem a pintar un quadrat que ocupi tot l’espai de renderitzat. Com que pels algorismes que estem desenvolupant necessitem les coordenades de la textura del volum (una textura 3D), amb cada vèrtex que volem pintar enviem les coordenades de la textura 3D del volum, on la coordenada z dependrà de la slice que estem visitant. A la secció 3.3.2 mostrarem amb més detall com hem implementat aquesta tècnica amb l’API que ofereix Unity3D. 3.3.1.2 Compute Shaders i Compute Buffers Un compute shader és un shader programable que expandeix la progrmació a les targetes gràfiques més enllà de la tasca de renderitzar. Ofereix un sistema de computació de propòsit general d’alta velocitat aprofitant la capacitat de paral·lelització de les GPU. També implementa mecanismes de memòria compartida i sincronització de threads per oferir més flexibilitat alhora de dissenyar i implementar mètodes de programació en paral·lel. Aquest projecte implementa els algorismes de segmentació amb compute shaders utilitzant l’API de Microsoft Direct3D 11 (Microsoft, 2018), però els conceptes que presentarem en aquest apartat es poden relacionar fàcilment amb les solucions que ofereixen altres API, com OpenGL (Khronos, 2019). La idea fonamental per treballar amb compute shaders recau en dos paràmetres: el nombre de grups de threads a executar (es defineix des de l’aplicació), i el nombre de threads que tindrà cada grup (es defineix quan es declara un kernel al compute shader). El primer es defineix cridant a un mètode ID3D11DeviceContext::Dispatch que permet definir tres dimensions de grups de threads. Des de la versió 11 de Direct3D, es poden definir fins a un màxim de 65535 grups de threads 25 Algorithm 3 Render To (3D) Texture. O(V0s z dimension resolution) 1: V←V olumeTexture 2: S . texture that will contain segmentation labels 3: for i= 1,2, . . . , V.resolution.z do 4: slice =i 5: GraphicsAPI.SetRenderT argetMethod(texture :S, slice).your API’s method to set render target 6: z=clamp(0,1,slice V.resolution.z−1 7: GraphicsAPI.Draw(QUAD).your API’s method to draw 4 vertexs. 8: GraphicsAPI.SendV ertex(0,0,0) 9: GraphicsAPI.SendTexCoord(0,0, texCoordZ) 10: GraphicsAPI.SendV ertex(1,0,0) 11: GraphicsAPI.SendTexCoord(1,0, texCoordZ) 12: GraphicsAPI.SendV ertex(1,1,0) 13: GraphicsAPI.SendTexCoord(1,1, texCoordZ) 14: GraphicsAPI.SendV ertex(0,1,0) 15: GraphicsAPI.SendTexCoord(0,1, texCoordZ) 16: GraphicsAPI.EndDraw() 17: end for per cada dimensió5. A partir d’aquí, per cada grup definit per la funció Dispatch, s’executen en paral·lel el nombre de threads que indica el kernel, també definit com un paràmetre de tres dimensions. Cada grup de threads que s’executa en paral·lel tindrà accés a recursos compartits només dins de la seva regió. Les API solen oferir modificadors per fer un recurs compartit entre tots els grups de threads. A més, podem definir el mètode inicial del nostre kernel perquè rebi un o més paràmetres, entre els quals hi ha l’identificador del grup (SV _GroupID), l’identificador del thread dins del grup (SV _GroupThreadID), i l’identificador del thread d’entre el nombre total de threads que es crea amb la crida al Dispatch (SV _DispatchT hreadID). La figura 23 mostra un exemple del què acabem d’explicar. El mètode principal d’un compute shader no retorna cap valor, de manera que a diferència de la tècnica explicada a la secció anterior (3.3.1.1), hem d’explicitar al nostre kernel que després de fer les operacions pertinents guardi el resultat on li pertoca per la nostra aplicació: la textura de segmentació. Per aconseguir-ho, podem declarar la textura com un objecte de tipus UAV (unordered-access view), de manera que podem llegir i escriure directament sobre la textura com si fos una estructura de dades convencional, tenint en compte que cal fer-la visible coherentment entre els threads, de manera que diferents grups puguin veure les escriptures d’altres. A part d’aquest ús que ofereixen les textures, els UAV també poden ser referenciats com a búffers d’un mateix 5A la versió 10 el nombre màxim de grups de threads per la dimensió "z"és de 1. 26 Figura 23: Exemple que mostra la relació entre els paràmetres del mètode Dispatch i de l’atribut numthreads d’un kernel d’un compute shader. Font: Microsoft, 2018. 27 tipus definit pel desenvolupador. Es va provar la solució que presentem a 3.3.2 amb l’ús d’aquests búffers, però no suportaven la mida per guardar la informació de tot el model volumètric. Vam concloure que podem cridar a executar els nostres compute shaders, on el nombre de threads de cada dimensió sigui equivalent a la resolució de cada dimensió (respectivament) del model volumètric que volem segmentar. Al compute shader calcularem l’etiqueta del vòxel que determina el paràmetre SV _DispatchT hreadID. Un cop sabem quin vòxel estem visitant, guardarem el resultat a la textura de segmentació, que té reservat un índex per emmagatzemar la informació de segmentació del vòxel.6. 3.3.1.3 Region Growing diffusion-based El criteri de segmentació per llindar vist fins ara consisteix en una decisió binària que dificulta la interacció de l’usuari amb l’evolució de la segmentació de l’algorisme basat en regió. L’usuari no pot corregir aquesta evolució fins que no veu que algun determinat vòxel s’ha etiquetat. La mètrica de difusió no lineal de Perona i Malik (Perona i Malik, 1990) que proposa Sherbondy et al. (2003) consisteix en expandir les llavors per regions d’intensitat similar, mentre es redueix l’expansió de la difusió davant de gradients alts (Sherbondy, Houston i Napel, 2003). Representem S(t, x, y, z)com el valor de la difusió d’un determinat vòxel a la posició (x, y, z)a un determinat instant de temps t, on t= 0 és l’estat inicial (amb les llavors col·locades per l’usuari) iV(t, x, y, z)com el valor d’intensitat d’aquest vòxel. L’equació 2mostra la difusió que governa l’expansió de les llavors: δS(t, x, y, z) δt =div(g(|∇V(t, x, y, z)|)∇S(t, x, y, z)) where g(s) = ν×exp −s2 K2 (2) Veiem que la difusió obté un valor escalar del camp vectorial que forma els valors d’intensitat del model volumètric. S’afegeixen les constants Kiνper controlar la velocitat de g(s)a tendir a 0 davant de gradients alts i regular la sensibilitat davant del soroll i la velocitat d’agrupar objectes propers a les llavors inicials, respectivament. Es discretitza l’equació 2al fragment shader seguint el model eulerià. L’equació 3mostra la discretització de la dimensió x: Sn+1 i=Sn i+h×((Sn i+1 −Sn i)×g(Vi+1 −Vi ∆x)−(Sn i−Sn i−1)×g(Vi−Vi−1 ∆x) where Sn i≈S(n×∆t, i ×∆x), Vi=V(i×∆x),0≤n≤N, 0≤i≤W, ∆x= 1/W, i h = ∆t/∆x2. (3) 6Com s’ha vist a 3.1, l’aplicació de visualització de models volumètrics utilitza una segona textura (de la mateixa resolució) per guardar la informació de segmentació de cada vòxel. 28 La discretització compta amb els sis veïns del vòxel que s’està avaluant. Nés el nombre total d’iteracions de l’expansió de la segmentació, i Wés la resolució de la dimensió xde la textura d’intensitats del volum. Explicitar la discretització a la GPU també redueix el temps de comunicació amb la CPU per l’intercanvi de paràmetres. Presentem a l’algorisme 4un pseudo-codi del funcionament de la segmentació per creixement de regió aplicant el criteri de difusió. Veiem que aquest mètode comportarà un creixement molt més lent de la segmentació, és per això que es sol afegir un criteri de parada per donar control del nombre d’iteracions a l’usuari, però també es pot implementar un mecansime per fer saber a la CPU que la difusió porta un nombre considerat d’iteracions sense canviar l’etiqueta de cap vòxel. A la secció 3.3.2 veurem com ho fem amb la nostra aplicació. Algorithm 4 Region Growing basat en difusió. 1: V←V olumeTexture 2: S . Diffusion values to 0, except for ones that are labelled as seeds (1). 3: thresholdmin,thresholdMAX ,τ 4: Q←seeds 5: while !Q.empty() || !stoppingCreiteria do 6: voxel ←Q.head() 7: for neighbour in voxel.neighbours() do 8: S[neighbour]←S[neighbour] + h×diffusion() .diffusion() is a function similar to equation 3. 9: if S[neighbour] == 1 then 10: Q.enqueue(neighbour) 11: end if 12: end for 13: if !voxel.AllNeighboursSeeded() then 14: Q.enqueue(voxel) 15: end if 16: end while 3.3.2 Integració amb Unity3D Hem pogut implementar els algorismes de segmentació mitjançant les dues tècniques descrites a la secció 3.3.1 gràcies al suport de l’API de Unity3D per treballar amb programes escrits per ser executats a la GPU, ja sigui per la configuració d’un fragment shader com per la configuració i execució de compute shaders. L’etiquetatge de la textura de segmentació es fa a la GPU abans d’executar l’algorisme de visualització que també la llegeix, de manera que es treu del pipline el pas de la textura actualitzada a la GPU (crida setPixels), que penalitzava la velocitat de refresc de l’aplicació. La figura 24 mostra el pipeline de l’aplicació amb la funcionalitat de visualitzar la 29 informació de segmentació modificada a la GPU. Figura 24: Pipeline de la funcionalitat de segmentar regions d’interès d’un model volumètric. Podem veure que tant el shader de visualització (Raytrace-Segmentation.shader) com els shaders que implementen els algorismes de segmentació utilitzen la mateixa textura de selecció. L’API de Unity3D ofereix la classe RenderTexture per treballar amb textures que poden ser escrites. El seu ús és molt comú per crear efectes sobre la visualització que capta la càmera de l’escena. Podem associar a una RenderTexture un format vàlid pel nostre controlador de la targeta gràfica i declarar-la com a UAV. La recerca de com fer un ús pertinent de l’API per implementar les tècniques descrites va ser un procés amb una corba d’aprenentatge lenta, ja que a la documentació es presenta com a ús avançat de l’API del motor gràfic sense entrar en molt detall del seu funcionament intern, i que la comunitat ha trobat que hi ha poc suport d’errors i millores entre les versions. Això s’acumulava amb la dificultat inicial del projecte de treballar amb conceptes que en la major part han quedat fora de l’abast de les assignatures de gràfics per computador del grau. Aquesta situació va fer difícil implementar la solució per render to texture, i es va optar primer per oferir la funcionalitat mitjançant compute shaders, ja que la seva condició de ser shaders de propòsit general fa que el seu funcionament es presenti més intuïtiu per començar a portar les implementacions a la GPU. 3.3.2.1 Implementació amb Compute Shaders La classe ComputeShader permet carregar, configurar i executar els algorismes de segmentació implementats amb aquesta metodologia. Concretament, podem enviar uniforms, saber el nombre de threads de cada grup definit pel kernel (ComputeShader::GetKernelThreadGroupSizes), i cridar a executar un nombre de grups per cada dimensió (ComputeShader::Dispatch()). Com s’ha comentat a la secció 3.3.1, podem concebre cada thread com al còmput de l’etiqueta de cada vòxel. La figura 25 és un exemple de com implementar aquesta tècnica per aplicar la segmentació per llindar, on podem veure que declarem la textura de segmentació amb el tipus 30 Figura 31: Rendiment de la segmentació per regió basada en el criteri de difusió, implementada fent ús d’un compute shader. davant l’augment de la resolució del model volumètric. 37 Figura 32: Temps d’execució de la segmentació per llindar utilitzant un fragment shader. Els temps d’execució són menors que els del mateix algorisme implementat amb compute shaders. Figura 33: Temps d’execució de la segmentació per region growing diffusion-based utilitzant un fragment shader. Els temps d’execució són menors que els del mateix algorisme implementat amb compute shaders. 38 3.4 Interacció La interacció juga un paper fonamental a una aplicació d’inspecció i diagnosi d’imatges mèdiques. Aquesta ha de permetre a un usuari accedir a les funcionalitats que ofereix. En el marc d’aquest projecte volem oferir mecanismes d’interacció per a poder etiquetar i visualitzar regions d’interès del model volumètric que s’està inspeccionant, tenint en compte que l’usuari es troba immers en una escena de realitat virtual. L’aplicació de visualització de models volumètrics de la qual parteix aquest projecte ja compta amb elements que permeten desenvolupar i integrar noves metàfores d’interacció. La figura 34 mostra la inspecció d’un model volumètric en un entorn de RV immersiu que ens ofereix l’aplicació de visualització que utilitzem. Concretament, l’usuari pot moure i rotar el model volumètric mentre prem el gallet del controlador que ofereix el dispositiu de RV, sempre que el comandament estigui ubicat dins del model. Aquesta metàfora és útil perquè permet la inspecció del model des de qualsevol angle de visió, sense la necessitat que sigui l’usuari el que es mogui per veure el model des del punt de vista desitjat; amb aquesta metàfora es permet modificar el punt de vista aplicant al model el moviment que l’usuari està realitzant amb el comandament. Figura 34: Inspecció d’un model volumètric en un entorn de RV immersiu. El raig que surt del controlador és una utilitat per millorar-ne la usabilitat. Permet saber a l’usuari cap a on està apuntant o dirigint el comandament. És una tècnica de feedback visual per l’usuari. La figura 35 mostra els diferents botons que ens ofereix el controlador d’HTC Vive, els quals utilitzarem per al desenvolupament de les nostres metàfores. 3.4.1 Formulació del problema Una metàfora d’interacció per a la funcionalitat de segmentar les regions d’interès d’un objecte ha de permetre a l’usuari afegir i treure llavors, i executar l’algorisme de segmentació. En el cas 39 Figura 35: Mapa de botons del controlador del dispositiu de RV immersiu HTC Vive. 1: Menú. 2: Joystick. 3: Menú d’Steam. 4: Estat del controlador. 5: Port de càrrega. 7: Gallet. 8: Agafada (Grip). de la segmentació per creixement de regió basat en la difusió, també interessa que l’usuari pugui decidir quan aturar l’expansió de la difusió, així pot beneficiar-se del caràcter interactiu d’aquest algorisme, a més de corregir per millorar el resultat de l’expansió. La figura 36 mostra els passos d’interacció per a dur a terme la segmentació. Com que la funcionalitat de segmentació més sofisticada de la nostra aplicació és la segmentació per creixement de regió basat en difusió, sempre que parlem d’interacció ho farem per a l’execució d’aquesta funcionalitat concreta, ja que les altres només requereixen de passos d’interacció molt bàsics (els quals formen part de la interacció global d’aquesta metàfora). Figura 36: Esquema d’interacció de la nostra aplicació que volem ofereixi per facilitar a l’usuari la tasca de segmentació. 40 3.4.2 Integració amb Unity3D Per reproduir els passos identificats a l’apartat anterior, s’ha definit el comportament de l’aplicació com una màquina d’estats que depèn de les accions de l’usuari. La figura 37 mostra aquesta màquina d’estats que canvia segons la configuració dels botons identificats a la figura 35, i permet estar en tots els estats descrits a la figura 36. Podem diferenciar dos tipus d’estats: els referents a l’estat d’execució de l’algorisme de segmentació, i els que fan referència amb l’addició o esborrat de llavors. Veiem doncs que l’usuari pot posar i treure llavors en tot moment (mentre tingui premut el gallet), i és decisió seva si vol fer-ho amb l’expansió de la difusió en funcionament o no. Figura 37: Esquema de la metàfora d’interacció que s’ha implementat per a la segmentació. Elaboració pròpia. 3.4.2.1 Metàfores d’interacció Per la tasca de posar i treure llavors, es proposen dues metàfores: la metàfora d’afegir llavors amb punter i la metàfora d’afegir llavors amb pla de clipping. La primera consisteix en disposar una esfera del tamany d’un vòxel del model volumètric a una distància del controlador determinada per l’usuari (mitjançant un paràmetre que actuï com a offset). Aquesta metàfora d’interacció és molt senzilla, ja que no permet posar llavors amb comoditat a totes les regions del volum. Per exemple, ens podem trobar amb regions molt internes del model, o potser d’altres que es troben naturalment contingudes dins d’altres estructures o ocultes per altres estructures des del punt de vista que s’està inspeccionant el model volumètric. Per resoldre aquest problema, la metàfora del pla de clipping retalla del contingut visible tota regió del model volumètric que es troba a una banda del pla definit segons la orientació del propi comandament. La figura 38 mostra un exemple d’inspecció d’un model volumètric en un entorn de RV immersiu fent ús de la metàfora del pla de clipping. Aquesta metàfora crida a una versió modificada del shader de visualització original, el 41 Figura 38: Inspecció d’un model volumètric en un entorn de RV immersiu fent ús de la metàfora del pla de clipping. qual descarta tots els vòxels que es troben per sobre del pla, en direcció a la normal positiva9. Quan l’usuari entra a l’estat per col·locar llavors (veure figura 37), la metàfora del punter dóna la llibertat de posar les llavors a qualsevol posició. Aquesta característica afegeix errors de precisió a l’hora de col·locar la llavor, ja que un usuari que no té dominada la sensibilitat de controlador veurà que li costarà posar les llavors a la posició que vol. Amb la metàfora del pla treiem un grau de llibertat quan l’usuari vol realitzar aquesta tasca. Per fer-ho, quan s’entra a l’estat Sembrant es congela el pla i es projecta l’esfera al punt d’intersecció de la direcció on apunta el controlador i el pla. Després de fer algunes proves, vam veure que podíem millorar la comoditat de treballar amb aquesta metàfora. Concretament, tenir la normal del pla amb la mateixa direcció que l’up del controlador comportava treballar amb l’amplada i profunditat com a graus de llibertat, mentre que és més fàcil interactuar amb l’amplada i alçada, com si l’usuari estigués pintant una paret vertical. És per això que es va afegir la funcionalitat de canviar la direcció de la normal del pla, per a què apuntés en la direcció (negada) amb la què apunta el controlador. Així, seguint la mateixa implementació, es descartarà tot píxel del model que es trobi entre l’usuari i el pla. D’aquesta manera, quan es volen posar llavors, es pot fer davant d’un pla vertical, millorant així la comoditat. La figura 39 mostra la visualització que es troba un usuari quan està posant llavors amb la metàfora del pla de clipping, on es pot apreciar que el shader tampoc evalua la funció de transferència pels píxels que es troben a la intersecció amb el pla, sinó que directament renderitza el valor llegint de la textura d’intensitats del volum, mostrant així una visualització de la imatge mèdica real que s’està utilitzant. Pensem que els pot ser de gran utilitat als professionals a qui va destinada aquesta aplicació, ja que estan més acostumats a treballar amb les imatges mèdiques originals. 9La normal del pla és el vector up del controlador 42 Figura 39: Inspecció d’un model volumètric en un entorn de RV immersiu, on s’ha entrat a l’estat per pintar/posar les llavors. El pla de clipping es troba fixat, de manera que l’usuari té dos graus de llibertat per decidir on vol col·locar les llavors. Noteu també que la normal del pla apunta a la direcció contrària al forward del raig del controlador. La figura 40 mostra l’opció de posar llavors sobre un pla congelat on la normal apunta a la mateixa direcció de l’up del controlador. Veient la posició a la que es troba el controlador, ja es pot deduir que és molt més còmode l’alternativa presentada. Finalment, vam haver voler sofisticar una mica més aquesta metàfora. La posició del pla fins ara respecte el controlador és sempre a la distància a la que es troba el centre de model volumètric. Quan la normal del pla apunta cap al controlador, no tenim forma de seleccionar vòxels de la tercera dimensió, ja que el pla es troba congelat al centre del volum. És per això que s’ha modificat la màquina d’estats que regeix la metàfora d’interacció amb pla de clipping, per poder afegir un desplaçament a la posició del pla calculada automàticament. La figura 41 mostra aquest canvi. 3.4.2.2 Altres Com s’ha comentat a l’explicació de la segmentació per creixement de la regió, el procés d’assignar les llavors és clau per al funcionament d’aquest. Per oferir comoditat a l’usuari, l’aplicació mostra en temps real les llavors que va col·locant l’usuari. La inviabilitat d’actualitzar la textura per CPU i enviar-la a la GPU que s’ha remarcat al llarg de la secció 3.2 ens ha obligat a optar per les mateixes tècniques descrites a la secció 3.3. En aquest sentit, s’envia a un shader un uniform que indica a quin vòxel l’usuari vol posar la llavor, de manera que de nou estem mantenint actualitzada la textura de segmentació a la GPU. La figura 42 mostra una escena de RV immersiva on l’usuari ha posat llavors a un model volumètric fent ús de la metàfora del pla de clipping. Finalment, s’ha volgut dotar d’una última utilitat a l’aplicació. Fent proves amb el creixament de 43 Figura 40: Interacció amb una metàfora de segmentació que implementa un pla de clipping. Es pot veure la rotació del controlador, que anuncia la incomoditat de treballar amb el pla fixat d’aquesta manera. la segmentació, hi ha molts casos que l’expansió creix ràpidament a zones on l’usuari sap que són incorrectes. Hem afegit la funcionalitat de poder posar llavors que anomenem tapes, les quals la seva etiqueta no canviarà en funció del valor de la difusió, i per tant permeten crear fronteres entre diferents regions del model volumètric i augmentar així la precisió del region growing. 44 Figura 41: Màquina d’estats de la metàfora de segmentació que implementa un pla de clipping, que permet modificar la distància a la què es troba el pla. Noteu que es reaprofita l’utilitat del Joystick. Figura 42: Posada de llavors a un model volumètric mitjançant la metàfora del pla de clipping. En aquesta imatge, s’està executant l’expansió de la segmentació amb el criteri de difusió. L’usuari segueix posant llavors mentre creix la regió de segmentació. 45 3.5 Resultats Afegim aquesta secció per ensenyar gràficament un procés complet de segmentació mitjançant la nostra aplicació. Les fotografies mostren un usuari utilitzant l’aplicació. El fons d’aquestes mostren el mateix contingut que està veient l’usuari. Les fotografies prenen tot el procés d’inspeccionar el volum, utilitzar la metàfora d’interacció per posar les llavors i veure com s’expandeix la segmentació en temps real. Figura 43: Test: Interacció amb el pla de clipping. 46 4 Gestió del projecte 4.1 Metodologia de treball i eines de seguiment 4.1.1 Metodologia La metodologia de treball seguirà el model àgil de cicles curts. Cada setmana es realitzaran una o dues reunions presencials (si és necessari, es realitzaran reunions telemàticament) amb l’Eva Monclús Lahoya, membre del grup de recerca ViRVIG i tutora d’aquest TFG, que s’encarregarà de l’assessorament més tècnic. Setmanalment s’establirà una feina a realitzar en una setmana vista, de manera que les reunions han de servir per aclarir dubtes, millorar la proposta del desenvolupador (que seré jo) i plantejar el següent objectiu. A més, al Centre de Realitat Virtual de la UPC, centre d’operacions del ViRVIG (Department of Computer Science, 2020), es podran fer les proves d’immersió amb l’aplicació per verificar la qualitat de la solució en cada etapa de la realització del projecte. La resta de feina es realitzarà des de casa, utilitzant l’eina Git (Conservancy, 2020) per al control de versions del software i per tenir el projecte sincronitzat amb l’ordinador connectat al dispositiu de RV que el centre de recerca posa a disposició. El desenvolupament de l’aplicació començarà primer per la implementació d’aspectes bàsics de segmentació per tal familiaritzar-me amb el codi del projecte actual, l’estil de programació exigit i l’entorn de RV. Tot el desenvolupament es dividirà en subobjectius que permetin fer testos i avaluar amb major freqüència la correctesa de la solució proposada en aspectes d’eficiència i usabilitat. D’aquesta manera plantejarem avaluacions parcials amb diferents membres del grup de recerca per tal d’obtenir feedback a les etapes inicials de la nostra proposta. Si la situació de pandèmia ocasionada per la COVID-19 ho permet, no descartem fer un test d’usuari a escala més àmplia on siguin usuaris de la comunitat mèdica les persones que avaluin la nostra proposta. 4.1.2 Seguiment Com s’acaba de comentar, la metodologia de treball emprada incentiva un contacte estret amb la tutora i permet un fàcil seguiment de l’avenç del projecte. A més el director del projecte, en Pere Pau Vázquez, s’encarregarà de la validació de l’assoliment dels objectius, de manera que amb ell també es realitzaran reunions presencials setmanalment. S’utilitzarà la plataforma web Trello (Altassian, 2020) per organitzar les tasques a realitzar, tenir un bon control del calendari i poder definir bé les fites a assolir (deadlines). Pel contacte telemàtic amb la tutora i director, tenim a disposició el servei de correu electrònic que ofereix la UPC, així com l’aplicació Google Meet (Google, 2020) per a les reunions i un canal d’Slack (Slack Technologies, 2020) per a converses que 53 requereixen un format de pregunta-resposta més ràpid. 4.2 Planificació temporal 4.2.1 Descripció de les tasques Aquesta secció pretén formalitzar tota la planificació prevista amb l’objectiu de tenir bona claredat respecte al volum i la càrrega de treball que comporta aquest projecte. Una bona definició prèvia de les tasques que cal realitzar per arribar a complir l’objectiu final del projecte ens ha permès tenir una visió clara de com hem de gestionar el temps de treball. El projecte es considera començat el dia 1 de setembre de 2020, i l’objectiu és considerar-lo acabat el dia 17 de desembre de 2020, que marca la data límit d’inscripció al torn de lectura del mes de gener, tot i que considerem que disposarem del temps entre la data límit d’inscripció i el dia del torn de lectura per si fos necessari acabar de lligar caps. Aquest interval consta de 108 dies, i es pretén dedicar entre 4 i 5 hores diàries. Els dies on es pot desenvolupar el projecte a l’espai de treball que ofereix el ViRVIG (Department of Computer Science, 2020) es podrà ampliar la jornada dedicada, ja que seran els dies que es dedicaran a les proves de correctesa i correccions especificades pel director o tutora. Els caps de setmana aniran enfocats a l’elaboració de la documentació requerida per la presentació del projecte. A continuació es donarà informació detallada de les tasques i com s’han organitzat, així com una explicació de la nomenclatura utilitzada. S’han definit un total de 32 tasques, algunes de les quals són considerades fites, que ens han servit per identificar els punts clau i crítics de tot el desenvolupament. Destaquem dos grans blocs dins del conjunt de tasques: la [GP] Gestió del projecte, i el [DP] Desenvolupament del projecte. Totes les tasques que integren cada un d’aquests blocs s’etiqueten seguint el format [xP.N], on Nés un nombre enter que identifica cada tasca. Les fites seguiran el format xP.F. Amb aquesta nomenclatura ha sigut molt fàcil identificar i assignar dependències entre les tasques, i es detallaran més aquelles que no segueixin el model Fi - Inici. També volem mencionar que al llarg de la planificació s’han marcat les reunions ([R] Reunió de seguiment) coincidint amb els dies de treball presencial pactats amb els responsables del projecte, tal i com s’ha explicat a la secció 4.1.2. [GP] Gestió del projecte La gestió del projecte és la fase que permet contextualitzar i definir l’abast del projecte, justificar-ne la necessitat i identificar totes les eines que faran falta per dur-lo a terme. S’estima una dedicació d’aproximadament 110 hores. També hem inclòs l’elaboració de la memòria final ([MEM] Elaboració de la memòria final), que es realitzarà durant l’etapa final del desenvolupament del projecte, però ens dóna més claredat 54 alhora de visualitzar el conjunt de tasques incloure-la dins de la gestió del projecte. S’estima una dedicació de 28 hores. [GP.1] Contextualització i abast Aquesta fase és el punt de partida del projecte. Permet la introducció de tots els elements que aquest requereix. En aquest punt es realitza una bona tasca de recerca per identificar el problema, entendre l’estat de l’art del camp que es tracta per justificar la solució que es proposa, i s’estableixen les pautes de metodologia i seguiment que s’utilitzaran al llarg del desenvolupament. La dedicació ha sigut d’aproximadament de 30 hores. [GP.2] Planificació Aquesta fase serveix per identificar totes les tasques, fites i punts crítics que intervenen en el desenvolupament del projecte. Aquesta tasca marca el camí per assolir l’abast definit a la fase anterior, i permetrà anticipar-se davant dels obstacles i riscos reconeguts a l’estudi previ. Una bona planificació des de l’inici ha de permetre poder-lo adaptar en fases del desenvolupament ja avançades, en cas que ens trobem davant d’un obstacle imprevist i sigui necessari optar per altres solucions. La dedicació ha sigut d’aproximadament 16 hores. [GP.3] Pressupost i sostenibilitat En el context d’aquest projecte, un cop se’n concep l’abast i la dedicació que requereix, haurem de quantificar-ne el cost tenint en compte el personal implicat i les eines i dispositius requerits, així com estimar el cost que puguin aportar els imprevistos que poden aprarèixer en fases més avançades. A més, es realitzarà un informe de sostenibilitat tenint en compte l’impacte medioambiental, econòmic i social del desenvolupament del projecte, així com de la producció i ús del material que utilitzarem. S’estima una dedicació de 14 hores a aquesta tasca. [GP.4] Elaboració del document final Aquesta tasca consistirà en fer un recull de les tasques anteriors, corregir els errors i afegir les millores suggerides pel tutor designat pel seguiment de la Gestió del projecte. En acabar aquesta tasca es tindrà un únic document amb tot el contingut mencionat anteriorment i es podrà complir amb la fita [GP.F] Entrega de l’informe de Gestió del projecte. Depenent dels canvis que calgui efectuar sobre la documentació, s’estima una dedicació màxima de 32 hores. Durant la realització de la gestió del projecte es faran reunions setmanalment amb el director i la tutora. Aquestes reunions seran d’entre 1 i 3 hores, un o dos cops a la setmana durant tota la fase 55 de la gestió del projecte. S’estima un cost temporal de 15 hores. [DP] Desenvolupament del projecte Aquesta secció engloba tot el procediment relacionat amb la implementació de la nostra aplicació. Veurem que la metodologia emprada estableix tasques que permeten fer-ne un seguiment setmanal, i la línia evolutiva del desenvolupament anirà des de la implementació de parts o eines enfocades a establir un primer contacte amb l’aplicació fins a la introducció de les noves funcionalitats que pretenem afegir. Al moment de la presentació d’aquest informe de seguiment, es preveu una dedicació final de desenvolupament de 368 hores, envers les 300 hores que es van preveure durant la fase inicial de planificació. A continuació es detallarà quins aspectes han canviat. Durant tot el procés de desenvolupament, es realitzaran reunions setmanalment amb el director del projecte, tal i com s’especifica a la secció de seguiment (vés a 4.1.2) d’acord amb la metodologia de treball escollida. Aquestes reunions generalment seran d’una hora. [DP.1] Formació i preparació Aquesta tasca ha consistit en la lectura de la memòria del projecte del qual partim (Sànchez, 2017), així com del codi font sobre el qual haurem d’implementar les nostres funcionalitats. Ha sigut molt important per entendre el model de dades de l’aplicació i com organitza les eines d’interacció per afegir-ne de noves. S’ha dedicat un temps d’unes 24 hores. [DP.2] Threshold Segmentation per CPU Aquesta tasca marca l’inici de la implementació de la nostra solució un cop s’ha assolit amb èxit l’objectiu de la tasca anterior. Aquest algorisme de segmentació és trivial (Schenke, Wünsche i Denzler, 2005), de manera que la seva implementació ha servit per poder jugar amb el model de dades, entendre com es guarda la informació dels vòxels i com accedir i modificar el seu etiquetatge. Encara que el temps dedicat a aquesta tasca no és superior a les 8 hores, el seu abast temporal ha estat major, ja que l’hem considerat acabada quan hem tingut implementat un sistema d’interacció bàsic ([DP.3] Interacció bàsica) per llegir la informació requerida dels vòxels i per aplicar l’algorisme i obtenir resultats visuals. [DP.3] Interacció Bàsica A l’inici del desenvolupament del projecte, es va planificar la implementació d’un sistema d’interacció bàsic per poder seleccionar els vòxels de les regions d’interès. Aquest procés és neccessari per obtenir les dades que necessiten els algorismes de segmentació. Aquesta interacció consistia en 56 disposar d’una esfera que servia per seleccionar els vòxels i obtenir-ne els valors d’intensitat per a llavors tenir el rang de threshold que utilitza la segmentació per a seleccionar o descartar la resta de vòxels. Un cop es van fer les proves de correctesa, vam veure que aquest mètode oferia poca usabilitat a l’usuari alhora de voler seleccionar vòxels que es troben molt endins del model volumètric, encara que afegíssim un paràmetre a la metàfora d’interacció per a poder determinar la distància a la que es troba l’esfera del controlador de l’usuari. Així doncs es va afegir una nova mètafora que hem anomenat pla de clipping. Aquesta ofereix a l’usuari un pla perpendicular a la direcció del dispositiu que controla l’usuari, i descarta renderitzar tots aquells vòxels que es troben a la direcció positiva de la normal del pla. Així l’usuari pot accedir amb més facilitat a zones internes del model volumètric. Aquesta nova metàfora també permet canviar la visualització del model volummètric, de manera que en comptes de visualitzar el model segons la funció de transferència, es pot visualitzar amb una escala de grisos pròpia d’una imatge obtinguda amb rajos X, oferint així a l’usuari una nova percepció de com és l’objecte d’interès. A més, l’esfera que marca els punts d’interès per l’usuari es troba sempre al punt d’intersecció entre la recta de direcció del controlador i el pla, de manera que l’usuari no ha de fer assajos per determinar a quina distància ha d’estar l’esfera per a poder seleccionar els vòxels de forma òptima, ja que simplement ha de posar el pla sobre la regió d’interès, i ja tindrà l’esfera preparada per marcar vòxels. El temps total de dedicació a la interacció ha sigut d’aproximadament 64 hores, envers les 8 que es van preveure quan només teníem intenció d’implementar l’esfera. Aquesta diferència és deguda a una altra tasca que es va afegir més endavant ([DP.3.4] Selecció i visualització de llavors per GPU), la qual explicarem a la secció que va originar el problema que aquesta soluciona (vés a 4.2.1). [DP.4] Region Growing per CPU Aquesta tasca és el primer punt clau del desenvolupament del projecte. La implementació per CPU és més senzilla que per GPU, de manera que aquesta fase ens portarà a un punt mig on podrem entendre el funcionament de la segmentació basada en regió, fet que pot facilitar en el futur la implementació que volem oferir per GPU. Aquesta tasca es desglossa en diferents fases de comprensió i disseny (DP.4.1, 10 hores) i d’implementació ([DP.4.2], 4 hores; [DP.4.3], 16 hores; [DP.4.5], 8 hores). Es marquen també dues fites ([DP.4.F.1] i[DP.4.F.2]) on es pretén realitzar proves de correctesa, que es preveu que requeriran una dedicació d’unes 4 hores cadascuna. Finalitzarem la tasca amb la realització de tests d’usabilitat ([DP.4.6]) que es poden dur a terme entre disseny, implementació i avaluació per part dels usuaris, en 28 hores. 57 [DP.5] Region Growing per GPU Aquesta tasca pretén adaptar l’algorisme dissenyat anteriorment per ser executat per la GPU. Aquest també es presenta com un punt clau del desenvolupament del projecte, ja que la implementació per GPU serà la base de l’estudi d’eficiència de la nostra aplicació. A la fase inicial del TFG aquesta tasca la vam desglossar en: •[DP.5.1] Lectura i comprensió de les especificacions sobre la implementació per GPU que ofereixen els articles dels quals partim (Sherbondy, Houston i Napel, 2003; Schenke, Wünsche i Denzler, 2005; Chen et al., 2006) i altres conceptes relacionats (N. Corporation, 2020). Temps previst: 16 hores. •[DP.5.2] Implementació de l’algorisme. Temps previst: 36 hores. •[DP.5.3] Possibles millores d’eficiència, combinar l’algorisme amb un threshold-based (Schenke, Wünsche i Denzler, 2005), etc. Temps previst: 24 hores. •[DP.5.F] Prova de correctesa. Fins al moment de començar amb aquesta tasca, totes les implementacions feien ús sencer de la CPU, des de la selecció de vòxels de l’usuari fins a la selecció de vòxels dels algorismes. Sense entrar molt al detall de la implementació, que es deixa per la memòria final, la segmentació guarda les etiquetes dels vòxels seleccionats en una textura de la mateixa ressolució que el volum. Quan volem veure visualment el resultat de la segmentació, hem d’indicar al motor gràfic (Unity Software Inc., 2016) que envii aquesta textura actualitzada a la GPU per a que el shader que s’encarrega de processar aquesta informació computi la imatge actualitzada. Aquest pas, tal i com s’indica a la literatura utilitzada (Smistad et al., 2015), és molt costós, i observàvem un augment de latència que bloquejava l’actualització (el main loop) de la nostra aplicació, fet problemàtic per vàries raons. Per una banda, l’usuari no pot veure en temps real quins vòxels està marcant, i cada cop que vulgui veure l’estat de la seva selecció ha de cridar a enviar la textura actualitzada i veure com l’aplicació es congela durant 1 o 2 segons. Per altra banda, region growing és un algorisme iteratiu, de manera que és interessant poder veure com evoluciona la segmentació per detectar si l’algorisme està etiquetant vòxels que no pertanyen a la regió d’interès i d’alguna manera limitar-ne l’expansió. A partir d’aquí, abans de començar amb la implementació per GPU, es va decidir readaptar la metàfora d’interacció per a poder etiquetar els vòxels seleccionats per l’usuari escribint directament sobre la textura de segmentació carregada ja a la GPU. Aquest procediment es coneix usualment com a render to texture, i consisteix en redireccionar la sortida d’un fragment shader perquè s’escrigui en una textura que després serà llegida pel shader que renderitza la segmentació. Així doncs, vam començar a investigar com utilitzar l’API de Unity (Unity Software Inc., 2016) per 58 implementar aquesta tècnica ([DP.5.2.1], 16 hores). Malauradament ens vam trobar amb poc suport per part de la documentació oficial, i vam trobar sobretot que la comunitat tenia molts problemes alhora de dissenyar una seqüència de crides a l’API per a implementar aquesta tècnica. Finalment, vam decidir abordar el problema fent ús de compute shaders. Aquests es defineixen com ashaders d’ús genèric que permeten fer càlculs per GPU fora de l’àmbit de gràfics per computador, aprofitant la capacitat de paral·lelització que ofereixen les targetes gràfiques (Microsoft, 2018). Aquests ofereixen tres grans avantatges: permeten a l’usuari definir el nombre de threads que executen un mateix kernel; permeten definir textures 3D com a estructures de dades amb accessos de lectura i escriptura; l’API de Unity ofereix la classe ComputeShader per poder-los configurar (Unity Software Inc., 2016). Quan es donin més detalls sobre la implementació, també veurem que són útils davant dels desavantatges de region growing analitzats a la secció 1.4.2.2. D’aquesta manera, la textura de segmentació del model volumètric es troba referenciada a dos compute shaders amb accés d’escriptura, un per a poder pintar els vòxels d’interès per l’usuari, i un altre que tindrà el procés d’una iteracó de region growing. Utilitzem el main loop de Unity per fer una crida al shader corresponent per cada situació, i el fragment shader inicial (el que s’encarregava de visualitzar la informació de segmentació) simplement llegirà d’aquesta textura actualitzada per la GPU, sense haver-la de transferir des de la CPU cada cop. Al moment de redactar aquest informe de seguiment, l’estat del projecte es troba havent finalitzat aquesta tasca. Sí que és veritat que quan es va proposar la planificació durant la fase inicial, no vam preveure el problema real de treballar amb l’alta latència de passar informació de CPU a GPU, ni que haguéssim de readaptar la tècnica render to texture per a la implementació de l’algorisme. És per això que aquesta tasca ha ocupat 40 hores de més. Per altra banda, ja tenim una versió d’un seeded region growing per GPU que funciona, i el projecte es troba en una fase que anomenem de refinament, envers la fase de millores ([DP.6] Millores) que vam definir durant la planificació inicial sense cap especificació. [DP.6] Refinament Un cop tenim una primera versió funcional d’un algorisme de segmentació per GPU, hem realitzat un estudi de millores de la interacció i usabilitat ([DP.6.A]). Tenim previst acabar les següents tasques abans d’acabar l’any, i deixar les vacances per acabar de redactar la memòria. •Afegir la funcionalitat de poder esborrar una seed. •Permetre a l’algorisme que s’aturi automàticament si detecta que no s’han etiquetat nous vòxels. •Poder guardar i recuperar la textura de segmentació. •Poder plantar seeds que no permetin l’expansió de la segmentació. 59 •Tenim previst comprovar la performance de la solució oferta amb models volumètrics més grans (256x256x256, i 512x512x256). [DP.7] Tests d’usabilitat Un cop tinguem l’aplicació acabada, procedirem a realitzar tests d’usabilitat, per comprovar que podem oferir una solució que compleix els requisits definits durant la fase d’estudi de l’abast. Podrem dedicar unes 24 hores a fer testos d’usabilitat, ja que s’hauran de realitzar al Centre de Realitat Virtual (Department of Computer Science, 2020), amb la supervisió del director i la tutora. 4.3 Recursos 4.3.1 Recursos humans (RH) Aquest projecte requereix de la intervenció de quatre rols ben definits: •Cap de projecte S’encarrega del curs que ha de seguir tot el desenvolupament, des de la planificació, les reunions i la documentació. •Investigador S’encarrega de fer tot el treball relacionat amb la recerca d’informació per assolir l’abast del projecte. •Programador S’encarregarà d’implementar la solució definida per la gestió del projecte. •Avaluador S’encarregarà de realitzar les proves de validació de l’aplicació, tan del seu correcte funcionament com dels tests d’usabilitat amb usuaris. 4.3.2 Recursos materials (RM) Llistem el conjunt de RM que utilitzarem per a la realització del projecte: •PC És important disposar d’ordinador propi pels dies que no es treballi al Centre de Realitat Virtual (Department of Computer Science, 2020). •Overleaf Aplicació web per crear documents en format L A TEX(Overleaf, 2020). •Unity3D Motor gràfic (Unity Software Inc., 2020). •HTC Vive Dispositiu de RV immersiu (H. Corporation, 2020). •GanttProject Eina de lliure distribució per elaborar el diagrama de Gantt i l’assignació de RH (BarD Software, 2020). 60 La taula 1sintetitza tota la informació que s’ha donat fins ara. S’ha assignat totes les tasques a un o més membres de l’equip (veure secció 4.3.1), i per cada una s’indica el material requerit. Pel què fa a les reunions de seguiment (tasques amb etiqueta [R]), s’ha assumit que hi assistiran els membres que estiguin fent la tasca d’aquella setmana i el cap de projecte, el qual s’encarrega de la supervisió de tot el desenvolupament. Al diagrama de Gantt adjuntat a l’apèndix (figura 49) es mostren els detalls de les tasques amb més profunditat. Concretament, per cada tasca es veu la seva data d’inici i finalització, la durada en dies, els recursos humans assignats i el risc que se li ha associat. El risc també es veu reflectit amb textures que es troben per sobre de les franges de colors que marquen el temps que ocupen les tasques. 4.4 Gestió del risc: Plans alternatius i obstacles Al diagrama de Gantt (veure figura 49) podem veure algunes trames marcades amb una textura més fosca. Aquestes corresponen a les tasques que considerem que pertanyen al camí crític o de risc. Aquestes són tasques que estan relacionades amb els obstacles i riscos analitzats durant l’etapa de [DP.1] Contextualització i abast (veure seccions 2.2 i2.3). Per una banda, les tasques d’implementació de l’algorisme de segmentació basat en regió per CPU ([DP.4]) les considerem crítiques perquè serà molt important que aquesta implementació sigui correcta i eficient, ja que un endarreriment o una mala implementació pot fer-nos arrossegar problemes d’eficiència o de temps a dedicar quan vulguem passar la implementació a la GPU. És per això que s’ha volgut desglossar bé aquesta tasca i fer un seguiment a detall de les diferents fases de les que consta l’algorisme. Serà molt important obtenir bons resultats dels tests d’usabilitat associats a aquesta tasca ([DP.4.6]). De la mateixa manera, la implementació per GPU ([DP.5]) és crítica perquè representa una part fonamental de l’aplicació que volem oferir, de manera que serà molt important tenir ben clar el disseny que farem abans de posar-nos-hi i realitzar una bona implementació amb el temps que li hem assignat, per a poder tenir marge més endavant per estudiar i aplicar les millores. Finalment, els tests d’usabilitat també els considerarem una tasca de risc, ja que si la nostra aplicació no compleix els requisits d’usabilitat desitjats, potser no la podem tenir llesta abans de la [F] Inscripció al Torn de Lectura. Un dels majors obstacles que podem tenir és la impossibilitat de realitzar les proves d’usabilitat al llarg del desenvolupament degut a l’emergència sanitària, ja que no podem preveure si en algun moment ens és impossible poder accedir a l’espai de treball i fer que varis usuaris utilitzin el dispositiu de RV. Si veiem que fos complicat poder fer estudis amb la interacció, ens veurem obligats a optar per enfocar la tasca [DP.6] Millores a oferir millores relaciones amb l’algorisme de segmentació que com ja vam comentar, al presentar-se com un algorisme de segmentació clàssic, 61 Nom Durada(h) Relacions RH RM [GP] Gestió del projecte 135 - - [GP.1] Contextualització i abast 30 - CP, I PC, Overleaf [GP.2] Planificació temporal 16 [GP.1] CP PC, Overleaf, GantProject [GP.3] Pressupost i sostenibilitat 14 [GP.2] CP PC, Overleaf, GantProject [GP.4] Integració del document final 32 [GP.3] CP PC, Overleaf [GP.F] Entrega d’informe de Gestió del projecte + Reunions 15 - CP PC, Overleaf [MEM] Elaboració de la memòria Final 28 - CP PC, Overleaf [DP] Desenvolupament del projecte 298 - - [DP.1] Formació i preparació. 24 - I, P PC, Unity3D, HTC Vive [R] Reunió de seguiment 1 - CP, I, P PC [DP.2] Threshold Segmentation per CPU 8 [DP.1] P PC, Unity3D, HTC Vive [R] Reunió de seguiment 1 - CP, P PC [R] Reunió de seguiment 1 - CP, P PC [DP.3] Interacció bàsica 10 [DP.2] Fi-Fi P PC, Unity3D, HTC Vive [DP.3.1] Esfera per llegir valors de voxels 7 - P - [R] Reunió de seguiment 1 - CP, P - [DP.3.2] Botó "aplica segmentació" 1 [DP.3.1] P - [R] Reunió de seguiment 1 - CP, P - [DP.4] Region Growing per CPU 79 [DP.2] - - [DP.4.1] Comprensió de l’algorisme 10 - I PC [R] Reunió de seguiment 1 - CP, I PC [DP.4.2] Plantat de llavors 4 [DP.4.1] P PC, Unity3D [DP.4.3] Evolució de la segmentació 16 [DP.4.2] P PC, Unity3D [DP.4.4] Adaptar la interacció 2 [DP.4.3] Fi-Fi P PC, Unity3D, HTC Vive [DP.4.F.1] Prova de correctesa 4 [DP.4.3] P, A PC, Unity3D, HTC Vive [DP.4.5] Image Smoothing 8 [DP.4.3] Fi-Fi P PC, Unity3D [R] Reunió de seguiment 1 - CP, P, A PC [DP.4.F.2] Prova de correctesa 4 [DP.4.5] P, A PC, Unity3D, HTC Vive [DP.4.6] Test d’usabilitat 28 - A PC, Unity3D, HTC Vive [R] Reunió de seguiment 1 - CP, P, A PC [DP.5] Region Growing versió híbrida (CPU - GPU) 82 [DP.4] - - [DP.5.1] Lectura i comprensió 16 - I PC [R] Reunió de seguiment 1 - CP, I PC [DP.5.2] Implementació 36 [DP.5.1] P PC, Unity3D [R] Reunió de seguiment 1 - CP, P PC [DP.5.3] Possibles millores 24 [DP.5.2] I, P PC, Unity3D [DP.5.F] Prova de correctesa 4 [DP.5.3] P, A PC, Unity3D, HTC Vive [DP.6.A] Millores d’interacció 8 - CP, I PC [DP.6.B] Millores de l’algorisme 8 - CP, I PC [R] Reunió de seguiment 1 - CP, I PC [DP.6] Aplicar millores 50 [DP.6.A];[DP.6.B] P PC, Unity3D, HTC Vive [R] Reunió de seguiment 1 - CP, P PC [DP.7] Tests d’usabilitat 24 - A PC, Unity3D, HTC Vive Total 433 --- Taula 1: Taula amb la planificació del projecte. Per cada tasca s’inclou la durada en hores, les relacions de dependència i els recursos humans (RH) i materials requerits (RM). Llegenda: CP - Cap de projecte, I - Investigador, P - Programador, A - Avaluador. 62 4.6.2 Impacte econòmic Estimació del cost de realització del projecte El pressupost d’aquest projecte posa molta èmfasi als recursos humans que requereix, essent l’element que marca la tendència del preu per a la realització del projecte. Inclús així, el desglossament de les tasques ens ha permès filar prim amb l’estimació del cost de la mà d’obra. Creiem que la selecció i ús del maquinari i software és molt concret i compleix amb els requisits mínims per poder elaborar una solució de qualitat. A més, aquest projecte es construirà sobre una aplicació ja existent, de manera que la nostra solució pretén abordar una petita part d’una que ja tenim disponible. D’aquesta manera valorem el producte que ens disposem a desenvolupar com a un recurs competitiu i a l’abast econòmic d’un òrgan o institució que el demani. Solucions actuals: On es troba aquest projecte? La gran diferència que veiem de les aplicacions actuals de segmentació de models volumètrics en 3D amb la nostra és la interacció, ja que tant metges com estudiants interactuen amb els models volumètrics a través d’una pantalla que ofereix eines d’interacció en 2D. És llavors mèrit de cada aplicació oferir eines que en faciliten la interacció. Sí que és veritat que a la nostra solució la interacció es basarà en un entorn de RV immersiu, amb tot el potencial que això suposa. Per altra banda, això requereix als usuaris de la nostra aplicació tenir més recursos, com un ordinador de gamma alta i el dispositiu de RV, comportant un cost extra al que s’estima només amb l’elaboració i obtenció de l’aplicació. També volem destacar que amb la ràpida evolució que estan patint els sistemes de RV actuals, una hipotètica obsolescència de la nostra tecnologia pot ser perjudicial pels seus usuaris. 4.6.3 Impacte ambiental Impacte ambiental de la realització del projecte Creiem que el consum relacionat amb el desenvolupament del projecte entra dins dels estàndards de consum habituals de la vida quotidiana de les persones, ja que el projecte es desenvoluparà en un espai de treball compartit (Department of Computer Science, 2020), on es coordinen i es realitzen varis projectes de forma simultània. També hem definit el material mínim requerit, que encara que l’ús que en donarem no comporti un gran consum d’energia, no hem tingut en compte l’impacte ambiental del seu procés de fabricació. 69 Problemes i solucions actuals: On es troba aquest projecte? De la mateixa manera que quan s’ha comentat l’impacte econòmic, els requeriments mínims que es necessiten per al bon funcionament del nostre producte poden suposar un consum superior que les solucions actuals que no demanen tants recursos. També és important destacar que si l’impacte de la producció del nostre dispositiu de RV és qüestionable, estarem contribuint per partida doble a aquesta producció, ja que requerim als usuaris l’ús de dispositius com el nostre. 4.6.4 Impacte social Aportació personal d’aquest projecte A nivell personal, la realització d’aquest projecte em pot aportar tenir una visió més clara de l’ús i les aplicacions del processament de gràfics per computador, més enllà dels coneixements adquirits al respecte durant la realització del grau, que m’han servit per adquirir els coneixements fonamentals sobre les eines que hi ha avui en dia. El fet d’oferir una solució destinada a la comunitat mèdica em fa veure la importància de la informàtica i l’impacte que suposa per a altres sectors fins ara aliens durant el meu desenvolupament en la disciplina que vaig escollir estudiar. Solucions actuals: Necessitat real del projecte La segmentació de models volumètrics en un entorn 3D no és una eina encara molt utilitzada, i segueix formant part del camp de la recerca. Però hi ha la possibilitat real que poder segmentar en un entorn 3D ofereixi més precisió a l’usuari que fent-ho en 2D, ja que en un entorn de RV immersiu l’usuari pot veure tot el model amb percepció 3D. Caldria fer una avaluació de temps per veure si és més ràpid que emprant eines d’interacció en 2D, però com que actualment no s’han desenvolupat tècniques d’interacció específiques per a segmentació en entorns 3D, no disposem de suficient material per realitzar aquesta comparació. D’aquesta manera, creiem que oferir una eina de segmentació de models volumètrics en un entorn de RV, encara que no sigui l’única, servirà per a incentivar la recerca i la innvocació dels sistemes de RV, amb l’objectiu de trobar i oferir solucions estables per a l’ús quotidià de les persones, més enllà de potenciar el sector de l’entreteniment. La recerca i innovació d’aquest sector pot portar solucions també més eficients, així com perfeccionar l’impacte a la salut -marejos, problemes de visió, etc.- de les persones que en fan ús. Si aconseguim concebre els sistemes de RV com a eines que faciliten i milloren la qualitat de vida de les persones, en un futur podria créixer encara més la producció d’aquestes tecnologies, podent estar a l’abast de tothom. 70 Referències [1] Bernhard Preim i Charl P. Botha. Visual Computing for Medicine: Theory, Algorithms, and Applications. 2a ed. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2013. isbn: 9780124159792. [2] Markus Hadwiger. Joe Michael. Kniss Christof. Rezk Rezk-salama. Daniel Weiskopf. Klaus J Engel. Real-time Volume Graphics. A. K. Peters, Ltd., 2006. [3] Universitat Politècnica de Catalunya: Department of Computer Science. ViRVIG: Visualització, Realitat Virtual i Interacció Gràfica.url:https://www.virvig.eu/ (cons. 26 de set. de 2020). [4] Unity Technologies Unity Software Inc. Unity Real-Time Development Platform | 3D, 2D VR & AR Engine.url:https://unity.com/ (cons. 26 de set. de 2020). [5] Joan Fons Sànchez. Inspecció interactiva i immersiva de models volumètrics. Aplicació diagnosi mèdica. Inf. tèc. Universitat Politècnica de Catalunya, 2017. [6] HTC Corporation. HTC Vive.url:https://www.vive.com/eu/ (cons. 26 de set. de 2020). [7] Hung-Li Chen et al. “Sketch-based Volumetric Seeded Region Growing”. A: 2006, pàg. 123- 130. isbn: 3905673398. doi:10.2312/SBM/SBM06/123-129. [8] Josep Ciurana Herrera. Visualització avançada de models mèdics. Inf. tèc. Universitat Politècnica de Catalunya, 2020. [9] Stefan Schenke, Burkhard Wünsche i Joachim Denzler. “GPU-based volume segmentation”. A: (2005). [10] Erik Smistad et al. “Medical image segmentation on GPUs - A comprehensive review”. A: Medical Image Analysis 20 (febr. de 2015), pàg. 1 -18. doi:10.1016/j.media.2014.10.012. [11] A. Sherbondy, M. Houston i S. Napel. “Fast volume segmentation with simultaneous visualization using programmable graphics hardware”. A: IEEE Visualization, 2003. VIS 2003. 2003, pàg. 171- 176. [12] Unity Technologies Unity Software Inc. Unity - Manual.url:https://docs.unity3d.com/540/ Documentation/Manual/index.html (cons. 2016). [13] Joey de Vries. Learn OpenGL - Framebuffers. 15 de gen. de 2021. url:https://learnopengl. com/Advanced-OpenGL/Framebuffers. [14] Braynzar Soft. Render to texture.url:https://www.braynzarsoft.net/viewtutorial/q16390-35- render-to-texture (cons. 2 de nov. de 2015). [15] Aassif Benassarou et al. “MC Slicing for Volume Rendering Applications”. A: vol. 3515. Abr. de 2005, pàg. 47- 84. isbn: 978-3-540-26043-1. doi:10.1007/11428848_39. 71 [16] Microsoft. Compute Shader Overview - Win32 apps | Microsoft Docs.url:https://docs. microsoft.com/en-us/windows/win32/direct3d11/direct3d-11-advanced-stages-compute-shader (cons. 31 de maig de 2018). [17] Khronos. Compute Shader - OpenGL Wiki. 22 d’abr. de 2019. url:https://www.khronos. org/opengl/wiki/Compute_Shader. [18] P. Perona i J. Malik. “Scale-space and edge detection using anisotropic diffusion”. A: IEEE Transactions on Pattern Analysis and Machine Intelligence 12.7 (1990), pàg. 629- 639. doi: 10.1109/34.56205. [19] Software Freedom Conservancy. Git –fast-version-control.url:https://git-scm.com/ (cons. 27 de set. de 2020). [20] Altassian. Trello.url:https://trello.com/ (cons. 27 de set. de 2020). [21] Google. Google Meet.url:https://gsuite.google.com/products/meet/ (cons. 27 de set. de 2020). [22] Inc. Slack Technologies. Slack.url:https://slack.com (cons. 27 de set. de 2020). [23] NVIDIA Corporation. NVIDIA Developer Zone: Cg Language Specification.url:https:// developer.download.nvidia.com/cg/index_language.html (cons. 4 d’oct. de 2020). [24] Overleaf. Online Latex Editor Overleaf.url:https://www.overleaf.com/ (cons. 5 d’oct. de 2020). [25] s.r.o. BarD Software. GanttProject: Free desktop project scheduling app.url:https://www. ganttproject.biz/ (cons. 2 d’oct. de 2020). [26] Federación de Servicios CCOO. “Sondeo a la población del sector TIC”. A: (12 de febr. de 2020). [27] Sr. Días Laborables. Días laborables.url:https://www.dias-laborables.es/ (cons. 11 d’oct. de 2020). [28] Logical Increments. Logical Increments.url:https://www.logicalincrements.com/ (cons. 10 d’oct. de 2020). [29] Redacció BBC. “La ofensiva en EE.UU. para desmembrar las grandes empresas tecnológicas acusadas de monopolio”. A: (7 d’oct. de 2020). Ed. de BBC News. url:https://www.bbc. com/mundo/noticias-54458049. [30] Gemma Galdon Clavell. “¿Qué hacen con nuestros datos en internet?” A: (12 de juny de 2015). Ed. d’El País. url:https : / / elpais . com / tecnologia / 2015 / 06 / 12 / actualidad / 1434103095_932305.html. 72 Apèndix A Diagrama de Gantt Per les tasques relacionades amb la gestió del projecte s’utilitza el color blau, per les fites (proves de correctesa) i les reunions el color rosa, per les tasques relacionades amb la implementació dels algorismes el color vermell, i per les tasques relacionades amb implementar eines d’interacció s’utilitza el color verd. El color groc s’ha reservat pel període que encara queda per determinar s’hi s’aprofundirà amb segmentació o interacció. Figura 49: Diagrama de Gantt, part 1. 73 Figura 50: Diagrama de Gantt, part 2. Figura 51: Diagrama de Gantt, part 3. 74 Figura 52: Diagrama de Gantt, part 4. Figura 53: Diagrama de Gantt, part 5. 75