Reconhecimento de padrões — Eigenfaces

13 min readJun 12, 2019

Sobre este documento

Este é um relatório-trabalho desenvolvido para a matéria de Álgebra Linear Algorítmica, ministrada pelo professor João A. R. Paixão, do curso de Ciência da Computação da UFRJ.

O maior propósito deste trabalho é fornecer uma explicação sobre Análise de Componentes Principais (ACP) e exibir uma de suas aplicações — a obtenção de Eigenfaces.

Essa explicação possuirá formato que qualquer estudante de matemática (e cursos derivados) possam entender o seu uso sem, ter a necessidade de possuírem uma forte base matemática.

Na data da criação deste relatório e, consequentemente, apresentação deste trabalho, apenas abordarei a exibição dos contrastes obtidos pelos pesos dos eigenfaces, como também o método de Análise de Componentes Principais.

Em um futuro próximo, irei buscar aprender a fundo a aplicação da ACP no reconhecimento de rostos e outras etapas que podem ser envolvidas no processo:

Tratamento do dataset — recortando áreas de interesse das imagens e centralizando os rostos;
Detecção de faces — definindo uma área de interesse dinâmica para o reconhecimento do rosto. — possivelmente utilizando o algoritmo de Viola e Jones.
Reconhecimento de faces — reconhecer uma determinada face na área de interesse conforme banco de dados previamente cadastrado.
Criação de dataset em tempo de execução — Permitindo o cadastro de imagens do rosto de um indivíduo para futuro reconhecimento seu rosto.
Aplicações no mundo real — controle de acesso por reconhecimento, detecção de individuo não reconhecido em ambiente particular, login via reconhecimento de usuário, entre outros.

Introdução

Eigenfaces é o conjunto de autovetores de uma matriz de covariância formada por imagens de faces (rostos). Esta técnica foi desenvolvida por Sirovich e Kirby para representar padrões encontrados em imagens de rostos utilizando o método de Análise de Componentes Principais (sigla PCA em inglês).

Em 1991, Turk e Pentland, utilizaram esta representação para avaliar a distância entre rostos e “espaços de faces” para determinar quais rostos são similares. Em outras palavras, podemos utilizar este método para realizar o reconhecimento de rostos — dizer a quem um determinado rosto pertence baseado num banco de dados sobre esta pessoa previamente cadastrado.

Nota: Não confundir com “reconhecimento de faces” com “detecção de faces”.

Uma curiosidade

Enquanto realizava a pesquisa sobre este trabalho, relembrei de uma notícia que muitos anos atrás em que haviam pesquisado o rosto “médio” de determinadas países. Fiquei muito feliz e, até mesmo, bobo em pensar que estou aprendendo coisas que antes considerava “do futuro” ou até mesmo “do diabo”.

Rostos médios de mulheres em determinados países.

Antes de entrarmos na parte de Eigenfaces, é preciso entender o algoritmo de ACP, simplificando e explicando o máximo possível os conceitos matemáticos envolvidos: padronização, covariância, autovetores, autovalores, etc, antes de criarmos qualquer código.

Análise de Componentes Principais (ACP)

O ACP é um método de redução de dimensionalidade que é frequentemente utilizado para redução da dimensionalidade de um grande dat, transformando seu grande conjunto de variáveis em conjuntos menores, os quais possuem as maiores|mais importantes|mais significativas informações do dataset original.

Reduzindo o número de variáveis, não estou perdendo informação?

Sim e não! É claro que informações serão perdidas neste processo, mas acabamos perdendo pouca precisão em troca de um granho desproporcionalmente maior na simplicidade. Os datasets menores são mais fáceis de explorar e visualizar, tornando o processo de análise muito mais fácil e rápido para os algoritmos de Machine Learning.

Com este mesmo processo, também é possível obtermos redução de ruídos indesejados no conjunto de dados e, consequentemente, homogenizando ainda o dataset. A redução de dimensão sempre é feita naturalmente priorizando a preservação da informação que os dados nos traz.

Padronização

A padronização tem o objetivo padronizar (amenizar a diferença) do intervalo das variáveis, de forma que cada variável contribua o mais igualmente possível para a análise.

A principal razão de realizarmos esse tratamento antes da análise é que pode haver poucas variáveis com intervalos muito maiores que a maioria das variáveis. Por exemplo, podemos ter poucas variáveis com intervalos de [0, 100] e muitas variáveis com intervalos de [0, 1]. Neste caso, a minoria vai se sobrepor a maioria e isso pode resultar uma análise enviesada.

A padronização é feita subtraindo o valor da variável pela média dos valores das variáveis e dividindo este resultado pelo desvio-padrão.

Após a padronização, todas as variável são transformadas para a mesma escala, evitando, assim, qualquer enviesamento na análise.

Um boa explicação sobre a importância da importância da padronização num conjunto de dados pode ser obtida neste story no Medium do Towards Data Science.

Cálculo da Matriz de Covariância

A matriz de covariância busca estabelecer alguma relação (ou ausência de relação) entre as variáveis de um determinado dataset. Muitas variáveis podem estar altamente relacionadas a ponto de gerarem redundância nos dados.

A matriz de convariância é uma matriz simétrica NxN (matriz quadrada de tamanho N, onde N é o número de variáveis) que tem suas entradas de covariações associaadas com todos os pares de valores iniciais.

Por exemplo, um conjunto de dados tridimensional (com três variáveis, por exemplo: x, y e z) possui a matriz de covariância no seguinte formato:

Covariância de uma matriz tridimensional.

Precisamos ficar atentos a:

A covariância de uma variável por ela mesma é variância da própria variável:
Cov(a, a) = Var(a)
Consequentemente, A diagonal principal (superior esquerdo ao inferior direito) são as variâncias de todas as variáveis do sistema:
Cov(x, x) = Var(x)
Cov(y, y) = Var(y)
Cov(z, z) = Var(z)
A covariância possui uma propriedade comutativa, ou seja, Cov(a,b) = Cov(b,a):
Cov(x, y) = Cov(y, x)
Cov(y, z) = Cov(z, y)
Cov(z, x) = Cov(x, z)

E de acordo com o resultado, podemos considerar o seguinte:

Se positivo, então as duas variáveis crescem ou decrescem juntas (correlacionadas);
Se negativo, então uma das variáveis cresce enquanto a outra decresce (inversamente correlacionadas).

Cálculo dos autovetores e autovalores da Matriz de Covariância para identificar os principais componentes

Autovetores e autovalores são são os conceitos de álgebra linear que precisamos calcular a partir da matriz de covariância para determinar os principais componentes dos dados.

Principais componentes são as novas variáveis que são construídas através de combinações lineares da variáveis iniciais. Estas combinações são feitas de forma que as novas variáveis (principais componentes) não estejam correlacionadas entre si e a maior parte da informação inicial (variáveis iniciais) foram compactadas nos primeiros componentes.

Por exemplo, se tivermos um conjunto de dados de dimensão 10, os mesmos fornecem 10 componentes principais. No entanto, o APC tenta mover o máximo de informações para o primeiro componente, depois tenta mover o máximo das informações restantes para o segundo componente e assim por diante. No final, o dado terá uma aparência como o gráfico abaixo.

Após organizar as informações desta forma, podemos reduzir o número de dimensões de forma a não perdemos tanta informação, bastando remover os componentes com pouca informação (últimos).

Precisamos prestar atenção que os componentes principais são menos interpretáveis que as informações originais e não possuem nenhum significado real, pois foram combinações das variáveis iniciais.

Geometricamente falando, os componentes principais vão tratar o dado de uma forma generalizada, retornando a “direção dos dados”. Esta direção explica a quantidade máxima de variância, ou seja, as linhas (vetores) que capturam mais informações dos dados.

Por exemplo, se tivéssemos inicialmente um conjunto de dados 3D, aplicássemos o APC, alterando a dimensão para 2D, teríamos um conjunto de dados mais confortável de se trabalhar. Conseguiríamos enxergar melhor qualquer diferença nos dados.

Como o APC constrói os principais componentes?

Haverão muitos componentes principais em mesmo número que há de variáveis nos dados. Eles são construídos de forma que o principal componente possuíra a maior variância possível no conjunto de dados. Ou seja, ele possuirá o maior espaçamentos entre novos pontos obtidos pela redução de dimensão que originou ele.

O momento em que os pontos vermelhos estão mais espaçados é na linha é onde o principal componente reside.

Visualizando a imagem acima, percebemos que o primeiro componente principal (localizado nas retas rosas) não perdeu tanta informação (variância dos pontos em sua reta). O segundo componente principal está localizado ortogonalmente primeiro. Perceba que ele mantém muito menos informações (variância dos pontos em sua reta).

E os autovetores e os autovalores?

Autovetores são os vetores que não mudaram de direção após uma transformação. Entretanto, por mais que os vetores possam permanecer na mesma direção, eles podem mudar de intensidade|módulo|magnitude. Essas alterações são fatores (multiplicando o módulo original dos vetores) chamados de autovalores e estão relacionadas a cada autovalor.

Ou seja, eles sempre andam em pares. Para cada autovetor temos um autovalor. E suas quantidades serão iguais a dimensão , para qualquer matriz de dimensão N, teremos N autovetores e autovalores.

E onde eles entram no APC?

Os autovalores da matriz de covariância são as direções dos eixos onde possuem a maior variância (maior quantidade de informações) e que chamamos de componentes principais. E os autovalores fornecem a quantidade de variância transportada em cada componente principal.

Resumindo, ao classificarmos os autovetores e autovalores da matriz de covariância, do maior para o menor autovetor, obtemos os componentes principais em ordem de importância.

Nota: quando dizemos “maior autovetor” e “menor autovetor” estamos nos referindo, respectivamente, ao “autovetor com maior autovalor” e “autovetor com menor autovalor”.

Exemplo

Suponhamos que nosso conjunto de dados são bidimensionais, variáveis x e y, e que seus autovetores e autovalores da matriz de covariância são os seguintes:

Classificado os autovetores do maior para o menor, temos que λ1>λ2. O que significa que o autovetor v1 é o nosso componente principal (CP1) e que o vetor v2 é o segundo componente principal (CP2).

Para determinarmos o quanto a variância (informação) que cada componente principal possui, calculamos a porcentagem dividindo o autovalor relacionado a esse componente principal (autovetor) pela soma de todos os autovalores.

CP1 -> 96%
CP2 -> 4%

Agora, temos uma matriz de autovetores (e autovalores)

Podemos reduzir uma dimensão do nosso dado descartando o componente principal de menor importância (autovetor com menor autovalor da matriz de covariância).

Para o exemplo anterior, nossa matriz bidimensional:

Teria o segundo (e menos importante) componente descartado:

Reduzindo, assim, em uma dimensão.

Quanto de informação nós perdemos? 4%.
Quanto de informação foi mantida? 96%

Como vamos usar estes 96% de informação que não pode ser interpretada da mesma forma que os dados originais?

Sim. Da forma que eles se encontram, não servem de muita coisa pra gente.

Nós conseguimos reduzir a “nuvem de informação” em uma dimensão mantendo 96% de informação. Agora, temos que transformar estes 96% para o universo dos dados originais, com seus respectivos eixos, os quais poderiam ser interpretados.

Por fim, iremos multiplicar a transposta da matriz com os autovetores da matriz de covariância pelo conjunto de dados que foi padronizado.

O dataset final é o nosso dataset original reduzido em uma dimensão, mantendo uma boa porcentagem das informações relevantes.

E pasmem!

Eigenfaces

Eigenfaces são imagens que podem ser adicionadas a uma face média para criar novas imagens faciais. Sua fórmula matemática é:

F é uma nova face;
Fm é a face média;
Fi é uma eigenface;
αi é um escalar que nós multiplicamos para encontrar novas faces — podem ser positivas ou negativas.

As eigenfaces são calculadas estimando os componentes principais do conjunto de dados de imagens faciais. São utilizadas para aplicações de reconhecimento facial e detecção de bordas faciais.

Transformando imagens em vetores

Uma imagem colorida de tamanho 100 x 100 (largura e altura) pixeis pode ser representada por 3 matrizes de tamanho 100 x 100, onde cada matriz representa a concentração de cor em cada pixel: vermelho, verde e azul (sigla RGB em inglês).

Por exemplo, que temos uma imagem de tamanho 3 x 3 com as respectivas cores:

Imagem RGB e tamanho 3x3 (considere cada quadrado como um pixel).

A representação dessa imagem em matriz poderia ser três matrizes, onde cada um contém o quanto de concentração de verde, vermelho e azul possuem em cada pixel.

Representação da imagem em três matrizes separadas (RGB).

Podemos organizar todos estes valores em um único array — e é o que faremos. Encararemos qualquer imagem como sendo um array contendo todos estes dados.

Voltando ao primeiro exemplo, com uma imagem colorida de tamanho 100x100, poderíamos originalmente guardar em uma matriz onde cada elemento guardasse os três valores. Ficaria fácil para nós visualizarmos isso.

Agora, se tivéssemos que colocar essa imagem em um array de uma dimensão, teríamos 30k elementos no array. Ou seja, um espaço dimensional de 30 mil. Conseguíamos visualizar como o dado está armazenado da mesma forma de antes? Não, né?!

Entretanto, não é porque não conseguimos visualizar que não é que seja possível. Em Álgebra Linear aprendemos que o que normalmente vale pra uma, duas e três dimensões valem para todas as outras. Então vamos seguir com essa mesma convicção!

Calculando Eigenfaces

Seguiremos os seguintes passos para calcularmos as Eigenfaces:

Obtenção de um dataset de imagens faciais (de rosto) — Utilizaremos o dataset CelebA, fornecido pela Multimedia Labs, a Universidade Chinesa da Hong Kong.
Alinhar e formas as imagens — O ideal é que as imagens possuam o mesmo tamanho e que tenham os rostos alinhados no meio das imagens. Isso facilita a remoção de ruídos. Para nossa sorte, parte do dataset que utilizaremos já foi formatado. Utilizaremos cerca de 200 imagens.
Criação de uma matriz com todas as imagens — a criação da matriz contendo todas as imagens, onde cada imagem é uma linha na matriz.
Calcular o vetor médio —antes de executarmos o algoritmo da ACP nos dados, necessitamos subtrair o vetor médio. Está é uma tarefa opcional, pois o OpenCV já realiza este cálculo durante os procedimentos e a mesma não nos fornece o vetor para cálculo. Isto não acontece quando utilizamos bibliotecas de álgebra linear (Eigen, Lapack, PETSc, etc);
Calcular os componentes principais — Basta obtermos criarmos uma matriz com todos os autovetores da matriz de covariância do nosso conjunto de dados.
Formatar nossa matriz de autovetores para obtermos as Eigenfaces — neste ponto, teremos obtido autovetores do tamanho de 30k, contendo as imagens de tamanho 100x100x3. Nós podemos reformatar estes autovetores para este tamanho para obter as Eigenfaces.

Análise de Componentes Principais (CPA) através do OpenCV

A biblioteca de processamento de imagens OpenCV possui uma classe chamada PCA (Principal Components Analysis) , a qual realiza o cálculo dos componentes principais de uma matriz.

Nota: Documentação da classe PCA do OpenCV.

O uso dessa classe no Python pode ser feito da seguinte forma:

# Importamos o módulo do OpenCV
import cv2# Função simbólica para obtenção da matriz de imagens
matrix = readImageMatrix()# Uso da classe PCA
mean, eigenVectors = cv2.PCAComputer(matrix, mean=None, maxComponents=10)

Sobre os parâmetros da função:

matrix — é a matriz contendo todas as imagens, uma em cada linha;
mean — a média dos variáveis da matriz. Não fornecendo este, a classe PCA o calcula e retorna junto com os autovetores;
maxComponents — definindo quais dos mais importantes componentes principais queremos que seja calculado.

Resultados

Alterando o peso de alguns Eigenfaces geramos novos rostos.

Sobre o código

O código para a geração de eigenfaces é o código abaixo.

# Importando pacotes
import os
import sys
import cv2
import numpy as np
from glob import glob# Criando a matriz pela lista de imagens
def createDataMatrix(images):
    print("Criando a matriz com os dados ",end=" ... ")
    data = np.zeros((len(images), np.prod(images[0].shape)), dtype=np.float32)
    for i in range(0, len(images)):
        data[i,:] = images[i].flatten()
    print("TERMINADO")
    return data# Lendo as imagens do diretório
def readImages(path):
    print("Lendo as imagens do diretório {} ".format(path), end="...")
    
    # Lista para as imagens
    images = []
    
    # Iterando todas as imagens do diretório
    for imageFile in glob("{}/*jpg".format(path)):
        
        # Tentativa de leitura da iamgem
        im = cv2.imread(imageFile)
        if im is None:
            print("A imagem '{}' não pôde ser lida".format(imageFile))
        else :
            # Convertendo a imagem
            im = np.float32(im)/255.0
            # Adicionando a imagem para a Lista
            images.append(im)
            # Rotacioando a imagem
            imFlip = cv2.flip(im, 1);
            # Adicionando a imagem rotacionadada
            images.append(imFlip)
    
    # Caso nenhuma imagem seja lida, encerre o programa
    if not len(images):
        print("FATAL ERROR - Nenhuma imagem encontrada")
        sys.exit(0)# Exibindo a quantidade de imagens lidas
    print("{} arquivos lidos".format(int(len(images)/2)))
          
    return images# Adicionando os pesos para cada Eigenface
def createNewFace(*args):
    # Começando pela imagem média
    output = averageFace
    
    # Adicionando todas as Eigenfaces com os respectivos pesos
    for i in range(0, NUM_EIGEN_FACES):
        sliderValues[i] = cv2.getTrackbarPos("Peso" + str(i), "Eigenfaces e Pesos");
        weight = sliderValues[i] - MAX_SLIDER_VALUE/2
        output = np.add(output, eigenFaces[i] * weight)# Exibe os resultados com o dobro do tamanho
    output = cv2.resize(output, (0,0), fx=2, fy=2)
    cv2.imshow("Resultado", output)def resetSliderValues(*args):
    for i in range(0, NUM_EIGEN_FACES):
        cv2.setTrackbarPos("Peso" + str(i), "Eigenfaces e Pesos", int(MAX_SLIDER_VALUE/2));
    createNewFace()if __name__ == '__main__':# Quantidade de EigenFaces a serem gerados (considerados)
    NUM_EIGEN_FACES = 15# Peso máximo dos EigenFaces
    MAX_SLIDER_VALUE = 255# Diretório das imagens
    dirName = "images"# Lendo as imagens
    images = readImages(dirName)
    
    # Tamanho das imagens (todas possuem tamanhos iguais)
    sz = images[0].shape# Cria uma matriz para a ACP
    data = createDataMatrix(images)# Cálcula os EigenVectors
    print("Calculando ACP ", end="...")
    mean, eigenVectors = cv2.PCACompute(data, mean=None, maxComponents=NUM_EIGEN_FACES)
    print ("Finalizado")averageFace = mean.reshape(sz)eigenFaces = [];for eigenVector in eigenVectors:
        eigenFace = eigenVector.reshape(sz)
        eigenFaces.append(eigenFace)# Cria uma janela para exibir o rosto médio
    cv2.namedWindow("Resultado", cv2.WINDOW_AUTOSIZE)
    
    # Exibe as imagens com o dobro do tamanho
    output = cv2.resize(averageFace, (0,0), fx=2, fy=2)
    cv2.imshow("Resultado", output)# Janela para os sliders
    cv2.namedWindow("Eigenfaces e Pesos", cv2.WINDOW_AUTOSIZE)sliderValues = []
    
    # Cria os sliders
    for i in range(0, NUM_EIGEN_FACES):
        sliderValues.append(int(MAX_SLIDER_VALUE/2))
        cv2.createTrackbar("Peso" + str(i), "Eigenfaces e Pesos", int(MAX_SLIDER_VALUE/2), MAX_SLIDER_VALUE, createNewFace)
    
    # Clicando na imagem original, reseta os sliders.
    cv2.setMouseCallback("Resultado", resetSliderValues)cv2.waitKey(0)
    cv2.destroyAllWindows()