Transformada de Karhunen-Loève

Em processamento digital de sinais, a transformada de Karhunen-Loève (KLT, do inglês Karnuhen-Loève transform) é uma transformada integral discreta 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 coeficientes.

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

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ève. Outra aplicação em que o uso da KLT é tradicional é no reconhecimento de padrões.

Definição

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 · f^T, 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 a_ij 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 v_ij 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 w_j 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 w_j; não existe expressão explícita para esses coeficientes, mesmo no caso modelo do sinal de entrada ser um sinal Markov-1 perfeito.

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\;\neq \;0\end{matrix}}\right.\qquad (2e)$

que é a expressão de definição da DCT2.

Propriedades

A propriedade notável da KLT é que ela diagonaliza a matriz de autocorrelação A da sequência de entrada, ou seja, V^H · A · V = λ, onde V^H é 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 componentes

Outra propriedade notável é que ela é a sua própria inversa, ou seja, além de O = V · f^T, temos f = V · O^T. 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 original.

Uma KLT alternativa pode ser obtida a partir da matriz de autocovariância S, em lugar de A. Neste caso, teremos U^H · 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 componentes.

Erro na representação

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 · f^T. 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 f_j e g_j são os coeficientes de f(k) e g(k), respectivamente.

Aproximações

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 superior.

A transformada de Karhunen-Loève bidimensional

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 n² elementos tais que $\mathbf {\xi } \;=\;\{\Xi _{11},\Xi _{12},...\Xi _{1n},\Xi _{21},...\Xi _{nn}\}$. O procedimento usual para encontrar a KLT pode ser então aplicado a ξ; a matriz V terá, então, n² x n² elementos. O número de autovalores e autovetores será também igual a n².

Esse procedimento, apesar de teoricamente simples, é extremamente oneroso em termos computacionais, devido à complexidade proporcional a O{n²} 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 = C ⊗ L. 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{n²} 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 L.

Ver também

• Análise de Componentes Principais
• Kari Karhunen
• Michel Loève
• Joint Photographic Experts Group