Automatische Segmentierung der Lungenflügel in CT-Daten Matthias Wilms, Jan Ehrhardt, Heinz Handels Institut für Medizinische Informatik, Universität zu Lübeck matthias.wilms@gmail.com Kurzfassung. In diesem Beitrag wird ein automatisches Verfahren zur Lungensegmentierung in CT-Datensätzen vorgestellt. Ausgehend von ei- nem Saatpunkt in der Luftröhre wird unter Verwendung von Volumen- wachstumsverfahren eine Segmentierung der Lunge erzeugt. Da dieses Vorgehen zu einem Zusammenlaufen der beiden Lungenflügelsegmentie- rungen führen kann, wird die Trennung der Lungenflügel mit Hilfe des Dijkstra-Algorithmus vorgenommen. Anschließend werden die Segmen- tierungen durch den Einsatz morphologischer Operatoren geglättet. Eine Evaluation anhand von 100 CT-Datensätzen zeigt die Genauigkeit des Verfahrens und die Robustheit gegenüber verschiedener CT-Protokolle und der Parameterwahl. 1 Einleitung Segmentierungen der Lunge werden in zahlreichen Algorithmen, die auf thora- kalen CT-Daten aufbauen, benötigt, um Arbeitsbereiche sinnvoll beschränken zu können. Deshalb wurden für diesen Anwendungsbereich schon einige automa- tisierte Segmentierungsverfahren vorgeschlagen [1, 2, 3]. Als Methoden nutzen diese Algorithmen hauptsächlich Schwellwert- oder Volumenwachstumsverfahren in Kombination mit morphologischen Operatoren zur Nachbearbeitung der Seg- mentierungen. Diese eher einfachen Methoden lassen sich im Falle der Lunge sehr gut anwenden, da sich diese in den CT-Daten klar von umgebenden Strukturen absetzt. Bei der Verwendung von Schwellwert- oder Volumenwachstumsverfah- ren kommt es allerdings u.U. dazu, dass die beiden Lungenflügelsegmentierungen zusammenlaufen. Dies hängt mit den CT-Werten der Pleura zusammen, welche im angenommenen Wertebereich des Lungengewebes liegen können, was in Re- gionen, in denen die beiden Lungenflügel sehr dicht aneinander liegen, zu einer Verbindung der beiden Segmentierungen führt. Um zwischen linker und rechter Lunge unterscheiden zu können, stellt sich deshalb das Problem der korrekten Trennung. Hierfür werden in der Literatur hauptsächlich einfache, relativ unge- naue Ansätze [1], bei denen gradlinige klare Schnitte zwischen den Segmentie- rungen gezogen werden und exaktere [2, 3], auf dem Prinzip der dynamischen Programmierung aufbauende, Methoden genannt. In diesem Beitrag wird ein automatisches Segmentierungsverfahren für die Lunge auf der Basis von Volumenwachstumsalgorithmen und morphologischen 120 Wilms et al. Operatoren vorgestellt und anhand umfangreicher Testdaten evaluiert. Im Ge- gensatz zu anderen Verfahren wird die Trennung der Lungenflügel mittels des Dijkstra-Algorithmus [4] durchgeführt. Die Evaluation erfolgt anhand von 100 CT-Datensätzen, bei der auch die Robustheit der Parameter betrachtet wird. 2 Material und Methoden Das hier vorgestellte Verfahren arbeitet dreistufig: In einem ersten Schritt wird die Lunge auf der Basis von Volumenwachstumsverfahren segmentiert, wonach in einem zweiten Schritt eine möglicherweise notwendige Trennung der beiden Lungenflügel mittels des Dijkstra-Algorithmus vorgenommen wird. Durch das abschließende morphologische Closing werden die bei der Segmentierung ent- standenen Löcher geschlossen und eine Glättung des Ergebnisses erreicht. 2.1 Segmentierung der Lunge Ausgehend von einem automatisch detektierten Saatpunkt in der Luftröhre, wer- den mit Hilfe von Volumenwachstumsverfahren zwei Segmentierungen erzeugt. Die erste Segmentierung erfasst anhand vorgegebener Schwellwerte (-1000 – -400 Hounsfield Units (HU)) die Lunge inkl. Luftröhre und Bronchialbaum. Mit der zweiten Segmentierung werden durch das explosionsgesteuerte Volumen- wachstumsverfahren aus [5] hauptsächlich Luftröhre und Bronchialbaum seg- mentiert, um diese aus der ersten Segmentierung entfernen zu können. Hierfür wird ein vorgegebener oberer Startwertschwellwert (-900 HU) in großen Schritten erhöht, bis das Volumenverhältnis der Segmentierungen zweier aufeinanderfol- gender Schritte über dem gewählten Explosionsfaktor liegt. In diesem Schwell- wertintervall wird mittels binärer Suche der optimale Schwellwert gesucht, der die Grenze der Ausbreitung der Luftröhrensegmentierung in die Lunge markiert. Die resultierende Segmentierung wird auf das Vorhandensein von exakt zwei zusammenhängenden Komponenten, den beiden Lungenflügeln, überprüft. Sollte nur ein Objekt gefunden werden, erfolgt eine Trennung der Lungenflügel. 2.2 Trennung der Lungenflügel Ziel ist es die Verbindungslinie zwischen den beiden Lungenflügelsegmentierun- gen zu finden, um sie aus der Segmentierung zu entfernen. Hierbei hilft der Um- stand, dass die Werte der Pleura in den CT-Daten größer als die des umliegenden Lungengewebes sind, sodass sich die Verbindungslinie lokal als maximaler Ko- stenpfad der negativen CT-Werte (in HU) der betreffenden Voxel darstellt. Die- ser Pfad wird mit Hilfe des Dijkstra-Algorithmus auf allen axialen Schichten, auf denen die Lungenflügel zusammenhängen, ermittelt. Der Dijkstra-Algorithmus bietet im Vergleich zu Algorithmen mit linearer Zeitkomplexität den Vorteil, dass er keine topologische Sortierung des Graphen benötigt. Um den Algorith- mus nutzen zu können, muss das duale Problem des minimalen Kostenpfades mit inversen (und positiven) Kantengewichten betrachtet werden. Hierzu werden die Segmentierung in CT-Daten 121 Voxel als Knoten in einem nicht gerichteten Graphen eingesetzt. Als jeweiliges Kantengewicht wird der invertierte Mittelwert der beiden beteiligten Voxel ge- wählt. Um positive Gewichte zu gewährleisten, werden negative Kantengewichte durch den Wert einer positiven Konstante ersetzt. Die Suchregion wird durch ein minimal umgebendes Rechteck der Segmentierung automatisch bestimmt. Start- und Endpunkt des Pfades werden dabei mittig am hinteren und vorde- ren Teil der Lunge außerhalb des Rechtecks festgelegt, um vordere und hintere Verbindungen der Lungenflügel extrahieren zu können. 2.3 Evaluation Die Evaluation des Verfahrens erfolgt anhand von 100 anonymisierten CT-Daten- sätzen, für die eine manuelle Lungensegmentierung zur Verfügung steht, welche von einem medizinischen Experten erstellt wurde. 94 dieser Datensätze entstam- men Low-Dose-4D-CT-Aufnahmen von insgesamt 12 Patienten, aufgenommen bei freier Atmung, wohingegen es sich bei den restlichen Daten um 6 Ultra-Low- Dose-CT-Datensätze von 6 Patienten bei angehaltener Atmung handelt. In den Datensätzen sind sowohl gesunde als auch mit Tumoren und Emphysemen behaf- tete Lungen enthalten. Die Datensätze haben eine Größe von 512 × 512 × 270- 467 Voxel, bei einer Voxelgröße von 0.68 × 0.68 × 0.7 mm bis 0.97 × 0.97 × 1.5 mm. Die Werte der Parameter sind für alle Datensätze einheitlich und experi- mentell festgelegt worden. Die manuellen Segmentierungen dienen in der Evaluation als Goldstandard, mit dem die durch das vorgestellte Verfahren automatisch generierten Ergebnisse verglichen werden. Als Maße werden hierfür der Jaccard-Koeffizient, die mitt- lere Distanz zwischen den segmentierten Lungenoberflächen und die Hausdorff- Distanz herangezogen. Da es in der Mediastinalregion, bedingt durch die Gefäße, verschiedene Möglichkeiten zur Segmentierung gibt, wird die Auswertung jeweils mit und ohne Mediastinalregion angegeben. 3 Ergebnisse Tabelle 1 stellt die Ergebnisse der Evaluation dar. Bei 8 Low-Dose-Datensätzen ist die Segmentierung mit den einheitlichen Parametern nicht oder nur teilweise gelungen, weil entweder die Luftröhre nicht gefunden wurde oder der Explosions- faktor des explosionsgesteuerten Volumenwachstumsalgorithmus falsch gewählt war. Eine Segmentierung dieser Datensätze ist aber durch die individuelle Wahl des Explosionsfaktors und der zulässigen numerischen Exzentrizität für den Luft- röhrenquerschnitt möglich. Die aus diesen Ergebnissen folgende Robustheit der Parameter, wird für den, neben dem Explosionsfaktor entscheidenden, oberen Lungenschwellwert in Abb. 1 (a) exemplarisch dargestellt. Die Betrachtung der mittleren Hausdorff-Distanz zeigt, dass sich in der Me- diastinalregion im Mittel die größten Unterschiede zwischen Segmentierung und Goldstandard ergeben (Abb. 1 (b)). Bei den Mittelwerten des Jaccard-Koeffi- zienten und der mittleren Oberflächendistanz liefern beide Versuchsanordnungen 122 Wilms et al. Tabelle 1. Vergleich der automatisch generierten Segmentierungen S mit dem Goldstandard G, jeweils mit und ohne Mediastinalregion. Vergleichsmaße: Jaccard- Koeffizient J(S, G); mittlere Oberflächendistanz d(S, G); Hausdorff-Distanz H(S, G). Basis Low-Dose-CT: 94 Datensätze; Ultra-Low-Dose-CT: 6 Datensätze. Low-Dose-CT-Daten Ultra-Low-Dose-CT-Daten Maß Mittelwert Std.-Abw. Mittelwert Std.-Abw. mit J(S, G) 0.9456 0.0107 0.9743 0.0030 d(S, G) [mm] 0.7349 0.2417 0.4665 0.0228 H(S, G) [mm] 25.8826 7.5902 17.6588 6.6228 ohne J(S, G) 0.9416 0.0137 0.9724 0.0077 d(S, G) [mm] 0.7180 0.2502 0.4509 0.0634 H(S, G) [mm] 10.4486 4.3380 5.0541 1.8597 sehr ähnliche Werte. Die Trennung der Lungenflügel konnte bei allen Datensät- zen erfolgreich vorgenommen werden (Abb. 2). Die durchschnittliche Rechenzeit für Datensätze mit notwendiger Lungenflügeltrennung beträgt ca. 10 min, ge- messen auf einem Intel Xeon W3520 Rechner mit 2.67GHz und 24GB RAM. Die Trennung der Lungenflügel benötigt hierbei durchschnittlich 50 % der Re- chenzeit, wobei die Anwendung des Dijkstra-Algorithmus ca. 0.5 s pro Schicht in Anspruch nimmt. Datensätze ohne notwendige Lungenflügeltrennung können in durchschnittlich ca. 5 min segmentiert werden. 4 Diskussion In diesem Beitrag wurde ein dreistufiges automatisches Verfahren zur Lungen- flügelsegmentierung in CT-Datensätzen vorgestellt und umfangreich evaluiert. Die Evaluation zeigt die Robustheit des Verfahrens gegenüber verschiedenen Abb. 1. Ausgewählte Ergebnisse. Links: Beispiel zum Einfluss des oberen Lungen- schwellwerts auf das Segmentierungsergebnis anhand eines Testdatensatzes. Markie- rung: Evaluationsschwellwert −400 HU. Rechts: Oberflächenmodell eines automatisch segmentierten Lungenflügels. Die Färbung entspricht der Oberflächendistanz d(S, G). Segmentierung in CT-Daten 123 Abb. 2. Beispiel zur Trennung der Lungenflügel. (a): Axiale Schicht eines CT- Datensatzes inkl. einer markierten Beispielregion. (b): Zusammenhängende Aus- gangssegmentierung der Beispielregion (ohne Closing). (c): Anwendung des Dijkstra- Algorithmus auf die Beispielregion. (d): Ergebnissegmentierung der Beispielregion (mit Closing). (a) (b) (c) (d) Eingabedaten (mehrere Patienten; Low-Dose u. Ultra-Low-Dose) und der Pa- rameterwahl. Von den 100 Testdatensätzen konnten lediglich 8 nicht mit den einheitlich gewählten Parametern segmentiert werden. Die ermittelten Mittel- werte für den Jaccard-Koeffizienten und die mittlere Oberflächendistanz zeigen die hohe Übereinstimmung mit den als Goldstandard genutzten manuellen Seg- mentierungen. Die Mittelwerte für den Jaccard-Koeffizienten und die Hausdorff- Distanz (mit Mediastinalregion) stimmen weitestgehend mit den Ergebnissen aus [2] überein, wohingegen die Werte für die mittlere Oberflächendistanz etwas niedriger als die dortigen Vergleichswerte sind und auch unter den dort publi- zierten Interobserver-Variabilitäten liegen. Die Nutzung der manuellen Segmen- tierungen ergibt allerdings Probleme, die bei der Interpretation der Ergebnisse beachtet werden müssen: Teilweise gibt es mehrere Möglichkeiten zur Segmen- tierung (z.B. Mediastinalregion) und für die hier genutzten manuellen Segmen- tierungen liegen keine durch einen zweiten Experten erstellten Vergleichsdaten vor. Literaturverzeichnis 1. Messay T, Hardie RC, Rogers SK. A new computationally efficient CAD system for pulmonary nodule detection in CT imagery. Med Image Anal. 2010;14(3):390 – 406. 2. van Rikxoort E, de Hoop B, Viergever M, et al. Automatic lung segmentation from thoracic computed tomography scans using a hybrid approach with error detection. Med Phys. 2009;36(7):2934–47. 3. Hu S, Hoffman EA, Reinhardt JM. Automatic lung segmentation for accurate quan- titation of volumetric x-ray CT images. IEEE Trans Med Imaging. 2001;20(6):490–8. 4. Dijkstra EW. A note on two problems in connexion with graphs. Numer Math. 1959;1:269–71. 5. Mori K, Hasegawa J, Toriwaki J, et al. Recognition of bronchus in three-dimensional x-ray CT images with application to virtualized bronchoscopy system. Proc IEEE ICPR. 1996;3:528–32.