Segmentierung (Bildverarbeitung)

Grundidee und Einordnung

Segmentierung ist ein Teilgebiet der digitalen Bildverarbeitung und des Computer-Sehens. Dabei werden benachbarte Pixel oder Voxel nach einem Homogenitätskriterium zu inhaltlich zusammenhängenden Regionen zusammengefasst. Jedem Bildpunkt wird dadurch ein Segment beziehungsweise eine Klasse (Label) zugeordnet.

Im maschinellen Sehen ist die Segmentierung üblicherweise der erste Schritt der Bildanalyse nach der Bildvorverarbeitung. Der typische Ablauf lautet: Szene → Bildaufnahme → Bildvorverarbeitung → Segmentierung → Merkmalsextraktion → Klassifizierung → Aussage.

Segmentierungen können automatisch, manuell oder semi-automatisch durchgeführt werden. Die Grenzen zwischen verschiedenen automatischen Verfahren sind häufig fließend; außerdem lassen sich Verfahren kombinieren, um bessere Ergebnisse zu erhalten.

Mathematische Beschreibung und Eigenschaften

Gegeben sei ein Gebiet Ω ⊂ ℝᵈ und ein Bild u: Ω → 𝓜ᵏ. Dabei ist d ∈ ℕ die Dimension des Bildes und k ∈ ℕ die Anzahl der Kanäle im Farbraum 𝓜ᵏ. Das Gebiet wird in disjunkte Teilgebiete Ωᵢ zerlegt: Ω̄ = ⋃ᵢ Ω̄ᵢ und Ωᵢ ∩ Ωⱼ = ∅ für i ≠ j. Bei zweidimensionalen Bildern entsprechen die Teilgebiete gleich großen Rechtecken, also Pixeln (d = 2), bei dreidimensionalen Bildern Würfeln, also Voxeln (d = 3). Innerhalb eines solchen Teilgebiets besitzt das Bild den konstanten Wert c ∈ 𝓜ᵏ. Bei einem Graustufenbild mit k = 1 und einer Farbtiefe von 16 Bit gilt beispielsweise 𝓜ᵏ = {0, …, 2¹⁶ − 1}¹.

Eine Segmentierung ist eine Abbildung A: Ω → {0, 1, 2, …}, die jedem Pixel oder Voxel anhand bildbezogener Entscheidungskriterien ein Label zuweist. Bei der Segmentierung eines einzelnen Objekts kann der Objektbereich den Labelwert 1 und der Hintergrund den Wert 0 erhalten: A|Ωᵢ = 1, falls Ωᵢ dem Objekt zugeordnet wird, und A|Ωᵢ = 0, falls Ωᵢ dem Hintergrund zugeordnet wird.

Eine Segmentierung ist vollständig, wenn jedes Pixel mindestens einem Segment zugeordnet wird. Sie ist überdeckungsfrei, wenn jedes Pixel höchstens einem Segment zugeordnet wird. Ist sie vollständig und überdeckungsfrei, gehört jedes Pixel genau einem Segment an. Zusammenhängend ist eine Segmentierung, wenn jedes Segment ein zusammenhängendes Gebiet bildet.

Typen der Segmentierung

Im maschinellen Lernen werden insbesondere vier Typen unterschieden:

Die semantische Segmentierung teilt ein Bild in Klassen ein. Jedem Pixel oder Datenpunkt wird beispielsweise die Klasse „Fußgänger“ oder „Fahrradfahrer“ zugeordnet.
Die Instanzsegmentierung unterscheidet einzelne Objekte derselben Klasse. Jeder Instanz wird ein individueller Wert zugewiesen. Mehrere sichtbare Fußgänger werden dadurch als verschiedene Instanzen erkannt; dies ermöglicht auch ihre zeitliche Verfolgung, das Tracking.
Die panoptische Segmentierung verbindet semantische und Instanzsegmentierung. Jedes Pixel erhält sowohl eine Klasse als auch eine Instanz, sodass einzelne Objekte einer Klasse zugeordnet werden können.
Die amodale Segmentierung berücksichtigt Verdeckungen. Einem Pixel können dabei mehrere Klassen oder Instanzen zugewiesen werden. Ein teilweise von einem Fahrradfahrer verdeckter Fußgänger kann so vollständig gelabelt werden.

Verfahren und Methoden

Automatische Verfahren werden häufig in pixel-, kanten- und regionenorientierte Verfahren eingeteilt. Zusätzlich gibt es modellbasierte Verfahren, die von einer bestimmten Objektform ausgehen, sowie texturorientierte Verfahren, die die innere Struktur eines Objekts berücksichtigen.

Pixelorientierte Verfahren entscheiden für jeden Bildpunkt, ob er zu einem Segment gehört. Sie sind meist einfach und schnell zu berechnen, erzeugen aber zunächst keine zusammenhängenden Segmente. Die Binarisierung ist eine Vorstufe der Segmentierung: Ein Bild wird in zwei Wertebereiche eingeteilt, sodass einzelne Objekte gezählt und beispielsweise durch Lauflängencodierung beschrieben werden können. Besonders verbreitet ist das Schwellwertverfahren. Der Schwellwert wird möglichst über ein Histogramm bestimmt; im einfachsten Fall ist er der Mittelwert aus dem dunkelsten und dem hellsten Grauwert.

Kantenorientierte Verfahren suchen nach Kanten oder Objektübergängen. Die zunächst gefundenen Kantenpixel sind oft nicht geschlossen und müssen durch Kantenverfolgung zu Linien, Polygonen oder Kurven verbunden werden. Der Sobel-Operator und der Laplace-Operator sowie Gradientensuchen dienen der Kantenerkennung. Beim Sobel-Operator werden zwei Faltungsmatrizen verwendet: eine für horizontale und eine für vertikale Kanten. Bei einer Faltung wird ein Filterkern auf das Bild gelegt, elementweise mit den Bildwerten multipliziert, schrittweise verschoben und auf alle Pixel angewendet. Das Live-Wire-Verfahren sucht einen optimalen Weg zwischen Start und Ziel, der möglichst über starke Kantenpixel verläuft; hierfür kann beispielsweise eine Breitensuche eingesetzt werden. Die Wasserscheidentransformation arbeitet auf Graustufenbildern und liefert immer geschlossene Kantenzüge. Weitere Verfahren sind parallele und sequentielle Kantenextraktion, optimale Kantensuche, der Felzenszwalb-Huttenlocher-Algorithmus, Active Shape Models und Snakes.

Regionenorientierte Verfahren betrachten Punktmengen als zusammenhängende Gesamtheit. Zu ihnen gehören Region Growing, Region-Splitting, Pyramid Linking sowie Split and Merge. Bei der Schwellenwertsegmentierung werden Pixelwerte unter- oder oberhalb eines Schwellenwerts als Objekt oder Hintergrund klassifiziert. Ein globaler Schwellenwert kann Objekt und Hintergrund trennen; bei mehreren Objekten werden mehrere, als lokale Schwellenwerte bezeichnete Werte verwendet. Das Verfahren ist schnell und funktioniert bei hohem Kontrast gut, scheitert aber leichter bei geringen Graustufenunterschieden oder überlappenden Helligkeitswerten.

In einem kontinuierlichen Modell kann ein Graustufenbild als Funktion u₀: [0;1]² → ℝ aufgefasst werden. Energiemethoden ordnen jeder möglichen Segmentierung einen Energiewert zu und suchen ein Minimum. Typische Bestandteile sind der Unterschied zum Originalbild, etwa ∫(u − u₀)², die Länge der Segmentierungskanten, etwa 𝓗²(C), sowie bei nicht konstanten Intensitäten ein Maß wie ∫_[0;1]²\C |∇u|. Graph-Cut-Verfahren führen zu diskreten Algorithmen und sind für kleinere Bilder derzeit in Echtzeit mit 30 fps möglich, jedoch nur pixelgenau. Variationsmethoden lösen den Abstieg der Energiefunktion als partielle Differentialgleichung und erlauben Subpixelgenauigkeit. Das vermeidet Treppeneffekte an diagonalen Kanten. Für GPU-Umsetzungen wurden Geschwindigkeitsvorteile vom Faktor 5 bis 40 vorausgesagt.

Beim k-Means-Verfahren wird ein Bild iterativ in k Cluster aufgeteilt. Zuerst werden k Clusterzentren gewählt. Danach wird jedes Pixel dem nächstgelegenen Zentrum zugeordnet, die Zentren werden aus den Pixeln ihres Clusters neu berechnet und die Schritte werden wiederholt, bis kein Pixel mehr das Cluster wechselt. Als Abstand dienen typischerweise die quadratische oder absolute Differenz; berücksichtigt werden können Pixelfarbe, Intensität, Textur und Ort oder eine gewichtete Kombination. k-Means konvergiert immer, liefert aber nicht zwingend die optimale Lösung. Das Ergebnis hängt von der Anfangsauswahl und vom Wert k ab.

Modellbasierte Verfahren verwenden Wissen über die erwartete Form oder Struktur eines Objekts. Die Hough-Transformation kann Punkte in einem Parameterraum zu Linien oder Kreisen zusammenfügen. Außerdem werden statistische Modelle und Template-Matching eingesetzt, bei dem im Bild nach vorgegebenen Vorlagen gesucht wird. Texturorientierte Verfahren behandeln Objekte, die keine einheitliche Farbe, aber eine einheitliche Textur besitzen. Beispiele sind Cooccurrence-Matrizen beziehungsweise Haralick-Matrizen, Texturenergiemaße, Lauflängenmatrizen, fraktale Dimensionen, Markow-Random-Fields, Gibbs-Potentiale, strukturelle Ansätze und signaltheoretische Konzepte. Diese Verfahren liegen teilweise im Grenzbereich zur Klassifikation oder verbinden Segmentierung und Klassifizierung.

Deep Learning und Segmentierungsprobleme

Auch Methoden des maschinellen Lernens werden zur Segmentierung eingesetzt. Fully Convolutional Networks (FCNs) sind Varianten von Convolutional Neural Networks (CNNs), die ausschließlich Faltungsoperationen verwenden. Sie können Eingabedaten beliebiger Größe in Ausgaben entsprechender Größe umwandeln. Im Encoder-Teil erkennen die Faltungen zunehmend abstrakte Merkmale (Features) bei abnehmender räumlicher Auflösung. Der Decoder-Teil projiziert diese Merkmale wieder auf die ursprüngliche Bildauflösung.

Ein häufig verwendeter Vertreter ist U-Net. Seine zentrale Erweiterung sind Skip-Connections: Jede Decoderebene erhält zusätzlich die Merkmale der entsprechenden Encoderebene. Meta AI veröffentlichte im April 2023 das Segment Anything Model (SAM). Es kann mithilfe einfacher Eingaben wie Punkten oder Begrenzungsrahmen nahezu beliebige Objekte segmentieren, ohne für bestimmte Objektklassen neu trainiert werden zu müssen. Im Juli 2024 folgte SAM 2, das die Segmentierung auf Videos erweiterte.

Die Qualität einer Segmentierung kann durch wechselnde Beleuchtung beeinträchtigt werden. Dann funktioniert die Segmentierung möglicherweise nur in einem Bildbereich zuverlässig. Eine Vorbearbeitung, beispielsweise eine Shading-Korrektur, kann Helligkeitsunterschiede ausgleichen. Weitere typische Fehler sind Übersegmentierung mit zu vielen und Untersegmentierung mit zu wenigen Segmenten. Dagegen können Wissen über die erwartete Anzahl der Segmente, ein nachfolgender Klassifikationsschritt oder eine manuelle Zusammenfassung helfen. Viele Verfahren, darunter Schwellwertverfahren und Wasserscheidentransformation, arbeiten nur mit einkanaligen Graustufenbildern. Bei Mehrkanalbildern wie Farbbildern bleiben deshalb Informationen ungenutzt, sofern nicht mehrere einkanalige Segmentierungen anschließend zusammengeführt werden.

Anwendungen und Software

Segmentierung ist häufig die Grundlage für eine anschließende Klassifizierung und weitere Bildanalyse. Ihr derzeit häufigster Einsatzbereich ist die Medizin, insbesondere bei Aufnahmen aus Computertomografie und Magnetresonanztomografie. Werden beispielsweise ein Tumor oder ein Organ aus einem Bild herausgetrennt, können Volumen und Form bestimmt oder ein dreidimensionales Modell erzeugt werden. Dadurch ist Segmentierung für computergestützte ärztliche Diagnostik und Therapieplanung besonders wichtig.

Weitere Anwendungen liegen in der Geodatenverarbeitung, bei der Satelliten- und Luftbilder in geometrische Daten überführt werden. So können unterschiedliche Landbedeckungs- oder Landnutzungsflächen abgegrenzt werden; dabei kommen vor allem regionen- und kantenbasierte Verfahren zum Einsatz. Auch die automatische optische Qualitätskontrolle von Werkstücken, etwa die Prüfung der Position eines Bohrlochs, die Schrifterkennung sowie die Gesichtserkennung verwenden Segmentierung. In der OCR wird durch Binarisierung Schrift vom Hintergrund getrennt.

Bildverarbeitungsprogramme wie das freie Scikit-image stellen Segmentierungsalgorithmen und darauf aufbauende Bildverarbeitungsfunktionen bereit, etwa zur Ermittlung von Objektpositionen in der Robotik. Bildbearbeitungsprogramme wie das freie GIMP und das kostenlose IrfanView bieten einfache Verfahren, beispielsweise Schwellwertsegmentierung oder Kantendetektion mit Sobel- und Laplace-Operatoren. Schrifterkennungsprogramme und Spezialsoftware für Medizin und Geoinformatik können Segmentierung ebenfalls als ersten oder zentralen Verarbeitungsschritt einsetzen.