Representation in the Fourier Domain

A simple neighborhood also has a special form in Fourier space. In or- der to derive it, we fi rst assume that the whole image is described by Eq. (13.1), i. e., n ¯ does not depend on the position. Then — from the very fact that a simple neighborhood is constant in all directions except n ¯

— we infer that the Fourier transform must be confi ned to a line. The direction of the line is given by n ¯:

g( x T  n ¯ )       ◦ •   gˆ (k)δ ( k − n ¯ ( k ^T n ¯ )),                       (13.3)

 

342                                                                                  13 Simple Neighborhoods

 

Figure 13.3: Illustration of a linear symmetric or simple neighborhood. The gray values depend only on a coordinate given by a unit vector n ¯.

 

−

where k denotes the coordinate in the Fourier domain in the direction of n ¯.  The argument in the δ function is only zero when k   is parallel to n ¯.  In a second step, we now restrict Eq. (13.3) to a local neighbor- hood by multiplying g( x T  n ¯ ) with a window function w( x  x ₀) in the spatial domain. Thus, we select a local neighborhood around x ₀. The size and shape of the neighborhood is determined by the window func- tion. A window function that gradually decreases to zero diminishes the infl uence of pixels as a function of their distance from the outer pixel. Multiplication in the space domain corresponds to a convolution in the Fourier domain (Section 2.3). Thus,

w( x − x ₀) · g( x T  n ¯ )           ◦ •   wˆ ( k ) ∗ gˆ (k)δ ( k − n ¯ ( k ^T n ¯ )),  (13.4)

where wˆ ( k ) is the Fourier transform of the window function.

The limitation to a local neighborhood, thus, blurs the line in Fourier space to a “sausage-like” shape. Because of the reciprocity of scales be- tween the two domains, its thickness is inversely proportional to the size of the window. From this elementary relation, we can already conclude qualitatively that the accuracy of the orientation estimate is directly re- lated to the ratio of the window size to the wavelength of the smallest structures in the window.

 

Vector Representation of Local Neighborhoods

For an appropriate representation of simple neighborhoods, it is fi rst important to distinguish orientation from direction. The direction is de- fi ned over the full angle range of 2π (360°). Two vectors that point in opposite directions, i. e., diff er by 180°, are diff erent. The gradient vec- tor, for example, always points into the direction into which the gray values are increasing. With respect to a bright object on a dark back- ground, this means that the gradient at the edge is pointing towards the

13.2 Properties of Simple Neighborhoods                                     343

A                                           b                                           c

Figure 13.4: Representation of local orientation as a vector: a the orientation vector; b averaging of orientation vectors from a region with homogeneous ori- entation; c same for a region with randomly distributed orientation.

 

object. In contrast, to describe the direction of a local neighborhood, an angle range of 360° makes no sense. We cannot distinguish between patterns that are rotated by 180°. If a pattern is rotated by 180°, it still has the same direction. Thus, the direction of a simple neighborhood is diff erent from the direction of a gradient. While for the edge of an object, gradients pointing in opposite directions are confl icting and in- consistent, for the direction of a simple neighborhood this is consistent information.

In order to distinguish the two types of “directions”, we will speak of orientation in all cases where an angle range of only 180° is required. Orientation is still, of course, a cyclic quantity. Increasing the orientation beyond 180° fl ips it back to 0°. Therefore, an appropriate representation of orientation requires an angle doubling.

After this discussion of the principles of representing orientation, we are ready to think about an appropriate representation of simple neigh- borhoods. Obviously, a scalar quantity with just the doubled orientation angle is not appropriate. It seems to be useful to add a certainty mea- sure that describes how well the neighborhood approximates a simple neighborhood. The scalar quantity and the certainty measure can be put together to form a vector. We set the magnitude of the vector to the certainty measure and the direction of the vector to the doubled orien- tation angle (Fig. 13.4a). This vector representation of orientation has two signifi cant advantages.

First, it is more suitable for further processing than a separate repre- sentation of the orientation by two scalar quantities. Take, for example, averaging. Vectors are summed up by chaining them together, and the resulting sum vector is the vector from the starting point of the fi rst vector to the end point of the last vector (Fig. 13.4b). The weight of an individual vector in the vector sum is given by its length. In this way, the certainty of the orientation measurement is adequately taken into

344                                                                                  13 Simple Neighborhoods

 

account. The vectorial representation of local orientation shows suit- able averaging properties. In a region with homogeneous orientation the vectors line up to a large vector (Fig. 13.4b), i. e., a certain orientation estimate. In a region with randomly distributed orientation, however, the resulting vector remains small, indicating that no signifi cant local orientation is present (Fig. 13.4c).

Second, it is diffi cult to display orientation as a gray scale image. While orientation is a cyclic quantity, the gray scale representation shows an unnatural jump between the smallest angle and the largest one. This jump dominates the appearance of the orientation images and, thus, does not give a good impression of the orientation distribution. The orientation vector can be well represented, however, as a color image. It appears natural to map the certainty measure onto the luminance and the orientation angle as the hue of the color. Our attention is then drawn to the bright parts in the images where we can distinguish the colors well. The darker a color is, the more diffi cult it gets to distinguish the diff erent colors visually. In this way, our visual impression coincides with the orientation information in the image.

 

13.3 First-Order Tensor Representation†

The Structure Tensor

The vectorial representation discussed in Section 13.2.3 is incomplete. Although it is suitable for representing the orientation of simple neigh- borhoods, it cannot distinguish between neighborhoods with constant values and isotropic orientation distribution (e. g., uncorrelated noise). Both cases result in an orientation vector with zero magnitude.

Therefore, it is obvious that an adequate representation of gray value changes in a local neighborhood must be more complex. Such a repre- sentation should be able to determine a unique orientation (given by a unit vector n ¯ ) and to distinguish constant neighborhoods from neigh- borhoods without local orientation.

A suitable representation can be introduced by the following opti- mization strategy to determine the orientation of a simple neighborhood. The optimum orientation is defi ned as the orientation that shows the least deviations from the directions of the gradient. A suitable measure for the deviation must treat gradients pointing in opposite directions equally. The squared scalar product between the gradient vector and the unit vector representing the local orientation n ¯ meets this criterion:

( ∇ gT  n ¯ )2 = | ∇ g|2 cos².∠ ( ∇ g, n ¯ )Σ  .                                 (13.5)

This quantity is proportional to the cosine squared of the angle be- tween the gradient vector and the orientation vector and is thus maximal

13.3 First-Order Tensor Representation†                                                         345

 

∇

when  g and n ¯ are parallel or antiparallel, and zero if they are perpen- dicular to each other. Therefore, the following integral is maximized in a W -dimensional local neighborhood:

∫  w( x − x '). ∇ g( x ')T  n ¯ Σ 2 d^W x',                                  (13.6)

where the window function w determines the size and shape of the neighborhood around a point x in which the orientation is averaged. The maximization problem must be solved for each point x. Equation Eq. (13.6) can be rewritten in the following way:

n ¯ ^T J n ¯ → maximum                                           (13.7)

 

with

J = ∫  w( x − x '). ∇ g( x ') ∇ g( x ')T Σ  d^W x',

 

where ∇ g ∇ gT denotes an outer (Cartesian) product. The components of this symmetric W × W matrix are

 

∞

J_pq( x ) = ∫ w( x −

− ∞

x '). ∂ g( x ') ∂ g( x ') Σ d^W x'.                 (13.8)

∂ xp'    ∂ xq'

These equations indicate that a tensor is an adequate fi rst-order rep- resentation of a local neighborhood. The term fi rst-order has a double meaning. First, only fi rst-order derivatives are involved. Second, only simple neighborhoods can be described in the sense that we can analyze in which direction(s) the gray values change. More complex structures such as structures with multiple orientations cannot be distinguished.

The complexity of Eqs. (13.7) and (13.8) somewhat obscures their sim- ple meaning. The tensor is symmetric. By a rotation of the coordinate system, it can be brought into a diagonal form. Then, Eq. (13.7) reduces in the 2-Dcase to

1

2

0  J2' 2

J' = Σ n¯ ^', n¯ ^' Σ  Σ   J1' 1            0

Σ Σ  n¯ '1

Σ → maximum.           (13.9)

 

A unit vector n ¯ ^' = [cos φ sin φ ] in the direction φ gives the values

J' = J₁' 1 cos² φ + J₂' 2 sin² φ.

=

≥

Without loss of generality,  we assume that J₁' 1  J₂' 2.  Then,  it is obvious that the unit vector n ¯ ^'  [1 0]^T maximizes Eq. (13.9). The max- imum value is J₁' 1. In conclusion, this approach not only yields a tensor representation for the local neighborhood but also shows the way to de- termine the orientation. Essentially, we have to solve what is known as

346                                                                                  13 Simple Neighborhoods

 

 

Table 13.1: Eigenvalue classifi cation of the structure tensor in 2-D images.

 

Condition	rank(J)	Description
λ 1 = λ 2 = 0	0	Both eigenvalues are zero. The mean squared magnitude of the gradient (λ 1 + λ 2) is zero. The
λ 1 > 0, λ 2 = 0	1	local neighborhood has constant values. One eigenvalue is zero. The values do not change in the direction of the corresponding eigenvec- tor. The local neighborhood is a simple neigh-
λ 1 > 0, λ 2 > 0	2	borhood with ideal orientation. Both eigenvalues are unequal to zero. The gray values change in all directions. In the special case
		of λ 1 = λ 2, we speak of an isotropic gray value structure as it changes equally in all directions.

 

an eigenvalue problem. The eigenvalues λ _w and eigenvectors e _w of a

W × W matrix are defi ned by:

Je _w = λ _w e _w.                                               (13.10)

An eigenvector e _w of J is thus a vector that is not turned in direction by multiplication with the matrix J but is only multiplied by a scalar factor, the eigenvalue λ _w. This implies that the structure tensor be- comes diagonal in a coordinate system that is spanned by the eigen- vectors Eq. (13.9). For our further discussion it is important to keep the following basic facts about the eigenvalues of a symmetric matrix in mind:

1. The eigenvalues are all real and non-negative.

2. The eigenvectors form an orthogonal basis.

According to the maximization problem formulated here, the eigen- vector to the maximum eigenvalue gives the orientation of the local neighborhood.

 

13.3.2 Classifi cation of Eigenvalues

=

The power of the tensor representation becomes apparent if we classify the eigenvalues of the structure tensor. The classifying criterion is the number of eigenvalues that are zero. If an eigenvalue is zero, this means that the gray values in the direction of the corresponding eigenvector do not change. The number of zero eigenvalues is also closely related to the rank of a matrix. The rank of a matrix is defi ned as the dimension of the subspace for which Jk ≠ 0. The space for which is Jk 0 is denoted as the null space. The dimension of the null space is the dimension of the matrix minus the rank of the matrix and equal to the number of zero

13.3 First-Order Tensor Representation†                                                       347

 

Table 13.2: Eigenvalue classifi cation of the structure tensor in 3-D (volumetric) images.

 

Condition	rank(J)	Description
λ 1 = λ 2 = λ 3 = 0	0	The gray values do not change in any di- rection; constant neighborhood.
λ 1 > 0, λ 2 = λ 3 = 0	1	The gray values change only in one di- rection. This direction is given by the eigenvector to the non-zero eigenvalue. The neighborhood includes a boundary between two objects or a layered texture.
λ 1 > 0, λ 2 > 0, λ 3 = 0	2	In a space-time image, this means a con- stant motion of a spatially oriented pat- tern (“planar wave”). The gray values change in two directions and are constant in a third. The eigenvec- tor to the zero eigenvalue gives the direc-
λ 1 > 0, λ 2 > 0, λ 3 > 0	3	tion of the constant gray values. The gray values change in all three direc- tions.

 

 

eigenvalues. We will perform an analysis of the eigenvalues for two and three dimensions. In two and three dimensions, we can distinguish the cases summarized in Tables 13.1 and 13.2, respectively.

In practice, it will not be checked whether the eigenvalues are zero but below a critical threshold that is determined by the noise level in the image.

 

Orientation Vector

With the simple convolution and point operations discussed in the pre- vious section, we computed the components of the structure tensor. In this section, we solve the eigenvalue problem to determine the orien- tation vector. In two dimensions, we can readily solve the eigenvalue problem. The orientation angle can be determined by rotating the iner- tia tensor into the principal axes coordinate system:

Σ λ ₁ 0

Σ = Σ cos φ − sin φ Σ Σ J₁₁ J₁₂

Σ Σ cos φ    sin φ Σ .

0 λ ₂

sin φ       cos φ

J12 J22

− sin φ cos φ

Using the trigonometric identities sin 2φ = 2 sin φ cos φ and cos 2φ =

cos2 φ − sin² φ, the matrix multiplications result in

348                                                                                  13 Simple Neighborhoods

 

 

 λ 1 0 

   0  λ 2    =

 cos φ − sin φ            J₁₁ cos φ − J₁₂ sin φ J₁₁ sin φ + J₁₂ cos φ 

   sin φ       cos φ         − J₂₂ sin φ + J₁₂ cos φ  J₂₂ cos φ + J₁₂ sin φ     =

 J₁₁ cos2 φ + J₂₂ sin² φ –J₁₂ sin 2φ                   1/2(J₁₁–J₂₂) sin 2φ + J₁₂ cos 2φ 

   1/2(J₁₁–J₂₂) sin 2φ + J₁₂ cos 2φ                   J₁₁ sin² φ + J₂₂ cos2 φ + J₁₂ sin 2φ   

Now we can compare the matrix coeffi cients on the left and right side of the equation. Because the matrices are symmetric, we have three equations with three unknowns, φ, λ ₁, and λ ₂. Although the equation system is nonlinear, it can readily be solved for φ.

A comparison of the off -diagonal elements on both sides of the equa- tion

1/2(J₁₁ − J₂₂) sin 2φ + J₁₂ cos 2φ = 0                                 (13.11)

yields the orientation angle as

=

tan 2φ    2J 12         .                                   (13.12)

J22 − J11

Σ o =

Without defi ning any prerequisites, we have obtained the anticipated angle doubling for orientation. Since tan 2φ is gained from a quotient, we can regard the dividend as the y and the divisor as the x component of a vector and can form the orientation vector o, as introduced by Granlund [56]:

J22 − J11

2J₁₂

Σ .                                   (13.13)

The argument of this vector gives the orientation angle and the mag- nitude a certainty measure for local orientation.

The result of Eq. (13.13) is remarkable in that the computation of the components of the orientation vector from the components of the orientation tensor requires just one subtraction and one multiplication by two. As these components of the orientation vector are all we need for further processing steps we do not need the orientation angle or the magnitude of the vector. Thus, the solution of the eigenvalue problem in two dimensions is trivial.

 

Coherency

The orientation vector reduces local structure to local orientation. From three independent components of the symmetric tensor still only two are

13.3 First-Order Tensor Representation†                                                       349

+

used. When we fail to observe an orientated structure in a neighborhood, we do not know whether no gray value variations or distributed orienta- tions are encountered. This information is included in the not yet used component of the tensor, J₁₁ J₂₂, which gives the mean square magni- tude of the gradient. Consequently, a well-equipped structure operator needs to include also the third component. A suitable linear combination is

s  =     J −  J22                           11

 J11 + J22

2J₁₂

 .                                   (13.14)





This structure operator contains the two components of the orientation vector and, as an additional component, the mean square magnitude of the gradient, which is a rotation-invariant parameter. Comparing the latter with the magnitude of the orientation vector, a constant gray value area and an isotropic gray value structure without preferred orientation can be distinguished. In the fi rst case, both squared quantities are zero, in the second only the magnitude of the orientation vector. In the case of a perfectly oriented pattern, both quantities are equal. Thus their ratio seems to be a good coherency measure c_c for local orientation:

 (J₂₂ − J₁₁)2 + 4J2

λ − λ

c_c =

12           1        2.                  (13.15)

J11 + J22

λ ₁ + λ ₂

=

=

=

The coherency ranges from 0 to 1. For ideal local orientation (λ ₂ 0, λ ₁ > 0) it is one, for an isotropic gray value structure (λ ₁ λ ₂ > 0) it is zero.

 

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

Поделиться: