3-4 The Mole – muldvarpen.

Jeg spottede igen en del matematik i dette afsnit: Analyse af et trafikuheld brugte cykloidekurver til at beskrive positionen af trafikofferets hæl ved almindelig gang. Der var billeder med skjulte beskeder (matematikken var desværre ikke rigtig med, for man skulle bare kigge nøje på en forstørrelse – og vups havde kvindens hår skjulte bankkontonumre og navnet på to vidner, der var blevet myrdet… Vi har tidligere haft en mere avanceret brug af billeder, nemlig steganografi, oppe i bloggen, men det var ikke det, Charlie brugte idag.)
Charlie og Larry spillede med en rubiksagtig dims til sidst. den vil jeg gerne høre om, hvis nogen ved, hvad det var.

Der var også omtale af kombinatorisk optimering – det skulle Amita være særlig god til. Det skulle bruges til at finde næste mødested for muldvarpen og repræsentanten for den kinesiske efterretningstjeneste.

Den matematik, I får mere om idag, er det, der blev brugt til at søge billederne fra sikkerhedkameraerne igennem, nemlig Eigenfaces, eller egenansigter må det danske ord være.

Et digitalt billede består af pixelværdier. Lad os sige, der er 255 gråtoner, så vil hver pixel have en værdi mellem 0 og 255. Et billede med 100 x 100 pixels har altså 10000 tal mellem 0 og 255, en vektor med 10000 koordinater. Det giver i princippet [tex]256^10000[/tex], et tal med 24000 cifre, mulige billeder. Hvis vi på forhand ved, at billederne forestiller ansigter, så er der rigtig mange af mulighederne, som ikke vil optræde, og det kan man udnytte. Ideen er, at ansigterne, som jo i første omgang er i et 10000 dimensionalt rum (10000 koordinater pr. ansigt), faktisk ikke skal bruge så mange koordinater. Hvis vi ved, vi befinder os på jorden, kan vi give position ved længde og breddegrad, selvom vi jo i pricippet er i et (mindst) tre dimensionalt rum.

Hvis nu vi havde to koordinater til at beskrive billeder, ville ideen være, at de ligger cirka på en linje. Man finder altså bedste rette linje igennem. Derefter kan alle billeder beskrives ved en parameter, som giver, hvor langt ude af linjen, de ligger. I den teknik, jeg beskriver nedenfor, vil man
1) finde det midterste punkt (xM,yM), som middelværdien af x-koordinaterne, og middelværdien af y-koordinaterne.
2) Så beregner man for alle punkter differensen mellem deres koordinat og middelpunktet.
3) Man finder en vektor, der repræsenterer den retning, hvor afvigelsen fra middelpunktet er størst, svarende til en retningsvektor for den linje, de ligger på. Det er det, der nedenfor er egenvektoren med størst egenværdi.

Først samler man en masse billeder af ansigter sammen. Hvert billede giver en vektor med 10000 koordinater. Lad os sige, vi har 500.
Man udregner “middelfjæset” ved at lægge alle vektorerne sammen og dividere med antallet.
Nu repræsenteres hvert ansigt istedet ved afvigelsen fra middelfjæset – man trækker middelfjæsvektoren fra alle de andre. Og så bliver det lidt avanceret: Lad A være den 500 x 10000 matrix, der har afvigelses vektorerne som rækkevektorer. Matricen [tex]C=A^TA[/tex] kaldes kovariansmatricen. Den er nu 10000 x 10000 og den er symmetrisk. En vektor v, som opfylde [tex]Cv=lambda v[/tex] kaldes en egenvektor for C, og de billeder, der svarer til disse vektorer kaldes egenansigter/eigenfaces. Man vil nu beskrive andre ansigter som vægtede summer af egenansigterne. En høj værdi af [tex]lambda[/tex] (en høj egenværdi) svarer til, at billedet er væsentligt til karakterisation af andre ansigter (indgår med høj vægt), og det viser, sig, at man kan nøjes med meget få egenansigter – man udelader dem med meget lav [tex]lambda[/tex].
Lad os sige, der er 10 egenansigter med høje egenværdier. Så kan vi nu beskrive alle andre ansigter med 10 koordinater i stedet for 10000.

Når man skal sammenligne ansigter, som de gør i serien, bliver det nu et meget mere beregningsmæssigt overkommeligt problem.

Man skal desuden have metoder til at finde ansigter i større billeder, så man kan fokusere på netop ansigterne. Både eigenface teknologien og dette er beskrevet i M. Turk og A. Pentland “Eigenfaces for Recognition” Journal of Cognitive Neoscience Vol 3 no.1, 1991.

Der er masser af Google hits på eigenfaces. Her er et par eksempler på eigenfaces hentet fra Eigenface group på Rice university http://www.owlnet.rice.edu/~elec301/Projects99/faces/index.html