Otsu-menetelmä

Otsun menetelmä on harmaasävykuvan binarisointikynnys - algoritmi , jota käytetään tietokoneiden hahmontunnistuksessa ja kuvankäsittelyssä mustavalkokuvien tuottamiseksi.

Algoritmi mahdollistaa kahden luokan ("hyödyllinen" ja "tausta") pikselien erottamisen laskemalla sellainen kynnys, että luokan sisäinen varianssi on minimaalinen [1] . Otsu-menetelmällä on myös parannettu versio useiden kuvatasojen tukemiseksi [2] , jota kutsutaan multi-Otsu-menetelmäksi .

Useista venäjänkielisistä lähteistä löytyy erilaisia tapoja kirjoittaa kirjoittajan sukunimi Nobuyuki Otsu ( englanniksi ), esimerkiksi Otsu- menetelmä ja Otsu-menetelmä .

Menetelmä

Otsu-menetelmä etsii kynnystä, joka pienentää luokan sisäistä varianssia , joka määritellään kahden luokan varianssien painotetuksi summaksi:

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

jossa painot ovat kahden kynnysarvon t erottaman luokan todennäköisyyksiä, on näiden luokkien varianssi. $\omega _{i}$
${\displaystyle \sigma _{i}^{2))$

Otsu osoitti, että varianssin minimoiminen luokan sisällä vastaa luokkien välisen varianssin maksimoimista : [1]

\sigma _{b}^{2}(t)=\sigma ^{2}-\sigma _{w}^{2}(t)=\omega _{1}(t)\omega _ {2}(t)\vasen[\mu _{1}(t)-\mu _{2}(t)\oikea]^{2}

joka ilmaistaan todennäköisyyksien ja aritmeettisen keskiarvon luokassa , joka puolestaan voidaan päivittää iteratiivisesti . Tämä idea johti tehokkaaseen algoritmiin. $\omega _{i}$ $\mu _{i}$

Algoritmi

Annettu harmaasävykuva Toistolaskuri $G(i,j),i={\overline {1,Height)),j={\overline {1,Width)).$ $k=0.$

Laske kuvan histogrammi ja taajuus kullekin kuvan voimakkuustasolle . $p(l)$ $N(l)$ $G$
Laske ja alkuarvot $\omega _{1}(0),\omega _{2}(0)$ $\mu _{1}(0),\mu _{2}(0).$
Jokaiselle arvolle - puoliäänet - histogrammin vaaka-akseli: $t={\overline {1,max(G)))$
1. Päivitämme ja $\omega _{1},\omega _{2}$ ${\displaystyle \mu _{1},\mu _{2))$
2. Laskea $\sigma _{b}^{2}(t)=\omega _{1}(t)\omega _{2}(t)\left[\mu _{1}(t)-\mu _{2}(t)\oikea]^{2}.$
3. Jos enemmän kuin olemassa oleva, niin muistamme myös kynnyksen arvon $\sigma _{b}^{2}(t)$ ${\displaystyle \sigma _{b}^{2))$ $t.$
Vaadittu kynnys vastaa maksimiarvoa . $\sigma _{b}^{2}(t)$

N_{T}=\sum _{i=0}^{max(G)}{p(i)}

\omega _{1}(t)={{\sum _{i=0}^{t-1}{p(i)}} \over {N_{T}}}={\sum _ {i=0}^{t-1}{N(i)}},\quad \omega _{2}(t)=1-\omega _{1}(t)

\mu _{T}={{\sum _{i=0}^{max(G)}{i\cdot p(i)}} \over {N_{T}}}={\sum _{i=0}^{max(G)}{i\cdot N(i)}}

\mu _{1}(t)={{\sum _{i=0}^{t-1}{i\cdot p(i)}} \over {N_{T}\cdot \omega _{1}(t)}}={{\sum _{i=0}^{t-1}{i\cdot N(i)}} \over {\omega _{1}(t))) ,\quad \mu _{2}(t)={{\mu _{T}-\mu _{1}(t)\cdot \omega _{1}(t)} \over {\omega _{ 2}(t)}}.

Ohjelmiston toteutus

JavaScript

Tässä funktiossa pixelsNumber-argumentti on kuvan pikselien kokonaismäärä ja histogrammi-argumentti on 8-bittisen harmaasävykuvan histogrammi, joka esitetään yksiulotteisena taulukkona, jossa elementin numero koodaa harmaasävynumeron, ja kentän arvo koodaa pikselien määrän kyseisellä harmaasävyllä.

funktio otsu ( histogrammi , pikselinluku ) { var summa = 0 , summaB = 0 , wB = 0 , wF = 0 , mB , mF , max = 0 , välillä , kynnys = 0 ; for ( var i = 0 ; i < 256 ; ++ i ) { wB += histogrammi [ i ]; if ( wB == 0 ) jatka ; wF = pikselinluku - wB ; if ( wF == 0 ) tauko ; summaB += i * histogrammi [ i ]; mB = summaB / wB ; mF = ( summa - summaB ) / wF ; välillä = wB * wF * Math . pow ( mB - mF , 2 ); if ( välillä > max ) { max = välillä ; kynnys = i ; } } paluukynnys ; _ } // Testaa: avaa mikä tahansa kuva selaimessa ja suorita koodi konsolissa var im = document . getElementsByTagName ( 'img' )[ 0 ] , cnv = asiakirja . createElement ( 'canvas' ) , ctx = cnv . getContext ( '2d' ); cnv . leveys = im . leveys ; cnv . korkeus = im . korkeus ; ctx . piirtokuva ( im , 0 , 0 ); var imData = ctx . getImageData ( 0 , 0 , cnv . leveys , cnv . korkeus ) , histogrammi = Array ( 256 ) , i , punainen , vihreä , sininen , harmaa ; kun ( i = 0 ; i < 256 ; ++ i ) histogrammi [ i ] = 0 ; for ( i = 0 ; i < imData . data . pituus ; i += 4 ) { punainen = imData . data [ i ]; sininen = imdata . data [ i + 1 ]; vihreä = imData . data [ i + 2 ]; // alfa = imData.data[i + 3]; // https://en.wikipedia.org/wiki/Harmaasävy harmaa = punainen * .2126 + vihreä * .7152 + sininen * .0722 ; histogrammi [ Math . pyöreä ( harmaa )] += 1 ; } var threshold = otsu ( histogrammi , imData . data . pituus / 4 ); konsoli . loki ( "kynnys =%s" , kynnys ); for ( i = 0 ; i < imData . data . pituus ; i += 4 ) { imData . data [ i ] = imData . data [ i + 1 ] = imData . data [ i + 2 ] = imData . data [ i ] >= kynnys ? 255 : 0 ; // opasiteetti 255 = 100 % imData . data [ i + 3 ] = 255 ; } ctx . putImageData ( imData , 0 , 0 ); asiakirja . kehoa . appendChild ( cnv ); konsoli . loki ( "valmis" );

Tämän koodin suorittamisen tulos konsolissa näkyy täällä .

Toteutus C:ssä

// Kuvan intensiteettitasojen lukumäärä. // Harmaan kuvan oletusarvo on 256. 0 - 255. const int INTENSITY_LAYER_NUMBER = 256 ; // Palauttaa histogrammin kuvan intensiteetille 0 - 255 mukaan lukien void laskentaHist ( const IMAGE * kuva , const int koko , int * hist ) { // Alusta histogrammi nollien memsetillä ( hist , 0 , INTENSITY_LAYER_NUMBER * sizeof ( * hist )); // Laske histogrammi kohteelle ( int i = 0 ; i < koko ; ++ i ) { ++ hist [ kuva [ i ]]; } } // Laske kaikkien intensiteettien summa int laskeaIntensitySum ( const IMAGE * kuva , const int koko ) { int summa = 0 ; for ( int i = 0 ; i < koko ; ++ i ) { summa += kuva [ i ]; } palautussumma ; _ } // Funktio palauttaa binarisointikynnyksen harmaasävykuvalle pikselien kokonaismäärällä. // const IMAGE *image sisältää kuvan intensiteetin 0 - 255 mukaan lukien. // koko -- kuvan pikselien määrä. int otsuThreshold ( const IMAGE * kuva , const int koko ) { int hist [ INTENSITY_LAYER_NUMBER ]; laskeaHist ( kuva , koko , hist ); // Tarvitaan luokkien välisen varianssieron nopeaan uudelleenlaskentaan int all_pixel_count = koko ; int all_intensity_sum = laskeIntensitySum ( kuva , koko ); int paras_thresh = 0 ; kaksinkertainen paras_sigma = 0,0 ; int ensimmäinen_luokka_pikselien_määrä = 0 ; int ensimmäisen_luokan_intensiteettisumma = 0 ; // Iteroi luokkien välisen rajan yli // thresh < INTENSITY_LAYER_NUMBER - 1, koska 255:ssä for ( int thresh = 0 ; thresh < INTENSITY_LAYER_NUMBER - 1 ; ++ thresh ) sisällä oleva nimittäjä menee nollaan ensimmäinen_luokka_pikselien_määrä += hist [ thresh ] ; ensimmäinen_luokka_intensiteetti_summa += thresh * hist [ thresh ] ; double ensimmäinen_luokka_prob = ensimmäinen_luokka_pikselien_määrä / ( double ) all_pixel_count ; kaksinkertainen toisen_luokan_todennäköisyys = 1.0 - ensimmäinen_luokka-ongelma ; double ensimmäinen_luokka_keskiarvo = ensimmäisen_luokan_intensiteetti_summa / ( kaksinkertainen ) ensimmäisen luokan_pikseleiden_määrä ; double toisen_luokan_keskiarvo = ( kaikki_intensiteetin_summa - ensimmäisen_luokan_intensiteetin_summa ) / ( kaksinkertainen ) ( kaikkien_pikseleiden_määrä - ensimmäisen_luokan_pikseleiden_määrä ); double mean_delta = ensimmäisen_luokan_keskiarvo - toisen_luokan_keskiarvo ; double sigma = ensimmäisen_luokan_todennäköisyys * toisen_luokan_todennäköisyys * keskiarvo_delta * keskiarvo_delta ; if ( sigma > paras_sigma ) { paras_sigma = sigma ; paras_thresh = thresh ; } } return best_thresh ; }

Muistiinpanot

↑ 12 N. Otsu . Kynnyksen valintamenetelmä harmaatason histogrammeista // IEEE Trans. Sys., mies, Cyber. : päiväkirja. - 1979. - Voi. 9 . - s. 62-66 .
↑ Ping-Sung Liao ja Tse-Sheng Chen ja Pau-Choo Chung. Nopea algoritmi monitasoiselle kynnykselle (määrittämätön) // J. Inf. sci. Fin .. - 2001. - T. 17 . - S. 713-727 .

Linkit

Luentomuistiinpanot kynnysarvosta - kattaa Otsu-menetelmän.