2.2.1 Zero–One Functions

Let be a region in the ‐dimensional space, . We define the zero–one function as illustrated in Figure 2.3(a) by

(2.1)

Sometimes, is called the indicator function of the region . Different functions are obtained with different choices of the region . Such functions arise frequently in modeling sensor elements or display elements (sub‐pixels). The most commonly used ones in image processing are the rect and the circ functions in two dimensions. Specifically, for a unit‐square region we obtain (Figure 2.3(b))

(2.2)

For a circular region of unit radius we have (Figure 2.3(c))

(2.3)

These definitions can be extended to the three‐dimensional case (where the region is a cube or a sphere) or to higher dimensions in a straightforward fashion, and the single notation or can be used to cover all cases. We will see later how these basic signals can be shifted, scaled, rotated or otherwise transformed to generate a much richer set of zero–one functions. Other zero–one functions that we will encounter correspond to various polygonal regions such as triangles, hexagons, octagons, etc.

2.2.2 Sinusoidal Signals

As in one‐dimensional signals and systems, real and complex‐exponential sinusoidal signals play an important role in the analysis of image processing systems. There are several reasons for this but a principal one is that if a complex‐exponential sinusoidal signal is applied as input to a linear shift‐invariant system (to be introduced shortly), the output is equal to the input multiplied by a complex scalar. A general, real two‐dimensional sinusoid with spatial frequency is given by

(2.4)

where and are spatial coordinates in ph (say), and are fixed spatial frequencies in units of c/ph (cycles per picture height) and is the phase. In general, for a given unit of spatial distance (e.g., m), spatial frequencies are measured in units of cycles per said unit (e.g., c/m).

Figure 2.4 illustrates a sinusoidal signal with horizontal frequency 1.5 c/ph and vertical frequency 2.5 c/ph in a square image window of size 1 ph by 1 ph. The actual signal displayed is , which has a range from 0 (black) to 1 (white). From this figure, we can identify a number of features of the spatial sinusoidal signal. The sinusoidal signal is periodic in both the horizontal and vertical directions, with horizontal period and vertical period . The signal is constant if is constant, i.e. along lines parallel to the line .

The one‐dimensional signal along any line through the origin is a sinusoidal function of distance along the line. The maximum frequency along any such line is , along the line , as illustrated in Figure 2.4. The proof is left as an exercise.

As in one dimension, the complex exponential sinusoidal signals play an important role, e.g., in Fourier analysis. The complex exponential corresponding to the real sinusoid of Equation (2.4) is

(2.5)

where can be complex. In this book, we use j to denote . We often will adopt the vector notation

(2.6)

where in the two‐dimensional case denotes as before, denotes and denotes . When using the column matrix notation, then and we can write . This is extended to any number of dimensions in a straightforward manner. Using Euler's formula, the complex exponential can be written in terms of real sinusoidal signals

(2.7)

If is given as in Equation (2.6), then for any fixed , we have

(2.8)

In other words, the shifted complex exponential is equal to the original complex exponential multiplied by the complex constant . This in turn leads to the key property of linear shift‐invariant systems mentioned earlier in this section. This will be analyzed in Section 2.5.5 but is mentioned here to motivate the importance of sinusoidal signals in multidimensional signal processing.

2.2.3 Real Exponential Functions

Real exponential signals also have wide applicability in multidimensional signal processing. First‐order exponential signals are given by

(2.9)

and second‐order, or Gaussian, signals by

(2.10)

Gaussian signals, similar in form to the Gaussian probability density, are widely used in image processing. Some illustrations can be seen later, in Figure 2.6. We define the standard versions of these signals as follows:

(2.11)

(2.12)

2.2.4 Zone Plate

A very useful two‐dimensional function that is often used as a test pattern in imaging systems is the zone plate, or Fresnel zone plate. The sinusoidal zone plate is based on the function

(2.13)

where is a parameter that sets the scale. Figure 2.5 illustrates the zone plate with ph. It is often convenient to consider the zone plate as the real part of the complex exponential function .

Examining Figure 2.5, it can be seen that locally (say, within a small square window) the function is a sinusoidal signal with a horizontal frequency that increases with horizontal distance from the origin, and similarly a vertical frequency that increases with vertical distance from the origin. To make this concept of local frequency more precise, consider a conventional two‐dimensional sinusoidal signal

(2.14)

where . In this case we see that the horizontal and vertical frequencies are given by

We use these definitions to define the local frequency of a generalized sinusoidal signal . For the zone plate, we have and so obtain

(2.15)

(2.16)

which confirms that local horizontal and vertical frequencies vary linearly with horizontal and vertical position respectively.

We define standard versions of the real and complex zone plates by

(2.17)

(2.18)

There is also a binary version of the zone plate that is widely used:

(2.19)

2.2.5 Singularities

As in one‐dimensional signals and systems, singularities play an important role in multiD signal and system analysis. These singularities are not functions in the conventional sense; they can be described as functionals and are often referred to as generalized functions, rigorously treated using distribution theory. However, following common practice, we will nevertheless sometimes refer to them as functions (e.g., delta functions). We present here some basic properties of singularities suitable for our purposes. More details can be found in Papoulis (1968) and Barrett and Myers (2004). A more rigorous but relatively accessible development is given in Richards and Youn (1990), and a careful development of signal processing using distribution theory can be found in Gasquet and Witomski (1999).

The 1D Dirac delta, denoted , is characterized by the property that

(2.20)

for any function that is continuous at . In particular, taking , we have

(2.21)

The Dirac delta can be considered to be the limit of a sequence of narrow pulses of unit area, for example, or , as .

The 2D Dirac delta is defined in a similar fashion by the requirement

(2.22)

for any function that is continuous at . Again, the 2D Dirac delta can be considered to be the limiting case of sequences of narrow 2D pulses of unit volume, e.g.,

The 2D Dirac delta satisfies the scaling property

(2.23)

Other important properties of Dirac deltas will emerge as we investigate their role in multiD system analysis.

The Dirac delta can be extended to the multiD case in an obvious fashion, with the notation covering all cases. The conditions (2.20) and (2.22) are written

(2.24)

in the general case, where is understood to mean , or according to context. As a consequence of (2.23) in the general case,

(2.25)

In addition to the point singularities defined above, we can have singularities on lines or curves in two or three dimensions, or on surfaces in three dimensions. See Papoulis (1968) for a discussion of singularities on a curve in two dimensions.

2.2.6 Separable and Isotropic Functions

A two‐dimensional function is said to be separable if it can be expressed as the product of one‐dimensional functions,

(2.26)

Several of the 2D functions we have seen are separable, including , the complex exponential , and the exponential functions. Also, the 2D Dirac delta can be considered to be separable: . The extension to higher‐dimensional separable signals is evident,

(2.27)

Separability is a convenient way to generate multiD signals from 1D signals. Note that signals can also be separable in other variables than the standard orthogonal axes .

A 2D signal is said to be isotropic (circularly symmetric) if it is only a function of the distance from the origin,

(2.28)

Examples of isotropic signals that we have seen are , the Gaussian signal, and the zone plate. Again, the extension to multiD signals is evident: . We may also call such a signal rotation invariant, since it is invariant to a rotation of the domain about the origin.

2.5.1 Linear Systems

We first make the assumption that the signal space has the properties of a real or complex vector space. This ensures that elements of the signal space can be added together, and can be multiplied by a scalar constant, and that in each case the result also lies in the given signal space. This holds for most signal spaces of interest.

If and , then the sum is defined by for all . Similarly, , the multiplication by a scalar, is defined by for all . Given these conditions, a system is said to be linear if

(2.31)

(2.32)

for all , and for all (or for all for complex signal spaces). The definition of a linear system extends in an obvious fashion if and in Equation (2.30) are different vector spaces. The most basic example of a linear system is , which is easily seen to satisfy the definition. A system that does not satisfy the conditions of a linear system is said to be a nonlinear system. A simple and common example of a nonlinear system is given by .

Linear systems are of particular interest because if we know the response of the system to a number of basic signals , namely , then we can determine the response to any linear combination of the :

(2.33)

As a simple example of a linear system, consider the shift (or translation) operator for some fixed shift vector . If , then . For this operation to be well defined, the domain of the signal space must be all of . In two dimensions, we would have , and . It can easily be verified from the definitions that is a linear system. Figure 2.8 illustrates the shift operator with .

Another important class of linear systems consists of systems induced by an arbitrary nonsingular linear transformation of the domain for some . Let be such a transformation, where is a nonsingular matrix. The induced system is defined by

(2.34)

Again, it is easily verified from the definitions that is a linear system. We will mainly use this category of systems for scaling and rotating basic signals such as those of Section 2.2, but more general cases are widely used as well. If is a diagonal matrix, the transformation carries out a separate scaling along each of the axes, as illustrated in two dimensions in Figure 2.9(a). In this example, , which has the effect of magnifying the image by a factor of two in each dimension. In general, if , the system will scale the image by a factor of in the horizontal dimension and by in the vertical dimension.

If is a two‐dimensional rotation matrix,

the transformation rotates the signal in the clockwise direction, as illustrated in Figure 2.9(b). The rotation of the domain is given by

(2.35)

where explicitly

(2.36)

The rotation of the domain and the rotation of the signal are in opposite directions. Since this sometimes leads to confusion, we present a specific illustration. To demonstrate how acts on , consider the following four points, marked on Figure 2.10.

These points are mapped by to

These are marked on the right of Figure 2.10 for , where and . We see that this transformation has rotated points in counterclockwise by .

Now let us consider what happens when a two‐dimensional signal is mapped through the linear system given by Equation (2.34) for this transformation. Thus,

(2.37)

Thus, explicitly, . For example,

This is illustrated in Figure 2.11, which shows the effect of applying this linear system to a diamond‐shaped zero‐one function. From the figure, we see that the linear system has rotated the two‐dimensional signal clockwise by , which is the opposite direction to that in which has rotated the points of .

Another more general class of linear systems involves an affine transformation of the independent variables. One way to express this is

(2.38)

where is a nonsingular matrix. The affine transformation can be expressed as a cascade of the two preceding types of linear systems in two ways: . Generally the representation is more convenient. The signal is first rotated, scaled and perhaps sheared with respect to the origin, then centered at point . It can be shown that the cascade of any linear systems is also a linear system, and thus the system induced by an affine transformation of the domain is a linear system. As an example of an affine transformation, the Gaussian image of Figure 2.6 can be obtained from the unit variance, zero‐centered Gaussian using the affine transformation with

2.5.2 Linear Shift‐Invariant Systems

An important subclass of linear systems is the class of linear shift‐invariant (LSI) systems. In such a system, if the response to an input is , then if is shifted by any amount , the resulting output is equal to shifted by the same amount . Using the above terminology, if , then for any . For an LSI system , for any . We say that the two systems and commute. The shift system is itself an LSI system, since for any . However, the general affine transformation system is not an LSI system if , since but .

Another important class of LSI systems are those that involve partial derivatives of the input function with respect to the independent variables. As the simplest example, consider the 2D system defined by . Such systems are often connected in series or parallel, for example the system , where the output is given by

(2.39)

This system is known as the Laplacian. This and other derivative‐based systems are further discussed in Section 2.7. Note that the series and cascade connection of LSI systems is also an LSI system. The proof is left as an exercise.

2.5.3 Response of a Linear System

The defining property of the Dirac delta function is given in Equation (2.24): . From this, we can derive the so‐called sifting property

(2.40)

This follows from

The sifting property (2.40) can be interpreted as the synthesis of the signal by the superposition of shifted Dirac delta functions with weights :

(2.41)

For a linear system , we can conclude that

(2.42)

where is the response of the system to a Dirac delta function located at position s. If we denote this impulse response , we obtain

(2.43)

It is important to recognize that while the above result is broadly valid and applies to essentially all cases of interest to us, the development is informal and there are many unstated assumptions. For example, the existence of (or more generally of ) and the applicability of the linearity condition to an integral relation are assumed. The development can be treated more rigorously in several ways, such as assuming a specific signal space with a given metric, and assuming that the linear system is continuous. Then, an arbitrary signal can be approximated as a superposition of a finite number of pulse functions of the form , and the output to this approximation determined. Taking the limit as and the extent tending to infinity yields the desired result. More details of this approach can be found in section 7.2 of Barrett and Myers (2004).

2.5.4 Response of a Linear Shift‐Invariant System

Equation (2.43) describes the response of a general space‐variant linear system. Most optical systems are indeed space variant, with the response to an impulse in the corner of the image being different than the response to an impulse in the center of the image, for example. However, the design goal is usually to have a system that is as close to being shift invariant as possible. Thus, shift‐invariant systems are an important class. In this case,

(2.44)

where is the response of the LSI system to an impulse at the origin, and so

(2.45)

Evaluating at position gives

(2.46)

which is called the convolution integral, and is denoted

(2.47)

By a simple change of variables in the integral (2.46), we can show that , i.e. convolution is commutative.

2.5.5 Frequency Response of an LSI System

Suppose that the input to an LSI system is the complex sinusoidal function . According to Equation (2.46), the corresponding output is

(2.48)

where is a complex scalar (assuming the integral converges). Thus, exactly as in one dimension, if the input to an LSI system is a complex sinusoidal signal with frequency vector , then the output is that same complex sinusoidal signal multiplied by the complex scalar . Taken as a function of the two or three‐dimensional frequency vector, is referred to as the frequency response of the LSI system. According to this observation, is called an eigenfunction of the linear system with corresponding eigenvalue .

Multiplication by amounts to multiplying the magnitude of by and introducing a phase shift of , i.e.

(2.49)

2.6.1 Fourier Transform Properties

The proofs of the properties in Table 2.1 are straightforward (aside from convergence issues) and similar to analogous proofs for the one‐dimensional Fourier transform, as given in many standard texts such as Bracewell (2000), Gray and Goodman (1995). They are presented briefly here. Again, the proofs are informal and assume that the relevant integrals converge, as would be the case for example if all the functions involved are absolutely integrable. Note that Property 2.6 relating to a linear transformation of the domain is a more complex generalization from the 1D case. In some proofs, we assume the validity of the inverse Fourier transform of Equation (2.51), although it has not been proved at this point.

Note that using this property, commutativity and associativity of complex multiplication imply commutativity and associativity of convolution.

This property can be used to determine the effect of independent scaling of ‐ and ‐axes, of rotation of the image, or of an affine transformation of the independent variable (along with the shifting property). For any rotation matrix in dimensions, and (so ), so that in this case . Also, if , we get immediately that .

If , we obtain

(2.67)

2.6.2 Evaluation of Multidimensional Fourier Transforms

In general, the multiD Fourier transform is determined by direct evaluation of the defining integral (2.50) using standard methods of integral calculus. Simplifications are possible if the function is separable or isotropic, and of course maximum use should be made of the Fourier transform properties of Table 2.1. A few examples follow, and Table 2.2 provides a number of useful two‐dimensional Fourier transforms, and others are derived in the problems.

	1

2.6.3 Two‐Dimensional Fourier Transform of Polygonal Zero–One Functions

Polygonal zero–one functions are frequently encountered in the analysis of modern cameras and display devices, and their Fourier transform is required. For the rectangular region considered in Example 2.3, it is straightforward to compute the Fourier transform by direct evaluation of the integral. However, for other shapes, such as hexagons, octagons, chevrons, etc., direct computation of the Fourier transform is more involved and tedious. It is possible to convert the area integral in the direct definition of the Fourier transform to a line integral along the boundary of the region using the 2D version of Gauss's divergence theorem and thereby obtain a closed form expression for the Fourier transform in the case of polygonal regions.

Let be a bounded, simply connected region in the plane and define as in Equation (2.1). Then, the Fourier transform is given by

(2.68)

Let be the boundary of , assumed to be piecewise smooth, traversed in the clockwise direction. Then let be a vector field defined on , assumed to be continuous with continuous first partial derivatives. The divergence theorem (see for example [(Kaplan, 1984, section 5.11)]) states that

(2.69)

where

(2.70)

is a unit vector normal to at and pointing outward, and denotes arc length along at . This result can be applied to computing the Fourier transform in Equation (2.68) by choosing

(2.71)

By applying the definition of divergence,

(2.72)

We then find that

(2.73)

This result has been called the Abbe transform and was cited in the dissertation of Straubel in 1888 [Komrska (1982)]. As shown in Komrska (1982), the contour integral can easily be evaluated in closed form for a polygonal region as follows.

Assume that is a polygon with sides, with vertices in the clockwise direction; for convenience, we denote . We define the following quantities that are easily determined once the vertices are specified:

(2.74)

(2.75)

(2.76)

(2.77)

where rotates counterclockwise by . With these definitions, the Fourier transform expression given in Equation (2.73) can be written as a sum of the integrals over each of the polygon sides as follows.

(2.78)

The integral can be easily evaluated to give the final result:

(2.79)

In many (but not all) cases of interest, the polygon is symmetric about the origin, i.e. . In this case, the number of vertices and sides is necessarily even, and the terms corresponding to the two opposite sides in Equation (2.79) can be combined to yield a real‐valued Fourier transform [Lu et al. (2009)].

(2.80)

This result has been extended to zero–one functions in more than two dimensions where the region of support is a polytope [Brandolini et al. (1997)], and applications in multiD signal processing have been described in Lu et al. (2009).

It is very straightforward to apply this result to determine the Fourier transform of a rect function, and this is left as an exercise. The following shows the application to a regular hexagon with unit side.

2.6.4 Fourier Transform of a Translating Still Image

Assume that a still image is moving with a uniform velocity to produce the time‐varying image . We wish to relate the 3D Fourier transform of to the 2D Fourier transform of .

Thus, the 3D Fourier transform is concentrated on the plane . This leads us to conclude that the 3D Fourier transform of a typical time‐varying image is not uniformly spread out in 3D frequency space, but will be largely concentrated near planes representing the dominant motions in the scene.

2.7.1 Directional Derivative

Let be a unit vector in . The directional derivative is a scalar function giving the rate of change of in the direction . This can be denoted

(2.81)

We assume is continuous at . From standard multivariable calculus, we know that

(2.82)

The magnitude of the directional derivative is maximum when the unit vector is collinear with the gradient , and it is zero when is orthogonal to the gradient. As a result, the gradient is often used to quantify the local directionality of . Although this result is quite evident from standard vector analysis, the following matrix proof leads to many interesting generalizations. We can express the magnitude squared of the directional derivative as

(2.83)

where . This is maximized when is the normalized eigenvector corresponding to the maximum eigenvalue of . Since has rank one and thus the null space has dimension , it follows that eigenvalues are zero. The eigenvector corresponding to the one non‐zero eigenvalue is , since

(2.84)

Then, the maximum value of is , which occurs for , as stated previously. The entity is usually referred to as the structure tensor, and this is a quantity that has many generalizations.

The Fourier transform of is then given by . Thus, the directional derivative is a linear shift‐invariant system with frequency response .

2.7.2 Laplacian

The Laplacian is a scalar system involving second order derivatives, typically denoted :

(2.85)

If , the Fourier transform of the output of the Laplacian is given by

(2.86)

Thus, the Laplacian is an LSI system, with frequency response , which is isotropic.

2.7.3 Filtered Derivative Systems

The derivative systems presented so far have frequency responses that increase in magnitude with . This makes them very sensitive to high‐frequency noise, and they are regularly coupled with low‐pass filters. For example, the gradient and Laplacian are frequently preceded with Gaussian filters to smooth the high frequencies before applying the gradient, Laplacian or higher‐order derivative operator. When using these to analyze the image, the Gaussian filter can also serve to set the scale at which the analysis takes place.

As an example, consider the Laplacian that is an isotropic scalar system. It is usually coupled with an isotropic Gaussian low‐pass filter with impulse response and frequency response

(2.87)

Thus, the filtered Laplacian has frequency response

(2.88)

Using the associative property of LSI systems, the impulse response of the filtered Laplacian is given by the Laplacian of the Gaussian impulse response (so it is called a Laplacian of Gaussian or LoG filter):

(2.89)

The filtered Laplacian is most frequently used in two dimensions, where the frequency response and the impulse response can be written

(2.90)

(2.91)

In general, the absolute magnitude of is not significant, and it can be scaled to any convenient value. The frequency response is circularly symmetric with value 0 at the origin and for large frequency, and a peak amplitude at the radial frequency . Figure 2.13 depicts the impulse response and magnitude frequency response of a LoG filter with ph. The filter is scaled so that the maximum magnitude frequency response is 1.0, which occurs at radial frequency 90 c/ph. Figure 2.14 shows a simulation of the filtering of the ‘Barbara’ image with this LoG filter. Since the mean output level of the filtered image is 0, a value of 0.5 on a scale of 0 to 1 is added to the image for the purpose of display.