Forums

DCT & IDCT algorithm problems

Started by Unknown April 10, 2005
Howdy,

I'm trying to get the DCT and IDCT algorithm correct for MPEG-4
encoding/decoding.  Following the DCT equation that I've put here:
http://www.teamearth.com/wiki/Main/MPEG4 , I generated the following
DCT and IDCT algorithms:

 void dct(int data[8][8]) {
   int u,v,x,y;
   double temp[8][8] = {{0}};
   for (u=0; u<8; u++) {
      for (v=0; v<8; v++) {
         for (x=0; x<8; x++) {
            for (y=0; y<8; y++) {
               temp[u][v] += data[x][y] * cos((2*x+1)*u*PI/16.0) *
cos((2*y+1)*v*PI/16.0);
            }
         }
      }
   }

   for (u=0; u<8; u++) {
      for (v=0; v<8; v++) {
         if (u==0) temp[u][v] *= .7071;
         if (v==0) temp[u][v] *= .7071;
         data[u][v] = floor(temp[u][v] / 16.0+0.5);
      }
   }
 }

 void idct(int data[8][8]) {
   int u,v,x,y;
   double temp[8][8] = {{0}};
   for (x=0; x<8; x++) {
      for (y=0; y<8; y++) {
         for (u=0; u<8; u++) {
            for (v=0; v<8; v++) {
               temp[x][y] += data[u][v] * cos((2*x+1)*u*PI/16.0) *
cos((2*y+1)*v*PI/16.0);
               if (u==0) { temp[x][y] *= .7071; }
               if (v==0) { temp[x][y] *= .7071; }
            }
         }
      }
   }

   for (x=0; x<8; x++) {
      for (y=0; y<8; y++) {
         data[x][y] = floor(temp[x][y] / 16.0 + 0.5);
      }
   }
 }

When I give DCT an 8x8 matrix of all 10s, I get back a matrix with a 20
for the DC and 0s for the AC.  When I send that to the AC, I get all 0s
back.  Does anyone see what my problem is?  Or am I approaching this
incorrectly?

Thanks,
J.R.

Test runs:

 Original Matrix
 10  10  10  10  10  10  10  10
 10  10  10  10  10  10  10  10
 10  10  10  10  10  10  10  10
 10  10  10  10  10  10  10  10
 10  10  10  10  10  10  10  10
 10  10  10  10  10  10  10  10
 10  10  10  10  10  10  10  10
 10  10  10  10  10  10  10  10

 After DCT
 20  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0

 After IDCT
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  
 0  0  0  0  0  0  0  0

Problem 1: 2/N = 1/4, not 1/16.

Problem 2: temp[u][v] += data[x][y] * cos((2*x+1)*u*PI/16.0) *
cos((2*y+1)*v*PI/16.0);
I think you can tell what's wrong now that I've pinpointed the line.

They were rather annoying to track down; such small things are so easy
to overlook. :)

Whoops never mind that second part; there was a problem with my own
copied code and I got mixed up :). The real problem is with the lines:
temp[x][y] += data[u][v] * cos((2*x+1)*u*PI/16.0) *
cos((2*y+1)*v*PI/16.0);
if (u==0) { temp[x][y] *= .7071; }
if (v==0) { temp[x][y] *= .7071; }

There is a flaw in your logic here that doesn't have anything to do
with mistyped variables or the like. I could tell you, but it'll be
more fun if you see it yourself!

Well I had that originally and the result is even more unrealistic than
with 16.  (Also I had some reason as to why it was 16, but I've stared
at it so long I can't remember why now).  Instead of an array with a DC
of 20 and all 0s for AC, you get DC of 80 and 0s for all AC when you
divide by 4.  Regardless, sending 80 and all 0s to the IDCT function
still results in all 0s and leaves me just as confused.
Thanks,
J.R.

The 80 and all 0s is correct. Solve the second part, and you're home
free.

It might be more fun for you... but my eyes have gone over it too many
times to see the error.  I'd appreciate you just pointing it out.  I'm
just trying to understand it all.
Thanks,
J.R.

Hehe, okay. The problem is that the order is wrong. The *= hits not only the 
term that you just +='d, but all terms that were +='d before that. I'm the 
same guy as before, but Google Groups was giving me a headache.
<groups@jrmanes.com> wrote in message 
news:1113180020.027476.296660@g14g2000cwa.googlegroups.com...
> > It might be more fun for you... but my eyes have gone over it too many > times to see the error. I'd appreciate you just pointing it out. I'm > just trying to understand it all. > Thanks, > J.R. >
Maybe that's a little cryptic, so here's what I mean in code:
double tempValue = data[u][v] * cos((2*x+1)*u*PI/16.0) * 
cos((2*y+1)*v*PI/16.0);
if (u==0) { tempValue *= .7071; }
if (v==0) { tempValue *= .7071; }
temp[x][y] += tempValue ;

"James Park" <jpark37@hotmail.com> wrote in message 
news:yt6dnbh3wNWnVMTfRVn-hQ@comcast.com...
> Hehe, okay. The problem is that the order is wrong. The *= hits not only > the term that you just +='d, but all terms that were +='d before that. I'm > the same guy as before, but Google Groups was giving me a headache. > <groups@jrmanes.com> wrote in message > news:1113180020.027476.296660@g14g2000cwa.googlegroups.com... >> >> It might be more fun for you... but my eyes have gone over it too many >> times to see the error. I'd appreciate you just pointing it out. I'm >> just trying to understand it all. >> Thanks, >> J.R. >> > >
OK, I think I see what you mean.  I removed those two lines, and move
the *= section down to where I go through the loop a second time:

...
            for (v=0; v<8; v++) {
               temp[x][y] += data[u][v] * cos((2*x+1)*u*PI/16.0) *
cos((2*y+1)*v*PI/16.0);
            }
         }
      }
   }

   for (x=0; x<8; x++) {
      for (y=0; y<8; y++) {
         if (x==0) { temp[x][y] *= .7071; }
         if (y==0) { temp[x][y] *= .7071; }
         data[x][y] = floor(temp[x][y] / 4.0 + 0.5);
      }
   }

When I do that, I get the 10 back as the DC, but different ACs:

Original Matrix
10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10
10  10  10  10  10  10  10  10

After DCT
80  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0

After iDCT
10  14  14  14  14  14  14  14
14  20  20  20  20  20  20  20
14  20  20  20  20  20  20  20
14  20  20  20  20  20  20  20
14  20  20  20  20  20  20  20
14  20  20  20  20  20  20  20
14  20  20  20  20  20  20  20
14  20  20  20  20  20  20  20


Is this right now?  Or should I be getting the original matrix back
after doing IDCT?

Thanks,
J.R.

The matrix should come back to normal. I didn't explain it too well; just 
see code in my other post (which judging by your post time, you probably 
already have come across).
<groups@jrmanes.com> wrote in message 
news:1113181124.569060.165440@z14g2000cwz.googlegroups.com...
> > OK, I think I see what you mean. I removed those two lines, and move > the *= section down to where I go through the loop a second time: > > ... > for (v=0; v<8; v++) { > temp[x][y] += data[u][v] * cos((2*x+1)*u*PI/16.0) * > cos((2*y+1)*v*PI/16.0); > } > } > } > } > > for (x=0; x<8; x++) { > for (y=0; y<8; y++) { > if (x==0) { temp[x][y] *= .7071; } > if (y==0) { temp[x][y] *= .7071; } > data[x][y] = floor(temp[x][y] / 4.0 + 0.5); > } > } > > When I do that, I get the 10 back as the DC, but different ACs: > > Original Matrix > 10 10 10 10 10 10 10 10 > 10 10 10 10 10 10 10 10 > 10 10 10 10 10 10 10 10 > 10 10 10 10 10 10 10 10 > 10 10 10 10 10 10 10 10 > 10 10 10 10 10 10 10 10 > 10 10 10 10 10 10 10 10 > 10 10 10 10 10 10 10 10 > > After DCT > 80 0 0 0 0 0 0 0 > 0 0 0 0 0 0 0 0 > 0 0 0 0 0 0 0 0 > 0 0 0 0 0 0 0 0 > 0 0 0 0 0 0 0 0 > 0 0 0 0 0 0 0 0 > 0 0 0 0 0 0 0 0 > 0 0 0 0 0 0 0 0 > > After iDCT > 10 14 14 14 14 14 14 14 > 14 20 20 20 20 20 20 20 > 14 20 20 20 20 20 20 20 > 14 20 20 20 20 20 20 20 > 14 20 20 20 20 20 20 20 > 14 20 20 20 20 20 20 20 > 14 20 20 20 20 20 20 20 > 14 20 20 20 20 20 20 20 > > > Is this right now? Or should I be getting the original matrix back > after doing IDCT? > > Thanks, > J.R. >