Estoy buscando un algoritmo simple para DCT rápido y IDCT de matriz

Estoy buscando un algoritmo simple para realizar DCT rápido (tipo 2) de una matriz de cualquier tamaño [NxM], y también un algoritmo para la transformación inversa IDCT (también llamada DCT tipo 3).

Necesito un algoritmo DCT-2D, pero incluso un algoritmo DCT-1D es lo suficientemente bueno porque puedo usar DCT-1D para implementar DCT-2D (e IDCT-1D para implementar IDCT-2D).

El código PHP es preferible, pero cualquier algoritmo que sea lo suficientemente claro lo hará.

Mi script PHP actual para implementar DCT / IDCT es muy lento cuando el tamaño de la matriz es más de [200×200].

Estaba saltando para encontrar una manera de preformar DCT de hasta [4000×4000] en menos de 20 segundos. Alguien sabe como hacerlo?

Aquí está el cálculo de la mina de 1D FDCT e IFDCT por FFT con la misma longitud:

 //--------------------------------------------------------------------------- void DFCTrr(double *dst,double *src,double *tmp,int n) { // exact normalized DCT II by N DFFT int i,j; double nn=n,a,da=(M_PI*(nn-0.5))/nn,a0,b0,a1,b1,m; for (j= 0,i=n-1;i>=0;i-=2,j++) dst[j]=src[i]; for (j=n-1,i=n-2;i>=0;i-=2,j--) dst[j]=src[i]; DFFTcr(tmp,dst,n); m=2.0*sqrt(2.0); for (a=0.0,j=0,i=0;i=0;i-=2,j++) dst[i]=src[j]-m; for (j=n-1,i=n-2;i>=0;i-=2,j--) dst[i]=src[j]-m; } //--------------------------------------------------------------------------- 
  • dst es el vector de destino [n]
  • src es el vector fuente [n]
  • tmp es vector temporal [2n]

¡Estas matrices no deberían superponerse! Está tomado de la clase de transformación de minas, así que espero que no te olvides de copiar algo.

  • XXXrr significa que el destino es real y la fuente también es dominio real
  • XXXrc significa que el destino es real y la fuente es dominio complejo
  • XXXcr significa que el destino es complejo y la fuente es dominio real

Todos los datos son matrices double , para el dominio complejo, el primer número es real y la segunda parte imaginaria, por lo que la matriz es de tamaño 2N . Ambas funciones usan FFT e iFFT si necesita código también para que me comenten. Solo para asegurarme de haber agregado la implementación no rápida de ellos a continuación. Es mucho más fácil copiar eso porque los rápidos usan demasiado la jerarquía de clase de transformación

implementaciones DFT e iDFT lentas para probar:

 //--------------------------------------------------------------------------- void transform::DFTcr(double *dst,double *src,int n) { int i,j; double a,b,a0,_n,q,qq,dq; dq=+2.0*M_PI/double(n); _n=2.0/double(n); for (q=0.0,j=0;j 

Por lo tanto, para las pruebas simplemente DFFTcr a escribir los nombres en DFFTcr e iDFFTrc (o iDFFTrc para compararlos con su FFT,iFFT ) cuando el código funcione correctamente, luego implemente su propia FFT, iFFT. Para obtener más información, consulte:

  • ¿Cómo calcular la Transformada de Fourier Discreta?

DFCT 2D

  1. cambiar el tamaño de la matriz src a la potencia de 2

    añadiendo ceros, para usar algoritmo rápido el tamaño debe ser siempre el poder de 2 !!!

  2. asignar matrices reales NxN tmp,dst y 1xN vector complejo t

  3. transformar líneas por DFCTrr

     DFCT(tmp.line(i),src.line(i),t,N) 
  4. transponer matriz de tmp

  5. transformar líneas por DFCTrr

     DFCT(dst.line(i),tmp.line(i),t,N) 
  6. transponer la matriz dst

  7. normalizar dst por multiplicar matriz por 0.0625

2D iDFCT

Es lo mismo que arriba, pero use iDFCTrr y multiplique por 16.0 lugar.

[Notas]

¡Asegúrese antes de implementar su propia FFT e iFFT de que dan el mismo resultado que la mía, de lo contrario DCT / iDCT no funcionará correctamente!