Help - 2D DCT in C++

[Azuen]

I'm currently trying to code a 2D DCT in C++, based on the general equation found here: http://www.cs.cf.ac.uk/Dave/Multimedia/node231.html

From what I understand, the function requires an array of 64 shorts containing the luminance values of an 8x8 block (range from 0 to 255).

Below is the code I am attempting to use, which compiles under Visual Studio 2008.

It copies the values from DCT to a another array where the calculated DCT will be stored until the end when it gets copied back.

The two outer for loops are to loop through the original luminance values.

The two inner loops use the equation to calculate the values and add them to the results to get the summed value.

void CAppFocus::fdct8x8(short *dct) {
	//	Input: dct - contains the luminance value of an 8x8 block (range from 0 to 255)
	//	Output: dct - the corresponding DCT transform coefficients of the input block

	//	Note:
	//		1. The variable 'dct' in this function serves as both the input and the output.
	//		2. The DCT coefficients should be scaled properly to make them fall within
	//		   the range of [-2048, 2047]


	short calc_dct[64];

	memcpy(calc_dct, dct, 64*sizeof(short));

	double result = 0;

	int u,v,i,j;

	for(u = 0; u < 8; u++) // 
	{
		for(v = 0; v < 8; v++)
		{
			result = 0; // reset summed results to 0
			for(i = 0; i < 8; i++)
			{
				for(j = 0; j < 8; j++)
				{
					double x = 1;
					double y = 1;
					if (i = 0)
					{
						x = 1/sqrt(2.0);
					} else{
						x = 1;
					}
					if (j = 0)
					{
						y = 1/sqrt(2.0);
					} else{
						y = 0;
					}
					result = result + (x*y*
						cos(((M_PI*u)/(2*height))*(2*i + 1))*
						cos(((M_PI*v)/(2*height))*(2*j + 1))*
						dct[i * 8 + j]);
				}
			}
			calc_dct[u * 8 + v] = result; //store the results
		}
	}


	memcpy(dct, calc_dct, 64*sizeof(short));
}

The method ends up doing 4096 calculations.

The input image has a resolution of 704x528 (88x66 input blocks for 5808 calls to the fdct8x8 method).

The problem is that the code I have written seems to never finish, even when I tested with a single 8x8 bmp.

 

[Cogman]

...The method ends up doing 4096 calculations.

The input image has a resolution of 704x528 (88x66 input blocks for 5808 calls to the fdct8x8 method).

The problem is that the code I have written seems to never finish, even when I tested with a single 8x8 bmp.

Your going to kick yourself when you see the problem

                    double x = 1;
                    double y = 1;
                    if (i = 0)
                    {
                        x = 1/sqrt(2.0);
                    } else{
                        x = 1;
                    }
                    if (j = 0)
                    {
                        y = 1/sqrt(2.0);
                    } else{
                        y = 0;
                    }
                    result = result + (x*y*
                        cos(((M_PI*u)/(2*height))*(2*i + 1))*
                        cos(((M_PI*v)/(2*height))*(2*j + 1))*
                        dct[i * 8 + j]);

should be

           double x = 1;
                    double y = 1;
                    if (i == 0)
                    {
                        x = 1/sqrt(2.0);
                    } else{
                        x = 1;
                    }
                    if (j == 0)
                    {
                        y = 1/sqrt(2.0);
                    } else{
                        y = 0;
                    }
                    result = result + (x*y*
                        cos(((M_PI*u)/(2*height))*(2*i + 1))*
                        cos(((M_PI*v)/(2*height))*(2*j + 1))*
                        dct[i * 8 + j]);

Your reseting i and j to 0 in every loop, pretty sure that isn't what you wanted to do rather == means compare i and j to 1 and 0 respectively.

There are a couple of things that I would change for the sake of speed. First off, I would change the inside loop to

                    double x = 1;
                    double y = 0;
                    if (i == 0)
                    {
                        x = 1/sqrt(2.0);
                    }
                    if (j == 0)
                    {
                        y = 1/sqrt(2.0);
                    }

                    result = result + (x*y*
                        cos(((M_PI*u)/(2*height))*(2*i + 1))*
                        cos(((M_PI*v)/(2*height))*(2*j + 1))*
                        dct[i * 8 + j]);

Since you initalize x and y, there is no need to reset them if the conditions are false.

After that, you have a few constant values that really don't need to be calulated as often as they are, specifically 1/sqrt(2.0) and 2 * height. Both of those don't change, so they should be pulled out of the loop. Thus, you could have some constant INV_SQRT_2 and a variable heightT2 that are set at the beginning of the function rather then being calculated (or potentially calculated) at every loop.

 

[Azuen]

Your going to kick yourself when you see the problem

Haha. You're right, I am kicking myself.

Thanks for your advice, I'll move those outside the function call so they should only need calculated once.