Properties of the Fourier transform

± ± ±

In this section we discuss the basic properties of the continuous and dis- crete Fourier transform. We point out those properties of the FT that are most signiﬁ cant for image processing. Together with some basic Fourier transform pairs ( R5), these general properties ( R4, R7) form a pow- erful framework with which further properties of the Fourier transform and the transforms of many functions can be derived without much ef- fort.

Periodicity of DFT. The kernel of the DFT Eq. (2.25) shows a character- istic periodicity

exp.− 2π i(n + lN) Σ = exp.− 2π in Σ , w⁽ⁿ^+lN) = wⁿ, ∀ l ∈ Z. (2.43)

48 2 Image Representation

A b

Figure 2.14: Geometric interpretation of the periodicity of the one- and two- dimensional DFT with a the Fourier ring and b the Fourier torus.

The deﬁ nitions of the DFT restrict the spatial domain and the Fourier domain to a ﬁ nite number of values. If we do not care about this restric- tion and calculate the forward and back transformation for all integer numbers, we ﬁ nd from Eqs. (2.37) and (2.39) the same periodicities for functions in the space and Fourier domain:

wave number domain

gˆ u+kM, v+lN = gˆ u, v, ∀ k, l ∈ Z

(2.44)

space domain g_m_{+kM, n}_+lN = g_{m, n}, ∀ k, l ∈ Z.

These equations state a periodic replication in all directions in both domains beyond the original deﬁ nition range. The periodicity of the DFT gives rise to an interesting geometric interpretation. In the one- dimensional case, the border points g_N_{− 1} and g_N g₀ are neighbor- ing points. We can interpret this property geometrically by drawing the points of the vector not on a ﬁ nite line but on a circle, the so-called Fourier ring (Fig. 2.14a). This representation has a deeper meaning when we consider the Fourier transform as a special case of the z-transform [133]. With two dimensions, a matrix is mapped onto a torus (Fig. 2.14b), the Fourier torus.

Symmetries. Four types of symmetries are important for the Fourier transform:

even g(− x ) = g( x ),

odd g(− x ) = − g( x ), hermitian g(− x ) = g∗ ( x ), anti-hermitian g(− x ) = − g∗ ( x )

(2.45)

∗

The symbol denotes the complex conjugate. The hermitity is of im- portance because the kernels of the FT Eq. (2.18) and DFT Eq. (2.25) are hermitian.

2.3 Wave Number Space and Fourier Transform 49

Any function g( x ) can be split into its even and odd parts by

eg( x ) g( x ) + g( − x )

and ^og( x ) g( x ) − g( − x ). (2.46)

With this partition, the Fourier transform can be parted into a cosine and a sine transform:

∞ ∞

gˆ ( k ) = 2∫ eg( x ) cos(2π k ^T x )d^W x + 2i∫ og( x ) sin(2π k ^T x )d^W x. (2.47)

0 0

It follows that if a function is even or odd, its transform is also even or odd. The full symmetry relations are:

real ◦ • Hermitian

imaginary ◦ • anti-Hermitian

Hermitian ◦ • real

anti-Hermitian ◦ • imaginary

even ◦ • even

odd ◦ • odd

real and even ◦ • real and even

real and odd ◦ • imaginary and odd imaginary and even ◦ • imaginary and even imaginary and odd ◦ • real and odd

(2.48)

= ± =

The DFT shows the same symmetries as the FT (Eqs. (2.45) and (2.48)). In the deﬁ nition for even and odd functions g(− x ) = ±g( x ) only x must be replaced by the corresponding indices: g_{− n} g_n or g_{− m,}_{− n}

g_{m, n}. Note that because of the periodicity of the DFT, these symmetry relations can also be written as

g− m, − n = ±gm, n ≡ gM− m, N− n = ±gm, n (2.49)

+ −

for even ( sign) and odd ( sign) functions. This is equivalent to shifting the symmetry center from the origin to the point [M/2, N/2]^T.

The study of symmetries is important for practical purposes. Care- ful consideration of symmetry allows storage space to be saved and al- gorithms to speed up. Such a case is real-valued images. Real-valued images can be stored in half of the space as complex-valued images. From the symmetry relation Eq. (2.48) we can conclude that real-valued functions exhibit a Hermitian DFT:

g_n = g_n∗ ◦ • gˆ _N₋_v = gˆ ∗ v

(2.50)

gmn = gm∗ n ◦ •

gˆ M− u, N− v = gˆ u∗ v

The complex-valued DFT of real-valued vectors is, therefore, completely determined by the values in one half-space. The other half-space is ob- tained by mirroring at the symmetry center [N/2]. Consequently, we

50 2 Image Representation

A b

U U

-1 M-1

M/2-1

-2 M-2

-M/2

M/2 0

M/2-1 -1

0 1 2 N/2-1 N/2

-M/2

-N/2

-1 0 1

V N/2-1

Figure 2.15: a Half-space as computed by an in-place Fourier transform algo- rithm; the wave number zero is in the upper left corner; b FT with the missing half appended and remapped so that the wave number zero is in the center.

need the same amount of storage space for the DFT of a real vector as for the vector itself, as only half of the complex spectrum needs to be stored.

In two and higher dimensions, matters are slightly more complex. Again, the Fourier transform of a real-valued image is determined com- pletely by the values in one half-space, but there are many ways to select the half-space. This means that all except for one component of the wave number can be negative.

+ =

The Fourier transform of a real M N image can be represented by M rows and N/2 1 columns (Fig. 2.15) assuming that N is even. Un- fortunately, N/2 1 columns are required, because the ﬁ rst (m 0) and last column (m M/2) are symmetric to themselves according to Eq. (2.50). Thus it appears impossible to overwrite a real image by its complex Fourier transform because we need one more column. A closer examination shows that it works nevertheless. The ﬁ rst and last

columns are real-valued because of symmetry reasons (gˆ _{0, N}_{− v} = gˆ 0∗, v

and gˆ _{M/2, N}_{− v} gˆ M∗ /2, v). Therefore, the real part of column M/2 can be

stored in the imaginary part of column 0.

−

For real-valued image sequences, again we need only a half-space to represent the spectrum. Physically, it makes the most sense to choose the half-space that contains positive frequencies. In contrast to a single image, we obtain the full wave-number space. Now we can identify the spatially identical wave numbers k and k as structures propagating in opposite directions.

2.3 Wave Number Space and Fourier Transform 51

Separability. The kernel of the Fourier transform is separable (Eq. (2.34)). Therefore, the transform of a separable function is also separable:

W W

. g(x_p) ◦ •. gˆ (k_p). (2.51)

p=1 p=1

This property is essential to compute transforms of multidimensional functions eﬃ ciently from 1-Dtransforms because many of them are sep- arable.

Similarity. The similarity theorem states how a Fourier transform is inﬂ uenced by scaling of the coordinate system. In one dimension, a function can only be scaled (x' ax). In multiple dimensions, the co- ordinate system can be transformed in a more general way by an aﬃ ne transform ( x ' Ax ), i. e., the new basis vectors are linear combinations of the old basis vectors. A special case is the rotation of the coordinate system.

= =

Theorem 1 (Similarity) Be a a non-zero real number, A a real, invertible matrix, and R an orthogonal matrix representing a rotation of the coordi- nate system ( R − 1 R T, det R 1). Then the following similarity relations hold:

◦ •

Scalar g(a x ) 1

|a|

gˆ ( k /a)

◦ •

Aﬃ ne transform g( Ax ) 1 gˆ (( A T )− 1 k )

det A

(2.52)

Rotation g( Rx ) ◦ •

gˆ ( Rk )

If a function is squeezed in the spatial domain, it is stretched in the Fourier domain, and vice versa. A rotation of the coordinate system in the spatial domain causes the identical rotation in the Fourier domain.

.=n

The above similarity theorems do not apply to the discrete Fourier transform because an arbitrary scaling and rotation is not possible. A stretching of a discrete function is only possible by an integer factor K (upsampling) and the newly generated discrete points are ﬁ lled with zeros:

( g _↑_K

) g_n/K n = 0, K, 2K,... (N − 1)K)

0 otherwise.

(2.53)

Theorem 2 (Similarity, discrete) Be g a complex-valued vector with N elements and K ∈ N. Then the discrete Fourier transform of the upsam- pled vector g _{↑ K} with KN elements is given by

g ↑ K

◦ • 1 g ˆ

with

gˆ _kN_+v = gˆ _v. (2.54)

52 2 Image Representation

Upsampling by a factor K thus simply results in a K-fold replication of the Fourier transform. Note that because of the periodicity of the discrete Fourier transform discussed at the beginning of this section, gˆ _kN_+v = gˆ _v.

. Σ

Shift. In Section 2.3.1 we discussed some properties of the basis images of the Fourier space, the complex exponential functions exp 2π i k ^T x . A spatial shift of these functions causes a multiplication by a phase factor:

exp.2π i( x − x ₀)T k Σ = exp.− 2π i x T k Σ exp.2π i k ^T x Σ (2.55)

As a direct consequence of the linearity of the Fourier transform, we can formulate the following shift theorem:

Theorem 3 (Shift) If the function g( x ) has the Fourier transform gˆ ( k ), then g( x − x ₀) has the Fourier transforms exp(− 2π i x T k )gˆ ( k ).

−

Thus, a shift in the spatial domain does not change the Fourier transform except for a wave number-dependent phase change 2π x T k .

−

The shift theorem can also be applied in the Fourier domain. A shift in the Fourier space, gˆ ( k k ₀), results in a signal in the spatial domain that is modulated by a complex exponential with the wave number vector k ₀: exp(2π i k ^T x )g( x ).

Convolution. Convolution is one of the most important operations for signal processing. For a continuous signal it is deﬁ ned by

∞

(g ∗ h)( x ) =

∫ h( x ')g( x − x ')d^W x'. (2.56)

− ∞

In signal processing, the function h( x ) is normally zero except for a small area around zero and is often denoted as the convolution mask. Thus, the convolution with h( x ) results in a new function g'( x ) whose values are a kind of weighted average of g( x ) in a small neighborhood around x. It changes the signal in a deﬁ ned way, for example, makes it smoother. Therefore it is also called a ﬁ lter.

One- and two-dimensional discrete convolution are deﬁ ned analo- gous to Eq. (2.56) by

N− 1 M− 1 N− 1

g_n' =

. hn' gn− n', gm' , n = . . hm'n' gm− m', n− n' (2.57)

n'=0 m'=0n'=0

The convolution theorem for the FT and DFT states:

Theorem 4 (Convolution) If g( x )( g, G ) has the Fourier transforms gˆ ( k ) ( g ˆ, G ˆ ) and h( x ), ( h, H ) have the Fourier transforms hˆ ( k )( h ˆ, H ˆ ), then h∗

2.3 Wave Number Space and Fourier Transform 53

g( h ∗ g, H ∗ G ) has the Fourier transforms hˆ ( k )gˆ ( k ), (N h ˆ · g ˆ, MN H ˆ · G ˆ ):

FT: h( x ) ∗ g( x ) ◦ • hˆ ( k ) · gˆ ( k )

1-D DFT: h ∗ g ◦ • N h ˆ · g ˆ

2-D DFT: H ∗ G ◦ • MN H ˆ · G ˆ

(2.58)

. Σ

Thus, convolution of two functions means multiplication of their transforms. Likewise, convolution of two functions in the Fourier do- main means multiplication in the space domain. The simplicity of con- volution in the Fourier space stems from the fact that the base func-

tions of the Fourier domain, the complex exponentials exp 2π i k ^T x , are joint eigenfunctions of all convolution operators. This means that these functions are not changed by a convolution operator except for the multiplication by a factor.

From the convolution theorem, the following properties are immedi- ately evident. Convolution is

commutative h ∗ g = g ∗ h,

associative h₁ ∗ (h₂ ∗ g) = (h₁ ∗ h₂) ∗ g,

distributive over addition (h₁ + h₂) ∗ g = h₁ ∗ g + h₂ ∗ g.

(2.59)

In order to grasp the importance of these properties of convolution, we note that two operations that do not look so at ﬁ rst glance, are also convolution operations: the shift operation and all derivative operators. In both cases the Fourier transform is only multiplied by a complex factor. For a shift operation this can be seen directly from the shift theorem (Theorem 3). The convolution mask of a shift operator is a

shifted δ distribution:

S( s )g( x ) = δ ( x − s ) ∗ g( x ). (2.60) For a partial derivative of a function in the spatial domain the deriva-

tion theorem states:

Theorem 5 (Derivation) If g( x ) is diﬀ erentiable for all x and has the Fourier transform gˆ ( k ), then the Fourier transform of the partial deriva- tive ∂ g( x )/∂ x_p is 2π ik_pgˆ ( k ):

∂ g( x )

∂ x_p

◦ • 2π ik_pgˆ ( k ). (2.61)

The derivation theorem results directly from the deﬁ nition of the inverse Fourier transform in Eq. (2.33) by interchanging the partial derivative with the Fourier integral.

The inverse Fourier transform of 2π ik₁, that is, the corresponding convolution mask, is no longer an ordinary function (2π ik₁ is not ab- solutely integrable) but the derivative of the δ distribution:

2π ik

δ '(x)

dδ (x)

lim d

. exp(− π x2/a2) Σ . (2.62)

◦ • =

dx = a→ 0 dx a

54 2 Image Representation

Of course, the derivation of the δ distribution exists—as all properties of distributions—only in the sense as a limit of a sequence of functions as shown in the preceding equation.

With the knowledge of derivative and shift operators being convolu- tion operators, we can use the properties summarized in Eq. (2.59) to draw some important conclusions. As any convolution operator com- mutes with the shift operator, convolution is a shift-invariant operation. Furthermore, we can ﬁ rst diﬀ erentiate a signal and then perform a con- volution operation or vice versa and obtain the same result. The proper- ties in Eq. (2.59) are essential for an eﬀ ective computation of convolution operations.

∝ −

Central-limit theorem. The central-limit theorem is mostly known for its importance in the theory of probability [134]. However, it also plays an important role for signal processing as it is a rigorous statement of the tendency that cascaded convolution tends to approach Gaussian form ( exp( ax2)). Because the Fourier transform of the Gaussian is also a Gaussian ( R6), this means that both the Fourier transform (the transfer function) and the mask of a convolution approach Gaussian shape.

Thus the central-limit theorem is central to the unique role of the Gaussian function for signal processing. The suﬃ cient conditions under which the central-limit theorem is valid can be formulated in diﬀ erent ways. We use here the conditions from [134] and express the theorem with respect to convolution.

Theorem 6 (Central-limit theorem) Given N functions h_n(x) with a zero

− ∞

mean, ∞ xh_n(x)dx and the variance σ 2 =, ∞ x2h_n(x)dx with z =

x/σ , σ 2 =, n=1 σ 2 then

N→ ∞

h = lim h₁ ∗ h₂ ∗ ... ∗ h_N ∝ exp(− z2/2) (2.63)

provided that

lim

N→ ∞ n

. σ 2 → ∞ (2.64)

and there exists a number α > 2 and a ﬁ nite constant c such that

∞

∫ xα h_n(x)dx < c < ∞ ∀ n. (2.65)

− ∞

The theorem is of great practical importance because — especially if h is smooth — the Gaussian shape is approximated suﬃ ciently accurately for values of N as low as 5.

2.3 Wave Number Space and Fourier Transform 55

| |

| | | | =

Smoothness and compactness. The smoother a function is, the more compact is its Fourier transform. This general rule can be formulated more quantitatively if we express the smoothness by the number of derivatives that are continuous and the compactness by the asymptotic behavior for large values of k. Then we can state: If a function g(x) and its ﬁ rst n− 1 derivatives are continuous, its Fourier transform decreases at least as rapidly as k ^{− (n}⁺¹⁾ for large k, that is, lim_|k_{|→ ∞} k ng(k) 0. As simple examples we can take the box and triangle functions (see next section). The box function is discontinuous (n 0), its Fourier transform, the sinc function, decays with k − 1. In contrast, the triangle function is continuous, but its ﬁ rst derivative is discontinuous. There- fore, its Fourier transform, the sinc² function, decays steeper with k − 2. In order to include also impulsive functions (δ distributions) in this re- lation, we note that the derivative of a discontinuous function becomes impulsive. Therefore, we can state: If the nth derivative of a function becomes impulsive, the function’s Fourier transform decays with k − n.

The relation between smoothness and compactness is an extension of reciprocity between the spatial and Fourier domain. What is strongly localized in one domain is widely extended in the other and vice versa.

∞

Uncertainty relation. This general law of reciprocity ﬁ nds another quan- titative expression in the classical uncertainty relation or the bandwidth- duration product. This theorem relates the mean square width of a func- tion and its Fourier transform. The mean square width (∆ x)2 is deﬁ ned as

−

∫ x2 .g(x).2  ∫ ∞ x.g(x).2 

2 ∞  ∞ . 

(∆ x)

= − ∞

− ∞ . (2.66)

 

∫ .g(x).  ∫ .g(x). 





− ∞ .

. − ∞ . .

. .

It is essentially the variance of g(x) , a measure of the width of the distribution of the “energy” of the signal. The uncertainty relation states:

Theorem 7 (Uncertainty relation) The product of the variance of

2 2

. . . .

g(x), (∆ x)2, and of the variance of gˆ (k) , (∆ k)2, cannot be smaller than 1/4π:

∆ x∆ k ≥ 1/(4π ). (2.67)

The relations between compactness and smoothness and the uncer- tainty relation give some basic guidance for the design of linear ﬁ lter (convolution) operators.

56 2 Image Representation

A b

r a e ija

phase phase

r b e ijb

amplitude amplitude

r eⁱ^jb

C d

r b eⁱ^ja

Figure 2.16: Illustration of the importance of phase and amplitude in Fourier space for the image content: a, b two original images; c composite image using the phase from image b and the amplitude from image a; d composite image using the phase from image a and the amplitude from image b.

Phase and Amplitude

As outlined above, the DFT can be regarded as a coordinate transfor- mation in a ﬁ nite-dimensional vector space. Therefore, the image infor- mation is completely conserved. The inverse transform results in the original image again.

In Fourier space, we observe the image from another “point of view”. Each point in the Fourier domain contains two pieces of information: the amplitude and the phase, i. e., relative position, of a periodic structure. Given this composition, we ask whether the phase or the amplitude con- tains the more signiﬁ cant information on the structure in the image, or whether both are of equal importance.

2.3 Wave Number Space and Fourier Transform 57

In order to answer this question, we perform a simple experiment. Figure 2.16a, b shows two images. One shows Heidelberg University buildings, the other several lines of printed text. Both images are Fourier transformed and then the phase and amplitude are interchanged as il- lustrated in Fig. 2.16c, d. The result of this interchange is surprising. It is the phase that determines the content of an image for both images. Both images look patchy but the signiﬁ cant information is preserved.

From this experiment, we can conclude that the phase of the Fourier transform carries essential information about the image structure. The amplitude alone implies only that such a periodic structure is contained in the image but not where. We can also illustrate this important fact with the shift theorem (Theorem 3, p. 52 and R7). A shift of an object in the space domain leads to a shift of the phase in the wave number domain only. The amplitude is not changed. If we do not know the phase of its Fourier components, we know neither what the object looks like nor where it is located.

It becomes obvious also that the power spectrum, i. e., the squared amplitude of the Fourier components (see also Section 3.5.3), contains only very little information, since all the phase information is lost. If a gray value can be associated with the amplitude of a physical process, say a harmonic oscillation, then the power spectrum gives the distribution of the energy in the wave number domain.

2.3.7 Practical Application of the DFT‡

Units. For a practical application of the DFT, it is important to consider the various factors that can be used in the deﬁ nition of the DFT and to give them a clear meaning. Besides the deﬁ nition in Eq. (2.29) two others are commonly used:

gˆ _v = √ N . w⁻^nv g_n ◦ • g_n = √ N . w^nv gˆ _v (a)

1 N− 1 1 N− 1

n=0

1 N− 1

n=0 N− 1

gˆ _v = N . w⁻^nv g_n ◦ • g_n = . w^nv gˆ _v (b)

(2.68)

gˆ _v = . w⁻^nv g_n ◦ • g_n = N . w^nv gˆ _v (c)

n=0 N− 1

n=0

1 N− 1

n=0

Mathematically spoken, the symmetric deﬁ nition (a) is the most elegant because it uses in both directions the scalar product with the orthonormal base vectors in Eqs. (2.28) and (2.29). In practice, deﬁ nition (b) is used most often, because gˆ ₀ gives the mean value of the vector in the spatial domain, independent of its length:

1 N− 1 1 N− 1

gˆ ₀ = N . w⁻ⁿ⁰ g_n = N . g_n. (2.69)

n=0 n=0

Therefore we will use deﬁ nition (b) almost everywhere in this book.

58 2 Image Representation

In practice it is important to know which spatial or temporal intervals have been used to sample the discrete signals. Only then it is possible to compare DFTs correctly that have been sampled with diﬀ erent intervals. The relation can be seen most easily if we approximate the Fourier integral in Eq. (2.18) by a sum and sample the values in the spatial and temporal domain using x = n∆ x, k = v∆ k und ∆ x∆ k = 1/N:

∞

gˆ (v∆ k) =

≈

∫ g(x) exp (− 2π iv∆ kx) dx

− ∞

− 1

g_n exp (− 2π inv∆ x∆ k) ∆ x

= N∆ x 1 . g_n exp.− 2 π i nv Σ = N∆ xgˆ _v.

n=0

(2.70)

N n=0 N

These equations state that the Fourier transform g_v computed with the DFT must be multiplied by the factor N∆ x 1/∆ k in order to relate it to a unit interval of the wave number. Without this scaling, the Fourier transform is related to the interval ∆ k 1/(N∆ x) and thus diﬀ ers for signals sampled with diﬀ erent rates.

For 2-Dand higher-dimensional signals corresponding relations are valid:

∆ k ∆ k₁ ₂

gˆ (v∆ k₁, u∆ k₂) ≈ N∆ xM∆ ygˆ _uv = 1 gˆ _uv. (2.71)

∞

The same scaling must be applied to the squared signals (energy) and not the squared factors from Eq. (2.70). This result follows from the Rayleigh theorem for continuous and discrete signals (± R4, ± R7):

Continuous:

∫ .g(x).2 dx = ∫

N− 1

∞

.gˆ (k).2 dk, ≈ . .gˆ (v∆ k).2 ∆ k

− ∞ . .

1 N− 1

− ∞ . .

N− 1

v=0.

. (2.72)

Discrete:

. .gn.₂ = . .gˆ v .₂.

N n=0. . v=0. .

The Rayleigh theorem says that the signal energy can either be integrated in the

ˆ 2

spatial or the Fourier domain. For discrete Signals this means that the average energy is either given by averaging the squared signal in the spatial domain or by summing up the squared magnitude of the signal in the Fourier domain (if we use deﬁ nition (b) of the DFT in Eq. (2.68)). From the approximation of the integral over the squared magnitude in the Fourier domain by a sum in

. .

Eq. (2.72), we can conclude that gˆ (v∆ k) ² ≈ .g_v. /∆ k. The units of the thus

scaled squared magnitudes in the Fourier space are ·/m− 1 or ·/Hz for time series, where · stands for the units of the squared signal.

Dynamic Range. While in most cases it is suﬃ cient to represent an image with 256 quantization levels, i. e., one byte per pixel, the Fourier transform of an image needs a much larger dynamical range. Typically, we observe a strong decrease of the Fourier components with the magnitude of the wave

2.3 Wave Number Space and Fourier Transform 59

A b

Figure 2.17: Partition of the Fourier domain into a Cartesian and b logarithmic- polar intervals.

number (Fig. 2.15). Consequently, at least 16-bit integers or 32-bit ﬂ oating-point numbers are necessary to represent an image in the Fourier domain without signiﬁ cant rounding errors.

The reason for this behavior is not the insigniﬁ cance of high wave numbers in images. If we simply omit them, we blur the image. The decrease is caused by the fact that the relative resolution is increasing. It is natural to think of relative resolutions, because we are better able to distinguish relative distance diﬀ erences than absolute ones. We can, for example, easily see the diﬀ erence of 10 cm in 1 m, but not in 1 km. If we apply this concept to the Fourier domain, it seems to be more natural to represent the images in a so-called log-polar coordi- nate system as illustrated in Fig. 2.17. A discrete grid in this coordinate system separates the space into angular and lnk intervals. Thus the cell area is propor- tional to k2. To account for this increase of the area, the Fourier components need to be multiplied by k2 in this representation:

∞ ∞

∫ |gˆ ( k )|2dk₁dk₂ = ∫ k2|gˆ ( k )|2d ln kdϕ. (2.73)

− ∞ − ∞

| |

If we assume that the power spectrum gˆ ( k ) 2 is ﬂ at in the natural log-polar coordinate system, it will decrease with k− 2 in Cartesian coordinates.

For a display of power spectra, it is common to take the logarithm of the gray values in order to compress the high dynamic range. The discussion of log-polar coordinate systems suggests that multiplication by k2 is a valuable alternative. Likewise, representation in a log-polar coordinate system allows a much better evaluation of the directions of the spatial structures and the smaller scales (Fig. 2.18).

60 2 Image Representation

| |

Figure 2.18: Representation of the Fourier transformed image in Fig. 2.7 in a Cartesian and b logarithmic polar coordinates. Shown is the power spectrum Gˆ uv 2) multiplied by k2. The gray scale is logarithmic and covers 6 decades (see also Fig. 2.15).

2.4 Discrete Unitary Transforms‡

2.4.1 General Properties‡

In Sections 2.3.1 and 2.3.2, we learnt that the discrete Fourier transform can be regarded as a linear transformation in a vector space. Thus it is only an example of a large class of transformations, called unitary transforms. In this section, we discuss some of their general features which will be of help for a deeper insight into image processing. Furthermore, we give examples of other unitary transforms which have gained importance in digital image processing.

Unitary transforms are deﬁ ned for vector spaces over the ﬁ eld of complex num- bers, for which an inner product is deﬁ ned. Both the FT Eq. (2.22) and DFT Eq. (2.29) basically compute scalar products.

The basic theorem about unitary transform states:

Theorem 8 (Unitary transform) Let V be a ﬁ nite-dimensional inner product vec- tor space. Let U be a one-one linear transformation of V onto itself. Then the following are equivalent:

. .. .

U is unitary.

2. U preserves the inner product, i. e., g | h = Ug | Uh , ∀ g, h ∈ V.

3. The inverse of U , U − 1, is the adjoin of U : UU ∗ T = I.

4. The row vectors (and column vectors) of U form an orthonormal basis of the vector space V.

2.4 Discrete Unitary Transforms‡ 61

In this theorem, the most important properties of a unitary transform are al- ready related to each other: a unitary transform preserves the inner product. This implies that another important property, the norm, is also preserved:

1/2

⊗ g ⊗ ₂ =. g . g . =. U g . U g . . (2.74)

It is appropriate to think of the norm as the length or magnitude of the vector. Rotation in R2 or R3 is an example of a transform where the preservation of the length of the vectors is obvious (compare also the discussion of homogeneous coordinates in Section 7.3.3).

The product of two unitary transforms, U ₁ U ₂, is unitary. As the identity op- erator I is unitary, as is the inverse of a unitary operator, the set of all unitary transforms on an inner product space is a group under the operation of com- position. In practice, this means that we can compose/decompose complex unitary transforms from/into simpler or elementary transforms.

We will illustrate some of the properties of unitary transforms discussed with the discrete Fourier transform. First we consider the one-dimensional DFT Eq. (2.29):

1 N− 1

g ˆ = √ N . g_nw⁻^nv.

n=0

This equation can be regarded as a multiplication of the N × N matrix W _N

( W N)nv = w− nv

with the vector g:

g ˆ = √ N W _N g. (2.75)

Explicitly, the DFT for an 8-dimensional vector is given by

0   ₈

 gˆ 0 

 w

0 0 0

8 8 8

 8

6 8

4 8

2 8

0 8

6 8

0 7 6

0 0 0

8 8 8

5 4 3

0 0 g0

4 8

2 8

8 8

 



2 1

 gˆ 1 

 w8 w8 w8 w8 w8 w8 w8 w8

  g1 

 





gˆ ₃ 

1 w⁰

5 2 7

8 w6

8 w1

8 8 8

4 1 6

8 w4

8 w7

8 w2

8 8 8

8   g3 

 gˆ



 gˆ ₄

 = 8  w0 w4

w0 w4

  g4 



8 w0

8 w3

 ₅ 

 8 8 8

8 8 8

8 8   ₅ 

8 w5

gˆ ₆

 

  w



gˆ ₇ 

0 2 4

8 8 8

0 1 2

8 8 8

6 0 2

8 8 8

3 4 5

8 8 8

8 8     g₆  

g₇

  g



We made use of the periodicity of the kernel of the DFT Eq. (2.43) to limit the exponents of W between 0 and 7. The transformation matrix for the DFT is symmetric ( W = W T ); W T ∗ is the back transformation.

× ×

For the two-dimensional DFT, we can write similar equations if we map the M N matrix onto an MN-dimensional vector. There is a simpler way, however, if we make use of the separability of the kernel of the DFT as expressed in Eq. (2.37). Using the M M matrix W _M and the N N matrix W _N analogously to the one-dimensional case, we can write Eq. (2.75) as

1 M− 1N− 1

gˆ _uv = √ MN g_mn( W _M)_mu( W _N)_nv, (2.76)

m=0n=0

62 2 Image Representation

A b c

0 0 0

1 1 1

4 4

5 5

Figure 2.19: Base functions of one-dimensional unitary transforms for N 8: a

cosine transform, b sine transform, and c Hartley transform.

or, in matrix notation,

G ˆ = √ MN

W M T

G W _N = √ MN

W _M GW _N. (2.77)

M˛ × ¸ Nr M˛ × ¸ Mr M˛ × ¸ Nr N ˛ × ¸ Nr

Physicists will be reminded of the theoretical foundations of quantum mechan- ics which are formulated in an inner product vector space of inﬁ nite dimension, the Hilbert space. In digital image processing, the diﬃ culties associated with inﬁ nite-dimensional vector spaces can be avoided.

After discussing the general features, some illustrative examples of unitary transforms will be given. However, none of these transforms is as important as the Fourier transform in signal and image processing.

2.4.2 Cosine, Sine, and Hartley Transforms‡

It is often inconvenient that the discrete Fourier transform maps real-valued to complex-valued images. We can derive a real transformation if we decompose the complex DFT into its real and imaginary parts:

( W _N)_nv = cos.− 2 π n v Σ + i sin.− 2 π n v Σ . (2.78)

Neither the cosine nor the sine part is useful as a transformation kernel, since these functions do not form a complete basis of the vector space. The cosine and sine functions only span the subspaces of the even and odd functions, respectively.

This problem can be solved by limiting the cosine transform and the sine trans- form to the positive half space in the spatial and Fourier domains. Then sym-

2.4 Discrete Unitary Transforms‡ 63

metry properties play no role and the two transforms are deﬁ ned as

∞ ∞

c gˆ (k) = ∫ g(x)√ 2 cos(2π kx)dx ◦ • g(x) = ∫ c gˆ (k)√ 2 cos(2π kx)dk

0 0

∞ ∞

s gˆ (k) = ∫ g(x)√ 2 sin(2π kx)dx ◦ • g(x) = ∫ s gˆ (k)√ 2 sin(2π kx)dk.

0 0

(2.79)

For the corresponding discrete transforms, base vectors with the missing sym- metry can be generated by adding trigonometric functions with half-integer wavelengths. This is equivalent to doubling the base wavelength. Consequently, the kernels for the cosine and sine transforms in an N-dimensional vector space are

c_nv =, 2 cos. π nv Σ , s_nv =, 2 sin. π (n + 1)(v + 1) Σ . (2.80)

N N N + 1 N + 1

Figure 2.19a, b shows the base functions of the 1-D cosine and sine functions. From the graphs, it is easy to imagine that all the base functions are orthogonal to each other. Because of the doubling of the periods, both transforms now con- tain even and odd functions. The base functions with half-integer wavelengths ﬁ ll in the functions with the originally missing symmetry.

The cosine transform has gained importance for image data compression [86]. It is included in the standard compression algorithm proposed by the Joint Photographic Experts Group (JPEG).

The Hartley transform (HT ) is a much more elegant solution than the cosine and sine transforms for a transform that avoids complex numbers. By adding the cosine and sine function, we yield an asymmetrical kernel

cas 2π kx = cos(2π kx) + sin(2π kx) = √ 2 cos(2π (kx − 1/8)) (2.81) that is suitable for a transform over the whole space domain:

∞ ∞

hgˆ (k) = ∫ g(x) cas(2π kx)dx ◦ • g(x) = ∫ hgˆ (k) cas(2π kx)dk. (2.82)

− ∞ − ∞

The corresponding discrete Hartley transform (DHT ) is deﬁ ned as:

1 N− 1 1 N− 1

hgˆ _v = √ N . g_n cas(2π nv/N) ◦ • g_n = √ N . hgˆ _v cas(2π nv/N). (2.83)

n=0 n=0

The base vectors for N 8 are shown in Fig. 2.19c. Despite all elegance of the Hartley transform for real-valued signals, it shows a number of disadvantages in comparison to the Fourier transform. Especially the simple shift theorem 3 of the Fourier trasnform is no longer valid. A shift rather causes base functions with positive and negative wave numbers to be combined with each other:

g(x − x₀) ◦ • hgˆ (k) cos(2π kx₀) + hgˆ (− k) sin(2π kx₀) g_n₋_n' ◦ • hgˆ _v cos(2π n'v/N) + hgˆ _N₋_v sin(2π n'v/N)

. (2.84)

Similar complications arise with the convolution theorem for the Hartley trans- form (± R8).

64 2 Image Representation

A b

0 0

1 1

2 2

3 3

4 4

5 5

6 6

7 7

Figure 2.20: First 8 base functions of one-dimensional unitary transforms for

N = 16: a Hadamard transform and b Haar transform.

2.4.3 Hadamard Transform‡

The base functions of the Hadamard transform are orthogonal binary patterns (Fig. 2.20a). Some of these patterns are regular rectangular waves, others are not. The Hadamard transform is computationally eﬃ cient, because its kernel contains only the ﬁ gures 1 and –1. Thus only additions and subtractions are necessary to compute the transform.

2.4.4 Haar Transform‡

The base vectors of all the transforms considered so far are characterized by the fact that the base functions spread out over the whole vector or image. In this sense we denote these transforms as global. All locality is lost. If we have, for example, two independent objects in our image, then they will be simultaneously decomposed into these global patterns and will no longer be recognizable as two individual objects in the transform.

The Haar transform is an example of a unitary transform which partly pre- serves local information, since its base functions are pairs of impulses which are non-zero only at the position of the impulse (Fig. 2.20a). With the Haar transform the position resolution is better for smaller structures. As with the Hadamard transform, the Haar transform is computational eﬃ cient. Its kernel only includes the ﬁ gures − 1, 0, and 1.

2.5 Fast Algorithms for Unitary Transforms 65

⇐ Предыдущая 8 9 10 11 121314 15 16 17 Следующая ⇒

Последнее изменение этой страницы: 2019-05-04; Просмотров: 241; Нарушение авторского права страницы