Object Recognition and Neighborhood Operations

An analysis of the spatial relations of the gray values in a small neigh- borhood provides the fi rst clue for the recognition of objects in images. Let us take a scene containing objects with uniform radiance as a simple example. If the gray value does not change in a small neighborhood, the neighborhood lies within an object. If, however, the gray value changes signifi cantly, an edge of an object crosses the neighborhood. In this way, we recognize areas of constant gray values and edges.

Just processing individual pixels in an image by point operations does not provide this type of information. In Chapter 10 we show in detail that such operations are only useful as an initial step of image process- ing to correct inhomogeneous and nonlinear responses of the imaging sensor, to interactively manipulate images for inspection, or to improve the visual appearance.

A new class of operations is necessary that combines the pixels of a small neighborhood in an appropriate manner and yields a result that forms a new image. Operations of this kind belong to the general class of neighborhood operations. These are the central tools for low-level image processing. This is why we discuss the principally possible classes of neighborhood operations and their properties in this chapter.

The result of any neighborhood operation is still an image. How- ever, its content has been changed. A properly designed neighborhood operation to detect edges, for instance, should show bright values at pix- els that belong to an edge of an object while all pixels — independent of their gray value — should show low values. This example illustrates that by the application of a neighborhood operator, information is generally lost. We can no longer infer the original gray values. This is why neigh- borhood operations are also called fi lters. They extract a certain feature of interest from an image. The image resulting from a neighborhood operator is therefore also called a feature image.

It is obvious that operations combining neighboring pixels to form a new image can perform quite diff erent image processing tasks:

 

 

99

B. Jä hne, Digital Image Processing                                                                                                       Copyright © 2002 by Springer-Verlag

ISBN 3–540–67754–2                                                                                                    All rights of reproduction in any form reserved.

100                                                                              4 Neighborhood Operations

 

•

Detection of simple local structures such as edges, corners, lines, and areas of constant gray values (Chapters 12 and 13)

• Motion determination (Chapter 14)

• Texture analysis (Chapter 15)

•

Reconstruction of images taken with indirect imaging techniques such as tomography (Chapter 17)

•

Restoration of images degraded by defocusing, motion blur, or similar errors during image acquisition (Chapter 17)

•

Correction of disturbances caused by errors in image acquisition or transmission. Such errors will result in incorrect gray values for a few individual pixels (Chapter 17)

 

4.1.2 General Defi nition

A neighborhood operator N takes the values of the neighborhood around a point, performs some operations with them, and writes the result back on the pixel. This operation is repeated for all points of the signal.

 

Defi nition 5 (Continuous neighborhood operator) A continuous neigh- borhood operator maps a multidimensional continuous signal g( x ) onto itself by the following operation

g'( x ) = N({g( x ')}, ∀ ( x − x ') ∈ M)                                          (4.1)

where M is a compact area.

 

The area M is called mask, window, region of support, or structure element of the neighborhood operation. For the computation of g'( x ), the size and shape of M determines the neighborhood operation by spec- ifying the input values of g in the area M that is shifted with its origin to the point x. The neighborhood operation N itself is not specifi ed here. It can be of any type. For symmetry reasons the mask is often symmetric and has its origin in the symmetry center.

 

Defi nition 6 (Discrete neighborhood operator) A discrete neighborhood operator maps a M × N matrix onto itself by the operation

T

Gm'  , n = N(Gm'− m, n'− n, ∀ Σ m', n'Σ

where M is now a discrete set of points.

∈ M),                    (4.2)

 

Expressions equivalent to Def. 6 can easily be written for dimensions other than two. Although Eqs. (4.1) and (4.2) do not specify in any way the type of neighborhood operation that is performed, they still reveal the common structure of all neighborhood operations.

4.1 Basic Properties and Purpose                                                 101

 

Mask Size and Symmetry

+ ×    +

The fi rst characteristic of a neighborhood operation is the size of the neighborhood. The window may be rectangular or of any other form. We must also specify the position of the pixel relative to the window that will receive the result of the operation. With regard to symmetry, the most natural choice is to place the result of the operation at the pixel in the center of an odd-sized mask of the size (2R 1) (2R 1).

Even-sized masks seem not to be suitable for neighborhood opera- tions because there is no pixel that lies in the center of the mask. If the result of the neighborhood operation is simply written back to pixels that lay between the original pixels in the center of the mask, we can apply them nevertheless. Thus, the resulting image is shifted by half the pixel distance into every direction. Because of this shift, image features computed by even-sized masks should never be combined with original gray values because this would lead to considerable errors. If we apply several masks in parallel and combine the resulting feature images, all masks must be either even-sized or odd-sized into the same direction. Otherwise, the output lattices do not coincide.

 

Operator Notation

It is useful to introduce an operator notation for neighborhood operators. In this way, complex composite neighbor operations are easily compre- hensible. All operators will be denoted by calligraphic letters, such as

B D H S                   H

, , , . The operator         transforms the image G into the image G ':

= H

G ' G. This notation can be used for continuous and discrete signals of any dimension and leads to a compact representation-independent no- tation of signal-processing operations.

Consecutive application is denoted by writing the operators one after the other. The rightmost operator is applied fi rst. Consecutive applica- tion of the same operator is expressed by an exponent

H H. .. H = H p.                                               (4.3)

 p t˛ im¸  es  r

If the operator acts on a single image, the operand, which is to the right in the equations, can be omitted. In this way, operator equations can be written without targets. Furthermore, we will use braces in the usual way to control the order of execution. We can write basic properties of operators in an easily comprehensible way, e. g.,

 

commutativity                            H₁H₂ = H₂H₁

associativity                                H₁(H₂H₃) = (H₁H₂)H₃

distributivity over addition (H₁ + H₂)H₃ = H₁H₂ + H₂H₃

(4.4)

102                                                                              4 Neighborhood Operations

 

Other operations such as addition can also be used in this operator notation. Care must be taken, however, with any nonlinear operation. As soon as a nonlinear operator is involved, the order in which the operators are executed must strictly be given.

·

D      B

B D ·D

A simple example for a nonlinear operator is pointwise multiplication of images, a dyadic point operator. As this operator occurs frequently, it is denoted by a special symbol, a centered dot ( ). This symbol is required in order to distinguish it from successive application of opera- tors. The operator expression B(D_p · D_q), for instance, means: apply the operator D_p and D_q to the same image, multiply the result pointwise, and apply the operator B on the product image. Without parentheses the expression BD_p · D_q would mean: apply the operator D_q to the image and apply the operator _p and to the same image and then multiply the results point by point. The used operator notation thus gives monadic operators precedence to dyadic operators. If required for clarity, a placeholder for an object onto which an operator is acting is used, denoted by the symbol “: ”. With a placeholder, the aforementioned operator combination is written as ( _p: _q: ).

In the remainder of this chapter we will discuss the two most im- portant classes of neighborhood operations, linear shift-invariant fi lters (Section 4.2) and rank value fi lters (Section 4.4). An extra section is de- voted to a special subclass of linear-shift-invariant fi lters, known as re- cursive fi lters (Section 4.3).

 

4.2 Linear Shift-Invariant Filters†

Discrete Convolution

First we focus on the question as to how we can combine the gray values of pixels in a small neighborhood.

The elementary combination of the pixels in the window is given by an operation which multiplies each pixel in the range of the fi lter mask with the corresponding weighting factor of the mask, adds up the products, and writes the sum to the position of the center pixel:

 

gm'  n  =

r            r

.. hm'n' gm− m', n− n'

m'=r− r  n'=r− r

(4.5)

=..

h− m'', − n'' gm+m', n+n'.

m''=− r n''=− r

In Section 2.3.5, the discrete convolution was defi ned in Eq. (2.57) as:

 

g_m'  n =

M− 1

.

N− 1

. hm'n' gm− m', n− n'                                                       (4.6)

m'=0 n'=0

4.2 Linear Shift-Invariant Filters†                                                                       103

 

Both defi nitions are equivalent if we consider the periodicity in the space domain given by Eq. (2.44). From Eq. (2.44) we infer that negative indices are equivalent to positive coeffi cients by the relations

 

g− n = gN− n,        g− n, − m = gN− n, M− m.                                  (4.7)

+ ×    +

The restriction of the sum in Eq. (4.5) refl ects the fact that the elements of the matrix H are zero outside the few points of the (2R 1) (2R 1) fi lter mask. Thus the latter representation is much more practical and gives a better comprehension of the fi lter operation. The following 3 × 3 fi lter mask and the M × N matrix H are, e. g., equivalent

 

 0 − 1 − 2 

0_• − 1 0... 0 1





1   0 0... 0  2

 0   0 0... 0 0 

.

   1 0_•  − 1    ≡      .

... .. .

.          (4.8)

2   1   0

.   ..         ..

                                  

                                  

0   0 0... 0 0

 − 1 − 2 0... 0 0 

A W -dimensional fi lter operation can be written with a simplifi ed vec- tor indexing:

g _n '  =

R

. h_{− n} ' g _{n + n} '                                                                    (4.9)

n '=− R

with n = [n₁, n₂,..., n_W ], R = [R₁, R₂,..., R_W ], where h _n is an element of a W -dimensional signal g_n1, n2,..., nW. The notation for the sums in this equation is an abbreviation for

 

R                 R1

. =.

 

R₂                    R_W

.....

 

.                        (4.10)

n '=− R

n'1=− R₁ n'2=− R₂

n'W =− R_W

The vectorial indexing introduced here allows writing most of the rela- tions for arbitrary dimensional signals in a simple way.

 

Symmetries

With regard to symmetry, we can distinguish two important classes of fi lters: even and odd fi lters with the condition in one or more directions that

h_{− m, n} = ±h_mn or h_{m, − n} = ±h_mn,                                           (4.11)

+    −

where the     and  signs stand for even and odd symmetry. From this defi nition we can immediately reduce Eq. (4.5) to make the computation

104                                                                              4 Neighborhood Operations

 

of one-dimensional fi lters more effi cient:

.

r

even:  g_m'  n = h₀g_{m, n} +

.

r

hn'(gm, n− n' + gm, n+n')

n'=1

 

(4.12)

odd:    g_m'  n =

hn'(gm, n− n' − gm, n+n').

n'=1

The sums only run over half of the fi lter mask, excluding the center pixel, which must be treated separately because it has no symmetric counterpart. It can be omitted for the odd fi lter since the coeffi cient at the center pixel is zero according to Eq. (4.11).

In the 2-D case, the equations become more complex because it is now required to consider the symmetry in each direction separately. A 2-Dfi lter with even symmetry in both directions reduces to

gm'  , n  =  h00gnm

.

r

+     h0n'(gm, n− n' + gm, n+n')

.

n'r=1

+      hm'0(gm− m', n + gm+m', n)

m'=1

 

 

(4.13)

r        r

+.. hm'n'(gm− m', n− n' + gm− m', n+n'

m'=1 n'=1

+gm+m', n− n' + gm+m', n+n').

 

Also, 2-Dfi lters can have diff erent types of symmetries in diff erent di- rections. For example, they can be odd in horizontal and even in vertical directions. Then

gm'  , n  =

r

. h0n'(gm, n− n' − gm, n+n')

n'r=1

+.

r

. hm'n'(gm− m', n− n' − gm− m', n+n'

(4.14)

m'=1 n'=1

+gm+m', n− n' − gm+m', n+n').

 

The equations for higher dimensions are even more complex [81].

 

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

Поделиться: