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 Algorytmy. Ćwiczenia
34,90 zł
Uczenie maszynowe z użyciem Scikit-Learn i TensorFlow
89,00 zł
UX w projektowaniu witryn internetowych
−30%38,43 zł
JavaScript i jQuery. Interaktywne strony WWW dla każdego. Podręcznik Front-End Developera
99,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 Floyda-Warshalla – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Jest to algorytm oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n3) i złożoność pamięciową O(n2), gdzie n jest liczbą wierzchołków.

Algorytm dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli. Algorytm może być również wykorzystywany do wyszukiwania ujemnych cykli w grafie.

→ Czytaj całość

Metoda z zastosowaniem przepływu blokującego – algorytm wyznaczający maksymalny przepływ w sieci przepływowej. W algorytmie tym przepływ zwiększany jest iteracyjnie, w każdej iteracji wyznaczony przepływ jest powiększany o przepływ blokujący w warstwowej sieci residualnej.

→ Czytaj całość

Graf – struktura składająca się ze zbioru wierzchołków oraz zbioru krawędzi. Grafy mają szerokie zastosowanie w informatyce, można za ich pomocą przedstawić wiele zagadnień.

Wyróżniamy grafy nieskierowane oraz grafy skierowane. W grafie nieskierowanym relacja sąsiedztwa jest symetryczna, tzn. krawędź łączy wierzchołki „w obie strony”. W grafie skierowanym krawędzie są „jednokierunkowe”. Krawędź grafu skierowanego zazwyczaj jest określana jako łuk.

Graf ważony (inaczej graf z wagami) to taki graf, w którym każdej krawędzi przypisana jest pewna wartość liczbowa. Wartość ta może oznaczać np. długość krawędzi lub jej przepustowość.

→ Czytaj całość
Polityka prywatnościKontakt