# PRELIMINARIES 2.1 FUNDAMENTALS 21

Download 2.54 Mb.
 Page 4/30 Date 18.10.2016 Size 2.54 Mb.
 20 PRELIMINARIES 2.1 FUNDAMENTALS 21 In visual data, that same transition corresponds to the spectrum between blurred imagery and images rich in visual detail. Note that high frequencies refer to wild intensity excur- sions. This tends to correspond to visual detail like edges and texture in high contrast images. High frequencies that are subjectively determined to add nothing to the informa- tion content of the signal are usually referred to as noise. Since blurred images have slowly varying intensity functions, they lack significant high frequency information. In either case, music and images are time- and spatially-varying functions whose informa- tion content is embedded in their frequency spectrum. The conversion between the spa- tial and frequency domains is achieved by means of the Fourier transform. We are familiar with other instances in which mathematical transforms are used to simplify a solution to a problem. The logarithm is one instance of such a transform. It simplifies problems requiring products and quotients by substituting addition for multi- plication and subtraction for division. The only tradeoff is the accuracy and time neces- sary to convert the operands into logarithms and then back again. Similar benefits and drawbacks apply to the Fourier transform, a method introduced by the French physicist Joseph Fourier nearly two centuries ago. He derived the method to transform signals between the spatial (or time) domain and the frequency domain. As we shall see later, using two representations for a signal is useful because some operations that are difficult to execute in one domain are relatively easy to do in the other domain. In this manner, the benefits of beth representations are exploited. 2.1.5.2. Fourier Transforms Fourier transforms are central to the study of signal processing. They offer a powerful set of analytical tools to analyze and proc\$ss singi a0d multidimensional sig- napd_syse_ms: The great impact thakEom'ier_tra snsfformsha_s_ha_d on sgnal proih is dug:, in large part, to the fundamental understandiog ginned by exarmmng a sgnalTTom  entirely different viewpoint7 We had earlier considered an arbitrary input function f (x) to be the sum of an infinite number of impulses, each scaled and shiftdi'sish[ 'in  gr]lap ofitriagihfi- ti /ou'i'scovered that an alternfi- u-n'lpo-sible: f (x)earr be tafffi the sum of'hn 'ififihit'hurlr. o 'mus0idai x.' "f'hi 'rivvi(Jnt ]S'jSfiflable bce ie 'eln}e o/5-ax linear, spae-invariant system to a complex exponential (sinusoid) is another cmpllOx exponential of the same frequency but altered amplitude and phase. DeLe`minrgtheptde-sand-phase-iftsfr`upd-`!s ).e.central topic of F'ier analgi_S,.. Conversely, the act of adding these scaled and shi8'-- FtiaOiSqOdih-df'i':own a Fourier synthesis. Fourier analS,i and yfithesi'e made possible by the Fourier transform pair: where i =',/21-, and F(u) = f f (x)e-i2WC dx (2.1.13) f (x) = i F(u)e+ianUX du (2.1.14) e i2nux = cos2gux _+ isin2gux (2.1.15) is a succinct expression for a complex exponential at frequency u. The definition of the Fourier transform, given in Eq. (2.1.13), is valid for any integrable function f (x). It decomposes f (x) into a sum of complex exponentials. The complex function F (u) specifies, for each frequency u, the amplitude and phase of each complex exponential. F(u) is commonly known as the signal's frequency spectrum. This should not be confused with the Fourier transform of a filter, which is called the fre- quency response (for 1-D filters) or the modulation transfer function (for 2-D filters). The frequency response of a filter is computed as the Fourier transform of its impulse response. It is important to realize that f (x) and F (u) are two different representations of the same function. In particular, f(x) is the signal in the spatial domain and F(u) is its counterpart in the frequency domain. One goes back and forth between these two representations by means of the Fourier transform pair. The transformation from the fre- quency domain back to the spatial domain is given by the inverse Fourier transform, defined in Eq. (2.1.14). Although f (x) may be any complex signal, we are generally interested in real func- tions, i.e., standard color images. The Fourier transform of a real function is usually complex. This is actually a clever encoding of the orthogonal basis set, which consists of sine and cosine functions. Together, they specify the amplitude and phase of each fre- quency component, i.e., a sine wave. Thus, we have F(u) defined as a complex function of the form R (u) + i! (u), where R (u) and 1 (u) are the real and imaginary components, respectively. The amplitude, or magnitude, of F (u) is defined as [F (u) l = 5]R2(u) + 12(u) (2.1.16) It is often referred to as the Fourier spectrum. This should not be mistaken with the Fourier transform F(u), which is itself commonly known as the spectrum. In order to avoid confusion, we shall refer to [F(u) l as the magnitude spectrum. The phase spec- trum is given as [I(u) ] (2.1.17) ½(u) = tan -1 [ R'J This specifies the phase shift, or phase angle, for the complex exponential at each fre- quency u. PRELIMINARIES'>22 PRELIMINARIES The Fourier transform of a signal is often plotted as magnitude versus frequency, ignoring phase angle. This form of display has become conventional because the bulk of the information relayed about a signal is embedded in its frequency content, as given by the magnitude spectrum IF (u)[. For example, Figs. 2.5a and 2.5b show a square wave and its spectrum, respectively. In this example, it just so happens that the phase function (u) is zero for all u, with the spectrum being defined in terms of the following infinite 1  1 . 1 _ F(u) = cosu - cos.u + -cos u - cosu + ... (2.1.18) 1 1 sin7u+ '" = sinu + -sin3u + sin5u + Consequently, the spectrum is real and we display its values directly. Note that both positive and negative frequencies are displayed, and the amplitudes have been halved accordingly. An application of Fourier synthesis is shown in Fig. 2.5c, where the first five nonzero components ofF(u) are added together. With each additional component, the reconst'ucted function increasingly takes on the appearance of the original square wave. The ripples that persist are a consequence of the oscillatory behavior of the sinusoidal basis functions. They remain in the reconstruction unless all frequency com- ponents are considered in the reconstruction. This artifact is known as Gibbs phenomenon which predicts an overshoot/undershoot of about 22% near edges that are not fully reconstructed [Antoniou 79]. A second example is given in Fig. 2.6. There, an arbitrary waveform undergoes Fourier analysis and synthesis. In this case, F(u) is complex and so only the magnitude spectrum IF(u) l is shown in Fig. 2.6b. Since the spectrum is defined over infinite fre- quencies, only a small segment of it is shown in the figure. The results of Fourier syn- thesis with the first ten frequency components are shown in Fig. 2.6c. As before, incor- porating the higher frequency components adds finer detail to the reconstructed function. The two examples given above highlight an important property of Fourier transforms that relate to periodic and aperiodic functions. Periodic signals, such as the square wave shown in Fig. 2.5a, can be represented as the sum of phase-shifted sine waves whose frequencies are integral multiples of the signal's lowest nonzero frequency component. In other ._..,r_d a periodic signal contains all the frequencies that are har- monics of the fundamental frequency. We normally associate the analysis of periodic signals with Fourier series rather than Fourier transforms. The Fourier series can be expressed as the following summation f (x) = a c(nuo)ei2nux (2.1.19) where c (nuo) is the nth Fourier coefficient c(nuo) = f f (x)e-i2nnuX dx (2.1.20) 2.1 FUNDAMENTALS f (x) F (u) (a) (b) sin(x) sin(3x) sin(5x) sin(7x) (c) Figure 2.5: Fourier transform. (a) square wave; (b) spectrum; (c) partial sums. 23 and u 0 is the fundamental frequency. Note that since f (x) is periodic, the integral in Eq. (2.1.20) that is used to compute the Fourier coefficients must only integrate over period X0. Aperiodic signals do not enjoy the same compact representation as their periodic counterparts. Whereas a periodic signal is expressed in terms of a sum of frequency components that are integer multiples of some fundamental frequency, an aperiodic sig- nal must necessarily be represented as an integral over a continuum of frequencies, as in Eq. (2.1.13). This is reflected in the spectra of Figs. 2.5b and Fig. 2.6b. Notice that the square wave spectrum consists of a discrete set of impulses in the frequency domain, while the spectrum of the aperiodic signal in Fig. 2.6 is defined over all frequencies. For this reason, we distinguish Eq. (2.1.13) as the Fourier integral. It can be shown that the Fourier series is a special case of the Fourier integral. In summary, periodic signals have discrete Fourier components and are described by a Fourier series. Aperiodic signals 24 PRELIMINARIES f (x) IF(u)[ (a) (b) VII  VIII .5 L5 2 (c) Figure 2.6: Fourier transform. (a) aperiodic signal; (b) spectrum; (c) partial sums. .5n 1.5n 2g 2.1 FUNDAMENTALS 2 have continuously varying Fourier components and are described by a Fourier integral. There am several other symmetries that apply between the spatial and frequency domains. Table 2.2 lists just a few of them. They refer to functions being real, ima- ginary, even, and odd. A function is real ifJhe imaginary component is set to zero. Simlariy, a function is imaginary if its real component is zero. A function f (x) is even iff(-x):f(x). Iff(-x)=-f(x), then f(x) is said to be an odd function. Finally, F*(u) refers to the complex conjugate of F(u). That is, if F(u)=R(u)+il(u), then F* (u)=R(u)-il(u). Spatial Domain, f (x) Real Imaginary Even Odd Real and Even Real and Odd Imaginary and Even Imaginary and Odd Periodic Periodic Sampling Frequency Domain, F (u) F(-u) =F*(u) F(-u) = -F*(u) Even Odd Real and Even Imaginary and Odd Imaginary and Even Real and Odd Discrete Periodic Copies Table 2.2: Symmetries between the spatial and frequency domains. The last two symmetries listed above are particularly notable. By means of the Fourier series, we have already seen periodic signals produce discrete Fourier spectra (Fig. 2.5). We shall see later that periodic spectra correspond to sampled signals in the spatial domain. The significance of this symmetry will become apparent when we dis- cuss discrete Fourier transforms and sampling theory. In addition to the symmetries given above, there are many properties that apply to the Fourier transform. Some of them are listed in Table 2.3. Among the most important of these properties is linearity because it reflects the applicability of the Fourier transform to linear system analysis. Spatial scaling is of significance, particularly in the context of simple warps that consist only of scale changes. This property establishes a reciprocal relationship between the spatial domain and the frequency domain. Therefore, expansion (compression) in the spatial domain corresponds to compression (expansion) in the fre- quency domain. Furthermore, the frequency scale not only contracts (expands), but the amplitude increases (decreases) vertically in such a way as to keep the area constant. Finally, the property that establishes a correspondence between convolution in one domain and multiplication in the other is of gmat practical significance. The proofs of these properties are left as an exercise for the reader. A detailed exposition can be found in [Bracewell 86], [Brigham 88], and most signal processing textbooks. 26 PRELIMINARIES Property Lineafity Spatial Scaling Frequency Scaling Spatial Shifting Frequency Shifting (Modulation) Convolution Multiplication Spatial Domain, f (x) (Zlf 1 (X)+Ov2f:(x) f(ax) f (x-a) f (x)e 12r. ox g(x)=f (x)* h(x) g(x)=f (x)h(x) Frequency Domain, F (u) oqFl(u)+o2F2(u) al-F() F(au) F (u) e -i2,,,, F(u-a) G (u) = F (u) H (u) G (u) = F (u) * H (u) Table 2.3: Fourier transform properties. The Fourier transform can be easily extended to multidimensional signals and sys- tems. For 2-D images f (x,y) that are integrable, the following Fourier transform pair exists: F(u,v) : f f f (x,y)e-i2n(ta+vY' dxdy (2.1.21) f(x,y) = f f V(u,v)e+i2(m+Y) dudv (2.1.22) where u and v are frequency vaxiables. Extensions to higher dimensions are possible by simply adding exponent terms to the complex exponential, and integrating over the addi- tional space and frequency vaxiables. 2.1.5.3. Discrete Fourier Transforms The discussion thus far has focused on continuous signals. In practice, we deal with discrete images that are both limited i_n._extent _and sampl a_[is9rete points. The results d'evetoped-sfrstee mdified to beeful in this domain. We thus come to define the discrete Fourier tradofln pair: F (u ) = ' x=O f '.x ) e  2ux/l (2.1.23) f (x) =  F (u)e 12r"xl (2.1.24) u=0 for 0 \$ u,x < N -1, where N is the number of input samples. The 11N factor that appears in front of the forward transform serves to normalize the spectrum with respect to the length of the input. There is no strict rule which requires the normalization to be applied to F(u). In some sources, the lIN factor appears in front of the inverse transform instead. For reasons of symmetry, other common formulations have the forward and 2.1 FUNDAMENTAL 27 inverse transforms each scaled by 1/,f. As long as a cumulative I/N factor is applied somewhere along the transform pair, the final results will be properly normalized. The discrete Fourier transform (DFT), defined in Eq. (2.1.23), assumes thatf (x) is an input array consisting of N regularly spaced samples. It maps these N complex numbers into F(u), another set of N complex numbers. Since the frequency domain is now discrete, the DFT must treat the input as a periodic signal (from Table 2.2). As a result, we have let the limits of summation change from (-N/2, N/2) to (0, N-l), bearing in mind that the negative frequencies now occupy positions N/2 to N-1. Although nega- tive frequencies have no physical meaning, they are a byproduct of the mathematics in this process. It is noteworthy to observe, though, that the largest reproducible frequency for an N-sample input is N/2. This corresponds to a sequence of samples that alternate between black and white, in which the smallest period for each cycle is two pixels. The data in f (x) is treated as one period of a periodic signal by replicating itself indefinitely, thereby tiling the input plane with copies of itself. This makes the opposite ends of the signal adjacent by virtue of wraparound from f (N-i) to f (0). Note that this is only a model of the infinite input, given only the small (aperiodic) segment f (x), i.e., no physical replication is necessary. While this permits F(u) to be defined for discrete values of u, it does introduce artifacts. First, the transition across the wraparound border may be discontinuous in value or derivative(s). This has consequences in the high fre- quency components of F(u). One solution to this problem is windowing, in which the actual signal is multiplied by another function which smoothly tapers off at the borders (see Chapter 5). Another consideration is the value ofN. A small N produces a coarse approximation to the continuous Fourier transform. However, by choosing a sufficiently high sampling rate, a good approximation to the continuous Fourier transform is obtained for most signals. The i-D discrete Fourier transform pairs given in Eqs. (2.1.23) and (2.1.24) can be extended to higher dimensions by means of the separability property. For an NxM images, we have the following DFT pair: F(u,v) = -   f(x,y)e (2.1.25) f(x,y) =   F(u,v)e i2nOtx/N+vyM) (2.1.26) The DFT pair given above can be expressed in the separable forms 1 M-I N-I } f(x,y) =   F(u,v)e i2mtxlN e i2vylM (2.1.28) for u,x =0,1,...,N-I, and v,y =0,1,...,M-1. 28 PRELIMINARIE The principal advantage of this reformulation is that F (u,v) and f (x,y) can each be obtained by successive applications of the 1-D DFT or its inverse. By regrouping the operations above, it becomes possible to compute the xansforms in the following manner. First, transform each row independently, placing the results in intermediate image 1. Then, transform each column of/independently. This yields the correct results for either the forward or inverse transforms. In Chapter 7, we will show how separable algorithms of this kind have been used to greatly reduce the computational cost of digital image warping. Although the DFT is an important tool that is amenable for computer use, it does so at a high price. For an N-sample input, the computational cost of the DFT is O (N2). This accounts for N summations, each requiring N multiplication operations. Even with high-speed computers, the cost of such a transform can be overwhelming for large N. Consequently, the DFT is often generated with the fast Fourier transform (FFT), a com- putational algorithm that reduces the computing time to O (N log2N). The FFT achieves large speedups by exploiting the use of partial results that combine to produce the correct output. This increase in computing speed has completely revolutionized many facets of scientific analysis. A detailed description of the FFT algorithm, and its variants, are given in Appendix 1. In addition to this review, interested readers may also consult [Brigham 88] and [Ramirez 85] for further details. The development of the FFT algorithm has given impetus to filtering in the fre- quency domain. There are several advantages to this approach. The foremost benefit is that convolution in the spatial domain corresponds to multiplication in the frequency domain. As a result, when a convolution kernel is sufficiently large, it becomes more cost-effective to transform the image and the kemel into the frequency domain, multiply them, and then transform the product back into the spatial domain. A second benefit is that important questions relating to sampling, interpolation, and aliasing can be answered rigorously. These topics are addressed in subsequent chapters. 2.2. IMAGE ACQUISITION Before a digitaputer can begin to process an image, that image must first be available in digital 1hrm This is made possible by a digital image acquisition system, a device that scans the scene and generates an array of numbers representing the light intensities at a discrete set of points. Also known as a digitizer, this device serves as the front-end to any image processing system, as depicted in Fig. 2.7. Digital image acquistion systems consist of three basic components: an imaging sensor to measure light, scanning hardware to collect measurements across the entire scene, and an analog-to-digital converter to disaretize the continuous values into finite- precision numbers suitable for computer processing. The remainder of this chapter is devoted to describing these components. However, since a full description that does jus- tice to this topic falls outside the scope of this book, our discussion will be brief and incomplete. Readers can find this material in most image processing textbooks. Useful reviews can also be found in [Nagy 83] and [Schreiber 86]. 2.2 IMAGE ACQUISITION 29 Digitizer Input  n, Digital Scene I ....... ' ' I image ICom. puter I Figure 2.7: Elements of an image processing system. Consider the image acquisition system shown in Fig. 2.8. The entire imaging pro- cess can be viewed as a cascade of filters applied to the input image. The scene radiance f (x,y) is a continuous two-dimensional image. It passes through an imaging subsystem, which acts as the first stage of data acquisition. Section 2.3 describes the operation of several common imaging systems. Due to the point spread function of the image sensor, h (x,y), the output g (x,y) is a degraded version off (x,y). Scene r [ Subsytem Subsystem * h (x,y) * s (x,y) Quantizer ga(x,y) Digitiz Image Figure 2.8: Image acquisition system. By definition, g(x,y) = f (x,y) * h(x,y) (2.2.1) where * denotes convolution. If the PSF profile is identical in all orientations, the PSF is said to be rotationally-symmetric. Furthermore, if the PSF retains the same shape throughout the image, it is said to be spatially-invariant. Also, if the two-dimensional PSF can be decomposed into two one-dimensional filters, e.g., h (x,y) = hx(x,y) hy(x,y), it is said to be separable. In practice, though, point spread functions are usually not rotationally-symmetric, spatially-invaxiant, or separable. As a result, most imaging dev- ices induce geometric distortion in addition to blurring. 0 PRELIMINARIE The continuous image g (x,y) then enters a sampling subsystem, generating the discrete-continuous image gs(x,y). The sampled image gs(x,y) is given by gs(x,y) = g (x,y) s (x,y) (2.2.2) where s(x,y) =   5(x-m,y-n) (2.2.3) is the two-dimensional comb function, depicted in Fig. 2.9, and 5 (x,y) is the impulse Directory: filedownloadDownload 2.54 Mb.Share with your friends:

The database is protected by copyright ©ininet.org 2020
send message

Main page