AT502127B1 - Verfahren zur segmentierung von datenstrukturen - Google Patents

Description

2 AT 502 127 B1

Die Erfindung betrifft ein Verfahren gemäß dem Oberbegriff des Patentanspruches 1.

Verfahren zur Segmentierung sind aus der DE 199 28 231 A1, der US 2005/0008205 A1, der DE 102, 49 320 A1 und der US 6,785,409 B1 bekannt

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.

Aufgabe der Erfindung ist die Erstellung eines Verfahrens zur Segmentierung von Datenstrukturen, das der Realität entsprechende Ergebnisse erreichen lässt, auch wenn relativ unscharf begrenzte Objekte segmentiert werden.

Geeignet für das erfindungsgemäße Segmentierungsverfahren sind beliebig-dimensionale 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äßsysteme 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äße 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äße Vorgangsweise. Fig. 3 zeigt Kurven betreffend die Differenz der mittleren Distanzen sowie deren Ableitung und eine Gauß'sche Glockenkurve zentriert an der Stelle des stärksten Anstieges.

Die erfindungsgemäße 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 Merk- 3 AT 502 127 B1 male 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öherdimen-sionalen 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 bloß 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äß 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 n-dimensionalen Datensatzes die kürzeste Distanz im Sinne der Metrik der Mannigfaltigkeit relativ zu diesem(n) Eingabepunkt(en) berechnet. Damit wird ein n-dimensionales Matrix- bzw. 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, wie insbesondere aus Fig. 2 ersichtlich, in dem erhaltenen Distanzfeld beginnend mit der Distanz Null mit vorgegebener Schrittweite Δ 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 Δ=1) unterteilt und der Datensatz nach Punkten gleicher Distanz d überprüft. (d=0, A,2A,...,dmax).

Im Folgenden werden für alle Isodistanzlinien bzw. Isodistanz-Hyperflächen für alle Datenpunk-

Claims (14)

1. 4 AT 502 127 B1 te 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 schließlich 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 5(d*) der mittleren Distanz aller Datenpunkte mit d<d* und der mittleren Distanz aller Datenpunkte mit d*<d<(d*+A) erfolgt iterativ für wachsende Distanzwelle 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*+A) berechnet. Dieser Differenzwert δ, als Funktion der Distanz aufgetragen (5(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 5(d) den ersten starken bzw. stärksten Anstieg aufweist, durch Bildung der Ableitung (Kurve B) und „zentriert“ man eine statistische Verteilungsfunktion, z.B. eine Gauß'sche Glockenkurve C, an diesem Wert, kann man den Datenpunkten des Originaldatensatzes „Dichten“ n(d) gemäß dem Funktionswert der Glockenkurve zuweisen (siehe 10, 11, 12). Die Berechnung einer Funktion n(d) ordnet jedem Distanzwert d eine Dichte Π 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 n(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 außerhalb 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. Patentansprüche: 1. Verfahren zur Segmentierung von Datenstrukturen n-dimensionaler Datensätze, aus denen Objekte zu segmentieren sind, wobei jedem Datenpunkt des Datensatzes ein Datenvektor mit einer vorgegebenen Anzahl von für das Objekt als charakteristisch betrachteten Merkmalen zugeordnet ist, die Aussagen und/oder Hinweise über die Zugehörigkeit des Datenpunktes zu dem Objekt enthalten, dadurch gekennzeichnet, - dass zumindest ein Punkt des Objektes ausgewählt oder bestimmt wird, - dass ein Distanzfeld erstellt und/oder berechnet wird, indem für jeden Punkt des Datensatzes unter Anwendung einer vorgegebenen Metrik die kürzeste Distanz zu dem(n) ausgewählten Punkt(en) berechnet wird, 5 AT 502 127 B1 - 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 schließlich 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 um diesem Wert eine statistische Verteilungsfunktion errichtet, insbesondere zentriert, wird und die Distanzen im n-dimensionalen Matrix- oder Distanzfeld durch den der jeweiligen Distanz zugeordneten Funktionswert der Verteilungsfunktion ersetzt werden und - dass dieses Feld oder die erhaltene Punktwolke dieser zugeordneten Funktionswerte der Verteilungsfunktion zur Auswertung und/oder Darstellung herangezogen wird.
2. 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. 3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, - dass zur Erstellung des Distanzfeldes m Merkmale (m£l) 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 oder Messvorschrift vorgegeben wird, - dass im Einbettungsraum basierend auf dieser Metrik und der vorgegebenen Einbettungsvorschrift eine induzierte Metrik oder Messvorschrift auf der Mannigfaltigkeit zur Berechnung von Distanzen auf der Mannigfaltigkeit berechnet oder ermittelt wird und - dass mit der induzierten Metrik für alle Datenpunkte des n-dimensionalen Datensatzes die jeweils kürzeste Distanz zu diesem(n) ausgewählten Datenpunkt(en) der Datenpunkte berechnet und ein n-dimensionales Matrix- oder Distanzfeld angelegt wird.
4. 4. Verfahren nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, dass die Objekte diffuse oder unbestimmte Objektgrenzen besitzen.
5. 5. Verfahren nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, dass die dem Datenvektor zugeordneten Merkmale Messwerte sind.
6. 6. Verfahren nach einem der Ansprüche 1 bis 5, dadurch gekennzeichnet, dass der ausgewählte oder bestimmte zumindest eine Punkt des Objektes im mittleren Bereich des zu segmentierenden Objektes, insbesondere im Gebiet von als zusammengehörig oder zusammenhängend bewerteten Daten ausgewählt oder bestimmt wird.
7. 7. Verfahren nach einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, dass die statistische Verteilungsfunktion eine Gauß'sche Glockenkurve ist.
8. 8. Verfahren nach einem der Ansprüche 3 bis 7, dadurch gekennzeichnet, dass die zur Erstellung des Distanzfeldes ausgewählten Merkmale Messwerte sind. 6 AT 502 127 B1
9. 9. Verfahren nach einem der Ansprüche 3 bis 8, dadurch gekennzeichnet, dass der höherdi-mensionale Raum ein Riemann'scher Raum ist.
10. 10. Verfahren nach einem der Ansprüche 3 bis 10, dadurch gekennzeichnet, dass als Metrik oder Messvorschrift eine konisch-euklidische Metrik vorgegeben wird.
11. 11. Verfahren nach einem der Ansprüche 3 bis 10, dadurch gekennzeichnet, dass die jeweils kürzeste Distanz mit einem "fast sweeping"-Verfahren berechnet wird.
12. 12. Verfahren nach einem der Ansprüche 3 bis 11, dadurch gekennzeichnet, dass die kürzeste Distanz zum nächstliegenden ausgewählten Datenpunkt einberechnet wird.
13. 13. Verfahren nach einem der Ansprüche 1 bis 12, dadurch gekennzeichnet, dass es zur Segmentierung von Objekten in Datenbildern von bildgebenden medizinischen Verfahren, Gewebeschnitten, Radaraufnahmen, Luftbildaufnahmen (IR, optisch) eingesetzt wird.
14. 14. Computerprogrammprodukt mit Programmcode-Mitteln, die auf einem computerlesbaren Datenträger gespeichert sind, um das Verfahren nach einem der Ansprüche 1 bis 13 durchzuführen, wenn das Programmprodukt auf einem Computer ausgeführt wird. Hiezu 3 Blatt Zeichnungen