Transformada de Karhunen-Loève

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em processamento digital de sinais, a transformada de Karhunen-Loève (KLT, do inglês Karnuhen-Loève transform) é uma transformada integral dicreta que se demonstra ser ótima sob vários aspectos importantes, e que por isso se constitui numa referência para avaliar o desempenho de outras transformações. A KLT possui a característica única de ser dependente da função de entrada, isto é, o núcleo da transformada varia conforme a função a ser transformada. Isso limita o seu uso em aplicações práticas, porque não é possível desenvolver-se um algoritmo eficiente para computar seus coeficientes1 2 3 .

Essa transformação é também conhecida como transformada de Hotelling em outros campos de pesquisa2 .

A aplicação principal da KLT é na compressão de dados, porque ela incorre no menor erro na representação de uma função contínua f(x) por meio de uma sequência de amostras de comprimento finito k, para qualquer valor de k. Isso é provado pelo teorema de Karhunen-Loève2 3 . Outra aplicação em que o uso da KLT é tradicional é no reconhecimento de padrões4 .

Definição[editar | editar código-fonte]

A transformação de Karhunen-Loève é representada por uma matriz, denotada aqui por V, que, multiplicada por um vetor f que representa o sinal discreto de entrada, resulta no vetor O que representa o sinal de saída (transformada): O = V · fT, onde o superscrito T indica a matriz transposta.

O sinal de entrada considerado é uma sequência de valores complexos aleatória, frequentemente modelada por um sinal estático de Markov de primeira ordem (ou simplesmente sinal de Markov-1), isto é, um vetor cuja matriz de autocorrelação A possui coeficientes aij de acordo com a expressão


a_{ij} \;=\; \rho ^ {|i \;-\; j|} \qquad (1a)


onde ρ é o coeficiente de autocorrelação de A, sempre um número real entre 0 e 1, sendo típicos valores na faixa 0,95 ≤ ρ ≤ 0,99.

Se chamarmos vij aos coeficientes da matriz V, podemos escrever


v_{ij} \;=\; \sqrt{\frac{2}{n \;+\; \mu_j}} \cdot \sin \left( w_j \left[ (i \;+\; 1) \;-\; \frac{n \;+\; 1}{2} \right] \;+\; \frac{(j \;+\; 1)}{2} \right) \qquad |\; i,j \in [0,n-1] \qquad (2a)


one n é o número de elementos do vetor de entrada (e também do vetor de saída), e os coeficientes μj e wj são dependentes da entrada f, de acordo com as expressões seguintes:


\mu_j \;=\; \frac{1 \;-\; \rho ^2}{1 \;-\; 2 \rho \cos (w_j) \;+\; \rho ^2} \qquad (2b)


\tan (w_j \cdot n) \;+\; \frac{(1 \;-\; \rho ^2) \cdot \sin(w_j)}{\cos(w_j) \;-\; 2 \rho \;+\; \rho ^2 \cos(w_j)}  \;=\; 0 \qquad (2c)


A equação (2c) precisa ser resolvida de forma a obterem-se valores reais para wj; não existe expressão explícita para esses coeficientes, mesmo no caso modelo do sinal de entrada ser um sinal Markov-1 perfeitonota 1 .

No caso limite ρ = 1 (sinal perfeitamente correlacionado), a expressão (2a) se simplifica para


v_{ij} \;=\; \sqrt{\frac{2}{n}} \cdot c_{j} \cdot \cos \left( \frac{j \left( i \;+\; \frac{1}{2} \right) \pi}{n} \right) \qquad |\; c_{k} \;=\; \left\{ \begin{matrix} \frac{1}{\sqrt{2}} & : & k \;=\; 0 \\ 1 & : & k \;\ne\; 0 \end{matrix} \right. \qquad (2e)


que é a expressão de definição da DCT21 2 4 5 3 .

Propriedades[editar | editar código-fonte]

A propriedade notável da KLT é que ela diagonaliza a matriz de autocorrelação A da sequência de entrada, ou seja, VH · A · V = λ, onde VH é o conjugado hermitiano de V e λ é uma matriz diagonal composta pelos autovalores de A. Isso tem as seguintes consequências benignas:

  • o sinal transformado é completamente decorrelacionado, ou seja, os coeficientes da sequência de saída são totalmente independentes, por isso qualquer processamento (quantização, codificação, etc.) executado sobre um deles não afeta os demais
  • o erro médio quadrático na representação da sequência de entrada por meio de um dado número de componentes (ou seja, para uma determinada taxa de amostragem) é minimizado
  • a transformada concentra o máximo de energia para um dado número de componentes1 2 3

Outra propriedade notável é que ela é a sua própria inversa, ou seja, além de O = V · fT, temos f = V · OT. Daí, segue-se também que a matriz V é unitária, e que seus autovetores formam uma base ortonormal. Os vetores coluna de O são chamados de as autofunções de f.

Uma propriedade da matriz λ é que os autovalores aparecem em ordem decrescente. Isso facilita o truncamento da representação para um número menor de coeficientes, em lugar de todos os existentes. Os autovalores são essencialmente a variância do vetor O; quanto maior a variância, maior o conteúdo de informação. Assim, cada autovalor é uma medida da importância relativa da importância do respectivo autovetor na reconstrução do sinal original3 .

Uma KLT alternativa pode ser obtida a partir da matriz de autocovariância S, em lugar de A. Neste caso, teremos UH · S · U = Λ, onde U é a matriz que define essa KLT e Λ é uma matriz diagonal composta pelos autovalores de S. A transformada O = U · f concentrará o máximo de variãncia para um dado número de componentes2 .

Erro na representação[editar | editar código-fonte]

Seja f(k) a sequência amostrada original e g(k) o resultado da reconstituição após a aplicação da KLT. Assim, g = V-1 · V · fT. O erro resultante da eliminação de componentes acima do k-ésimo em V é dado pela expressão


\epsilon(k) \;=\; \frac{1}{n} \cdot \sum_{j \;=\; 0}^{n \;-\; 1} \left( \frac{}{} f_j \;-\; g_j \right)^2 \;=\; \sum_{j \;=\; k \;+\; 1}^{n \;-\; 1} \lambda_j \qquad (3a)


onde λj é o j-ésimo autovalor de A e fj e gj são os coeficientes de f(k) e g(k), respectivamente2 .


Aproximações[editar | editar código-fonte]

A transformada fixa conhecida até o momento (2013) que mais se aproxima da KLT é a versão DCT2 da transformada discreta de cosseno. Várias outras transformadas se aproximam assintoticamente, para valores suficientemente grandes de n, do desempenho ideal, inclusive as demais versões das transformadas discretas de seno e de cosseno e a transformada discreta de Fourier (DFT), mas a DCT2, além de coincidir com a KLT para o caso limite ρ = 1 do sinal Markov-1 na entrada, conforme mostra a equação (2e), também se sai melhor que as concorrentes para vetores menos correlacionados e sinais de Markov de ordem superior3 .

A transformada de Karhunen-Loève bidimensional[editar | editar código-fonte]

A maioria das aplicações da KLT são na área de compressão de dados. Como frequentemente é necessário comprimir imagens e estas são normalmente representadas por uma matriz bidimensional, é natural que se estenda a definição de forma a se obter uma versão bidimensional da transformada de Karhunen-Loève.

Seja Ξ a matriz que representa a imagem amostrada, e sejam Ξij os seus coeficientes. Por simplicidade, consideremos que Ξ é uma matriz quadrada de n x n elementos reais. Pode-se definir um vetor ξ de n2 elementos tais que \bold{\xi} \;=\; \{ \Xi_{11}, \Xi_{12}, ... \Xi_{1n}, \Xi_{21}, ... \Xi_{nn} \}nota 2 . O procedimento usual para encontrar a KLT pode ser então aplicado a ξ; a matriz V terá, então, n2 x n2 elementos. O número de autovalores e autovetores será também igual a n2.

Esse procedimento, apesar de teoricamente simples, é extremamente oneroso em termos computacionais, devido à complexidade proporcional a O{n2} das equações de diagnonalização. A solução é considerar que, sendo cada linha ou coluna da imagem completamente independente das demais, V pode ser considerada como o produto diádico de duas matrizes diagonais C e L, ambas com n x n elementos cada: V = CL. Aplicam-se as equações (2a) a (2c) para encontrarem-se os coeficientes de C e L de forma independente, no primeiro caso empregando-se estatísticas referentes às colunas de Ξ e, no segundo caso, estatísticas referentes às linhas. O problema de complexidade O{n2} transforma-se então em dois problemas separados de complexidade O{n}. Haverá dois grupos de n autovalores e n autovetores, um relacionado a C e o outro a L2 .


Ver também[editar | editar código-fonte]


Notas[editar | editar código-fonte]

  1. Esta é, obviamente, mais uma grande desvantagem da KLT, pois torna o cálculo dos coeficientes complexo e computacionalmente intensivo.
  2. Aqui adotamos a convenção usual de numerar os índices a partir de 1, em vez de a partir de 0.


Referências

  1. a b c P. Yip - Sine and Cosine Transforms in A. Poularikas (org) - The Transforms and Applications Handbook, 2nd. edition, Boca Raton: CRC, 2000, Cap. 3, pp. 310 a 311
  2. a b c d e f g h K. Rao - Optimal Decorrelation and the KLT, disponível em http://www-ee.uta.edu/dip/Courses/EE5355/ch3.pdf, acessado em 08/12/2013
  3. a b c d e f Britanak, Rao e Yip - Discrete Cosine and Sine Transforms. General Properties, Fast Algorithms and Integer Approximations, Academic Press, 2006, Cap. 3, pp. 51 a 70
  4. a b Z. Hafed e M. Levine - Face Recognition Using the Discrete Cosine Transform in International Journal of Computer Vision, 43(3), 2001, pp. 167 a 188
  5. F. Giesen - DCT-II vs. KLT/PCA, disponível em http://www.farbrausch.de/~fg/articles/dct_klt.pdf, acessado em 08/12/2013


Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.