Szukaj

Metoda Otsu – algorytm służący do binaryzacji obrazu, czyli przekształcenia obrazu w odcieniach szarości do obrazu binarnego. Metoda ta realizuje progowanie globalne – dla całego obrazu wyznaczany jest jeden próg jasności, a następnie wszystkim pikselom jaśniejszym od tego progu przypisywana jest jedna wartość, a ciemniejszym druga.

Algorytm jest oparty na analizie histogramu. Przygotowanie histogramu polega na zliczeniu pikseli w każdym możliwym odcieniu (zazwyczaj liczba odcieni wynosi 256, gdyż tyle da się zakodować w jednym bajcie). Następnie należy sprawdzić każdy możliwy próg jasności i wybrać ten, dla którego wariancja międzyklasowa jest największa (lub suma ważona wariancji wewnątrzklasowych jest najmniejsza).

Jeśli obrazem wejściowym jest obraz kolorowy, można go łatwo sprowadzić do odcieni szarości. W przypadku kolorów zakodowanych w RGB najprostszym rozwiązaniem jest uśrednienie dla każdego piksela wartości wszystkich trzech kanałów.

Wzory

Wprowadźmy następujące oznaczenia: niech i oznacza barwę piksela, n_i liczbę pikseli w danym kolorze, a L liczbę kolorów. Próg jasności oznaczmy jako k. Całkowita liczba pikseli obrazu (N) oraz liczby pikseli w poszczególnych klasach (N₀, N₁) będą wyrażały się wzorami:

$$N = ∑↙{i=0}↖{L-1} n_i, N_0 = ∑↙{i=0}↖{k-1} n_i, N_1 = ∑↙{i=k}↖{L-1} n_i.$$

W analogiczny sposób możemy obliczyć sumę wartości pikseli, zarówno w całym obrazie (S), jak i w poszczególnych klasach (S₀, S₁).

$$S = ∑↙{i=0}↖{L-1} n_i i , N_0 = ∑↙{i=0}↖{k-1} n_i i , N_1 = ∑↙{i=k}↖{L-1} n_i i .$$

Teraz możemy łatwo obliczyć średnią wartość piksela w całym obrazie (X) oraz w poszczególnych klasach (X₀, X₁).

$$ X = S / N , X_0 = S_0 / N_0 , X_1 = S_1 / N_1 .$$

Wariancja jest miarą rozproszenia elementów w zbiorze. Oblicza się ją jako średnią kwadratów różnic wartości od średniej. W naszym przypadku wariancje wewnątrz obu klas oblicza się następująco:

$$ W_0 = 1 / N_0 ∑↙{i=0}↖{k-1} ({X_0-i})^2 n_i , W_1 = 1 / N_1 ∑↙{i=k}↖{L-1} ({X_1-i)}^2 n_i .$$

Mając te wartości można wyliczyć sumę ważoną wariancji międzyklasowych:

$$ W_W = N_0 / N W_0 + N_1 / N W_1 .$$

Próg jasności należy dobrać tak, aby wartość W_W była jak najmniejsza. Wykazano jednak, że zamiast tego można obliczać wariancję międzyklasową, co wymaga mniejszego nakładu obliczeń. W takim przypadku próg należy dobrać tak, żeby wartość ta była jak największa. Wariancję międzyklasową wyraża się następującym wzorem:

$$ W_M = N_0 / N (X-X_0)^2 + N_1 / N (X-X_1)^2 .$$

Wzór ten można sprowadzić do prostszej postaci:

$$ W_M = {N_0 N_1} / N^2 (X_0-X_1)^2 .$$

Dowody

Poniżej przedstawiono dowody na wymienność powyższych wzorów. Ich znajomość nie jest konieczna do prawidłowej implementacji – przedstawiono je z myślą o osobach chcących dokładniej zrozumieć, skąd się wzięły wzory przedstawione powyżej.

Jak wspomniano, znalezienie minimalnej sumy ważonej wariancji wewnątrzklasowych (W_W) i znalezienie maksymalnej wariancji międzyklasowej (W_M) da taki sam rezultat. Wynika to z faktu, że wariancja całego zbioru pikseli jest sumą obu tych wartości:

$$ W = W_M + W_W .$$

Wariancja całego zbioru (W) nie zależy od przyjętego progu. Z tego w oczywisty sposób wynika, że im mniejsze jest W_M, tym większe musi być W_W. Wariancja całego zbioru wyraża się następującym wzorem:

$$ W = 1 / N ∑↙{i=0}↖{L-1} ({X-i})^2 n_i .$$

Można sprowadzić ten wzór do postaci:

$$ W = 1 / N ∑↙{i=0}↖{L-1} ({X^2 - 2 X i + i^2}) n_i = 1/N [{ X^2 ∑↙{i=0}↖{L-1} n_i - 2 X ∑↙{i=0}↖{L-1} i n_i + ∑↙{i=0}↖{L-1} i^2 n_i }] = $$ $$ = 1/N [{ X^2 N - 2 X S + ∑↙{i=0}↖{L-1} i^2 n_i }] = 1/N [{ S X - 2 X S + ∑↙{i=0}↖{L-1} i^2 n_i }] = 1/N [{ ∑↙{i=0}↖{L-1} i^2 n_i - S X }].$$

Aby udowodnić prawdziwość wzoru $W = W_M + W_W$, należy sprowadzić do tej samej postaci również prawą stronę wzoru. Można to zrobić następująco:

$$ W_M + W_W = N_0 / N (X-X_0)^2 + N_1 / N (X-X_1)^2 + N_0 / N W_0 + N_1 / N W_1 = 1/N [{ N_0 (X-X_0)^2 + N_0 W_0 + N_1 (X-X_0)^2 + N_1 W_1 }] = $$ $$ = 1/N [{ N_0 (X^2 - 2 X X_0 + X_0^2) + N_0 / N_0 ({ ∑↙{i=0}↖{k-1} i^2 n_i - X_0 S_0 }) + N_1 (X^2 - 2 X X_1 + X_1^2) + N_1 / N_1 ({ ∑↙{i=k}↖{L-1} i^2 n_i - X_1 S_1 }) }] = $$ $$ = 1/N [{ N_0 X^2 - 2 N_0 X X_0 + N_0 X_0^2 - X_0 S_0 + N_1 X^2 - 2 N_1 X X_1 + N_1 X_1^2 - X_1 S_1 + ∑↙{i=k}↖{L-1} i^2 n_i}] = $$ $$ = 1/N [{ (N_0 + N_1) X^2 - 2 S_0 X + S_0 X_0 - X_0 S_0 - 2 S_1 X + S_1 X_1 - X_1 S_1 + ∑↙{i=k}↖{L-1} i^2 n_i}] = $$ $$ = 1/N [{ N X^2 - 2 X (S_0 + S_1) + ∑↙{i=k}↖{L-1} i^2 n_i}] = 1/N [{ S X - 2 X S + ∑↙{i=k}↖{L-1} i^2 n_i}] = 1/N [{ ∑↙{i=k}↖{L-1} i^2 n_i - S X }] .$$

Możemy udowodnić również, że oba przedstawione wzory na wariancję międzyklasową są równoważne. Dowód ten wygląda następująco:

$$ W_M = N_0 / N (X-X_0)^2 + N_1 / N (X-X_1)^2 = N_0 / N (N_0 / N X_0 + N_1 / N X_1 - X_0)^2 + N_1 / N (N_0 / N X_0 + N_1 / N X_1 - X_0)^2 = $$ $$ = N_0 / N (X_0 (N_0 / N - 1) + N_1 / N X_1)^2 + N_1 / N (X_1 (N_1 / N - 1) + N_0 / N X_0)^2 = N_0 / N ({N_0 - N} / N X_0 + N_1 / N X_1)^2 + N_1 / N ({N_1 - N} / N X_1 + N_0 / N X_0)^2 = $$ $$ = N_0 / N (-N_1 / N X_0 + N_1 / N X_1)^2 + N_1 / N (-N_0 / N X_1 + N_0 / N X_0)^2 = N_0 / N (N_1 / N)^2 (-X_0 + X_1)^2 + N_1 / N (N_0 / N)^2 (-X_1 + X_0)^2 = $$ $$ = (N_0 / N (N_1 / N)^2 + N_1 / N (N_0 / N)^2) (X_0 - X_1)^2 = {N_0 N_1^2 + N_1 N_0^2} / N^3 (X_0 - X_1)^2 = {N_0 N_1 (N_0 + N_1)} / N^3 (X_0 - X_1)^2 = $$ $$ = {N_0 N_1 N} / N^3 (X_0 - X_1)^2 = {N_0 N_1} / N^2 (X_0 - X_1)^2 .$$

Bibliografia

• Nobuyuki Otsu, A Threshold Selection Method from Gray-Level Histograms, IEEE Transactions on Systems, Man, and Cybernetics, Volume 9, Issue 1, 1979, s. 62-66, DOI: 10.1109/TSMC.1979.4310076.