Help - 2D DCT in C++

Discussion in 'Programming' started by Azuen, Dec 2, 2009.

  1. Azuen

    Azuen Member

    Joined:
    Sep 22, 2004
    Messages:
    133
    Likes Received:
    0
    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.

    Code:
    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.
     
  2. Cogman

    Cogman Lifer

    Joined:
    Sep 19, 2000
    Messages:
    10,078
    Likes Received:
    12
    Your going to kick yourself when you see the problem :)
    Code:
                        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
    Code:
               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

    Code:
                        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.
     
  3. Azuen

    Azuen Member

    Joined:
    Sep 22, 2004
    Messages:
    133
    Likes Received:
    0
    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.