Metoda Otsu

REKLAMA

English 4 IT. Praktyczny kurs języka angielskiego dla specjalistów IT i nie tylko
−35%25,93 zł
PHP 7. Algorytmy i struktury danych
−35%38,35 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 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ść

Sortowanie przez wstawianie (ang. insertion sort) – prosty algorytm sortowania polegający na wstawianiu kolejnych elementów ciągu we właściwe miejsca. Złożoności czasowa algorytmu wynosi O(n2). Jest to algorytm realizujący metodę przyrostową.

→ Czytaj całość

Ten artykuł opisuje algorytm zachłanny rozwiązujący problem wydawania reszty. Algorytm ten polega na wybieraniu zawsze największej dostępnej monety, tzn. takiej, która nie jest większa od kwoty pozostałej do wydania.

Algorytm nie zawsze znajduje rozwiązanie optymalne. Przykładowo, dla zbioru nominałów {1, 3, 4} i kwoty 6 algorytm użyje najpierw monety o nominale 4 (pozostaje do wydania kwota 2), potem monety o nominale 1 (pozostaje kwota 1) i jeszcze raz monety o nominale 1. Łącznie algorytm użyje więc trzech monet, podczas gdy rozwiązanie optymalne wymaga użycia tylko dwóch (dwie monety o nominale 3).

→ Czytaj całość
Polityka prywatnościKontakt