The Fourier transform is a generalization of the complex Fourier series in the limit as
 |  | | (1) |
| | | (2) |
Here,
| | | (3) |
| | | (4) |
is called the forward (
| | | (5) |
| | | (6) |
is called the inverse (
Note that some authors (especially physicists) prefer to write the transform in terms of angular frequency
| | | (7) |
| | | (8) |
| | | (9) |
| | | (10) |
To restore the symmetry of the transforms, the convention
| | | (11) |
| | | (12) |
| | | (13) |
| | | (14) |
is sometimes used (Mathews and Walker 1970, p. 102).
In general, the Fourier transform pair may be defined using two arbitrary constants
| | | (15) |
| | | (16) |
The Fourier transform
Since any function can be split up into even and odd portions
| | | (17) |
| | | (18) |
a Fourier transform can always be expressed in terms of the Fourier cosine transform and Fourier sine transform as
| (19) |
A function
| (20) |
provided that
1.
2. There are a finite number of discontinuities.
3. The function has bounded variation. A sufficient weaker condition is fulfillment of the Lipschitz condition
(Ramirez 1985, p. 29). The smoother a function (i.e., the larger the number of continuous derivatives), the more compact its Fourier transform.
The Fourier transform is linear, since if
| | | (21) |
| | | (22) |
Therefore,
| | | (23) |
| | | (24) |
The Fourier transform is also symmetric since
Let
| | | (25) |
| | | (26) |
| | | (27) |
| | | (28) |
The first of these is derived as follows:
| | | (29) |
| | | (30) |
| | | (31) |
| | | (32) |
where
There is also a somewhat surprising and extremely important relationship between the autocorrelation and the Fourier transform known as the Wiener-Khinchin theorem. Let
| (33) |
The Fourier transform of a derivative
| (34) |
Now use integration by parts
| (35) |
with
| | | (36) |
| | | (37) |
and
| | | (38) |
| | | (39) |
then
| (40) |
The first term consists of an oscillating function times
| (41) |
(as any physically significant signal must be), then the term vanishes, leaving
| | | (42) |
| | | (43) |
This process can be iterated for the
| (44) |
The important modulation theorem of Fourier transforms allows
| | | (45) |
| | | (46) |
| | | (47) |
| | | (48) |
Since the derivative of the Fourier transform is givenby
| (49) |
it follows that
| (50) |
Iterating gives the general formula
| | | (51) |
| | | (52) |
The variance of a Fourier transform is
| (53) |
and it is true that
| (54) |
If
| | | (55) |
| | | (56) |
so
| (57) |
If
| (58) |
so
| (59) |
The "equivalent width" of a Fourier transform is
| | | (60) |
| | | (61) |
The "autocorrelation width" is
| | | (62) |
| | | (63) |
where
Any operation on
| (64) |
The following table summarized some common Fourier transform pairs.
In two dimensions, the Fourier transform becomes
| | | (65) |
| | | (66) |
Similarly, the
| | | (67) |
| | | (68) |
The Fourier Transform is animportant image processing tool which is used to decompose an imageinto its sine and cosine components. The output of the transformationrepresents the image in the Fourier or frequencydomain, while the input image is the spatial domainequivalent. In the Fourier domain image, each point represents aparticular frequency contained in the spatial domain image.
The Fourier Transform is used in a wide range of applications, such asimage analysis, image filtering, image reconstruction and imagecompression.
As we are only concerned with digital images, we will restrict thisdiscussion to the Discrete Fourier Transform (DFT).
The DFT is the sampled Fourier Transform and therefore does notcontain all frequencies forming an image, but only a set of sampleswhich is large enough to fully describe the spatial domain image. Thenumber of frequencies corresponds to the number of pixels in the spatialdomain image, i.e. the image in the spatial and Fourier domain are of thesame size.
For a square image of size N×N, the two-dimensional DFT is given by:
where f(a,b) is the image in the spatial domain and the exponentialterm is the basis function corresponding to each point F(k,l) inthe Fourier space. The equation can be interpreted as: the value ofeach point F(k,l) is obtained by multiplying thespatial image with the corresponding base function and summing theresult.
The basis functions are sine and cosine waves with increasing frequencies, i.e. F(0,0) represents the DC-component of the image which corresponds to the average brightness and F(N-1,N-1) represents the highest frequency.
In a similar way, the Fourier image can be re-transformed to thespatial domain. The inverse Fouriertransform is given by:
Note the
To obtain the result for the above equations, a double sum has to becalculated for each image point. However, because the Fourier Transform isseparable, it can be written as
where
Using these two formulas, the spatial domain image is first transformedinto an intermediate image using N one-dimensional FourierTransforms. This intermediate image is then transformed into the finalimage, again using N one-dimensional FourierTransforms. Expressing the two-dimensional Fourier Transform in termsof a series of 2N one-dimensional transforms decreases the numberof required computations.
Even with these computationalsavings, the ordinary one-dimensional DFT has
The Fourier Transform produces a complex number valued output imagewhich can be displayed with two images, either with the realand imaginary part or with magnitude and phase. Inimage processing, often only the magnitude of the Fourier Transform isdisplayed, as it contains most of the information of the geometricstructure of the spatial domain image. However, if we want to re-transformthe Fourier image into the correct spatial domain after some processing inthe frequency domain, we must make sure to preserve both magnitude andphase of the Fourier image.
The Fourier domain image has a much greater range than the image inthe spatial domain. Hence, to be sufficiently accurate, its values areusually calculated and stored in float values.
The Fourier Transform is used if we want to access the geometriccharacteristics of a spatial domain image. Because the image in theFourier domain is decomposed into its sinusoidal components, it iseasy to examine or process certain frequencies of the image, thusinfluencing the geometric structure in the spatial domain.
In most implementations the Fourier image is shifted in such a way that theDC-value (i.e. the image mean) F(0,0) is displayed in the centerof the image. The further away from the center an image point is, thehigher is its corresponding frequency.
We start off by applying the Fourier Transform of
The magnitude calculated from the complexresult is shown in
We can see that theDC-value is by far the largest component of the image. However, thedynamic range of the Fourier coefficients (i.e. the intensity values inthe Fourier image) is too large to be displayed on the screen,therefore all other values appear as black. If we apply alogarithmic transformation to the image we obtain
The result shows that the image containscomponents of all frequencies, but that their magnitude gets smallerfor higher frequencies. Hence, low frequencies contain more imageinformation than the higher ones. The transform image also tells usthat there are two dominating directions in the Fourier image, onepassing vertically and one horizontally through the center. Theseoriginate from the regular patterns in the background of the originalimage.
The phase of the Fourier transform of the same image is shown in
The value of each point determines thephase of the corresponding frequency. As in the magnitude image, wecan identify the vertical and horizontal lines corresponding to thepatterns in the original image. The phase image does not yield muchnew information about the structure of the spatial domain image;therefore, in the following examples, we will restrict ourselves todisplaying only the magnitude of the Fourier Transform.
Before we leave the phase image entirely, however, note that if weapply the inverse Fourier Transform to the above magnitude image whileignoring the phase (and then histogram equalize theoutput) we obtain
Although this image containsthe same frequencies (and amount of frequencies) as the original inputimage, it is corrupted beyond recognition. This shows that the phaseinformation is crucial to reconstruct the correct image in the spatialdomain.
We will now experiment with some simple images to betterunderstand the nature of the transform. The response of the FourierTransform to periodic patterns in the spatial domain images can be seenvery easily in the following artificial images.
The image
shows 2 pixel wide vertical stripes. The magnitude of theFourier transform of this image is shown in
If we look carefully, we can see that itcontains 3 main values: the DC-value and, since the Fourier image issymmetrical to its center, two points corresponding to the frequencyof the stripes in the original image. Note that the two points lie ona horizontal line through the image center, because the imageintensity in the spatial domain changes the most if we go along ithorizontally.
The distance of the points to the center can be explained as follows:the maximum frequency which can be represented in the spatial domain aretwo pixel wide stripe pairs (one white, one black).
Hence, the two pixel wide stripes in theabove image represent
Thus, the points in the Fourierimage are halfway between the center and the edge of the image, i.e.the represented frequency is half of the maximum.
Further investigation of the Fourier image shows that the magnitude ofother frequencies in the image is less than
Similar effects as in the above example can be seen when applying theFourier Transform to
which consists of diagonalstripes. In
showing the magnitude of the FourierTransform, we can see that, again, the main components of thetransformed image are the DC-value and the two points corresponding tothe frequency of the stripes. However, the logarithmic transform of theFourier Transform,
shows that now the imagecontains many minor frequencies. The main reason is that adiagonal can only be approximated by the square pixels of the image,hence, additional frequencies are needed to compose the image. Thelogarithmic scaling makes it difficult to tell the influence of singlefrequencies in the original image. To find the most importantfrequencies we threshold the original Fourier magnitude image atlevel 13. The resulting Fourier image,
shows allfrequencies whose magnitude is at least 5% of the main peak. Comparedto the original Fourier image, several more points appear. They areall on the same diagonal as the three main components, i.e. they alloriginate from the periodic stripes. The represented frequencies areall multiples of the basic frequency of the stripes in the spatial domainimage. This is because a rectangular signal, like the stripes, withthe frequency
A Fourier-Transformedimage can be used for frequency filtering.A simple example is illustrated with the above image. If we multiplythe (complex) Fourier image obtained above with an image containing acircle (of r = 32 pixels), we can set all frequencies larger than
By applying the inverseFourier Transform we obtain
The resultingimage is a lowpass filtered version of the original spatial domainimage. Since all other frequencies have been suppressed, this resultis the sum of the constant DC-value and a sine-wave with the frequency
A property of the Fourier Transform which is used, for example, forthe removal of additive noise, is its distributivityover addition. We can illustrate this by adding thecomplex Fourier images of the two previous example images. To displaythe result and emphasize the main peaks, we threshold the magnitude ofthe complex image, as can be seen in
Applyingthe inverse Fourier Transform to the complex image yields
According to the distributivity law, this imageis the same as the direct sum of the two original spatial domain images.
Finally, we present an example (i.e. text orientation finding) wherethe Fourier Transform is used to gain information about the geometricstructure of the spatial domain image. Text recognition using imageprocessing techniques is simplified if we can assume that the textlines are in a predefined direction. Here we show how the FourierTransform can be used to find the initial orientation of the text andthen a rotation can be applied to correct the error. Weillustrate this technique using
a binaryimage of English text. The logarithm of the magnitude of its Fouriertransform is
and
isthe thresholded magnitude of the Fourier image. We can see that themain values lie on a vertical line, indicating that the text lines inthe input image are horizontal.
If we proceed in the same way with
which was rotated about 45°, we obtain
and
in the Fourier space. Wecan see that the line of the main peaks in the Fourier domain isrotated according to rotation of the input image. The second line inthe logarithmic image (perpendicular to the main direction) originatesfrom the black corners in the rotated image.
Although we managed to find a threshold which separates the main peaks from the background, we have a reasonable amount of noise in the Fourier image resulting from the irregular pattern of the letters. We could decrease these background values and therefore increase the difference to the main peaks if we were able to form solid blocks out of the text-lines. This could, for example, be done by using a morphological operator.
Another sinusoidal transform(i.e. transform with sinusoidal base functions) related to the DFT isthe Discrete Cosine Transform (DCT). For an N×N image, theDCT is given by
with
Themain advantages of the DCT are that it yields a real valued outputimage and that it is a fast transform. A major use of the DCT is inimage compression --- i.e. trying to reduce the amount of data neededto store an image. After performing a DCT it is possible to throw awaythe coefficients that encode high frequency components that the humaneye is not very sensitive to. Thus the amount of data can be reduced,without seriously affecting the way an image looks to the human eye.
联系客服
