Forward and Inverse Mapping

Geometric transforms defi ne the relationship between the points in two images. This relation can be expressed in two ways. Either the coordi- nates of the output image, x ', can be specifi ed as a function of the input coordinates, x, or vice versa:

x ' = M( x ) or x = M− 1( x '),                                       (10.31)

where M specifi es the mapping function and M− 1 its inverse. The two expressions in Eq. (10.31) give rise to two principal kinds of spatial trans- formation: forward mapping and inverse mapping.

With forward mapping, a pixel of the input image is mapped onto the output image (Fig. 10.15a). Generally, a pixel of the input image lies in- between the pixels of the output image. With forward mapping, it is not appropriate just to assign the value of the input pixel to the nearest pixel in the output image (point-to-point or nearest neighbor mapping). Then, it may happen that the transformed image contains holes as a value is never assigned to a pixel in the output image or that a value is assigned more than once to a point in the output image. An appropriate technique distributes the value of the input pixel to several output pixels. The easiest procedure is to regard pixels as squares and to take the fraction of the area of the input pixel that covers the output pixel as the weighting factor. Each output pixel accumulates the corresponding fractions of the input pixels which — if the mapping is continuous — add up to cover the whole output pixel.

266                                                                                               10 Pixel Processing

 

a

input image                   output image

b

input image                   output image

 

Figure 10.15: Illustration of a forward mapping and b inverse mapping for spatial transformation of images.

 

translation              rotation

surface

dilation                  stretch                shearing

 

Figure 10.16: Elementary geometric transforms for a planar surface element: translation, rotation, dilation, stretching, and shearing.

 

With inverse mapping, the coordinates of a point in the output image are mapped back onto the input image (Fig. 10.15b). It is obvious that this scheme avoids holes and overlaps in the output image as all pixels are scanned sequentially. Now, the interpolation problem occurs in the input image. The coordinates of the output image in general do not hit a pixel in the input image but lie in between the pixels. Thus, its correct value must be interpolated from the surrounding pixels. Generally, in- verse mapping is a more fl exible technique as it is easier to implement various types of interpolation techniques.

 

10.5.2 Affi ne Transform

ty

An affi ne transform is a linear coordinate transformation that includes the elementary transformations translation, rotation, scaling, stretching, and shearing (Fig. 10.16) and can be expressed by vector addition and matrix multiplication.

Σ

Σ   Σ =

x'            a11 a12

y'        a21 a22

Σ Σ x

 

Σ + Σ tx

Σ .           (10.32)

10.5 Geometric Transformations                                                   267

With homogeneous coordinates (Section 7.3.3), the affi ne transform is written with a single matrix multiplication as

 x' 

 a11 a12 tx

  x 

 y'  =  a21 a22 ty

  y  .                 (10.33)

 1 

  0   0   1

  1 

An affi ne transform has six degrees of freedom: two for translation (t_x, t_y) and one each for rotation, scaling, stretching, and shearing (a₁₁, a₁₂, a₂₁, and a₂₂). The affi ne transform maps a triangle into a triangle and a rectangle into a parallelogram. Therefore, it is also referred to as three-point mapping. Thus, it is obvious that the use of the affi ne transform is restricted. More general distortions such as the mapping of a rectangle into an arbitrary quadrilateral are not affi ne transforms.

 

Perspective Transform

 



Perspective projection is the basis of optical imaging as discussed in Section 7.3. The affi ne transform corresponds to parallel projection and can only be used as a model for optical imaging in the limit of a small fi eld of view. The general perspective transform is most conveniently written with homogeneous coordinates (Section 7.3.3) as

 w'x' 

 a11 a12 a13

  wx 

   w'y'

   =     a21  a22  a23

  wy 

 

or X' = PX.    (10.34)

                       

 

The two additional coeffi cients, a₃₁ and a₃₂, in comparison to the affi ne transform Eq. (10.33), describe the perspective projection (com- pare Eq. (7.15) in Section 7.3.3).

Written in standard coordinates, the perspective transform according to Eq. (10.34) reads as

=

x'      a₁₁x + a₁₂y + a₁₃

a₃₁x + a₃₂y + 1

=

y'   a₂₁x + a₂₂y + a₂₃.

a₃₁x + a₃₂y + 1

 

 

(10.35)

In contrast to the affi ne transform, the perspective transform is non- linear. However, it is reduced to a linear transform by using homoge- neous coordinates. A perspective transform maps lines into lines but only lines parallel to the projection plane remain parallel. A rectangle is mapped into an arbitrary quadrilateral. Therefore, the perspective transform is also referred to as four-point mapping.

268                                                                                               10 Pixel Processing

 

10.5.4 Determination of Transform Coeffi cients by Point Matching

Generally, the coeffi cients of a transform, as described in Sections 10.5.2 and 10.5.3, are not known. Instead we have a set of corresponding points between the object and image space. In this section, we learn how to infer the coeffi cients of a transform from sets of corresponding points. For an affi ne transform, we need three non-collinear points (to map a triangle into a triangle). With these three points, Eq. (10.33) results in the following linear equation system:

 

  x1'

x2'

x3'  

 a11 a12 tx

  x1 x2 x3 

   y₁^'

y2'

y3'

   =     a21  a22  ty

       y1  y2  y3

    (10.36)

1  1  1

or

0    0   1

1  1  1

P ' = AP                                                 (10.37)

from which A can be computed as

A = P ' P − 1.                                               (10.38)

The inverse of the matrix P exists when the three points X ₁, X ₂, X ₃ are linearly independent. This means geometrically that they must not lie on one line.

With more than three corresponding points, the parameters of the affi ne transform can be solved by the following equation system in a least square sense (Section 17.6):

A       =        P ' P T ( PP T )− 1 with

 

T                    ,  x_n' x_n

x_n' y_n

,

xn'



,

P ' P

y' xn           y' yn           y'

=      n                       n                        n  

 

(10.39)

, x_n     , y_n      N

n

    ,         ,                ,

 , x2

 

, xnyn, xn 

PP    =

x_ny_n          y_n        y_n

2

, x_n     , y_n      N

  .

The inverse of an affi ne transform is itself affi ne. The transformation matrix of the inverse transform is given by the inverse of A− 1.

The determination of the coeffi cients for the perspective projection is slightly more complex. Given four or more corresponding points, the coeffi cients of the perspective transform can be determined. To that end, we rewrite Eq. (10.35) as

x' = a₁₁x + a₁₂y + a₁₃ − a₃₁xx' − a₃₂yx' y' = a₂₁x + a₂₂y + a₂₃ − a₃₁xy' − a₃₂yy'.

 

(10.40)

10.6 Interpolation†                                                                                                   269

For N points, this leads to a linear equation system with 2N equations and 8 unknowns of the form

  x1'  

   x₁  y₁  1       0   0  0 − x₁x₁'

− y₁x₁'

     a'11  



y₁              0   0 0 x₁  y₁  1       − x₁y₁ − y₁y₁

a'12





'





x2'

y2'

   

 

'



x₂  y₂  1        0   0  0 − x₂x₂'

=

  0   0 0 x₂  y₂  1       − x₂y₂'

 

'

− y₂x₂'

− y₂y₂'

 a13 

  a21 

.                              .

a22

 









 

 

 

    

a23



  



 



xN'

yN'

or

x_N  x_N  1         0   0  0 − x_Nx_N'

0   0  0  x_N  y_N  1  − x_Ny_N'

− y_Nx_N'

− y_Ny_N'

a31 a32

d = Ma.                                                 (10.41)

This can be solved as a least square problem by

a = ( M T  M )− 1 M T  d.                                           (10.42)

 

10.6 Interpolation†

General

The other important aspect of discrete geometric operations besides the transform is interpolation. Interpolation is required as the transformed grid points of the input image in general no longer coincide with the grid points of the output image and vice versa.

The basis of interpolation is the sampling theorem (Section 9.2.2). This theorem states that the digital image completely represents the continuous image provided the sampling conditions are met. In short it means that each periodic structure that occurs in the image must be sampled at least twice per wavelength. From this basic fact it is easy — at least in principle — to devise a general framework for interpolation: reconstruct the continuous image fi rst and then perform a new sampling to the new grid points. This procedure only works as long as the new grid has an equal or a narrower grid spacing. If it is wider, aliasing will occur. In this case, the image must be pre-fi ltered before it is resampled. Although these procedures sound simple and straightforward, they are not at all. The problem is related to the fact that the reconstruction of the continuous image from the sampled image in practice is quite involved and can be performed only approximately. Thus, we need to consider how to optimize the interpolation given certain constraints. In this section, we will fi rst see why ideal interpolation is not possible and

then discuss various practical approaches in Sections 10.6.2–10.6.6.

In Section 9.3.1, we stated that reconstruction of a continuous func- tion from sampled points can be considered as a convolution operation,

 

=.                −

g_r ( x )           g( x _{m, n})h( x        x _{m, n}),                          (10.43)

m, n

270                                                                                               10 Pixel Processing

 

where the continuous interpolation mask h is the sinc function

h( x ) = sin π x₁/ ∆ x₁ sin π x₂/ ∆ x₂.                                   (10.44)

π x₁/∆ x₁       π x₂/∆ x₂

The transfer function of the point spread function in Eq. (10.44) isa box function with width ∆ x_w/2π:

hˆ ( k ) = Π (k˜ 1/2, k˜ 2/2)  with  k˜ w = k_w∆ x_w/π.                                  (10.45)

 

The interpolatory nature of the convolution kernel Eq. (10.44) can be inferred from the following properties. The interpolated values in Eq. (10.43) at grid points x _mn should reproduce the grid points and not depend on any other grid point. From this condition, we can infer the interpolation condition:

.h(x     ) =m, n

1    m = 0, n = 0

0    otherwise

 

.                   (10.46)

 

The interpolation mask in Eq. (10.44) meets this interpolation condi- tion. Any interpolation mask must, therefore, have zero crossings at all grid points except the zero point where it is 1.

The fact that interpolation is a convolution operation and thus can be described by a transfer function in Fourier space Eq. (10.45) gives us a handy tool to rate the errors associated with an interpolation tech- nique. The box-type transfer function for the ideal interpolation func- tion simply means that all wave numbers within the range of possible

| | ≤

wave numbers k_w         ∆ x_w/π experience neither a phase shift nor am-

plitude damping. Also, no wave numbers beyond the allowed interval are present in the interpolated signal, because the transfer function is zero there.

The ideal interpolation function in Eq. (10.43) is separable. Therefore, interpolation can as easily be formulated for higher-dimensional images. We can expect that all solutions to the interpolation problem will also be separable. Consequently, we need only discuss the 1-Dinterpolation problem. Once it is solved, we also have a solution for the n-dimensional interpolation problem.

An important special case is the interpolation to intermediate grid points halfway between the existing grid points. This scheme doubles the resolution and image size in all directions in which it is applied. Then, the continuous interpolation kernel reduces to a discrete convo- lution mask. As the interpolation kernel Eq. (10.44) is separable, we can fi rst interpolate the intermediate points in a row in the horizontal direc- tion before we apply vertical interpolation to the intermediate rows. In three dimensions, a third 1-Dinterpolation is added in the z or t direc- tion. The interpolation kernels are the same in all directions. We need

10.6 Interpolation†                                                                                                  271

the continuous kernel h(x) only at half-integer values for x/∆ x. From Eq. (10.44) we obtain the discrete ideal interpolation kernel

h Σ      (–1)m− 1 2

– 222 – 2

(–1)m− 1 2

Σ (10.47)

= ··· (2m − 1)π ···

3π π π

3π ··· (2m − 1)π ··· 

with coeffi cients of alternating sign.

 

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

Поделиться: