Saltar para o conteúdo

Transformada discreta de seno

Origem: Wikipédia, a enciclopédia livre.
Existem versões diferentes da transformada discreta de seno.

Em matemática, a transformada discreta de seno (DST, do inglês Discrete Sine Transform) é a versão da transformada de seno para um domínio discreto. Na verdade, podem-se definir 4 tipos diferentes de DST, de acordo com critérios diversos; essas transformadas são denotadas DST1, DST2, DST3 e DST4 ou DST-I, DST-II, DST-III e DST-IV[1][2][nota 1]

Transformadas discretas, ao contrário das transformadas contínuas, aplicam-se não a funções contínuas mas a amostras obtidas destas. A partir de uma função contínua f(t) obtém-se uma sequência de n valores f(k), sendo k um número inteiro de 0 a n-1; a transformada discreta de seno da sequência f(k) é uma outra sequência, que chamaremos S(k), dada pelas expressões de definição. A sequência original pode ser recuperada a partir da sequência S(k) por meio das expressões de definição da transformação inversa. A amostragem deve ser executada sobre um intervalo de comprimento τ, suficiente para que todas as componentes significativas de f(t) estejam representadas devidamente em f(k) (ver Taxa de amostragem); assume-se que o intervalo Δt entre as amostragens é fixo.

A recuperação da sequência original pela aplicação da transformada inversa assume que a função f(t) é nula para t < 0 e também que ela é uma função "ímpar", no sentido de termos f(k) = - f(n-k) no intervalo considerado.[nota 2][3]

A DST possui as propriedade notáveis de:

Se chamarmos fk e Sk ao k-ésimo coeficiente de f(k) e S(k), respectivamente, podemos definir a transformada discreta de seno de tipo 1 (DST1) por meio da expressão seguinte:

Vemos que a sequência S(k) terá apenas n-1 valores, porque os coeficientes extremos devem ser nulos: tanto k quanto j situam-se no intervalo [1,n-1], e não no intervalo [0,n-1], como é usual na definição de transformadas discretas. A transformada inversa é dada por

também com k e j no intervalo [1,n-1]. Note-se a simetria entre a transformação direta e a inversa, e a similaridade com as transformações contínuas correspondentes.

Alternativamente, pode-se definir a DST1 como a matriz que, multiplicada por f(k), resulta em S(k); em notação matricial, S = Ds · f. Se denotarmos os coeficientes da matriz Ds por sjk, podemos escrever

Como a transformada de seno é simétrica, a mesma matriz serve para a obtenção da inversa.[nota 4] Assim, podemos escrever f = Ds · S.[1][5]

A título de exemplo, eis a matriz S para n = 4:

[6]

Ortonormalidade

[editar | editar código-fonte]

A matriz da DST1 (Ds) é unitária e composta de vetores coluna ortogonais. Essas duas propriedades implicam que esses vetores formam uma base ortonormal.[nota 5] Isso é expresso matematicamente por meio do produto interno:

onde dk é um vetor coluna qualquer de Ds, e δ é o delta de Kronecker.[7]

Escalamento no domínio do tempo[nota 6]

[editar | editar código-fonte]

Seja f(k) a sequência de valores amostrados a partir de f(t), e g(k) a sequência de valores amostrados a partir de g(t), segundo critérios idênticos (em particular, o número de amostras n e o intervalo Δt entre as mesmas). Seja g(t) = f(at). Como a transformação não trabalha diretamente com o tempo, e sim sobre sequências de valores amostrados, uma mudança na escala de tempo não altera a transformada.[nota 7] Podemos escrever

Nisso a versão discreta da transformada de seno difere da versão contínua.[7]

Deslocamento no tempo

[editar | editar código-fonte]

Seja f(k) a sequência de valores amostrados a partir de f(t), e g(k) a sequência de valores amostrados a partir de g(t), segundo critérios idênticos (em particular, o número de amostras n e o intervalo Δt entre as mesmas), e seja g(t) = f(t + Δt). Nesse caso, é óbvio que gk = fk+1 para 0 ≤ k < n[nota 8]. Demonstra-se que:

onde Gk é o k-ésimo coeficiente da transformada discreta de seno de g(k), sk é o k-ésimo coeficiente da transformada discreta de seno de f(k), ck é o k-ésimo coeficiente da transformada discreta de cosseno de f(k) e fk é o k-ésimo coeficiente de f(k).[7]

Diferenciação

[editar | editar código-fonte]

Num domínio discreto, o operador de diferença Δ tem papel análogo ao do operador diferencial em um domínio contínuo. Seja f(k) a sequência de valores amostrados a partir de f(t), e g(k) a sequência de valores amostrados a partir de g(t), segundo critérios idênticos (em particular, o número de amostras n e o intervalo Δt entre as mesmas), e seja g(t) = f(t + Δt). A derivada de f(t) pode ser aproximada por uma função h(t) tal que

Nesse caso, a aplicação do operador de diferença a f(k) resulta numa nova sequência h(k); podemos escrever Δf(k) = h(k). Os coeficientes de h(k) serão tais que hk = gk - fk = fk+1 - fk, para 0 ≤ k < n[nota 9]. A DST1 de h(k) será dada por

devido à propriedade básica de linearidade da transformação. É óbvio que h(k) está relacionada a h(t); os coeficientes de h(k) são os valores amostrados de h(t) multiplicados pela constante Δt. Como h(t) aproxima f'(t), podemos escrever

onde f'(k) é a sequência de valores amostrados de f'(t). Comparando-se a expressão (4c) com as expressões para a transformada de seno de f'(t), a derivada de f(t), percebe-se que neste caso a versão discreta se comporta de forma bastante diferente da versão contínua.

Da mesma forma, o comportamento da DST1 com relação à integração no domínio do tempo, à integração no domínio da frequência e à convolução não são similares ao da transformada contínua de seno. Essa é uma das grandes desvantagens da versão discreta.[7]

Outras versões da DST

[editar | editar código-fonte]

Interpretação

[editar | editar código-fonte]

A DST1 pode ser pensada simplesmente como a discretização da transformada de seno. No entanto, a DST pode ser considerada de forma mais geral, a partir do problema físico do oscilador harmônico não amortecido, quando resolvido pelo método das diferenças finitas. A equação diferencial linear de segunda ordem

onde x(t) descreve a posição da massa oscilante em um instante t qualquer, se transforma então na equação de diferença

onde k é o tempo discreto. A solução da equação diferencial acima é uma combinação de funções senoidais; essas funções são as chamadas autofunções do problema. As autofunções da equação de diferença acima também são senoidais, com a diferença que neste caso são senóides discretizadas. Dois tipos de condição de contorno são especialmente relevantes:

  • a condição de contorno de Neumann, no caso contínuo, e no caso discreto
  • a condição de contorno de Dirichlet, no caso contínuo, e no caso discreto

Em geral, essas condições são aplicadas ao ponto inicial (x=0) ou ao ponto final do oscilador (x=L). Quando, no caso discreto, tais pontos coincidem com a grade que discretiza o problema, as autofunções coincidem com a DST1 e a DCT1, que correspondem exatamente às transformadas contínuas de seno e de cosseno; quando, ao contrário, os pontos extremos não estão posicionados sobre a grade, e sim a meio caminho entre duas linhas sucessivas da mesma, as autofunções do problema devem ser expressas a partir das outras versões discretas: DST2, DST3 etc.[5]

As diversas versões da DST, assim, podem ser obtidas:

  • aplicando-se a condição de contorno de Dirichlet no ponto inicial (x = 0)[nota 10]
  • considerando que este ponto está sobre a grade ou que está a meio caminho entre duas linhas sucessivas da grade
  • e aplicando-se a condição de contorno de Dirichlet ou a condição de contorno de Neumann no ponto final (x = L)
  • considerando que este ponto está sobre a grade ou que está a meio caminho entre duas linhas sucessivas da grade

o que dá um total de 8 possibilidades, que estão listadas na tabela abaixo. Apenas as 4 primeiras são geralmente consideradas na literatura (as chamadas versões "pares" da DST); as demais (as versões "ímpares") aparecem a título de completude. A definição de cada versão aparece como o coeficiente da matriz que define a transformação, nos moldes da equação (3a) que define a DST1.

Tabela 1 - Versões da transformada discreta de seno[5][6]
Posição do ponto inicial Condição aplicada ao ponto final Posição do ponto final Versão da transformação Definição
sobre a grade Dirichlet sobre a grade DST1
fora da grade Dirichlet fora da grade DST2
sobre a grade Neumann sobre a grade DST3
fora da grade Neumann fora da grade DST4
sobre a grade Dirichlet fora da grade DST5
sobre a grade Dirichlet fora da grade DST6
sobre a grade Neumann fora da grade DST7
fora da grade Neumann sobre a grade DST8
onde:
  • sjk é o coeficiente da matriz S que define a transformação: O = S · f
  • "fora da grade" significa "a meio caminho entre duas linhas sucessivas da grade"

As diversas versões da DST são lineares mas, apesar de serem todas unitárias, nem todas são suas próprias inversas. Se denotarmos por Dn a matriz de transformação da DSTn, podemos escrever:

Com relação ao escalamento no domínio do tempo e à diferenciação, todas elas se comportam da forma apresentada acima para a DST1. Com relação a um deslocamento no tempo, entretanto, elas diferem bastante uma da outra.[5]

Desempenho da transformação

[editar | editar código-fonte]

Métricas estatísticas

[editar | editar código-fonte]

O desempenho da DST, em todas as suas versões, pode ser medido por meio de uma comparação com o da transformada de Karnuhen-Loève, que reconhecidamente possui o melhor teoricamente possível. A matriz Ds da DST é unitária e simétrica, como a matriz V da KLT, mas não produz uma diagonalização perfeita da matriz de autocorrelação A. A matriz A obtida a partir de Ds não será perfeitamente diagonal, aparecendo coeficientes não nulos proximo à diagonal principal; a presença desses coeficientes indica que os vetores coluna de A não são completamente independentes; a eliminação de um conjunto de autovetores na representação, com objetivos de simplificação e economia, conduzirá a um erro médio quadrático não-mínimo. Em compensação, demonstra-se que, para grandes valores de n e do coeficiente de correlação, o desempenho da DST se aproxima assintoticamente do da KLT. Como o cálculo da DST é muito mais simples e estão disponíveis algoritmos rápidos para seu cálculo, ela acaba sendo mais utilizada na prática que a KLT.[nota 3][4][nota 11]

Custo de processamento

[editar | editar código-fonte]

O custo de processamento da DST, em todas as suas versões, é bastante favorável, quando comparado com as concorrentes, como a KLT e a DFT, esta última normalmente calculada através do algoritmo da Transformada rápida de Fourier (FFT). Isso porque, em contraste com a KLT, o núcleo é fixo e podem ser desenvolvidos algoritmos rápidos para o cálculo dos coeficientes; em contraste com a FFT, a DST exige o cálculo de um número menor de coeficientes e o cálculo não envolve números complexos. Estão disponíveis algoritmos rápidos de diversos tipos, inclusive alguns baseados na própria FFT. A complexidade computacional dos melhores algoritmos é da ordem O{2·n·log2(n)}: (n/2)·log2(n) multiplicações mais n·log2(n) adições. Uma vantagem adicional da maioria dos algoritmos é a sua estabilidade numérica, isto é, o resultado é relativamente pouco afetado por erros de arredondamento e outros relacionados.[nota 3][6]

Modernamente vêm sendo estudados algoritmos que empregam apenas números inteiros, com o objetivo de diminuir o custo computacional das transformadas discretas. Isso é possível porque, na maioria das aplicações práticas, a sequência de entrada é composta por valores inteiros, não por valores reais. Trabalhar apenas com números inteiros diminui também o uso de memória e evita erros de arredondamento e similares. A transformada discreta inteira de seno é obtida a partir de um desses algoritmos.[8]

O processamento digital, especialmente quando alguma compressão de dados está envolvida, pode produzir artefatos perceptíveis. Uma das causas principais na introdução de artefatos é o fato de o processamento frequentemente se efetuar em blocos independentes. A DST[nota 3]também está sujeita a esse problema, que afeta inclusive a KLT, que é uma transformada otimizada apenas com relação às métricas estatísticas (erro médio quadrático, concentração de energia e variãncia etc.). Transformadas especiais, conhecidas como transformadas superpostas (ing. lapped transforms) foram desenvolvidas para minorar esses inconvenientes; a transformada discreta local de seno é uma delas.[9]

  1. Britanak et al(2006) define 8 versões, de DST-I a DST-VIII. Ver a seção Outras versões para mais detalhes.
  2. Isso porque a definição da transformada contínua de seno, com o objetivo de obter o máximo de simplificação em relação à transformada de Fourier, assume que tais condições estejam presentes. Para maiores detalhes, consultar o verbete Transformadas de seno e de cosseno.
  3. a b c d Esta propriedade também é exibida pela transformada discreta de cosseno.
  4. Em matemática, essa propriedade se chama involução.
  5. Geometricamente, a transformação equivale a uma rotação do vetor de entrada f(k) (ou S(k), se se tratar da transformada inversa).
  6. Como a transformada é linear, a expressão é trivial.
  7. É a operação de amostragem que deve levar em conta a escala de tempo, primeiro para garantir que a taxa de amostragem seja adequada, e segundo para reconstituir o sinal a partir da transformada inversa, se necessário.
  8. E gn = 0.
  9. E hn = -fn.
  10. A aplicação a esse ponto da condição de contorno de Neumann resulta em 8 versões para a transformada discreta de cosseno.
  11. Cumpre lembrar que nenhuma das versões da DST alcança o desempenho da DCT2.

Referências

  1. a b P. Yip - Sine and Cosine Transforms in A. Poularikas (org) - The Transforms and Applications Handbook, 2nd. edition, Boca Raton: CRC, 2000, Cap. 3, pp. 305 a 306
  2. 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
  3. a b R. Bracewell - The Fourier Transform and its Applications, 3rd. Edition, New York: McGraw-Hill, 2000, ISBN 0-07303-938-1 / ISBN 978-0-0730-3938-1, Cap. 12, pp. 301 a 303
  4. a b P. Yip - op. cit., Cap. 3, pp. 310 a 311
  5. a b c d Britanak, Rao e Yip - Discrete Cosine and Sine Transforms. General Properties, Fast Algorithms and Integer Approximations, Academic Press, 2006, Cap. 2, pp. 16 a 48
  6. a b c Britanak, Rao e Yip - op. cit, Cap. 4, pp. 73 a 132
  7. a b c d P. Yip - op. cit., cap. 3, pp. 306 a 309
  8. Britanak, Rao e Yip - op. cit, Cap. 5, pp. 141 a 294
  9. P. Yip - op. cit., pp. 320 a 324