Autofaces (Eigenfaces)

IMPA - Instituto Nacional de Matemática Pura e Aplicada

Disciplina: Álgebra Linear e Aplicações 2008

Autor: Eric Jardim {ejardim@impa.br}

Professor: Moacyr


pdf - código-fonte - demo space

Introdução

A idéia deste projeto é utilizar a decomposição espectral para reduzir as dimensões de um espaço vetorial de dimensão finita alta, investigando algumas possíveis aplicações.

Método

Suponha uma imagem em tons-de-cinza com dimensões horizontal e vertical    e   . Se imaginarmos que o a escala varia de 0 (preto) a 1 (branco), podemos mapear qualquer imagem com estas dimensões como um vetor de dimensão   , dentro do   .

As imagens que serão utilizadas são imagens de faces humanas. Iremos tirar proveito das semelhanças faciais entre indivíduos diferentes, capturando as principais feições humanas em um espaço de dimensão menor. De fato, estamos interessado em um   -eplisóide (  ) centrado em algum ponto de   . Este elipsóide é induzido por um subespaço afim que iremos chamar de espaço das faces.

Todas as aplicações seguem a etapa de estimação do espaço das faces. Vale lembrar que como estamos procurando semelhanças em imagens, para que o método funcione bem, é importante ter imagens de faces alinhadas, com tamanho semelhante e mesma iluminação. Se imaginarmos que uma face é a representação de uma amostra de evento aleatório (o qual queremos capturar), posição, tamanho e iluminação são variáveis complicam o nosso espaço de faces, aumentando a dimensão requerendo um maior número de amostras.

Sendo assim, tendo um conjunto    com    faces razoavelmente alinhadas e com pouca variação de iluminação, iremos estimar o espaço de faces a partir de uma face média

 


Iremos trabalhar com os vetores   . Feito isso, queremos encontrar um subespaço de dimensão menor   . Para tal, iremos correlacionar as dimensões utilizando a matriz de covariância em cima das amostras. Se dispusermos os vetores    em coluna na matriz   , então a matriz de covariância é

 


Queremos encontrar os autovetores    de    associados aos maiores autovalores. Quanto maior o autovalor, melhor o autovetor captura as propriedades do espaço. Quanto mais energia estiver concentrada nos primeiros autovetores, poderemos estimar o espaço das faces com um número menor de vetores.

Como    é uma matriz    e o número de amostra é em geral menor que o número de píxels (  ), podemos obter os autovetores    da matriz    que é quadraticamente menor (  ). Iremos mostrar que um autovetor    de    nos dá um autovetor    de   . Com efeito, se    é um autovetor de   

 


onde    é um vetor de   , e possuem o mesmo autovalor. Assim, os    autovetores de    nos dão os    maiores autovetores de   . Com isso, já temos uma primeira redução dimensional. Podemos ainda selecionar os    melhores autovetores para representar uma face no espeço das faces. Podemos agora definir    como sendo o nosso espaço de faces. Lembrando que    é um subespaço afim do espaço das imagens, logo, de fato    é o espaço afim das faces.

Por fim, para representar uma imagem qualquer    no espaço das faces basta escrever

 


onde    é a projeção da imagem na direção de    (estamos supondo    normalizado) e    é a projeção de    no espaço das faces. Dizemos que    são os coeficientes    no espaço das faces.

Aplicações

As seguintes aplicações são voltadas para imagens de faces, mas poderiam ser aplicadas a qualquer outro espaço de dimensão alta, com os devidos cuidados de cada problema.

Compressão

A aplicação mais óbvia de redução dimensional é a compressão de dados. É natural que o descarte de vetores acarreta na perda de informação. Contudo, descartar informação associada aos piores autovetores é perceptualmente melhor que um descarte em direções arbitrárias, pois os melhores autovetores concentram a maior parte da energia e logo a maior parte da informação, minizando o erro total.

Um conjunto de    imagens com    pixels ocupa    posições de memória. Se quisermos armazenar este mesmo conjunto com apenas    autovetores, precisamos guardar os    autovetores de dimensão    mais a face média e os    coeficientes de dimensão   , logo teremos um gasto de memória   . Vale lembrar que    tem que ser pequeno o suficiente para que haja compressão de fato.

Exemplo: se temos    imagens tem dimensão   , temos um gasto de aproximadamente   Mb. Mas se armazenarmos apenas    coeficientes, teremos um gasto de apenas   Mb.

Reconhecimento e busca aproximada

É mais eficiente realizar uma comparação em um espaço de dimensão menor. Além disso, sabendo de antemão quais direções são mais representativas, é possível ponderar as direções de forma a obter um resultado mais preciso. Dada uma face    com coeficientes    no espaço da imagem e sejam    um conjunto de faces conhecidas com coeficientes   , podemos definir uma distância intrínseca ao espaço entre duas faces

 


onde    é uma norma conveniente. Podemos usar a simples norma euclidiana, ou tirar proveito de já conhecer os autovalores e usar a norma de Mahalanobis

 


que é uma métrica elipsoidal, levando em conta a variação em cada autovetor. É possível utilizar esta métrica para decidir se uma determinada face é ou não alguma face já conhecida. É possível também utilizar um raio de pesquisa de forma a garimpar faces aproximadas.

Reconstrução de dados e redundância

Uma outra possível aplicação é a de reconstrução de um dado levemente modificado. É possível que uma determinada face foi parcialmente avariada devido há algum erro de armazenamento ou transferência. Em geral, o ruído acrescentado é distribuído em todas dimensões e afeta pouco   , visto que ele é bem menor que o espaço total. Logo, ao projetarmos a informação avariada num espaço de dimensão baixa, alta o suficiente para reconstruir o dado, é possível ter uma reconstrução satisfatória.

 


Outra possibilidade é armazenar o espaço de faces como redundância do dado, para posterior reconstrução, caso necessário.

Detecção

Por fim, podemos utilizar a projeção de uma imagem no espaço de face para determinar se tal imagem é uma face ou não.
Sabemos que o espaço de faces    é um subespaço de dimensão   , logo sabemos que    e podemos escrever qualquer imagem como

 



é razoável que esperar que uma imagem de face tenha valores baixos de   , que são os coeficientes dos vetores nas direções    que formam uma base de   .
Se    é a projeção de uma imagem   , podemos definir a distância extrínseca de uma imagem ao espaço de face por

 


supondo    uma base ortonormal de   .

Estimando um limiar conveniente baseado nas amostras de faces conhecidas, podemos utilizar esta medida como um detector de faces.

Referências

Turk, M. and Pentland, A. - "Eigenfaces for Recognition", Journal of Cognitive Neuroscience, vol. 3, no. 1, pp. 71-86, 1991