Go Back   AnandTech Forums > Software > Programming

Forums
· Hardware and Technology
· CPUs and Overclocking
· Motherboards
· Video Cards and Graphics
· Memory and Storage
· Power Supplies
· Cases & Cooling
· SFF, Notebooks, Pre-Built/Barebones PCs
· Networking
· Peripherals
· General Hardware
· Highly Technical
· Computer Help
· Home Theater PCs
· Consumer Electronics
· Digital and Video Cameras
· Mobile Devices & Gadgets
· Audio/Video & Home Theater
· Software
· Software for Windows
· All Things Apple
· *nix Software
· Operating Systems
· Programming
· PC Gaming
· Console Gaming
· Distributed Computing
· Security
· Social
· Off Topic
· Politics and News
· Discussion Club
· Love and Relationships
· The Garage
· Health and Fitness
· Merchandise and Shopping
· For Sale/Trade
· Hot Deals with Free Stuff/Contests
· Black Friday 2014
· Forum Issues
· Technical Forum Issues
· Personal Forum Issues
· Suggestion Box
· Moderator Resources
· Moderator Discussions
   

Reply
 
Thread Tools
Old 12-02-2009, 04:03 AM   #1
Azuen
Member
 
Join Date: Sep 2004
Posts: 133
Default Help - 2D DCT in C++

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.
Azuen is offline   Reply With Quote
Old 12-02-2009, 07:08 AM   #2
Cogman
Diamond Member
 
Cogman's Avatar
 
Join Date: Sep 2000
Location: A nomadic herd of wild fainting goats
Posts: 9,802
Default

Quote:
Originally Posted by Azuen View Post

...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
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.
Cogman is offline   Reply With Quote
Old 12-02-2009, 07:47 AM   #3
Azuen
Member
 
Join Date: Sep 2004
Posts: 133
Default

Quote:
Originally Posted by Cogman View Post
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.
Azuen is offline   Reply With Quote
Reply

Tags
2d dct, c++, vs2008

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -5. The time now is 08:26 AM.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2014, vBulletin Solutions, Inc.