CS825留学生代做、代写C/C++程序设计、代写c++设计

日期：2020-07-21 10:29

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.

}

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[][];

}

// Pass 2: Apply 1D FFT to each row of DFT[][]

For (i=0; i<ROWS; 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<N; i++)

newIndex[i] = reversBits(I, n);

}

Function: Complex Numbers Addition

// 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<ROWS; i++) {

For (j=0; j<COLS; 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<ROWS; i++) {

For (j=0; j<COLS; 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]