AT502127A2 - Verfahren zur segmentierung von datenstrukturen - Google Patents

Description

  .. ..
Die Erfindung betrifft ein Verfahren gemäss dem Oberbegriff des Patentanspruches 1.
Bei Datenstrukturen, die unscharf begrenzte Objekte enthalten, spiegeln die Resultate "harter" Segmentierungsmethoden (z.B. Erzeugung von Oberflächenmodellen) eine perfekt definierte Form wider, was nicht der Realität entspricht und den Benutzer in die Irre führen kann. Oftmals ist die Information, wie zuverlässig das Resultat einer bestimmten Segmentierungsmethode an welcher Stelle des Objekts ist, selbst Teil der ursprünglichen Fragestellung und lässt eine bessere Auswertung zu.
Geeignet für das erfmdungsgemässe Segmentierungsverfahren sind beliebigdimensionale Daten (2D Bilder, 3D Volumina nD Datensätze) aus denen mehr oder weniger kompakte Objekte (z. B. ein Tumor in einem medizinischen 3D Bilddatensatz, ein Hurricane aus einem Satellitenbild, od. dgl.) zu segmentieren sind.

   Auch röhrenartige oder verästelte Strukturen (wie z. B. Gefässsysteme in medizinischen 3D Bilddatensätzen) sind unter gewissen Voraussetzungen segmentierbar. Die Vorteile des Verfahrens kommen besonders dann zur Geltung, wenn das zu segmentierende Objekt nur unscharf von seiner Umgebung abgegrenzt ist, das Verfahren funktioniert selbstverständlich auch bei relativ scharf begrenzten Objekten.
In jedem Datenpunkt des n-dimensionalen Datensatzes der zu untersuchenden Datenstruktur wird eine beliebige Anzahl von Merkmalen, insbesondere Messwerten, in Form eines Merkmalsvektors definiert bzw. den jeweiligen Datenpunkten zugeordnet. Die Merkmale enthalten Hinweise über die Zugehörigkeit des Datenpunktes zum zu segmentierenden Objekt und können als Ausgangsdaten für das erfindungsgemässe Verfahren verwendet werden. Die Merkmale können z. B.

   Grauwert(e), Farbwert(e), Textur oder ein beliebiger anderer Messwert sein.
Ein mit geringem Rechenaufwand die tatsächlichen Verhältnisse gut wiedergebendes, rasches Verfahren zur Segmentierung von Objekten aus Datenstrukturen der eingangs genannten Art ist durch die im Kennzeichen des Anspruches 1 angeführten Merkmale charakterisiert.
Fig. 1 und 2 zeigen ein Flussdiagramm betreffend die erfindungsgemässe Vorgangsweise.

   Fig. 3 zeigt Kurven betreffend die Differenz der mittleren Distanzen sowie deren Ableitung und eine Gauss'sche Glockenkurve zentriert an der Stelle des stärksten Anstieges.
Die erfindungsgemässe Vorgangsweise wird im folgenden anhand der in Fig. 1 und 2 dargestellten Flussdiagramme beispielsweise näher erläutert.
Nach dem in Fig. 1 dargestellten Flussdiagramm bildet ein n-dimensionaler Datensatz mit einer beliebigen Anzahl von Merkmalen pro Datenpunkt (Merkmalsvektor) den Ausgangspunkt des Verfahrens (siehe 1). Daraufhin werden ein oder mehrere, insbesondere ein zentraler bzw. zentrale, Punkt(e) des zu segmentierenden Objektes, insbesondere im Gebiet von zusammengehörig bzw. zusammenhängend gewerteten Daten ausgewählt bzw. bestimmt (siehe 2).

   Mit diesen Punkten, die per Definition eine Distanz 0 besitzen, wird sodann ein Distanzfeld erstellt bzw. berechnet, in dem für jeden Punkt des Datensatzes im Sinne bzw. unter Anwendung einer gegebenen Metrik die kürzeste Distanz zu dem(n) ausgewählten Punkt(en) berechnet wird (siehe 6). Um zu diesem Distanzfeld zu gelangen, werden vorteilhafterweise die folgenden Schritte vorgenommen:
Es wird eine Anzahl von Merkmalen aus der Anzahl der jedem Datenpunkt zugeordneten Merkmale ausgewählt, welche für das Objekt als charakteristisch betrachtet werden. Die Anzahl der ausgewählten Merkmale beträgt m>=1. Aus dem n-dimensionalen Datensatz und einer beliebigen Anzahl von Merkmalen wird eine Mannigfaltigkeit konstruiert, welche in einem höherdimensionalen Raum, z. B.

   Riemannschen Raum (Dimension > n) eingebettet wird (siehe 3).
Aus den ausgewählten Merkmalen und den n räumlichen Koordinaten erfolgt durch diese Einbettung in den höher dimensionalen Raum mit der Dimension n+m mittels einer Einbettungsvorschrift die Erstellung der Mannigfaltigkeit.
Sodann wählt man in diesem Einbettungsraum eine Metrik bzw. Messvorschrift, z.B. im einfachsten Fall eine kanonisch euklidische Metrik (siehe 4). Aus dieser Metrik im Einbettungsraum und der Einbettungsvorschrift selbst lässt sich eine induzierte Metrik bzw.

   Messvorschrift auf der Mannigfaltigkeit berechnen, die dann in weiterer Folge dazu dient, Distanzen auf der Mannigfaltigkeit zu berechnen (siehe 5).
Solcherart berechnete Distanzen spiegeln nicht bloss räumliche Distanzen im ursprünglichen n-dimensionalen Datensatz wider, sondern beinhalten auch den Einfluss der Merkmale, die im Zuge der Einbettung verwendet wurden. Werden z.B. 2D Grauwertdaten G(x,y) (Grauwertbild) in einem 3D Riemann-Raum gemäss F= ( x, y, G(x,y) ) eingebettet und die Metrik wie oben beschrieben berechnet, so gibt die Distanz zwischen zwei Punkten in G(x,y) nicht nur an, wie "weit" sie im Bild voneinander entfernt liegen, sondern ist auch umso höher, je stärker sich die Grauwerte auf dem Weg zwischen den zwei Punkten ändern.
Zu Segmentierungszwecken wird diese Vorgangsweise wie im Folgenden beschrieben ausgenutzt.

   Es wird zumindest ein Punkt, vorzugsweise im mittleren Bereich des zu segmentierenden Objektes, im Gebiet von als zusammengehörig bzw. zusammenhängend bewerteten Daten ausgewählt bzw. bestimmt. Es wird somit als einzige Eingabe zumindest ein Punkt, allenfalls bzw. ungefähr in der Mitte des zu segmentierenden Objekts benötigt; ferner werden Merkmale, die das Objekt charakterisieren und zur Einbettung verwendet werden sollen, benötigt, so wie sie in den Merkmalvektoren enthalten sind. Daraufhin wird für alle übrigen Punkte des ndimensionalen Datensatzes die kürzeste Distanz im Sinne der Metrik der Mannigfaltigkeit relativ zu diesem(n) Eingabepunkt(en) berechnet. Damit wird ein n-dimensionales Matrixbzw. Distanzfeld angelegt.

   Datenpunkte, die dem Objekt angehören, erhalten dadurch kleine Distanzwerte, während an den Grenzen des Objekts die Distanz stärker ansteigt, da sich dort die Merkmale der Daten des Datensatzes stärker verändern.
Man leitet somit aus der Mannigfaltigkeit durch Vorgabe zumindest eines Punktes eine Distanzfunktion, basierend auf der Metrik der Mannigfaltigkeit, ab (siehe 6).
Zur Berechnung der Distanzfunktion (siehe 7) aus der Metrik und den Eingabepunkten können unterschiedliche Methoden verwendet werden. Für 2D und 3D Datensätze ist der Einsatz einer "fast sweeping" Methode vorteilhaft und im Hinblick auf die Berechnungsgeschwindigkeit optimiert.

   Ein anwendbares "fast sweeping"-Verfahren ist bekannt aus Tsai YHR, Cheng LT, Osher S, et al.: Fast sweeping algorithms for a dass of Hamilton-Jacobi equations; SIAM JOURNAL ON NUMERICAL ANALYSIS 41(2) : pp673-694 ; 2003.
Im Folgenden werden in dem erhaltenen Distanzfeld beginnend mit der Distanz Null mit vorgegebener Schrittweite [Delta] Isodistanzlinien bzw. Isodistanz-Hyperflächen ermittelt, um basierend auf der generierten Distanzfunktion zu einem Segmentierungsergebnis zu gelangen, das zur Visualisierung geeignet ist (siehe 8). Die vom Benutzer vorgegebenen Eingabepunkte haben per Definition die Distanz Null. Der Wertebereich der Distanzfunktion 0 wird nun in vorgegebene Intervalle (zB [Delta]=1) unterteilt und der Datensatz nach Punkten gleicher Distanz d überprüft. (d=0, [Delta],2[Delta] dmax).
Im Folgenden werden für alle Isodistanzlinien bzw.

   Isodistanz-Hyperflächen für alle Datenpunkte innerhalb der jeweiligen Isodistanzlinie bzw. Isodistanz-Hyperfläche die mittlere Distanz sowie für alle zwischen zwei aufeinanderfolgenden Isodistanzlinien liegende Datenpunkte eine weitere mittlere Distanz und schliesslich die jeweiligen Differenzen zwischen der mittleren Distanz der Datenpunkte innerhalb der jeweiligen Isodistanzlinie und der weiteren mittleren Distanz der Datenpunkte zwischen dieser Isodistanzlinie und der diese unmittelbar umgebenden Isodistanzlinie ermittelt. Die Bestimmung der Differenz [delta](d*) der mittleren Distanz aller Datenpunkte mit d<d* und der mittleren Distanz aller Datenpunkte mit d*<d<(d*+[Delta]) erfolgt iterativ für wachsende Distanzwerte d* (siehe 9).

   Dabei wird bei jedem Schritt d=d* die Differenz der mittleren Distanz aller Datenpunkte mit d<d* und der mittleren Distanz aller Datenpunkte mit d*<d<(d*+[Delta]) berechnet. Dieser Differenzwert [delta], als Funktion der Distanz aufgetragen ([delta](d*)), ergibt eine Kurve A in Fig. 3 mit starkem bzw. stärkstem Anstieg bei Distanzwerten, die im Originaldatensatz die Grenze des Objekts markieren. Detektiert man den Distanzwert, bei dem [delta](d) den ersten starken bzw. stärksten Anstieg aufweist, durch Bildung der Ableitung (Kurve B) und "zentriert" man eine statistische Verteilungsfunktion, z.B. eine Gauss'sche Glockenkurve C, an diesem Wert, kann man den Datenpunkten des Originaldatensatzes "Dichten" [pi](d) gemäss dem Funktionswert der Glockenkurve zuweisen (siehe 10, 11, 12).

   Die Berechnung einer Funktion [pi](d) ordnet jedem Distanzwert d eine Dichte [pi] zu, zum Beispiel in Form einer Gauss'schen Glockenkurve zentriert am Punkt dmax. Die Berechnung einer Darstellung der Datenstruktur kann durch Zuordnung eines Wertes l(v) zu jedem Voxel v entsprechend dem Produkt aus dem Wert der Dichtefunktion seiner Distanz [pi](d(v)) und dem Betrag des Gradienten der Distanzfunktion »V(d(v))» an der Position v erfolgen.
In Fig. 3 sind auf der Abszisse die Distanzen d aufgetragen und auf der Ordinate die entsprechenden Funktionswerte.
Entsprechend dieser Vorgangsweise erhalten Punkte nahe der vermeintlichen Objektgrenze hohe Dichten, während die Dichtewerte benachbarter Punkte innerhalb und ausserhalb des Objekts abfallen.

   Dementsprechend zeigen Isodistanzlinien an den präsumptiven Rändern des Objektes geringeren Abstand als z.B. im Inneren des Objektes, in dem die Merkmale der Datenvektoren der einzelnen Punkte weniger unterschiedlich ausgebildet sind.
Der Betrag des Gradienten der Distanzfunktion ist ein weiterer Indikator für das Vorhandensein einer Objektgrenze, da eine starke Veränderung in den Merkmalen einen starken Anstieg der Distanz und damit einen hohen Gradienten der Distanzfunktion bedingt.

   Führt man daher zusätzlich eine Gewichtung der Dichtewerte mit dem Betrag des Gradienten der Distanzfunktion durch, erhält man eine "Punktwolke" (siehe 14) variabler Dichte, die umso durchsichtiger ist, je schlechter die Objektgrenze an der betreffenden Stelle definiert ist und umso undurchsichtiger und schärfer begrenzt ist, je besser und klarer die Objektgrenze im ursprünglichen Datensatz hervortritt (siehe 13).
Diese Punktwolke repräsentiert das zu segmentierende Objekt und kann einer weiteren Auswertung zugrundegelegt werden.

Claims (5)

Patentansprüche:

1. Verfahren zur Segmentierung von Datenstrukturen n-dimensionaler Datensätze, aus denen Objekte, insbesondere mit diffusen bzw. unbestimmten Objektgrenzen, zu segmentieren sind, wobei jedem Datenpunkt des Datensatzes ein Datenvektor mit einer vorgegebenen Anzahl von Merkmalen, insbesondere Messwerten, zugeordnet ist, die Aussagen bzw. Hinweise über die Zugehörigkeit des Datenpunktes zu dem Objekt enthalten, dadurch gekennzeichnet,

- dass zumindest ein Punkt des Objektes, vorzugsweise im mittleren Bereich des zu segmentierenden Objektes, insbesondere im Gebiet von als zusammengehörig bzw. zusammenhängend bewerteten Daten, ausgewählt bzw. bestimmt wird,

- dass ein Distanzfeld erstellt bzw. berechnet wird, indem für jeden Punkt des Datensatzes im Sinn bzw. unter Anwendung einer vorgegebenen Metrik die kürzeste Distanz zu dem(n) ausgewählten Punkt(en) berechnet wird,

- dass in dem erhaltenen Distanzfeld beginnend mit der Distanz Null mit vorgegebener Schrittweite Isodistanzlinien ermittelt werden,

- dass für alle Isodistanzlinien für alle Datenpunkte innerhalb der jeweiligen Isodistanzlinie die mittlere Distanz sowie für alle zwischen zwei aufeinanderfolgenden Isodistanzlinien liegende Datenpunkte eine weitere mittlere Distanz und schliesslich die jeweiligen Differenzen zwischen der mittleren Distanz der Datenpunkte innerhalb einer isodistanzlinie und der weiteren mittleren Distanz der Datenpunkte zwischen dieser Isodistanzlinie und der diese unmittelbar umgebenden Isodistanzlinie ermittelt werden,

- dass die Funktion betreffend den Zusammenhang zwischen den Differenzwerten und dem jeweiligen Abstand der zugeordneten innenliegenden Isodistanzlinien von dem(n) Punkt(en) der Distanz Null generiert wird,

- dass der maximale Anstieg dieser Funktion ermittelt und an bzw. um diesem Wert eine statistische Verteilungsfunktion, vorzugsweise eine Gauss'sche Glockenkurve, errichtet, insbesondere zentriert, wird und die Distanzen im n-dimensionalen Matrix- bzw. Distanzfeld durch den der jeweiligen Distanz zugeordneten Funktionswert der Verteilungsfunktion ersetzt werden und

- dass dieses Feld bzw. die erhaltene Punktwolke dieser zugeordneten Funktionswerte der Verteilungsfunktion zur Auswertung bzw. Darstellung herangezogen wird.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass in den einzelnen Punkten der erhaltenen Punktwolke eine Gradientenbildung und Ermittlung des ..

Absolutbetrages des Gradienten erfolgt und dieser Absolutbetrag mit dem jeweiligen Funktionswert des Punktes multipliziert wird.

3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet,

- dass zur Erstellung des Distanzfeldes m Merkmale, insbesondere Messwerte, (m>= 1) aus der Anzahl der jedem Datenpunkt zugeordneten Merkmale ausgewählt werden, welche für das Objekt charakteristisch sind,

- dass aus den n-dimensionalen Datensätzen und der ausgewählten Anzahl von Merkmalen der Datenvektoren der Datenpunkte eine Mannigfaltigkeit konstruiert und in einem höherdimensionalen (Dimension m+n) Raum, insbesondere Riemann'schen Raum, eingebettet wird,

- dass für diesen Raum eine Metrik bzw. Messvorschrift, z. B. eine kanonischeuklidische Metrik, vorgegeben wird,

- dass im Einbettungsraum basierend auf dieser Metrik und der vorgegebenen Einbettungsvorschrift eine induzierte Metrik bzw. Messvorschrift auf der Mannigfaltigkeit zur Berechnung von Distanzen auf der Mannigfaltigkeit berechnet bzw. ermittelt wird und

- dass mit der induzierten Metrik für alle Datenpunkte des n-dimensionalen Datensatzes, insbesondere mit einem "fast sweeping"-Verfahren, die jeweils kürzeste Distanz zu diesem(n) ausgewählten Datenpunkt(en) der Datenpunkte, insbesondere zum nächstliegenden derartigen Datenpunkt, berechnet und ein n-dimensionales Matrix- bzw. Distanzfeld angelegt wird,

4. Verfahren nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, dass es zur Segmentierung von Objekten in Datenbildern von bildgebenden medizinischen Verfahren, Gewebeschnitten, Radaraufnahmen, Luftbildaufnahmen (IR, optisch)od. dgl. eingesetzt wird.

5. Computerprogrammprodukt mit Programmcode-Mitteln, die auf einem computerlesbaren Datenträger gespeichert sind, um das Verfahren nach einem der Ansprüche 1 bis 4 durchzuführen, wenn das Programmprodukt auf einem Computer ausgeführt wird.

Wien, am 4. Juli 2005

Advanced - ACV durch: <EMI ID=6.1>