Academic Tutorials



English | French | Portugese | German | Italian
Home Advertise Payments Recommended Websites Interview Questions FAQs
News Source Codes E-Books Downloads Jobs Web Hosting
Chats

Graphics
Graphics Introduction
Graphics Printmaking
Graphics Photography
Graphics for Web
Computer graphics
Computer graphics II
Graphics C++, SDL
Graphics QuickCG
Graphics Light and Color
Graphics Color Model
Graphics Image
Graphics 2D Drawing
Graphics Flood Fill
Graphics Clipping
Graphics Fractals
Graphics Sierpinski
Graphics Julia
Graphics Fire Effect
Graphics Tunnel Effect
graphics Raycasting
Graphics Raycaster
Graphics Floor & Ceiling
Graphics Sprites
Graphics Filtering
Graphics Fourier Trans
Graphics FT on Images
Graphics DC Component
Graphics Texture Gen..
Graphics Random Noise
Graphics Clouds

HTML Tutorials
HTML Tutorial
XHTML Tutorial
CSS Tutorial
TCP/IP Tutorial
CSS 1.0
CSS 2.0
HLML
XML Tutorials
XML Tutorial
XSL Tutorial
XSLT Tutorial
DTD Tutorial
Schema Tutorial
XForms Tutorial
XSL-FO Tutorial
XML DOM Tutorial
XLink Tutorial
XQuery Tutorial
XPath Tutorial
XPointer Tutorial
RDF Tutorial
SOAP Tutorial
WSDL Tutorial
RSS Tutorial
WAP Tutorial
Web Services Tutorial
Browser Scripting
JavaScript Tutorial
VBScript Tutorial
DHTML Tutorial
HTML DOM Tutorial
WMLScript Tutorial
E4X Tutorial
Server Scripting
ASP Tutorial
PERL Tutorial
SQL Tutorial
ADO Tutorial
CVS
Python
Apple Script
PL/SQL Tutorial
SQL Server
PHP
.NET (dotnet)
Microsoft.Net
ASP.Net
.Net Mobile
C# : C Sharp
ADO.NET
VB.NET
VC++
Multimedia
SVG Tutorial
Flash Tutorial
Media Tutorial
SMIL Tutorial
Photoshop Tutorial
Gimp Tutorial
Matlab
Gnuplot Programming
GIF Animation Tutorial
Scientific Visualization Tutorial
Graphics
Web Building
Web Browsers
Web Hosting
W3C Tutorial
Web Building
Web Quality
Web Semantic
Web Careers
Weblogic Tutorial
SEO
Web Site Hosting
Domain Name
Java Tutorials
Java Tutorial
JSP Tutorial
Servlets Tutorial
Struts Tutorial
EJB Tutorial
JMS Tutorial
JMX Tutorial
Eclipse
J2ME
JBOSS
Programming Langauges
C Tutorial
C++ Tutorial
Visual Basic Tutorial
Data Structures Using C
Cobol
Assembly Language
Mainframe
Forth Programming
Lisp Programming
Pascal
Delphi
Fortran
OOPs
Data Warehousing
CGI Programming
Emacs Tutorial
Gnome
ILU
Soft Skills
Communication Skills
Time Management
Project Management
Team Work
Leadership Skills
Corporate Communication
Negotiation Skills
Database Tutorials
Oracle
MySQL
Operating System
BSD
Symbian
Unix
Internet
IP-Masquerading
IPC
MIDI
Software Testing
Testing
Firewalls
SAP Module
ERP
ABAP
Business Warehousing
SAP Basis
Material Management
Sales & Distribution
Human Resource
Netweaver
Customer Relationship Management
Production and Planning
Networking Programming
Corba Tutorial
Networking Tutorial
Microsoft Office
Microsoft Word
Microsoft Outlook
Microsoft PowerPoint
Microsoft Publisher
Microsoft Excel
Microsoft Front Page
Microsoft InfoPath
Microsoft Access
Accounting
Financial Accounting
Managerial Accounting
Network Sites


2D Fourier Transform On Images


Previoushome Next






2D Fourier Transform on Images


A D V E R T I S E M E N T

The extension of the Fourier Transform to 2D is actually pretty simple. First you take the 1D FT of every row of the image, and then on this result you take the 1D FT of every column.

Here follows the code of a program that does exactly that, and two alternative functions that do the same are given in it: one will use the 2D version of the slow DFT, and the other the 2D version of the Fast Fourier Transform (FFT). The program will first calculate the FT of the image, and then calculate the Inverse FT of the result, to check if the formula is working correctly: if it gives back the original it works. You can freely change between calls to DFT2D() and FFT2D() in the main function, and you'll notice that the DFT2D() function is very slow now, while the FFT2D() function works very fast.

Because an RGB image has 3 color channels, the FT is calculated for each color channel separately, so in fact 3 greyscale FT's are calculated.

The program requires that there's a 24-bit color, 128*128 bitmap image pics/test.png (path relative to the program).

First again all the variables and functions are declared.
N and M are the width and height of the image in pixels.
The arrays for the signal and it's spectrum are now 3-dimensional: 2 dimensions for the size, and 1 dimension for the RGB color components. The class ColorRGB can't be used here because more precision is required for FT, that's why the color components are put in a double array instead; index 0 represents red, index 1 green, and index 2 is blue.

There are two versions of the FT functions here, the slow DFT2D and the fast FFT2D.


//yeah, we're working with fixed sizes again...
const int N = 128; //the width of the image
const int M = 128; //the height of the image

double fRe[N][M][3], fIm[N][M][3], fAmp[N][M][3]; //the signal's real part, imaginary part,
and amplitude
double FRe[N][M][3], FIm[N][M][3], FAmp[N][M][3]; //the FT's real part, imaginary part 
and amplitude
double fRe2[N][M][3], fIm2[N][M][3], fAmp2[N][M][3]; //will become the signal again after 
IDFT of the spectrum
double FRe2[N][M][3], FIm2[N][M][3], FAmp2[N][M][3]; //filtered spectrum

double pi = 3.1415926535897932384626433832795;

void draw(int xpos, int yPos, int n, int m, double *g, bool shift, bool neg128);
void DFT2D(int n, int m, bool inverse, double *gRe, double *gIm, double *GRe, double *GIm);
void calculateAmp(int n, int m, double *ga, double *gRe, double *gIm);

The main function first loads an image, and then sets the signal to that image.

Next, it draws the image. It draws the real part, the imaginary part (which is 0!), and the amplitude, which looks the same as the real part.

Then it calculates the FT of the image, by using the DFT2D function, but you can as well change this to FFT2D instead: it'll go faster then. Then it draws the just calculated spectrum.

Finally, it calculates the inverse FT of that spectrum again and draws the result, this is only to check if the functions are working correctly: if you get the original image back, they are.


		int main(int /*argc*/, char */*argv*/[])
{
  screen(N * 3, M * 3, 0, "2D DFT and FFT");

  std::vector<ColorRGB> img;
  unsigned long dummyw, dummyh;
  if(loadImage(img, dummyw, dummyh, "pics/test.png"))
  {
    print("image pics/test.png not found");
    redraw();
    sleep();
    cls();
  }
  
  //set signal to the image
  for(int x = 0; x < N; x++) 
  for(int y = 0; y < M; y++) 
  {
    fRe[x][y][0] = img[N * y + x].r;
    fRe[x][y][1] = img[N * y + x].g;
    fRe[x][y][2] = img[N * y + x].b;
  }
   
  //draw the image (real, imaginary and amplitude)
  calculateAmp(N, M, fAmp[0][0], fRe[0][0], fIm[0][0]);
  draw(0, 0, N, M, fRe[0][0], 0, 0);
  draw(N, 0, N, M, fIm[0][0], 0, 0);
  draw(2 * N, 0, N, M, fAmp[0][0], 0, 0);
   
  //calculate and draw the FT of the image
  DFT2D(N, M, 0, fRe[0][0], fIm[0][0], FRe[0][0], FIm[0][0]); //Feel free to
  change this to FFT2D
  calculateAmp(N, M, FAmp[0][0], FRe[0][0], FIm[0][0]);
  draw(0, M, N, M, FRe[0][0], 1, 1);
  draw(N, M, N, M, FIm[0][0], 1, 1);
  draw(2 * N, M, N, M, FAmp[0][0], 1, 0);

  //calculate and draw the image again
  DFT2D(N, M, 1, FRe[0][0], FIm[0][0], fRe2[0][0], fIm2[0][0]); //Feel free to 
  change this to FFT2D
  calculateAmp(N, M, fAmp2[0][0], fRe2[0][0], fIm2[0][0]);
  draw(0, 2 * M, N, M, fRe2[0][0], 0, 0);
  draw(N, 2 * M, N, M, fIm2[0][0], 0, 0);
  draw(2 * N, 2 * M, N, M, fAmp2[0][0], 0, 0);

  redraw();
  sleep();
  return 0;
}

This is the DFT2D function, it's really just the same as the 1D versions of DFT which was explained in an earlier section, only with an extra loop to do the calculation for every row or column, and repeated twice (for the columns, and for the rows), and this separately for every color component. The function take now two parameters for the dimensions: m and n, because an image is 2D. The parameter inverse can be set to true to do the inverse calculations instead. Again *gRe and *gIm are the input arrays, and *GRe and *GIm the output arrays. In this 2D version, the values are divided through m for the normal DFT and through n for the inverse DFT. There are also definitions where you should divide through m*n in one direction and through 1 in the other, or though sqrt(m*n) in both, but it doesn't really matter which one you pick, as long as the forward FT and the inverse together give the original image back. The version here gives the nicest results to draw.


void DFT2D(int n, int m, bool inverse, double *gRe, double *gIm, double *GRe, double *GIm)
{
  std::vector<double> Gr2(m * n * 3);
  std::vector<double> Gi2(m * n * 3); //temporary buffers
   
  //calculate the fourier transform of the columns
  for(int x = 0; x < n; x++)
  for(int c = 0; c < 3; c++)
  {
    print(" % done",8, 0, RGB_White, 1);
    print(50 * x / n, 0, 0, RGB_White, 1);
    if(done()) end();
    redraw();
    //This is the 1D DFT:
    for(int w = 0; w < m; w++)
    {
      Gr2[m * 3 * x + 3 * w + c] = Gi2[m * 3 * x + 3 * w + c] = 0;
      for(int y = 0; y < m; y++)
      {
        double a= 2 * pi * w * y / float(m);
        if(!inverse)a = -a;
        double ca = cos(a);
        double sa = sin(a);
        Gr2[m * 3 * x + 3 * w + c] += gRe[m * 3 * x + 3 * y + c] * ca - 
		gIm[m * 3 * x + 3 * y + c] * sa;
        Gi2[m * 3 * x + 3 * w + c] += gRe[m * 3 * x + 3 * y + c] * sa + 
		gIm[m * 3 * x + 3 * y + c] * ca;    
      }
   
    }
  }
  //calculate the fourier transform of the rows
  for(int y = 0; y < m; y++)
  for(int c = 0; c < 3; c++)
  {
    print(" % done",8, 0, RGB_White, 1);
    print(50 + 50 * y / m, 0, 0, RGB_White, 1);
    if(done()) end();
    redraw();
    //This is the 1D DFT:
    for(int w = 0; w < n; w++)
    {
      GRe[m * 3 * w + 3 * y + c] = GIm[m * 3 * w + 3 * y + c] = 0;
      for(int x = 0; x < n; x++)
      {
        double a = 2 * pi * w * x / float(n);
        if(!inverse)a = -a;
        double ca = cos(a);
        double sa = sin(a);
        GRe[m * 3 * w + 3 * y + c] += Gr2[m * 3 * x + 3 * y + c] * ca - 
		Gi2[m * 3 * x + 3 * y + c] * sa;
        GIm[m * 3 * w + 3 * y + c] += Gr2[m * 3 * x + 3 * y + c] * sa + 
		Gi2[m * 3 * x + 3 * y + c] * ca;
      }
      if(inverse)
      {
        GRe[m * 3 * w + 3 * y + c] /= n;
        GIm[m * 3 * w + 3 * y + c] /= n;
      }
      else
      {
        GRe[m * 3 * w + 3 * y + c] /= m;
        GIm[m * 3 * w + 3 * y + c] /= m;
      }
    }
  }
}

And here's the Fast Fourier Transform again, in 2D this time. The same can be said about this function as for the DFT2D function. The explanation of the FFT was already done in an earlier section.


void FFT2D(int n, int m, bool inverse, double *gRe, double *gIm, double *GRe, double *GIm)
{
  int l2n = 0, p = 1; //l2n will become log_2(n)
  while(p < n) {p *= 2; l2n++;}
  int l2m = 0; p = 1; //l2m will become log_2(m)
  while(p < m) {p *= 2; l2m++;}
  
  m = 1 << l2m; n = 1 << l2n; //Make sure m and n will be powers of 2, otherwise you'll
  get in an infinite loop
   
  //Erase all history of this array
  for(int x = 0; x < m; x++) //for each column
  for(int y = 0; y < m; y++) //for each row
  for(int c = 0; c < 3; c++) //for each color component
  {
    GRe[3 * m * x + 3 * y + c] = gRe[3 * m * x + 3 * y + c];
    GIm[3 * m * x + 3 * y + c] = gIm[3 * m * x + 3 * y + c];
  }
   
  //Bit reversal of each row
  int j;
  for(int y = 0; y < m; y++) //for each row
  for(int c = 0; c < 3; c++) //for each color component
  {
    j = 0;
    for(int i = 0; i < n - 1; i++)
    {
      GRe[3 * m * i + 3 * y + c] = gRe[3 * m * j + 3 * y + c];
      GIm[3 * m * i + 3 * y + c] = gIm[3 * m * j + 3 * y + c];
      int k = n / 2;
      while (k <= j) {j -= k; k/= 2;}
      j += k;
    }
  }
  //Bit reversal of each column
  double tx = 0, ty = 0;  
  for(int x = 0; x < n; x++) //for each column
  for(int c = 0; c < 3; c++) //for each color component
  {
    j = 0;
    for(int i = 0; i < m - 1; i++)
    {
      if(i < j)
      {
        tx = GRe[3 * m * x + 3 * i + c];
        ty = GIm[3 * m * x + 3 * i + c];
        GRe[3 * m * x + 3 * i + c] = GRe[3 * m * x + 3 * j + c];
        GIm[3 * m * x + 3 * i + c] = GIm[3 * m * x + 3 * j + c];
        GRe[3 * m * x + 3 * j + c] = tx;
        GIm[3 * m * x + 3 * j + c] = ty;
      }
      int k = m / 2;
      while (k <= j) {j -= k; k/= 2;}
      j += k;
    }
  }

  //Calculate the FFT of the columns
  for(int x = 0; x < n; x++) //for each column
  for(int c = 0; c < 3; c++) //for each color component
  {
    //This is the 1D FFT:
    double ca = -1.0;
    double sa = 0.0;
    int l1 = 1, l2 = 1;
    for(int l=0;l < l2n;l++)
    {
      l1 = l2;
      l2 *= 2;
      double u1 = 1.0;
      double u2 = 0.0;
      for(int j = 0; j < l1; j++)
      {
        for(int i = j; i < n; i += l2)
        {
          int i1 = i + l1;
          double t1 = u1 * GRe[3 * m * x + 3 * i1 + c] - u2 * GIm[3 * m * x + 3 * i1 + c];
          double t2 = u1 * GIm[3 * m * x + 3 * i1 + c] + u2 * GRe[3 * m * x + 3 * i1 + c];
          GRe[3 * m * x + 3 * i1 + c] = GRe[3 * m * x + 3 * i + c] - t1;
          GIm[3 * m * x + 3 * i1 + c] = GIm[3 * m * x + 3 * i + c] - t2;
          GRe[3 * m * x + 3 * i + c] += t1;
          GIm[3 * m * x + 3 * i + c] += t2;
        }
        double z =  u1 * ca - u2 * sa;
        u2 = u1 * sa + u2 * ca;
        u1 = z;
      }
      sa = sqrt((1.0 - ca) / 2.0);
      if(!inverse) sa = -sa;
      ca = sqrt((1.0 + ca) / 2.0);
    }
  }
  //Calculate the FFT of the rows
  for(int y = 0; y < m; y++) //for each row
  for(int c = 0; c < 3; c++) //for each color component
  {
    //This is the 1D FFT:
    double ca = -1.0;
    double sa = 0.0;
    int l1= 1, l2 = 1;
    for(int l = 0; l < l2m; l++)
    {
      l1 = l2;
      l2 *= 2;
      double u1 = 1.0;
      double u2 = 0.0;
      for(int j = 0; j < l1; j++)
      {
        for(int i = j; i < n; i += l2)
        {
          int i1 = i + l1;
          double t1 = u1 * GRe[3 * m * i1 + 3 * y + c] - u2 * GIm[3 * m * i1 + 3 * y + c];
          double t2 = u1 * GIm[3 * m * i1 + 3 * y + c] + u2 * GRe[3 * m * i1 + 3 * y + c];
          GRe[3 * m * i1 + 3 * y + c] = GRe[3 * m * i + 3 * y + c] - t1;
          GIm[3 * m * i1 + 3 * y + c] = GIm[3 * m * i + 3 * y + c] - t2;
          GRe[3 * m * i + 3 * y + c] += t1;
          GIm[3 * m * i + 3 * y + c] += t2;
        }
        double z =  u1 * ca - u2 * sa;
        u2 = u1 * sa + u2 * ca;
        u1 = z;
      }
      sa = sqrt((1.0 - ca) / 2.0);
      if(!inverse) sa = -sa;
      ca = sqrt((1.0 + ca) / 2.0);
    }
  }
 
  int d;
  if(inverse) d = n; else d = m;
  for(int x = 0; x < n; x++) for(int y = 0; y < m; y++) for(int c = 0; c < 3; c++) //for every value 
  of the buffers
  {
    GRe[3 * m * x + 3 * y + c] /= d;
    GIm[3 * m * x + 3 * y + c] /= d;
  }
}

The draw function does what the plot function did in the 1D version: show the signal on screen. Now this function will draw the signal or spectrum arrays you feed it as a 24-bit RGB image with the upper left corner at xpos,yPos. The shift parameter can be used to bring the corners to the center and the center to the corners, useful for FT's to bring the DC component to the center. The neg128 parameter can be used to draw images that can have negative pixel values: now gray (RGB color 128, 128, 128) is used as 0, darker colors are negative, and brighter ones are positive.


		//Draws an image
void draw(int xPos, int yPos, int n, int m, double *g, bool shift, bool neg128) //g is the 
image to be drawn
{
  for(int x = 0; x < n; x++)
  for(int y = 0; y < m; y++)
  {
    int x2 = x, y2 = y;
    if(shift) {x2 = (x + n / 2) % n; y2 = (y + m / 2) % m;} //Shift corners to center
    ColorRGB color;
    //calculate color values out of the floating point buffer
    color.r = int(g[3 * m * x2 + 3 * y2 + 0]); 
    color.g = int(g[3 * m * x2 + 3 * y2 + 1]); 
    color.b = int(g[3 * m * x2 + 3 * y2 + 2]); 

    if(neg128) color = color + RGB_Gray;
    //negative colors give confusing effects so set them to 0
    if(color.r < 0) color.r = 0;
    if(color.g < 0) color.g = 0;
    if(color.b < 0) color.b = 0;
    //set color components higher than 255 to 255
    if(color.r > 255) color.r = 255;
    if(color.g > 255) color.g = 255;
    if(color.b > 255) color.b = 255;
    //plot the pixel
    pset(x + xPos, y + yPos, color);
  }
}

The calculateAmp function is also again the same as the 1D version, only with an extra loop for the 2nd dimension, and another one for the color components. This function is used to generate the amplitudes of the signals and spectra so that you can draw those.

//Calculates the amplitude of *gRe and *gIm and puts the result in *gAmp
void calculateAmp(int n, int m, double *gAmp, double *gRe, double *gIm)
{
  for(int x = 0; x < n; x++)
  for(int y = 0; y < m; y++)
  for(int c = 0; c < 3; c++)
  {
    gAmp[m * 3 * x + 3 * y + c] = sqrt(gRe[m * 3 * x + 3 * y + c] * 
	gRe[m * 3 * x + 3 * y + c] + gIm[m * 3 * x + 3 * y + c] * gIm[m * 3 * x + 3 * y + c]);
  }
}

Note that, because of the way C++ works, the arrays are passed to the functions in a special way, and inside the functions they have to be treated as 1-dimensional.

The output of the program is as follows:

2D DFT

On the top row are the real part, imaginary part and amplitude of the image. The imaginary part of the image is 0.

On the center row are the real part, imaginary part and amplitude of the spectrum from the image. The real and imaginary part can have negative values, so they have the "neg128" option enabled to draw them and grey represents 0. Since the amplitude is always positive, black is 0 there.

The bottom row is again the image, calculated by using the Inverse DFT of the spectrum. It looks almost the same as the original, a few pixels might slightly differ in color due to rounding errors.

The text "99% done" only appears if you use the DFT2D function, since it's so slow (30 seconds on an Athlon 1700+ processor for an 128x128 image) a progress counter is handy. The FFT2D does the same calculation immediatly, so such a counter isn't needed.

If you study the spectra of the images, you'll see horizontal and vertical lines through the center. They're caused by the sides of the image: since mathematically speaking, the FT is calculated of the image tiled infinite times, there's an abrupt change when going from one side of the image to the other, causing the lines in the spectrum.

Some remarks:
  • If you'd calculate the forward FT instead of the inverse FT to go back from the spectrum to the image, you get the image upside down.
  • Both the real and imaginary part of the spectrum are needed to reconstruct the image out of it, even though the image itself has no imaginary part.
  • The FT functions also work on images that have an imaginary part, for example if a color image would have only 2 color channels, one color channel could be used as real part and the other as imaginary part.
  • Even though the image itself is in 24-bit color, which means that each pixel has 8 bit per color channel, or 256 discrete color values per channel, the FT of it requires much more precision: both the real and imaginary component require floating point numbers that can go from -infinity to +infinity. Otherwise you'll lose information and the image you get back after doing the inverse FT on it again will look very crappy. The spectra displayed on the computer screen don't contain all information, since they're converted back to integers with 256 discrete values.
  • By taking the DFT of the amplitude of the spectrum of an image, you will NOT get the original image back at all, since it requires a high precision real and an imaginary part of the spectrum, not the amplitude.

The Spectra of Images


You can replace test.png by any 24-bit 128*128 color bitmap you want. You can even use another size, but then you'll have to change the parameters N and M in the code (on top). Note that the FFT2D function only works on images with a size that is a power of two (64x64, 128x256, 256x256... all work), otherwise you'll have to use the slower DFT2D function.

The spectrum of an image isn't immediatly the most interesting thing (applying filters on it and then taking the inverse FT again is much more interesting), but you can still learn a bit about an image by looking at it's spectrum: here are a few examples, each picture shows the real part of the image, and the amplitude of the spectrum. To see the real and imaginary part of the spectrum, run the images through the program yourself.

This image is a sine function with a DC component added (because images can only have positive pixel values): the color of each pixel is 128 + 128 * sin(pi*y/16.0). If you remember the spectra of 1D signals, you'll remember that a sine function gave a peak on the negative and positive side, and that the DC component gave a peak at zero. Here you can see the same in the spectrum: the center dot is the DC component, and the two others represent the frequency of the sine function, the one dot is just a mirrored version of the other one. There are no pixels in the x-direction, because the image is the same everywhere in that direction.



Here a sine function with a higher frequency is used to generate the image, so the two dots are further away from the origin to represent the higher frequency. Remember the scale property of the Fourier Transform? Here it's illustrated very well: the image contracts, and it's spectrum becomes wider.



In the next image, the sine function doesn't tile: if you'd put the same image twice on top of each other, you wouldn't see a sine anymore in the y-direction (while in the previous two examples you would). This isn't considered a real sine anymore by the spectrum either, and it doesn't contain just two dots, but a line.



One of the properties of the 2D FT is that if you rotate the image, the spectrum will rotate in the same direction:



The following image shows the sum of 2 sine functions, each in another direction (Plasma effects are often made this way):



The following image shows how lines in an image often generate perpendicular lines in the spectrum:



The sloped lines in the spectrum here are obviously due to the sharp transition from the sky to the mountain.



The FT of a rectangular function is a 2D sinc function:



And here's the FT of a tillable texture, since it's tillable there are no abrupt changes on the horizontal and vertical sides, so there are no horizontal and vertical lines in the spectrum:



2D Filters


Now comes the most interesting application of the FT on images: you can easily apply all sorts of filters to the spectrum, again by multiplying them with a 2D transfer function, or by making some parts of the spectrum zero, or just applying some whacko formula to the spectrum. After doing that, take the inverse FT of the modified spectrum to get the filtered image.

Here's part of the code for a program that'll allow you to select different images (a bitmap, modified versions of it, and some generated functions), and then after pressing space, allows you to apply different filters and see their effect.
This code doesn't contain much new, it's much more interesting to run it and study the results of the filters.

Once again, first come all the declarations of functions and variables. f2 and F2 will become the buffers for the filtered versions of the original image and spectrum.


		//yeah, we're working with fixed sizes again...
const int N = 128; //the width of the image
const int M = 128; //the height of the image

double fRe[N][M][3], fIm[N][M][3], fAmp[N][M][3]; //the signal's real part, imaginary part,
and amplitude
double FRe[N][M][3], FIm[N][M][3], FAmp[N][M][3]; //the FT's real part,
imaginary part and amplitude
double fRe2[N][M][3], fIm2[N][M][3], fAmp2[N][M][3]; //will become the signal again 
after IDFT of the spectrum
double FRe2[N][M][3], FIm2[N][M][3], FAmp2[N][M][3]; //filtered spectrum

double pi = 3.1415926535897932384626433832795;

void draw(int xpos, int yPos, int n, int m, double *g, bool shift, bool neg128);
void FFT2D(int n, int m, bool inverse, double *gRe, double *gIm, double *GRe, double *GIm);
void calculateAmp(int n, int m, double *ga, double *gRe, double *gIm);

The main function loads a PNG image first, and will then start the first loop, the loop that lets you try out different modified versions of the PNG image and some other generated signals:

int main(int /*argc*/, char */*argv*/[])
{
  screen(3 * N,4 * M + 8, 0,"2D FFT and Filters");
  std::vector img;
  unsigned long dummyw, dummyh;
  if(loadImage(img, dummyw, dummyh, "pics/test.png"))
  {
    print("image pics/test.png not found");
    redraw();
    sleep();
    cls();
  }
  //set signal to the image
  for(int x = 0; x < N; x++)
  for(int y = 0; y < M; y++)
  {
    fRe[x][y][0] = img[N * y + x].r;
    fRe[x][y][1] = img[N * y + x].g;
    fRe[x][y][2] = img[N * y + x].b;
  }

  int ytrans=8; //translate everything a bit down to put the text on top

  //set new FT buffers   
  for(int x = 0; x < N; x++)
  for(int y = 0; y < M; y++)
  for(int c = 0; c < 3; c++)
  {
    FRe2[x][y][c] = FRe[x][y][c];
    FIm2[x][y][c] = FIm[x][y][c];
  }
 
  bool changed = 1, endloop = 0;
  while(!endloop)
  {
    if(done()) end();
    readKeys();

Here's a small part of the input part of the first loop, it looks pretty messy here, only a few keys are shown here, the code for all keys is included in the downloadable file.

    if(keyPressed(SDLK_a) || changed)
    {
      for(int x = 0; x < N; x++)
      for(int y = 0; y < M; y++)
      for(int c = 0; c < 3; c++)
      {
        fRe2[x][y][c] = fRe[x][y][c];
      } changed = 1;
    } //no effect
    if(keyPressed(SDLK_b))
    {
      for(int x = 0; x < N; x++)
      for(int y = 0; y < M; y++)
      for(int c = 0; c < 3; c++)
      {
        fRe2[x][y][c] = 255 - fRe[x][y][c];
      }
    changed = 1;} //negative
    if(keyPressed(SDLK_c))
    {
      for(int x = 0; x < N; x++)
      for(int y = 0; y < M; y++)
      for(int c = 0; c < 3; c++)
      {
        fRe2[x][y][c] = fRe[x][y][c]/2;
      }
      changed = 1;
    } //half amplitude


    //ETCETERA... *snip*

    if(keyPressed(SDLK_SPACE)) endloop = 1;

If a key was pressed, the new version of the image and it's spectrum will be drawn. If the first loop was done (by pressing space), the second loop is initialized:

    if(changed)
    {
      //Draw the image and it's FT
      calculateAmp(N, M, fAmp2[0][0], fRe2[0][0], fIm2[0][0]);
      draw(0, ytrans, N, M, fRe2[0][0], 0, 0);  draw(N, 0+ytrans, N, M,
	  fIm2[0][0], 0, 0);
	  draw(2 * N, 0+ytrans, N, M, fAmp2[0][0], 0, 0); //draw real, 
	  imag and amplitude
      FFT2D(N, M, 0, fRe2[0][0], fIm2[0][0], FRe[0][0], FIm[0][0]);
      calculateAmp(N, M, FAmp[0][0], FRe[0][0], FIm[0][0]);
      draw(0,M + ytrans, N, M, FRe[0][0], 1, 1);  draw(N, M + ytrans, N, M, 
	  FIm[0][0], 1, 1);
	  draw(2 * N, M + ytrans, N, M, FAmp[0][0], 1, 0); //draw real, imag and amplitude   
      print("Press a-z for effects and space to accept", 0, 0, RGB_White, 
	  1, ColorRGB(128, 0, 0));
      redraw();
    }
    changed = 0;
  }
  changed = 1;
  while(!done())
  {
    readKeys();

Here's a small part of the input code to apply filters: a Low Pass, High Pass and Band Pass filter are given. The rest of the keys is in the downloadable file.

    if(keyPressed(SDLK_f))
    {
      for(int x = 0; x < N; x++)
      for(int y = 0; y < M; y++)
      for(int c = 0; c < 3; c++)
      {
        if(x * x + y * y < 64 || (N - x) * (N - x) + (M - y) * (M - y) < 64 ||
		x * x + (M - y) * (M - y) < 64 || (N - x) * (N - x) + y * y < 64)
        {
          FRe2[x][y][c] = FRe[x][y][c];
          FIm2[x][y][c] = FIm[x][y][c];
        }
        else
        {
          FRe2[x][y][c] = 0;
          FIm2[x][y][c] = 0;
        }
      }
      changed = 1;
    } //LP filter

    if(keyPressed(SDLK_i))
    {
      for(int x = 0; x < N; x++)
      for(int y = 0; y < M; y++)
      for(int c = 0; c < 3; c++)
      {
        if(x * x + y * y > 16 && (N - x) * (N - x) + (M - y) * (M - y)
		> 16 && x * x + (M - y) * (M - y) > 16 && (N - x) *
			(N - x) + y * y > 16)
        {
          FRe2[x][y][c] = FRe[x][y][c];
          FIm2[x][y][c] = FIm[x][y][c];
        }
        else
        {
          FRe2[x][y][c] = 0;
          FIm2[x][y][c] = 0;
        }
      }
      changed = 1;
    } //HP filter

    if(keyPressed(SDLK_s))
    {
      for(int x = 0; x < N; x++)
      for(int y = 0; y < M; y++)
      for(int c = 0; c < 3; c++)
      {
        if((x * x + y * y < 256 || (N - x) * (N - x) + (M - y) * (M - y) < 256 || 
		x * x + (M - y) * (M - y) < 256 || (N - x) * (N - x) + y * y < 256) &&
		(x * x + y * y > 128 && (N - x) * (N - x) + (M - y) * (M - y) > 128 && 
		x * x + (M - y) * (M - y) > 128 && (N - x) * (N - x) + y * y > 128))
        {
          FRe2[x][y][c] = FRe[x][y][c];
          FIm2[x][y][c] = FIm[x][y][c];
        }
        else
        {
          FRe2[x][y][c] = 0;
          FIm2[x][y][c] = 0;
        }
      }
      changed = 1;
    } //BP filter

    //ETCETERA... *snip*

This is the part of the second loop that draws the filtered spectrum and signal, and the final part of the main function:

    if(changed)
    {
      //after pressing a key: calculate the inverse!  
      FFT2D(N, M, 1, FRe2[0][0], FIm2[0][0], fRe[0][0], fIm[0][0]);
      calculateAmp(N, M, fAmp[0][0], fRe[0][0], fIm[0][0]);
      draw(0, 3 * M + ytrans, N, M, fRe[0][0], 0, 0);  draw(N, 3 * M + ytrans, N, M, fIm[0][0], 0, 0);
	  draw(2 * N, 3 * M + ytrans, N, M, fAmp[0][0], 0, 0);
      calculateAmp(N, M, FAmp2[0][0], FRe2[0][0], FIm2[0][0]);
      draw(0, 2 * M + ytrans, N, M, FRe2[0][0], 1, 1);  draw(N, 2 * M + ytrans, N, M, FIm2[0][0], 1, 1);
	  draw(2 * N, 2 * M + ytrans, N, M, FAmp2[0][0], 1, 0);
      print("Press a-z for filters and arrows to change DC", 0, 0, RGB_White, 1, ColorRGB(128, 0, 0));
      redraw();
    }
    changed=0;
  }
  return 0;
}

The functions FFT2D, draw and calculateAmp are the same as before again and not shown here. They're also in the downloadable file.

Here's a possible output of the program:



The top row shows the original image, below that is it's spectrum (the amplitude on the right), the third row shows the spectrum with a low pass filter applied to it: only the low frequency components remain. The bottom row shows the result of the Inverse FT on the new spectrum: all high frequency components of the image are removed, and the image becomes blurred.

Here's another example, which shows what happens if you set the imaginary part of the spectrum to 0. To get this, first press space and then press the b key in the program.



More on different types of filters follows in the next sections.

© Lode Vandevenne. Reproduced with permission.


Be the first one to comment on this page.




  Graphics eBooks
More Links » »
 
 Graphics FAQs
More Links » »
 
 Graphics Interview Questions
More Links » »
 
 Graphics Articles
More Links » »
 
 Graphics News
More Links » »
 
 Graphics Jobs
More Links » »

Share And Enjoy:These icons link to social bookmarking sites where readers can share and discover new web pages.
  • blinkbits
  • BlinkList
  • blogmarks
  • co.mments
  • connotea
  • del.icio.us
  • De.lirio.us
  • digg
  • Fark
  • feedmelinks
  • Furl
  • LinkaGoGo
  • Ma.gnolia
  • NewsVine
  • Netvouz
  • RawSugar
  • Reddit
  • scuttle
  • Shadows
  • Simpy
  • Smarking
  • Spurl
  • TailRank
  • Wists
  • YahooMyWeb

Previoushome Next

Keywords: 2D Fourier Transform on Images, Graphics, Graphics, Graphics tutorial, Graphics tutorial pdf, history of Graphics, learn Graphics

HTML Quizzes
HTML Quiz
XHTML Quiz
CSS Quiz
TCP/IP Quiz
CSS 1.0 Quiz
CSS 2.0 Quiz
HLML Quiz
XML Quizzes
XML Quiz
XSL Quiz
XSLT Quiz
DTD Quiz
Schema Quiz
XForms Quiz
XSL-FO Quiz
XML DOM Quiz
XLink Quiz
XQuery Quiz
XPath Quiz
XPointer Quiz
RDF Quiz
SOAP Quiz
WSDL Quiz
RSS Quiz
WAP Quiz
Web Services Quiz
Browser Scripting Quizzes
JavaScript Quiz
VBScript Quiz
DHTML Quiz
HTML DOM Quiz
WMLScript Quiz
E4X Quiz
Server Scripting Quizzes
ASP Quiz
PERL Quiz
SQL Quiz
ADO Quiz
CVS Quiz
Python Quiz
Apple Script Quiz
PL/SQL Quiz
SQL Server Quiz
PHP Quiz
.NET (dotnet) Quizzes
Microsoft.Net Quiz
ASP.Net Quiz
.Net Mobile Quiz
C# : C Sharp Quiz
ADO.NET Quiz
VB.NET Quiz
VC++ Quiz
Multimedia Quizzes
SVG Quiz
Flash Quiz
Media Quiz
SMIL Quiz
Photoshop Quiz
Gimp Quiz
Matlab Quiz
Gnuplot Programming Quiz
GIF Animation Quiz
Scientific Visualization Quiz
Graphics Quiz
Web Building Quizzes
Web Browsers Quiz
Web Hosting Quiz
W3C Quiz
Web Building Quiz
Web Quality Quiz
Web Semantic Quiz
Web Careers Quiz
Weblogic Quiz
SEO Quiz
Web Site Hosting Quiz
Domain Name Quiz
Java Quizzes
Java Quiz
JSP Quiz
Servlets Quiz
Struts Quiz
EJB Quiz
JMS Quiz
JMX Quiz
Eclipse Quiz
J2ME Quiz
JBOSS Quiz
Programming Langauges Quizzes
C Quiz
C++ Quiz
Visual Basic Quiz
Data Structures Using C Quiz
Cobol Quiz
Assembly Language Quiz
Mainframe Quiz
Forth Programming Quiz
Lisp Programming Quiz
Pascal Quiz
Delphi Quiz
Fortran Quiz
OOPs Quiz
Data Warehousing Quiz
CGI Programming Quiz
Emacs Quiz
Gnome Quiz
ILU Quiz
Soft Skills Quizzes
Communication Skills Quiz
Time Management Quiz
Project Management Quiz
Team Work Quiz
Leadership Skills Quiz
Corporate Communication Quiz
Negotiation Skills Quiz
Database Quizzes
Oracle Quiz
MySQL Quiz
Operating System Quizzes
BSD Quiz
Symbian Quiz
Unix Quiz
Internet Quiz
IP-Masquerading Quiz
IPC Quiz
MIDI Quiz
Software Testing Quizzes
Testing Quiz
Firewalls Quiz
SAP Module Quizzes
ERP Quiz
ABAP Quiz
Business Warehousing Quiz
SAP Basis Quiz
Material Management Quiz
Sales & Distribution Quiz
Human Resource Quiz
Netweaver Quiz
Customer Relationship Management Quiz
Production and Planning Quiz
Networking Programming Quizzes
Corba Quiz
Networking Quiz
Microsoft Office Quizzes
Microsoft Word Quiz
Microsoft Outlook Quiz
Microsoft PowerPoint Quiz
Microsoft Publisher Quiz
Microsoft Excel Quiz
Microsoft Front Page Quiz
Microsoft InfoPath Quiz
Microsoft Access Quiz
Accounting Quizzes
Financial Accounting Quiz
Managerial Accounting Quiz
Testimonials | Contact Us | Link to Us | Site Map
Copyright 2008. Academic Tutorials.com. All rights reserved Privacy Policies | About Us
Our Portals : Academic Tutorials | Best eBooksworld | Beyond Stats | City Details | Interview Questions | Discussions World | Excellent Mobiles | Free Bangalore | Give Me The Code | Gog Logo | Indian Free Ads | Jobs Assist | New Interview Questions | One Stop FAQs | One Stop GATE | One Stop GRE | One Stop IAS | One Stop MBA | One Stop SAP | One Stop Testing | Webhosting in India | Dedicated Server in India | Sirf Dosti | Source Codes World | Tasty Food | Tech Archive | Testing Interview Questions | Tests World | The Galz | Top Masala | Vyom | Vyom eBooks | Vyom International | Vyom Links | Vyoms | Vyom World
Copyright 2003-2017 Vyom Technosoft Pvt. Ltd., All Rights Reserved.