Was ist ein Kettencode?
In der Computergrafik und Bildverarbeitung ist ein Kettencode ein Algorithmus, mit dem die Konturen eines Objekts in einem Schwarzweiß- oder Schwarzweißbild codiert werden. Die resultierende Sequenz von Codes kann entweder beschreiben, wie der Umriss des Objekts relativ zu dem Bild, in dem es sich befindet, gezeichnet wird, oder es kann eine Sammlung von Richtungen relativ zu dem Ort auf dem Umriss sein, an dem der Algorithmus gestartet wurde, und im Wesentlichen Schritte bereitstellen, die dies ermöglichen kann befolgt werden, um das Objekt neu zu zeichnen. Diese Codes können nach einer Formel normalisiert und dann mit einem anderen Kettencode verglichen werden, um festzustellen, ob zwei Objekte identisch sind. Ein Kettencode kann zum Isolieren von Objekten in einem Computer-Bildverarbeitungsprogramm oder zur Bildsegmentierung bei der Bildverarbeitung verwendet werden, obwohl er häufiger in Programmen zur optischen Zeichenerkennung (OCR) verwendet werden kann.
Obwohl es für einen Kettencode mehrere etablierte Algorithmen gibt, ist das Grundkonzept in jedem gleich. Erstens wird die Kante eines Objekts lokalisiert, normalerweise durch Bewegen von Pixel zu Pixel durch ein Rasterbild. Sobald lokalisiert, wird die Position aufgezeichnet und die umliegenden Kanten werden erkannt. Abhängig davon, ob sich der Erkennungsalgorithmus im oder gegen den Uhrzeigersinn bewegt, wird die aktuelle Position in die eine oder andere Richtung entlang der Kante verschoben, bis sie zur ursprünglichen Position zurückkehrt.
Jedes Mal, wenn sich die aktuelle Position bewegt, wird eine Nummer im Kettencode vermerkt. Diese Zahl gibt im Allgemeinen die Richtung an, die entlang der Kante des Objekts bewegt wurde. Wenn beispielsweise ein Kettencodealgorithmus einer geraden Kante von rechts nach links folgt, wird jedes Mal, wenn die Kante nach links gezogen wird, der numerische Code für links am Ende des Codes hinzugefügt. Der resultierende Code ist eine Folge von Zahlen, bei der, wenn die Sequenz von einem beliebigen Startpunkt aus verfolgt und bei jedem Schritt ein Pixel platziert wird, der Umriss des Objekts neu gezeichnet wird.
Sobald die Zahlenfolge, aus der der Code besteht, vollständig ist, können verschiedene Algorithmen angewendet werden, um Vergleiche mit anderen Kettencodesequenzen anzustellen. Zuerst wird die Zahl normalisiert, indem die Startzahl gedreht wird, bis der niedrigste ganzzahlige Wert bestimmt ist. Auf diese Weise können zwei Objekte mit demselben Umriss verglichen werden, unabhängig davon, wo bei jedem Objekt die Codierung gestartet wurde.
Andere, komplexere Versionen des Kettencodealgorithmus existieren. Dazu gehört die vektorbasierte Codierung, bei der der Umriss eines Objekts durch eine Folge von Koordinaten beschrieben wird, die durch Linien verbunden sind, obwohl diese Methode bei der Verwendung fein detaillierter Umrisse verlustbehaftet sein kann. Es gibt auch eine Version des Algorithmus, die die Lauflängencodierung (RLE) verwendet, um die Codes für außergewöhnlich große oder komplexe Objekte weiter zu komprimieren, damit sie effizienter gespeichert werden können.