Transformação rápida de cosseno via FFT

15

Eu quero implementar a Transformação rápida de cosseno. Eu li na wikipedia , que existe uma versão rápida do DCT que é similarmente calculada à FFT. Tentei ler o artigo Makhoul * citado , para as implementações FTPACK e FFTW que também são usadas no Scipy , mas não consegui extrair o algoritmo realmente. Isto é o que eu tenho até agora:

Código FFT:

def fft(x):
    if x.size ==1:
        return x
    N = x.size
    x0 = my_fft(x[0:N:2])
    x1 = my_fft(x[0+1:N:2])
    k = numpy.arange(N/2)
    e = numpy.exp(-2j*numpy.pi*k/N)
    l = x0 + x1 * e
    r = x0 - x1 * e  
    return numpy.hstack([l,r])

Código DCT:

def dct(x):
    k = 0
    N = x.size
    xk = numpy.zeros(N)
    for k in range(N):     
        for n in range(N):
            xn = x[n]
            xk[k] += xn*numpy.cos(numpy.pi/N*(n+1/2.0)*k)
    return xk 

Julgamento da FCT:

def my_fct(x):
    if x.size ==1:
        return x
    N = x.size
    x0 = my_fct(x[0:N:2]) # have to be set to zero?
    x1 = my_fct(x[0+1:N:2])
    k = numpy.arange(N/2)
    n = # ???
    c = numpy.cos(numpy.pi/N*(n+1/2.0)*k)
    l = x0 #???
    r = x0 #???
    return numpy.hstack([l,r])

* J. Makhoul, "Uma transformação rápida de cosseno em uma e duas dimensões", IEEE Trans. Acoust. Speech Sig. Proc. 28 (1), 27-34 (1980).

Framester
fonte
2
Você está perguntando se o seu código DCT está correto ou algo assim?
Jim Clay
Obrigado por seus comentários. Eu adicionei outra frase no começo. O meu objetivo é implementar a FCT com base na FFT.
Framester
O IDCT é dado em Computação do inverso DCT (IDCT) usando DCT ou IFFT .
Royi 18/08/19

Respostas:

18

Nxkarange(N)[0 0,1,2,...,N-1]

Tipo 2 DCT usando 4N FFT e sem turnos

O sinal [a, b, c, d]se torna

[0, a, 0, b, 0, c, 0, d, 0, d, 0, c, 0, b, 0, a].

Em seguida, pegue a FFT para obter o espectro

[A, B, C, D, 0, -D, -C, -B, -A, -B, -C, -D, 0, D, C, B]

jogue fora tudo, menos o primeiro [A, B, C, D], e pronto:

u = zeros(4 * N)
u[1:2*N:2] = x
u[2*N+1::2] = x[::-1]

U = fft(u)[:N]
return U.real

Tipo 2 DCT usando 2N FFT espelhado (Makhoul)

[a, b, c, d][a, b, c, d, d, c, b, a][A, B, C, D, 0, D*, C*, B*][A, B, C, D]e-jπk2N

y = empty(2*N)
y[:N] = x
y[N:] = x[::-1]

Y = fft(y)[:N]

Y *= exp(-1j*pi*k/(2*N))
return Y.real

Tipo 2 DCT usando 2N FFT acolchoado (Makhoul)

[a, b, c, d][a, b, c, d, 0, 0, 0, 0][A, B, C, D, E, D*, C*, B*][A, B, C, D]2e-jπk2N

y = zeros(2*N)
y[:N] = x

Y = fft(y)[:N]

Y *= 2 * exp(-1j*pi*k/(2*N))
return Y.real

DCT tipo 2 usando N FFT (Makhoul)

[a, b, c, d, e, f][a, c, e, f, d, b][A, B, C, D, C*, B*]2e-jπk2N

v = empty_like(x)
v[:(N-1)//2+1] = x[::2]

if N % 2: # odd length
    v[(N-1)//2+1:] = x[-2::-2]
else: # even length
    v[(N-1)//2+1:] = x[::-2]

V = fft(v)

V *= 2 * exp(-1j*pi*k/(2*N))
return V.real

Na minha máquina, todas elas têm aproximadamente a mesma velocidade, pois a geração exp(-1j*pi*k/(2*N))leva mais tempo que a FFT. : D

In [99]: timeit dct2_4nfft(a)
10 loops, best of 3: 23.6 ms per loop

In [100]: timeit dct2_2nfft_1(a)
10 loops, best of 3: 20.1 ms per loop

In [101]: timeit dct2_2nfft_2(a)
10 loops, best of 3: 20.8 ms per loop

In [102]: timeit dct2_nfft(a)
100 loops, best of 3: 16.4 ms per loop

In [103]: timeit scipy.fftpack.dct(a, 2)
100 loops, best of 3: 3 ms per loop
endólito
fonte
2
Ótima resposta, ajudou muito na minha implementação! Nota adicional: O último método "Tipo 2 DCT usando N FFT" ainda funciona corretamente se o comprimento do sinal for ímpar; o último elemento se move para o elemento do meio. Eu verifiquei a matemática e o código para esse fato.
Nayuki
1
@Nayuki Você está gerando exp(-1j*pi*k/(2*N))ou existe um atalho para essa etapa?
Endolith
Estou gerando exp(-1j*pi*k/(2*N))no meu código , porque é necessário um deslocamento de quarto de amostra para fazer o mapeamento do DCT para o DFT. O que faz você perguntar?
Nayuki
Oi, como isso funcionaria para o DCT do tipo III, para calcular o inverso do DCT-II?
Jack H
8

x(n)

deixei

y(n)={x(n),n=0 0,1,...,N-1x(2N-1-n),n=N,N+1,...,2N-1

O DCT é então dado por

C(k)=Re{e-jπk2NFFT{y(n)}}

2Ny(n)x(n)x(n)

Aqui está o código no MATLAB.

function C = fdct(x)
    N = length(x);
    y = zeros(1,2*N);
    y(1:N) = x;
    y(N+1:2*N) = fliplr(x);
    Y = fft(y);
    k=0:N-1;
    C = real(exp(-j.* pi.*k./(2*N)).*Y(1:N));

Editar:

Nota: A fórmula DCT que está usando é:

C(k)=2n=0 0N-1x(n)porque(πk2N(2n+1))

Existem várias maneiras de dimensionar a soma para que ela não corresponda exatamente a outras implementações. Por exemplo, o MATLAB usa:

C(k)=W(k)n=0 0N-1x(n)porque(πk2N(2n+1))

W(0 0)=1NW(1 ...N-1)=2N

Você pode explicar isso dimensionando corretamente a saída.

Jason B
fonte
1
y (n) deve ser comprimento N, não comprimento 2N. É assim que você obtém a velocidade de computação 4x, calculando DCT de comprimento N a partir do sinal de comprimento N em vez de 2N FFT a partir do sinal 2N. fourier.eng.hmc.edu/e161/lectures/dct/node2.html www-ee.uta.edu/dip/Courses/EE5355/Discrete%20class%201.pdf
endolith
0

Para uma verdadeira computação científica, a quantidade de uso de memória também é importante. Portanto, o ponto N FFT é mais atraente para mim. Isso só é possível devido à simetria hermitiana do sinal. A referência Makhoul é dada aqui. E, na verdade, possui o algoritmo para calcular DCT e IDCT ou DCT10 e DCT01.
http://ieeexplore.ieee.org/abstract/document/1163351/

Hasbestein
fonte