Click here to Skip to main content
15,867,141 members
Articles / Desktop Programming / MFC
Article

FFT & DCT Library

Rate me:
Please Sign up or sign in to vote.
4.31/5 (16 votes)
25 Mar 20044 min read 164K   6.7K   48   28
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:

Image 1

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.

License

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


Written By
Business Analyst HSBC, Citi
Indonesia 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

 
GeneralQuestion. Pin
Flying_Doc28-Mar-09 0:57
Flying_Doc28-Mar-09 0:57 
GeneralMAG = sqrt((double)(RE*RE+IM+IM)); Pin
chernobyl16-Mar-07 21:13
chernobyl16-Mar-07 21:13 
QuestionWhy the result is different from the fft() in Matlab?? Pin
Karlzheng9-Nov-06 18:45
Karlzheng9-Nov-06 18:45 
GeneralUsage; Frequency histogram [modified] Pin
Markus Mayer11-Jul-06 8:11
Markus Mayer11-Jul-06 8:11 
GeneralBug Pin
Lampros Giampouras11-Feb-06 4:34
Lampros Giampouras11-Feb-06 4:34 
GeneralRe: Bug Pin
Lampros Giampouras11-Feb-06 5:00
Lampros Giampouras11-Feb-06 5:00 
QuestionHow to link my picture? Pin
uumeme1-Dec-05 4:53
uumeme1-Dec-05 4:53 
Generalconfusion Pin
TassadaqHussain24-Oct-05 15:30
TassadaqHussain24-Oct-05 15:30 
GeneralRe: confusion Pin
Christian Graus24-Oct-05 16:12
protectorChristian Graus24-Oct-05 16:12 
QuestionCan i be taught how to use this library? Pin
redishung12-Nov-04 21:34
redishung12-Nov-04 21:34 
AnswerRe: Can i be taught how to use this library? Pin
Lampros Giampouras18-Mar-05 1:47
Lampros Giampouras18-Mar-05 1:47 
Generalbinary files Pin
miklosiklaci21-Apr-04 23:06
miklosiklaci21-Apr-04 23:06 
Generaloptimizing your code Pin
Teajay20-Apr-04 20:47
Teajay20-Apr-04 20:47 
GeneralRe: optimizing your code Pin
miklosiklaci21-Apr-04 23:11
miklosiklaci21-Apr-04 23:11 
Generalcool Pin
electro200020-Apr-04 2:14
electro200020-Apr-04 2:14 
great to see someone's effort in DIP Smile | :)
GeneralOne Observation Pin
Roger Wright28-Mar-04 11:02
professionalRoger Wright28-Mar-04 11:02 
QuestionMultithreading ? Pin
Rick York26-Mar-04 20:25
mveRick York26-Mar-04 20:25 
AnswerRe: Multithreading ? Pin
Aris Adrianto S27-Mar-04 2:20
Aris Adrianto S27-Mar-04 2:20 
GeneralRe: Multithreading ? Pin
Rick York27-Mar-04 13:57
mveRick York27-Mar-04 13:57 
GeneralRe: Multithreading ? Pin
Aris Adrianto S27-Mar-04 19:24
Aris Adrianto S27-Mar-04 19:24 
GeneralRe: Multithreading ? Pin
Rick York27-Mar-04 14:35
mveRick York27-Mar-04 14:35 
AnswerRe: Multithreading ? Pin
27-Mar-04 14:45
suss27-Mar-04 14:45 
GeneralRe: Multithreading ? Pin
Rick York27-Mar-04 17:34
mveRick York27-Mar-04 17:34 
GeneralDisagree Pin
Gabriel 226-Mar-04 11:43
Gabriel 226-Mar-04 11:43 
GeneralRe: Disagree Pin
John M. Drescher26-Mar-04 11:54
John M. Drescher26-Mar-04 11:54 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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