Bachelor Thesis Roelof Berg 2012

  • Published on
    12-Aug-2015

  • View
    21

  • Download
    2

Embed Size (px)

Transcript

<p>Wilhelm Bchner HochschuleDarmstadtFachbereich InformatikBachelor-Thesis:Leistungssteigerung in der medizinischenBildregistrierung durch Mehrkern-Signalprozessorenvorgelegt von:Roelof BergTechnische InformatikMatrikel-Nummer 877492Adalbert-Stifter-Str. 1923562 LbeckErstgutachter Prof. Dr. rer. nat. Ralph LausenInstitut Fraunhofer MEVIS in LbeckFachbetreuer Jan Rhaak, Lars KnigAbgabe 02.08.2012AbstractDeutschUntersucht wird der Einsatz digitaler Signalprozessoren (DSP) fr die Bildregistrierung.Nach einer Einfhrung in die Bildregistrierung wird zunchst ein mathematisches Verfah-ren fr die rigide Registrierung zweidimensionaler Graustufenbilder entworfen. Es wirdgezeigt, wie dieses Verfahren algorithmisch auf einem verteilten Rechnersystem so umge-setzt werden kann, dass eine efziente Berechnung ermglicht wird. In Zusammenhangmit den daraus gewonnenen Erkenntnissen wird ein Beispielsystem entwickelt, das Bildre-gistrierung auf vier Hochgeschwindigkeits-DSPs mit je acht, also insgesamt 32 Rechenker-nen, durchfhrt. Die Geschwindigkeit dieses DSP-basierten Systems wird abschlieendmesstechnisch mit der Geschwindigkeit herkmmlicher PC-Technik verglichen. Dabeistellt sich heraus, dass durch den Gebrauch von DSPs eine zur PC-Technik konkurrenz-fhige Rechenleistung nur dann erreicht wird, wenn der Overhead zur Bildbertragungweitestgehend reduziert wird. Eine Bildregistrierung kann mit DSP-Bausteinen innerhalbvon wenigen Sekunden durchgefhrt werden, bei gleichzeitiger berlegenheit in punctoEnergie- und Raumbedarf gegenber der PC-Technik.EnglishIn this paper, the use of digital signal processors (DSP) for image registration is studied.After an introduction into image registration, a mathematical method for the rigid regis-tration of two-dimensional greyscale images is initially outlined. It will be shown howthis method can be implemented algorithmically on a distributed computer system ina way that enables efcient calculation. The ndings will help to develop an examplesystem that performs image registration on four high-speed DSPs with eight calculationcores each, that is 32 in total. In the nal section, the speed of this DSP-based system willbe metrologically compared with the speed of traditional PC technology. As a result, itappears that the use of DSPs only achieves a computing power that is able to competewith PC technology if the overhead for image transfer is being reduced to the greatestpossible extent. With DSP components, an image registration can be performed within afew seconds, simultaneously outrunning PC technology in terms of energy consumptionand space requirement.IInhaltsverzeichnisAbbildungsverzeichnis VIITabellenverzeichnis IX1 Einleitung 12 Bildregistrierung 32.1 Optimierungsproblem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 Mathematische Anstze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.3 Bildregistrierung nach Modersitzki . . . . . . . . . . . . . . . . . . . . . . . . 62.4 Mathematische Bausteine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4.1 Bildformat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4.2 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4.3 Distanzma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.4.4 Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.5 Zielfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.5.1 Rigide Registrierung. . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.5.2 Afne Registrierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.6 Gradient der Zielfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.7 Herleitung der Jacobi-Matrizen . . . . . . . . . . . . . . . . . . . . . . . . . . 122.7.1 Die Funktion T(wr) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.7.2 Die Funktion /(T) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.7.3 Die Funktion T [y](/) . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.7.4 Die Funktion Tr(T [y]) . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.7.5 Die Funktion Ts(Tr). . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.8 Multiplikation der Jacobi-Matrizen. . . . . . . . . . . . . . . . . . . . . . . . 202.9 Optimierungsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 Algorithmische Umsetzung 233.1 Randwertproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.2 Gradientenbildung ohne LSI-Filter . . . . . . . . . . . . . . . . . . . . . . . . 263.3 Reduktion von Speicherzugriffen. . . . . . . . . . . . . . . . . . . . . . . . . 263.3.1 Matrixfreie Berechnung pro Pixel . . . . . . . . . . . . . . . . . . . . . 27IIIInhaltsverzeichnis3.4 Parallelisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.4.1 Parallelisierung ber mehrere DSP-Chips . . . . . . . . . . . . . . . . 293.4.2 Parallelisierung pro DSP-Chip an seine Rechenkerne . . . . . . . . . 324 Hardwareaufbau 354.1 DSP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.1.1 Hochleistungs-DSP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.1.2 Vergleich zu GPU-Prozessoren . . . . . . . . . . . . . . . . . . . . . . 364.1.3 Raum- und Energieanforderungen. . . . . . . . . . . . . . . . . . . . 374.2 Der C6678-DSP von Texas Instruments . . . . . . . . . . . . . . . . . . . . . . 394.2.1 C6678-Evaluierungsmodule. . . . . . . . . . . . . . . . . . . . . . . . 404.3 Versuchsaufbau fr die messtechnische Analyse . . . . . . . . . . . . . . . . 414.3.1 JTAG-Konguration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.3.2 Netzwerkkonguration . . . . . . . . . . . . . . . . . . . . . . . . . . 455 Softwareimplementierung 475.1 Software fr die messtechnische Erforschung. . . . . . . . . . . . . . . . . . 475.1.1 Rapid Prototyping in Matlab . . . . . . . . . . . . . . . . . . . . . . . 505.1.2 Matlab-Coder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525.2 Verteilte Informationsverarbeitung. . . . . . . . . . . . . . . . . . . . . . . . 575.2.1 HPRPC-Protokoll . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575.2.2 Protokollformat. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595.2.3 Datenkompression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605.3 PC-Clientsoftware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625.3.1 Entwicklungsumgebung . . . . . . . . . . . . . . . . . . . . . . . . . . 635.3.2 Multicore-Parallelisierung mittels OpenMP . . . . . . . . . . . . . . . 645.3.3 Parallele Datenbertragung mittels nicht blockierender Sockets . . . 665.4 Embedded DSP-Serversoftware. . . . . . . . . . . . . . . . . . . . . . . . . . 665.4.1 Entwicklungsumgebung . . . . . . . . . . . . . . . . . . . . . . . . . . 675.4.2 Partitionierung der Applikation . . . . . . . . . . . . . . . . . . . . . 685.4.3 Multicore-Parallelisierung ber IPC-Nachrichten . . . . . . . . . . . 725.4.4 Datenbertragung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745.4.5 Speicherfragmentierung. . . . . . . . . . . . . . . . . . . . . . . . . . 765.5 Strukturiertes Vorgehen bei der Implementierung . . . . . . . . . . . . . . . 765.5.1 Qualittssicherung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 795.6 Wissenschaftliche Vergleichbarkeit der Performance unterschiedlicher Sys-teme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 795.6.1 Rechengenauigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80IVInhaltsverzeichnis6 Messtechnische Untersuchung 836.1 Messverfahren. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 836.2 Messergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 856.2.1 Overhead durch Datenbertragung . . . . . . . . . . . . . . . . . . . 886.2.2 Efzienz der Parallelisierung . . . . . . . . . . . . . . . . . . . . . . . 886.3 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 896.3.1 Skalierbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 906.3.2 Overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 926.4 Eignung fr die Medizintechnik . . . . . . . . . . . . . . . . . . . . . . . . . 937 Zusammenfassung 95Literaturverzeichnis 97AAnhang 105A.1 Pichtenheft . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105A.1.1 Projektziel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105A.1.2 Funktionale Anforderungen . . . . . . . . . . . . . . . . . . . . . . . . 105A.2 Auszge aus dem Softwareentwurf . . . . . . . . . . . . . . . . . . . . . . . . 109A.3 Konguration des SYS/BIOS Betriebssystems . . . . . . . . . . . . . . . . . . 112A.4 Matlab-Quellcode. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117A.5 Messdaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120A.6 HPRPC-Protokoll . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121A.6.1 Opcodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121A.6.2 Fehlercodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122A.7 CD-ROM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123VAbbildungsverzeichnis2.1 Anwendungsbeispiel: Histologische Schnitte eines menschlichen Gehirns . 32.2 Digitaldaten eines Schnittexemplars . . . . . . . . . . . . . . . . . . . . . . . 32.3 Distanzma zweier aufeinanderfolgender Schnitte. . . . . . . . . . . . . . . 42.4 Zusammengesetzte 3D-Daten . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.5 Zwei Beispielbilder, das linke soll auf das rechte registriert werden . . . . . 52.6 Sukzessive Approximation auf das minimale Distanzma . . . . . . . . . . . 52.7 Vernderung des Distanzmaes bei Rotation des Templatebilds . . . . . . . 52.8 / weist Koordinaten zu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.1 Bounding-Box fr bekannte Transformationsparameter w . . . . . . . . . . . 253.2 Knstlicher Rand gegen Pipelinehemmnisse . . . . . . . . . . . . . . . . . . 253.3 Verantwortlichkeit des ersten DSP bezogen auf das Referenzbild . . . . . . . 293.4 Transformierte Eckkoordinaten denieren die vom Templatebild bentigtenDaten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.5 Fr mehrere Iterationen wird eine Worst-Case-Annahme getroffen . . . . . 313.6 Bounding-Box zur Reduktion der Datenbertragung . . . . . . . . . . . . . 323.7 Parallele Berechnung auf acht Rechenkernen ber ein Viertel des Referenzbilds 334.1 Optischer Vergleich zwischen DSP-Chip und PC-Platine . . . . . . . . . . . 384.2 Industriell verfgbare Komponenten mit C6678-DSPs . . . . . . . . . . . . . 414.3 Testaufbau schematisch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.4 Testaufbau mit vier DSP-Evaluierungsmodulen . . . . . . . . . . . . . . . . . 424.5 Alternativer Testaufbau mit dedizierten JTAG-Verbindungen . . . . . . . . . 445.1 Verteilung des Registrierungsalgorithmus. . . . . . . . . . . . . . . . . . . . 485.2 Kommandozeilenoptionen der PC Software . . . . . . . . . . . . . . . . . . . 495.3 Kommandozeilenausgabe der PC Software . . . . . . . . . . . . . . . . . . . 505.4 Bildausgabe der PC Software - Gehirn . . . . . . . . . . . . . . . . . . . . . . 515.5 Bildausgabe der PC Software - Tumor . . . . . . . . . . . . . . . . . . . . . . 515.6 Prototyp in Matlab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525.7 Denition von Variablentypen in Matlab-Coder . . . . . . . . . . . . . . . . 545.8 Matlab-Embedded-Coder-Einstellungen fr Texas Instruments DSPs . . . . 545.9 Einordnung des HPRPC-Protokolls in das OSI-Referenzmodell . . . . . . . 595.10 Speicherkonguration als Teil der Plattformkonguration . . . . . . . . . . 705.11 Sequenzdiagramm zur Verdeutlichung der IPC-Kommunikation . . . . . . 73VIIAbbildungsverzeichnis6.1 Berechnungsauer bei 512x512 Pixel Bildgre. . . . . . . . . . . . . . . . . . 866.2 Berechnungsdauer bei 3000x3000 Pixel Bildgre . . . . . . . . . . . . . . . . 866.3 Registrierungsgeschwindigkeit abhngig von der Anzahl Rechenkerne. . . 876.4 Relative Geschwindigkeit von vier DSPs in Relation zu verschiedenen PCs . 876.5 Overhead bei unterschiedlicher Gre der Bilddaten . . . . . . . . . . . . . . 886.6 Prognose fr die notwendige Anzahl an DSP-Bausteinen, um die gleicheLeistung einer PC-Lsung zu erzielen . . . . . . . . . . . . . . . . . . . . . . 916.7 Prognose fr die notwendige Anzahl an DSP-Bausteinen ohne Overheadfr die Bilddatenbertragung . . . . . . . . . . . . . . . . . . . . . . . . . . . 92VIIITabellenverzeichnis2.1 Nomenklatur nach Modersitzki . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2 Zustzliche Nomenklatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.3 Einzelabbildungen der Distanzma-Berechnung in der Reihenfolge ihrerAusfhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114.1 Vergleich im Energieverbrauch zwischen CPU, GPU und DSP . . . . . . . . 384.2 Kennwerte des C6678-DSP von TI . . . . . . . . . . . . . . . . . . . . . . . . 394.3 C6678-Evaluierungsmodul von TI . . . . . . . . . . . . . . . . . . . . . . . . 404.4 Hardwareausstattung fr die Performancemessung . . . . . . . . . . . . . . 444.5 IP-Konguration des Aufbaus fr die Performancemessung . . . . . . . . . 455.1 Umfang der Software in Dateien und Code- sowie Kommentarzeilen . . . . 475.2 Ausgabetypen von Matlab-Coder . . . . . . . . . . . . . . . . . . . . . . . . . 535.3 HPRPC Request . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595.4 HPRPC Response . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595.5 HPRPC Error Response . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605.6 Speicherbereiche eines C-Programms . . . . . . . . . . . . . . . . . . . . . . . 695.7 Speicherarten des C6678-Evauierungsmoduls . . . . . . . . . . . . . . . . . . 695.8 Planung der wchentlichen Meilensteine . . . . . . . . . . . . . . . . . . . . 796.1 Messpunkte fr eine verteilte Bildregistrierung. . . . . . . . . . . . . . . . . 836.2 Messpunkte fr eine lokale Bildregistrierung . . . . . . . . . . . . . . . . . . 836.3 Messpunkte fr eine verteilte Bildregistrierung. . . . . . . . . . . . . . . . . 846.4 Messpunkte fr eine lokale Bildregistrierung . . . . . . . . . . . . . . . . . . 856.5 Messpunkte fr eine lokale Bildregistrierung . . . . . . . . . . . . . . . . . . 856.6 Efzienz der Parallelisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . 896.7 Hardwarelsungen fr die Vermeidung/Reduzierung von Overhead. . . . 936.8 Dauer einer verteilten Bildregistrierung auf vier DSPs. . . . . . . . . . . . . 94IX1EinleitungDas...</p>