Binaryzacja

Obrazy w odcieniach szarości są łatwiejsze w analizie niż te posiadające trzy oddzielne kanały (obrazy kolorowe). W obrazach w odcieniach szarości kolor każdego piksela zapisywany jest na 8 bitach.

W obrazie binarnym każdy element jest zapisywany za pomocą 1 bitu (czarny lub biały piksel). Obrazy binarne są tworzone za pomocą binaryzacji (z ang. thresholding). A mianowicie wyznaczamy próby podziału (the threshold) i wszystkie elementy poniżej pewnego progu są zamieniane na 0, a powyżej na 255. Często się używa przeskalowanych kolorów i w takiej sytuacji próg należy do przedziału [0,1], a wartości są zamieniane na zero lub jedynkę w zależności od poziomu progu. 

Algorytm

Input: Image $f$ of size $m,n$, threshold  $T$
for $i=1$ to $m$ do
  for $j=1$ to $n$ do
    if  $f(i,j) > T$ do
      $f(i,j) \leftarrow 1$
    else
      $f(i,j) \leftarrow 0$
  end for
end for

Jedną z najbardziej efektywnych metod implementacji binaryzacji jest skorzystanie z LUT (Lookup Table).

    

Ilustracja. Wynik binaryzacji obrazu Leny z różnymi progami (100,110,120,130,140).

Kod do binaryzacji z zadanym progiem (OpenCV (C++)). Jak zmienia się obraz dla różnych parametrów binaryzacji można prześledzić za pomocą: OpenCV (C++).

Prawdopodobnie najczęściej rozważanym problemem w kontekście binaryzacji jest zagadnienie odseparowania pierwszego planu od tła. Jeżeli obraz jest zaciemniony lub elementy nie są wyraźnie odseparowane, zagadnienie to jest bardzo trudne, a czasami wręcz niemożliwe. Poniższy przykład prezentuje obraz (num.jpg) oraz jego histogram. Jak widzimy ciężko jest dobrać idealny próg binaryzacji (OpenCV (C++)):

  

Ilustracja. Oryginalny obraz oraz binaryzacja z progiem $T=116$.

Ilustracja. Histogram dali obrazu powyżej.

Istnieje wiele technik, które starają się dobrać odpowiedni próg. 

W dalszej części tego rozdziału będziemy zakładać, że rozważamy tylko obrazy w odcieniach szarości $f(i,j)$. Ponadto zakładamy, że mamy histogram zbudowany zgodnie ze wzorem:

\[ h(x) = \sum_{i,j} \left\{ \begin{array}{ll} 1 & \textrm{gdy $f(i,j)=x$}\\ 0 & \textrm{gdy $f(i,j) \neq x$} \end{array} \right. \].

Program będziemy traktować jako gęstość rozkładu prawdopodobieństwa, czyli:

\[ p(x) = \frac{h(x)}{ \sum_{i=0}^{255} h(i) }. \]

Histogram dwumodalny

Jeśli założymy, że histogram jest dwumodalny (elementy tła wchodzą w skład jednej składowej, a pierwszego planu w skład drugiej) to możemy przyjąć, że histogram posiada dwa główne piki. Następnie, aby znaleźć próg możemy po prostu patrzeć na doliny histogramu (minimalna wartość pomiędzy szczytami / modami). 

Przyglądając się histogramowi zaprezentowanemu na powyższej ilustracji można zauważyć, że jest on właśnie dwumodalny. Niemniej jednak jego kształt nie jest jednolity - istnieje wiele lokalnych minimów i maksimów. W konsekwencji znalezienie optymalnego progu (doliny między modami) jest trudne.

Istnieje kilka metod rozwiązania tego problemu. Możemy wygładzić histogram za pomocą średniej ruchomej. Innym sposobem jest rozważanie szerszych binów, co da podobny efekt wygładzenia histogramu. Możemy również pominąć wszystkie punkty o małych wartościach.

Niestety takie podejścia mają tendencję do przesuwania faktycznego progu binaryzacji. W dalszej części tego rozdziału omówimy kilka podejść, które używają pewnego / nie zmienionego histogramu

Optymalny thresholding

Technika optymalnego podziału działa dość dobrze pod warunkiem, że mody są dobrze odseparowane, a szumy w histogramie są niewielkie. Jeżeli te dwa warunki nie są spełnione, to wynik binaryzacji tą metodą nie jest optymalny.

Rozważmy dwie gęstości rozkładów normalnych, które będą reprezentować dwie mody w histogramie oraz ich sumę (patrz ilustracja poniżej).

W takim przypadku optymalny podział jest reprezentowany poprzez miejsce przecięcia się dwóch gęstości rozkładów normalnych (lewa pionowa linia na powyższej ilustracji). Natomiast rozważając model składający się  z dwóch rozkładów normalnych zachodzących na siebie jesteśmy w stanie zlokalizować dolinę, która się tworzy między modami. Jest ona troszkę przesunięta w stosunku do optymalnego podziału.

Jeżeli modelujemy histogram za pomocą dwóch rozkładów normalnych, które się przecinają, to możemy użyć metody optymalnego podziału. Jest to metoda iteracyjna, która zakłada istnienie dwóch komponentów $b$ -- becgroung oraz $f$ -- foregrand. W każdej iteracji $t$ będziemy potrzebować opisu klas w zależności od obecnego podziału $T^t$:

\[ w_{b}(T^t) = \sum_{i=0}^{T^t-1} p(i), \qquad  \mu_{b}(T^t) = \sum_{i=0}^{T^t-1}  p(i) \frac{i}{w_{b}(T^t)}, \]

\[ w_{f}(T^t) = \sum_{i=T^t}^{255} p(i) = 1 − w_b(T^t) , \qquad  \mu_{f}(T^t) = \sum_{i=T^t}^{255}  p(i) \frac{i}{w_{b}(T^t)}, \]

Teraz możemy podać pseudokod

Set $t = 0$, $T^t = $ some initial threshold value
repeat 
    compute average values
    $\mu_{b}(T^t)$, $\mu_{b}(T^t)$  
    update the threshold 
    $T^{t+1} =\frac{\mu_{b}(T^t) + \mu_{f}(T^t)}{2}$
until $T^t+1 = T^t$

Binaryzacja Otsu

Metoda optymalnego podziału zakłada, że histogram jest sumą dwóch rozkładów normalnych. Często nie jest to prawdą co powoduje, że ta metoda nie działa zbyt dobrze.

Innym algorytmem podziału jest metoda Otsu, która wyznacza próg tak by zminimalizować wariancję dwóch powstałych klas.

Algorytm Otsu sprawdza wszystkie możliwe podziały i wybiera ten, który minimalizuje wariancję wewnątrz klasową:

\[ \sigma_{w}(T) = w_{f}(T) \sigma_{f}^2(T) + w_{b}(T) \sigma_{b}^2(T) \],

gdzie:

\[ w_{b}(T) = \sum_{i=0}^{T^t-1} p(i), \qquad  \sigma_{b}(T) = \sum_{i=0}^{T-1}  p(i) \frac{ (i - \mu_{f} )^2 }{w_{b}(T)} \qquad \mu_{b}(T) = \sum_{i=0}^{T-1}  p(i) \frac{i}{w_{b}(T)}, \]

\[ w_{f}(T) = \sum_{i=T}^{255} p(i), \qquad  \sigma_{f}(T) = \sum_{i=T}^{255}  p(i) \frac{ (i - \mu_{f} )^2 }{w_{b}(T)}, \qquad  \mu_{f}(T) = \sum_{i=T}^{255}  p(i) \frac{i}{w_{b}(T)}. \]

Łatwo można zauważyć, że minimalizowanie wariancji wewnątrz klasowej jest równoważne maksymalizacji wariancji międzyklasowej:

\[ \sigma^2_{N}(T) = w_{f}(T) ( \mu_{f}(T) - \mu )^2 + w_{b}(T) ( \mu_{b}(T) - \mu )^2  \]

gdzie: $ \mu =  w_{f}(T) \mu_{f}(T) + w_{b}(T)  \mu_{b}(T) $.

Poprzez proste przeliczenia możemy uzyskać prostszą wersję wzoru na wariancję międzyklasową:

\[ \sigma_{B}(T) = w_{f}(T) w_{b}(T) (\mu_{f}(T) - \mu_{b}(T))^2 \].

Jak widzimy, wynik binaryzacji metodą Otsu uzyskujemy poprzez analizę średnich ważonych w komponentach.

  

Ilustracja. Wynik binaryzacji metodą Otsu.

Kod programu do binaryzacji Otsu Open CV (C++).

Adaptive Thresholding

We wszystkich dotychczasowych przykładach wykorzystywaliśmy globalny próg do binaryzacji (pojedynczy próg został zastosowany do wszystkich punktów obrazu). W niektórych sytuacjach można znacząco poprawić wyniki przy użyciu wielu progów.

Rozważmy sobie zdjęcie gazeta.jpg. Jak widzimy globalny próg jest daleki od optymalnego.

  

Ilustracja. Wynik algorytmu Otsu.

Zacznijmy od opisania lokalnej binaryzacji w swojej klasycznej postaci. Najczęściej opisuje się ją w trzech krokach:

  1. Podziel obraz na rozłączne kratki $8 \times 8$ pikseli,
  2. W każdej kratce wyznacz próg binaryzacji (np. za pomocą Otsu),
  3. Dla każdego piksela użyj lokalnego progu, który jest przybliżony za pomocą 4 najbliższych progów.

Powyższy algorytm jest rzadko stosowany. Większą popularność zyskała metoda Bernsena. W każdym punkcie rozważa się otoczenie o zadanej wielkości (jak przy filtrach). Próg binaryzacji jest ustalany jako średnia z danych lub średnia ważona z wagami Gaussowskimi (można również stosować inne statystyki np. medianę). 

Czasami stosuje się metodę mieszaną (lokalnej binaryzacji z globalną). Progowanie mieszane przebiega podobnie jak progowanie lokalne (metoda Bernsena), z tym że jeśli średnia lub mediana lokalna dla danego piksela odbiega o więcej niż ustalony próg (program pobiera tą wartość jako parametr) od wartości globalnej (wyznaczoną za pomocą Otsu), to za próg przyjmuje się wartość globalną, a nie lokalną.

  

Ilustracja. Wynik algorytmu lokalnego progowania przy użyciu średniej oraz średniej ważonej.

Powyższe obrazki można uzyskać za pomocą programu OpcenCV (C++).

Jako parametr w powyższej metodzie można podać tolerancję progu, czyli o ile może być odległy próg od wartości średniej w oknie. Zależność między tą odległością, a wynikami binaryzacji (OpenCV (C++)) prezentuje poniższa ilustracja. 

   

   

Binaryzacja z podwójnym progiem

Jest wiele różnych podejść do binaryzacji. Jedną z nich jest tak zwana binaryzacja z podwójnym progiem, która pozwala wyodrębnić zakres między dwoma progami binaryzacji $T_1$, $T_2$.

Input: Image $f$ of size $m,n$, thresholds  $T_1$, $T_2$
for $i=1$ to $m$ do
  for $j=1$ to $n$ do
    if  $f(i,j) > T_1$ && $f(i,j) < T_2$ do
      $f(i,j) \leftarrow 1$
    else
      $f(i,j) \leftarrow 0$
  end for
end for

Metodę tą można użyć do wyznaczenia konturów.

  

Lustracja. Wynik binaryzacja z podwójnym progiem [110,126], który dobieramy na podstawie histogramu.

Powyższe obrazy można uzyskać za pomocą kodu OpenCV (C++).

Semi binaryzacja

Jeszcze innym podejściem jest tak zwana semi binaryzacja, która usuwa tło ale zachowuje odcienie szarości na pierwszoplanowych obiektach.

Input: Image $f$ of size $m,n$, threshold  $T$
for $i=1$ to $m$ do
  for $j=1$ to $n$ do
    if  $f(i,j) > T$ do
      $f(i,j) \leftarrow f(i,j) $
    else
      $ f(i,j) \leftarrow 0 $
  end for
end for

Efekt semi binaryzacji można otrzymać za pomocą programu OpenCV (C++).

  

Ilustracja. Wynik semi binaryzacji z progiem 115.