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: 0.
- Algorytm Zhanga-Suena
- Metoda Otsu
Dodano: 2 lutego 2019 15:18, ostatnia edycja: 21 kwietnia 2020 17:38.
Zobacz też
Metoda przyrostowa – technika projektowania algorytmów polegająca na dodawaniu do rozwiązania kolejnych elementów z danych wejściowych. Przykładem algorytmu opartego na tej metodzie jest sortowanie przez wstawianie, gdzie kolejne elementy są wstawiane do posortowanej części tablicy.
Jest to metoda prosta, jednak sprawdza się tylko dla niektórych problemów obliczeniowych.
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).
Programowanie dynamiczne – technika projektowania algorytmów polegająca na rozwiązywaniu podproblemów i zapamiętywaniu ich wyników. W technice tej, podobnie jak w metodzie dziel i zwyciężaj, problem dzielony jest na mniejsze podproblemy. Wyniki rozwiązywania podproblemów są jednak zapisywane w tabeli, dzięki czemu w przypadku natrafienia na ten sam podproblem nie trzeba go ponownie rozwiązywać.
Wykorzystując programowanie dynamiczne można zastosować metodę zstępującą z zapamiętywaniem lub metodę wstępującą.
- Metoda zstępująca z zapamiętywaniem polega na rekurencyjnym wywoływaniu funkcji z zapamiętywaniem wyników. Metoda ta jest podobna do metody dziel i zwyciężaj – różni się od niej tym, że jeśli rozwiązanie danego problemu jest już w tabeli z wynikami, to należy je po prostu stamtąd odczytać.
- Metoda wstępująca polega na rozwiązywaniu wszystkich możliwych podproblemów, zaczynając od tych o najmniejszym rozmiarze. Wówczas w momencie rozwiązywania podproblemu na pewno są już dostępne rozwiązania jego podproblemów. W tym podejściu nie zużywa się pamięci na rekurencyjne wywołania funkcji. Może się jednak okazać, że część podproblemów została rozwiązana nadmiarowo (nie były one potrzebne do rozwiązania głównego problemu).