# FFT & DCT Library

, 25 Mar 2004
 Rate this:
Image Processing Algorithm

## Introduction

This Library is specifically designed for image processing analysis. You may just use it in your app, but it isn’t optimized yet (if someone interested to optimize my code, please notify me via email). My main purpose is to provide a simple way for people who is interested in FFT & DCT for Digital Image Processing. Mainly for FFT, I have noticed that, many programmers forget the essence of FrequencyDomain Image Processing, that is, we actually cannot change the FFTed image into RGB, and process the RGB (it doesn’t make sense).

### Issues with `CxImage`

This is my critic for `CxImage `which provides a simple FFT but at the same time forget about few things:

• The result of `CxImage`’s FFT is an image (it is supposed to be complex numbers)

• It is ridiculous to process FFT’s result as an image

• It doesn’t give any complex data that we can process further

• The scaling is quite good, but scaling is supposed to be done only when we want to view the result.

• It changes the image into grayscaled image.

• The most minus point is, it allows us to reverse transform from an image ! How could this be done after scaling process (read: many truncations happen) has been performed.

## How It Works

The library only does two basic functions: FFT (forwardreverse) and DCT (forwardreverse). I’ve seen many algorithm for FFT, and I’ve chosen one of them that I think it is sufficient. The input form is matrices (I use class `Cmatrix `made by R.Allen) so that you don’t have to use malloc/free or such (It’s better to use new/delete, just like I did). The numbers are all in doubles, this will assure the accuracy.

Only for FFT, the dimension of matrix must be exponent of 2, e.g 256, 512, 1024, etc. You can use many method to compensate this limitation (bilinear, bicubic, nearest nighbour), remember that resampling to a larger dimension yields a better result, but more slower execution time. `CxImage `class have provide these resample methods perfectly. After processing, you can then resample back the matrix to it’s original image (The difference in using resample or not is not very significant, thus can be ignored for some reasons). The result of the forward FFT is complex numbers, while the result of reverse FFT is real numbers. In reverse FFT, you only need the Real values.

For DFT, I chose the unoptimized method since I don’t know why the optimized version (uses fft) is irreversible. As a result, the DFT doesn’t have dimension requirements and yet very slow. But DFT is often used only for compression and analysis. It’s not commonly used in a process.

## Multi Thread for True Color Image

Life is full of colors, so do the image. But the problem is, if we want to transform a true color image, we have to process it 3 times. This will slow the execution time three times. This library tries to minimize this phenomena by using Multi Threading support in MFC. It will process the R, G, and B matrices parallel. The priority is set to normal, but you can change it to suit your need. This trick may not be perfect, but at least it helps.

For DFT, I only made the support for TrueColor DFT for fun. In fact, using this functions is no fun at all (sooo slow). Since DFT is only used for analysis, it is much recommended to gray scale the image before DFT and use the regular DFT. But if you want to make it reversible, there is no choice, you have to use the true color DFT.

## Function Lists

```//direct Functions
BOOL FFT(CMatrix *ReInput, CMatrix *ImInput,
CMatrix *ReOutput, CMatrix *ImOutput, int dir = 1);
BOOL DCT(CMatrix *Source, CMatrix *Destination = NULL, int dir = 1);

//true color (uses parallel processing, use with care)
BOOL TRUEFFT(CMatrix *ReInput[3], CMatrix *ImInput[3],
CMatrix *ReOutput[3], CMatrix *ImOutput[3],int dir = 1);
BOOL TRUEDCT(CMatrix *Source[3],
CMatrix *Destination[3],int dir = 1    );```

## Examples of use

Just include the header (ArisImageRoutines1.h) and link the ArisImageRoutines.lib in your project. The most easy to link is by rightclicking at your project’s name and choose Add Files to Project, and browse for the lib. This uses a DLL, so don’t forget to place the DLL in your project’s environment directory.

(it is assumed that you use `CxImage `class, if not just modify the `SetPixel`/`GetPixel `method)

```extern CxImage *image; // assumed that image is in gray scale
image->resample(512,512);

CMatrix ReIn(512,512);
CMatrix ReOut(512,512);
//CMatrix ImIn(512,512); we currently don’t need it
CMatrix ImOut(512,512);

for(int x=0;x<512;x++)
{
for(int y=0;y<512;y++)
{
ReIn.SetElement(x,y, image>GetPixelGray(x,y));
}
}

ArisImageRoutines fft;

if (!fft.FFT(&ReIn, //input Real
NULL, //input Imaginary
&ReOut, //output Real
&ImOut, //output Imaginary
1)) return;

//here the ImOut contains the imaginary result,
//and ReOut contains the Real, respectively.```

## Tips

If you want to acquire the power of the FFT result and then view it as an image, use `sqrt(...) `for each element in Real and Imaginary output. Then use this formula:

```RE = ReOut.GetElement(x,y);
IM = ImOut.GetElement(x,y);
MAG = sqrt((double)(RE*RE+IM+IM));
//this calculates the magnitudes

BYTE Gray = max(0,min(255,(BYTE)(512*log((double)(1+MAG)))));
//this calculates the power 512 is the scale factor

Image>SetPixelGray(x,y,Gray);```

Actually, there are many methods to perform scaling on the resulted matrix. But the above scaling is enough if you just want to see what FFT looks like. Commonly, scientists does not the above resulted image directly. But it process the image first so that we can interpret it better. The image result is usually have higher power value on every corners. The most common way is to change the image like this:

## Last Words

The codes are quite self explained, so I think that you can learn while trying them.

## Future Works

I am currently trying to add a functions that can perform convolution with a given kernel in frequency domain. I am still confused about what padding method should I use to compensate the image dimension which is surely much bigger than the kernel. If some one can help, please notify me.

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

## About the Author

Business Analyst HSBC, Citi
Indonesia
Multi Platform System Analyst, Application Developer, Database Designer, and Project Manager in a wide variety of Business Applications and Industrial Automations.

Experienced for in-depth data analysis, data warehousing, reporting, and actively involve in supporting the business growth.

## Comments and Discussions

 First Prev Next
 Question. Flying_Doc 28-Mar-09 1:57
 MAG = sqrt((double)(RE*RE+IM+IM)); chernobyl 16-Mar-07 22:13
 Why the result is different from the fft() in Matlab?? Karlzheng 9-Nov-06 19:45
 Usage; Frequency histogram [modified] Markus Mayer 11-Jul-06 9:11
 Bug Vertical_Horizon 11-Feb-06 5:34
 Re: Bug Vertical_Horizon 11-Feb-06 6:00
 How to link my picture? uumeme 1-Dec-05 5:53
 confusion TassadaqHussain 24-Oct-05 16:30
 Re: confusion Christian Graus 24-Oct-05 17:12
 Can i be taught how to use this library? redishung 12-Nov-04 22:34
 Re: Can i be taught how to use this library? labrosgiamp 18-Mar-05 2:47
 binary files miklosiklaci 22-Apr-04 0:06
 optimizing your code Teajay 20-Apr-04 21:47
 Re: optimizing your code miklosiklaci 22-Apr-04 0:11
 cool electro2000 20-Apr-04 3:14
 One Observation Roger Wright 28-Mar-04 12:02
 Multithreading ? Rick York 26-Mar-04 21:25
 Re: Multithreading ? Aris A S 27-Mar-04 3:20
 Re: Multithreading ? Rick York 27-Mar-04 14:57
 Re: Multithreading ? Aris A S 27-Mar-04 20:24
 Re: Multithreading ? Rick York 27-Mar-04 15:35
 Re: Multithreading ? Robert Buldoc 27-Mar-04 15:45
 Re: Multithreading ? Rick York 27-Mar-04 18:34
 Disagree Gabriel 2 26-Mar-04 12:43
 Re: Disagree John M. Drescher 26-Mar-04 12:54
 Re: Disagree Aris A S 26-Mar-04 13:06
 Re: Disagree Anonymous 30-Mar-04 6:11
 Re: Disagree Gabriel 2 31-Mar-04 3:55
 Last Visit: 31-Dec-99 19:00     Last Update: 22-Dec-14 5:48 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.