next up previous contents index
Next: Discriminantes Lineares (LDA) Up: Extração de características Previous: Redução de Dimensionalidade usando   Contents   Index


Análise de Componentes Principais (PCA)

Segundo Jain et al. [Jain et al., 2000], o melhor extrator de características linear conhecido é o de análise de componentes principais (PCA). Essa transformada, também conhecida como transformada de Hotelling e por expansão de Karhunen-Loève, é amplamente utilizada pela comunidade de reconhecimento de padrões e de reconhecimento de faces [Kirby and Sirovich, 1990,Turk and Pentland, 1991,Chellappa et al., 1995,Romdhani, 1996,Pentland, 2000].

Visando a tratar imagens como padrões em um espaço linear para efetuar reconhecimento estatístico, essas devem ser representadas de acordo com o conceito de padrão descrito na seção 2.1. Sendo $h$ o número de linhas de uma imagem e $w$ o número de colunas, pode-se dizer que uma imagem é um padrão de $h \times w$ características ou um vetor no espaço ($h \times w$)-dimensional, o qual chamaremos de ``espaço de imagens'', representado por $\mathcal{I}$.

Assim, dada uma imagem representada como uma matriz $h \times w$, pode-se construir sua representação como um vetor através de uma leitura coluna a coluna da imagem, colocando o valor de cada pixel da imagem em um vetor coluna ${\bf x}$. Ou seja, dada uma matriz $Z$ de $A$ linhas e $L$ colunas representando uma imagem,

\begin{displaymath}
{\bf x}^{l} = Z^{j, k},
\end{displaymath} (3.12)

para $j = 1, 2, 3, \cdots, h$, $k = 1, 2, 3, \cdots, w$ e $l = j + (k-1)
\cdot h$. Assim, a dimensionalidade do espaço de imagens $N$ é dada por $N = h \times w$.

A figura 3.2 ilustra didaticamente o processo de criação de um padrão ${\bf x}$ a partir de uma imagem de face3.1.

PCA_Sami.ps Processo de criação de um padrão ${\bf x}$ a partir de uma imagem (adaptada de [Romdhani, 1996]).

Dessa forma, a base canônica do espaço de faces pode ser ilustrada de acordo com a figura 3.3.

img_space.ps Base canônica do espaço de faces (adaptada de [Romdhani, 1996]).

Em reconhecimento de padrões, é sempre desejável dispor de uma representação compacta e de um bom poder de discriminação de classes de padrões. Para isso, é importante que não haja redundância entre as diferentes características dos padrões, ou seja, que não haja covariância entre os vetores da base do espaço de características. Mas, obviamente, pode-se notar que o espaço de imagens é altamente redundante quando usado para descrever faces, pois cada pixel é muito correlacionado com outros pixels, já que todas as faces possuem olhos, nariz, boca, bochecha, testa etc, o que faz com que os vetores que representam faces sejam altamente correlacionados.

Para verificar se há covariância entre as características (ou variáveis), utiliza-se a matriz de covariância $32$ da matriz dos padrões (de acordo com [Kennedy and Neville, 1986] e [Duda and Hart, 1973]). Dados $\forall {\bf x}_j \notin \omega_i$ padrões de treinamento, ${\bf x}_1, {\bf x}_2, \cdots, {\bf x}_{\vert T\vert}$, a matriz de covariância desses padrões é calculada a partir da matriz dos padrões de treinamento $X$. Ela é definida como uma matriz em que cada coluna possui um padrão de treinamento:

\begin{displaymath}
X = [{\bf x}_1, {\bf x}_2, {\bf x}_3, \cdots, {\bf x}_{\vert T\vert}]
\end{displaymath} (3.13)

Dada uma matriz de padrões $X$, a matriz $\Sigma_X$ de covariância de $X$ pode ser obtida a partir da seguinte aproximação (vide equação 2.15):

\begin{displaymath}
\Sigma_X = (X-{\mu}) \cdot (X-{\mu})^t,
\end{displaymath} (3.14)

em que ${\mu}$ é a matriz $ N \times \vert T\vert$ (mesma dimensão que $X$), e todas suas colunas contêm o valor esperado dos padrões de $X$, ou seja:
\begin{displaymath}
{\mu}_{l, i} = {1 \over {\vert T\vert}} \cdot \sum_{j=1}^{\vert T\vert} {X_{l, j}},
\end{displaymath} (3.15)

para $l = 1, 2, 3, \cdots, N$ e $i = 1, 2, 3, \cdots, \vert T\vert$.

É importante notar que $\Sigma^{l, l}_X$ é a variância da característica $l$. Ou seja, os elementos da diagonal da matriz de covariância referem-se à variância das características. Já os elementos fora da diagonal, isto é, $\Sigma_{l, o}$ para $l \neq o$, representam a covariância entre a característica $l$ e $o$. Se duas características, $l$ e $o$, são estatisticamente independentes, a covariância é nula ( $\Sigma_{l, o} = 0$).

Conforme dito anteriormente, é desejável que os padrões sejam representados em um espaço em que não haja covariância entre características diferentes. Um espaço vetorial com essa propriedade possui uma base cuja matriz de covariância de seus vetores é diagonal. Partindo-se de um conjunto de exemplos de padrões de treinamento para obter uma base com tal propriedade, basta utilizar uma transformada que diagonalize a matriz de covariância da base atual do espaço. Com a diagonalização da matriz de covariância, a variância das variáveis (características) será maximizada e a covariância entre uma variável e outra será nula.

De acordo com [Theodoridis and Koutroumbas, 1999], [Duda and Hart, 1973] e
[Callioli et al., 1998], devido ao processo de criação da matriz de covariância, pode-se mostrar que ela é diagonalizável. Para diagonalizar-se a matriz de covariância dos padrões de treinamento $\Sigma_X$, deve-se obter uma representação desses padrões em uma outra base do espaço de características. Em outras palavras, deve-se efetuar uma mudança de base. A matriz mudança de base que possui essa propriedade é definida da seguinte maneira:

\begin{displaymath}
H=[e_1, e_2, e_3, \cdots, e_m],
\end{displaymath} (3.16)

em que $e_i$ é obtido a partir da seguinte decomposição:
\begin{displaymath}
\lambda_i e_i = \Sigma_X e_i,
\end{displaymath} (3.17)

ou seja, $e_i$ é o $i$-ésimo auto-vetor de $\Sigma_X$ [Callioli et al., 1998], $m$ é o número total de auto-vetores de $\Sigma_X$, e $\lambda_i$ é o $i$-ésimo auto-valor de $\Sigma_X$. Nos trabalhos em que o PCA é utilizado para reconhecimento de faces, ou seja, quando os padrões de treinamento são imagens de faces, esses autovetores são chamados de eigenfaces (vide capítulo 4). Isso deve-se ao fato de que esses auto-vetores, quando visualizados como imagens, possuem a aparência de faces. O mesmo ocorre para imagens regiões características da face, como olhos (eigeneyes), nariz (eigennoses) e boca (eigenmouth).

Assim, as variáveis dos padrões representados em termos dessa nova base do espaço de características não possuem correlação entre si. Essa mudança de base é efetuada através da seguinte operação3.2:

\begin{displaymath}
{\bf y}_i = H^t \cdot {\bf x}_i,
\end{displaymath} (3.18)

para $i = 1, 2, 3, \cdots, \vert T\vert$, em que ${\bf y}_i$ é a representação do padrão ${\bf x}_i$ nesse novo espaço de características. Para ilustrar o efeito dessa mudança de base, pode ser criada uma matriz $Y$ contendo todos os padrões ${\bf y}_i$ (da mesma forma que é feita na criação da matriz $X$ - equação 3.13). Dessa maneira, será verificado que a matriz de covariância de $Y$, $\Sigma_Y$, será diagonal.

É importante lembrar que os auto-valores refletem a importância dos auto-vetores. No caso de PCA, os auto-valores da matriz de covariância são iguais à variância das características transformadas [Theodoridis and Koutroumbas, 1999]. Assim, se um auto-vetor possui auto-valor grande, significa que esse fica em uma direção em que há uma grande variância dos padrões. A importância disso está no fato de que, em geral, é mais fácil distinguir padrões usando uma base em que seus vetores apontam para a direção da maior variância dos dados, além de não serem correlacionados entre si.

Através das figuras 3.4, 3.5 e 3.6, pode-se visualizar o efeito da transformada PCA para o caso bidimensional. Pode-se notar que é realizada uma rotação da base do espaço vetorial de forma que o primeiro vetor da nova base fique na direção em que há maior variância dos dados e o segundo fique perpendicular ao primeiro, na direção da segunda maior variação.

[width=5cm, height=5cm]pca_in1.eps Dados artificiais bidimensionais.

[width=5cm, height=8cm]pca_vet1.eps Dados de teste com os auto-vetores da matriz de covariância e seus respectivos auto-valores.

[width=10cm, height=3cm]pca_t1.eps Dados no espaço criado.

O número de auto-vetores obtido é, no máximo, igual ao número de pixels da imagem (ou variáveis dos padrões de entrada), ou seja, $N$. Porém, conforme dito anteriormente, se a matriz $H$ for construída de forma que sejam escolhidos somente os auto-vetores contendo os maiores auto-valores, a variância total dos padrões de entrada não sofre grandes alterações. Em [], o autor discute o conceito de erro residual, o qual é calculado atravéz da diferença entre a reconstrução dos padrões com o uso de todos os autovetores e a reconstrução utilizando alguns autovetores (com redução de dimensionalidade). A representação dos padrões no espaço de características formado pelos auto-vetores com os maiores auto-vetores possui erro residual pequeno. Assim, é possível realizar redução de dimensionalidade utilizando-se, na construção de $H$, somente os $m$ primeiros auto-vetores. Com isso, a dimensionalidade dos vetores ${\bf y}_i$ torna-se $m$, o que significa uma redução de dimensionalidade de $N - m$ dimensões.

Embora essa transformada PCA seja relativamente simples conceitualmente, o processo de treinamento é complexo, visto que, dentre outras operações, é necessário efetuar $\vert T\vert \times
\vert T\vert \times N$ multiplicações para criar a matriz de covariância $\Sigma_X$ [Campos et al., 2000d]. Porém, sua aplicação é muito rápida e, em geral, produz bons resultados para reconhecimento de faces.

Segundo [Duda and Hart, 1973], PCA é uma técnica de extração de características não supervisionada propícia para dados com distribuição Gaussiana, mas não se tem certeza de que as faces possuam tal distribuição. Através das figuras 3.7, 3.8 e 3.9, pode-se observar um caso simples bidimensional ilustrando um problema que pode ocorrer com a redução de dimensionalidade através de PCA. Nesse caso, será muito mais difícil distinguir os padrões das duas classes utilizando somente o primeiro auto-vetor. Já o segundo auto-vetor possui a direção que melhor discrimina as duas classes.

[width=5cm, height=5cm]pca_in.eps Dados artificiais de teste: duas classes em um espaço bidimensional.

[width=5cm, height=8cm]pca_vet.eps Dados de teste de duas classes com os auto-vetores da matriz de covariância e seus respectivos auto-valores.

[width=10cm, height=3cm]pca_t.eps Dados no espaço criado: note que o primeiro auto-vetor não possui poder de discriminação.

Conforme será descrito posteriormente, uma forma de eliminar esse problema consiste na aplicação de um algoritmo de seleção de características (vide seção 3.3). Com a aplicação de um método de seleção automática de características, os autovetores da base do espaço de características são escolhidos de forma ótima.


next up previous contents index
Next: Discriminantes Lineares (LDA) Up: Extração de características Previous: Redução de Dimensionalidade usando   Contents   Index
Teofilo Emidio de Campos 2001-08-29