Algorytm Zhanga-Suena

Szkieletyzacja, animacja (1) Wykonanie algorytmu krok po kroku. Kolorem szarym oznaczono piksele usuwane w bieżącej iteracji
Szkieletyzacja, skoczek (2) Przykładowy obraz binarny i jego szkielet uzyskany za pomacą algorytmu
REKLAMA PHP 7. Algorytmy i struktury danych
59,00 zł
English 4 IT. Praktyczny kurs języka angielskiego dla specjalistów IT i nie tylko
39,90 zł
Ethereum dla zaawansowanych. Tworzenie inteligentnych kontraktów i aplikacji zdecentralizowanych
−30%55,30 zł
Mistrz czystego kodu. Kodeks postępowania profesjonalnych programistów
39,00 zł

Algorytm Zhanga-Suena – algorytm służący do szkieletyzacji obrazu binarnego. Szieletyzacja polega na wyborze z obrazu binarnego tych pikseli, które są równo odległe od krawędzi obiektu.

Przebieg algorytmu

Przyjmijmy, że w przetwarzanym obrazie binarnym piksele o wartości 0 są pikselami tła, a piksele o wartości 1 są pikselami obiektów. Algorytm Zhanga-Suena jest algorytmem iteracyjnym – w każdej iteracji dla każdego piksela obiektów podejmowana jest decyzja, czy piksel ten należy usunąć, czy zostawić. Przy podjęciu decyzji brane jest pod uwagę sąsiedztwo piksela liczące 8 pikseli (sąsiedztwo Moore'a). Niech piksel P1 będzie aktualnie analizowanym pikselem. Jego sąsiedztwo oznaczone jest następująco:

P9 P2 P3
P8 P1 P4
P7 P6 P5

Dla analizowanego piksela P1 najpierw należy wyznaczyć następujące wartości:

  • B(P1) – liczba pikseli o wartości 1 w sąsiedztwie piksela,
  • A(P1) – liczba przejść 01 w ciągu (P2, P3, P4, P5, P6, P7, P8, P9, P2).
Piksel P1 należy usunąć, jeśli spełnione są następujące warunki:
  • 2 ≤ B(P1) ≤ 6,
  • A(P1) = 1,
  • (P2×P4×P6)+(P4×P6×P8)=0.
W iteracjach o numerach parzystych (druga, czwarta itd.) trzeci warunek należy zastąpić warunkiem:
  • (P2×P4×P8)+(P2×P6×P8)=0.

Należy pamiętać, że w każdej iteracji obraz należy zmodyfikować dopiero po przeanalizowaniu wszystkich pikseli – jeśli podjęto decyzję o usunięciu piksela, to do zakończenia danej iteracji dla jego sąsiadów musi on być nadal traktowany jako piksel o wartości 1. Można to zagwarantować np. tworząc na początku iteracji kopię obrazu, aby sprawdzać wartość pikseli w kopii, a modyfikować oryginał.

Algorytm kończy swoje działanie, gdy w trakcie dwóch ostatnich iteracji nie został usunięty żaden piksel.

Aby uniknąć błędów związanych z odczytem spoza obrazu, nie można analizować pikseli znajdujących się przy samej krawędzi. Z tego powodu dobrze jest zapewnić, że żaden piksel obiektu nie leży na krawędzi obrazu. Przykładowo, można przed rozpoczęciem działania algorytmu dodać do obrazu z każdej strony krawędź o szerokości jednego piksela zawierającą tylko piksele tła.

Komentarze

Warunek B(P1)≥2 zabezpiecza przed usunięciem ostatniego piksela w linii. Warunek B(P1)≤6 zabezpiecza przed wycinaniem dziur wewnątrz obiektów. Warunek A(P1)=1 zabezpiecza przed usunięciem piksele należące do szkieletu (sąsiadujące z tłem z więcej niż jednej strony). Dzięki trzeciemu warunkowi (zmieniającemu się pomiędzy iteracjami) w przypadku idealnie pionowych lub poziomych bloków ścinana jest naprzemiennie jedna i druga krawędź, co zabezpiecza przez powstaniem dziur w szkielecie (nie ma ryzyka, że dwa piksele pośrodku bloku zostaną usunięte w tej samej iteracji).

Algorytm ma pewne mankamenty. Przykładowo, w wyniku jego działania usunięte zostaną kwadraty o wymiarach 2×2. Innym problemem jest przycięcie niektórych ukośnych linii do pojedynczego piksela – taki przypadek przedstawiono w lewym dolnym rogu animacji (1).

Algorytm został opublikowany w pracy [1]. Przykładowe implementacje algorytmu są dostępne na stronie [2].

Bibliografia

  • T.Y. Zhang, C.Y. Suen, A Fast Parallel Algorithm for Thinning Digital Patterns, Magazine Communications of the ACM, Volume 27, Issue 3, 1984, s. 236-239, DOI: 10.1145/357994.358023.
  • Zhang-Suen thinning algorithm, rosettacode.org [Dostęp 2019-02-02].
Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 2 lutego 2019 15:18.

REKLAMA

Zobacz też

Algorytm najbliższego sąsiada (ang. nearest neighbour algorithm, w skrócie NN) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm wykorzystujący strategię zachłanną.
→ Czytaj całość

Dziel i zwyciężaj (ang. divide and conquer) – technika projektowania algorytmów polegająca na podejściu rekurencyjnym. W technice tej problem dzielony jest na mniejsze podproblemy, te podproblemy na jeszcze mniejsze podproblemy, aż dojdzie się do przypadków trywialnych (np. posortowanie jednoelementowej tablicy, obliczenie silni z 1).

Jeśli rozpatrywany problem wymaga podzielenia na podproblemy, jest on określany jako przypadek rekurencyjny. Jeśli mamy do czynienia z przypadkiem trywialnym, jest to przypadek bazowy. Tworząc algorytm wykorzystujący metodę dziel i zwyciężaj musimy ustalić:

  • Jak rozwiązać przypadek bazowy (trywialny).
  • Jak wyznaczyć rozwiązanie problemu, mając dostępne rozwiązania podproblemów.

Przykładem algorytmu opartego na tej metodzie jest sortowanie przez scalanie.

→ Czytaj całość

Sortowanie przez wstawianie (ang. insertion sort) – prosty algorytm sortowania polegający na wstawianiu kolejnych elementów ciągu we właściwe miejsca. Złożoności czasowa algorytmu wynosi O(n2). Jest to algorytm realizujący metodę przyrostową.

→ Czytaj całość
Polityka prywatnościKontakt