Connected-Component-Labeling (CCL), auch bekannt als Connected-Component-Analyse, Blob-Extraktion, Regionen-Labeling oder Blob-Erkennung, ist eine algorithmische Anwendung der Graphentheorie, bei der Teilmengen verbundener Komponenten basierend auf einer gegebenen Heuristik eindeutig beschriftet werden. Sie wird in der Computervision verwendet, um verbundene Regionen in binären digitalen Bildern zu erkennen, obwohl auch Farbbilder und höherdimensionale Daten verarbeitet werden können. CCL unterscheidet sich von der Bildsegmentierung, und die Blob-Extraktion ist verwandt mit, aber verschieden von der Blob-Erkennung.
In der Praxis arbeitet CCL auf einem Graphen, der aus Eingabedaten konstruiert wird, wobei Knoten Pixel oder Elemente darstellen und Kanten die Konnektivität zwischen Nachbarn anzeigen. Ein Algorithmus durchläuft den Graphen und weist Knoten Beschriftungen basierend auf Konnektivität und relativen Werten zu. Nach der Beschriftung kann der Graph in Teilmengen partitioniert werden, sodass die ursprünglichen Informationen wiederhergestellt und für Aufgaben wie Zählen, Filtern und Verfolgen von Blobs verarbeitet werden können.
Definition und Terminologie
Der Begriff Connected-Component-Labeling wird in der akademischen Literatur konsistent verwendet, während Connected-Component-Analyse (CCA) sowohl in der Terminologie als auch in der Problemdefinition variiert. Rosenfeld et al. definieren CCL als die Erstellung eines beschrifteten Bildes, in dem Positionen, die mit derselben verbundenen Komponente des binären Eingabebildes assoziiert sind, eine eindeutige Beschriftung haben. Shapiro et al. beschreiben CCL als einen Operator, dessen Eingabe ein binäres Bild und dessen Ausgabe ein symbolisches Bild ist, wobei die Beschriftung jedes Pixels eine ganze Zahl ist, die seine verbundene Komponente eindeutig identifiziert.
Es gibt keinen Konsens über die Definition von CCA; sie wird oft austauschbar mit CCL verwendet. Eine umfassendere Definition von Shapiro et al. besagt, dass CCA aus Connected-Component-Labeling schwarzer Pixel besteht, gefolgt von Eigenschaftsmessung der Komponentenregionen und Entscheidungsfindung. Dieser Artikel übernimmt eine breitere Interpretation, die diese Perspektiven integriert.
Graphkonstruktion und Konnektivität
Ein Graph wird aus relevanten Eingabedaten konstruiert, wobei Knoten Informationen enthalten, die für die Vergleichsheuristik benötigt werden, und Kanten verbundene Nachbarn anzeigen. Der Algorithmus durchläuft den Graphen und beschriftet Knoten basierend auf Konnektivität und relativen Werten. Die Konnektivität wird durch das Medium bestimmt; für Bildgraphen umfassen übliche Nachbarschaften 4-verbunden (Norden, Süden, Osten, Westen) und 8-verbunden (einschließlich Diagonalen).
Nach der Beschriftung kann der Graph in Teilmengen partitioniert werden, wonach ursprüngliche Informationen wiederhergestellt und verarbeitet werden können. Dieser Ansatz verallgemeinert auf beliebige Dimensionen, obwohl Zeit- und Raumkomplexität entsprechend zunehmen.
Ein-Komponente-auf-einmal-Algorithmus
Der Ein-Komponente-auf-einmal-Algorithmus ist schnell, einfach zu implementieren und basiert auf Graphendurchlaufmethoden. Er ist Teil von Vincent und Soilles Wasserscheiden-Segmentierungsalgorithmus, wobei andere Implementierungen existieren. Die Methode verwendet eine verknüpfte Liste, um Indizes verbundener Pixel zu speichern, wobei die Wahl zwischen Tiefensuche oder Breitensuche für diese Anwendung keinen praktischen Unterschied macht.
Der Algorithmus nimmt ein binäres Bild mit Vordergrund- und Hintergrundpixeln an und zielt darauf ab, verbundene Komponenten im Vordergrund zu beschriften. Schritte:
- Beginne beim ersten Pixel und setze die aktuelle Beschriftung auf 1.
- Wenn das Pixel Vordergrund und unbeschriftet ist, weise die aktuelle Beschriftung zu und füge es einer Warteschlange hinzu; andernfalls bewege dich zum nächsten Pixel.
- Entnimm ein Element aus der Warteschlange und untersuche seine Nachbarn (basierend auf dem Konnektivitätstyp). Wenn ein Nachbar Vordergrund und unbeschriftet ist, weise die aktuelle Beschriftung zu und füge es der Warteschlange hinzu. Wiederhole, bis die Warteschlange leer ist.
- Bewege dich zum nächsten Pixel und erhöhe die aktuelle Beschriftung.
Pixel werden beschriftet, bevor sie in die Warteschlange aufgenommen werden, und die Nachbarn jedes Vordergrundpixels werden nur einmal überprüft; die Nachbarn von Hintergrundpixeln werden nicht überprüft. Der Pseudocode verwendet zwei Warteschlangen, um die Pixelverarbeitung zu verwalten und eine effiziente Traversierung sicherzustellen.
Anwendungen in der Computervision
CCL wird häufig in der Computervision verwendet, um verbundene Regionen in binären Bildern zu erkennen, oft nach einem Schwellenwert-Schritt. Die Blob-Extraktion kann auch auf Graustufen- und Farbbilder angewendet werden. Blobs können gezählt, gefiltert und verfolgt werden, was CCL in Bilderkennungssystemen und Mensch-Computer-Interaktionsschnittstellen wertvoll macht.
Zum Beispiel kann CCL in Machine learning-Pipelines Bilder für Objekterkennungs- oder Segmentierungsaufgaben vorverarbeiten und Techniken wie U-Net-Architekturen ergänzen. Es wird auch in Artificial intelligence-Systemen zur Analyse medizinischer Bilder, industrieller Inspektion und autonomen Fahrens verwendet, wo die Identifizierung verbundener Regionen entscheidend ist.
Verwandte Konzepte und Erweiterungen
CCL ist verwandt mit, aber verschieden von der Blob-Erkennung, die sich auf die Identifizierung von Interessensregionen basierend auf Intensitätsvariationen konzentriert. Im Gegensatz dazu beschriftet CCL alle verbundenen Komponenten basierend auf Konnektivität. Der Algorithmus kann auf höherdimensionale Daten erweitert werden, wie 3D-Volumina in der medizinischen Bildgebung, mit erhöhten Rechenkosten.
Jüngste Fortschritte in Deep learning und Neural network-Modellen haben zu gelernten Ansätzen für die Segmentierung geführt, aber CCL bleibt ein grundlegendes Werkzeug für Nachbearbeitung und Analyse. Seine Einfachheit und Effizienz machen es zu einem festen Bestandteil in Computervisionsbibliotheken und -frameworks, oft verwendet in Verbindung mit Data Augmentation und Loss Functions in Trainingspipelines.
Siehe auch
- Computer vision
- image-segmentation
- blob-detection
- graph-theory