Metoda Otsu

REKLAMA

Kwalifikacja INF.03. Tworzenie i administrowanie stronami i aplikacjami internetowymi oraz bazami danych. Część 1. Projektowanie stron internetowych. Podręcznik do nauki zawodu technik informatyk i technik programista
−25%37,42 zł
C++. Algorytmy i struktury danych
103,95 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: 3.

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

REKLAMA

Zobacz też

Algorytm heurystyczny, heurystyka – algorytm niedający (w ogólnym przypadku) gwarancji znalezienia rozwiązania optymalnego, umożliwiający jednak znalezienie rozwiązania dość dobrego w rozsądnym czasie. Algorytmy tego typu używane są w takich problemach obliczeniowych, gdzie znalezienie rozwiązania optymalnego ma zbyt dużą złożoność obliczeniową (w szczególności są to problemy NP-trudne) lub w ogóle nie jest możliwe. Metody heurystyczne zaliczają się do sztucznej inteligencji.

Pojęcie algorytmów heurystycznych jest bardzo szerokie, dotyczy ono różnych technik projektowania algorytmów. Wiele heurystyk wykorzystuje losowość, inne zaś są deterministyczne (wówczas dla takich samych danych wejściowych algorytm zawsze zwróci ten sam wynik).

Ogólny algorytm heurystyczny (opisujący samą ideę poszukiwań) bywa określany w literaturze jako metaheurystyka. Zgodnie z tym nazewnictwem, metaheurystyką jest np. algorytm zachłanny (jako ogólna idea), zaś heurystyką jest np. algorytm najbliższego sąsiada (jako zastosowanie idei algorytmu zachłannego do konkretnego problemu).

Przykładowe techniki konstruowania algorytmów heurystycznych to:

→ Czytaj całość

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ść

Powtarzalny algorytm najbliższego sąsiada (ang. repetitive nearest neighbour algorithm, w skrócie RNN) – algorytm służący do rozwiązywania problemu komiwojażera korzystający z algorytmu najbliższego sąsiada.

Algorytm polega na wielokrotnym wykonaniu algorytmu najbliższego sąsiada w taki sposób, aby każdy wierzchołek raz był wierzchołkiem początkowym. Następnie algorytm zwraca najlepsze spośród otrzymanych rozwiązań.

Dla grafu pełnego algorytm ma złożoność O(n3), gdzie n jest liczbą wierzchołków. W trakcie wykonywania algorytmu RNN n razy zostanie wykonany algorytm najbliższego sąsiada, który ma złożoność czasową O(n2).

Algorytm RNN nie daje gwarancji znalezienia rozwiązania optymalnego. W odróżnieniu od algorytmu najbliższego sąsiada daje jednak gwarancję, że zwróci rozwiązanie co najmniej tak dobre, jak n/2-1 innych rozwiązań (dowód i więcej informacji na ten temat znajduje się w pracy podanej w bibliografii).

→ Czytaj całość
Polityka prywatnościKontakt