Spaghetti-Labeling: Gerichtete azyklische Graphen für blockbasierte Kennzeichnung zusammenhängender Komponenten

Die Kennzeichnung zusammenhängender Komponenten ist ein wesentlicher Schritt in vielen Aufgaben der Bildverarbeitung und Computer Vision. Seit dem ersten Vorschlag eines Kennzeichnungsalgorithmus aus den sechziger Jahren haben viele Ansätze die Rechnerlast optimiert, die nötig ist, um ein Bild zu kennzeichnen. Insbesondere sind in letzter Zeit Entscheidungswälder und Zustandsvorhersage als wertvolle Strategien erschienen, um die Leistung zu verbessern. Aufgrund des Aufwands für die manuelle Erstellung von Vorhersagezuständen und der Größe des resultierenden Maschinencodes war jedoch die Anwendung dieser Strategien auf kleine Masken beschränkt, wodurch der Nutzen einer blockbasierten Herangehensweise ignoriert wurde. In diesem Papier kombinieren wir eine blockbasierte Maske mit Zustandsvorhersage und Codekompression: Der resultierende Algorithmus wird als gerichteter, verwurzelter azyklischer Graph mit mehreren Einstiegspunkten modelliert, der automatisch ohne manuelles Eingreifen generiert wird. Bei Tests an synthetischen und realen Datensätzen zeigt der vorgeschlagene Ansatz im Vergleich zu optimierten Implementierungen von Hochleistungsalgorithmen eine überlegene Leistung und übertrifft die Ergebnisse aller verglichenen Ansätze in allen Einstellungen.