FFT & DCT Library

• Download source - 29.3 Kb
• Download binary - 66.3 Kb

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.