Otsusova metoda - Otsus method - Wikipedia

Příklad obrázku s prahem pomocí Otsuova algoritmu

Originální obrázek

v počítačové vidění a zpracování obrazu, Otsuova metoda, pojmenoval podle Nobuyuki Otsu (大津展之, Ōtsu Nobuyuki), se používá k provádění automatického obrazu prahování.^[1] V nejjednodušší formě algoritmus vrací jedinou prahovou hodnotu intenzity, která odděluje pixely do dvou tříd, popředí a pozadí. Tato prahová hodnota je určena minimalizací rozptylu intenzity uvnitř třídy nebo ekvivalentně maximalizací rozptylu mezi třídami.^[2] Otsuova metoda je jednorozměrný diskrétní analog Fisherova diskriminační analýza, je spojen s Jenksova metoda optimalizace, a odpovídá celosvětově optimálnímu k-prostředky^[3] provedeno na histogramu intenzity. Rozšíření na víceúrovňové prahování bylo popsáno v původním dokumentu,^[2] a od té doby byly navrženy výpočetně efektivní implementace.^[4]^[5]

Otsuova metoda

Vizualizace metody Otsu

Algoritmus vyčerpávajícím způsobem hledá prahovou hodnotu, která minimalizuje odchylku uvnitř třídy, definovanou jako vážený součet odchylek dvou tříd:

{ displaystyle sigma _ {w} ^ {2} (t) = omega _ {0} (t) sigma _ {0} ^ {2} (t) + omega _ {1} (t) sigma _ {1} ^ {2} (t)}

Závaží ${ displaystyle omega _ {0}}$ a ${ displaystyle omega _ {1}}$ jsou pravděpodobnosti dvou tříd oddělených prahovou hodnotou ${ displaystyle t}$ ,a ${ displaystyle sigma _ {0} ^ {2}}$ a ${ displaystyle sigma _ {1} ^ {2}}$ jsou odchylky těchto dvou tříd.

Pravděpodobnost třídy ${ displaystyle omega _ {0,1} (t)}$ se počítá z ${ displaystyle L}$ koše histogramu:

{ displaystyle { begin {aligned} omega _ {0} (t) & = sum _ {i = 0} ^ {t-1} p (i) [4pt] omega _ {1} ( t) & = sum _ {i = t} ^ {L-1} p (i) end {zarovnáno}}}

Pro 2 třídy je minimalizace rozptylu uvnitř třídy ekvivalentní maximalizaci rozptylu mezi třídami:^[2]

{ displaystyle { begin {aligned} sigma _ {b} ^ {2} (t) & = sigma ^ {2} - sigma _ {w} ^ {2} (t) = omega _ {0 } ( mu _ {0} - mu _ {T}) ^ {2} + omega _ {1} ( mu _ {1} - mu _ {T}) ^ {2} & = omega _ {0} (t) omega _ {1} (t) left [ mu _ {0} (t) - mu _ {1} (t) right) ^ {2} end { zarovnaný}}}

což je vyjádřeno pravděpodobnostmi třídy ${ displaystyle omega}$ a třídní prostředky ${ displaystyle mu}$ , kde třída znamená ${ displaystyle mu _ {0} (t)}$ , ${ displaystyle mu _ {1} (t)}$ a ${ displaystyle mu _ {T}}$ jsou:

{ displaystyle { begin {aligned} mu _ {0} (t) & = { frac { sum _ {i = 0} ^ {t-1} ip (i)} { omega _ {0} (t)}} [4pt] mu _ {1} (t) & = { frac { sum _ {i = t} ^ {L-1} ip (i)} { omega _ {1 } (t)}} mu _ {T} & = sum _ {i = 0} ^ {L-1} ip (i) end {zarovnáno}}}

Následující vztahy lze snadno ověřit:

{ displaystyle { begin {aligned} omega _ {0} mu _ {0} + omega _ {1} mu _ {1} & = mu _ {T} omega _ {0} + omega _ {1} & = 1 end {zarovnáno}}}

Pravděpodobnosti třídy a prostředky třídy lze vypočítat iterativně. Tato myšlenka přináší efektivní algoritmus.

Algoritmus

Vypočítejte histogram a pravděpodobnosti každé úrovně intenzity
Nastavit počáteční ${ displaystyle omega _ {i} (0)}$ a ${ displaystyle mu _ {i} (0)}$
Projděte všechny možné prahové hodnoty ${ displaystyle t = 1, ldots}$ ${ displaystyle t = 1, ldots}$ maximální intenzita
1. Aktualizace ${ displaystyle omega _ {i}}$ a ${ displaystyle mu _ {i}}$
2. Vypočítat ${ displaystyle sigma _ {b} ^ {2} (t)}$
Požadovaná prahová hodnota odpovídá maximu ${ displaystyle sigma _ {b} ^ {2} (t)}$

Implementace MATLAB nebo Octave

histogramCount je 256prvkový histogram obrazu ve stupních šedi s různými úrovněmi šedé (typické pro 8bitové obrázky). úroveň je prahová hodnota pro obrázek (dvojitá).

funkceúroveň =otsu(histogramCount)celkový = součet(histogramCount); % z celkového počtu pixelů v obrázku %% OTSU automatické prahováníhorní = 256;součet B. = 0;wB = 0;maximum = 0.0;součet1 = tečka(0:horní-1, histogramCount);pro ii = 1:horní    wF = celkový - wB;    -li wB > 0 && wF > 0        mF = (součet1 - součet B.) / wF;        val = wB * wF * ((součet B. / wB) - mF) * ((součet B. / wB) - mF);        -li ( val >= maximum )            úroveň = ii;            maximum = val;        konec    konec    wB = wB + histogramCount(ii);    součet B. = součet B. + (ii-1) * histogramCount(ii);koneckonec

Matlab má vestavěné funkce šedá a multithresh () v nástroji Image Processing Toolbox, které jsou implementovány metodou Otsu a metodou Multi Otsu.

Omezení

Otsuova metoda vykazuje relativně dobrý výkon, pokud lze předpokládat, že histogram má bimodální distribuci a předpokládá se, že má hluboké a ostré údolí mezi dvěma vrcholy. Pokud je však oblast objektu ve srovnání s oblastí pozadí malá, histogram již nevykazuje bimodalitu.^[6] A pokud jsou odchylky objektu a intenzity pozadí velké ve srovnání se středním rozdílem, nebo je obraz silně poškozen aditivním šumem, ostré údolí histogramu úrovně šedé se degraduje. Potom možná nesprávná prahová hodnota stanovená metodou Otsu vede k chybě segmentace. (Zde definujeme velikost objektu jako poměr plochy objektu k celé ploše obrazu a střední rozdíl jako rozdíl průměrných intenzit objektu a pozadí)

Empirické výsledky ukazují, že výkon globálních prahových technik používaných pro segmentaci objektů (včetně metody Otsu) je omezen malou velikostí objektu, malým průměrným rozdílem mezi pixely v popředí a pozadí, velkými odchylkami pixelů, které patří k objektu, a těm, které patří na pozadí, velké množství hluku atd.^[7]

Vylepšení

Byla vyvinuta různá rozšíření, která řeší omezení Otsuovy metody. Jedním z populárních rozšíření je dvourozměrná Otsuova metoda, který funguje lépe pro úlohu segmentace objektů v hlučných obrazech. Zde se porovnává hodnota intenzity daného pixelu s průměrnou intenzitou jeho bezprostředního sousedství, aby se zlepšily výsledky segmentace.^[8]

U každého pixelu se vypočítá průměrná hodnota úrovně šedé v okolí. Nechte úroveň šedé daného pixelu rozdělit na ${ displaystyle L}$ diskrétní hodnoty a průměrná úroveň šedé je také rozdělena na stejné ${ displaystyle L}$ hodnoty. Poté se vytvoří dvojice: úroveň šedé pixelu a průměr okolí ${ displaystyle (i, j)}$ . Každý pár patří jednomu z ${ displaystyle L krát L}$ možné 2-dimenzionální koše. Celkový počet výskytů (frekvence), ${ displaystyle f_ {ij}}$ , z páru ${ displaystyle (i, j)}$ , děleno celkovým počtem pixelů v obrázku ${ displaystyle N}$ , definuje hmotnostní funkci pravděpodobnosti kloubu v 2-rozměrném histogramu:

{ displaystyle P_ {ij} = { frac {f_ {ij}} {N}}, qquad sum _ {i = 0} ^ {L-1} sum _ {j = 0} ^ {L- 1} P_ {ij} = 1}

A dvourozměrná metoda Otsu je vyvinuta na základě dvourozměrného histogramu následujícím způsobem.

Pravděpodobnosti dvou tříd lze označit jako:

{ displaystyle { begin {aligned} omega _ {0} & = sum _ {i = 0} ^ {s-1} sum _ {j = 0} ^ {t-1} P_ {ij} omega _ {1} & = sum _ {i = s} ^ {L-1} sum _ {j = t} ^ {L-1} P_ {ij} end {zarovnáno}}}

Vektory střední hodnoty intenzity dvou tříd a celkový střední vektor lze vyjádřit takto:

{ displaystyle { begin {aligned} mu _ {0} & = [ mu _ {0i}, mu _ {0j}] ^ {T} = left [ sum _ {i = 0} ^ { s-1} sum _ {j = 0} ^ {t-1} i { frac {P_ {ij}} { omega _ {0}}}, sum _ {i = 0} ^ {s- 1} sum _ {j = 0} ^ {t-1} j { frac {P_ {ij}} { omega _ {0}}} right] ^ {T} mu _ {1} & = [ mu _ {1i}, mu _ {1j}] ^ {T} = left [ sum _ {i = s} ^ {L-1} sum _ {j = t} ^ {L -1} i { frac {P_ {ij}} { omega _ {1}}}, sum _ {i = s} ^ {L-1} sum _ {j = t} ^ {L-1 } j { frac {P_ {ij}} { omega _ {1}}} vpravo] ^ {T} mu _ {T} & = [ mu _ {Ti}, mu _ {Tj }] ^ {T} = left [ sum _ {i = 0} ^ {L-1} sum _ {j = 0} ^ {L-1} iP_ {ij}, sum _ {i = 0 } ^ {L-1} sum _ {j = 0} ^ {L-1} jP_ {ij} right] ^ {T} end {zarovnáno}}}

Ve většině případů bude pravděpodobnost mimo úhlopříčku zanedbatelná, takže je snadné ji ověřit:

{ displaystyle omega _ {0} + omega _ {1} cong 1}

{ displaystyle omega _ {0} mu _ {0} + omega _ {1} mu _ {1} cong mu _ {T}}

Diskrétní matice mezi třídami je definována jako

{ displaystyle S_ {b} = součet _ {k = 0} ^ {1} omega _ {k} [( mu _ {k} - mu _ {T}) ( mu _ {k} - mu _ {T}) ^ {T}]}

Stopu diskrétní matice lze vyjádřit jako

{ displaystyle { begin {aligned} & operatorname {tr} (S_ {b}) [4pt] = {} & omega _ {0} [( mu _ {0i} - mu _ {Ti }) ^ {2} + ( mu _ {0j} - mu _ {Tj}) ^ {2}] + omega _ {1} [( mu _ {1i} - mu _ {Ti}) ^ {2} + ( mu _ {1j} - mu _ {Tj}) ^ {2}] [4pt] = {} & { frac {( mu _ {Ti} omega _ {0 } - mu _ {i}) ^ {2} + ( mu _ {Tj} omega _ {0} - mu _ {j}) ^ {2}} { omega _ {0} (1 omega _ {0})}} end {zarovnáno}}}

kde

{ displaystyle mu _ {i} = součet _ {i = 0} ^ {s-1} součet _ {j = 0} ^ {t-1} iP_ {ij}}

{ displaystyle mu _ {j} = součet _ {i = 0} ^ {s-1} součet _ {j = 0} ^ {t-1} jP_ {ij}}

Podobně jako jednorozměrná Otsuova metoda, optimální prahová hodnota ${ displaystyle (s, t)}$ se získá maximalizací ${ displaystyle operatorname {tr} (S_ {b})}$ .

Algoritmus

The ${ displaystyle s}$ a ${ displaystyle t}$ se získává iterativně, což je podobné jednorozměrné Otsuově metodě. Hodnoty ${ displaystyle s}$ a ${ displaystyle t}$ se mění, dokud nezískáme maximum ${ displaystyle operatorname {tr} (S_ {b})}$ , to je

max,s,t = 0;pro ss: 0 na L-1 dělat    pro tt: 0 na L-1 dělat        vyhodnotit tr (S_b);        -li tr (S_b) > max            max = tr(S,b);            s = ss;            t = tt;        konec -li    konec prokonec provrátit se s,t;

Všimněte si, že pro hodnocení ${ displaystyle operatorname {tr} (S_ {b})}$ , můžeme použít rychlý rekurzivní dynamický programovací algoritmus ke zlepšení výkonu času.^[9] Avšak i při přístupu dynamického programování má metoda 2d Otsu stále velkou časovou složitost. Proto bylo provedeno mnoho výzkumů ke snížení nákladů na výpočet.^[10]

Pokud jsou k sestavení 3 tabulek použity tabulky se sečtenou oblastí, sečtěte ${ displaystyle P_ {ij}}$ , součet přes ${ displaystyle i * P_ {ij}}$ a součet ${ displaystyle j * P_ {ij}}$ , pak je běhová složitost maximem (O (N_pixels), O (N_bins * N_bins)). Všimněte si, že pokud je potřeba pouze hrubé rozlišení, pokud jde o prahovou hodnotu, lze N_bins snížit.

Implementace Matlabu

funkční vstupy a výstupy:

historie je ${ Displaystyle 256 krát 256}$ 2D histogram hodnoty ve stupních šedi a dvojice průměrných hodnot ve stupních šedi v sousedství.

celkový je počet párů v daném obrázku. je určen počtem košů 2D-histogramu v každém směru.

práh je dosažená prahová hodnota.

funkcepráh =otsu_2D(historie, celkem)maximum = 0.0;práh = 0;pomocníkVec = 0:255;mu_t0 = součet(součet(repmat(pomocníkVec',1,256).*historie));mu_t1 = součet(součet(repmat(pomocníkVec,256,1).*historie));p_0 = nuly(256);mu_i = p_0;mu_j = p_0;pro ii = 1:256    pro jj = 1:256        -li jj == 1            -li ii == 1                p_0(1,1) = historie(1,1);            jiný                p_0 (ii, 1) = p_0(ii-1,1) + historie(ii,1);                mu_i(ii,1) = mu_i(ii-1,1)+(ii-1)*historie(ii,1);                mu_j(ii,1) = mu_j(ii-1,1);            konec        jiný            p_0(ii,jj) = p_0(ii,jj-1)+p_0(ii-1,jj)-p_0(ii-1,jj-1)+historie(ii,jj);            mu_i(ii,jj) = mu_i(ii,jj-1)+mu_i(ii-1,jj)-mu_i(ii-1,jj-1)+(ii-1)*historie(ii,jj);            mu_j(ii,jj) = mu_j(ii,jj-1)+mu_j(ii-1,jj)-mu_j(ii-1,jj-1)+(jj-1)*historie(ii,jj);        konec        -li (p_0 (ii, jj) == 0)            pokračovat;        konec        -li (p_0 (ii, jj) == celkový)            přestávka;        konec        tr = ((mu_i(ii,jj)-p_0(ii,jj)*mu_t0)^2 + (mu_j(ii,jj)-p_0(ii,jj)*mu_t1)^2)/(p_0(ii,jj)*(1-p_0(ii,jj)));        -li ( tr >= maximum )            práh = ii;            maximum = tr;        konec    koneckoneckonec

Reference

^ M. Sezgin a B. Sankur (2004). "Průzkum technikami prahování obrazu a kvantitativním hodnocením výkonu". Journal of Electronic Imaging. 13 (1): 146–165. doi:10.1117/1.1631315.
^ ^A ^b ^C Nobuyuki Otsu (1979). "Metoda výběru prahové hodnoty z histogramů úrovně šedé". IEEE Trans. Sys. Muž. Cyber. 9 (1): 62–66. doi:10.1109 / TSMC.1979.4310076.
^ Liu, Dongju (2009). „Metoda Otsu a K-prostředky“. Devátá mezinárodní konference o hybridních inteligentních systémech IEEE. 1: 344–349.
^ Liao, Ping-Sung (2001). "Rychlý algoritmus pro víceúrovňové prahování" (PDF). J. Inf. Sci. Eng. 17 (5): 713–727.
^ Huang, Deng-Yuan (2009). „Optimální víceúrovňové prahování pomocí dvoustupňového přístupu optimalizace Otsu“. Písmena pro rozpoznávání vzorů. 30 (3): 275–284. doi:10.1016 / j.patrec.2008.10.003.
^ Kittler, Josef & Illingworth, John (1985). Msgstr "Výběr prahu pomocí kritérií shlukování". Transakce IEEE na systémech, člověku a kybernetice. SMC-15 (5): 652–655. doi:10.1109 / tsmc.1985.6313443.
^ Lee, Sang Uk a Chung, Seok Yoon a Park, Rae Hong (1990). "Srovnávací studie výkonu několika globálních prahových technik pro segmentaci". Počítačové vidění, grafika a zpracování obrazu. 52 (2): 171–190. doi:10.1016 / 0734-189x (90) 90053-x.CS1 maint: více jmen: seznam autorů (odkaz)
^ Jianzhuang, Liu a Wenqing, Li a Yupeng, Tian (1991). "Automatické prahování obrázků na úrovni šedé pomocí dvourozměrné metody Otsu". Circuits and Systems, 1991. Conference Proceedings, China., 1991 International Conference on: 325–327.CS1 maint: více jmen: seznam autorů (odkaz)
^ Zhang, Jun & Hu, Jinglu (2008). "Segmentace obrazu založená na metodě 2D Otsu s analýzou histogramu". Výpočetní technika a softwarové inženýrství, 2008. 6: 105–108. doi:10.1109 / CSSE.2008.206. ISBN 978-0-7695-3336-0.
^ Zhu, Ningbo a Wang, Gang a Yang, Gaobo a Dai, Weiming (2009). "Rychlý 2d prahový algoritmus otsu založený na vylepšeném histogramu". Pattern Recognition, 2009. CCPR 2009. Čínská konference o: 1–5.CS1 maint: více jmen: seznam autorů (odkaz)

externí odkazy

Implementace metody prahování Otsu tak jako GIMP -plugin pomocí Script-Fu (a Systém -založený jazyk)
Poznámky k přednášce o prahování - pokrývá metodu Otsu
Plugin pro ImageJ pomocí metody Otsu k dosažení prahu
Úplné vysvětlení Otsuovy metody s fungujícím příkladem a implementací Java
Implementace Otsuovy metody v ITK
Otsu Thresholding in C # - přímá implementace C # s vysvětlením
Otsuova metoda využívající MATLAB
Otsu Thresholding with scikit-image v Pythonu

[Mehmet-1] M. Sezgin a B. Sankur (2004). "Průzkum technikami prahování obrazu a kvantitativním hodnocením výkonu". Journal of Electronic Imaging. 13 (1): 146–165. doi:10.1117/1.1631315.

[Otsu-2] A ^b ^C Nobuyuki Otsu (1979). "Metoda výběru prahové hodnoty z histogramů úrovně šedé". IEEE Trans. Sys. Muž. Cyber. 9 (1): 62–66. doi:10.1109 / TSMC.1979.4310076.

[3] Liu, Dongju (2009). „Metoda Otsu a K-prostředky“. Devátá mezinárodní konference o hybridních inteligentních systémech IEEE. 1: 344–349.

[4] Liao, Ping-Sung (2001). "Rychlý algoritmus pro víceúrovňové prahování" (PDF). J. Inf. Sci. Eng. 17 (5): 713–727.

[5] Huang, Deng-Yuan (2009). „Optimální víceúrovňové prahování pomocí dvoustupňového přístupu optimalizace Otsu“. Písmena pro rozpoznávání vzorů. 30 (3): 275–284. doi:10.1016 / j.patrec.2008.10.003.

[kittler1985threshold-6] Kittler, Josef & Illingworth, John (1985). Msgstr "Výběr prahu pomocí kritérií shlukování". Transakce IEEE na systémech, člověku a kybernetice. SMC-15 (5): 652–655. doi:10.1109 / tsmc.1985.6313443.

[lee1990comparative-7] Lee, Sang Uk a Chung, Seok Yoon a Park, Rae Hong (1990). "Srovnávací studie výkonu několika globálních prahových technik pro segmentaci". Počítačové vidění, grafika a zpracování obrazu. 52 (2): 171–190. doi:10.1016 / 0734-189x (90) 90053-x.CS1 maint: více jmen: seznam autorů (odkaz)

[jianzhuang1991automatic-8] Jianzhuang, Liu a Wenqing, Li a Yupeng, Tian (1991). "Automatické prahování obrázků na úrovni šedé pomocí dvourozměrné metody Otsu". Circuits and Systems, 1991. Conference Proceedings, China., 1991 International Conference on: 325–327.CS1 maint: více jmen: seznam autorů (odkaz)

[zhang2008image-9] Zhang, Jun & Hu, Jinglu (2008). "Segmentace obrazu založená na metodě 2D Otsu s analýzou histogramu". Výpočetní technika a softwarové inženýrství, 2008. 6: 105–108. doi:10.1109 / CSSE.2008.206. ISBN 978-0-7695-3336-0.

[zhu2009fast-10] Zhu, Ningbo a Wang, Gang a Yang, Gaobo a Dai, Weiming (2009). "Rychlý 2d prahový algoritmus otsu založený na vylepšeném histogramu". Pattern Recognition, 2009. CCPR 2009. Čínská konference o: 1–5.CS1 maint: více jmen: seznam autorů (odkaz)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]