Algorytm Zhanga-Suena
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 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).
- 2 ≤ B(P1) ≤ 6,
- A(P1) = 1,
- (P2×P4×P6)+(P4×P6×P8)=0.
- (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].
Liczba głosów: 1.
- Algorytm Zhanga-Suena
- Metoda Otsu
Dodano: 2 lutego 2019 15:18, ostatnia edycja: 21 kwietnia 2020 17:38.
Zobacz też
Notacja dużego O – notacja przedstawiająca asymptotyczne tempo wzrostu, wykorzystywana do zapisywania złożoności obliczeniowej algorytmu. Za pomocą tej notacji zapisywany jest rząd wielkości funkcji wyrażającej liczbę operacji dominujących (w przypadku złożoności czasowej) lub rozmiar wymaganej pamięci (w przypadku złożoności pamięciowej) w zależności od liczby danych wejściowych.
Wykorzystując notację dużego O nie podajemy dokładnego wzoru funkcji, a jedynie jej najbardziej znaczący składnik, w dodatku z pominięciem stałego współczynnika. Przykładowo, funkcję postaci f(n)=5n2+20n+100 możemy zapisać jako O(n2). Zakładamy bowiem, że dla dostatecznie dużych n wpływ pomijanych elementów jest znikomy. Choć oczywiście dla małych n może się zdarzyć, że funkcja o gorszej złożoności będzie się wykonywała szybciej.
Weźmy dla przykładu funkcje f(n) = 1000n+2000 i g(n) = n2. Choć pierwsza funkcja ma pozornie bardzo duże stałe współczynniki, to dla n ≥ 1002 będzie ona przyjmowała wartości mniejsze. Im większe n, tym ta różnica będzie wyraźniejsza. Dla n = 10000 (w przypadku danych przetwarzanych komputerowo nie jest to wielka wartość) f(n) = 10002000 (ok. 10 mln), a g(n) = 100000000 (100 mln), czyli blisko 10 razy więcej.
Możliwe jest również wykorzystanie notacji dużego O dla funkcji wielu zmiennych. Wówczas zapis może wyglądać tak: O(v2e). Znajduje to zastosowanie np. dla algorytmów operujących na grafach, gdzie złożoność zależy zarówno od liczby wierzchołków, jak i liczby krawędzi w grafie.
Algorytm Edmondsa-Karpa – algorytm wyszukiwania maksymalnego przepływu w sieci przepływowej. Jest to przypadek szczególny algorytmu Forda-Fulkersona.
W algorytmie Edmondsa-Karpa ścieżka powiększająca wyznaczana jest za pomocą przeszukiwania grafu wszerz. Dzięki temu w każdej iteracji algorytmu dołączana jest zawsze najkrótsza (pod względem liczby krawędzi) ścieżka powiększająca. W metodzie Forda-Fulkersona sposób wyznaczania ścieżki powiększającej jest dowolny.
Ten artykuł opisuje pewną modyfikację algorytmu opartego na programowaniu dynamicznym rozwiązującego problem wydawania reszty. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego. Algorytm zaproponował J.W. Wright w pracy The Change-Making Problem (link w bibliografii).