Description

Part 1: FFT Implementation

Write a complete program that implements the FFT algorithm. Test your program with two input images:

•      square256.raw                        // 256X256 gray scale raw image

•      car.raw                                    // 256X256 gray scale raw image

To help you get started, a reference program structure is provided below. You may modify the structure as you wish or as needed.

Global Image Buffers:

[defined in C-style, but can be easily translated into other programming languages.]

define ROWS 256;  // # of rows  define COLS 256;  // # of columns  

 typedef struct {  // complex data type  double r;      // real part  double i;      // imaginary part  

} COMPLEX; 

unsigned char in_img[ROWS][COLS]; // for input image  COMPLEX C_img[ROWS][COLS]; // for image of complex type COMPLEX DFT[ROWS][COLS]; // for Fourier Transform  unsigned char out_img[ROWS][COLS]; // for output image 

Main Program:

{

1.      Read a raw gray scale image from a specified file into the buffer in_img[][];

2.      Convert the gray scale image in_img[][] into complex image and store it in the buffer

C_img[][], where C_img[][].r = (double)in_img[][], and C_img[][].i = 0.0;

3.      Apply 2D FFT to  C_img[][] and store the result in DFT[][];

4.      Compute the magnitude of DFT[][], scale the value into the range [0, 255], and store the result in out_img[][];

5.      Save DFT[][] into a file in binary format for future use;

6.      Save out_img[][] into a file in raw format for display.

}

Function: Read image Parameters:

string filename                                                  // name of raw gray scale image file unsigned char img[ROWS][COLS]           // buffer for the image

{

1.       Open the input file with “filename”;

2.       If open file operation failed return (-1);

3.       Read data from the input file into img[][];

4.       If read data operation has error return (-1);

5.       return( 0);

}

Function:  Convert a real image to a complex image Parameters:

               unsigned char img[ROWS][COLS]              // buffer of real image

               COMPLEX Cimg[ROWS][COLS]                   // buffer of complex image

{

For (i=0; i<ROWS; i++)

For (j=0; j<COLS; j++) {

Cimg[i][j].r = (double)img[i][j];

Cimg[i][j] = 0.0;

}

}

Function: 2D FFT Parameters:

               COMPLEX Cimg[ROWS][COLS]                   // buffer of complex image

               COMPLEX DFT[ROWS][COLS]                     // buffer of Fourier Transform

{

         COMPLEX TDC[ROWS]                         // temp 1D buffer for a column

         COMPLEX TDR[COLS]                           // temp buffer for a row

// Pass 1: Apply 1D FFT to each column of Cimg[][]

For (i=0; i<COLS; i++){

1.       Copy the column I from Cimg[][] to TDC[];

2.       Apply 1D FFT to TDC[] and return the result in TDC[];

3.       Copy TDC[] to the column I of DFT[][];