Szukaj

Algorytm Zhanga-Suena – algorytm służący do szkieletyzacji obrazu binarnego. Szkieletyzacja 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 P₁ 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 P₁ najpierw należy wyznaczyć następujące wartości:

• B(P₁) – liczba pikseli o wartości 1 w sąsiedztwie piksela,
• A(P₁) – liczba przejść 01 w ciągu (P₂, P₃, P₄, P₅, P₆, P₇, P₈, P₉, P₂).

Piksel P₁ należy usunąć, jeśli spełnione są następujące warunki:

• 2 ≤ B(P₁) ≤ 6,
• A(P₁) = 1,
• (P₂×P₄×P₆)+(P₄×P₆×P₈)=0.

W iteracjach o numerach parzystych (druga, czwarta itd.) trzeci warunek należy zastąpić warunkiem:

• (P₂×P₄×P₈)+(P₂×P₆×P₈)=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(P₁)≥2 zabezpiecza przed usunięciem ostatniego piksela w linii. Warunek B(P₁)≤6 zabezpiecza przed wycinaniem dziur wewnątrz obiektów. Warunek A(P₁)=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].