Składowe spójne

W analizie obrazu często musimy analizować obiekty / kształty na obrazie. W konsekwencji dokonujemy progowania, a następnie obraz binarny oczyszczamy za pomocą operacji morfologicznych. Po tych operacjach możemy znaleźć obiekty na zdjęciu. Jest wiele podejść do tego zagadnienia. Jednym z nich jest znalezienie obszarów pikseli, które są koło siebie, czyli znaleźć składowe spójne.

Jednym z najprostszych algorytmów wyszukania składowych spójnych jest metoda polegająca na podwójnym labelowaniu danych należących do obiektu. Zakładamy, że wszystkie elementy na binarnym obrazie, które maja kolor czarny (przyjmują wartość $0$) należą do tła. Będziemy szukać składowych spójnych wśród elementów należących do obiektu (biały kolor lub równoważnie wartość $1$).

Należy zacząć od zdefiniowania elementów / pikseli, które są blisko tego, który rozważamy. Najczęściej używa się dwóch podejść:

  1. sąsiedztwo $4$-elementowe - gdzie tylko cztery piksele: północ, południe, wschód i zachód traktowane są jako elementy w sąsiedztwie,
  2. sąsiedztwo $8$-elementowe - gdzie wszystkie piksele dotykające danego są traktowane jako elementy z otoczenia.

Ilustracja. Piksele uznawane za znajdujące się w otoczeniu (zaznaczone na szaro).
w dwóch przypadkach sąsiedztwa $4$-elementowe oraz sąsiedztwa $8$-elementowe.

Algorytm wyszukiwania komponentów spójnych można przedstawić w następujący sposób:

  1. Przejdź po całym obrazie i w każdym pikselu wykonaj operację:
    Dla każdego niezerowego piksela wykonaj:
        Jeżeli wszystkie poprzednie piksele otoczenia (patrz Ilustracja poniżej) są pikselami tła (wartość koloru 0)
            Przypisz nowy numer klasy (label)
        w innym przypadku
            Wybierz dowolny numer klasy z pośród klas, do których należą sąsiednie piksele
            Jeżeli jakiś z sąsiednich pikseli posiada inny 
                Zapisz połączenie między tymi klasami

  2. Przejdź po obrazie drugi raz i połącz obiekty / klasy, które zostały zapisane jako połączone.

W czasie przechodzenia po obrazie musimy analizować wszystkie poprzednie piksele otoczenia, czyli takie, które są w otoczeniu (jednego z typów: sąsiedztwa $4$-elementowe oraz sąsiedztwa $8$-elementowe), które zostały odwiedzone podczas przechodzenia obrazu, wiersz po wierszu od lewej strony. Poniższa Ilustracja prezentuje taka sytuację.

Ilustracja. Poprzednie punkty otoczenia podczas przechodzenia obrazu wiersz po wierszu 
od lewej strony dla odpowiednio sąsiedztwa $8$-elementowe oraz sąsiedztwa $4$-elementowe

Wynik działania powyższej metody krok po kroku przedstawiony jest na poniższej ilustracji.

Ilustracja. Od prawej odpowiednio mamy oryginalny obraz, efekt uzyskany po przejściu pierwszą pętlą, a następnie efekt ostatniego przejścia algorytmu.

Wynik działania algorytmu znajdowania składowych spójnych zaprezentujemy na obrazie circles.png.

  

Ilustracja. Wynik algorytmu wyszukiwania komponentów spójnych.