Ein fortschrittlicher Ansatz zum Erkennen von Grenzen am Beispiel von Schiffswänden

Interessante Informationen

Die folgende Abbildung zeigt eine dreidimensionale Rekonstruktion des Herzens, die als Ergebnis der Arbeit eines modernen Tomographen erhalten wurde:


Für die Skalierung beträgt die Dicke des Aortenkolbens 3,2 cm, denken Sie nur! Wenn Menschen jedoch Herzprobleme aufgrund von Blutgefäßen haben, sprechen wir in der Regel nicht über so große. Das Bild zeigt, dass das Herz von kleineren Gefäßen umgeben ist und einige von ihnen direkt von den großen Arterien abzweigen. Dies sind die sogenannten Koronararterien, die das Herz direkt mit Blut versorgen. Wenn bei ihnen beispielsweise aufgrund der Bildung von Kalzium eine Verengung des Lumens (Stenose) auftritt, nimmt der Blutfluss ab. Wenn eine Stenose ausgeprägt ist, tritt eine Gewebenekrose auf, dh ein Herzinfarkt. Als nächstes werde ich über unseren Ansatz zur Berechnung der Grenzen von Blutgefäßen sprechen, der es Ihnen ermöglicht, die Verengung automatisch zu finden und ihnen eine Schätzung zu geben.

Um das Material zu verstehen, müssen Sie das Volumen, die Voxel und ihre Intensitäten oberflächlich verstehen. Sie können dies herausfinden, indem Sie den Anfang dieses Artikels lesen.

Um die Verengung eines Gefäßes beurteilen zu können, müssen wir das Lumen des Gefäßes oder seine innere Grenze kennen. Erkennen Sie dazu mindestens das gesamte Kalzium. Wir finden auch die äußere Grenze, weil es möglich ist, die Wandstärke abzuschätzen, was ebenfalls nützlich ist. Schauen wir uns zunächst das vollständige Grenzerkennungsschema an und analysieren dann jede Phase im Detail:

Zeichnen der Mittellinie

Die schwierigste Phase in Bezug auf die Implementierung (zumindest hat es die meiste Zeit gedauert). Die Methode basiert auf der Verwendung einer hessischen Matrix (Multi-Scale Vessel Segmentation Using Hessian Matrix Enhancement). Weitere Details im bereits erwähnten Artikel .

Schneiden

Wir haben nur eine Mittellinie und brauchen räumlich abhängige Intensitäten von Voxeln, mit denen bequem gearbeitet werden kann. Um sie zu bekommen, geht ein „Stapel“ Scheiben. Für den Anfang werden Punkte über feste Abstände auf der Mittellinie gesetzt. Dann wird aus jedem Punkt eine Senkrechte konstruiert . Nach ist die zweite Senkrechte . Wo - die Richtung der Mittellinie an einem Punkt. Beide Senkrechten sind normalisiert. Zu jedem Zeitpunkt Mittellinienvektor bilden ein 2d Koordinatensystem. So werden Scheiben gebildet:


Die Voxelposition ist definiert als wo hier Sind die reellen Koordinaten des Voxels, ist k die Schichtnummer. Inverse Formel für reelle Koordinaten: . Wenn Sie zu einem neuen Koordinatensystem wechseln, wird der durch die Schichten gebildete Raum vereinfacht:


Was wir brauchen!

Bau der Außengrenze des Schiffes

Schauen wir uns das Diagramm an:


Wir schneiden unseren Stapel von Scheiben, die wir in der vorherigen Phase erhalten haben, in acht Ebenen (ähnlich wie beim Schneiden eines Kuchens) und führen alle Berechnungen im Raum von Ebenen durch:


Wenn Sie die normalisierten Werte der Intensitäten der Voxel anzeigen, die auf die Schnittebene treffen, erhalten Sie das folgende Bild:


Um die Grenzen des Gefäßes zu erkennen, wird der klassische Ansatz (Kantenerkennung durch Gradienten) in Verbindung mit der Suche nach dem Pfad verwendet. Schema:


1. Wenden Sie die Gaußsche Glättung mit einem kleinen Wert an Lärm unterdrücken:
Für einen Punkt mit Koordinaten ::
wo Gibt den Intensitätswert an einem Punkt zurück ;; r nimmt normalerweise den Wert an ( - Aufrunden); - Glättungskoeffizient.

2. An jedem Punkt finden wir den Gradienten und seinen Wert, die Berechnungen werden mit geglätteten Intensitätswerten durchgeführt:
,
wo - private Derivate. Sie werden nach der Finite-Differenzen-Methode gefunden:

,
wo - Intensität an einem Punkt nach dem Glätten.
Als nächstes brauchen wir die Richtung des Gradienten ( Ist die Normalisierung des Vektors) und der Wert des Gradienten ( Ist die Länge des Vektors)

3. Die Richtung des Gradienten wird in Grad oder Bogenmaß umgerechnet:
(atan2 () ist die Funktion der Bogen-Tangente in C ++, nicht zu verwechseln mit atan ()). Dann runden wir den Winkel so, dass er 4 Werte in Schritten von 45 Grad haben kann, d. h. oben und unten werden in die gleiche Richtung betrachtet:

4. Führen Sie die Unterdrückung von Nichtmaxima durch. Ist der Gradientenwert Wenn mindestens einer von zwei benachbarten Punkten (entsprechend der Richtung des Gradienten) größer oder gleich dem Gradientenwert am aktuellen Punkt ist, kann ein solcher Punkt nicht zur Grenze gehören:


5. Alle verbleibenden Voxel gelten als Grenzen. Basierend auf dem Wert des Gradienten, der Kalziumschwelle (die nicht sofort verfügbar ist) und der Nähe zum „vertikalen“ Zentrum werden jedem Punkt bestimmte Kosten zugewiesen (je heller das Voxel, desto höher ist seine Priorität bei der Suche nach einem Pfad):

In dieser Form sind die Grenzen des Gefäßes fast eindeutig definiert.

6, 7. Um Grenzen zu bilden, verwenden wir die Suche nach dem Pfad. Die nächstgelegenen Extrempunkte mit den geringsten Kosten werden als Anfangs- und Endpunkt genommen. Verwenden Sie zum Suchen nach einem Pfad eine einfache Breitensuche, bei der die Grenzpunkte mit den geringsten Kosten ausgewählt werden. Sprünge sind ebenfalls verfügbar, aber ihr Preis ist hoch. Die oberen und unteren Grenzen des Gefäßes werden getrennt durchsucht und anschließend geglättet:


Diese Prozedur wird für jede Ebene durchgeführt, was zu Ringen mit 16 Segmenten für jede Scheibe im Stapel führt. Diese Ringe bilden die äußeren Ränder des Gefäßes.

Wie Sie auf dem Bild sehen können, gibt es Bereiche, in denen die Ränder falsch erkannt werden. Dies ist auf das Vorhandensein von Kalzium zurückzuführen, das zum Nachweis von Kalziumgrenzen und nicht von Gefäßgrenzen führt. Um dies nach dem ersten Erkennen von Grenzen zu verhindern, muss die Kalziumschwelle bestimmt werden (dazu später mehr) und anschließend die zweite Erkennung von Grenzen durchgeführt werden, wobei die mit Kalzium verbundenen Voxel ignoriert werden. Dann bekommen wir:

Schwellenwerterkennung

Betrachten Sie nun die Maximierung der Clustering-Algorithmus-Erwartung (im Folgenden als EM bezeichnet). Beginnen wir mit der Normalverteilungsfunktion: Sie zeichnet sich durch eine mathematische Erwartung aus und Standardabweichung . So wirken sie sich auf die Art der Verteilung aus:



Angenommen, wir haben Daten (Punkte), die aus einer „gelben“ Quelle und aus einer „blauen“ Quelle stammen:


Dann finden wir unter Verwendung von Standardformeln leicht den Mittelwert und die Standardabweichung für jede Quelle. Formeln für Quelle "a":




Was aber, wenn wir die Anzahl der Quellen kennen, aber nicht wissen, welche Punkte zu welcher Quelle gehören? Was ist, wenn wir so ein Bild haben?


Wenn jemand kam und uns die Verteilungsparameter mitteilte, konnten wir leicht die Wahrscheinlichkeit berechnen, dass jeder Punkt zu jeder der Quellen gehört. Die Wahrscheinlichkeit, dass der Punkt zur Quelle „a“ gehört:

wo




Und wenn wir die Quellparameter berechnen müssen, kennen wir die Wahrscheinlichkeiten:



So entsteht ein Teufelskreis: Wenn wir die Parameter der Quellen kennen würden, würden wir berechnen, welcher Punkt zu welcher Quelle gehört, aber wir kennen die Parameter nicht. Und wenn wir wüssten, welcher Punkt zu welcher Quelle gehört, würden wir ihre Parameter berechnen, aber wir wissen nicht, welcher Punkt zu welcher Quelle gehört. Das Abwägen zwischen diesen Tatsachen ist genau das, was der EM-Algorithmus tut.

Beim Start erhält EM einige vordefinierte Parameter für Quellen, die einfach zufällig ausgewählt werden können. Wenn die Parameter bekannt sind, können wir natürlich die Wahrscheinlichkeit berechnen, dass jeder Punkt zu jeder der Quellen gehört. Nachdem die Wahrscheinlichkeiten bekannt sind, können wir neue genauere Parameter berechnen. Dann geht es wieder von vorne los, aber mit neuen Parametern. Nach jedem Zyklus werden die Parameter der Quellen genauer.

Wie können wir dieses Wissen in Bezug auf Schiffe nutzen? Werfen wir einen Blick auf die Struktur eines von ihnen:

In Diagrammen wird dieser Punkt normalerweise weggelassen, es können jedoch auch Fett- und Kalziumbildungen im Gefäß vorhanden sein. Somit gehört jedes Voxel zu einem der Gewebe. Nach den Experimenten stellte sich heraus, dass es ausreicht, folgende Unterteilungen vorzunehmen:

- Fett
- Wand Nr. 1
- Wand Nr. 2
- Kontrastmittel
- Kalzium

Die Verteilung der Voxelintensitäten ist jeweils normal. Das heißt, Wir haben alles, was wir brauchen, um mit EM die Parameter jeder Quelle zu finden.


Nachdem wir die Parameter jeder Quelle kennen, können wir die Schwellenwerte berechnen - die Werte der Intensitäten, an deren Schnittpunkt sich die Voxelmitgliedschaft von einer Quelle zur anderen ändert. Wir interessieren uns für:

1. Die Schwelle der Außengrenze des Schiffes. Wenn die Voxelintensität unter diesem Wert liegt, wird angenommen, dass sie überhaupt nicht zum Gefäß gehört;

2. Die Schwelle der inneren Grenze des Schiffes. Wenn die Voxelintensität größer als dieser Wert ist, dann ist es
bezieht sich auf das Lumen des Gefäßes, d.h. zu einer Mischung aus Blut und Kontrastmittel;

3. Die Schwelle von Kalzium. Wenn der Wert der Voxelintensität größer als dieser Wert ist, bezieht er sich auf Calcium.

Konstruktion der inneren Grenze des Schiffes

Beginnen wir wie immer mit dem Diagramm: Für jedes Slice werden Berechnungen durchgeführt.



Wenn Sie die Daten gemäß den im vorherigen Schritt ermittelten Schwellenwerten visuell anzeigen, erhalten Sie das folgende Bild:



Rote Farbe ist die Wand des Gefäßes. Grüne Farbe - Abstand. Weiß ist Kalzium.

Das erste, was auffällt, ist das „hängende“ Kalzium, das an keine der Wände angrenzt. Dies wird als normal angesehen und ergibt sich aus der vom Tomographen selbst angewendeten Glättung.

Zuerst müssen Sie die Grenzen gemäß den Schwellenwerten ermitteln, und hierfür wird der Algorithmus für Marschquadrate verwendet. Es kann gesagt werden, geht in zwei Stufen. Zunächst wird die Fläche durch ein diskretes Gitter geteilt, und die Quadrate, in denen die Intensitätswerte größer oder gleich dem Schwellenwert sind, werden als "positiv" betrachtet, der Rest als "negativ".

Jedes Mal befinden wir uns in einer Art Knoten und müssen eine Kontur um die „positiven“ Quadrate zeichnen. Um eine Entscheidung zu treffen, betrachten wir die Vorzeichen von vier benachbarten Quadraten: oben links, unten links, oben rechts, unten rechts. Ohne Symmetrie interessieren uns drei Fälle.

1. Drei Quadrate mit einem Zeichen und einem gegenüberliegenden, die Bewegung der Kontur erfolgt diagonal:


2. Zwei Quadrate mit demselben Vorzeichen und zwei gegenüberliegenden und die Quadrate mit demselben Vorzeichen befinden sich auf einer Seite. Die Bewegung der Kontur ist vertikal oder horizontal:


3. Zwei Quadrate mit demselben Zeichen und zwei gegenüberliegende Quadrate mit demselben Zeichen werden auf gegenüberliegenden Seiten platziert:


Dies ist ein Ausnahmefall. Um eine Entscheidung zu treffen, wird der Durchschnittswert der Intensität in allen vier Quadraten ermittelt. Wenn er größer oder gleich dem Schwellenwert ist, ist das Zentrum positiv, in anderen Fällen negativ. Es ist auch wichtig, welcher Knoten gerade aktuell ist:


Der Marschquadrat-Algorithmus konstruiert genau und eindeutig eine Kontur. Im folgenden Beispiel habe ich die Linie absichtlich von der Mitte der Seite verschoben, sodass jeder Schritt deutlich sichtbar war.


Für jeden Abschnitt des Schiffes finden wir zwei Hauptkonturen - dies ist die Kontur des äußeren Randes und die Kontur des inneren Randes. Wir „schneiden“ sofort die Außenkontur mit unserer anderen Außenkontur, die wir am Anfang des Artikels gefunden haben, indem wir nach Pfaden gesucht haben. Dies geschieht, um die Zweige des Schiffes zu ignorieren. Wir ignorieren die Konturen von Kalzium, die zu weit von der Innenwand entfernt sind, als ob sie überhaupt nicht existieren. Wir finden den Rest und verwenden sie in Zukunft. Wenn sich das Zentrum des Gefäßes innerhalb des Kalziums befindet, verschieben wir es in die Richtung, die dem Kalziumkreislauf am nächsten liegt, bis sich das Zentrum im Lumen befindet (im grünen Bereich). Solch ein aktualisiertes Zentrum werde ich die Startposition nennen.

Nach dem Schema kann es zwei Fälle geben: einfache und komplexe.


Befindet sich die Startposition innerhalb einer geschlossenen Kalziumschleife (z. B. wenn ein Stent installiert ist), setzen wir den inneren Rand sofort dieser Schleife gleich. Die Dinge sind komplizierter, wenn sich das Zentrum außerhalb von Kalzium befindet. In diesem Fall müssen wir den Startkreis erweitern, damit er reibungslos um Kalzium und die innere Grenze fließt:


Um das gewünschte Ergebnis zu erzielen, wurde ein spezieller Algorithmus entwickelt, der auf Ideen basiert, die in physikalischen 2D-Engines verwendet werden, insbesondere auf der Lösung von Polygonkollisionen und dem Satz über separate Achsen.

Zwei grundlegende Konzepte, auf die nicht verzichtet werden kann: Für sich überschneidende konvexe Polygone ist der MTV-Vektor (minimaler Translationsvektor) die kleinste Verschiebung eines der Polygone, nach der der Schnittpunkt stoppt.

Wir brauchen auch die Polygonnormalen - in 2D stehen sie senkrecht zu den Flächen und zeigen "out" an:

Um den Artikel nicht lang zu machen, werde ich den Rest der Details zu physischen Motoren weglassen. Das einzige, was ich bemerke, ist, dass während jeder Iteration jeder Punkt in der Kontur den Einfluss von Kräften auf sich selbst in Form eines Vektors akkumuliert und sich am Ende jeder Iteration um die Länge dieses Vektors in seine Richtung verschiebt. Betrachten Sie die Kräfte:

1. Auf jeden Scheitelpunkt der Startkontur wirken zwei Kräfte in Richtung benachbarter Scheitelpunkte, und die Kräfte sind direkt proportional zum Abstand zu diesen Scheitelpunkten. Dadurch schrumpft der Umriss und versucht, eine abgerundete Form beizubehalten.

2. Wenn der Scheitelpunkt der Seitenkontur in die Startkontur fällt, wird der Versatz proportional zum Scheitelpunkt-MTV-Vektor des Scheitelpunkts auf die nächste Fläche der Startkontur angewendet.

3. Befindet sich die Oberseite der Startkontur innerhalb der Seitenkontur, wird ein Versatz proportional zum Scheitelpunkt-MTV-Vektor des Scheitelpunkts auf die Oberseite der Startkontur angewendet. Zusammen mit dem vorherigen Absatz erlaubt dies nicht, dass die Schaltung die Grenzen anderer Schaltungen überschreitet;

4. Wenn die Fälle 2 und 3 für den Scheitelpunkt nicht funktionierten, wird eine Kraft in der gemittelten Richtung der beiden Normalen benachbarter Flächen auf ihn ausgeübt. Dies stellt das Wachstum der Kontur "in der Breite" sicher.

Wichtig: Sie können einen Scheitelpunkt oder eine Fläche nicht vollständig um die Länge des MTV-Vektors verschieben - er wird mit einem bestimmten Koeffizienten im Bereich von 0,2 bis 0,8 multipliziert. Die Koeffizienten für jede Kraft in den übrigen Fällen werden experimentell ausgewählt.

Dank dieses Ansatzes finden wir das Lumen des Gefäßes unter Berücksichtigung der Tatsache, dass Kalzium nicht in der Nähe der Wände angrenzt. Kombinieren Sie nun einfach die Ergebnisse aus allen Abschnitten und erhalten Sie die inneren und äußeren Ränder des Schiffes:


Die offensichtliche Ungenauigkeit der Grenze nach dem Stent wird durch eine anomale Gabelung verursacht:


Der Bereich des inneren Randes am Schnitt kennzeichnet genau den Abstand, an dem wir letztendlich interessiert sind. Die weitere Verwendung dieser Daten halte ich für trivial und bedarf keiner Berücksichtigung. Zum Schluss lasse ich das Bild des exportierten inneren Randes in 3D: