CS825 Assignment 4

CS825 Assignment 4/Term Project

Assigned Date: Saturday, July 11, 2020
Part 1 Due Date: Monday, July 20, 2020
Part 2 Due Date: Monday, August 3, 2020
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.
}
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
For (j=0; 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
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[][];
}
// Pass 2: Apply 1D FFT to each row of DFT[][]
For (i=0; i
1. Copy row I from DFT[][] to TDR[];
2. Apply 1D FFT to TDR[] and return the result in TDR[];
3. Copy TDR[] to the row I of DFT[][];
}
// The final Fourier Transform is in buffer DFT[][].
}
Function: 1D FFT
[See lecture note]
Some utility functions can be useful in 1DS FFT:
Function: Index Mapping
Parameters:
Int n; // # of binary bits of an integer to be reversed.
Int N; // size of index mapping table
Int newIndex[N] // index mapping table
{
for (i=0; i
newIndex[i] = reversBits(I, n);
}
// Given two complex values, returns the results of addition operation
Function: Complex Numbers Subtraction
// Given two complex values, returns the results of subtraction operation
Function: Complex Numbers Multiplication
// Given two complex values, returns the results of multiplication operation
Function: Real and Complex Number Multiplication
// Given a real value and a complex value, returns the results of multiplication operation
[Note: If you are familiar with operator overloading in Object-Oriented programming, the above four
functions can be implemented in this style.]
Function: Compute Power Spectrum
Parameters:
COMPLEX DFT[][] // buffer for Fourier transform
Unsigned char out_img[][] // buffer for power spectrum
{
Double spectrum[ROWS][COLS];
For (i=0; i
For (j=0; j
Compute the magnitude of DFT[i][j] and store the value in spectrum[i][j];
}
}
Scan though the spectrum[][] to find the max value;
Find the scaling factor that maps the spectrum values from the range [0.0, max] to [0. 255].
For (i=0; i
For (j=0; j
1.Map the value in spectrum[i][j] to a new value in the range [0, 255] using the
scaling afctor;
2.Convert the scaled spectrum value from double type to unsigned char type and
save it in out_img[i][j];
}
}
}
Part 2: Fourier Spectrum Analysis, Low-Pass and High-Pass Filtering
[To be continued]

• QQ：99515681
• 邮箱：99515681@qq.com
• 工作时间：8:00-23:00
• 微信：codinghelp