Students
Register
Advertisement

Transformada de Karhunen-Loève

Ariane Böge


Resumo[]

Neste trabalho será estudado sobre a Transformada de Karhunen-Loève, que é uma técnica de redução do número total de variáveis. Esta técnica é empregada quando existe redundância nos dados de uma amostra, onde redundância pode ser entendida como dados correlacionados, provavelmente em função de estarem medindo o mesmo evento. A existência de redundância é o que permite a redução no número de variáveis. Para verificar a existência ou não de redundâncias, a matriz de correlações entre as variáveis deve ser analisada [Duxus, 2002]. Será realizada sua implementação e os resultados apresentados.

Introdução[]

A análise dos componentes principais(ACP), é um método que tem por finalidade básica, a análise dos dados utilizados visando sua redução, eliminação de sobreposições e a escolha das formas mais representativas de dados a partir de combinações lineares das variáveis originais[Vasconcelos,2007].

É também chamado de Transformada de Karhunen-Loève(KLT) ou ainda Transformada Hotelling, em homenagem a Karl Karhunen, Michel Loève[1907-1979] e Harold Hotelling. Ela transforma variáveis discretas em coeficientes descorrelacionados. Foi derivada por Hotelling e por ele denominada como Método dos Componentes Principais.

A Análise de Componentes Principais(PCA) é um dos métodos estatísticos de múltiplas variáveis mais simples. A PCA é considerada a transformação linear ótima, dentre as transformadas de imagens, sendo muito utilizada pela comunidade de reconhecimento de padrões.

Trabalhos Científicos que utilizam a Transformada de Karhunen Loève[]

Alguns do trabalhos científicos que utilizam da Transformada de Karhunen Loève são:

  • Síntese de Sons Musicais;
  • Extração de Características de Imagens do Olho Humano;
  • Segmentação por Cor;
  • Reconhecimento de Padrões Numéricos; e
  • Processamento, Compressão e Reconhecimento de Imagens.

Organização do trabalho[]

Este trabalho está organizado da seguinte forma: Na seção 3 será apresentada a Transformada de Karhunen Loève, na subseção 3.1 a Matriz de Covariância, na subseção 3.2 os Autoespaços, Autovalores e Autovetores, na seção 3.3 será apresentado a implementação da KLT, na seção 4 será demosntrada uma aplicação da KLT, na seção 5 será apresentado os resultados da implementação, na seção 6 as conclusões e na seção 7 as referências.

Transformada de Karhunen Loève[]

A Análise de Componentes Principais(PCA) é muito útil quando os vetores de características têm muitas dimensões, quando uma representação gráfica não é possível, mas também pode ser útil em dimensões menores, como mostra a Figura 1.

A componente principal é o arranjo que melhor representa a distribuição dos dados(linha vermelha na Figura 1) e a componente secundária é perpendicular a componente principal(linha azul na Figura 1).

Fig1

Figura 1 - Linha vermelha mostra a distribuição principal dos dados e a linha azul mostra a componente secundária.

Os passos para calcular as componentes principais são:

  • Obter os dados ou as M amostras de vetores de dimensão n;
  • Calcular a média ou o vetor médio destes dados;
  • Subtrair a média de todos os itens de dados;
  • Calcular a matriz de covariância utilizando todas as subtrações. Ela é o resultado da média do produto de cada subtração por ela mesma e terá dimensão n X n;
  • Calcular os auto valores e auto vetores da matriz de covariância;
  • Arranjar os autovetores da matriz da Transformada de Karhunen Loève(cujas linhas são formadas a partir dos autovetores da matriz de covariância arranjados de modo que a primeira linha, o elemento (0,0), seja o auto vetor correspondente ao maior autovalor, e assim sucessivamente até que a última linha corresponda ao menor autovalor.

O autovetor com o maior autovalor associado, corresponde à componente principal do conjunto de dados utilizados. Isso significa que esse é o relacionamento mais significativo entre as dimensões dos dados. Na Figura 1 pode-se perceber este ponto.

A transformada pode então ser utilizada conforme a maneira desejada. Seja apenas para visualização, para aquisição de imagens de objetos 2D de acordo com o melhor posicionamento da câmera ou reconhecimento das principais características de medidas a serem usadas.

=>Matriz de Covariância[]

A matriz de covariância para M amostras de vetores em um conjunto qualquer, com vetor médio mx pode ser calculado da seguinte forma :

Fig2

=>Autoespaços, Autovalores e Autovetores[]

Diz-se que um vetor v é um autovetor de uma matriz quadrada M se a multiplicação da matriz M pelo vetor v resulta num múltiplo de v, ou seja, na multiplicação de um escalar pelo vetor. Nesse caso, E'é o chamado autovalor de M associado ao autovetor v.

Segundo , uma propriedade dos autovetores é que eles são perpendiculares entre si. Essa propriedade é importante porque torna possível expressar os dados em termos dos autovetores, em vez de em termos dos eixos x,y e z.

Para matrizes de dimensões 2X2 ou também 3X3, os autovalores podem ser calculados usando a equação característica de M: det(M-E*I)=0

Onde I é a matriz identidade, M a matriz dada e os escalares não nulos, E, que a solucionam serão os autovalores.

Como a matriz de covariância é real e simétrica, é sempre possível encontrar um conjunto de n autovetores ortonormais[Vasconcelos,2007]. Considerando que estes n autovetores sejam arranjados de modo decrescentes de acordo com os valores dos n autovalores, isto é, chamar de e1 o autovetor correspondente ao maior autovalor, h1 e chamar de e2 o autovetor correspondente ao segundo maior valor, h2, e assim sucessivamente.

Considerando a matriz A, cujas colunas sejam os autovetores de Cx e uma transformção definida pela matriz: y=A(x-mx) Está matriz realiza o mapeamento dos valores x, em valores y, cuja média será zero, isto é my=0, e cuja matriz de covariância dos y pode ser obtida de A e Cx através de: Cy=ACxA^T.

Esta matriz Cy é a diagonal e tem elementos ao longo da diagonal principal que são os autovalores de Cx.

Como os elementos fora da diagonal principal de Cy são zeros, os elementos dos vetores y são descorrelacionados. Como os elementos da diagonal de uma matriz diagonal são seus autovalores, segue que Cx e Cy possuem os mesmos autovalores e autovetores.

A transformação representada pela equação y=A(x-mx) é chamada de Transformada de Karhunen Loève. Com a utilização desta transformada, obtém-se o estabelecimento de um novo sistema de coordenadas cuja origem será o centróide do conjunto de pontos(o vetor de média) e cujos eixos estarão na direção dos autovetores de Cx. Esta interpretação geométrica mostra claramente que o efeito da Transformada de Karhunen Loève é a obtenção de um alinhamento dos autovetores por rotação do sistema de eixos. Este alinhamento é o mecanismo que descorrelaciona os dados. Além disso, cada autovalor indica a variância do componente yi ao longo do autovetor vi.

Segundo [Vasconcelos,2007], a idéia de alinhar objetos desempenha um papel muito importante na Análise de Imagens, no Reconhecimento de Padrões e objetos e na Visão de Máquina. Depois que os objetos são extraídos, ou segmentados das imagens, extraí-se características para seu reconhecimento, onde a maioria deles é muito sensível ao ângulo que a direção entre os eixos da câmera e os eixos do objeto fazem. A utilização da direção adequada evita muitos erros posteriores.

Implementação[]

Os passos para a implementação da Transformada de Karhunen Loève são:

Passo1 - Transformar cada imagem (por exemplo uma matriz 512x512) em um vetor. Isso resulta em M vetores-imagem de 262144 (N2) posições cada;

Passo2 - Calcular o produto externo entre esses vetores que resultará em uma matriz L. Uma entrada Lij nessa matriz é o produto interno entre os vetores-imagem i e j. Como a operação de produto interno é comutativa, essa matriz L será simétrica;

Passo3 - Calcular os autovetores dessa matriz L. Isso resulta em M-1 vetores de tamanho M;

Passo4 - Usar os autovetores de L para construir as autofaces da seguinte forma: haverá uma autoface para cada autovetor de L. Para cada autovetor de L, multiplicar cada elemento desse vetor e multiplicar pelo vetor-imagem de mesmo índice e somar todas essas multiplicações, este somatório será a autoface;

Passo5 - Se preferir, descartar as autofaces associadas aos autovalores de menor valor.

Aplicação[]

Uma das aplicações que utilizam a transformada de Karhunen Loève é a segmentação de padrões coloridos em imagens complexas. Nesta aplicação será realizada a quantificação da mucina em imagens de intestino de rato coloridas por corante.

Segundo [Júnior, 2002], o algoritmo tem início com transformação da imagem originalmente em RGB para HSI. Em seguida, o usuário define na imagem uma amostra da cor, que melhor represente a informação de interesse, utilizando como ferramenta interativa o mouse. Após definida a amostra, o algoritomo efetua o cálculo da transformada TKL e fornece novas componentes para representar a cor. Neste novo espaço, a informação apresenta-se melhor distribuída para que possa ser realizada a devida identificação e extração da amostra selecionada pelo usuário. Isto acontece através da pesquisa em uma ou na combinação das componentes calculadas na TKL, escolhidas pelo usuário.

Durante os experimentos foram utilizadas imagens referentes ao exame de biópsia de dois ratos normais da linhagem SPRAGUE-DAWLEY, denominados rato-1 e rato-2. De cada animal foram processadas as imagens obtidas a partir de quatro lâminas, peliminarmente preparadas com ácido periódico de Schiff, para o destaque da mucina com a cor azul. Estes cortes dizem respeito a partes diferentes do intestino dos ratos e foram identificados como c1, c2, c3 e c4.

Nas figuras 2, 3, 4 e 5 pode-se verificar o resultado do processo de quantificação da mucina realizado respectivamente para os cortes c1, c2, c3 e c4 do rato-1. Neles, o algoritmo de segmentação por cor, forneceu resultados significativos.

Figura2

Figura 2 - Quantificação mucina corte "c1"rato-1. a)Imagem Biópsia colônica. b) Extração da mucina. c)Extração das células secretoras da mucina. d)Verificação da extração do muco através da sobreposição do contorno na imagem da biópsia colônica.

Figura3

Figura 3 - Quantificação mucina corte "c2"rato-1. a)Imagem Biópsia colônica. b) Extração da mucina. c)Extração das células secretoras da mucina. d)Verificação da extração do muco através da sobreposição do contorno na imagem da biópsia colônica.

Figura4

Figura 4 - Quantificação mucina corte "c3"rato-1. a)Imagem Biópsia colônica. b) Extração da mucina. c)Extração das células secretoras da mucina. d)Verificação da extração do muco através da sobreposição do contorno na imagem da biópsia colônica.

Figura5

Figura 5 - Quantificação mucina corte "c4"rato-1. a)Imagem Biópsia colônica. b) Extração da mucina. c)Extração das células secretoras da mucina. d)Verificação da extração do muco através da sobreposição do contorno na imagem da biópsia colônica.

Conforme Figura6, foi possível observar que a coloração da mucina no rato-2 obtidano corte c2(em azul mais escuros que os demais) apresenta-se muito próxima da cor das células secretoras e do ruído, dificultando a extração da mucina.

Figura6

Figura 6 - Quantificação mucina corte "c2"rato-2. a)Imagem Biópsia colônica. b) Extração da mucina. c)Extração das células secretoras da mucina. d)Verificação da extração do muco através da sobreposição do contorno na imagem da biópsia colônica.

A partir dos experimentos realizados pode-se verificar a importância de uma segmentação significativa durante a análise de imagens e a valiosa contribuição da cor neste processo. O algoritmo foi capaz de produzir resultados satisfatórios em todas as imagens analisadas, permitindo a realização do processo de quantificação de mucina nos quatro cortes de cada amostra.

Resultados[]

Aplicando a imagem Lenna (512X512) na Transformada da KLT para a compressão da imagem, pode-se obter o seguinte resultado: a Figura 7(a) mostra a imagem de teste Lenna (512X512 pixels)original, sem nenhuma compressão. A Figura7(b) mostra a imagem Lenna (512X512) reconstruída a partir do processamento da imagem original, utilizando KLT.

Fig7

Figura 7:(a) e (b) respectivamente

O gráfico obtido a partir da aplicação da imagem e correspondente aos valores dos 4 autovalores da matriz de correlação dos vetores da Figura7(b) é:

Fig8

Conclusões[]

Pelos resultados obtidos nos experimentos, pode-se concluir que a Transformada de Karhunen Loève é uma ferramenta poderosa se tratando na compressão de imagens e também na segmentação de padrões coloridos em imagens complexas. Pôde-se perceber que a característica básica da KLT é a redução do espaço necessário para a representação da imagem na sua compressão.

Concluí-se então que com o uso da KLT a visualização de diversas variáveis em um determinado conjunto de dados torna-se mais produtiva, rápida, objetiva e eficiente.

Referências[]

[[1]] DUXUS, E., PCA - Principal Component Analysis. www.duxus.com.br, 2002. SP - Brazil. Último acesso: 24 junho de 2007.

[Vasconcelos, S., Análise de Componentes Principais(PCA). 2007. Último Acesso: 26 junho de 2007.]

[Júnior, A., Técnica Interativa de Segmentação por cor: aplicação à quantificação da mucina(muco intestinal). 2002. Universidade Estadual de Ponta Grossa - Paraná.

Anexo[]

Coloque o código completo da implementação da transformada --Alexandre 02:34, 14 May 2007 (UTC) Bold text

Advertisement