Click here to Skip to main content
11,645,087 members (70,408 online)
Click here to Skip to main content

2D FFT of an Image in C#

, 20 Jul 2012 CPOL 127.6K 8.2K 72
Rate this:
Please Sign up or sign in to vote.
Two dimensional Fast Fourier Transform of an image in C#.

Introduction

A Fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. There are many distinct FFT algorithms involving a wide range of mathematics, from simple complex-number arithmetic to group theory and number theory; this article gives an overview of the available techniques and some of their general properties, while the specific algorithms are described in subsidiary articles linked below.

A DFT decomposes a sequence of values into components of different frequencies. This operation is useful in many fields (see discrete Fourier transform for properties and applications of the transform), but computing it directly from the definition is often too slow to be practical. An FFT is a way to compute the same result more quickly: computing a DFT of N points in the obvious way, using the definition, takes O(N 2) arithmetical operations, while an FFT can compute the same result in only O(N log N) operations. The difference in speed can be substantial, especially for long data sets where N may be in the thousands or millions—in practice, the computation time can be reduced by several orders of magnitude in such cases, and the improvement is roughly proportional to N/log(N). This huge improvement made many DFT-based algorithms practical; FFTs are of great importance to a wide variety of applications, from digital signal processing and solving partial differential equations to algorithms for quick multiplication of large integers.

Cooley–Tukey algorithm

By far the most common FFT is the Cooley–Tukey algorithm. This is a divide and conquer algorithm that recursively breaks down a DFT of any composite size N = N1N2 into many smaller DFTs of sizes N1 and N2, along with O(N) multiplications by complex roots of unity traditionally called twiddle factors.

This method (and the general idea of an FFT) was popularized by a publication of J. W. Cooley and J. W. Tukey in 1965, but it was later discovered (Heideman & Burrus, 1984) that those two authors had independently re-invented an algorithm known to Carl Friedrich Gauss around 1805 (and subsequently rediscovered several times in limited forms).

The most well-known use of the Cooley–Tukey algorithm is to divide the transform into two pieces of size N / 2 at each step, and is therefore limited to power-of-two sizes, but any factorization can be used in general (as was known to both Gauss and Cooley/Tukey). These are called the radix-2 and mixed-radix cases, respectively (and other variants such as the split-radix FFT have their own names as well). Although the basic idea is recursive, most traditional implementations rearrange the algorithm to avoid explicit recursion. Also, because the Cooley–Tukey algorithm breaks the DFT into smaller DFTs, it can be combined arbitrarily with any other algorithm for the DFT, such as those described below.

Using the code

First, we read the selected image into a 2D array of integers; we are using a pointer based image reading for the same. The code is as follows:

private void ReadImage()
{
    int i, j;
    GreyImage = new int[Width, Height];  //[Row,Column]
    Bitmap image = Obj;
    BitmapData bitmapData1 = 
       image.LockBits(new Rectangle(0, 0, image.Width, image.Height),
       ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);
    unsafe
    {
        byte* imagePointer1 = (byte*)bitmapData1.Scan0;

        for (i = 0; i < bitmapData1.Height; i++)
        {
            for (j = 0; j < bitmapData1.Width; j++)
            {
                GreyImage[j, i] = (int)((imagePointer1[0] + 
                   imagePointer1[1] + imagePointer1[2]) / 3.0);
                //4 bytes per pixel
                imagePointer1 += 4;
            }//end for j
            //4 bytes per pixel
            imagePointer1 += bitmapData1.Stride - (bitmapData1.Width * 4);
        }//end for i
    }//end unsafe
    image.UnlockBits(bitmapData1);
    return;
}

FFT of an image will be a complex array; we need to store this thing, so we define a complex structure for the same.

struct COMPLEX
{
    public double real, imag;
    public COMPLEX(double x, double y)
    {
        real = x;
        imag = y;
    }
    public float Magnitude()
    {
        return ((float)Math.Sqrt(real * real + imag * imag));
    }
    public float Phase()
    {            
         return ((float)Math.Atan(imag / real));
    }
}

The FFT is implemented using the separability property of a Fourier transform. We find the FFT of the rows of an image and then the columns.

Points of interest

The Fourier plot is generated, frequency shifting is performed on the complex Fourier coefficients array, and using dynamic range compression, we generate the Fourier plot. 

Original C++ code used for Reference can be found Here (Thank to Paul Bourke) 

http://local.wasp.uwa.edu.au/~pbourke/miscellaneous/dft/

 

History

This is my first article on FFT, any suggestions and modifications are welcome.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author


You may also be interested in...

Comments and Discussions

 
Questionplot into a graph Pin
Member 1173875429-Jul-15 4:49
memberMember 1173875429-Jul-15 4:49 
QuestionImplementation on CCS studio Pin
Member 114346927-Feb-15 2:40
memberMember 114346927-Feb-15 2:40 
BugGiving error ! Pin
Member 1076608722-Apr-14 0:45
memberMember 1076608722-Apr-14 0:45 
QuestionMissing reference Pin
Stevea200024-Feb-14 13:16
memberStevea200024-Feb-14 13:16 
QuestionQuestion about calculating the energy spectrum Pin
Member 871827623-Dec-12 0:37
memberMember 871827623-Dec-12 0:37 
AnswerRe: Question about calculating the energy spectrum Pin
Dr. Vinayak Ashok Bharadi17-Jan-13 22:31
memberDr. Vinayak Ashok Bharadi17-Jan-13 22:31 
Questionx and y values ? Pin
efekucukkeskin17-Oct-12 5:10
memberefekucukkeskin17-Oct-12 5:10 
AnswerRe: x and y values ? Pin
Dr. Vinayak Ashok Bharadi17-Jan-13 22:32
memberDr. Vinayak Ashok Bharadi17-Jan-13 22:32 
QuestionFFT, c# Pin
vampiluna4-Oct-12 22:41
membervampiluna4-Oct-12 22:41 
QuestionRestoring color Pin
Eugene Popov18-Sep-12 1:04
memberEugene Popov18-Sep-12 1:04 
AnswerRe: Restoring color Pin
Dr. Vinayak Ashok Bharadi8-Oct-12 20:03
memberDr. Vinayak Ashok Bharadi8-Oct-12 20:03 
QuestionRemoveFFTShift = FFTShift Pin
andreynikif18-Aug-12 9:52
memberandreynikif18-Aug-12 9:52 
Questionquzzz Pin
sachitha123457-Aug-12 18:20
membersachitha123457-Aug-12 18:20 
AnswerRe: quzzz Pin
Dr. Vinayak Ashok Bharadi7-Aug-12 23:53
memberDr. Vinayak Ashok Bharadi7-Aug-12 23:53 
GeneralMy vote of 2 Pin
Kevin Bewley23-Jul-12 4:00
memberKevin Bewley23-Jul-12 4:00 
QuestionComplex struct.. there's already a class for that Pin
Kevin Bewley23-Jul-12 3:59
memberKevin Bewley23-Jul-12 3:59 
AnswerRe: Complex struct.. there's already a class for that Pin
Dr. Vinayak Ashok Bharadi7-Aug-12 23:50
memberDr. Vinayak Ashok Bharadi7-Aug-12 23:50 
GeneralRe: Complex struct.. there's already a class for that Pin
Kevin Bewley8-Aug-12 0:01
memberKevin Bewley8-Aug-12 0:01 
GeneralRe: Complex struct.. there's already a class for that Pin
Dr. Vinayak Ashok Bharadi8-Aug-12 21:22
memberDr. Vinayak Ashok Bharadi8-Aug-12 21:22 
QuestionThanks Pin
andreynikif23-Jun-12 18:30
memberandreynikif23-Jun-12 18:30 
AnswerRe: [My vote of 1] This is Paul Bourke's code. Pin
Dr. Vinayak Ashok Bharadi20-Jul-12 0:50
memberDr. Vinayak Ashok Bharadi20-Jul-12 0:50 
AnswerRe: [My vote of 1] This is Paul Bourke's code. Pin
Dr. Vinayak Ashok Bharadi20-Jul-12 0:54
memberDr. Vinayak Ashok Bharadi20-Jul-12 0:54 
Question2D FFT final return Pin
chamara547-Jun-12 19:03
memberchamara547-Jun-12 19:03 
AnswerRe: 2D FFT final return Pin
Dr. Vinayak Ashok Bharadi20-Jul-12 0:56
memberDr. Vinayak Ashok Bharadi20-Jul-12 0:56 
GeneralRe: 2D FFT final return Pin
chamara547-Aug-12 19:55
memberchamara547-Aug-12 19:55 
GeneralRe: 2D FFT final return Pin
Dr. Vinayak Ashok Bharadi7-Aug-12 23:59
memberDr. Vinayak Ashok Bharadi7-Aug-12 23:59 
AnswerRe: 2D FFT final return Pin
sachitha123457-Aug-12 18:27
membersachitha123457-Aug-12 18:27 
GeneralRe: 2D FFT final return Pin
chamara547-Aug-12 19:43
memberchamara547-Aug-12 19:43 
GeneralMy vote of 5 Pin
manoj kumar choubey28-Mar-12 0:35
membermanoj kumar choubey28-Mar-12 0:35 
GeneralThanks Pin
Caspilar28-Apr-11 18:51
memberCaspilar28-Apr-11 18:51 
Generalshifting th image Pin
hooper195416-Mar-11 8:28
memberhooper195416-Mar-11 8:28 
GeneralRe: shifting th image Pin
QuantumDJ20-May-13 2:41
memberQuantumDJ20-May-13 2:41 
Generalfft and ifft Pin
N. krishnam19-Jul-10 3:03
memberN. krishnam19-Jul-10 3:03 
GeneralError [fix] Pin
Dadsy3-Mar-10 12:43
memberDadsy3-Mar-10 12:43 
GeneralGreat article Pin
aldo hexosa18-Feb-10 15:32
memberaldo hexosa18-Feb-10 15:32 
GeneralInverse FFT issue Pin
Collin Jasnoch23-Dec-09 8:29
memberCollin Jasnoch23-Dec-09 8:29 
GeneralRe: Inverse FFT issue Pin
Vinayak Bharadi23-Dec-09 17:01
memberVinayak Bharadi23-Dec-09 17:01 
General[My vote of 2] Simple but lacking Pin
Collin Jasnoch15-Dec-09 10:13
memberCollin Jasnoch15-Dec-09 10:13 
GeneralRe: [My vote of 2] Simple but lacking Pin
Collin Jasnoch15-Dec-09 11:16
memberCollin Jasnoch15-Dec-09 11:16 
GeneralRe: [My vote of 2] Simple but lacking Pin
Collin Jasnoch15-Dec-09 11:21
memberCollin Jasnoch15-Dec-09 11:21 
GeneralRe: [My vote of 2] Simple but lacking Pin
Vinayak Bharadi18-Dec-09 20:36
memberVinayak Bharadi18-Dec-09 20:36 
Questiononly on gray images? Pin
cifftsifir2-Dec-09 3:27
membercifftsifir2-Dec-09 3:27 
AnswerRe: only on gray images? Pin
Vinayak Bharadi2-Dec-09 16:49
memberVinayak Bharadi2-Dec-09 16:49 
GeneralRe: only on gray images? Pin
cifftsifir2-Dec-09 19:49
membercifftsifir2-Dec-09 19:49 
GeneralRe: only on gray images? Pin
cifftsifir4-Dec-09 2:59
membercifftsifir4-Dec-09 2:59 
GeneralRe: only on gray images? Pin
Vinayak Bharadi4-Dec-09 16:35
memberVinayak Bharadi4-Dec-09 16:35 
GeneralRe: only on gray images? Pin
Amarnath S11-Dec-09 3:27
groupAmarnath S11-Dec-09 3:27 
GeneralComplex angle Pin
syutzy20-Nov-09 3:19
membersyutzy20-Nov-09 3:19 
GeneralRe: Complex angle Pin
Vinayak Bharadi20-Nov-09 16:52
memberVinayak Bharadi20-Nov-09 16:52 
GeneralNeeds More Pin
John Simmons / outlaw programmer19-Nov-09 23:36
mvpJohn Simmons / outlaw programmer19-Nov-09 23:36 

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

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

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150731.1 | Last Updated 20 Jul 2012
Article Copyright 2009 by Dr. Vinayak Ashok Bharadi
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid