Co to jest kodeks łańcuchowy?
W grafice komputerowej i przetwarzaniu obrazu kod łańcucha jest algorytmem używanym do kodowania konturów obiektu w obrazie czarno-białym lub monochromatycznym. Wynikowa sekwencja kodów może albo opisać, jak narysować kontur obiektu względem obrazu, na którym się znajduje, lub może być zbiorem kierunków względem lokalizacji na konturze, w którym algorytm się rozpoczął, zasadniczo zapewniając kroki, które można śledzić, aby przerysować obiekt. Kody te można znormalizować zgodnie ze wzorem, a następnie porównać z innym kodem łańcucha, aby ustalić, czy dwa obiekty są identyczne. Kod łańcuchowy może być używany do izolowania obiektów w komputerowym programie wizyjnym lub segmentacji obrazu podczas przetwarzania obrazu, chociaż częściej może być stosowany w programach optycznego rozpoznawania znaków (OCR).
Chociaż istnieje kilka ustalonych algorytmów dla kodu łańcucha, podstawowa koncepcja jest taka sama w każdym. Najpierw lokalizowana jest krawędź obiektu, zwykle poprzez przesunięcie piksel po pikselu przez obraz rastrowy. Po zlokalizowaniu pozycja jest rejestrowana, a otaczające ją krawędzie są wykrywane. W zależności od tego, czy algorytm wykrywania przesunie się w prawo, czy w lewo, bieżąca lokalizacja jest przesuwana w jednym lub drugim kierunku wzdłuż krawędzi, aż powróci do pierwotnej pozycji.
Za każdym razem, gdy bieżąca pozycja się porusza, w kodzie łańcucha zapisywana jest liczba. Liczba ta ogólnie wskazuje kierunek, który został przesunięty wzdłuż krawędzi obiektu. Na przykład, jeśli algorytm kodu łańcucha podąża za prostą krawędzią od prawej do lewej, to za każdym razem, gdy krawędź jest śledzona w lewo, kod numeryczny dla lewej jest dodawany na końcu kodu. Wynikowy kod jest ciągiem liczb, w którym, jeśli sekwencja będzie śledzona od dowolnego punktu początkowego, a piksel zostanie umieszczony na każdym kroku, kontur obiektu zostanie przerysowany.
Po zakończeniu ciągu liczb składających się na kod można zastosować kilka różnych algorytmów, aby pomóc w porównaniu z innymi sekwencjami kodu łańcucha. Po pierwsze, liczbę normalizuje się, obracając liczbę początkową, aż do ustalenia najniższej wartości całkowitej. W ten sposób można porównać dwa obiekty o tym samym obrysie, niezależnie od tego, gdzie na każdym obiekcie rozpoczęło się kodowanie.
Istnieją inne, bardziej złożone wersje algorytmu kodu łańcucha. Obejmują one kodowanie wektorowe, w którym obrys obiektu jest opisany przez sekwencję współrzędnych połączonych liniami, chociaż ta metoda może być stratna, jeśli zostanie użyta na bardzo szczegółowych konturach. Istnieje również wersja algorytmu, która wykorzystuje kodowanie typu run-length (RLE) w celu dalszego kompresowania kodów dla wyjątkowo dużych lub złożonych obiektów, aby można je było przechowywać w bardziej wydajny sposób.