Igenkanning av bilddata med hjalp av

Kohonen-natverk, samt beskrivning av program

Jerker Bjorkqvist

September 2001

1 Introduktion

I detta arbete undersokts hur klassificering av bilddata kan goras med ettKohonen-natverk. Tidigare har liknande arbete gjorts med Hopfield-natverk,dar problemet dock var att datan maste presenteras i binar form. Kohonen-natverkets kan a andra sidan behandla mer generell data (flyttal). Detta gordet mojligt att behandla bilder med gratoner (och i princip aven farger), samtaven behandla transformationer av bilder, dar man istallet for en spatiella in-formationen kartlagger t.ex. frekvensinnehallet i bilden.

I samband med jobbet utvecklades ett program “wnnet” for att folja med hurett Kohonen-natverk beter sig vid traningen.

2 Kohonen natverk

I ett Kohonen natverk stravar man att karakterisera indatan med hjalp av farredimensioner an den har fran borjan, ofta i tva dimensioner. Detta kallas oftaaven for Self-Organizing Map (SOM), eller sjalvorganiserad karta. Noderna idetta natverk har en narhet till varandra som definieras av deras placering ikartan.

Till varje nod i associeras en viktvektor wi med samma dimension som input-vektorn x. Avstandet mellan tva noder i och j har ett definierat varde, om t.ex.noderna ar placerade i tva dimensioner, varvid positionen kan ges som (xi, yi)ges av den euklidiska normen

d =√

(xi − xj)2 + (yi − yj)2 (1)

Iden med ett Kohonennatverk ar nu att noder som ligger nara varandra ocksaskall ha viktmatriser som paminner om varandra. Genom att undersoka vilken

1

nod som ligger bast motsvarar en given input, kan vi klassificera en input. Dennod i som ligger narmast ges av

i∗ = arg mini||x− wi|| (2)

Innan natverket kan anvandas for klassificering bor det tranas. Detta gors genomfoljande steg:

1. Satt viktvektorns wi element wij slumpmassigt for alla noder i

2. Presentera en inputvektor x och avgor vilken nod i∗ som ligger narmastgenom att anvanda uttryck 2

3. Uppdatera nodernas vikter enligt

wij(t+ 1) = α(t)e−d/ρ(t)(xj(t)− wij(t)) (3)

4. Om ej max iterationer uppnatts, ga till 2)

Funktionen α(t) beskriver hur uppdateringen av noder avtar med tiden, eftersomman vill att inlarningen smaningom avtar. Likasa onskar man att den “grann-skap” som berors av av uppdateringarna avtar bade med avstand till noden i∗

samt tiden. Tidsberoende for det senare beskrivs med funktionen ρ(t).

3 Klassificering av bilder m.h.a. Kohonen natverk

Emedan ett Kohonen-natverk formar klassificera inputdata testar vi har huruvi-da en klassificering av bilder fungerar. Harvid maste bilden representeras av envektor. Enklast gor vi detta genom att representera en tvadimensionell bild somen datavektor genom att lata ett varde mellan 0 och 1 representera graheten ivarje pixel, da vi radvis gar igenom bilden. T.ex. den svartvita bilden represen-terande ett T

111111110001100000011000000110000001100000011000

blir saledes x = { 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0,0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0}.

2

4 Test med svartvita bilder

Ett natverk bestanden av 10x10 noder anvandes for klassificeringen av svartvitabilder av storleken 64x64 pixel. Forst tranades natverket enligt traningsbilder ifigur 1.

Figur 1: Bilder for traning

Traningen genomfordes med α(t) = 1/t samt ρ(t) = 10/t. Varje bild vektorfick i tur och ordning fungera som insignal, denna procedur upprepades fort = 1, . . . , 100. Antalet traningar var aningen litet, men p.g.a. av vektorns storlek(4096 element) sa var den relativt tidskravande redan for 100 iterationer.

Efter att natverket tranats, gjordes foljande forsok: en av bilderna genomgicken “scrambling”, vilket innebar att elementen i vektorn med sannolikheten β =0, 0.1, . . .1.0 overgick till fran varde 1 till 0 respektive 0 till 1. En sadan serieses i figur 2. I figur 3 ses den klassificering som natet gor. Eftersom startbildeni detta fall motsvarar bild 4, borde d4 vara minst. Vi ser att till scrambling upptill 0.3 verkar klassificering fungera relativt bra.

Figur 2: Startfigurer med olika scramblingsannolikheter 0.1, 0.3, 0.5, 0.7, 0.9

En motsvarande serie ses i figur 4. I figur 5 ses klassificeringen som natet gor.Nu ar startbilden bild nummer 2, vi ser att klassificeringen stammer val upp tilloch med β = 0.3.

I figur 6 visas 6 bilder som ar modifierade. De bilder som ar uppebara ar de somar uppochner samt de bilder dar en del av bilden saknas. Bild nr 2 fran vaster armodifierad sa att bilden ar flyttat till hoger ett antal pixel. Motsvarande resultatses i figur 6. Nu ser vi att uppochnervanda och flyttade bilder verkar visa daligklassificering. Daremot ar klassificeringen av ofullstandiga bilder nojaktig (enafallet blev det ratt, andra fallet “grannnoden”).

3

Figur 3: Klassificering av scramblade bilder, bilder som anvants flr traning pasidorna

Figur 4: Startfigurer med olika scramblingsannolikheter 0.1, 0.3, 0.5, 0.7, 0.9

5 Test med graskalade bilder

De graskalade bilderna representerades sa att varje pixel fick ett varde mellan 0och 1 dar detta varde representerade graheten. Natverket tranades bilder enligtfigur 8.

Bilderna modifierades pa olika satt enligt figur 11. Igen ar de uppochnervandabilderna uppenbara, medan bild nr 2 ar flyttat i sidled, vilket inte ses direktfran figuren.

Resultatet for motsvarande klassificering ses i figur ??. Igen ser vi att de ofullstandigabilderna ger bra klassificering (2 av 3 ratt), medan uppochnervanda och flyttadebilder ger betydligt samre klassificering.

4

Figur 5: Klassificering av scramblade bilder, bilder som anvants flr traning pasidorna

Figur 6: Modifierade startbilder

6 Program for visualisering av Kohonen natverk

Ett Kohonen-natverk klassificerar som tidigare namnt vektorer. For att visuali-sera detta byggdes ett dataprogram som klassificerar graskalade bilder och visarresultaten.

Vi anvander som inputvektor x en tvadimensionell matris dar varje elementmotsvaras av graheten hos motsvarande pixel i bilden. Vi har motsvarande vikt-vektorer wi for varje nod i i den m× n stora nodkartan. Vi kan nu konstateraatt i vilket skede som helst av traningen kan dessa vikmatrisen askadliggorasav motsvarande bilder. Da vi visualiserar detta far vi ett rutfalt av bilder darvarje bild representerar viktvektorn i motsvarande nod. Detta visas i figur ??.

Genom att for varje traningsiteration rita upp bilder, kan vi mycket val foljamed hur Kohonen-natverket beter sig da det tranas.

5

Figur 7: Klassificering av modifierade bilder, bilder som anvants flr traning pasidorna

Figur 8: Graskalade bilder for traning

Figur 9: Modifierade startbilder

6.1 Anvandning av programmet

Programmet fungerar bade i Win32 och Linux-omgivning. Programmet ar gra-fiskt och typisk anvandning sker genom foljande steg.

1. Programmet startas med kommandot “wnnet”. Programmet oppnas meden tom skarm, (fig 12).

6

Figur 10: Klassificering av modifierade bilder, bilder som anvants flr traning pasidorna

Figur 11: Rutfalt med bilder

2. Genom “File-¿Load” fran menyn oppnar man en fildialog. I denne valjs debilder man vill trana med. Bilderna skall vara av typ “BMP”. Man valjervalfritt antal bilder. Alla bilder skalas, oberoende av ursprungsstorlek tillgraskalade bitkartor av storleken 64x64 pixels.

3. Traningen startas genom “Train-¿Start”. Dialogen “Network parameters”visas. I denna valjer man natverkets storlek, traningsparametrar samt an-talet iterationer. Genom att trycka pa “Ok” startas traningen.

7

4. Under traningen visas hur ur viktvektorerna utvecklas.

5. Da traningen ar fardig kan man valja en bild genom “Evaluate-¿Evaluatebitmap...” for att se vilket nod som bast motsvarar den valda bilden.

Figur 12: Huvudfonster for programmet

6.2 Traningsparametrar

Genom dialogen 13 valjer man parametrar for traningen. Vid varje iterationuppdateras viktvektorerna genom uttrycket

Figur 13: Dialogbox for parameterinstallning

wij(t+ 1) = α(t)e−d/ρ(t)(xj(t)− wij(t)) (4)

dar α(t) = a/t samt ρ(t) = b/t. Vi far saledes

wij(t + 1) = a/te−dt/b(xj(t) −wij(t)) (5)

8

Vi har med andra ord parametrarna a samt b. Vi har dessutom mojlighetenatt genom att specificera a = 0 sa far vi istallet α(t) = 1, varvid vi far denforenklade uppdateringen

wij(t + 1) = e−dt/b(xj(t) −wij(t)) (6)

Vi har dessutom mojlighet att trana med hjalp av transformerad data (“Usetransformation”), enligt metoderna i 7.2.

6.3 Test med bildserie

I foljande exempel anvands 9 bilder som traningsvektorer. Traningen genomforsi 100 iterationer med parametrarna a = 10 samt b = 50. Det valda natverkethar storleken 7 × 7 noder. Resultatet av traningen efter 8, 33, 60 samt 100iterationer visas i figur 14.

Figur 14: Viktmatriser efter 8,33,60 samt 100 iterationer

9

6.4 Nerladdning av programmet

Programmet finns att nerladda pa addressen http://www.abo.fi/ jbjorkqv/wnnet.

7 Igenkanning av flyttade bilder

I det tidigare avsnittet noterades att bilder som flyttats eller speglats var svaraatt kanna igen for natverket. Intiuitivt kunde orsaken vara att eftersom bildenflyttas, kommer den vektor som beskriver bilden ocksa att forskjutas sa att detkan vara mycket svart att efter detta klassificera vektorn.

Ett satt att undvika detta kunde vara att beskriva bilddatan med annan anspatiell information. Ett satt ar att med en vektor bestamma frekvensinnehalleti en bild, vilket inte namnvart borde andra avenom bilden flyttas. Frekvensin-nehallet i en datavektor kan analyseras med den diskreta cosinustransformen,definierad enligt

7.1 Fourieranalys

Fourieranalys spelar en stor roll vid signalbehandling, bade analog och digital.Fundamentalt sager fouriranalysen att en godtycklig signal kan ses som sam-mansatta sinusvagor. Vi later x(t) vara en periodisk funktion med perioden T0,sa att

x(t+ T0) = x(t) (7)

Da kan x(t) uttryckas som en summa av sinus- och cosinusfunktioner enligt

x(t) =a0

2+∞∑k=1

ak cos(

2πktT0

)+∞∑k=1

bk cos(

2πktT0

)(8)

Vanligen ges cosinus- och sinusfunktionerna med hjalp av exponentialfunktio-nen,

ejθ = cos θ+ j sin θ (9)

Vi kan da skriva

x(t) =∞∑

k=−∞cke

jkω0t (10)

10

dar frekvensen ω0 ges av ω0 = 2πT0

.

Vi ar nu intresserade av att hitta de (komplexvarda) koefficienterna ck. Utanharledning har ges dessa enligt

ck =1T0

∫ T0

0

x(t)e−jkω0tdt (11)

Om signalen ar icke-periodisk,dvs T0 → ∞, sa gar grundfrekvensen ω0 → 0.Detta leder till att vi istallet for en funktion som definierar spektraldensiteten

X(ω) =∫ ∞−∞

x(t)e−jωtdt (12)

vilket kallas Fouriertransformen av x(t).

7.2 Diskret cosinustransform

Da vi har en diskret funktion x(n) kan vi anvanda den diskreta Fouriertrans-formen, dar koefficienterna ck ges av

Xk =N−1∑n=0

xn)e−j2πkn

N (13)

dar N ar langden pa insignalsvektorn x. Vi ser att eftersom vi endast hadediskreta varden pa insignalen xn, sa integralen overgatt i en summation.

Vi kan igen konstatera att koefficienterna i Xk ar komplexvarda. Detta bety-der att berakningarna ar relativt arbetsdryga. Darfor anvands ofta en annantransformation, den diskreta cosinustransformationen DCT, som ar definieradenligt

ck = ν(k)N−1∑n=0

x(n) cos(πk(n + 1/2)

N

), k = 1, . . .N (14)

dar

ν(k) =

{ 1√N, om k = 0√

2N , om k 6= 0

(15)

11

7.3 DCT i 2 dimensioner

Hittills har vi behandlat rackor i en dimension. Bilder representeras i tva di-mensioner, och harvid maste transformationen forandras. Nu ges

cu,v = ν(u)ν(v)N−1∑m=0

N−1∑n=0

xm,n cos[πu(m+ 1/2)

N

]cos[πv(n + 1/2)

N

](16)

I praktiken ar alltsa 2d DCT en endimensionell DCT som appliceras pa datatva ganger, forst i x-led sedan i y-led. Detta leder till att komplexiteten vidberakningarna ar stor for stora bilder. For att kunna utfora berakningar i ma-trisform kan den 2d DCT ocksa skrivas

C = ATXA (17)

dar

am,n = ν(n) cos[

(m+ 1/2)nπN

](18)

010

2030

4050

6070

0

20

40

60

80−1200

−1000

−800

−600

−400

−200

0

200

400

600

Figur 15: Ursprungsbilden till vanster 70x70 punkter, motsvarande koefficient-matris efter DCT till hoger

Vi kan namna att for t.ex. JPEG bildkompression delas bilden upp i underblockav storleken 8x8 pixel (eller 16x16 pixel) fore DCT och vidare behandling.

12