Jump to content
Accelerated Evolution
Sign in to follow this  
Sanjuro

slow DFT is slow

Recommended Posts

Working on what should've been a quick and easy assignment for my digital image processing class...but yeah, it's not quite as quick as I thought.

-We're given a test image, which we load into our c++ program.

-We zero-pad the sucker to oblivion

-We're supposed to shift the image data by (-1)^(X+Y)...which presents a little problem since the image data is unsigned

-Then we compute the DFT of the image, using the definition of DFT...and for our 206x156 test image this takes just shy of 2.5 hours

-We then apply an ideal low pass filter

-Compute the inverse DFT

-Write the result out to a different image file

I'm just ignoring the whole multiply odd-row even numbered and even-row odd numbered pixels by -1 for now, but the DFT is killing me. Over 2 hours before I find out if I have a mistake or not...

On the off chance someone here can look at what I've got and know if it's wrong or not...


void DFT(int rows, int cols, unsigned char** &image, unsigned char** &result, bool inverse)

{

	//computes the DFT of the image given by the image parameter

	//it will instead compute the IDFT if inverse is set to true


	//we need to make use of the complex template class to get sqrt(-1)

	//complex<double> i (0.0,1.0);

	complex<double> forward_const (0,-2*PI);

	complex<double> inverse_const (0,2*PI);

	complex<double> normalize_const ((rows*cols),0);


	if(!inverse)

	{

		//set up a temp array to hold the complex values

		complex<double>** temp = (complex<double>**)malloc(rows*sizeof(complex<double>*));

		for(int i = 0; i < HEIGHT; i++)

		{

			*(temp + i) = (complex<double>*)malloc(cols*sizeof(complex<double>));

		}


		for(int u = 0; u < rows; u++)

		{

			for(int v = 0; v < cols; v++)

			{

				cout << "u = " << u << ", v = " << v << endl;

				for(int x = 0; x < rows; x++)

				{

					for(int y = 0; y < cols; y++)

					{

						complex<double> iterating_var ((((u*x)/cols)+((v*y)/rows)),0.0);

						temp[u][v] = temp[u][v] + (complex<double>)image[x][y]*exp(forward_const*iterating_var);

					}

				}

                                //I need the fourier spectrum to see if I did it right

				result[u][v] = (unsigned char)sqrt(pow(real(temp[u][v]),2) + pow(imag(temp[u][v]),2));

			}

		}

	}

	else

	{

                //inverse DFT goes here

	}


}

Share this post


Link to post

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now
Sign in to follow this  

×
×
  • Create New...