Hovedkomponentanalyse til ansiktsgjenkjenning

Introduksjon

Hovedkomponentanalyse (prinicipal component analysis eller PCA) er et sentralt verktøy i Data Science. Dataene vi samler inn har ofte hundrevis av dimensjoner, altfor mange til å bruke direkte i en modell. Ved å bruke hovedkomponentanalyse kan vi identifisere de viktigste dimensjonene i dataene hvor størstedelen av variasjonen foregår. Med andre ord kan hovedkomponentanalyse fortelle oss hvilke faktorer vi bør inkludere for eksempel i en maskinlæringsmodell, eller for å kategorisere datapunkter.

Et interessant eksempel på bruk av hovedkomponentanalyse til sistnevnte er automatisk ansiktsgjenkjenning. Automatisk ansiktsgjenkjenning har mange interessante anvendelsesområder. Vi nevner i fleng identifisering av kriminelle, bruk i sikkerhetssystemer og pålogging på pc og mobil. I denne artikkelen illustrerer vi bruken av hovedkomponentanalyse på nettopp dette eksempelet.

Eksempel på ansikt

Vi antar at alle bildene har samme oppløsning på \(n_{lengde} \times n_{høyde} = n\) piksler. Siden bildene er svart-hvitt er hver piksel gitt av et tall mellom 0 (svart) og 1 (hvitt). Hvert bilde er dermed gitt av \(n\) reelle tall, og vi kan tenke på hvert bilde \(\mathbf{B}\) som et punkt i et rom med \(n\) dimensjoner kalt \(\mathbb{R}^n\). Anta nå at vi har et sett med \(m\) svart-hvitt bilder, \(\mathbf{B}_1,\mathbf{B}_2, . . . ,\mathbf{B}_m\), av en gruppe på \(p\) personer. Vi kaller dette settet for treningssettet. Problemet vårt er å klassifisere et nytt sett med bilder av de samme personene, basert på hvilket individ bildet viser. Slik det er vanlig i Data Science kaller vi dette nye settet for testsettet. For enkelhets skyld antar vi som nevnt at bildene ikke er av andre personer enn de i treningssettet, selv om det er fullt mulig å ta hensyn til dette.

Eksemplet vårt er et sett med 400 bilder fordelt på 10 bilder av 40 personer. Vi lar 7 bilder av hver person danne treningssettet slik at \(m = 280\). De 3 resterende bildene av hver person danner testsettet på 120 bilder. Bildenes har en oppløsning på \(112 \times 92\) slik at de har \(n=10304\) piksler. Et eksempelbilde fra testsettet er vist til høyre.

Egenansikter

Vi kan finne gjennomsnittsansiktet, \(\mathbf{B}_{snitt}\), av ansiktene i treningssettet som

Gjennomsnittsansikt

\( \mathbf{B}_{snitt} = \frac{1}{m} \sum_{i=1}^{m} \mathbf{B}_i. \)

De ulike ansiktene avviker dermed fra gjennomsnittet med

\(\mathbf{B}_i-\mathbf{B}_{snitt}, \ \ i=1,2, . . . ,m. \)

Gjennomsnittsansiktet for eksemplet vårt vises til høyre.

Siden bilder av ansikter er svært like sammenlignet med vilkårlige svart-hvitt bilder, vil ikke disse bildene være tilfeldig fordelt utover i rommet. Den sentrale ideen bak hovedkomponentanalyse i denne settingen er å finne de viktigste retningene (vektorene) i rommet av alle svart-hvitt bilder hvor ansiktsbildene fordeler seg relativt til gjennomsnittsansiktet. Vi kan kalle den delen av rommet

Egenansiktet \(\mathbf{u}_1 \)

som inneholder ansiktsbilder for ansiktsrommet. Siden vi har \(m\) ansiktsbilder vil dimensjonen av dette rommet (maksimalt) være \(m-1\). Vi søker derfor \(m-1\) gjensidig vinkelrette enhetsvektorer (lengde 1) \(\mathbf{u}_k\) i \(\mathbb{R}^n\) for \(k = 1,2, . . . ,m-1\), og indekserer dem etter hvor mye av variasjonen av ansiktsbilder som skjer i deres retning. Mest variasjon skjer dermed i retning \(\mathbf{u}_1\), nest mest i retning \(\mathbf{u}_2\) og så videre.

Vi hopper her for enkelthets skyld over de detaljerte utregningene, men nevner for de interesserte at disse retningsvektorene viser seg å være egenvektorene til kovariansmatrisen til ansiktsbildene. Siden disse egenvektorene også kan sees på som svart-hvitt bilder, og da ligner spøkelsesaktige ansikter, kaller vi dem for egenansikter. Det viktigste egenansiktet \(\mathbf{u}_1\) for vårt eksempel er vist til høyre.

Ansiktsgjenkjenning

Egenansiktene, \(\mathbf{u}_k\), danner en basis for ansiktsrommet. Vi kan bruke dette til å identifisere ansikter. Da egenansiktene er sortert i synkende rekkefølge når det gjelder evnen til å beskrive variasjonen i ansikter, kan vi komme unna med å kun bruke de første \(l\) egenansiktene. \(l\) er her betydelig mindre enn \(m-1\). Den sentrale prosessen er nå å transformere et ansiktsbilde \(\mathbf{B}\) om til sine egenansiktkomponenter \(\omega_k\) for \(k=1,2, . . . ,l\). Vi finner \(\omega_k\) ved å projisere avstanden mellom dette ansiktet og gjennomsnittsansiktet ned på egenansiktet \(\mathbf{u}_k\)

\(\omega_k = \mathbf{u}_k^T(\mathbf{B}-\mathbf{B}_{snitt})\) for \(k = 1,2, . . . ,l \).

Beste match til ansiktet

Egenansiktkomponenten \(\omega_k\) beskriver hvor mye ansiktet \(\mathbf{B}\) avviker fra gjennomsnittsansiktet i retningen gitt av egenansiktet \(\mathbf{u}_k\). Hovedkomponentanalyse har med andre ord latt oss gå fra å beskrive ansiktsbilder som en stor samling av \(n\) piksler til å kunne beskrive dem omtrentlig med et langt mindre antall komponenter. Disse komponentene angir hvordan ansiktet avviker fra et gjennomsnittlig ansikt på de viktigste måtene.

Kall vektoren med egenansiktkomponentene til bilde \(\mathbf{B}_i \) for \(\boldsymbol{\Omega}_{i}\). Vi beregner \(\boldsymbol{\Omega}_{i}\) for alle bildene i treningssettet. Identifikasjonen av et nytt ansiktsbilde \(\mathbf{B}\) går kort sagt ut på å sammenligne dens komponenter \(\boldsymbol{\Omega}\) med de ulike \(\boldsymbol{\Omega}_{i}\). Når det gjelder eksakt metode for dette finnes flere muligheter. En av de enkleste er å bruke nærmeste nabo: La \(\boldsymbol{\Omega}_{j}\) være den av \(\boldsymbol{\Omega}_{i}\) som er nærmest \(\boldsymbol{\Omega}\) i avstand, og identifiser \(\mathbf{B}\) som personen som er avbildet på bildet \(\mathbf{B}_j\).

Vi tester nå denne prosedyren på eksempelet vårt. Bildenes oppløsning er som nevnt \(n=10304\) piksler, mens vi til identifiseringen kun bruker komponentene \(\omega_k\) forbundet med de 19 viktigste egenansiktene \(\mathbf{u}_k\). Vi har dermed redusert antall dimensjoner vi ser på med en faktor på over 500. Likevel klarer prosedyren å korrekt identifisere 118 av 120 bilder i testsettet, en suksessrate på 98.3%. Til høyre vises bildet som ble identifisert som nærmeste nabo i treningssettet til det tidligere viste eksempelbildet fra testsettet.

Til slutt

Dette var en kort introduksjon til hovedkomponentanalyse: hvordan det kan anvendes til å plukke ut de viktige faktorene i et problem og dermed gjøre det langt mer håndterbart. Dersom du ikke hadde det allerede fikk du forhåpentligvis øynene opp for nytteverdien av denne og lignende reduksjonsteknikker innenfor Data Science.

Ta gjerne kontakt med oss i RAV Norge dersom du ønsker å vite mer om dette eller andre temaer innenfor Data Science, eller om du har forretningsutfordringer du ønsker å diskutere med oss.


Om forfatteren

Eirik Hoel Høiseth

Lyst å lære mer om dette?

Del denne artikkelen