Linearity and Shift Invariance

Linear operators are defi ned by the principle of superposition.

H

Defi nition 7 (Superposition Principle) If G and G ' are two W -dimension- al complex-valued signals, a and b are two complex-valued scalars, and is an operator that maps G onto G ', then the operator is linear if and

only if

H (a G + b G ') = aH G + bH G '.                                  (4.15)

We can generalize Def. 7 to the superposition of many inputs

 

H .akGk  =.akH Gk.                                    (4.16)

 k              k

The superposition states that we can decompose a complex signal into simpler components. We can apply a linear operator to these com- ponents and then compose the resulting response from that of the com- ponents.

Another important property of an operator is shift invariance (also known as translation invariance or homogeneity). It means that the re- sponse of the operator does not explicitly depend on the position in the image. If we shift an image, the output image is the same but for the shift applied. We can formulate this property more elegantly if we defi ne a shift operator mnS as

mnSgm'n'  = gm'− m, n'− n.                                             (4.17) Then we can defi ne a shift-invariant operator in the following way:

Defi nition 8 (Shift invariance) An operator is shift invariant if and only if it commutes with the shift operator S:

H mnS= mnSH.                                             (4.18)

From the defi nition of the convolution operation Eqs. (4.5) and (4.9), it is obvious that it is both linear and shift invariant. This class of operators is called linear shift-invariant operators (LSI operators). In the context of time series, the same property is known as linear time-invariant (LTI ). Note that the shift operator mnS itself is an LSI operator.

Point Spread Function

The linearity and shift-invariance make it easy to understand the re- sponse to a convolution operator. As discussed in Section 2.3.1, we can decompose any discrete image (signal) into its individual points or basis images:

M− 1 N− 1

G =.. G_mn mn P.                                       (4.19)

m=0 n=0

108                                                                              4 Neighborhood Operations

 

Linearity says that we can apply an operator to each basis image and than add up the resulting images. Shift invariance says, that the response to each of the point images is the same except for a shift. Thus, if we know the response to a point image, we can compute the response to any image.

Consequently, the response to a point image has a special meaning. It is known as the point spread function (PSF, for time series often de- noted as impulse response, the response to an impulse). The PSF of a convolution or LSI operator is identical to its mask:

r

pm'  n =.

r

00

. h− m', − n' pm+m', n+n' = hm, n                                            (4.20)

m'=− r n'=− r

and completely describes a convolution operator in the spatial domain.

 

Transfer Function

In Section 2.3, we discussed that an image can also be represented in the Fourier domain. This representation is of special importance for linear fi lters since the convolution operation reduces to a multiplication in the Fourier domain according to the convolution theorem (Theorem 4, p. 52).

g ∗ h ◦ • N g ˆ h ˆ, G ∗ H ◦ • MN G ˆ H ˆ

(4.21)

The Fourier transform of the convolution mask or PSF is known as the transfer function of the linear fi lter. The transfer function has an important practical meaning. For each wave number, it gives the factor by which a periodic structure is multiplied using the fi lter operation. Note that this factor is a complex number. Thus a periodic structure experiences not only a change in the amplitude but also a phase shift:

gˆ u' , v = hˆ u, v gˆ _{u, v}  =  r_h exp(iϕ _h) r_g exp(iϕ _g)

= r_hr_g exp[i(ϕ _h + ϕ _g)],

(4.22)

 

where the complex numbers are represented in the second part of the equation with their magnitude and phase as complex exponentials.

The symmetry of the fi lter masks, as discussed in Section 4.2.2, sim- plifi es the transfer function considerably. We can then combine the cor- responding symmetric terms in the Fourier transform of the PSF:

hˆ v  =

R n'.=− R

h_n' exp.− 2π inv Σ      (with  h_{− n}' = ±h_n')

N

r

 

 

(4.23)

= h₀ +

. h_n' .exp.− 2π inv Σ  ± exp. 2π inv Σ Σ  .

n'=1                                            N                          N

4.2 Linear Shift-Invariant Filters†                                                                        109

 

The defi nition of the transfer function includes the factors N and MN, respectively. In all future equations for transfer functions Nh_v and MNHˆ  is replaced by hˆ v and Hˆ v , respectively.

These equations can be further simplifi ed by replacing the discrete wave number by the scaled continuous wave number

k˜  = 2v/N,      with  − N/2 ≤ v < N/2.                           (4.24)

−

The scaled wave number k˜  is confi ned to the interval [  1, 1[.  A wave number at the edge of this interval corresponds to the maximal wave number that meets the sampling theorem (Section 9.2.3).

=     +

Using the Euler equation exp(ix) cos x i sin x, Eq. (4.23) reduces for 1-Deven and odd fi lters to:

 

even:

hˆ (k˜ ) = h₀ +

R

. 2h_n' cos(n'π k˜ )

 

odd:

R n'=1

.

hˆ (k˜ ) = − i        2h_n' sin(n'π k˜ ).

n'=1

(4.25)

+ ×    +

Correspondingly, a (2R       1) (2R 1) mask with even horizontal and vertical symmetry results in the transfer function

hˆ ( k ˜ )  =  h₀₀

R                                                                  R

+  2. h_0n' cos(n'π k˜ 1) + 2.  h_m'0 cos(m'π k˜ 2)

n'=1

R       R

m'=1

(4.26)

+  4.. h_m'n' cos(n'π k˜ 1) cos(m'π k˜ 2).

m'=1 n'=1

Similar equations are valid for other symmetry combinations.

Equations (4.25) and (4.26) are very useful, because they give a straight- forward relationship between the coeffi cients of a fi lter mask and the transfer function. They will be our main tool to study the properties of fi lters for specifi c image processing tasks in Chapters 11–15.

 

Further Properties

In this section, we discuss some further properties of convolution oper- ators that we be useful for image and signal processing.

Property 1 (Commutativity) LSI operators are commutative:

HH ' = H 'H,                                               (4.27)

i. e., the order in which we apply convolution operators to an image does not matter. This property is easy to prove in the Fourier domain, because there the operators reduce to a commutative multiplication.

110                                                                              4 Neighborhood Operations

 

Property 2 (Associativity) LSI operators are associative:

H 'H '' = H.                                                  (4.28)

Because LSI operations are associative, we can compose a complex oper- ator out of simple operators. Likewise, we can try to decompose a given complex operator into simpler operators. This feature is essential for an eff ective implementation of convolution operators. As an example, we consider the operator

1 4 6 4 1 4 16 24 16 4 6 24 36 24 6 4 16 24 16 4 1 4 6 4 1

                            

                             .                               (4.29)

                              

 

 

We need 25 multiplications and 24 additions per pixel with this convo- lution mask. We can easily verify, however, that we can decompose this mask into a horizontal and vertical mask:





1 4 6 4 4 16 24 16 6 24 36 24 4 16 24 16 1 4 6 4

1                                  1 

                        6  = [1464 1] ∗  6  .              (4.30)

1

 

                          4   

4

 1 

 

Applying the two convolutions with the smaller masks one after the other, we need only 10 multiplications and 8 additions per pixel. Fil- ter masks which can be decomposed into one-dimensional masks along the axes are called separable masks. We will denote one-dimensional op- erators with an index indicating the axis. We can then write a separable operator B in a three-dimensional space:

B= B_zB_yB_x.                                                (4.31)

× ×

In case of one-dimensional masks directed in orthogonal directions, the convolution reduces to an outer product. Separable fi lters are more effi - cient the higher the dimension of the space. Let us consider a 9 9 9 fi lter mask as an example. A direct implementation would cost 729 mul- tiplications and 728 additions per pixel, while a separable mask of the same size would just need 27 multiplications and 24 additions, a factor of about 30 fewer operations.

Property 3 (Distributivity over Addition) LSI operators are distributive over addition:

H ' +H '' = H.                                                (4.32)

4.2 Linear Shift-Invariant Filters†                                                                       111

 

Because LSI operators are elements of the same vector space to which they are applied, we can defi ne addition of the operators by the addition of the vector elements. Because of this property we can also integrate operator additions and subtractions into our general operator notation introduced in Section 4.1.4.

 

⇐ Предыдущая19202122232425262728Следующая ⇒

Поделиться: