Jump to content
Accelerated Evolution

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);



		//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));






                //inverse DFT goes here



Link to comment

Please sign in to comment

You will be able to leave a comment after signing in

Sign In Now
  • Create New...