General Properties of a Scale Space

In this section, we discuss some general properties of scale spaces. More specifi cally, we want to know what kinds of condition must be met by a fi lter kernel generating a scale space. We will discuss two basic re- quirements. First, no new details must be added with increasing scale parameter. From the perspective of information theory, we may say that the information content in the signal should continuously decrease with the scale parameter.

The second property is related to the general principle of scale in- variance. This basically means that we can start smoothing the signal at any scale parameter in the scale space and still obtain the same scale space. Here, we will give only some basic ideas about these elementary properties and no proofs. For a detailed treatment of the scale space theory we refer to the recent monograph on linear scale space theory by Lindeberg [113].

The linear homogenous and isotropic diff usion process has according to Eq. (5.14) the convolution kernel

B ( x, ξ )   1 exp.

| x |2 Σ                       (5.20)

 

= 2π ξ and the transfer function Eq. (5.13)

− 2ξ

B ˆ ( k, ξ ) = exp(− 2π 2| k |2ξ ).                                         (5.21)

In these equations, we have replaced the explicit dependence on time by the scale parameter ξ using Eq. (5.16). In a representation-independent

5.2 Scale Space†                                                                                                    133

 

way, we denote the scale space generating operator as

B(ξ ).                                                     (5.22)

The information-decreasing property of the scale space with ξ can be formulated mathematically in diff erent ways. We express it here with the minimum-maximum principle which states that local extrema must not be enhanced. This means that the gray value at a local maximum or minimum must not increase or decrease, respectively. For a diff usion process this is an intuitive property. For example, in a heat transfer problem, a hot spot must not become hotter or a cool spot cooler. The Gaussian kernel Eq. (5.20) meets the minimum-maximum principle.

The second important property of the scale space is related to the scale invariance principle. We want to start the generating process at any scale parameter and still get the same scale space. More quantitatively, we can formulate this property as

B(ξ ₂)B(ξ ₁) = B(ξ ₁ + ξ ₂).                                         (5.23)

+

This means that the smoothing of the scale space at the scale ξ ₁ by an op- erator with the scale ξ ₂ is equivalent to the application of the scale space operator with the scale ξ ₁ ξ ₂ to the original image. Alternatively, we can state that the representation at the coarser level ξ ₂ can be computed from the representation at the fi ner level ξ ₁ by applying

B(ξ ₂) = B(ξ ₂ − ξ ₁)B(ξ ₁) with ξ ₂ > ξ ₁.                                (5.24)

From Eqs. (5.20) and (5.21) we can easily verify that Eqs. (5.23) and (5.24) are true. In mathematics the properties Eqs. (5.23) and (5.24) are referred to as the semi-group property.

Conversely, we can ask what scale space generating kernels exist that meet both the minimum-maximum principle and the semi-group prop- erty. The answer to this question may be surprising. The Gaussian kernel is the only convolution kernel that meets both these criteria and is in ad- dition isotropic and homogeneous [113]. This feature puts the Gaussian convolution kernel and — as we will see later — its discrete counterpart the binomial kernel into a unique position for image processing. It will be elaborated in more detail in Section 11.4.

W

It is always instructive to discuss a counterexample. The most straight- forward smoothing kernel for a W -dimensional image — known as the moving average — is the box fi lter

R ( x, ξ ) = 1

. Π . x w Σ                      (5.25)

 

with the transfer function

ξ W w=1              ξ

R ˆ ( k, ξ ) =

W w.=1

sin(k_wξ /2) k_wξ /2

 

.                              (5.26)

134                                                                              5 Multiscale Representation

 

A                                                                    b

Figure 5.4: Scale space of a 1-D signal with varying wave number computed with a a Gaussian and b box kernel. The scale parameter runs from top to bottom.

 

This kernel meets neither the minimum-maximum principle nor the semi- group property. Figure 5.4 compares scale spaces of a periodic signal with varying wave number generated with a Gaussian and a box ker- nel. In Fig. 5.4b it becomes evident that the box kernel does not meet the minimum-maximum principle as structures decrease until they are completely removed but then appear again.

 

5.2.3 Quadratic and Logarithmic Scale Spaces‡

Despite the mathematical beauty of scale space generation with a Gaussian con- volution kernel, this approach has one signifi cant disadvantage. The standard deviation of the smoothing increases only by the power half with time Eq. (5.15). Therefore the scale parameter ξ is only proportional to the square of the stan- dard deviation. This results in a nonlinear scale coordinate. While smoothing goes fast for fi ne scales, it becomes increasingly slower for larger scales.

There is a simple cure for this problem. We need a diff usion process where the diff usion constant increases with time. We fi rst discuss a diff usion coeffi - cient that increases linearly with time. This approach results in the diff erential equation

∂ g

∂ t = D₀t∆ g.                                                   (5.27)

A spatial Fourier transform results in

∂ t

∂ g ˆ ( k ) = − 4π 2D₀t| k |2gˆ ( k ).                                           (5.28)

This equation has the general solution

.=

| |

Σ

gˆ ( k, t) = exp(− 2π 2D₀t2| k |2)gˆ ( k, 0)                                        (5.29) which is equivalent to a convolution in the spatial domain. Thus,

g( x, t)

1 exp 2π D₀t2

x 2

 

− 2D₀t2 ∗

g( x, 0).                    (5.30)

5.2 Scale Space†                                                                                                    135

From these equations we can write the convolution kernel and transfer function in the same form as in Eqs. (5.20) and (5.21) with the only exception that the scale parameter

ξ _q = D₀t2.                                                     (5.31)

Now the standard deviation for the smoothing is proportional to time for a diff usion process that increases linearly in time. As the scale parameter ξ is proportional to the time squared, we denote this scale space as the quadratic scale space. This modifi ed scale space still meets the minimum-maximum prin- ciple and the semi-group property.

For even more accelerated smoothing, we can construct a logarithmic scale space, i. e., a scale space where the logarithm of the scale parameter increases linearly with time. We use a diff usion coeffi cient that increases exponentially in time

∂ g

∂ t = D₀ exp(t/τ )∆ g.                                                (5.32)

Again, we obtain a convolution kernel and a transfer function as in Eqs. (5.20) and (5.21), now with the scale parameter

ξ _l = 2D₀τ exp(t/τ ).                                                  (5.33)

5.2.4 Diff erential Scale Spaces‡

The interest in a diff erential scale space stems from the fact that we want to select optimum scales for processing of features in images. In a diff erential scale space, the change of the image with scale is emphasized. We use the transfer function of the scale space kernel Eq. (5.21) which is also valid for quadratic and logarithmic scale spaces. The general solution for the scale space can be written in the Fourier space as

gˆ ( k, ξ ) = exp(− 2π 2| k |2ξ )gˆ ( k, 0).                                         (5.34) Diff erentiating this signal with respect to the scale parameter ξ yields

∂ ξ

∂ g ˆ ( k , ξ ) = − 2π 2| k |2 exp(− 2π 2| k |2ξ )gˆ ( k, 0) = − 2π 2| k |2gˆ ( k, ξ ).                               (5.35)

The multiplication with − | k |2 is equivalent to a second-order spatial derivative (± R4), the Laplacian operator. Thus we can write in the spatial domain

∂ g( x , ξ )      1

∂ ξ     = 2 ∆ g( x, ξ ).                                          (5.36)

Equations (5.35) and (5.36) constitute a basic property of the diff erential scale space. The diff erential scale space is equivalent to a second-order spatial deriva- tion with the Laplacian operator and thus leads to an isotropic bandpass decom- position of the image. The transfer function at the scale ξ is

− 2π 2| k |2 exp(− 2π 2| k |2ξ ).                                              (5.37)

− | |

For small wave numbers, the transfer function is proportional to k 2. It reaches a maximum at

 

 

and then decays exponentially.

2           2

k

max = ξ

(5.38)

136                                                                              5 Multiscale Representation

 

5.2.5 Discrete Scale Spaces‡

The construction of a discrete scale space requires a discretization of the diff u- sion equation. We start with a discretization of the one-dimensional diff usion

equation                                 ∂ g(x,  ξ )

∂ ξ    = D

∂ 2g(x, ξ ).                             (5.39)

∂ x2

The derivatives are replaced by discrete diff erences in the following way:

∂ g(x, ξ )

∂ ξ

∂ 2g(x, ξ )

 

g(x, ξ + ∆ ξ ) − g(x, ξ )

=

∆ ξ

g(x + ∆ x, ξ ) − 2g(x, ξ ) + g(x − ∆ x, ξ )

 

 

(5.40)

∂ x2             =                                  ∆ x2                                               .

This leads to the following iteration scheme for computing a discrete scale space with H = D∆ ξ /∆ x2:

g(x, ξ + ∆ ξ ) = Hg(x + ∆ x, ξ ) + (1 − 2H)g(x, ξ ) + Hg(x − ∆ x, ξ )                                  (5.41) or written with discrete coordinates

i+1g_n = H ig_n+1 + (1 − 2H) ig_n + H ig_{n− 1}.                                          (5.42)

Lindeberg [113] shows that this iteration results in a discrete scale space that meets the minimum-maximum principle and the semi-group property if and only if                          H ≤ 1/4.                                                     (5.43)

The limiting case of ∆ ξ = 1/4 leads to the especially simple iteration

i+1g_n = 1/4 ⁱg_n+1 + 1/2 ⁱg_n + 1/4 ⁱg_{n− 1}.                                            (5.44)

=

Each step of the scale space computation is given by a spatial smoothing of the signal with the mask B 2 [1/4 1/2 1/4]. We can also formulate the general

B

scale space generating operator in Eq. (5.41) using the convolution operator. Written in the operator notation introduced in Section 4.1.4, the operator for one iteration step to generate the discrete scale space is

(1 − 4H)I+ 4HB2 with H ≤ 1/4,                                        (5.45)

where I denotes the identity operator.

B

This expression is signifi cant, as it can be extended directly to higher dimen- sions by replacing 2 with a correspondingly higher-dimensional smoothing operator. The convolution mask B 2 is the simplest mask in the class of smooth- ing binomial fi lters. These fi lters will be discussed in detail in Section 11.4.

 

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

Поделиться: