Metoda Otsu

REKLAMA Algorytmy. Ćwiczenia
34,90 zł
Jak naprawić sprzęt elektroniczny. Poradnik dla nieelektronika. Wydanie II
−40%29,40 zł
Spring w akcji. Wydanie V
−30%62,30 zł
Opus magnum C++. Misja w nadprzestrzeń C++14/17. Tom 4
−40%29,40 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: -1 Tak Nie
Liczba głosów: 1.

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

REKLAMA

Zobacz też

Notacja dużego O – notacja przedstawiająca asymptotyczne tempo wzrostu, wykorzystywana do zapisywania złożoności obliczeniowej algorytmu. Za pomocą tej notacji zapisywany jest rząd wielkości funkcji wyrażającej liczbę operacji dominujących (w przypadku złożoności czasowej) lub rozmiar wymaganej pamięci (w przypadku złożoności pamięciowej) w zależności od liczby danych wejściowych.

Wykorzystując notację dużego O nie podajemy dokładnego wzoru funkcji, a jedynie jej najbardziej znaczący składnik, w dodatku z pominięciem stałego współczynnika. Przykładowo, funkcję postaci f(n)=5n2+20n+100 możemy zapisać jako O(n2). Zakładamy bowiem, że dla dostatecznie dużych n wpływ pomijanych elementów jest znikomy. Choć oczywiście dla małych n może się zdarzyć, że funkcja o gorszej złożoności będzie się wykonywała szybciej.

Weźmy dla przykładu funkcje f(n) = 1000n+2000 i g(n) = n2. Choć pierwsza funkcja ma pozornie bardzo duże stałe współczynniki, to dla n ≥ 1002 będzie ona przyjmowała wartości mniejsze. Im większe n, tym ta różnica będzie wyraźniejsza. Dla n = 10000 (w przypadku danych przetwarzanych komputerowo nie jest to wielka wartość) f(n) = 10002000 (ok. 10 mln), a g(n) = 100000000 (100 mln), czyli blisko 10 razy więcej.

Możliwe jest również wykorzystanie notacji dużego O dla funkcji wielu zmiennych. Wówczas zapis może wyglądać tak: O(v2e). Znajduje to zastosowanie np. dla algorytmów operujących na grafach, gdzie złożoność zależy zarówno od liczby wierzchołków, jak i liczby krawędzi w grafie.

→ Czytaj całość

Algorytm Helda-Karpa (czasami określany jako algorytm Bellmana-Helda-Karpa) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm dokładny oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n22n) i złożoność pamięciową O(n2n). Jest to co prawda złożoność gorsza od wielomianowej, ale algorytm ten jest znacznie lepszy od algorytmu sprawdzającego wszystkie warianty (złożoność czasowa O(n!)).

→ Czytaj całość

Algorytm genetycznymetaheurystyka inspirowana biologiczną ewolucją.

Pojęcie algorytmu genetycznego nie jest powiązane z żadnym konkretnym problemem obliczeniowym, algorytm ten może być wykorzystywany do rozwiązywania różnych problemów. Algorytm genetyczny nie próbuje rozwiązywać problemu w sposób analityczny, ale próbuje uzyskać jak najlepsze rozwiązania poprzez wybieranie jak najlepszych cech rozwiązań z określonej puli. Implementując algorytm genetyczny należy przedstawić potencjalne rozwiązanie problemu w postaci jakiejś struktury danych, a następnie zdefiniować operacje krzyżowania, mutacji i selekcji. Zakładamy, że z każdym kolejnym pokoleniem rozwiązania występujące w populacji będą coraz lepsze.

→ Czytaj całość
Polityka prywatnościKontakt