Transformada discreta local de seno

Em processamento de sinal, a transformada discreta local de seno (DLS, do inglês Discrete Local Sine transform) é uma transformada superposta cuja base é uma função senoidal discreta. A exemplo de outras transformadas superpostas, encontra utilização em compressão de dados, especialmente na compressão de imagens com perda. Seu desempenho é bastante satisfatório quando comparado a outras transformadas similares, como a transformada superposta ortogonal (LOT) e a transformada superposta modulada (MLT), e a transformadas não-superpostas, como as diversas versões da transformada discreta de cosseno (DCT).^[1]

Motivação

Assim como as demais transformadas superpostas, a DLS foi desenvolvida com o objetivo de minimizar a introdução de artefatos devidos ao fato de o processamento geralmente operar sobre blocos independentes. Examinemos um exemplo de compressão de imagem com perda por meio de transformada discreta.

A necessidade de blocagem

A divisão em blocos é empregada porque as operações de compressão frequentemente são executadas sobre objetos muito grandes e seria inviável tratar todo o objeto de uma só vez. Por exemplo, uma imagem de 512 x 512 pixels possui 512² = 2¹⁸ > 256 mil pixels. Para comprimi-la com perdas usando-se a técnica comum de codificação por transformada, a imagem seria analisada por meio de uma transformada discreta, como a DCT, por exemplo, para seleção dos detalhes menos significativos, que podem ser eliminados sem causar grande impacto visual. A equação que descreve o processo é a seguinte:

${\displaystyle \mathbf {O} ^{\;}=\;\mathbf {\Phi } \cdot \mathbf {I} ^{T}}$

onde Φ é a matriz de transformação, I é a sequência de dados de entrada, isto é, um vetor com todos os pixels da imagem em ordem, e O é a sequência de saída, isto é, coeficientes que indicam o peso de cada autofunção da transformada presente no sinal de entrada (no caso da DCT, funções senoidais). No exemplo, Φ teria 2¹⁸ linhas x 2¹⁸ colunas, o que significa um total de 2³⁶ coeficientes.

Com a divisão da imagem em blocos de 8 x 8 pixels, a mesma equação descreve o processo, mas a matriz Φ passaria a ter apenas 64 linhas e 64 colunas. Um vetor de saída O é então gerado para cada bloco de entrada I.

Uso da transformada discreta na compressão

Imagem antes e depois de sofrer compressão (à direita), com erro de blocagem perceptível.

Se a transformada for empregada para compressão, e não apenas para análise do sinal, Φ terá um número menor de linhas do que de colunas; assim, o vetor de saída será menor que o de entrada. No exemplo dado, uma matriz Φ de 16 linhas x 64 colunas comprimirá a informação contida em cada bloco de 64 pixels de entrada em um bloco de saída de 16 pixels. Cada um destes 16 pixels depende mais ou menos de cada um dos 64 originais, e nada dos demais pixels da imagem de entrada.

No entanto, em geral pixels vizinhos são altamente correlacionados. A correlação entre pixels vizinhos que tenham sido alocados em blocos diferentes é, entretanto, ignorada no processamento. A segmentação arbitrária da imagem original pode fazer com que apareçam descontinuidades na imagem resultante (ver figura ao lado).

Em geral, se a imagem original tiver N x N pixels, o tamanho padrão do bloco usado for n x n pixels e se desejar um fator r de compressão, cada bloco terá dimensão n² e gerará uma saída de dimensão m², com ${\displaystyle m\;=\;{\frac {n}{\sqrt {r}}}}$. A matriz Φ deverá ter, então, m² linhas e n² colunas. A imagem original será dividida em q blocos independentes, sendo ${\displaystyle q\;=\;{\frac {N^{2}}{n^{2}}}}$.

Por simplicidade, e sem perda de generalidade, consideremos a partir deste ponto que os conjuntos de dados que serão processados, muitas vezes multidimensionais e multimodais, são sempre representados por uma sequência de entrada de comprimento N. Chamemos n ao tamanho do bloco e r ao fator de compressão. A imagem original será dividida em q blocos independentes, sendo ${\displaystyle q\;=\;{\frac {N}{n}}}$. Podemos escrever

${\displaystyle \mathbf {O} _{k}\;=\;\mathbf {\Phi } \cdot \mathbf {I} _{k}^{T}\qquad k\in [1,q]\qquad (1a)}$

onde I_k é o k-ésimo bloco de dados de entrada, e O_k é a correspondente sequência de saída. I_k terá dimensão n e O_k, dimensão p, tal que ${\displaystyle {\frac {n}{r}}\;<\;p\;<\;n}$.

A transformação total, por sua vez, pode ser representada por uma matriz Ψ, de dimensões M x N, tal que

${\displaystyle \mathbf {O} \;=\;\mathbf {\Psi } \cdot \mathbf {I} ^{T}\qquad (1b)}$

onde I é a sequência de entrada completa, e O é a sequência de saída. As dimensões de I e O, obviamente, são N e M, respectivamente, com ${\displaystyle M\;=\;{\frac {N}{r}}}$.

A matriz Ψ será uma matriz de bloco diagonal

${\displaystyle \mathbf {\Psi } \;=\;\left({\begin{matrix}\mathbf {\Phi } &\mathbf {0} &\mathbf {0} &...&\mathbf {0} \\\mathbf {0} &\mathbf {\Phi } &\mathbf {0} &...&\mathbf {0} \\\mathbf {0} &\mathbf {0} &\mathbf {\Phi } &...&\mathbf {0} \\...&...&...&...&...\\\mathbf {0} &\mathbf {0} &\mathbf {0} &...&\mathbf {\Phi } \end{matrix}}\right)\qquad (1c)}$

onde 0 é a matriz nula de dimensão m x n. Para n = 4 e m = 2, por exemplo

${\displaystyle \mathbf {\Psi } \;=\;\left({\begin{matrix}a_{11}&a_{12}&a_{13}&a_{14}&0&0&...&0\\a_{21}&a_{22}&a_{23}&a_{24}&0&0&...&0\\0&0&0&0&a_{11}&a_{12}&...&0\\0&0&0&0&a_{21}&a_{22}&...&0\\...&...&...&...&...&...&...&...\\0&0&0&0&0&0&...&a_{24}\end{matrix}}\right)\qquad (1d)}$

Transformadas superpostas

Uma transformada superposta, nas mesmas condições, usa a mesma matriz Φ de transformação, mas a matriz Ψ total será montada com uma superposição entre as matrizes componentes tal que

${\displaystyle \mathbf {\Psi } \;=\;\left({\begin{matrix}\mathbf {\Phi } &&&...&\mathbf {0} \\&\mathbf {\Phi } &&...&\\&&\mathbf {\Phi } &...&\\...&...&...&...&...\\\mathbf {0} &&&...&\mathbf {\Phi } \end{matrix}}\right)\qquad (1e)}$

onde a ausência do símbolo 0 indica que os coeficientes nulos podem não formar uma matriz nula de dimensão m x n. O comprimento da superposição é simbolizado por L, que deve estar na faixa 1 ≤ L < n. Para n = 4, m = 2 e L = 1, por exemplo

${\displaystyle \mathbf {\Psi } \;=\;\left({\begin{matrix}a_{11}&a_{12}&a_{13}&a_{14}&0&0&...&0\\a_{21}&a_{22}&a_{23}&a_{24}&0&0&...&0\\0&0&0&a_{11}&a_{12}&a_{13}&...&0\\...&...&...&...&...&...&...&...\\0&0&0&0&0&0&...&a_{24}\end{matrix}}\right)\qquad (1f)}$

Dessa forma, a transformação leva em conta, para cada bloco de saída a ser gerado, além do bloco de entrada, também alguns pixels vizinhos. Esse procedimento suaviza as áreas de contato entre os blocos de saída e minimiza o erro de blocagem. O termo superposta alude ao fato de dois blocos adjacentes compartilharem alguns pixels. Pode-se interpretar a operação como uma janela deslizante de tamanho n operando sobre a imagem de entrada em passos de tamanho n-L.

A matriz Ψ terá dimensão M x P, com P = N + L. Com isso, o vetor de entrada precisará ter valores nulos inseridos para ajustar-se à transformação. O fator de compressão permanece o mesmo.^[1][2]

Definição

A transformada discreta local de seno será representada por uma matriz Φ, de dimensões m x n, tal que valem as expressões (1a), (1b) e (1e), e os coeficientes φ_ij de Φ são dados pelas expressões seguintes:

${\displaystyle \phi _{ij}\;=\;{\sqrt {\frac {2}{m}}}\cdot \beta _{j}\cdot \sin \left({\frac {(2i\;-\;1)(2j\;-\;L\;-\;1)\pi }{4m}}\right)\qquad |\;i\in [1,m]\;\land \;j\in [1,n]\qquad (1g)}$

${\displaystyle \beta _{j}\;=\;\left\{{\begin{matrix}S_{\epsilon }(j)&:&1\;\leq \;j\;\leq \;L\\\\1&:&L\;<\;j\;\leq \;m\\\\C_{\epsilon }(j\;-\;m)&:&m\;<\;j\;\leq \;n\end{matrix}}\right.\qquad (1h)}$

${\displaystyle S_{\epsilon }(j)\;=\;\sin \left(\epsilon (j)\right)\qquad \qquad C_{\epsilon }(j)\;=\;\cos \left(\epsilon (j)\right)\qquad (1i)}$

${\displaystyle \epsilon (j)\;=\;{\frac {(j\;-\;1)\pi }{2L\;-\;1}}\;-\;{\frac {1}{4}}\sin \left({\frac {2(j\;-\;1)\pi }{L\;-\;1}}\right)\qquad (1j)}$

A sequência de entrada I, na equação (1b), precisa ter nulos inseridos até completar a dimensão P = N + L. Essa inserção deve ser feita nos locais corretos; no caso de uma imagem, por exemplo, os nulos devem completar as bordas da mesma. O procedimento, portanto, depende de cada aplicação específica.

O comprimento da superposição L é sempre igual a (r-1)m. O fator de compressão r, dado por ${\displaystyle r\;=\;{\frac {n}{m}}}$, deve ser um número inteiro; dessa forma, a matriz Φ pode ser dividida em r matrizes quadradas de dimensão m x m. Chamando essas matrizes de Φ_k, com 1 < k < r, Ψ pode ser expressa por

${\displaystyle \mathbf {\Psi } \;=\;\left({\begin{matrix}\mathbf {\Phi } _{1}&\mathbf {\Phi } _{2}&...&\mathbf {\Phi } _{r}&\mathbf {0} &\mathbf {0} &...&\mathbf {0} \\\mathbf {0} &\mathbf {\Phi } _{1}&...&\mathbf {\Phi } _{r-1}&\mathbf {\Phi } _{r}&\mathbf {0} &...&\mathbf {0} \\...&...&...&...&...&...&...&...\\\mathbf {0} &\mathbf {0} &\mathbf {0} &\mathbf {0} &\mathbf {0} &\mathbf {0} &...&\mathbf {\Phi } _{r}\end{matrix}}\right)\qquad (1k)}$

onde 0 é a matriz nula de dimensão m x m.^[1][2]

Exemplo

Para N = 2¹⁸, que corresponde a uma imagem de 512 x 512 pixels, e supondo um bloco usual de 8 x 8 pixels, teremos n = 64. Escolhamos para m o valor 16, que nos dá um fator de compressão de 4. A matriz Φ, com dimensão 16 x 64, seria composta por 4 matrizes quadradas de 16 x 16 coeficientes, Φ₁ a Φ₄. O vetor de entrada I seria dividido em M = 2¹² blocos de comprimento n, e o vetor de saída O teria o mesmo número de blocos, com comprimento m cada. A matriz Ψ terá dimensão M x P,

${\displaystyle \mathbf {\Psi } \;=\;\left({\begin{matrix}\mathbf {\Phi } _{1}&\mathbf {\Phi } _{2}&\mathbf {\Phi } _{3}&\mathbf {\Phi } _{4}&\mathbf {0} &\mathbf {0} &...&\mathbf {0} \\\mathbf {0} &\mathbf {\Phi } _{1}&\mathbf {\Phi } _{2}&\mathbf {\Phi } _{3}&\mathbf {\Phi } _{4}&\mathbf {0} &...&\mathbf {0} \\...&...&...&...&...&...&...&...\\\mathbf {0} &\mathbf {0} &\mathbf {0} &\mathbf {0} &\mathbf {0} &\mathbf {0} &...&\mathbf {\Phi } _{4}\end{matrix}}\right)\qquad (1l)}$

onde 0 é a matriz nula de dimensão 16 x 16.^[1][2]

Propriedades

Transformada inversa

Transformadas superpostas não possuem inversas. Em geral, a expressão Ψ^T · O^T não resultará no vetor I original; além disso, não é possível calcular Ψ^-1, porque ela não é uma matriz quadrada.^[2]

Ortogonalidade

Para transformadas superpostas não vale a condição de ortogonalidade tradicional, e sim a formulação alternativa

${\displaystyle \sum _{k\;=\;1}^{N\;-\;i}\mathbf {\Phi } _{k}\cdot \mathbf {\Phi } _{k\;+\;i}^{T}\;=\;\sum _{k\;=\;1}^{N\;-\;i}\mathbf {\Phi } _{k\;+\;i}^{T}\cdot \mathbf {\Phi } _{k}\;=\;\delta _{1i}\cdot \mathbf {1} \qquad (2a)}$

onde δ é o delta de Kronecker e 1 é a matriz identidade de ordem m. Essa propriedade é conhecida como a condição da perfeita reconstrução. Uma maneira diferente de expressar (2a) é

${\displaystyle \mathbf {\Phi } _{k}^{T}\cdot \mathbf {W} \cdot \mathbf {\Phi } _{k}\;=\;\mathbf {0} \qquad (2b)}$

onde O é a matriz nula de dimensão m x m e W é a matriz, também de dimensões m x m, dada por

${\displaystyle \mathbf {W} \;=\;\left({\begin{matrix}{\frac {}{}}&\mathbf {1} \\{\frac {}{}}&{\frac {}{}}\end{matrix}}\right)\qquad (2c)}$

onde 1 é a matriz identidade de dimensão L x L e os demais coeficientes são nulos.^[1][2]

Conservação da energia

Das propriedades (2a), (2b) e (2c) deduz-se que

${\displaystyle \mathbf {\Psi } ^{T}\cdot \mathbf {\Psi } \;=\;\mathbf {\Psi } \cdot \mathbf {\Psi } ^{T}\qquad (2d)}$

o que significa que a transformação total conserva a energia^{[nota 1]} do sinal de entrada. Isso permite considerar a DLS como uma transformação unitária.^[2]

Variância

A variância de cada bloco de saída O_k pode ser obtida a partir do correspondente bloco de entrada I_k pela expressão

${\displaystyle \sigma _{Ok}^{2}\;=\;\mathbf {\Phi } _{k}^{T}\mathbf {R} _{kk}\mathbf {\Phi } _{k}\qquad (2e)}$

onde σ_2Ok é a variância do k-ésimo bloco de saída e R_kk é a matriz de autocorrelação do k-ésimo bloco de entrada.^[2]

Desempenho

O desempenho da DLS, considerando-se a relação sinal-ruído da saída, é superior ao da LOT e inferior ao da MLT, com as quais apresenta algumas semelhanças, bem como ao da tradicional DCT, que é a transformada mais utilizada.^[1] No entanto, para a LOT e a MLT conhecem-se algoritmos rápidos para cálculo dos coeficientes, o que não acontece com a DLS.^[2]

Notas

1. A energia de um sinal f(t) é medida através do Teorema de Parseval.

Referências

1. P. Yip - Sine and Cosine Transforms in A. Poularikas (org) - The Transforms and Applications Handbook, 2nd. edition, Boca Raton: CRC, 2000, Cap. 3, pp. 320 a 324
2. R. Queiroz - Lapped Transforms in A. Poularikas (org) - The Transforms and Applications Handbook, 2nd. edition, Boca Raton: CRC, 2000, Cap. 14, pp. 1108 a 1109, 1112 a 1117