Implementação rápida do DCT

7

Estou tendo problemas para descobrir como seguir os diagramas rápidos do algoritmo DCT 8x8 encontrados nos dois documentos a seguir:

(1) Um algoritmo computacional rápido para a transformação discreta de cossenos por Chen et al.

e

(2) Algoritmos práticos rápidos de DCT 1-D com 11 multiplicações por Loeffler et al.

Em particular, o segundo diagrama que mostra o algoritmo em (2) se parece com o seguinte:

insira a descrição da imagem aqui

A descrição das operações neste algoritmo são:

insira a descrição da imagem aqui

Existem algumas perguntas que tenho sobre essa formulação e não tenho certeza de onde encontrar as respostas:

  1. (2) sugere que esse algoritmo gera um DCT escalado por algum valor C=2. Menciona que esteCfoi escolhido arbitrariamente para evitar multiplicações na computação do coeficiente DC. Realmente o único requisito é queCDCTCEuDCT=4N2. Então, minha pergunta é a seguinte: Qual é o fator de escala dos coeficientes de saída usando esse algoritmo? Parece que eles são diferentes da definição original do DCT, mas não sei por quanto (principalmente porque não vejo realmente nenhuma relação entre este diagrama e a formulação original do DCT):

    F(k)=2c(k)Nn=0 0N-1 1f(n)porque((2n+1 1)πk2N)
    Onde c(k)=1 12 para k=0 0 e c(k)=1 1 para k0 0.
  2. O artigo afirma que a execução do IDCT pode ser feita usando exatamente o mesmo algoritmo, mas transformando saídas em entradas e vice-versa. Primeiro, os coeficientes do DCT devem ser ordenados na ordem inversa de bits antes de executá-los no IDCT? Segundo, para os blocos de rotação (os quadrados no diagrama), a operação inversa não deveria ser:

    O0 0=Eu0 0kporquenπ2N-Eu1 1kpecadonπ2NO1 1=Eu1 1kpecadonπ2N+Eu1 1kporquenπ2N
    Meu raciocínio é o seguinte: o inverso de uma rotação por θ é uma rotação por -θ. Portanto, apenas substituímos o ângulo por seu inverso e usamos as identidadesporque(-θ)=porque(θ) e pecado(-θ)=-pecado(θ). Terceiro, qual é o fator de escala dos valores transformados após o IDCT? (2) diz2N2, mas empiricamente, isso não produziu resultados corretos.
  3. Suponha que, depois de executar o algoritmo, tenha o resultado de cada pista armazenada nos valores d0 ... d7 . Qual das seguintes opções está correta:

    saída [0] = d0 ou saída [0] = d0
    saída [4] = d1 saída [1] = d4
    saída [2] = d2 saída [2] = d2
    saída [6] = d3 saída [3] = d6
    saída [7] = d4 saída [4] = d7
    saída [3] = d5 saída [5] = d3
    saída [5] = d6 saída [6] = d5
    saída [1] = d7 saída [7] = d1 

Se houver alguma maneira de melhorar essa pergunta ou se eu perguntar em outro lugar, entre em contato.

Mokosha
fonte
Para responder a praticamente este tipo de perguntas que você realmente precisa é um conjunto de valores DCT pré-computadas e ajustar a sua implementação até que seus resultados está em conformidade com aqueles pré-computadas ....
Fat32
Eu tenho todas essas perguntas e mais ... você já descobriu isso? Encontrei alguma implementação em C que tento extrair material. Escreverei algo se encontrar respostas.
Pepijn

Respostas:

4

Tudo bem, depois de alguns dias olhando para esse problema, espero poder fornecer um pouco de orientação para a próxima pobre alma.

  1. Sim, a escala é diferente. Comparado com scipy.fftpack.dcto termo DC é1 12 e os outros termos 22. Mas, aparentemente, tudo cancela bem na transformação inversa.
  2. A ordem de entrada inversa é exatamente como eles saem: bit invertido. Literalmente, como se você virasse a figura e conecte as linhas. E sim, você está certo de que o pecado é negativo. Estou vendo um fator de escala de 8, FWIW.
  3. A ordem de saída da inversa é igual à ordem de entrada da conversão direta. assimx[n]=EuDCT(DCT(x[n]))8

Observe também que há um erro no gráfico e é 2c6 para o bloco de rotação do lado par.

Pepijn
fonte
Obrigado por responder a estas perguntas! Minha motivação original para isso estava no contexto de um algoritmo de compressão 2D, por isso ainda estou um pouco incerto sobre a ordem relativa das saídas (eu gostaria que elas fossem de 0 a 7 para que eu possa tê-las da menor para o maior). Eles também não são um tanto invertidos: 3 -> 5, 5 -> 6, 7 -> 1 não são exatamente reversões de bits (ou eu entendi errado aqui).
Mokosha 01/07/19
11
O pedido corresponde a en.wikipedia.org/wiki/Bit-reversal_permutation, então existe isso. Você pode, naturalmente, reordená-los como quiser. Eu sugeriria levar isso diretamente em consideração na etapa de zig-zag para evitar custos extras.
Pepijn