Das Korrespondenzproblem fur Statistische 3D-Formmodelle in

biomedizinischen Anwendungen

Ubersicht und Klassifikation

Studienarbeit

im Studiengang Diplom-Informatik

Thomas Wenckebachgeb. am 2.12.1977in Traben-Trarbach

Institut fur InformatikHumboldt-Universitat zu Berlin

Betreuer:

Prof. Dr. Beate Meffert, Lehrstuhl Signalverarbeitung und Mustererkennung

Hans Lamecker, Konrad-Zuse-Zentrum fur Informationstechnik Berlin (ZIB)

eingereicht am 29. April 2004

Zusammenfassung

Es wird eine Auswahl bekannter Verfahren zur Korrespondenzfindung bei der Erzeugung stati-stischer Formmodelle vorgestellt. Die Auswahl richtet sich nach Anwendbarkeit in 3D und Eig-nung fur biomedizinische Aufgabenstellungen. Die Verfahren werden aufgrund einer mathema-tischen Formulierung des Korrespondenzproblems klassifiziert und verglichen. Daneben werdensie hinsichtlich ihrer Allgemeinheit bezuglich der Topologie der Formen und hinsichtlich der ver-wendeten Optimierungsverfahren, also ihrer Komplexitat, unterschieden. Bei der Analyse wirdbesonders darauf geachtet, inwieweit der Anforderung, anatomisch plausible Korrespondenzenzu liefern, genugt wird.

Inhaltsverzeichnis

1 Einleitung 3

2 Ziel dieser Arbeit 3

3 Statistische 3D-Formmodelle 4

3.1 Anforderungen an die Korrespondenz . . . . . . . . . . . . . . . . . . . . . . . . . 53.2 Anforderungen an das Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

4 Korrespondenzproblem fur statistische Formmodelle 7

4.1 Reprasentation der Formen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84.1.1 Diskretisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4.2 Bewertung der Korrespondenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

5 Verfahren zur Korrespondenzfindung 11

5.1 Bildregistrierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115.1.1 Volumenregistrierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135.1.2 Oberflachenregistrierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

5.2 Implizite Korrespondenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175.2.1 Kanonische Parametrisierung . . . . . . . . . . . . . . . . . . . . . . . . . 175.2.2 Minimale Beschreibungslange . . . . . . . . . . . . . . . . . . . . . . . . . 20

5.3 Matching mit Formdeskriptoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215.3.1 Modal Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

6 Diskussion und Ausblick 22

2

1 Einleitung

Das Finden von Korrespondenzen zwischen Punktmengen im Raum ist ein zentrales Problemder Gebiete Computergraphik, Computer Vision, Robotik, Mustererkennung sowie Bildverarbei-tung. Eine Vielzahl von Anwendungen fuhrt darauf, unter anderem Morphing [ZSH00], Objekt-modellierung bzw. Formrekonstruktion [HHI95], Objekterkennung [SP95], Bewegungsverfolgung[KG92], Positionsbestimmung bzw. Navigation [SB92], Erzeugen von Atlanten [CTCG95], mul-timodale Bildfusion [Roh00], oder bildgesteuerte Chirurgie [MMF98].Die letzten drei Punkte sind typische Beispiele aus der biomedizinischen Bildverarbeitung, wodas Korrespondenzproblem oft durch Bildregistrierung gelost wird. In der Computer Visionspricht man auch haufig von Point bzw. Shape Matching.

Statistische Formmodelle werden seit einiger Zeit in der Computer Vision und der biomedizini-schen Bildverarbeitung erfogreich eingesetzt, um dem Ziel der Interpretation von Bildern naherzu kommen, z.B. dem automatischen Erkennen von Gesichtern [CT01] oder der automatischenSegmentierung von Organen [LLS03]. Sie wurden auch fur die Analyse von anatomischen Struk-turen im Rahmen der Bewegungsanalyse (z.B. des Herzens) oder zu diagnostischen Zwecken(z.B. Alzheimer oder Schizophrenie [WPS03]) angewendet, zur Planung radiologischer Behand-lungen [CHTH93] sowie zur funktionalen Analyse des Gehirns [CT99].Die Idee, die der Erzeugung statistischer Formmodelle zugrundeliegt, ist die Annahme, daßObjekte unserer Anschauung Klassen bilden, deren Elemente sich durch eine eingeschrankteVariabilitat in Große, Form und Aussehen unterscheiden [CTCG95]. Erfaßt man eine vergleichs-weise geringe Zahl N von Vertretern einer Klasse (die sogenannte Trainingsmenge), kann mandiese spezifische Variabilitat mittels einer Hauptmodenanalyse [Jol86] auf kompakte Weise mo-dellieren.

Wahrend die Hauptmodenanalyse ein etabliertes Verfahren ist, um Meßreihen großer Dimensi-on zu entkorrelieren, ist ihre Anwendung auf die Modellierung von dreidimensionalen Formenimmer noch Gegenstand aktiver Forschung. Grund ist, daß im Gegensatz zu traditionellen An-wendungen, wo Objektmerkmale wie Korpergroße und -gewicht klar definiert sind, hier derMerkmalsvektor in kanonischer Form fur jedes der N Objekte der Klasse erst generiert werdenmuß. Damit aber ein sinnvolles statistisches Formmodell resultiert, muß das i-te Element einesMerkmalvektors vj mit dem i-ten Element eines Merkmalvektors vl, l 6= j, i = 1...N korre-spondieren1. Man trifft auf das Korrespondenzproblem. Ursprunglich wurde es manuell gelost,das heißt fur jedes Element der Trainingsmenge wurden homologe Punkte definiert2 [CHTH93].Diese Praxis hat sich mangels Alternativen lange gehalten. Noch in 2000 veroffentlichten Lorenzund Krahnstover [LK00] ein manuelles Verfahren zur statistischen Formmodellbildung, obwohldas manuelle Bestimmen von Landmarken ein langwieriger Prozeß ist, der große Fachkenntnisund Routine verlangt.In der Folge wurden semiautomatische Methoden entwickelt [LLS03], welche immer noch einegewisse Absicherung der Ergebnisse durch ein menschliches Expertenurteil ermoglichen.Heute stehen vermehrt automatische Verfahren zur Verfugung, deren Losungen zum Teil pro-blematisch sind, weil sie nicht notwendig homologe Punkte liefern.

2 Ziel dieser Arbeit

Es wird beabsichtigt, einen Uberblick uber Verfahren zu geben, die zur Losung des Korrespon-denzproblems bei der Erzeugung statistischer 3D-Formmodelle eingesetzt werden, vorwiegendzur Modellierung biomedizinischer dreidimensionaler Formen. Da die Forschung schnell voran-schreitet, erscheint eine vergleichende bzw. resumierende Darstellung existierender Methoden

1Im Falle von biologischen oder medizinischen Daten bezeichnet man korrespondierende Punkte, also solche,die anatomisch denselben Ort darstellen, als homologe Punkte.

2Anatomisch oder geometrisch bedeutungsvolle Punkte werden im biomedizinischen Kontext als Landmarken

bezeichnet [Boo89].

3

wunschenswert. Sie werden nach einem Schema klassifiziert, welches sich aus einer mathemati-schen Formulierung des Korrespondenzproblems ableitet.Die zu verarbeitenden Bilddaten konnen verschiedener Herkunft sein, hauptsachlich handelt essich um Bilder, die von einem Computertomographen, einem Magnetresonanztomographen odereinem konfokalen Mikroskop aufgenommen worden sind.

Ein großer Teil der Literatur uber das Finden von Korrespondenzen aus den eingangs genanntenFeldern laßt sich aus folgenden Grunden kaum zur Erzeugung biomedizinischer statistischer 3D-Formmodelle anwenden und wird daher hier allenfalls am Rande erwahnt:

• Haufig wird angenommen, daß affine Transformationen ausreichen, um die Formen aufein-ander abzubilden, da es sich um Aufnahmen desselben Objekts handelt, bzw. daß Verande-rungen der Formen nur inkrementell stattfinden.Hier werden jedoch verschiedene Exemplare einer Klasse betrachtet. Auch kann man hiernicht annehmen, daß die Formen geordnet sind.

• Die Anwendung in 3D bringt besondere Probleme mit sich. Das 2D-Shape-Matching ist eineigenes Forschungsgebiet, von dem hier nur Ansatze erwahnt werden, deren erfolgreicheErweiterung auf 3D-Probleme dokumentiert ist.

• Es soll das Korrespondenzproblem fur Formmodelle untersucht werden: Daher wird derSpezialfall, wo Modelle basierend auf den Grauwerten erzeugt werden, ausgeklammert.

• Die manuelle Definition korrespondierender Landmarken fur große 3D-Datensatze ist kaumpraktikabel (s.o.).

Die Auswahl orientiert sich weiterhin an einem technischen Report sowie einer aktuellen ta-bellarischen Ubersicht des Erfinders der Active Shape Models, Timothy Cootes [CT01, Coo04],dessen Auflistung verwandter Verfahren nahezu ubereinstimmt mit [DTC+02]. Hinzu kommenErgebnisse eigener Recherche.

3 Statistische 3D-Formmodelle

Prominente Vertreter statistischer 3D-Formmodelle sind die Active Shape Models, unter diesemNamen eingefuhrt von Cootes et al. [CHTH93]. Sie werden hauptsachlich fur die automatischeSegmentierung benutzt. Bei den verwandten Active Contour Models oder Snakes [MT96] passensich die Konturlinien nur durch allgemeine mechanische Modelle eingeschrankt den Umrissen deszu segmentierenden Objekts an (Free-Form Deformations) und werden dabei leicht zu storendenAttraktoren geleitet, welche nicht Teil der Kontur sind. Im Gegensatz dazu werden bei den Ac-tive Shape Models die Einschrankungen der Variabilitat direkt aus der Klasse, der das Objektangehort, abgeleitet. Dennoch ist das Verfahren sehr allgemein, ist also nicht an die Anwendungauf eine bestimmte Klasse gebunden. Die folgende methodische Beschreibung orientiert sich andiesem verbreiteten Ansatz.

Statistische Formmodelle basieren in vielen Fallen auf der Reprasentation von Formen Sn,(n = 1..N), als Mengen diskreter numerierter Punkte, wobei man sich jeden Punkt als aneiner ausgezeichneten Stelle des Objekts plaziert vorstellt, d.h. die Form Sn wird diskret re-prasentiert durch eine Parametrisierung Φn. Indem die Statistik der Positionen der numeriertenPunkte untersucht wird, wird ein Punktverteilungsmodell berechnet. Dieses Modell stellt dieMittelwerte der Positionen der Punkte dar, sowie die Hauptmoden der Variation, welche in derTrainingsmenge angetroffen wurde.

Sei {Sn} eine Menge von N Formen mit M korrespondierenden Punkten und

vn = (xn0, yn0, zn0, ..., xnM−1, ynM−1, znM−1)T , vn ∈ R

3M , 0 ≤ n < N (1)

4

ein Formvektor, wobei (xnj, ynj , znj) der j-te Punkt der n-ten Form ist, der durch die Parame-trisierung Φn auf die Position j (0 ≤ j < M) abgebildet wurde.Mit der Hauptmodenanalyse kann die mittlere Form und die Variabilitat gefunden werden, mitderen Hilfe die vn als Linearkombination geschrieben werden konnen - das gesuchte lineareModell:

vn = v + Pbn = v +∑

k

pkbkn (2)

mit v dem mittleren Formvektor und P = {pk} der Matrix der Eigenvektoren der Kovarianzma-trix. Die zugehorigen Eigenwerte {λk} beschreiben die Varianz in Richtung der Eigenvektoren.Der Anteil an der gesamten Varianz, der durch jeden Eigenvektor erklart wird, ist gleich demzugehorigen Eigenwert [Jol86]. Der großte Teil der Variabilitat kann in der Regel durch einekleine Anzahl Moden erklart werden (t < 3n). Die Formparameter b = {bk} steuern die Modender Variation. Eine ausfuhrlichere Herleitung findet sich bei Cootes et al. [CTCG95] bzw. Jol-liffe [Jol86].Wie bereits erwahnt, ist es fur ein korrektes statistisches Modell wesentlich, daß alle M Punktejeder Form in anatomisch plausibler Korrespondenz stehen, also homolog sind und relativ zueinem gemeinsamen Referenzkoordinatensystem gegeben sind. Diese Teilprobleme werden i. A.unabhangig voneinander gelost [LLS03].Alternativ kann ein statistisches 3D-Formmodell durch die Hauptmodenanalyse analog aufGrundlage anderer Formbeschreibungen aufgebaut werden, z.B. mittels der Koeffizienten derEntwicklung der spharischen Harmonischen [KSG99], oder Deformationsfeldern [FRSN02]. Die-se Formbeschreibungen lassen sich in Punktreprasentationen uberfuhren, daher liegt das Korre-spondenzproblem dort in analoger Form vor.

3.1 Anforderungen an die Korrespondenz

Eigenschaften eines guten Algorithmus zur Korrespondenzfindung zwischen Punkten sind:

1. Medizinisch geschultes Fachpersonal sollte der Losung zustimmen, d.h. die Korrespondenzsollte anatomisch plausibel sein.

2. Die definierten Punkte sollten die Form verlaßlich darstellen, d.h. es sollten keine Teileausgelassen werden. Die Punkte sollten ausreichend dicht sein, so daß Details der Formdurch die Koordinaten der Punkte hinreichend reprasentiert werden.

3. Die Korrespondenzfunktion fij : Si → Sj sollte bijektiv und diffeomorph sein: Benachbartepi ∈ Si sollten mit benachbarten pi ∈ Sj korrespondieren.

4. Die Korrespondenzfindung sollte symmetrisch sein, also im Wesentlichen unabhangig vonder Wahl einer Referenzform Sr (s. Kap. 4).

5. Der Algorithmus sollte robust sein gegen Ausreißer.

6. Der Algorithmus sollte praktikabel sein, d.h. eine gute Performanz aufweisen und mitwenigen Parametern ausgestattet sein.

7. Die definierten Landmarken sollten zu einer guten Performanz einer nachgeordneten Ver-arbeitung fuhren (z.B. Segmentierung).

8. Eine gute Korrespondenz sollte auf ein gutes statistisches Formmodell fuhren.

Fur Punkt 3. haben Caunce und Taylor das Maß der Punktkoharenz entwickelt [CT99]. Da jederHauptmodus eine Weise angibt, wie sich alle Punkte bewegen, sollten sich benachbarte Punkte

5

bei Variation eines Formparameters bi in ahnliche Richtungen bewegen. Ein solcher Indikatorkann fur jeden Modus pk berechnet werden:

ck =1

M

M∑

m=1

1

nm

nm∑

j=1

||dkm · dk

j ||, (3)

wobei nm die Anzahl der Punkte in der Nachbarschaft von Punkt pm und dki den Verschie-

bungsvektor des Punktes pi bezeichnet3.

3.2 Anforderungen an das Modell

Zwei Ziele stehen bei der Erzeugung eines statistischen Formmodells in Konflikt [CTCG95]:Die Allgemeinheit bzw. die Vollstandigkeit des Modells sollte moglichst groß sein, um auch Ver-treter einer Klasse, die nicht in den Modellbildungsprozeß einbezogen worden sind, durch dasModell reprasentieren zu konnen. Dies kann durch Kreuzvalidierung (Leave-one-out-Tests) ge-messen werden. Die Spezifitat des Modells verlangt, daß nur Vertreter der Klasse durch dasModell reprasentiert werden konnen, daß also jede Linearkombination der Eigenmoden aus-schließlich gultige Objektinstanzen generiert.

Abbildung 1: Wenn Elemente des Formvektors (v1 und v2) korreliert sind, konnen auchsehr untypische Formen konstruiert werden (aus Cootes [CTCG95]).

Daneben tritt die Kompaktheit des Modells gemessen z.B. an der Minimalen Beschreibungslange(s. Kap. 4.2), also eine Darstellung aller Formen Sn mit moglichst wenig Eigenmoden, als drit-ter wesentlicher Aspekt eines guten statistischen Formmodells. Das zweite Ziel wird prinzipielldurch die der Hauptmodenanalyse zugrundeliegende Entkorrelierung der Variablen, in dem Fallder Positionen der Punkte (s. Abb. 1), erreicht. Dennoch kann eine ungunstige Wahl einer Mengevon Parametrisierungen {Φn} trotz ‘legaler’ Werte von {bn} ‘illegale’ Forminstanzen erzeugen(s. Abb. 2).

Abbildung 2: Der erste Modus zweier Formmodelle. Links: Modell A, manuell parametrisiert.Rechts: Modell B, parametrisiert nach der Bogenlange (aus Davies [DTC+02]).

Die Gute des Modells ist also ein schwer zu quantifizierender Begriff, der zudem stark anwen-dungsabhangig ist.

3Caunce und Taylor schreiben vermutlich versehentlich ck = 1

M

� M

m=1

1

nm||

� nm

j=1dj ||.

6

4 Korrespondenzproblem fur statistische Formmodelle

Das Korrespondenzproblem beim statistischen Modellieren von Formen besteht darin, fur je-de Form Landmarken zu definieren, so daß uber die gesamte Menge der Formen die Punktemiteinander korrespondieren. Dies entspricht der Suche nach einer Menge {Φn} von geeigne-ten Parametrisierungen der Formen oder aquivalent einer Menge von Korrespondenzfunktionen{fij}, i, j = 1..N ,

Si

fij→ Sj. (4)

Um die Korrespondenz zu finden, muß eine geeignete Reprasentation Si der Formen gewahltwerden, welche abweichen kann von der meist zur Modellbildung verwendeten Punktmengenre-prasentation. In manchen Fallen genugt eine Reprasentation der Oberflache, es kann aber auchsinnvoll sein, das gesamte Volumen zu modellieren.Aus der Reprasentation der Formen ergibt sich die Art der Korrespondenzfunktion: Sie kannauf Punktmengen definiert sein, fij : Si → Sj, auf 2D-Mannigfaltigkeiten, fij : Si → Sj , oderauf dem Raum, in den die Formen eingebettet sind: fij : R

3 → R3.

Die Suche nach fij geschieht durch Minimierung eines Funktionals:

minfij

E(fij , Si, Sj). (5)

Das Funktional, auch Kostenfunktional genannt, bewertet die Qualitat der Korrespondenz. Ver-wendet werden Terme zur Messung der geometrischen Verzerrung, die durch fij entsteht, oderzur Bewertung der Ahnlichkeit der Formen. Daneben werden Einschrankungen formuliert, diegewunschte Eigenschaften einer optimalen Korrespondenzfunktion unterstutzen, wie z.B. derenGlattheit.

Individuelle versus simultane Korrespondenzfindung Bei der individuellen Korrespon-denzfindung wird die Korrespondenz zwischen zwei Formen gesucht. Um ein statistisches Form-modell erzeugen zu konnen, muß also fur eine Referenzform Sr ein Formvektor vr definiertwerden. Mit Hilfe einer Abbildung fij kann die Parametrisierung Φn von Sr auf die Sn ubertra-gen werden, damit erhalt man mit vr korrespondierende vn. Damit wird aber implizit unterstellt,die Sn seien einer willkurlich ausgewahlten Form Sr besonders ahnlich, die Korrespondenz istasymmetrisch. Manche Verfahren versuchen, die Dominanz der Referenzform iterativ abzumil-dern, um die Korrespondenz zu verbessern [FLJ99].Bei der simultanen Korrespondenzfindung wird versucht, die Korrespondenzen zwischen allenFormen untereinander simultan zu optimieren. Dies ist ein sehr aufwendiger Vorgang, der im-mer dann, wenn die Trainingsmenge um neue Exemplare erweitert wird, aufs Neue durchgefuhrtwerden muß. Dagegen ist die Erweiterung der Trainingsmenge fur individuelle Korrespondenz-findungsverfahren vergleichsweise einfach.

Optimierungsverfahren Nur in zwei der hier vorgestellten Verfahren liegt ein lineares Op-timierungsproblem vor (s. Kap. 5.2.1). Ansonsten kann man zwei große Klassen nichtlinearerOptimierungsverfahren unterscheiden: Gradientenbasierte Verfahren und solche, die keine Gra-dienten verwenden, weil das Funktional nicht differenzierbar ist. Beispiele fur Letztere sindSimulated Annealing, Powells Methode, das Nelder-Mead-Simplexverfahren sowie GenetischeAlgorithmen. Sie werden nach Moglichkeit vermieden, weil sie deutlich komplexer und im All-gemeinen weniger robust sind. Die Klasse der Gradientenverfahren kann man weiter in solcheerster Ordnung, welche nur die erste Ableitung benutzen, und zweiter Ordnung, welche auch diezweite Ableitung benutzen, was zu einer schnelleren Konvergenz fuhrt, unterteilen. Ein guterOptimierer erster Ordnung ist z.B. Quasi-Newton. Kompliziertere, aber i.A. wesentlich effizi-entere Verfahren wie z.B. Levenberg-Marquardt [KNFM04] und Konjugierte Gradienten sindzweiter Ordnung. Eine ausfuhrliche Beschreibung findet man in [PTVF93].

7

4.1 Reprasentation der Formen

Die Formen liegen in der Regel nach einer manuellen Segmentierung als dreidimensionale, mar-kierte Voxelbilder vor (Labelfelder). Die Marken zeigen an, zu welchem Segment ein Voxel gehort.

Punkte Mengen von unverbundenen Punkten sind die einfachste Reprasentation von Formen.

Linien Teilmengen von Punkten konnen zu eindimensionalen Kurvensegmenten zusammenge-faßt werden. Damit wird versucht, strukturelle Eigenschaften der Form hervorzuheben und alsRandbedingung in die Korrespondenzfindung aufzunehmen. Man kann Kurvensegmente durchPfade maximaler Hauptkrummung definieren, welche geometrische Invarianten der triangulier-ten Oberflache darstellen (Crest Lines, [STA98]).

Flachen Eine triangulierte Oberflache Sn ist eine Menge von Vertizes und Kanten. Damit lie-gen zusatzlich Informationen zu Konnektivitat und Geometrie vor, es handelt sich um eine stuck-weise lineare, zweidimensionale Struktur im R

3 - eine explizite Darstellung der Flache. Sie kannaus dem binaren Voxeldatensatz mittels einer Distanztransformation [Bor96] extrahiert werden,denn die Voxel, die den Rand einer Markierung bilden, beschreiben die Flache bereits implizit.Um die Triangulierung durchzufuhren, wird die Punktdichte der Oberflache reduziert, in der Re-gel geleitet durch geometrische Eigenschaften wie Krummung. Das ist insofern problematisch,als im Ergebnis korrespondierende Punkte in verschiedenen Formen teils als Vertex ‘uberleben’,teils ausgedunnt worden sind. Daraus folgt, daß die Ausdunnung nur gering sein darf4. An-schließend wird ein Voronoi-Graph der Punktmenge benutzt, um die Delaunay-Triangulierungzu erhalten [BKOS98]. Haufig wird auch der Marching-Cubes-Algorithmus [LC87] direkt auf denVoxeldaten angewendet.

Volumen Ein Volumendatensatz ist eine Menge von Punkten, deren Koordinaten auf einemdreidimensionalen Gitter definiert sind.

Stetige Parametrisierung Eine Oberflache kann mittels einer stetigen bijektiven Abbildungzweier Parameterwerte (u, v) ∈ D fur ein konvexes D ⊂ R

2 auf die Punkte der Oberflacheparametrisiert werden:

x(u, v) =

x(u, v)y(u, v)z(u, v)

,

wobei x, y und z Koordinatenfunktionen R2 → R sind.

Um Deformationen von Formen zu modellieren, konnen die Koordinatenfunktionen wiederumdurch Parametrisierungsfunktionen Φ ausgedruckt werden, z.B. durch die Asymmetrische θ-Transformation nach Davies et al. (s. Kap. 5.2.2).

Formdeskriptoren Die Formen Sn konnen ausgehend von den bisher beschriebenen Re-prasentationen weitergehend charakterisiert werden, wobei als Resultat ein Formvektor vn ab-weichend vom oben beschriebenen (s. Gl. (1)) moglich ist. Man spricht von Feature Vectorsoder Formdeskriptoren. Sie sind in der Lage, verschiedene Formen, moglichst auch verschiedenerTopologie, in ihren globalen und lokalen Eigenschaften exakt und auf kanonische Weise darzu-stellen.Formdeskriptoren wie der Formkontext [BMP02] oder das Spin Image [JH97] sind von hoherraumlicher Komplexitat, da dort die Topographie der Formen durch mehrdimensionale Histo-gramme reprasentiert wird. Sie eignen sich deshalb zur Zeit nur fur 2D Probleme. Fur dieAnwendung des Shape Retrievals aus Datenbanken uber das World Wide Web wurde die Er-weiterung auf 3D bereits dokumentiert [KPNK03]. Die so gewonnen Korrespondenzen sind aber

4Eine Triangulierung einer menschlichen Leber beispielsweise enthalt immer noch ca. 11000 Vertizes.

8

fur die Zwecke der statistischen Formmodellierung nicht exakt genug.Eine andere Art, Formdeskriptoren abzuleiten, ist die Entwicklung uber eine vollstandige Mengevon Basisfunktionen wie B-Splines, Wavelets oder spharische Harmonische nach Kelemen et al.(s. Kap. 5.2.1).Geometrische Formen kann man auch mit Hilfe von Finite Elemente Methoden [Bet97] hierar-chisch in naturliche Schwingungen zerlegen [SP95]. Aus den pm ∈ Sn wird ein Finite-Elemente-Modell generiert. In dieses Modell gehen neben den Punktkoordinaten noch Informationen zurKonnektivitat der Punkte ein, es besteht im Wesentlichen aus Masse- und Steifigkeitsmatrizen.Zur weiteren Analyse werden die Eigenvektoren pk dieses Modells errechnet (Eigenmoden). Sieliefern eine orthogonale, nach der Frequenz geordnete kanonische Beschreibung der Form undihrer naturlichen Deformationen.

4.1.1 Diskretisierung

Ein Aspekt der Formreprasentation ist die notwendige Diskretisierung. Im Ergebnis kann essein, daß fur manche pi ∈ Si kein korrespondierender pj ∈ Sj existiert (s. Abb. 3). DieseSituation kann auch auftreten, wenn fur die Korrespondenzfindung Landmarken automatischauf der Form definiert werden, z.B. Kurvensegmente. Chui et al. [CZR04] sprechen sogar vomKonsistenzproblem, dem als wichtigen Teilproblem der Korrespondenzfindung nicht immer dienotige Aufmerksamkeit geschenkt werde (s. Abb.3).

Abbildung 3: Das Konsistenzproblem. Von links nach rechts: a) Die Originalpunkmenge mit einer dichtenPunktverteilung. b), c) Zwei abgetastete Punktmengen. d) Beide abgetastete Mengen ubereinandergelegt (nachChui et al. [CZR04]).

Je dichter die Punktverteilungen der Sn sind, desto weniger bedeutend wird allerdings dieseProblematik (dichte Korrespondenz).

4.2 Bewertung der Korrespondenz

Das zu minimierende Funktional E (s. Gl. (5)), welches die Qualitat der Korrespondenz mißt,kann unterschiedliche Gestalt annehmen:

Euklidischer Abstand Bei der Bildregistrierung (s. Kap. 5.1) muß gemessen werden, wieahnlich sich zwei Formen unter der jeweils aktualisierten geometrischen Transformation sind.Dies geschieht durch eine anwendungsspezifische Metrik.Der Euklidische Abstand zwischen zwei Punkten pi und pj im R

3 ist definiert als

deij = ||pi − pj || =

√

(xi − xj)2 + (yi − yj)2 + (zi − zj)2. (6)

Werden Oberflachen Si und Sj registriert, wird fur jeden Punkt pi ∈ Si der minimale EuklidischeAbstand zu einem Punkt pj ∈ Sj gemessen:

d(pi, Sj) = minpj∈Sj

||pi − pj || (7)

9

Der Abstand der Oberflachen ist dann

d(Si, Sj) =∑

pi∈Si

d(pi, Sj). (8)

Geometrische Ahnlichkeit Im Sinne einer anatomisch plausiblen Korrespondenz ist es grund-satzlich wunschenswert, die Geometrie der Formen in den Optimimierungsprozess einzubeziehen.Ein Maß fur die Ahnlichkeit der Oberflachennormalenvektoren ni ist [WPS00] deren Projektion:

dnij = ni · nj (9)

Analog kann fur Kurvensegmente die Ubereinstimmung der Tangenten ti gemessen werden:

dtij = ti · tj (10)

Auch die Hauptkrummungen k1 und k2 [Wun97] der Oberflache konnen in die Messung eingehen.Mit ihrer Hilfe kann man die Oberflache in eine von neun Klassen einordnen [WPS00]. Dazudient der Formindex

S =2

πarctan[(k1 + k2)/(k2 − k1)]. (11)

Weiterhin laßt sich das Ausmaß der Krummung [WPS00] bestimmen:

C =√

(k21 + k2

2)/2. (12)

Topographische Ahnlichkeit Topographische Eigenschaften, also die raumliche Strukturder Form, werden wegen des immensen Speicherbedarfs selten ausgewertet. Um den Formkontextdarzustellen, konnen Nachbarschaftshistogramme angelegt werden, was im Falle der vergleichs-weise effizienten Reprasentation der Formen durch Kurvensegmente durchaus praktikabel ist.Jedem Punkt pi eines Kurvensegments wird ein zweidimensionales Histogramm hik zugeordnet(wenn er an einer Verzweigung liegt, mehrere, k > 1). Es wird nach der Tangente der Kurveorientiert und stellt die mit einer Auflosung von acht Pixeln quantisierte Projektion von 3D nach2D dar [CT99]. Histogramme konnen verglichen werden, indem die Zeilen zu Einheitsvektorenkonkateniert und aufeinander projeziert werden:

dhij = max

kl(hik · hjl

) (13)

Ist die Form als Markenbild reprasentiert, kann man die Ahnlichkeit zweier Formen mit derMarkenkonsistenz [FRSN02] messen:

E(f, Si, Sj) =

L∑

l=1

pSiSj(l, l), (14)

wobei pSiSj(l,m) die Wahrscheinlichkeit fur ein gemeinsames Auftreten der Marken l und m in

Si und Sj ist.

Regularisierung Wenn die Korrespondenzfunktion fij eine Abbildung zwischen Oberflachenist, wird versucht, die durch diese Abbildung entstehende Verzerrung zu minimieren. Dazu gibtes verschiedene Ansatze:Durch eine Parametrisierung nach Floater [Flo97] werden Verzerrung, lokale Scherung undSkalierung der Oberflache minimiert, indem die intrinsischen geometrischen Eigenschaften Bo-genlange und Winkel lokal so weit wie moglich bewahrt werden (s. Kap. 5.2.1).Diesem Ansatz ahnlich ist der der harmonischen Abbildung: h : D → P bildet eine triangulierteOberflache D ⊂ R

3, welche topologisch aquivalent einer Kreisscheibe ist, auf eine polygonale

10

Region P des R2 ab und minimiert dabei die sogenannte metrische Dispersion [BT00]. Darunter

verstehen Brett und Taylor das Ausmaß, mit dem kleine Regionen von D durch die Abbildunggestreckt werden (s. Kap. 5.2.1).Eine dritte Variante nach Brechbuhler [BGK95] sucht eine flachenerhaltende Parametrisierung(s. Kap. 5.2.1): Jede Region der Objektoberflache muß auf eine proportionale Region der Ein-heitskugel abgebildet werden.

Um das aus einer Freiform-Bildregistrierung (s. Kap. 5.1) resultierende Deformationsfeld einzu-schranken, werden Regularisierungsterme in das Funktional E aufgenommen. Die Deformationwird geglattet, indem die Krummung des Gitters nach einem Elastizitatsmodell bestraft wird.Durch Bewertung der Jacobi-Determinante kann außerdem eine Ausdehnung des Volumens ein-geschrankt und eine Uberfaltung ausgeschlossen werden (s. Kap. 5.1).

Informationstheoretisches Maß Die Minimale Beschreibungslange als Maß fur die Kom-paktheit des statistischen Formmodells [DTC+02] ist folgendermaßen motiviert: Man stelle sichvor, eine Menge von Formen, welche durch ein lineares statistisches Modell (s. Gl. (2)) beschrie-ben werden, als codierte Nachricht versenden zu mussen. Die vollstandige Sendung beinhaltetdann nicht nur die codierten Daten, sondern auch die codierten Modellparameter, wie z.B. dieVarianzen in den Richtungen der Eigenvektoren der Kovarianzmatrix. Die Balance zwischender Komplexitat des Modells, welche sich in den Kosten fur das Senden der Modellparameterausdruckt, und der Qualitat der Anpassung des Modells an die Formen, ausgedruckt durch dieBeschreibungslange der Daten, wird durch das Maß Minimale Beschreibungslange hergestellt[DTC+02]. Dazu wird ein Ausdruck fur die Beschreibungslange eindimensionaler, beschrankterund quantisierter Daten abgeleitet, welcher auf einer zentrierten Gauß-Verteilung basiert undnach Shannons idealer Beschreibungslange berechnet wird (Details siehe [DTC+02]).

5 Verfahren zur Korrespondenzfindung

5.1 Bildregistrierung

Das Auffinden einer Zuordnung einer (Teil-)Menge von Punkten eines Datensatzes zu einer(Teil-)Menge von Punkten eines anderen Datensatzes wird als Bildregistrierung bezeichnet. DerBegriff Registrierung ist motiviert durch die rigide Registrierung, wo nur Translation und Rotati-on erlaubt sind: Hierbei handelt es sich um die Ausrichtung von Datensatzen in ein gemeinsamesKoordinatensystem.Die Bildregistrierung verbindet die Suche nach einer Korrespondenz zwischen Objekten mit derSuche nach einer geometrischen Transformation, welche die Objekte bestmoglich aufeinanderabbildet. Die Qualitat der Korrespondenz wird anhand ihres Uberlappbereichs auf verschiedeneWeise gemessen, bei Grauwertbildern z.B. mit dem Euklidischen Abstand oder der Korrelation.Einen guten Uberblick uber die medizinische Bildregistrierung bieten [HBHH01, AFP00].Zur Erzeugung von statistischen Formmodellen kann die Bildregistrierung nach dem Prinzip derindividuellen Korrespondenzfindung (s. Kap. 4) eingesetzt werden. Es sind keine Einschrankun-gen an die Objekttopologie notig.

Affine Bildregistrierung Bei der affinen Bildregistrierung wird die gesuchte Transformationauf die Klasse der affinen Transformationen eingeschrankt. Eine affine Transformation im R

3

weist je drei Freiheitsgrade fur Translation, Rotation, Skalierung und Scherung auf.

Freiform-Bildregistrierung Freiform-Deformationen, entwickelt in der Computergraphik,erlauben geometrische Transformationen mit einer frei wahlbaren Zahl von Freiheitsgraden.Durch Interpolation von Steuergitterkoordinaten konnen Objekte lokal deformiert werden. ZurModellierung von Freiform-Deformationen wird einer Form Sn eine Transformation Tn zugeord-

11

net, welche sich aus einer globalen und einer lokalen Komponente zusammensetzt:

Tn(x) = Tnl(x) ◦Tng(x). (15)

Tng ist eine globale, affine5 und Tnl eine nicht-lineare Transformation mit beliebig vielen Frei-heitsgraden. Um letztere zu reprasentieren, werden die Sn nach einer Methode von Lee et al.[LWS97] oder Szeliski und Lavallee [SL96] in ein Steuergitter der Große nx×ny ×nz mit Gitter-abstand δ eingebettet, welches iterativ verfeinert werden kann. Dieses definiert zusammen mitTng ein stetiges Deformationsfeld durch B-Spline-Basisfunktionen Bi, die an jedem Gitterpunktdefiniert sind (s. Abb. 4). Mit c als der Bezeichnung der Steuerpunkte, u = x/nx − bx/nxc,v = y/ny − by/nyc, w = z/nz − bz/nzc der relativen Positionen der Bildpunkte in einer Gitter-zelle und i = bx/nxc − 1, j = by/nyc − 1, k = bz/nzc − 1 der Gitterindizes des Knotens fur B0

ergibt sich

Tnl(x) =

3∑

l=0

3∑

m=0

3∑

n=0

Bl(u)Bm(v)Bn(w)ci+l,j+m,k+n. (16)

Die Basisfunktionen Bi sind

B0(t) = (−t3 + 3t2 − 3t + 1)/6,

B1(t) = (3t3 − 6t2 + 4)/6,

B2(t) = (−3t3 + 3t2 + 3t + 1)/6,

B3(t) = t3/6.

(17)

fij ist im Allgemeinen nicht surjektiv. Es ist praktisch kaum durchfuhrbar, die Formen so zuregistrieren, daß sie sich vollstandig uberdecken. Kritischer ist eine Uberfaltung, bei der die Injek-tivitat der Abbildung verloren geht (s. Abb. 4, 5). Um die Deformation einzuschranken, werden

Abbildung 4: Vektorfeld einer B-Spline-Deformation. In der Bildmitte ist deutlicheine globale Uberfaltung erkennbar.

Abbildung 5: Lokale Uberfaltung: Der markierte Bereich be-zeichnet eine Bildregion, die in zwei Schritten durch Verschie-bung eines Steuerpunktes deformiert wird. Im zweiten Schrittensteht die Mehrdeutigkeit.

in den unten vorgestellten Verfahren folgende Regularisierer eingesetzt:

a) VerformungsenergieDie Biegungsenergie einer dunnen Metallplatte wird als Modell fur die Verformung des Raumesdurch Spline-Interpolationsfunktionen hergenommen [Boo89]:

∫

�3

(

∂2T

∂x2

)2

+

(

∂2T

∂y2

)2

+

(

∂2T

∂z2

)2

+ 2

[

(

∂2T

∂x∂y

)2

+

(

∂2T

∂x∂z

)2

+

(

∂2T

∂y∂z

)2]

dx. (18)

Im Falle der B-Splines wird daraus eine Summation uber die Steuerpunkte. Wenn nur eine affineTransformation vorliegt, ist der Term Null, ansonsten sorgt er fur eine Glattung der Abbildung.

5Bei Szeliski und Lavallee [SL96] werden auch trilineare und quadratische Transformationen zugelassen.

12

b) Regularisierung mit Stabilisierern Die ’Verformungsenergie’ ist ein Tichonow-Stabilisiererzweiter Ordnung [Sze89, SL96], und damit ein Spezialfall der allgemeinen Regularisierung

P (T) =1

2

p∑

m=0

wmRm(T) (19)

mit dem Gewicht wm und dem Tichonow-Stabilisierer m-ter Ordnung

Rm(T(x)) =

∫

�3

∑

j1+···+jd=m

m!

j1! · · · jd!

∣

∣

∣

∣

∣

∂mT(x)

∂xj11 · · · ∂xjd

1

∣

∣

∣

∣

∣

2

dx. (20)

Der Stabilisierer nullter Ordnung bestraft die Ausdehnung des Volumens, wahrend der Stabili-sierer erster Ordnung lineare Variationen in T bestraft.

c) Jacobi-DeterminanteDie Determinante der Jacobischen Matrix [Wun97],

|J(T(x))| =

∣

∣

∣

∣

∣

∣

∂T1

∂x∂T2

∂x∂T3

∂x∂T1

∂y∂T2

∂y∂T3

∂y∂T1

∂z∂T2

∂z∂T3

∂z

∣

∣

∣

∣

∣

∣

, (21)

wobei Ti die i-te Koordinatentransformation ist, gibt den Faktor an, um den sich das Volumeneines Voxels mit dem Zentrum (x, y, z) unter der Transformation T andert. Wenn |J | = 0,ist die lineare Unabhangigkeit der Basisvektoren des Koordinatensystems verloren gegangenund damit die Injektivitat. Wenn |J | < 0, ist aus dem rechtsdrehenden Koordinatensystem einlinksdrehendes geworden, die Transformation bewirkt eine lokale Uberfaltung. Mit

∫

�3

V (J,T(x)) dx, V (J,T(x)) =

{

log |J(T)| wenn |J(T)| > 0,∞ sonst

(22)

erhalt man ein entsprechendes Maß fur die gesamte Form.Durch Bewertung der Jacobi-Determinante werden lokale Uberfaltungen (s. Abb. 5) ausgeschlos-sen, wahrend globale Uberfaltungen (s. Abb. 4) lediglich unwahrscheinlicher werden.

5.1.1 Volumenregistrierung

Die von Frangi et al. [FRSN02] verwendete Methode ist eine Freiform-Bildregistrierung, die zurInterpolation B-Splines nach Lee et al. (s. Kap. 5.1) verwendet. Es handelt sich um ein Multi-skalenverfahren, bei dem auf jeder Stufe das Steuergitter verfeinert wird. So vermeiden sie lokaleMinima der Optimierung, deren Parameter die Steuerpunkte sind. Sie registrieren das ganze Vo-lumen, welches aus Voxeln besteht, die keine Grauwerte, sondern Marken tragen. Als Metrik furdie Bildregistrierung dient die Markenkonsistenz (s. Kap. 4.2) erganzt um den Regularisierungs-term ’Verformungsenergie’ (s. Kap. 5.1). Restriktive Annahmen uber die Topologie der Objektesind nicht notig. Der erfolgreiche Einsatz zur Erzeugung statistischer Formmodelle der rechtenund linken Ventrikel des Herzens wird demonstriert. Das Funktional wird maximiert mittelseines Gradientenaufstiegsverfahren. Die Hauptmodenanalyse wird anschließend auf Grundlageder Deformationsvektoren durchgefuhrt.Bei diesem Ansatz wird die Geometrie der Formen nicht berucksichtigt. Die Verformung desVolumens wird auf willkurliche Art und Weise eingeschrankt, in dem Fall durch die ’Verfor-mungsenergie’. Eine Verwendung der Jacobideterminante an der Stelle wurde grundsatzlich eineebenso gute Abbildung im Sinne der verwendeten Metrik liefern, dennoch sahe das Gitter dannanders aus. Auch ganz ohne Einschrankung wurde die Bildregistrierung gelingen, allerdings sinddann Uberfaltungen wahrscheinlicher. Die Punkte, welche aufeinander abgebildet werden, wer-den aufgrund ihrer Marken unterschieden, welche in großen Bereichen homogen sind. Dadurchwird die Qualitat der Ubereinstimmung problematisch. Um die Korrespondenz zu verbessern,also die Abbildung homologer Punkte aufeinander zu befordern, ist folgende Modifikation denk-bar:

13

Skizze: Propagation geometrischer Eigenschaften Ausgangspunkt fur die Bildregistrie-rung sind nicht die homogenen Voxelbilder nach der manuellen Segmentierung, sondern dieextrahierten triangulierten Oberflachen Si der Formen. Auf den Si werden fur jeden Vertex geo-metrische Eigenschaften gj bestimmt, z.B. Normalenvektor oder Krummung. Jeder Punkt derOberflache tragt also neben seinen Koordinaten noch Information uber die lokale Geometrie derOberflache. Dieser Wert wird mittels einer Distanztransformation [Bor96] in den R

3 propagiert.Registriert werden nun diese Bilder der Referenzform Sr mit den Si nach dem vorhergehendenVerfahren, wobei geeignete Metriken zu entwickeln sind. Fur verschiedene gj konnen einzelnBildregistrierungen durchgefuhrt werden, deren Ergebnisse in geeigneter Weise kombiniert wer-den mussen. Wenn dies fur jede Form durchgefuhrt wurde, kann die Parametrisierung einerReferenzoberflache auf die Si ubertragen werden.

5.1.2 Oberflachenregistrierung

Bei der Bildregistrierung von Oberflachen werden grundsatzlich die Abstande zwischen denOberflachen minimiert. Ein wegweisendes Verfahren fur die Klasse der affinen Transformationenwar der Iterative-Closest-Points-Algorithmus (ICP) von Besl und McKay [BM92]. Einige der hiervorgestellten Registrierungsverfahren konnen als Derivate dieses Algorithmus betrachtet werden.

Iterative-Closest-Points

Eingabe: Eine Punktmenge {pi}, i = 1 . . . N , eine Zielpunktmenge {qj}, j = 1 . . . M .

Ausgabe: Eine rigide Transformation Tg, welche d(Si, Sj) minimiert.

1. Finde in Iteration k zu jedem Punkt pi den nachsten Punkt qj der Zielpunktmenge, sodaß d(pj , Si) = d(pj ,qj).

2. Bestimme analytisch minTkg

∑

i(Tkg(p

ki ) − (qk

j ))2.

3. Wende Tkg auf jeden Punkt pi an, um eine neue Punktmenge {pk+1

i } zu erhalten.

4. Terminiere die Iteration nach dem Abbruchkriterium. Ansonsten setze k = k + 1 undwiederhole von 1.-4.

Abbruchkriterium:

a) d(Si, Sj) unterschreitet eine feste Schranke.

b) Der Unterschied zwischen Tkg und Tk+1

g fallt unter eine feste Schranke.

c) Eine Hochstzahl an Iterationen wird erreicht.

Es gibt zahlreiche Variationen, wo neben den Punktabstanden noch andere Maße, z.B. geo-metrische, verwendet werden, um die Transformation zu bewerten [RL01, SLW02]. In unseremKontext genugen allerdings rigide Transformationen nicht, um zwei Oberflachen zufriedenstel-lend aufeinander abzubilden. Adaptionen fur Freiform-Oberflachenregistrierung findet man in[SL96, XF04, CR03]. Chui und Rangarajan entwickeln zusatzlich das bemerkenswerte Optimie-rungsverfahren Soft Assign und nennen ihren Algorithmus Robust Point Matching [CR03].

Auf dem ICP-Algorithmus basierende Verfahren bringen Korrespondenzfunktionen hervor, wel-che weder injektiv noch surjektiv sind, weil es leicht moglich ist, daß fur einige Punkte keinekorrespondierenden Punkte vorhanden sind. Das kann dazu fuhren, daß nach Optimierung einesbeliebigen Ahnlichkeitsmaßes (s. Kap. 4.2) mehrere Punkte pi mit demselben pj korrespondie-ren.

14

ICP fur Kurvensegmente Caunce und Taylor [CT99] erstellen statistische Modelle vonGehirnen. Jede Form Sn wird mit einer willkurlich ausgewahlten Referenzform Srregistriert.Sie verwenden den ICP-Algorithmus, ohne dabei die rigide Transformation durch eine Freiform-Transformation zu ersetzen. Stattdessen verbessern sie die Korrespondenz, in dem sie nebendem Euklidischen Abstand (s. Gl. (6)) einige weitere Informationen auswerten (s. Kap. 4.2). IhrFunktional lautet (mit δ ≈ 0)

E(f,pi, Sj) = deij(pi, f(pj)) ·

2 + δ

dnij(pi, f(pj)) + 1 + δ

·1 + δ

dtij(pi, f(pj)) + δ

·1 + δ

dhij(pi, f(pj)) + δ

,

welches fur eine erste Stufe verwendet wird, wo sie Kurvensegmente registrieren. Das Funktionalwird nur fur E > 0 ⇔ 〈ti, tj〉 ∈ [0, π

2 ] ausgewertet. Es wird durch extensive Suche minimiert undliefert jeweils einen korrespondierenden pj ∈ Sj. Nachdem auf diese Weise eine Punktkorrespon-denz bestimmt wurde, wird in einem Abstimmungsverfahren festgelegt, daß die Kurvensegmentemit den meisten Punktkorrespondenzen als korrespondierend betrachtet werden.In der zweiten Stufe werden dann mittels de

ij erneut Punktkorrespondenzen gesucht, aber nurnoch innerhalb der korrespondierenden Kurvensegmente. Dazu werden noch die korrespondieren-den Kurvenstucke auf gleiche Großen skaliert, auf ihre Schwerpunkte aligniert und gegebenenfallsneu verbunden. In einer Analyse zeigen die Autoren, daß sich die Punktkoharenz (s. Gl. (3)),ausgehend vom klassischen ICP-Algorithmus, immer mehr verbessert, wenn man zuerst dn

ij unddt

ij einbezieht, dann das Abstimmungsverfahren, die Skalierung, Alignierung und Verbindung

und schließlich noch dhij hinzunimmt.

Subsol et al. [STA98] registrieren ebenfalls Kurvensegmente mittels einer Adaption von ICP. Siezeigen ihr Verfahren in der Anwendung auf Schadelmodelle. Ihr Ansatz ist jedoch methodischuberzeugender, da sie anstelle von rigiden Transformationen B-Spline-basierte Transformationen(s. Kap. 5.1) zulassen und weiterhin die Kurvensegmente nicht durch einen Heurismus (s. Kap.4.1), sondern aufgrund von Pfaden maximaler Krummung gewinnen, welche geometrische Inva-rianten einer Oberflache darstellen. Sie betonen die anatomische Relevanz ihrer Formbeschrei-bung, welche mit durch Mediziner definierten weithin ubereinstimmen. Die Korrespondenzenfinden sie wie Caunce und Taylor zunachst zwischen Kurvensegmenten mit Hilfe eines Abstim-mungsverfahrens und dann zwischen den Punkten der korrespondierenden Segmente. Um dieKorrespondenzfindung bijektiv zu machen, fuhren sie Injektivitats- und Punktordnungsrand-bedingungen ein, benutzen aber als Ahnlichkeitsmaß nur de

ij (s. Gl. (6)) erweitert um einenTichonow-Stabilisierer (s. Kap. 5.1).

Das Konsistenzproblem (s. Kap. 4.1.1) losen beide Ansatze nicht. Es wird nicht vorgesehen,daß sich die Kurvensegmente wahrend der Optimierung auf der Oberflache der Form bewegen.Auch finden sie keine dichte Korrespondenz: Subsol et al. nennen als wunschenswerte Zahl vonKurvensegmenten 20 bis 30 [STA98]! Beide Verfahren eignen sich nur fur Anwendungen, woausgepragte Kurvensegmente extrahiert werden konnen. Fur Schadel und Gehirn ist das, wiedie Autoren zeigen, in robuster Weise moglich, fur andere Organe, wie z.B. Leber oder Herz, imAllgemeinen jedoch nicht.

Einbettung der Oberflache in B-Spline-Steuergitter Fleute et al. [FLJ99] schilderndie Erzeugung statistischer Formmodelle von Oberschenkelknochen. Sie betten die Formober-flache in ein B-Spline-Steuergitter ein (s. Kap. 5.1), wozu sie die Methode von Szeliski und La-vallee [SL96] benutzen. Dort werden auch die Stabilisierer m-ter Ordnung (s. Kap. 5.1) beschrie-ben, welche zur Regularisierung eingesetzt werden. Die Bildregistrierung ist eine Minimierungder Fehlerquadrate, wobei als Fehler der oben erwahnte Abstand der Oberflachen betrachtetwird (s. Gl. (7)). Wegen seiner guten Konvergenzeigenschaften wird der Levenberg-Marquardt-Algorithmus verwendet. 3D-Distanzfelder werden vorausberechnet [Bor96], um die Berechnungenzu beschleunigen. Weiterhin wird das Gitter mit den zugehorigen B-Spline-Basisfunktionen insogenannten Octrees abgespeichert, was eine effiziente Implementation des auch hier verwende-ten Multiskalenverfahrens erlaubt [SL96]. Die Robustheit des Algorithmus wird erhoht, indem

15

nach Konvergenz der Optimierung erneut einige Male iteriert wird, wobei Ausreißer, fur died2 � σ2 gilt, aus der Punktmenge entfernt werden.Wenn alle Sn mit Sr registriert worden sind, wird daraus ein erster mittlerer Formvektor v

berechnet. Danach wird bis zur Konvergenz wiederholt erneut registriert und gemittelt, was zurAbmilderung der Dominanz der Referenzform dient (s. Kap. 4).

Euklidischer Abstand und Oberflachengeometrie Mit der semiautomatischen Methodevon Wang et al. [WPS00] werden korrespondierende Punkte zweier Oberflachen in zwei Stufenanders als bei ICP direkt bestimmt. Zunachst wird eine Oberflache Sr trianguliert. Dann wirdSr mit den Sn affin registriert. Da es sich bei den Formen um Aufnahmen des Gehirns han-delt, wo man leicht zwei verschiedene Bereiche unterscheiden kann, namlich ’Taler’ (Sulci) und’Hohenzuge’ (Gyri), werden Vertizes interaktiv ausgewahlt und markiert: Neben gewohnlichenSulci (Marke Nr. 3) und Gyri (Nr. 4) werden noch Punkte in Spalten zwischen den Gehirnhe-mispharen (Nr. 1) und Punkte in Falten am Gehirnstamm (Nr. 2) markiert. Diese Unterschei-dung wird benutzt, um die Eindeutigkeit der Korrespondenz zu befordern: Fur Punkte, die mitMarken Nr. 3 und Nr. 4 ausgestattet sind, werden korrespondierende Punkte gesucht, nachdemdie Bilder mit einem Gaußfilter mit σ = 0.5 geglattet worden sind. Fur die Marken Nr. 1 undNr. 2 wird σ = 1.5 bzw. σ = 2.5 verwendet (s. Abb. 6).

Abbildung 6: Durch das Krummungsmaß markierte Sulci (rot) und Gyri (grun).Oben: Dorsale Ansicht; Unten: Ventrale Ansicht (aus Wang [WPS00]).

Mit dem Formindex (s. Gl. (11)) lassen sich Punkte eindeutig den Klassen Sulcus oder Gyruszuordnen. Zusammen mit dem Ausmaß der Krummung (s. Gl. (12)) wird daraus ein featurematch mij, welches angibt, mit welcher Sicherheit zwei Punkte pi ∈ Si und pj ∈ Sj einemgemeinsamen Bereich angehoren. Das Funktional lautet dann

E(f,pi, S′j) = (1 + de

ij(pi, f(pi))) · (2 − dnij(pi, f(pi))) · mij(pi, f(pi)),

welches fur jeden pi ∈ Sr in einer Region S ′j ⊆ Sj durch extensive Suche minimiert wird und

damit jeweils einen korrespondierenden pj ∈ Sj liefert. Wenn fur jeden der auf der Referenzo-berflache markierten Punkte ein korrespondierender Punkt pj gefunden wurde, wird eine dichteKorrespondenz definiert, indem die pj ∈ Sj mittels Suche nach dem geodatischen kurzesten Pfad[WPS00], verbunden werden. In der Mitte der Verbindungslinien werden Vertizes eingefugt, diemit entsprechenden Zwischenpunkten der Referenztriangulierung korrespondieren. Dieser Pro-zeß wird mehrmals wiederholt, bis eine Menge {frj} von Korrespondenzfunktionen frj : Sr → Sj

fur j = 1 . . . N − 1 vorliegt. Durch die zweite Stufe der Korrespondenzfindung wird eine gewisseKontinuitat der Korrespondenzfunktion gewahrleistet. Die Wahrscheinlichkeit, daß benachbartePunkte korrespondieren, wird erhoht.Das Verfahren ist bei der Anwendung auf Gehirne sehr erfolgreich, insbesondere weil hier dieKorrespondenz auch anatomisch fundiert ist. Fraglich ist allerdings, ob ein feature match fur

16

andere Formen mit einer ebensolchen Aussagekraft wie im Falle der Gyri und Sulci definiertwerden kann.

5.2 Implizite Korrespondenz

Den in diesem Abschnitt zusammengefaßten Verfahren ist gemeinsam, daß hier nicht explizitnach einer Korrespondenzfunktion gesucht wird, sondern nach geeigneten Parametrisierungender Formen: Anstatt direkt eine Funktion von einer Form auf die andere zu definieren, kannman, um die Korrespondenz zu finden, auch die Oberflachen Sn auf eine Zwischenoberflache Z,welche topologisch aquivalent ist, mittels einer Hilfsfunktion hn abbilden: hn : Sn → Z.Die Korrespondenzfunktion fij ergibt sich dann aus einer Uberlagerung der stetigen Parametri-sierungen:

fij = h−1j ◦ hi, fij : Si → Sj . (23)

Weil die hi bijektiv sind, ist auch fij bijektiv.

5.2.1 Kanonische Parametrisierung

Abbildung auf Einheitskugel Kelemen et al. [KSG99] verwenden fur die Erzeugung ihresstatistischen Formmodells die Koeffizienten der Entwicklung nach den spharischen Harmoni-schen, welche sie aus einer stetigen Oberflachenparametrisierung nach Brechbuhler [BGK95]gewinnen: Um die Formen auf eine invariante, kanonische Weise zu reprasentieren, parametrisie-ren sie die Oberflache der Formen zunachst, indem sie eine stetige bijektive Abbildung von denOberflachen, in dem Fall sind das die außeren Seiten der Randvoxel, auf die Oberflache einerEinheitskugel definieren. Dies wird als nichtlineares Optimierungsproblem mit Randbedingungenformuliert: Die zu maximierende Zielfunktion ist 1

2

∑3i=0 cos si, wobei cos si das Skalarprodukt

der beiden Vektoren vom Zentrum der Kugel zu den Endpunkten der Seite ist (s. Abb. 7). JedeRegion der Objektoberflachen muß auf eine proportionale Region der Einheitskugel abgebildetwerden, damit ist die Parametrisierung flachenerhaltend. Uberfaltungen werden ausgeschlossen,indem die Winkel αi der spharischen Vierecke auf das Intervall [0, π] eingeschrankt werden.So wird auch eine homogene Dichte des Parameterraumes erreicht. Auf der Grundlage dieser

Abbildung 7: Jede Außenseite der Randvoxel wird auf ein spharisches Viereck abgebildet. Weil derRadius der Kugel eins ist, hat jede Seite si die Lange des zugehorigen Zentrumswinkels im Bogenmaß (ausBrechbuhler [BGK95]).

Parametrisierung wird eine Entwicklung ahnlich einer Fourier-Reihe durchgefuhrt:

v(θ, φ) =

∞∑

l=0

l∑

m=−l

cml Y m

l (θ, φ), (24)

17

wobei Y ml die spharische Harmonische m-ter Ordnung vom Grade l ist [GD86]. Die Koeffizienten

cml beschreiben raumliche Frequenzbestandteile der Formen und somit hierarchisch globale und

lokale Formeigenschaften (s. Abb. 8). Um Rotationsinvarianz herzustellen, wird der Parameter-raum so rotiert, daß der “Nordpol” (θ = 0) und der Schnittpunkt des “Greenwich Meridians”mit dem “Aquator” (φ = 0, θ = π

2 ) an den Hauptachsen der Ellipse, die durch die spharischenHarmonischen erster Ordnung beschrieben wird (s. Abb. 8b)), ausgerichtet wird. Damit erhaltman eine kanonische Parametrisierung, die eine Eins-zu-Eins-Punktkorrespondenz darstellt.

Abbildung 8: Modellbildung. (a) Manuelle Segmentierung des linken Hippocampus.(b) Rekonstruktion mit Oberflachenformdeskriptor bis Grad 1. (c) bis Grad 10. (d) Nor-malisierung der Position im Objektraum (aus Kelemen [KSG99]).

Die Autoren zeigen, daß diese Methode geeignet ist, Gehirnstrukturen wie Hippocampus oderThalamus verschiedener Individuen in Korrespondenz zu bringen. Dadurch, daß die Parametri-sierungen kanonisch sind, werden sie fur ahnliche Formen vergleichbar, d.h. Parameterkoordina-ten (θ, φ) befinden sich in ahnlichen Regionen der Form innerhalb der Elemente der Trainings-menge. Wegen der Verwendung der Einheitskugel als Zwischenoberflache beschrankt sich dasVerfahren auf Formen mit spharischer Topologie.Die Normalisierungsmethode verlangt, daß die Koeffizienten erster Ordnung eine echte Ellipsebeschreiben. Wenn die Ellipse rotationssymmetrisch ist oder gar zu einer Kugel degeneriert,kann das Verfahren nicht angewendet werden.

Harmonische Abbildung Anstelle einer Kugel benutzen Brett und Taylor eine Kreisschei-be, um mittels harmonischer Abbildungen eine kanonische Parametrisierung zu erhalten [BT00].Damit wird die erlaubte Topologie der Formen weiter eingeschrankt. Die Parametrisierung wirdwie folgt konstruiert:Zuerst werden die Randvertizes der triangulierten Oberflache proportional der Bogenlange vonD auf einen Kreis in R

2 abgebildet. Die Positionen der ubrigen Vertizes xi werden unter Mini-mierung eines Energiefunktionals berechnet:

Eh(x) =1

2

∑

{i,j}∈kanten(D)

κi,j ||xi − xj||2 (25)

Eh kann als die Energie einer Konfiguration von Federn interpretiert werden, wobei jeder Kan-te von D eine Feder zugeordnet wird. In die Berechnung der Federkonstante κi,j gehen dieLangen der Kanten {i, j} sowie die Flache der Facetten, welche an {i, j} angrenzen, ein. DieseApproximation der harmonischen Abbildung nach Eck et al. [ERD+95] ist ein lineares Optimie-rungsproblem, welches analytisch (∇Eh = 0) gelost wird.In einem weiteren Schritt werden Oberflachen Sn, n = 1 . . . N − 1 mittels einer ICP-Variante

18

(s. Kap. 5.1.2) mit einer Referenzoberflache Sr registriert. Dadurch wird das Verfahren asym-metrisch (s. Kap. 4). Bei der Bildregistrierung werden neben den Euklidischen Abstanden derPunkte (s. Gl. (6)) noch die Ubereinstimmung der Oberflachennormalen (s. Gl. (9)) als Abstands-maß benutzt. Die resultierende Rotation wird dann auf die harmonischen ParametrisierungenPn angewendet, um die Korrespondenzfunktion (s. Gl. (23)) zu erhalten.

Convex-Combination Maps Bei Lamecker et al. [LLS03] sind die Formen Sn ebenfalls alstriangulierte Oberflachen Sn gegeben. Die Autoren beschreiben ein individuelles, asymmetrischesKorrespondenzfindungsverfahren. In einer interaktiven Vorverarbeitung wird jede Oberflachegleichermaßen in Flachenstucke mit der Topologie von Kreisscheiben zerlegt. Jedes Flachenstuckwird auf das entsprechende Flachenstuck der Referenzoberflache abgebildet (s. Abb. 9). Dies

Abbildung 9: Ein Homoomorphismus f zwischen den Formen (Lebern) S1 und S2 wird berechnet, indem jedesFlachenstuck der zwei Formen nach Floater (s. Kap. 4.2) mittels der verzerrungsminimierenden Abbildungen φ1

and φ2 auf eine Kreisscheibe abgebildet wird. Die Rander werden proportional zur Bogenlange auf den beidenOberflachen abgebildet. Die resultierende Abbildung fur ein Flachenstuck ist φ−1

2 ◦φ1 (aus Lamecker et al. [LLS03]).

wird uber die Parametrisierung mittels Convex-Combination Maps [Flo97] erreicht, d.h. hierwerden keine Zwischenoberflachen verwendet, der Parameterraum ist eine Kreisscheibe. Convex-Combination Maps approximieren fur jeden Vertex lokal die geodatische polare Abbildung (s.Abb. 10). Auf diese Weise konnen Verzerrung, lokale Scherung und Skalierung der Oberflache in

Abbildung 10: Die geodatische polare Abbildung wird um die sternformige Nachbarschaft eines Ver-tizes xi einer Oberflachentriangulisierung approximiert: Die Vertizes xjk werden auf pk so abgebildet,daß ||pk − p|| = ||xjk − xi|| und θ′ = 2πθk/

� ni

l=1θl (aus Lamecker et al. [LLS03]).

einem linearen Optimierungsverfahren minimiert werden. Durch Uberlagerung der Parametri-sierungen von entsprechenden Flachenstucken erhalt man die Korrespondenzfunktion wie in (s.Gl. (23)). Sind die Korrespondenzen bekannt, konnen mit einer Minimierung der Fehlerquadra-te analytisch affine Transformationen berechnet werden, welche die Formen in ein gemeinsameKoordinatensystem uberfuhren.In diesem Verfahren wird besonders die Konnektivitat der Punkte und die lokale Geometrie derOberflache berucksichtigt, was fur eine anatomisch plausible Korrespondenz ein vielversprechen-der Ansatz ist.

19

5.2.2 Minimale Beschreibungslange

Davies et al. [DTC+02] betrachten das Korrespondenzproblem ebenfalls als die Suche nach einergeeigneten Parametrisierung {Φn} der verschiedenen Formoberflachen. Eine stetige Parametri-sierung der Formoberflache mittels spharischer polaren Variablen (θ und φ) nach Brechbuhler (s.Kap. 5.2.1) wird mit Hilfe der asymmetrischen θ-Transformation in einem Multiskalenverfahrenoptimiert. Einer Veranderung der Parametrisierung der Oberflache entspricht eine Veranderungder Position der auf die Einheitskugel abgebildeten Vertizes,

Sn → S′n, θ → θ′, φ → φ,′ (26)

wobei Sn(θ, φ) = S′n(θ′, φ′) und θ′ = Φθ

n(θ, φ), φ′ = Φφn(θ, φ) ist. Gultige Parametrisierungs-

funktionen Φn sind homoomorphe Abbildungen der Kugel. Es wird zunachst nur eine Repa-rametrisierung θ → f(θ) betrachtet (symmetrische θ-Transformation), wofur die Autoren dieCauchy-Verteilung [Mar72] verwenden. Sie wird durch eine variable Breite a um den Punkt Pund eine Amplitude A definiert (Cauchy-Kern).Diese Parametrisierung kann zu θ → f(θ, φ) modifiziert werden, indem die Amplitude als glatteFunktion von φ geschrieben wird: A → A(φ), wozu wiederum die Cauchy-Verteilung benutztwird (asymmetrische θ-Transformation, s. Abb. 11).Verdrehungen und Scherungen um die Achse erreicht man, wenn man φ auf ahnliche Weise wieθ parametrisiert.Wahrend der Optimierung wird auf jeder Auflosungsstufe die Einheitskugel annahernd uni-

Abbildung 11: Links: Originalkugel. Rechts: Kugel nach einer asym-metrischen θ-Transformation (aus Davies [DTC+02]).

form abgetastet, um die Cauchy-Kerne P zu plazieren. Nacheinander wird fur jeden Kern dieAmplitude A optimiert, wahrend die Breite a festgehalten wird. Mit der nachsten Iterationwird die Abtastrate erhoht und gleichzeitig a verringert, so wird die Parametrisierung immermehr verfeinert. Die Optimierung wird mit dem Nelder-Mead-Simplexalgorithmus durchgefuhrt[PTVF93], kurzlich wurde allerdings ein deutlich effizienterer Gradientenabstieg erster Ordnungvorgestellt [EA03], was die praktische Anwendbarkeit deutlich erhohen konnte.Nach der Definition von Davies et al. ist das beste Modell jenes mit der optimalen Kompaktheit,Spezifitat und Vollstandigkeit. Die Korrespondenz wird nach der Minimalen Beschreibungslangesimultan optimiert, welche jedoch ausschließlich die Kompaktheit des Modells beschreibt - Spe-zifitat und Vollstandigkeit lassen sich nicht in ein Optimierungsverfahren integrieren. Daß einModell mit optimaler Kompaktheit auch optimale Spezifitat und Vollstandigkeit aufweist bzw.auf anatomisch plausiblen Korrespondenzen aufbaut, konnte bisher nicht gezeigt werden.

Erweiterung um Krummung Die Methode von Davies et al. sucht eine kompakte Beschrei-bung der Positionen der Punkte auf den Oberflachen der Formen. Damit wird aber die Geometrie,ein wichtiges Charakteristikum, ignoriert.Thodberg und Olafsdottir [TO03] erweitern den Ansatz fur 2D-Formen, indem sie außer derKompaktheit noch die Ubereinstimmung der Krummung der Oberflachen optimieren. Die Ubert-ragung dieser Idee auf 3D-Formen ist Gegenstand zukunftiger Forschung.

20

5.3 Matching mit Formdeskriptoren

5.3.1 Modal Matching

Sclaroff und Pentland [SP95] hatten in einem fruheren Verfahren, ahnlich dem Prinzip der Ab-bildung auf Zwischenoberflachen, die Korrespondenz gesucht, indem sie einen elastischen Korperdurch Federn mit den Punkten der Form verbunden haben. Unter der Kraft, die durch die Fe-dern auf den Korper wirkt, paßt er sich an die Form an, bis er ein dynamisches Gleichgewichterreicht:

MU + DU + KU = R, (27)

wobei M die Massenmatrix, U die Knotenverschiebungen, D die Reibungsmatrix, K die Stei-figkeitsmatrix und R die Matrix der Federkrafte darstellen. Der genaue Aufbau dieses Finite-Elemente-Modells findet sich in [SP95]. Mittels einer Eigenanalyse findet man eine analytischeLosung fur diese Gleichung. Fuhrt man dies fur mehrere Formen durch, kann man direkt diePunktkorrespondenz ablesen, wenn man beobachtet, welche Punkte auf korrespondierende Ortedes elastischen Korpers projeziert werden.

Die Autoren vermeiden mit dem neuen Modal Matching bewußt die kanonische Parametrisie-rung, die dem vorigen Verfahren innewohnte. Sie pladieren dafur, daß die Daten selbst ihrenaturliche Parametrisierung bestimmen. Sie benutzen eine Reprasentation der Formen durchein lokales Koordinatensystem, welches ebenfalls auf einem Finite-Elemente-Modell aufbaut. Indieser neueren Variante werden aber die Punkte der Form als Knoten des Modells verwendet,es gibt keinen Zwischenkorper, der verformt wird.

Abbildung 12: Systemdiagramm (aus Sclaroff und Pentland [SP95]).

Die Eigenmoden dieses Modells, auch Modale Formvektoren genannt, geben an, wie ein Modusden Formvektor (s. Gl. (1)) durch Verschiebung der Punkte deformiert (a ∈ R):

v′n = vn + apk (28)

Die kartesischen Koordinaten eines Punktes konnen eindeutig der Art und Weise, wie er sichinnerhalb jedes Eigenmodus bewegt, zugeordnet werden. Die Verschiebungsvektoren eines Punk-tes unter allen Moden pk erzeugen eine Verschiebungssignatur. Die einzelnen Schritte werdendurch Abbildung 12 illustriert.Zur Korrespondenzfindung wird ausgenutzt, daß ahnliche Formen ahnliche niederfrequente Ei-genmoden aufweisen (s. Abb. 13), selbst unter affinen oder nicht-linearen geometrischen Trans-formationen. Die Ubereinstimmung der Richtungen der Verschiebungsvektoren der niederfre-quenten Moden fur pi ∈ Si und pj ∈ Sj wird gemessen (Modal Matching) unter Verwendung

21

einer Assoziatonsmatrix nach Shapiro und Brady [SB92]. In Abbildung 13 sieht man, daß diemit Vektoren versehenen Punkte der Formen a) und b) korrespondieren, wahrend der markiertePunkt der Form c) eine deutlich unterschiedliche Verschiebungssignatur besitzt. Das Konsistenz-

Abbildung 13: 1. Spalte: Ahnliche Originalformen. 2.-5. Spalte: Funf niederfrequenteModen. Zusatzlich sind die Verschiebungsvektoren jedes Modus fur drei ausgewahltePunkte der Formen eingezeichnet (aus Sclaroff und Pentland [SP95]).

problem wird durch diesen Ansatz dadurch gelost, daß dem Modell nicht die exakten Positio-nen der Knoten zugrundeliegen, sondern Punkte, die durch Gaußsche Interpolationsfunktionenverschmiert werden. Das kann man sich als eine Anreicherung des Knotenmodells mit einer wei-chen Fullmasse vorstellen. Wegen der Komplexitat des Finite-Elemente-Modells kann eine dichtePunktkorrespondenz nicht direkt gesucht werden. In einem Multiskalenverfahren wird deshalbanfangs mit einer niedrigen Auflosung des Modells gearbeitet, in das nur wenige Knoten einge-hen. Wegen der verwendeten Interpolationsfunktionen konnen dann die Knotenverschiebungendieses Modells auf eines einer hoheren Auflosung ubertragen werden.

6 Diskussion und Ausblick

Es wurde eine Auswahl bekannter Verfahren zur Korrespondenzfindung bei der Erzeugung sta-tistischer 3D-Formmodelle in biomedizinischen Anwendungen vorgestellt. Die Verfahren wurdenaufgrund einer mathematischen Formulierung des Korrespondenzproblems klassifiziert und ver-glichen.Sie unterscheiden sich weiterhin in ihrer Allgemeinheit bezuglich der Topologie der Formen: Dieauf der Bildregistrierung und auf der Verwendung von Formdeskriptoren basierenden Verfah-ren sind fur Formen beliebiger Topologie anwendbar, wahrend solche, die uber eine kanonischeParametrisierung eine implizite Korrespondenz suchen, grundsatzlich auf die Topologie des Pa-rameterraumes eingeschrankt sind. Lamecker et al. (s. Kap. 5.2.1) umgehen das Problem durchZerlegung der Form in Flachenstucke, die topologisch aquivalent einer Kreisscheibe sind.Die Komplexitat der Verfahren wurde lediglich hinsichtlich der verwendeten Optimierungsver-fahren bewertet. Da es sich um Standardverfahren handelt, deren eingehende Analyse uber denRahmen dieser Arbeit hinausgeht, muss hier eine grobe Einteilung genugen: Lineare Optimie-rungsprobleme sind die Verfahren von Lamecker et al. sowie, abgesehen vom Registrierungs-schritt, das von Brett und Taylor (s. Kap. 5.2.1). Der Ansatz von Sclaroff und Pentland (s. Kap.5.3.1) wird ebenfalls in geschlossener Form gelost. Die Bildregistrierung ist ein nichtlineares Op-timierungsproblem, welches sich mit Gradientenverfahren erster und zweiter Ordnung losen laßt.Fur die Optimierung der Minimalen Beschreibungslange wurden bisher ineffiziente, nichtgradi-entenbasierte nichtlineare Optimierer verwendet, kurzlich wurde jedoch ein Gradientenverfahrenerster Ordnung prasentiert [EA03].

Voraussichtlich werden Verfahren zur Korrespondenzfindung in Zukunft vermehrt geometrischeund andere strukturelle Formeigenschaften wie den Formkontext in das Kostenfunktional auf-nehmen, um der Korrespondenz eine großere anatomische Fundierung zu verleihen. Fur die

22

ICP-basierten Verfahren ware das analog zu schon vorhandenen Erweiterungen fur den klassi-schen ICP-Algorithmus leicht moglich [SLW02].Bei der Analyse der Verfahren wurde darauf geachtet, inwieweit sie der Anforderung, anato-misch plausible Korrespondenzen zu liefern, genugen. Dieses Kriterium ist schwer theoretisch zudefinieren, es unterliegt vielmehr dem subjektiven Urteil medizinisch geschulter Experten. Dahersind die semiautomatischen Verfahren von Lamecker et al. (s. Kap. 5.2.1) sowie von Wang undStaib (s. Kap. 5.1.2) in diesem Sinne positiv zu bewerten. Fur automatisierte Verfahren ist esnaheliegend, die Geometrie bzw. die Topographie der Formen in die Korrespondenzfindung ein-zubeziehen, was aber nur bei den verwandten Registrierungsverfahren von Caunce und Taylorsowie Subsol et al. (s. Kap. 5.1.2), bei den Parametrisierungsverfahren von Kelemen et al. (s.Kap. 5.2.1), Brett und Taylor (s. Kap. 5.2.1), Lamecker et al. (s. Kap. 5.2.1) sowie Thodbergund Olafsdottir (s. Kap. 5.2.2) geschieht.

Cootes zufolge wird man ein Zusammenwachsen der bisher eher getrennten Forschungen imBereich der Korrespondenzfindung zur statistischen Modellbildung und der Bildregistrierung er-leben [CTTN02], was durch die hier vorgestellten Bildregistrierungsansatze belegt wird.

Eine interessante Fragestellung ist, inwieweit sich die Volumenregistrierung nach Frangi et al.(s. Kap. 5.1.1) durch eine Erweiterung des Funktionals um Geometriemaße verbunden mit topo-graphischen Informationen (Distanztransformation) verbessern laßt. Ein entsprechender Ansatzwurde skizziert (s. Kap. 5.1.1).

23

Literatur

[AFP00] Audette, M., Ferrie, F., Peters, T.: An Algorithmic Overview of Surface RegistrationTechniques for Medical Imaging. In: MIA 4 (2000), Nr. 3, S. 201–217

[Bet97] Betten, J.: Finite Elemente fur Ingenieure. Bd. 1. Berlin und Heidelberg: Springer Verlag,1997

[BGK95] Brechbuhler, C., Gerig, G., Kubler, O.: Parametrization of Closed Surfaces for 3-DShape Description. In: CVIU 61 (1995), S. 154–170

[BKOS98] de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geo-metry, Algorithms and Applications. 2. Auflage. Berlin und Heidelberg: Springer Verlag,1998

[BM92] Besl, P.J., McKay, N.D.: A Method for Registration of 3-D Shapes. In: IEEE Trans. PAMI14 (1992), Nr. 2, S. 239–256

[BMP02] Belongie, S., Malik, J., Puzicha, J.: Shape Matching and Object Recognition Using ShapeContexts. In: IEEE Trans. PAMI 24 (2002), Nr. 4, S. 509–522

[Boo89] Bookstein, F.L.: Principal Warps: Thin-Plate Splines and the Decomposition of Deforma-tions. In: IEEE Trans. PAMI 11 (1989), Nr. 6, S. 567–585

[Bor96] Borgefors, G.: On Digital Distance Transforms in Three Dimensions. In: CVIU 64 (1996),Nr. 3, S. 368–376

[BT00] Brett, A.D., Taylor, C.J.: Automated Construction of 3D Shape Models Using HarmonicMaps. In: MIUA (2000), S. 175–178

[CHTH93] Cootes, T.F., Hill, A., Taylor, C.J., Haslam, J.: The Use of Active Shape Models forLocating Structures in Medical Images. In: Proc. 13th ICIPMI, 1993, S. 33–47

[Coo04] Cootes, T.F.: Timeline of Developments in Algorithms for Finding Correspondences AcrossSets of Shapes / Wolfson Image Analysis Unit, Universitat Manchester. 2004. – Forschungs-bericht. http://www.isbe.man.ac.uk

[CR03] Chui, H., Rangarajan, A.: A New Point Matching Algorithm for Non-Rigid Registration.In: CVIU 89 (2003), Nr. 2/3, S. 114–141

[CT99] Caunce, A., Taylor, C.J.: Using Local Geometry to Build 3D Sulcal Models. In: Proc.16th ICIPMI, 1999, S. 196–209

[CT01] Cootes, T.F., Taylor, C.J.: Statistical Models of Appearance for Computer Vision /Wolfson Image Analysis Unit, Universitat Manchester. 2001. – Entwurf

[CTCG95] Cootes, T.F., Taylor, C.J., Cooper, D.H., Graham, J.: Active Shape Models - theirTraining and Application. In: CVIU 61 (1995), Nr. 1, S. 38–59

[CTTN02] Cootes, T.F., Taylor, C.J., Twining, C., N.Thacker: A Framework for Building Defor-mable Atlases / Wolfson Image Analysis Unit, Universitat Manchester. 2002. – Forschungs-bericht

[CZR04] Chui, H., Zhang, J., Rangarajan, A.: Unsupervised Learning of an Atlas from UnlabeledPoint-Sets. In: IEEE Trans. PAMI 26 (2004), Nr. 2, S. 160–172

[DTC+02] Davies, R.H., Twining, C.J., Cootes, T.F., Waterton, J.C., Taylor, C.J.: 3D StatisticalShape Models Using Direct Optimisation of Description Length. In: Proc. 7th ECCV Bd. 3,2002, S. 3–20

[EA03] Ericsson, A., Astrom, K.: Minimizing the Description Length Using Steepest Descent. In:14th BMVC Bd. 2, 2003, S. 93–102

[ERD+95] Eck, M., de Rose, T., Duchamp, T., Hoppe, H., Lounsberry, M., Stuetzle, W.: Mul-tiresolution Analysis of Arbitrary Meshes. In: Proc. SIGGRAPH Bd. 29, 1995, S. 173–182

[FLJ99] Fleute, M., Lavallee, S., Julliard, R.: Incorporating a Statistically Based Shape Modelinto a System for Computed-Assisted Anterior Cruciate Ligament Surgery. In: MIA 3 (1999),Nr. 3, S. 209–222

[Flo97] Floater, M.S.: Parametrization and Smooth Approximation of Surface Triangulations. In:Computer Aided Geometric Design 14 (1997), S. 231–250

24

[FRSN02] Frangi, A.F., Ruckert, D., Schnabel, J.A., Niessen, W.J.: Automatic Construction ofMultiple-Object Three-Dimensional Shape Models: Application to Cardiac Modeling. In:IEEE Trans. MI 21 (2002), Nr. 9, S. 1151–1166

[GD86] Greiner, W., Diehl, H.: Theoretische Physik - Ein Lehr- und Ubungsbuch fur Anfangsse-mester. Bd. 3: Elektrodynamik. Zurich u. Frankfurt a.M.: Verlag H. Deutsch, 1986

[HBHH01] Hill, D.G.L., Batchelor, P.G., Holden, M., Hawkes, D.J.: Medical Image Registration.In: Physics in Medicine and Biology 46 (2001), S. 1–45

[HHI95] Higuchi, K., Hebert, M., Ikeuchi, K.: Building 3D Models from Unregistered RangeImages. In: Graphical Models and Image Processing 57 (1995), Nr. 4, S. 315–333

[JH97] Johnson, A., Hebert, M.: Surface Registration by Matching Oriented Points. In: Proc.3DIM., 1997

[Jol86] Jolliffe, I.T.: Principal Component Analysis. 1. Auflage. New York: Springer Verlag, 1986

[KG92] Khambamettu, C., Goldgof, D.B.: Point Correspondence Recovery in Non-Rigid Motion.In: IEEE CVPR’92, 1992, S. 222–227

[KNFM04] Kabus, S., Netsch, T., Fischer, B., Modersitzki, J.: B-Spline Registration of 3D Imageswith Levenberg-Marquardt Optimization. In: Proc. SPIE MI Bd. 5370, 2004

[KPNK03] Kortgen, M., Park, G.-J., Novotni, M., Klein, R.: 3D Shape Matching with 3D ShapeContexts. In: The 7th Central European Seminar on Computer Graphics, 2003

[KSG99] Kelemen, A., Szekely, G., Gerig, G.: Elastic Model-Based Segmentation of 3D Neurora-diological Data Sets. In: IEEE Trans. MI 18 (1999), Nr. 10, S. 828 –839

[LC87] Lorensen, W.E., Cline, H.E.: Marching Cubes: A High Resolution 3D Surface ConstructionAlgorithm. In: Computer Graphics 21 (1987), Nr. 4, S. 163–169

[LK00] Lorenz, C., Krahnstover, N.: Generation of Point-Based 3D Statistical Shape Models forAnatomical Objects. In: CVIU 77 (2000), S. 175–191

[LLS03] Lamecker, H., Lange, T., Seebaß, M.: Segmentation of the Liver Using a 3D StatisticalShape Model. 2003. – eingereicht

[LWS97] Lee, S., Wolberg, G., Sung, Y.S.: Scattered Data Interpolation with Multilevel B-Splines.In: IEEE Trans. on Visualization and Computer Graphics 3 (1997), Nr. 3, S. 337–354

[Mar72] Mardia, K.V.: Statistics of Directional Data. London: Academic Press, 1972

[MMF98] Maurer, C.R., Macunias, R.J., Fitzpatrick, J.M.: Registration of Head CT Images toPhysical Space Using a Weighted Combination of Points and Surfaces. In: IEEE Trans. MIBd. 17, 1998, S. 753–61

[MT96] McInerney, T., Terzopoulos, D.: Deformable Models in MIA. In: Proc. IEEE Workshopon Mathematical Methods in Biomedical Image Analysis. San Francisco, 1996, S. 171–180

[PTVF93] Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P.: Numerical Recipesin C. Cambridge University Press, 1993

[RL01] Rusinkiewicz, S., Levoy, M.: Efficient Variants of the ICP Algorithm. In: Proc. of ThirdInternational Conference on 3D Digital Imaging and Modelling, 2001, S. 145–152

[Roh00] Rohlfing, T.: Multimodale Datenfusion fur die bildgesteuerte Neurochirurgie und Strahlen-therapie, Technische Universitat Berlin, Diss., 2000

[SB92] Shapiro, L., Brady, J.: Feature-Based Correspondence: An Eigenvector Approach. In:Image and Vision Computing 10 (1992), S. 283–288

[SL96] Szeliski, R., Lavallee, S.: Matching 3-D Anatomical Surfaces with Non-Rigid Deformationsusing Octree-Splines. In: IJCV 18 (1996), Nr. 2, S. 171–186

[SLW02] Sharp, G.C., Lee, S.W., Wehe, D.K.: ICP Registration Using Invariant Features. In: IEEETrans. PAMI 24 (2002), Nr. 1, S. 90–102

[SP95] Sclaroff, S., Pentland, A.P.: Modal Matching for Correspondence and Recognition. In:IEEE Trans. PAMI 17 (1995), Nr. 6, S. 545–561

25

[STA98] Subsol, G., Thirion, J.-P., Ayache, N.: A Scheme for Automatically Building Three-Dimensinal Morphometric Anatomical Atlases: Application to Skull Atlas. In: MIA 2 (1998),Nr. 1, S. 37–60

[Sze89] Szeliski, R.: Bayesian Modeling of Uncertainty in Low-Level Vision. Boston, Massachusetts:Kluwer Academic Publishers, 1989

[TO03] Thodberg, H.H., Olafsdottir, H.: Adding Curvature to Minimum Description LengthShape Models. In: 14th BMVC Bd. 2, 2003, S. 251–260

[WPS00] Wang, Y., Peterson, B. S., Staib, L.H.: Shape-Based 3D Surface Correspondence UsingGeodesics and Local Geometry. In: Proc. CVPR Bd. II, 2000, S. 644–651

[WPS03] Wang, Y., Peterson, B.S., Staib, L.H.: 3D Brain Surface Matching Based on Geodesicsand Local Geometry. In: CVIU 89 (2003), S. 252–271

[Wun97] Wunsch, V.: Differentialgeometrie. Kurven und Flachen. Stuttgart und Leipzig: TeubnerVerlagsgesellschaft, 1997

[XF04] Xie, Z., Farin, G.: Image Registration Using Hierarchical B-Splines. In: IEEE Trans. onVisualization and Computer Graphics 10 (2004), Nr. 1, S. 85–94

[ZSH00] Zockler, M., Stalling, D., Hege, H.-C.: Fast and Intuitive Generation of Geometric ShapeTransitions. In: The Visual Computer 16 (2000), Nr. 5, S. 241–253

26