Matematiken bakom ansiktsigenkänning

När Kristian Danev vaknade upp i Buenos Aires en februarimorgon år 2018, visste han inte att det var just denna dag som rättvisan skulle hinna i fatt honom. När han greps på flygplatsen hade han tillbringat närmare tio år på flykt, som en av Europas mest jagade brottslingar, misstänkt för knivmordet på en 24-årig man i staden Poděbrady i Tjeckien år 2008. Upprinnelsen till gripandet var att Danevs ansikte hade dykt upp i en utredning hos den argentiska polisen. Eftersom de inte kunde identifiera honom, skickade polisen vidare bilden till Interpol, för en sökning i Interpols ansiktsigenkänningsregister. När sökningen gav en träff, var det inte bara en triumf för polisen, utan också en fjäder i hatten för en antik matematisk sats.

Ansiktsigenkänning

Vi människor kan känna igen ett ansikte på ett ögonblick. Men för att en dator ska kunna identifiera ett ansikte, måste anletsdragen omvandlas till tal. Den processen kan delas upp i följande steg.

1. Detektion

En algoritm söker igenom bilden och lokaliserar ansiktet.

2. Landmärken

Algoritmen lokaliserar särskilda punkter i ansiktet, så kallade landmärken, till exempel hakans kant, ögonbrynens välvning eller näsans mitt. 

3. Ansiktsmått

Med hjälp av landmärkena gör algoritmen mätningar i ansiktet. Den kan till exempel bestämma avståndet mellan ögonen, näsans längd eller munnens bredd.

Dessa mätetal, i vissa algoritmer 128 stycken, är datorns numeriska beskrivning av det aktuella ansiktet. Varje bild av ett ansikte kodas alltså som en lång rad tal, där varje tal beskriver ett ansiktsmått. Raden av tal kallas för en egenskapsvektor eller deskriptor.

Att vara lika

När Interpol fick bilden från den argentiska polisen var deras uppgift att jämföra den med ansiktena på efterlysta brottslingar i sin databas. Det första steget var att beskriva den inkomna bilden med en deskriptor, en sådan där lång rad av tal. Nästa steg var att jämföra deskriptorn med deskriptorerna av bilderna i databasen. Det låter kanske som en ganska okomplicerad process. Om deskriptorerna överensstämmer, så beskriver de väl samma person? Men riktigt så enkelt är det inte. Deskriptorn beskriver nämligen en enskild bild av ett ansikte. Men vissa faktorer, som avstånd till kameran, minspel och ljussättning, gör att olika bilder av samma person ändå har delvis olika deskriptorer. För att få en träff i sökningen handlar det därför om att hitta deskriptorer som är tillräckligt lika varandra. Det visar sig att en något osannolik matematisk hjälte, Pythagoras sats, kan hjälpa till med just det.

Avståndsformeln

Men vänta ett ögonblick. Pythagoras sats beskriver sambandet mellan sträckorna i en rätvinklig triangel. Hur kan den hjälpa till att avgöra om två bilder beskriver samma ansikte? Enkelt uttryckt kan man säga att om två deskriptorer är någorlunda lika, så ligger de nära varandra i vårt universum av deskriptorer. Och att bestämma avstånd – det är Pythagoras sats en fena på.

Låt mig förklara.

Om vi placerar två punkter i ett rätvinkligt koordinatsystem, kan vi bestämma avståndet mellan dem med Pythagoras sats. Vi betraktar helt enkelt sträckan mellan punkterna som hypotenusan i en rätvinklig triangel. Det ger:

Vi kan beräkna avståndet d med hjälp av Pythagoras sats.

Om du tittar noga, ser du att längden av kateterna i triangeln är skillnaden mellan de båda punkternas x- respektive y-koordinater.

4 – 1 = 3 l.e.

6 – 2 = 4 l.e. 

Med hjälp av den iakttagelsen kan vi formulera den så kallade avståndsformeln. Den visar hur man kan beräkna avståndet mellan två punkter, om man vet punkternas koordinater.

Avståndsformeln i två dimensioner

Bli inte förskräckt. Avståndsformeln här ovanför är bara Pythagoras sats i fin kostym. Formeln säger att för att beräkna avståndet mellan två punkter, så beräknar man först skillnaden mellan punkternas respektive koordinater. Därefter kvadrerar man skillnaderna, adderar dem och drar roten ur resultatet.

Avståndsformeln fungerar faktiskt även om man vill beräkna avståndet mellan två punkter som befinner sig i rummet, dvs. i tre dimensioner, med den skillnaden att man har en tredje koordinat att ta hänsyn till, en z-koordinat som anger punktens höjd över xy-planet.

Avståndsformeln i tre dimensioner.

En punkt i rummet (3D) har tre koordinater.

Men hur kan vi använda detta för att avgöra om två deskriptorer beskriver samma ansikte? Jo, om man stretchar sin fantasi litegrann, så kan man tänka på varje deskriptor som en slags “punkt” som har 128 koordinater. Om vi vill avgöra om två deskriptorer är någorlunda lika, så kan vi avgöra om de ligger nära varandra, genom att beräkna avståndet mellan dem med hjälp av avståndsformeln. Eller ja, en version av avståndsformeln som tar hänsyn till alla 128 koordinater! Om avståndet mellan deskriptorerna är litet (mindre än något tröskelvärde som vi har bestämt från början), så har vi fått en träff! Bilderna visar troligtvis samma person. 

Pythagoras sats, eller dess kusin avståndsformeln, är ett sätt att avgöra om två deskriptorer är lika varandra. I moderna ansiktsigenkänningssystem finns flera andra sätt. Du kan läsa mer om dem här.

Nytta och nöje

Användning av ansiktsigenkänning är inte oproblematiskt. Det har hänt att människor har blivit felaktigt gripna, efter att en ansiktsigenkänningsalgoritm felaktigt pekat ut dem. Bruk av tekniken i offentliga miljöer, kan inkräkta på vår integritet. Och det är ett faktum att algoritmerna är bättre på att identifiera vita män, än kvinnor och mörkhyade, vilket är problematiskt ur ett diskrimineringsperspektiv. Men idéerna bakom ansiktsigenkänning kan också göra nytta. De hjälpte polisen i Argentina att ta fast Kristian Danev. De används för att lokalisera tumörer i röntgenbilder och utnyttjas dagligen i våra mobiler och sociala medier. Mobilföretag som Apple använder till exempel ansiktsigenkänning som en inloggningsmetod. Facebook använder tekniken för att lokalisera ansikten i bilder, så att vi ska kunna tagga våra vänner. Och videosamtalsappar lokaliserar konturerna av ditt ansikte för att du ska kunna använda skojiga effekter som de här.

Nästa gång du använder någon av de här tjänsterna, kan du sända en tanke till alla hängivna programmerare, men också en tacksam tanke till Pythagoras.

Referenser och vidare läsning

Alpman, Marie (2020) Ansiktsigenkänning - vem ser dig? Forskning och Framsteg

CTK (2018) Dopadení nejhledanějšího zločince z Česka: V Argentině ho odhalil počítačový program, Blesk.cz

Geitgey, Adam (2016) Modern Face Recognition with Deep Learning, Medium 

Hao Wu et.al. (2021) Face Recognition Based on Haar  Like and Euclidean  Distance Journal of Physics: Conference Series IOP Publishing doi:10.1088/1742-6596/1813/1/012036

Hill, Kashmir (2020) Another Arrest, and Jail Time, Due to a Bad Facial Recognition Match, New York Times,

Interpol (2018) INTERPOL facial recognition nets most wanted murder fugitive

NEC (2020) A brief history of facial recognition

PXL Vision (2021) Machine learning and how it applies to facial recognition technology, Blog 

Sunil  Swamilingappa  Harakannanavar et.al. (2018) Performance Evaluation of Face Recognition based on Multiple Feature Descriptors using Euclidean Distance Classifier, Int.  J. Advanced Networking and  Applications, 3864 Volume: 10  Issue: 03 Pages: 3864-3879  )  ISSN:  0975-0290

Thomas (2019) Building a face recogniser : traditional methods vs deep learning.

Demos:

Den här demon låter dig hitta landmärken i ett uppladdat foto: https://reconess.com/products/landmarks

Den här demon låter dig hitta både landmärken och ett rutnät i livefeeden från din webkamera: https://storage.googleapis.com/tfjs-models/demos/facemesh/index.html

Den här demon låter dig hitta rutnät i ett uppladdat foto: https://codepen.io/mediapipe/details/KKgVaPJ