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:


S_k \;=\; \sqrt{\frac{2}{n}} \cdot \sum_{j \;= 1}^{n-1} f_j \cdot \sin \left( \frac{j k \pi}{n} \right) \;\;\;\;\; (1a)


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


f_k \;=\; \sqrt{\frac{2}{n}} \cdot \sum_{j \;= 1}^{n-1} S_j \cdot \sin \left( \frac{j k \pi}{n} \right) \;\;\;\;\; (2a)


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


s_{jk} \;=\; \sqrt{\frac{2}{n}} \cdot \sin \left( \frac{j k \pi}{n} \right) \qquad |\; k,j \in [1,n-1] \qquad (3a)


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:


\bold{S} \;=\; \left( \begin{matrix} \frac{1}{2} & \sqrt{2} & \frac{1}{2} \\ \sqrt{2} & 0 & -\sqrt{2} \\ \frac{1}{2} & -\sqrt{2} & \frac{1}{2} \end{matrix} \right)[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:


\langle \bold{d}_i , \bold{d}_j \rangle \;=\; \bold{d}_i  \cdot \bold{d}_j^T \;=\; \delta_{ij} \qquad (4a)


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


\mathcal{DST} \{ f(k) \} \;=\; \mathcal{DST} \{ g(k) \} \qquad (4b)


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[8] . Demonstra-se que:


G_k \;=\; \cos \left( \frac{k \pi}{n} \right) \cdot s_k \;-\; \sin \left( \frac{k \pi}{n} \right) \cdot c_k \;+\ \sqrt{\frac{2}{n}} \; \sin \left( \frac{k \pi}{n} \right) \cdot \left[ \frac{f_0}{\sqrt{2}} \;-\; \left( 1 \;-\; \frac{1}{\sqrt{2}} \right) \cdot (-1)^k \cdot f_{n-1} \right] \qquad (4c)


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


h(t) \;=\; \frac{g(t) \;-\; f(t)}{\Delta t} \;\approx\; f'(t)


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[9] . A DST1 de h(k) será dada por


\mathcal{DST} \{ h(k) \} \;=\; \mathcal{DST} \{ g(k) \} \;-\;  \mathcal{DST} \{ f(k) \} \qquad (4c)


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


\mathcal{DST} \{ h(k) \} \;=\; \frac{1}{\Delta t} \cdot \mathcal{DST} \{ f'(k) \}


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


\frac{d^2}{dt^2} \; x(t) \;+\; \lambda x(t) \;=\; 0


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


-x(k \;-\; 1) \;+\; 2x(k) \;-\; \lambda x(k)


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:

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 \sqrt{\frac{2}{n}} \cdot \sin \left( \frac{j k \pi}{n} \right) \qquad |\; k,j \in [1,n-1]
fora da grade Dirichlet fora da grade DST2 \sqrt{\frac{2}{n}} \cdot \epsilon_k \cdot \sin \left( \frac{ \left(j \;+\; \frac{1}{2} \right)(k \;+\; 1) \pi}{n} \right) \qquad |\; k,j \in [0,n-1]
sobre a grade Neumann sobre a grade DST3 \sqrt{\frac{2}{n}} \cdot \epsilon_j \cdot \sin \left( \frac{(j \;+\; 1) \left(k \;+\; \frac{1}{2} \right) \pi}{n} \right) \qquad |\; k,j \in [0,n-1]
fora da grade Neumann fora da grade DST4 \sqrt{\frac{2}{n}} \cdot \sin \left( \frac{ \left( j \;+\; \frac{1}{2} \right ) \left( k \;+\; \frac{1}{2} \right ) \pi}{n} \right) \qquad |\; k,j \in [0,n-1]
sobre a grade Dirichlet fora da grade DST5 \sqrt{\frac{4}{2n \;-\; 1}} \cdot \sin \left( \frac{2 j k \pi}{2n \;-\; 1} \right) \qquad |\; k,j \in [1,n-1]
sobre a grade Dirichlet fora da grade DST6 \sqrt{\frac{4}{2n \;-\; 1}} \cdot \sin \left( \frac{2 \left(j \;+\; \frac{1}{2} \right)(k \;+\; 1) \pi}{2n \;-\; 1} \right) \qquad |\; k,j \in [0,n-2]
sobre a grade Neumann fora da grade DST7 \sqrt{\frac{4}{2n \;-\; 1}} \cdot \sin \left( \frac{2 (j \;+\; 1) \left(k \;+\; \frac{1}{2} \right) \pi}{2n \;-\; 1} \right) \qquad |\; k,j \in [0,n-2]
fora da grade Neumann sobre a grade DST8 \sqrt{\frac{4}{2n \;-\; 1}} \cdot \epsilon_j \cdot \epsilon_k \cdot \sin \left( \frac{ 2 \left( j \;+\; \frac{1}{2} \right ) \left( k \;+\; \frac{1}{2} \right ) \pi}{2n \;-\; 1} \right) \qquad |\; k,j \in [0,n-1]
onde:
  • sjk é o coeficiente da matriz S que define a transformação: O = S · f
  •  \epsilon_i \;=\; \left\{ \begin{matrix} \frac{1}{\sqrt{2}} & : & i \;=\; n \;-\; 1 \\ 1 & : & i \;\ne\; n \;-\; 1 \end{matrix} \right.
  • "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:

\bold{D_1} \;=\; \bold{D_1}^{-1} \qquad \qquad \bold{D_4} \;=\; \bold{D_4}^{-1}

\bold{D_2} \;=\; \bold{D_3}^{-1} \qquad \qquad \bold{D_3} \;=\; \bold{D_2}^{-1}

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

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

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 \mathcal{DST} \{ a \cdot f(k) \} \;=\; a \cdot \mathcal{DST} \{ f(k) \} é 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. E gn = 0.
  9. E hn = -fn.
  10. Britanak, Rao e Yip - op. cit, Cap. 5, pp. 141 a 294
  11. P. Yip - op. cit., pp. 320 a 324