Metoda Otsu

REKLAMA Algorytmy. Ćwiczenia
34,90 zł
Uczenie maszynowe z użyciem Scikit-Learn i TensorFlow
89,00 zł
UX w projektowaniu witryn internetowych
−30%38,43 zł
JavaScript i jQuery. Interaktywne strony WWW dla każdego. Podręcznik Front-End Developera
99,00 zł

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, ni 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 (N0, N1) 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 (S0, S1).

$$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 (X0, X1).

$$ 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ść WW 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 (WW) i znalezienie maksymalnej wariancji międzyklasowej (WM) 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 WM, tym większe musi być WW. 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.
Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 5 lutego 2019 17:50, ostatnia edycja: 6 lutego 2019 20:00.

REKLAMA

Zobacz też

Dziel i zwyciężaj (ang. divide and conquer) – technika projektowania algorytmów polegająca na podejściu rekurencyjnym. W technice tej problem dzielony jest na mniejsze podproblemy, te podproblemy na jeszcze mniejsze podproblemy, aż dojdzie się do przypadków trywialnych (np. posortowanie jednoelementowej tablicy, obliczenie silni z 1).

Jeśli rozpatrywany problem wymaga podzielenia na podproblemy, jest on określany jako przypadek rekurencyjny. Jeśli mamy do czynienia z przypadkiem trywialnym, jest to przypadek bazowy. Tworząc algorytm wykorzystujący metodę dziel i zwyciężaj musimy ustalić:

  • Jak rozwiązać przypadek bazowy (trywialny).
  • Jak wyznaczyć rozwiązanie problemu, mając dostępne rozwiązania podproblemów.

Przykładem algorytmu opartego na tej metodzie jest sortowanie przez scalanie.

→ Czytaj całość

Algorytm Johnsona – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Algorytm wykorzystuje algorytm Dijkstry i algorytm Bellmana-Forda. Dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli.

Złożoność czasowa algorytmu (jeśli algorytm Dijkstry zostanie zaimplementowany z wykorzystaniem kopca Fibonacciego) to O(n2log n + en), gdzie n jest liczbą wierzchołków, a e jest liczbą krawędzi. Dla grafów rzadkich (ze stosunkowo małą liczbą krawędzi) jest to złożoność lepsza, niż złożoność algorytmu Floyda-Warshalla.

→ Czytaj całość
Algorytm najbliższego sąsiada (ang. nearest neighbour algorithm, w skrócie NN) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm wykorzystujący strategię zachłanną.
→ Czytaj całość
Polityka prywatnościKontakt