Reconeixement de les persones pels trets de la cara

Francesc Serratosa

Nascut a Barcelona l’any 1967. Llicenciat en Enginyeria Informàtica per la Universitat Politècnica de Catalunya l’any 1993 i doctorat per aquesta mateixa universitat l’any 2000. Actualment és professor titular d’Informàtica a la Universitat Rovira i Virgili. Des de 1993 ha fet recerca activa en camps com la visió per ordinador, la robòtica, el reconeixement de patrons estructurals, l’aprenentatge de màquines i la biomètrica. Ha publicat més de noranta articles i exerceix activament d’avaluador en alguns congressos i publicacions. Dóna classes de Visió per ordinador i Biomètrica a la Universitat Rovira i Virgili i a la Universitat Oberta de Catalunya. Ha estat coordinador del curs de doctorat d’Informàtica i Seguretat a la Universitat Rovira i Virgili entre 2006 i 2012 i actualment és coordinador del màster interuniversitari de Teoria de la comunicació i la informació (MSITIC). Ha treballat en més de deu projectes de recerca i des de l’any 2005 és l’investigador principal d’un projecte de recerca de cinquè curs patrocinat per ENRESA i relacionat amb el desmantellament nuclear. És autor de tres patents i fa d’avaluador especialitzat de projectes públics de recerca.

PID_00215055

Els textos i imatges publicats en aquesta obra estan subjectes –llevat que s'indiqui el contrari– a una llicència de Reconeixement-NoComercial-SenseObraDerivada (BY-NC-ND) v.3.0 Espanya de Creative Commons. Podeu copiar-los, distribuir-los i transmetre'ls públicament sempre que en citeu l'autor i la font (FUOC. Fundació per a la Universitat Oberta de Catalunya), no en feu un ús comercial i no en feu obra derivada. La llicència completa es pot consultar a http://creativecommons.org/licenses/by-nc-nd/3.0/es/legalcode.ca

Índex

Introducció
Objectius
1.Etapes dels sistemes de reconeixement de persones pels trets de la cara
2.Detecció de les cares
3.Normalització de la cara
- 3.1.Normalització de les dimensions de la subfinestra
- 3.2.Normalització de la intensitat de la subfinestra
4.Extracció de les característiques
5.Verificació d’una cara
6.Identificació d’una cara
7.Generació de cares
Resum
Activitats
Annex
Abreviatures
Bibliografia

Introducció

El reconeixement de les persones per la cara és el mètode d’identificació de les persones més usat pels humans. Un altre mètode natural és l’olor, que és un dels mètodes més usat per molts animals, però aquesta tècnica de reconeixement va deixar de ser usada pels humans fa molts milers d’anys. El reconeixement de les persones per la cara és una tasca que portem a terme constantment i sense un esforç aparent. No obstant això, en la intel·ligència artificial continua sent una tasca de gran esforç computacional i de recursos. L’aparició de dispositius de baix cost i amb molta capacitat de càlcul, com portàtils o telèfons intel·ligents, ha despertat un interès enorme en el processament d’imatges i vídeos en moltes aplicacions, entre les quals hi ha la identificació mitjançant la biometria i el seguiment de persones o de les seves cares. Una aplicació típica és el seguiment automàtic de la cara d’un conferenciant.

La recerca en el reconeixement de cares està motivada no sols pel desafiament de la metodologia en si, sinó també per nombroses aplicacions pràctiques en què la identificació de les persones és necessària. El reconeixement de cares és un dels mètodes biomètrics més usats i ha esdevingut cada cop més i més important a causa dels avenços tan ràpids en les tecnologies de les càmeres digitals, Internet, dispositius mòbils i la demanda cada cop més gran de mesures de seguretat. La capacitat de càlcul del processador d’una càmera de fer fotos de baix cost és superior als ordinadors de sobretaula de principis de la dècada de 1980. Així, han pogut aparèixer els sistemes de detecció de cares en càmeres de baix cost.

Els principals avantatges del reconeixement de les persones per la cara són dos:

1) És el mètode més natural, al qual estem acostumats, i per tant és menys intrusiu.

2) És el mètode més fàcil d’usar de cara a l’usuari; simplement una càmera ha de captar la cara amb poca o cap col·laboració de l’usuari.

A més, és un sistema biomètric que pot treballar en un procés de verificació (o autenticació) o en un procés d’identificació (o reconeixement). Han aparegut aplicacions que duen a terme automàticament aquests dos processos (per exemple, Picassa o iPhoto). El seu objectiu és anar cercant cares conegudes en fotos personals i així poder-nos mostrar en quines fotos apareix una persona concreta. Hi ha un procés d’aprenentatge en què l’aplicació selecciona les cares i pregunta de quina persona són. Com més cares verifiquem, més aprèn el sistema i per tant, més cares troba i més en classifica en noms concrets. Un dels aspectes pràctics interessants és que l’aprenentatge es pot fer en qualsevol moment, és a dir, que sempre som a temps de corregir cares mal classificades o classificar cares sobre les quals el sistema dubta i ens demana la nostra ajuda. A més, quan hi anem afegint fotos noves, el sistema va detectant automàticament les cares noves que puguin aparèixer.

L’ordre en què es comenten les tècniques i els processos en aquest mòdul té certa relació amb el flux de la informació en el procés general de la comparació de dues cares o la cerca d’una cara en una base de dades. Comentarem aquests mètodes de la manera següent:

En l’apartat “Etapes dels sistemes de reconeixement de persones pels trets de la cara” comentem l’existència de les cinc etapes fonamentals d’un sistema de reconeixement de cares.
Després, detallarem cadascuna de les etapes. D’aquesta manera, en l’apartat “Detecció de les cares” expliquem com es pot detectar una cara dins d’una imatge, és a dir, com es pot saber que en alguna part o algunes parts de la imatge hi ha una cara o diverses cares.
En l’apartat “Normalització de la cara” expliquem un procés de normalització de la part de la imatge en què creiem que hi ha una cara. Aquesta normalització té l’objectiu de tenir la informació de la cara independentment de la posició de la persona i de la llum.
Un cop tenim la imatge normalitzada, en l’apartat “Extracció de les característiques” n’extraiem les característiques principals. En l’apartat “Verificació d’una cara” ja tenim el procés específic dels sistemes biomètrics que es basa a verificar si dues imatges de cares pertanyen a la mateixa persona.
Com a continuació natural, en l’apartat “Identificació d’una cara” s’explica com s’ha d’identificar una persona per la seva cara.
Finalment, en l’apartat “Generació de cares” s’explica com s’ha de generar una cara de manera sintètica a partir d’un conjunt de cares. Aquesta tècnica és interessant quan no tenim la imatge completa de la cara d’una persona i necessitem tenir-ne una bona aproximació.

Objectius

Els objectius bàsics d’aquest mòdul són els següents:

Conèixer les etapes bàsiques dels sistemes de reconeixement de les persones basats en la cara.
Conèixer les tècniques de la visió per computador aplicades a l’extracció de les característiques principals de la cara.
Representar una cara en un registre d’una base de dades.
Comparar dues cares.
Generar una cara de manera sintètica usant un conjunt de cares.

1.Etapes dels sistemes de reconeixement de persones pels trets de la cara

El primer sistema de reconeixement de persones per la cara fet públic va ser la tesi doctoral presentada per Kanade l’any 1974. Des d’aquell primer sistema fins ara, el rendiment dels sistemes de reconeixement de cares ha millorat significativament. A més, ara aquest procés es pot dur a terme a temps real amb imatges o vídeos capturats en situacions més o menys favorables. No obstant això, encara que la millora en aquests sistemes ha estat encoratjadora, aquesta tasca ha resultat ser un esforç difícil, especialment en situacions no controlades en què hi pot haver canvis d’il·luminació, expressions, punts de vista o oclusions. Els humans i alguns animals tenen una capacitat de reconeixement molt superior als sistemes artificials. Ara per ara, no se sap quan un sistema artificial serà millor que un de natural.

Avui en dia, les etapes principals dels sistemes de reconeixement de persones per la cara no ha variat gaire respecte de la primera solució proposada per Kanade. El que ha variat és la solució aplicada dins d’aquestes etapes. Tots els sistemes acostumen a estar formats per cinc grans mòduls que descriurem a continuació.

1) Detecció i seguiment de la cara⁽¹⁾: extreu la zona en què hi pot haver la cara dins de la imatge. En cas que treballem directament amb un seqüència de vídeo, també haurem de fer el seguiment de la cara, és a dir, anar sabent en quina zona de la imatge es troba la cara, imatge per imatge. No comentarem res més sobre els sistemes de seguiment de cares⁽²⁾; simplement esmentar que l’avantatge de treballar amb vídeo és que tenim una informació passada (posició, velocitat, acceleració, orientació, mida...) que usem per a predir aquestes dades en imatges futures.

2) Normalització de la cara⁽³⁾: l’objectiu és normalitzar la imatge de la cara respecte de les propietats geomètriques, tal com la mida i la posició, usant transformacions geomètriques o morfològiques. També es normalitza respecte de la il·luminació. L’objectiu d’aquestes transformacions és que la imatge resultant sigui tan invariant com sigui possible a tots els agents externs (focus, il·luminació, posició relativa d’on és la càmera respecte d’on és la cara, zoom de la càmera...). Es detecten els components facials com els ulls, les orelles, el nas o la boca i s’usen per a fer les transformacions necessàries.

3) Extracció de les característiques⁽⁴⁾: l’objectiu és obtenir informació efectiva de la imatge de la cara que sigui útil per a distingir entre dues cares diferents però en canvi que sigui invariant a dues imatges de la mateixa persona. A més, s’ha d’aconseguir que sigui estable respecte als agents externs.

4) Verificació o identificació de cares⁽⁵⁾: l’objectiu d’aquest mòdul depèn de si estem en un procés d’identificació o de verificació. En un procés d’identificació, compara les característiques extretes d’una imatge nova amb les característiques de diverses imatges de la base de dades i retorna la més semblant (o conjunt de més semblants). En un procés de verificació, compara les característiques de dues imatges i retorna si són la mateixa persona o no. També pot retornar una distància o probabilitat que siguin la mateixa persona.

5) Base de dades⁽⁶⁾: aquest mòdul emmagatzema les característiques de totes les imatges que ens han servit per a matricular les persones. En els processos d’identificació, va oferint característiques de cares perquè siguin comparades. Acostumen a tenir uns mecanismes interns anomenats indexació de bases de dades, que serveixen perquè no sigui necessari recórrer tota la base de dades i així reduir el temps de cerca.

Figura 1. Procés d’identificació o verificació de persones per la cara

2.Detecció de les cares

La detecció de la cara és el primer pas del procés d’identificació de les cares. La seva fiabilitat té una influència cabdal en tot el sistema de reconeixement, ja que si la cara no es detecta, llavors no s’aplica cap altre procés en aquella part de la imatge. Donada una sola imatge o una seqüència de vídeo, un detector de cares ideal hauria de tenir la capacitat de localitzar totes les cares, malgrat la posició, escalat, edat, expressió... A més, hauria de ser independent d’il·luminacions estranyes i del contingut de la imatge o vídeo. Fixeu-vos que detectar una cara vol dir que el sistema sàpiga que en aquells píxels de la imatge hi ha una cara, però encara no sap quina persona és.

S’han dissenyat diversos mètodes per localitzar cares en una imatge i també per al seguiment i detecció de cares en seqüències de vídeo.

La localització de la cara pel mètode basat en l’aparició⁽⁷⁾ es basa en la idea de cercar si la cara apareix en qualsevol punt de la imatge. El procés es porta a terme de la manera següent: la imatge d’entrada s’escaneja a totes les posicions possibles i en escalats diferents per una subfinestra. Aquesta subfinestra normalment és un quadrat de diferents dimensions. La detecció de la cara es planteja com un sistema que analitza només la subfinestra i sap classificar la zona de la imatge que cau dins de la subfinestra en només dues classes. Una classe és “cara” i l’altra classe és “no-cara”. Els píxels externs a la subfinestra no afecten aquesta decisió. La subfinestra serveix per a aïllar-nos de la resta de la imatge. El classificador que decideix si és una cara o no és una cara ha estat ensenyat amb molts exemples de subfinestres que són cares i molts exemples de subfinestra que no són cares. Com veurem a continuació, aquests exemples serveixen per a aportar informació estadística. Si les mides de la subfinestra són, per exemple, de 20 × 20 píxels, llavors detectarem cares a la imatge que ocupin 20 × 20 píxels. I per entrenar el classificador, haurem de passar imatges de 20 × 20 que siguin cares i imatges de 20 × 20 que no siguin cares.

En la figura 2 es veuen deu imatges de 20 × 20 píxels usades per a aprendre la classe “cara” i deu imatges de 20 × 20 píxels usades per a aprendre la classe “no-cara”.

Figura 2. Imatges usades per a aprendre la classe “cara” i imatges usades per a aprendre la classes “no-cara”

Aquí presentarem el classificador més senzill que s’ha dissenyat, s’anomena classificador de Bayes. Hi ha un altre classificador també molt usat anomenat Adaboost que normalment funciona una mica millor. Aquest altre classificador complica una miqueta la idea inicial de Bayes en afegir-hi ponderacions o pesos. Les mostres que anem deduint de manera iterativa que estan mal classificades es tenen molt en compte, ja que el pes amb què se les pondera va augmentant. Aquests dos classificadors de “cara” i “no-cara” aprenen perquè en les subfinestres que contenen una cara apareix una correlació entre els seus píxels. Per exemple, sempre que una zona està molt il·luminada, també ho està aquesta altra zona, o al revés, sempre que està molt il·luminada, detectem que aquesta altra zona és molt fosca. D’altra banda, se suposa que aquesta correlació no es detecta en les subfinestres on hi ha qualsevol altre objecte o part d’objecte que no sigui una cara.

Aquests classificadors no reben directament la subfinestra de la imatge, sinó un conjunt de característiques (normalment és un vector de nombres reals) extretes d’aquesta subfinestra de la imatge. Hi ha diversos mètodes per a generar aquestes característiques. Els més usats són les característiques de Haar proposades per Viola i Jones l’any 2001. Un altre mètode és el d’extreure les característiques amb els filtres de Gabor. A continuació, descriurem les característiques de Haar.

Les característiques de Haar (figura 3) estan formades per quatre imatges de dimensions diverses amb formes rectangulars bicolors.

Figura 3. Les quatre característiques bàsiques de Haar

F_i(I_j)=a_i^j

Quan s’ubica una característica de Haar sobre una subfinestra, els píxels de la subfinestra que cauen sobre la part blanca se sumen i els píxels de la subfinestra que cauen sobre la part negre es resten. El valor final d’aplicar un filtre concret en una posició concreta és el valor resultant de sumar les parts blanques i restar-hi les parts negres.

Cada tipus es pot concretar en una figura segons els paràmetres següents:

Ubicació de la característica de Haar_i en la imatge (x, y). Normalment, el centre de coordenades dels píxels de la imatge original, i també la subfinestra on s’aplica Haar, està localitzat a l’extrem inferior esquerre i les coordenades comencen pel punt (0, 0).
Diferents dimensions horitzontals i verticals (h, w) de la característica de Haar_i.

És a dir, que donada una subfinestra aplicarem Haar_i(x, y, h, w) i retornarà un valor enter.

Exemple

Donada aquesta petita imatge original de 6 × 6:

23	56	67	78	56	32
23	55	12	90	234	105
245	211	178	190	176	87
23	54	78	189	232	190
23	123	239	123	56	32
203	23	29	12	116	132

Haar₂(1, 1, 4, 4) retorna el valor −(55 + 12 + 211 + 178 + 54 + 78 + 123 + 239) + (90 + 234 + 190 + 176 + 189 + 232 + 123 + 56) = −950 + 1.290 = 340

Per tant, el vector d’entrades del classificador de Bayes està format pels quatre tipus de característiques en posicions diferents i dimensions diferents. Hi ha moltes combinacions possibles, per això, s’ha de decidir un subconjunt.

Un cop tenim convertida la subfinestra en un vector de n característiques x, explicarem com muntem un classificador de Bayes. Primer de tot, hem de deduir quina és la probabilitat que el valor de la i-èsima característica concreta sigui de la classe “cara”

P_{i}^{c} (x_{i})

i també que sigui de la classe “no-cara”

P_{i}^{n c} (x_{i})

. Un cop tinguem aquestes probabilitats, assumirem que són independents entre elles i llavors considerem que una mostra x és de classe “cara” o de classe “no-cara” segons el producte de probabilitats de totes les característiques de la manera següent:

La mostra x és “cara” si

\prod_{i = 1}^{n} P_{i}^{c} (x_{i}) > \prod_{i = 1}^{n} P_{i}^{n c} (x_{i})

. Altrament, és “no-cara”.

Ara ens queda comentar com calculem les probabilitats

P_{i}^{c} (x_{i})

P_{i}^{n c} (x_{i})

. En el mètode de Bayes, aquestes probabilitats és diuen probabilitats a posteriori i es calculen a partir d’altres probabilitats marginals i condicionals. La probabilitat a posteriori de la classe “cara” es defineix:

P_{i}^{c} (x_{i}) = \frac{P (x_{i} | " c a r a ") \cdot P (" c a r a ")}{P (x_{i})} 4.1

De manera similar, la probabilitat a posteriori de la classe “no-cara” es defineix:

P_{i}^{n c} (x_{i}) = \frac{P (x_{i} | " n o c a r a ") \cdot P (" n o c a r a ")}{P (x_{i})} 4.2

Les probabilitats condicionals

P (x_{i} | " c a r a ")

P (x_{i} | " n o c a r a ")

s’anomenen probabilitats a priori i són la funció de possibilitat (likelihood) de la classe “cara” i de la classe “no-cara”, respecte del valor

x_{i}

de la i-èsima característica. Les probabilitats de les classes

P (" c a r a ")

P (" n o c a r a ")

són la probabilitat a priori de la classe “cara” i de la classe “no-cara”. La probabilitat que aquesta mostra

x_{i}

aparegui,

P (x_{i})

, es calcula amb el teorema de la probabilitat conjunta:

P (x_{i}) = P (x_{i} | " c a r a ") \cdot P (" c a r a ") + P (x_{i} | " n o c a r a ") \cdot P (" n o c a r a ") 4.3

Només ens queda definir les probabilitats de les classes i les probabilitats a priori. Normalment, es considera que hi ha la mateixa probabilitat que a la subfinestra aparegui una cara o que no hi aparegui. Per aquest motiu, es pot assumir que:

P (" c a r a ") = P (" n o c a r a ") = 1 / 2 4.4

Amb la definició d’aquestes probabilitats, podem redefinir la fórmula general de la probabilitat a posteriori per a les dues classes de la manera següent:

P_{i}^{c} (x_{i}) = \frac{P (x_{i} | " c a r a ")}{P (x_{i} | " c a r a ") + P (x_{i} | " n o c a r a ")} 4.5

P_{i}^{n c} (x_{i}) = \frac{P (x_{i} | " n o c a r a ")}{P (x_{i} | " c a r a ") + P (x_{i} | " n o c a r a ")} 4.6

Aquesta funció ens indica que per a considerar que un element sigui de tipus “cara” (o “no-cara”) és important que la seva probabilitat a priori sigui alta, però també és important que la probabilitat a priori de l’altra classe sigui baixa.

Ara definirem les probabilitats a priori. Primer comencem per la probabilitat de ser classe tipus “cara”. Donat el conjunt de k subfinestres que sabem que hi ha una cara, calcularem els vectors de les seves n característiques i obtenim el conjunt de vectors

{a^{1}, a^{2}, \dots, a^{k}}

, en què:

a^{j} = [a_{1}^{j}, \dots a_{n}^{j}] 4.7

L’element

a_{i}^{j}

és el valor de la característica i-èsima de la mostra j-èsima que sabem que hi ha una cara. Aquesta característica es calcula amb una funció Haar aplicada a la mostra j-èsima amb uns paràmetres (x, y, h, w) concrets. Amb aquests vectors de característiques calcularem el valor mitjà de cada característica:

μ_{i}^{c} = \frac{1}{k} \sum_{j = 1}^{k} a_{i}^{j} 4.8

i també la seva desviació estàndard:

σ_{i}^{c} = \sqrt{\frac{1}{k - 1} \sum_{j = 1}^{k} {(a_{i}^{j} - μ_{i}^{c})}^{2}} 4.9

Llavors, assumim que aquestes característiques es poden aproximar per una funció normal i obtenim la probabilitat a priori de ser cara donada la mostra següent:

P (x_{i} | " c a r a ") = \frac{1}{σ_{i}^{c} \sqrt{2 π}} e^{\frac{- {(x_{i}^{} - μ_{i}^{c})}^{2}}{2 {(σ_{i}^{c})}^{2}}} 4.10

La figura 4 mostra de manera gràfica l’obtenció de la desviació estàndard i la mitjana de cada característica donades les imatges de la classe “cara”. En la matriu hi ha tantes columnes com imatges de cares i tantes files com filtres Haar s’hagin aplicat depenent dels cinc paràmetres de la funció Haar_i(x, y, h, w). En la figura es mostren quatre possibles valors del paràmetre i, i no es concreten els altres quatre paràmetres.

Figura 4. Extracció de la desviació estàndard i la mitjana donades les imatges de cares i cada combinació del filtre de Haar

El procés per a calcular la probabilitat de classe “no-cara” és similar al descrit amb la classe “cara”. De la mateixa manera, calcularem els vectors

{b^{1}, b^{2}, \dots, b^{k}}

que representen el mateix i es calculen de la mateixa manera que els vectors

{a^{1}, a^{2}, \dots, a^{k}}

però les mostres inicials són de subfinestres de la classe “no-cara”. Amb aquests vectors de característiques calcularem el valor mitjà de cada característica:

μ_{i}^{n c} = \frac{1}{k} \sum_{j = 1}^{k} b_{i}^{j} 4.11

i també la seva desviació estàndard:

σ_{i}^{n c} = \sqrt{\frac{1}{k - 1} \sum_{j = 1}^{k} {(b_{i}^{j} - μ_{i}^{n c})}^{2}} 4.12

Llavors, assumim que aquestes característiques es poden aproximar per una funció normal i obtenim la probabilitat de no ser cara donada la mostra:

P (x_{i} | " n o c a r a ") = \frac{1}{σ_{i}^{n c} \sqrt{2 π}} e^{\frac{- {(x_{i}^{} - μ_{i}^{n c})}^{2}}{2 {(σ_{i}^{n c})}^{2}}} 4.13

Exemple

En subfinestres de 24 × 24, es pot obtenir un vector de vuitanta valors. És a dir, vint combinacions diferents per a cada tipus de Haar. Si fem filtres de Haar de 6 × 6, llavors en podem posar setze. I si també considerem filtres de Haar de 12 × 12, llavors en podem posar quatre. Lògicament, es poden posar moltes altres combinacions, per exemple, i acceptar solapament entre filtres o que no hagin de ser quadrats.

La figura 5 mostra una fotografia en què s’han detectat automàticament les cares. Fixeu-vos que apareixen dos tipus d’errors de detecció que són semblants als errors comentats en el mòdul “Avaluació dels sistemes biomètrics en aplicacions reals”. Algunes cares no han estat detectades: fals rebuig⁽⁸⁾ i algunes parts que no són cares han estat considerades cares: falsa acceptació⁽⁹⁾. Tanmateix, el nombre d’acceptacions correctes⁽¹⁰⁾ és molt superior als errors.

Figura 5. Fotografia en què s’han detectat les cares de manera automàtica

3.Normalització de la cara

Com hem remarcat, els mètodes basats en l’aparició operen en subfinestres de mida fixa. Per aquest motiu, és necessari ajustar la mida de totes les finestres a una mida estàndard, per exemple 20 × 20. Això es deu al fet que els mètodes que comentarem més endavant per al reconeixement de cares necessiten tenir un nombre de píxels concret. A més a més, el mètode de Haar pretén ser independent als canvis d’il·luminació. Per això, és necessari un procés posterior de normalització de les subfinestres en què s’ha detectat la cara segons la seva intensitat. Si aquest procés no es fes, el reconeixement de cares es podria dur a terme però no funcionaria tan bé. Aquestes operacions són globals des del punt de vista que tots els píxels de la subfinestra es modifiquen.

3.1.Normalització de les dimensions de la subfinestra

Normalment, les subfinestres són quadrades ja que les cares es poden enquadrar bastant bé en un quadrat. Suposem que la subfinestra que ha detectat la cara té unes dimensions de (l₁, l₁) i nosaltres volem que totes les subfinestres en què hi ha possibles cares tingui unes dimensions de (l₂, l₂). Cada píxel de la subfinestra nova adoptarà el valor:

I_{2} (x, y) = I_{1} (| x \cdot \frac{l_{1}}{l_{2}} |, | y \cdot \frac{l_{1}}{l_{2}} |) 4.14

Les dimensions normalitzades acostumen a ser les de la finestra més petita. Això és així perquè si no ens trobaríem que hauríem d’omplir alguns píxels de la nova subfinestra de manera artificial, ja que alguns píxels de la finestra nova no serien omplerts per cap píxel de la finestra original. Un altre mètode més intel·ligent per a omplir les noves posicions es basa a trobar la mitjana ponderada dels píxels del voltant. Aquest mètode és el més usat quan es modifiquen les dimensions d’imatges encara que té l’inconvenient que té un efecte de filtratge.

3.2.Normalització de la intensitat de la subfinestra

Hi ha diverses tècniques per a normalitzar la imatge des d’un punt de vista de la intensitat. Aquí comentarem el mètode basat en l’equalització de l’histograma. Aquest mètode es basa a augmentar el contrast de la imatge ajustant els valors de l’histograma. Amb aquest ajustament, les intensitats dels píxels es distribueixen més equitativament en l’histograma. Primer haurem de calcular la intensitat de píxel mínima, v_mín, i màxima, v_màx. És a dir, els valors dels píxels de partir dels quals cap píxel de la imatge no té un valor inferior o superior (de vegades, en lloc de “cap” es considera un nombre petit). Llavors, aplicarem una transformació global a tots els píxels de la imatge segons l’equació:

I_{2} (x, y) = \frac{I_{1} (x, y) - V_{m i n}}{V_{m a x} - V_{m i n}} \cdot M A X 4.15

en què MAX representa el valor màxim possible del píxel (habitualment és de 255).

Aquesta transformació de la imatge implica que l’histograma resultant omple tot el rang possible de valors. La figura 6 mostra una imatge original i la mateixa imatge l’histograma de la qual s’ha equalitzat. També es mostra l’histograma original i l’histograma equalitzat.

Figura 6. Imatge equalitzada

a. Imatge original. b. Imatge tractada. c. Histograma abans del procés. d. Histograma equalitzat

4.Extracció de les característiques

Una imatge es pot veure com un punt en un espai discret que té tantes dimensions com píxels té la imatge i el nombre de valors de cada dimensió és la profunditat del píxel (normalment 256 × 3 canals; vermell, verd i blau).

Fixeu-vos que aquest espai és enorme. Suposem una càmera web de baixa resolució (640 × 480). Això vol dir que el nostre espai té 307.200 dimensions i cada dimensió està discretitzada en 256 × 3 valors.

Exemple

Imaginem-nos una càmera de resolució molt, molt baixa. Tan baixa que les imatges que fa només tenen dos píxels. En aquest cas, les imatges es poden definir en un espai de dues dimensions. La dimensió x₁ representa el píxel p₁ i la dimensió x₂ representa el píxel p₂. Com que aquesta càmera de dos píxels fa només fotografies en escala de grisos, ens trobem que la profunditat dels píxels és de 256 i, llavors, les dimensions d’aquest nou espai discret és de 256 posicions. Suposem que fem dues fotos amb aquesta càmera: imatge₁ =

[35 | 221]

. Això vol dir que el valor del píxel p₁ = 35 i el valor del píxel p₂ = 221. I la segona foto és imatge₂ =

[150 | 23]

. Si representem aquestes fotografies en el nou espai tindrem (figura 7):

Figura 7. Representació de dues fotografies fetes amb una càmera de només dos píxels i amb escala de grisos

El mètode que aquí comentarem considera aquest espai i intentarem reduir el nombre de dimensions d’aquest espai. Normalment, es porta a terme una reducció dràstica ja que s’acostuma a passar de 307.200 dimensions a unes 7 dimensions. Aquesta reducció es pot dur a terme per dos motius principals:

1) Només una petita zona d’aquest espai enorme és la que conté imatges amb cares.

2) Es duu a terme una transformació de l’espai i aquest espai nou on anem a parar és l’espai de la covariància entre els píxels de les imatges.

Portarem a terme la reducció amb el mètode d’anàlisi dels components principals (PCA) que s’explica més endavant.

En aquest nou espai podem analitzar quines fotografies han estat fetes a cares, quines no i, fins i tot, podem agrupar les fotos de cares depenent de la persona. D’aquesta manera, ens podria quedar un espai com el que mostra la figura 8.

Figura 8. Espai bidimensional en què es representa la zona on hi ha fotografies de cares i, dins d’aquesta zona, on hi ha les cares de dues persones

Com que en aquest espai és difícil separar de manera lineal les zones on hi ha cares de les persones, transformem aquest espai en un espai en què es considera la variabilitat entre els píxels, és a dir, la variabilitat entres les coordenades d’aquest espai nou.

L’anàlisi dels components principals (PCA) és una tècnica de reducció de les dimensions de l’espai basada a obtenir només un nombre imposat com a paràmetre d’entrada de components principals de dades multidimensionals.

El primer component principal és la combinació lineal de les dimensions originals que té la màxima variància. L’n-èsim component principal és la combinació lineal amb la màxima variància i amb la restricció que ha de ser ortogonal als n − 1 primers components principals.

La idea de la PCA s’il·lustra en la figura 9. Els eixos

x_{1}

x_{2}

representen la covariància entre dos píxels.

\emptyset^{1} (x_{1}, x_{2})

correspon a la direcció de la màxima variància i, per tant, s’escull com a primer component principal. En el cas de dues dimensions, el segon component principal,

\emptyset^{2} (x_{1}, x_{2})

, es determina unívocament per les restriccions d’ortogonalitat. En espais de més dimensions, la selecció de components continuaria, guiada per les variàncies de les projeccions. Si es volgués reduir l’espai a una sola dimensió, llavors posaríem tots els punts a la línia formada per l’eix

\emptyset^{1} (x_{1}, x_{2})

i imposaríem

\emptyset^{2} (x_{1}, x_{2}) = 0

en aquest nou espai

(\emptyset^{1}, \emptyset^{2})

com mostra la figura 9.

Figura 9

a. Representació dels dos eixos principals. b. Reducció a una sola dimensió

Per a trobar aquests nous eixos, usarem la tècnica de la transformació de Karhunen-Loève. No obstant això, per tal d’usar aquesta tècnica, hem de suposar que la mitjana de les dades és zero. Aquesta imposició no és cap inconvenient, ja que l’únic que ens exigeix és que inicialment restem la mitjana de les cares a totes les cares.

Suposem que les imatges de les cares tenen m × n píxels. Llavors, descrivim cada imatge com un vector v de N = m · n elements, simplement concatenant les columnes de la imatge per formar el vector. v_i representa el valor de la posició i-èsima del vector v. En la figura 10 mostrem una cara i el vector transposat que es genera (normalment, els vectors es representen de manera vertical).

Figura 10. Cara i vector transposat

a. Imatge de 16 × 16 píxels. b. Vector transposat que representa la imatge

També suposem que tenim M imatges diferents de la mateixa cara o persona. La cara j-èsima es descriu pel vector v^j. La posició i-èsima del vector v^j es descriu amb el símbol

v_{i}^{j}

. El primer que hem de fer és tornar a calcular els vectors de les cares de manera que la mitjana dels nous vectors

x^{j}

sigui zero. Cadascuna de les posicions del vector mitjana es defineix:

\bar{v_{i}} = \frac{1}{M} \sum_{j = 1}^{M} v_{i}^{j} 4.16

Aquest vector representa la cara mitjana, és a dir, com si les imatges fossin transparències i les poséssim totes en un munt. Llavors, els vectors normalitzats s’obtenen sostraient-ne la mitjana:

x_{i}^{j} = v_{i}^{j} - \bar{v_{i}} 4.17

per a tot

1 \leq i \leq N

i per a tot

1 \leq j \leq M

. La variable

x_{i}^{j}

representa el valor normalitzat de la posició i-èsima de la imatge j-èsima.

Amb aquest conjunt de vectors normalitzats formarem una matriu X de N files i M columnes:

X = [\begin{matrix} x_{1}^{1} & \dots & x_{1}^{M} \\ ⋮ & ⋱ & ⋮ \\ x_{N}^{1} & \dots & x_{N}^{M} \end{matrix}] 4.18

Volem estudiar la variabilitat entre els píxels que componen el conjunt de les imatges de la cara d’una mateixa persona. Per exemple, estudiar si sempre que un píxel augmenta de color, també augmenta el color d’un altre píxel. En cas que la imatge no sigui de la mateixa persona, assumim que aquesta variació concreta no serà tan important i així detectarem que no és la mateixa persona. Com que el que volem és estudiar la variabilitat entre les dades, amb la matriu X calcularem la matriu de covariància Σ de N × N dimensions de la manera següent:

{\sum^{​}}^{​} {^{​}}_{[_{i, j}]} = \frac{1}{M} {\sum^{​}}^{​}_{K = 1}^{M} x_{i}^{k} \cdot x_{j}^{k} 4.19

per a tot i, j d’1 a N.

En aquesta equació, hem assumit que els vectors que representen les cares són verticals. Fixeu-vos que el còmput de la covariància és molt senzill perquè les dades han estat normalitzades prèviament i la mitjana ja ha estat sostreta. La matriu de covariància es pot calcular de manera vectorial:

{\sum^{​}}^{​}_{[_{i, j}]} = \frac{1}{M} {(x^{i})}^{^{t}} · x^{j} 4.20

t representa la funció transposada, és a dir, que genera un vector horitzontal.

Un cop calculada la matriu de covariància, calcularem els vectors propis

\emptyset = [\emptyset^{1}, \dots, \emptyset^{N}]

i els valors propis

λ = [λ^{1}, \dots, λ^{N}]

. Cada vector propi

\emptyset^{i}

té N elements. Fixeu-vos que els vectors propis són els nous eixos representats en la figura 9. I els valors propis representen la variabilitat de les dades projectades en l’espai de vectors propis. Els vectors propis i valors propis s’ordenen de manera que:

λ^{1} \geq λ^{2} \geq \dots \geq λ^{N} 4.21

És a dir, que el vector propi

\emptyset^{i}

correspon a l’i-èsim valor propi

λ^{i}

més gran.

Finalment, la cara de la persona p-èsima, que a la base de dades original era representada per M imatges de N = m × n píxels, aquí es representa amb una matriu i dos vectors. La matriu de N × K elements són els K primers vectors propis

\emptyset^{p} = [\emptyset^{1^{p}}, \dots, \emptyset^{k^{p}}]

. I el primer vector està format pels K valors propis

λ^{p} = [λ^{1^{p}}, \dots, λ^{k^{p}}]

. Si K és exactament N, llavors no hi haurem aplicat cap tipus de reducció de les dades. Com més petit sigui K, menys ocupa la representació de cada persona però més probabilitat hi haurà que el sistema de reconeixement s’equivoqui. I el segon vector és la mitjana de les cares usades per a generar el model

{\bar{v}}^{p} = [{\bar{v}}^{1^{p}}, \dots, {\bar{v}}^{N^{p}}]

. Aquest vector sempre és de N elements. La representació de la persona p quedarà, doncs:

\emptyset^{p} = [\begin{matrix} \emptyset_{1}^{1^{p}} & \dots & \emptyset_{1}^{k^{p}} \\ ⋮ & ⋱ & ⋮ \\ \emptyset_{N}^{1^{p}} & \dots & \emptyset_{N}^{k^{p}} \end{matrix}]

en què

\emptyset_{i}^{q^{p}}

representa l’element i del vector propi q-èsim de la persona p amb una compressió de K vectors propis, i és

K \leq M

λ^{p} = [λ^{1^{p}}, \dots, λ^{k^{p}}]

en què

λ^{q^{p}}

representa el valor propi q-èsim més gran de la persona p. El vector q-èsim es relaciona amb el valor propi q.

{\bar{v}}^{p} = [{\bar{v}}^{1^{p}}, \dots, {\bar{v}}^{N^{p}}]

en què

{\bar{v}}^{i^{p}}

representa la mitjana del píxel i-èsim de totes les imatges usades per a modelar la persona p.

Resum dels índexs:

i: posició de l’element dins dels vectors. $i \in [1, \dots, N]$
j: índex que identifica una cara d’una persona concreta. $j \in [1, \dots, M]$
p: índex que identifica una persona. $p \in [1, \dots, Z]$
q: índex que identifica un vector propi i un valor propi. $q \in [1, \dots, K]$

La figura 11 mostra la cara mitjana de la persona p,

{\bar{v}}^{p}

, a l’esquerra. I els set primers vectors propis

\emptyset^{1^{p}}, \dots, \emptyset^{7^{p}}

de la persona p. Els vectors propis s’acostumen a anomenar eigenfaces⁽¹¹⁾ i es tradueix com a eigencares.

Figura 11. Representació d’una persona a partir de la seva mitjana i els set vectors propis

5.Verificació d’una cara

Suposem que tenim una imatge nova d’una cara en format de vector v i la representació de la persona p expressada de la manera que hem descrit en l’apartat anterior. Volem saber si aquesta imatge és de la persona P.

El procés de verificació farà els passos següents:

1) Normalitzar les dades. Obtenim el vector

x

a partir del vector imatge

v

del qual hem extret el vector mitjana

{\bar{v}}^{p}

de la persona p. Per tant:

x = v - {\bar{v}}^{p} 4.22

2) Apliquem un canvi de base a aquest vector x en què la nova base són els vectors propis

\emptyset^{p}

i obtenim la mateixa dada w, que es coneix com a pesos, però en les noves coordenades. El vector w és de k elements i es calcula:

w = {(\emptyset^{p})}^{t} \cdot x 4.23

El superíndex t representa la matriu transposada. Gràficament en la figura 12.

Figura 12

3) Calcularem la distància euclidiana entre els pesos obtinguts w i els valors propis de la persona p,

λ^{p}

. Formalment:

d^{p} (v) = \sqrt{\sum_{q = 1}^{k} {(λ^{q^{p}} - w^{q})}^{2}} 4.24

4) Finalment, si el valor obtingut és inferior a un llindar T imposat per l’administrador del sistema, considerarem que la cara v pertany a la persona p. Si

d^{p} (v) < T

llavors retorna SÍ. Altrament, retorna NO.

6.Identificació d’una cara

Com s’ha explicat en el mòdul “La biometria per a la identificació de les persones”, per identificar una persona, s’han de comparar les seves dades amb les dades de la base de dades. Ja hem dit que hi ha mètodes que permeten evitar algunes comparacions i no explorar tota la base de dades. No és l’objectiu d’aquesta assignatura parlar de temes de bases de dades, per això, suposarem que realment s’exploren tots els registres de la base de dades.

Suposem que tenim una imatge nova d’una cara en format de vector v que volem identificar i també suposem que tenim una base de dades de cares amb Z persones i que de cada persona hem extret les dades explicades en l’apartat “Extracció de les característiques”. El procés d’identificació farà els passos següents:

1) Per a totes les persones p inscrites a la base de dades, calcularem la distància entre la cara representada pel vector v i la representació de les persones,

d^{p} (v)

. Obtindrem un vector de distàncies:

D = [d^{1} (v), \dots, d^{p} (v), \dots, d^{z} (v)] 4.25

2) Reordenarem el vector D de menys a més i generem el vector:

D' = [d'^{1} (j, v), \dots, d^{'}^{e} (i, v), \dots, d'^{z} (t, v)] 4.26

Mantindrem la informació de cada distància a quina persona corresponia, ja que:

d'^{e} (i, v) = d^{i} (v) 4.27

en què la distància

d^{i} (v)

és l’e-èsima més petita.

3) Retornarem la identificació de les E primeres persones amb distància més petita. En alguns casos, només es vol saber la persona que més s’assembla, llavors E = 1. Però en algunes aplicacions, és habitual no ser tan restrictiu, i E pot variar, per exemple E = 10.

7.Generació de cares

Donada una fotografia d’una persona, la podem projectar sobre els models de components principals i després recuperar aquesta nova persona amb la informació de covariància de l’altra persona. La imatge obtinguda s’acostuma a anomenar imatge recuperada R. El procés s’anomena generació de cares. Aquest procés es compon de dues etapes:

1) Projectem la cara a l’espai de covariàncies.

2) Tornem a projectar les dades obtingudes a l’espai de les imatges.

Aquest procediment s’usa en dues situacions diferents. En la primera situació, volem generar una nova cara amb la informació de la persona que vulguem. És similar a imposar els trets característics d’una persona a una altra persona. La segona situació apareix quan tenim imatges amb molt de soroll o amb oclusions parcials.

Si v és el vector que representa la imatge de la persona

p^{1}

i volem generar una imatge recuperada de la cara R (R és un vector de N posicions) com si fos la persona

p^{2}

, els passos són els següents:

1) Normalitzar les dades. Obtenim el vector x a partir del vector imatge v de la persona

p^{1}

del qual hem extret el vector mitjana

{\bar{v}}^{p^{1}}

de la persona

p^{1}

2) Apliquem un canvi de base a aquest vector x, en què la nova base són els vectors propis

\emptyset^{p^{1}}

. Fins a aquest punt, l’únic que hem fet és convertir la imatge de la cara v a l’espai de les covariàncies. Es calcula:

w = {(\emptyset^{p^{1}})}^{t} \cdot x 4.28

El superíndex t representa la matriu transposada. Gràficament en la figura 13.

Figura 13

3) Ara, el que farem és obtenir el vector de la imatge recuperada R tornant a la base original però a partir dels vectors propis de la persona

p^{2}

i sumant la mitjana de la persona

p^{2}

. És a dir:

R = \emptyset^{p^{2}} \cdot w + {\bar{v}}^{p^{2}} 4.29

Gràficament en la figura 14.

Figura 14

En cas que

p^{1} = p^{2}

i quan no s’ha portat a terme reducció de vectors propis, k = N, llavors el resultat final és exactament la imatge original. En cas que k sigui inferior a N, llavors hi ha pèrdua d’informació, ja que la base dels vectors propis és de dimensió més petita. En aquest cas, la imatge original no és la mateixa que la recuperada. Però aquest fet, de vegades, és positiu, perquè serveix per a extreure la informació més “important”, la que té més covariància.

Si agrupem tots els passos en una sola equació matemàtica, tenim:

R = \emptyset^{p^{1}} \cdot {(\emptyset^{p^{2}})}^{t} \cdot x + {\bar{v}}^{p^{1}} 4.31

Gràficament en la figura 15.

Figura 15

En cas que volguéssim recuperar una imatge d’una mateixa persona, llavors

p = p^{1} = p^{2}

; per tant:

R = \emptyset^{p} \cdot {(\emptyset^{p})}^{t} \cdot x + {\bar{v}}^{p} 4.32

Les primeres imatges de la figura 16 mostren la cara d’una persona el punt de vista de la qual ha anat canviat. L’última imatge és la imatge mitjana. Fixeu-vos que en totes les imatges se’n poden veure els ulls.

Figura 16

a. Diverses imatges d’una persona. b. Imatge mitjana d’una persona

La imatge esquerra de la figura 17 mostra una imatge nova. Amb aquesta imatge, que té els ulls tancats, volem generar una imatge amb els ulls oberts. Usant la informació de les altres imatges i aplicant el sistema de generació d’imatges obtenim la imatge dreta de la figura 17.

Figura 17

a. Imatge usada per a la generació automàtica. b. Imatge resultat

La figura 18 mostra les eigenfaces ordenades segons la magnitud del vector propi. Fixeu-vos que la primera eigenface destaca el moviment de rotació del cap (píxels més clars).

Figura 18. Eigenfaces ordenades segons el valor propi

Nota

Aquest pas es pot dur a terme perquè la matriu inversa de la matriu transposada d’una matriu ortogonal és la mateixa matriu:

M = {(M^{'})}^{t} 4.30

Els superíndex t i ’ representen les matrius transposada i inversa, respectivament.

Resum

En aquest mòdul hem explicat algunes tècniques relacionades amb la identificació de les persones per les seves cares. La cara és el tret biomètric més usat pels humans per a identificar les persones, per això és extensament acceptat per la societat. Aquest fet ha influenciat de manera notable la posada en marxa d’aplicacions civils basades en el reconeixement de la cara. A més, el sensor per a capturar cares no és res més que una màquina de fer fotografies i tothom en té una i tothom està generant fotografies amb aquest dispositiu. Fixeu-vos que aquest és el motiu pel qual els sistemes d’identificació de persones com els que usen Picassa o iPhone tenen sentit. Si la gent no anés generant milers de fotografies i no les anés emmagatzemant, no tindríem el desig de cercar persones en les fotografies.

És important remarcar que la identificació de persones per les cares és un mètode no intrusiu i passiu. Per tant, no es demana a l’usuari que toqui res i s’evita així el rebuig de la societat a tocar aparells que d’altres toquen i s’eviten també possibles contagis. A més, el fet de ser passiu és usat per a identificar persones sense la seva col·laboració o, fins i tot, sense que se n’adonin.

No sols hem parlat d’identificar persones, sinó que gràcies a l’anàlisi dels components principals, hem aconseguit generar imatges noves amb cares. Aquesta és una aplicació útil per a reduir soroll en imatges o completar imatges de cares parcialment ocultes.

Finalment, per a explicar el procés d’identificació o verificació de cares ens ha fet falta explicar el classificador de Bayes, les característiques de Haar, i també l’anàlisi de components principals. Aquestes tècniques són àmpliament usades en molts altres sistemes i aplicacions.

Activitats

1. Descriviu les etapes del sistema de reconeixement de persones per la cara. Dibuixeu-ne l’esquema complet.

2. Poseu en funcionament el sistema de reconeixement de cares de Picassa, i si teniu un Mac, el de l’iPhone.

3. Com es diu el mètode que expliquem per a detectar cares? Per què creieu que es diu així? Creieu que és un mètode intel·ligent o és un mètode que usa “la força bruta”?

4. Com ho faríeu per definir un sistema que només detectés cares rient? O només cares de dones? O només cares d’una persona concreta?

5. Creieu que podríem definir altres característiques de Haar? Quina és la idea bàsica d’aquestes característiques? Com influencien els canvis d’il·luminació a aquestes característiques?

6. Imagineu-vos que volem fer un classificador de cares de dones i homes. Tenim dues opcions, una de les quals és fer dos classificadors. El primer detecta la classe “cara dona” i la classe “altres imatges”, i el segon detecta la classe “cara home” i la classe “altres imatges”. En cas que els dos classificadors prenguin la decisió que hi ha una cara en el mateix punt s’ha de prendre una decisió de quin classificador es considera el correcte. El segon mètode és crear un classificador directament que generi tres classes: “cara dona”, “cara home” i “altres imatges”. Podeu definir les probabilitats d’aquest classificador?

7. En la definició de les probabilitats hem suposat que es poden modelar usant una normal. Si fos el cas que no volguéssim aquesta modelització, com podríem definir aquestes probabilitats de manera que no fos necessari suposar cap tipus de model?

8. Detecteu acceptacions falses i rebutjos falsos en la imatge de la figura 5. En algunes acceptacions falses no es pot intuir la forma de cara. Per què creieu que pot haver generat aquesta acceptació falsa? I en el cas dels rebutjos falsos, per què creieu que no han detectat la cara?

9. Descriviu un algorisme en alt nivell que normalitzi tant les mides com la intensitat, donats els paràmetres necessaris.

Annex

La tècnica de l’anàlisi dels components principals (PCA) o transformació de Karhunen-Loève s’aplica en camps molts diversos. Té una base matemàtica molt forta que no hem analitzat en detall. En els vídeos següents s’explica la base matemàtica d’aquesta tècnica.

“Lec-32 Introduction to Principal Components and Analysis”. Neural Network and Applications (http://www.youtube.com/watch?v=H0HjNuNvFVI)

“Lec-33 Dimensionality reduction Using PCA”. Network and Applications (http://www.youtube.com/watch?v=HnVYF6VQryU)

Abreviatures

PCAPrincipal component analysis (‘anàlisi dels components principals’)

Bibliografia

Jain, Anil; Flynn, Patrick; Ros, Arun (editors) (2008). Handbook of biometrics. Editorial Springer.

Li i altres (2005). Handbook of face recognition. Editorial Springer.

23	56	67	78	56	32
23	55	12	90	234	105
245	211	178	190	176	87
23	54	78	189	232	190
23	123	239	123	56	32
203	23	29	12	116	132

23	56	67	78	56	32
23	55	12	90	234	105
245	211	178	190	176	87
23	54	78	189	232	190
23	123	239	123	56	32
203	23	29	12	116	132

Reconeixement de les persones pels trets de la cara

Francesc Serratosa

Introducció

Objectius

Annex

Abreviatures

23	56	67	78	56	32
23	55	12	90	234	105
245	211	178	190	176	87
23	54	78	189	232	190
23	123	239	123	56	32
203	23	29	12	116	132