Transformada discreta de seno

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Mergefrom 2.svg
O artigo ou secção Transformada discreta local de seno deverá ser fundido aqui. (desde dezembro de 2013)
(por favor crie o espaço de discussão sobre essa fusão e justifique o motivo aqui; não é necessário criar o espaço em ambas as páginas, crie-o somente uma vez. Perceba que para casos antigos é provável que já haja uma discussão acontecendo na página de discussão de um dos artigos. Cheque ambas (1, 2) e não esqueça de levar toda a discussão quando levar o caso para a central.).
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:

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

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]

Propriedades[editar | editar código-fonte]

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" 1]. 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" 2]. 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].

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

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 8]
  • 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"

Propriedades[editar | editar código-fonte]

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 9].

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

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

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

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


Notas[editar | editar código-fonte]

  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. A aplicação a esse ponto da condição de contorno de Neumann resulta em 8 versões para a transformada discreta de cosseno.
  9. 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


Erro de citação: Existem elementos <ref> para um grupo chamado "nota"", mas não foi encontrado nenhum <references group="nota""/> correspondente (ou falta um elemento de fecho </ref>)