Limitation to a Finite Window

So far, the sampled image is still infi nite in size. In practice, we can only work with fi nite image matrices. Thus the last step is the limitation of the image to a fi nite window size. The simplest case is the multiplication of the sampled image with a box function. More generally, we can take any window function g_l( x ) which is zero for suffi ciently large x values:

g_l( x ) = g_s( x ) · w( x )        ◦ • gˆ _l( k ) = gˆ _s( k ) ∗ wˆ ( k ).                  (9.11)

×

±

×                                                      ×

In Fourier space, the spectrum of the sampled image will be convolved with the Fourier transform of the window function. Let us consider the example of the box window function in detail. If the window in the x space includes M N sampling points, its size is M∆ x₁ N∆ x₂. The Fourier transform of the 2-D box function is the 2-D sinc func- tion ( R5). The main peak of the sinc function has a half-width of 2π /(M∆ x₁) 2π /(N∆ x₂). A narrow peak in the spectrum of the im- age will become a 2-D sinc function. Generally, the resolution in the spectrum will be reduced to the order of the half-width of the sinc func- tion.

In summary, sampling leads to a limitation of the wave number, while the limitation of the image size determines the wave number resolution. Thus the scales in space and wave number domains are reciprocal to each other. The resolution in the space domain determines the size in the wave number domain, and vice versa.

9.3 Reconstruction from Samples†                                                                  239

 

a

1

 

0.8

0.6

0.4

0.2

 

0

 

 

 

 

 

x/DX

-1      -0.5       0       0.5       1

 

b

1

0.8

 

0.6

0.4

0.2

 

0

-0.2

 

~

k

-4        -2        0         2         4

 

Figure 9.4: a PSF and b transfer function of standard sampling.

 

 

Standard Sampling

The type of sampling discussed in Section 9.2.1 using the example of the ideal CCD camera is called standard sampling. Here the mean value of an elementary cell is assigned to a corresponding sampling point. It is a kind of regular sampling, since each point in the continuous space is equally weighted. We might be tempted to assume that standard sam- pling conforms to the sampling theorem. Unfortunately, this is not the

case (Fig. 9.4).  To the Nyq√ uist wave number, the Fourier transform of

the box function is still 1/ 2. The fi rst zero crossing occurs at double

the Nyquist wave number. Consequently, Moiré eff ects will be observed with CCDcameras. The eff ects are even more pronounced as only a small fraction — typically 20% of the chip area for interline transfer cameras

— are light sensitive [108].

Smoothing over larger areas with a box window is not of much help as the Fourier transform of the box window only decreases with k− 1 (Fig. 9.4). The ideal window function for sampling is identical to the ideal interpolation formula Eq. (9.15) discussed in Section 9.3, as its Fourier transform is a box function with the width of the elementary cell of the reciprocal grid. However, this windowing is impracticable. A detailed discussion of interpolation can be found in Section 10.6.

 

9.3 Reconstruction from Samples†

Perfect Reconstruction

The sampling theorem ensures the conditions under which we can re- construct a continuous function from sampled points, but we still do not know how to perform the reconstruction of the continuous image from its samples, i. e., the inverse operation to sampling.

Reconstruction is performed by a suitable interpolation of the sam- pled points. Generally, the interpolated points g_r ( x ) are calculated from

240                                                        9 Digitization, Sampling, Quantization

 

the sampled values g( r _{m, n}) weighted with suitable factors depending on the distance from the interpolated point:

 

.=     −

g_r ( x )           h( x  r _{m, n})g_s( r _{m, n}).                                  (9.12)

m, n

 

Using the integral properties of the δ function, we can substitute the sampled points on the right side by the continuous values:

∞

g_r ( x )  =  m., n ∫  h( x − x   )g( x   )δ ( r _{m, n} − x   )                 x

'      '                    ' d2  '

− ∞

.−                  −

= ∫

∞

h( x x ')   δ ( r _{m, n} x ')g( x ')d²x'.

− ∞                   m, n

The latter integral is a convolution of the weighting function h with the product of the image function g and the 2-D δ -comb. In Fourier space, convolution is replaced by complex multiplication and vice versa:

 

.=     −

gˆ _r ( k )    hˆ ( k )  gˆ ( k   r ˆ _{u, v}).                               (9.13)

u, v

The interpolated function cannot be equal to the original image if the periodically repeated image spectra are overlapping. This is nothing new; it is exactly what the sampling theorem states. The interpolated image function is only equal to the original image function if the weight- ing function is a box function with the width of the elementary cell of the reciprocal grid. Then the eff ects of the sampling — all replicated and shifted spectra — are eliminated and only the original band-limited spectrum remains, and Eq. (9.13) becomes:

gˆ _r ( k ) = Π (k₁∆ x₁/2π, k₂∆ x₂/2π )gˆ ( k ).                                  (9.14)

Then the interpolation function is the inverse Fourier transform of the box function

=

h( x )   sin π x₁/ ∆ x₁

π x₁/∆ x₁

sin π x₂/ ∆ x₂.                           (9.15)

π x₂/∆ x₂

Unfortunately, this function decreases only with 1/x towards zero. Therefore, a correct interpolation requires a large image area; mathe- matically, it must be infi nitely large. This condition can be weakened if we “overfi ll” the sampling theorem, i. e., ensure that gˆ ( k ) is already zero before we reach the Nyquist wave number. According to Eq. (9.13), we can then choose hˆ ( k ) arbitrarily in the region where gˆ vanishes. We can use this freedom to construct an interpolation function that decreases more quickly in the spatial domain, i. e., has a minimum-length inter- polation mask. We can also start from a given interpolation formula.

9.3 Reconstruction from Samples†                                                                  241

 

Then the deviation of its Fourier transform from a box function tells us to what extent structures will be distorted as a function of the wave number. Suitable interpolation functions will be discussed in detail in Section 10.6.

 

9.3.2 Multidimensional Sampling on Nonorthogonal Grids‡

So far, sampling has only been considered for rectangular 2-D grids. Here we will see that it can easily be extended to higher dimensions and nonorthogonal grids. Two extensions are required.

First, W -dimensional grid vectors must be defi ned using a set of W not neces- sarily orthogonal basis vectors b _w that span the W -dimensional space. Then a vector on the lattice is given by

r_n = [n₁ b ₁, n₂ b ₂,..., n_W b _W ]^T with n = [n₁, n₂,..., n_W ], n_w ∈ Z. (9.16)

In image sequences one of these coordinates is the time. Second, for some types of lattices, e. g., a triangular grid, more than one point is required. Thus for general regular lattices, P points per elementary cell must be considered. Each of the points of the elementary cell is identifi ed by an off set vector s _p.

Therefore an additional sum over all points in the elementary cell is required in the sampling integral, and Eq. (9.4) extends to

g_s( x ) = g( x )..δ ( x − r _n − s _p).                                       (9.17)

In this equation, the summation ranges have been omitted.

±

The extended sampling theorem directly results from the Fourier transform of Eq. (9.17). In this equation the continuous signal g( x ) is multiplied by the sum of delta combs. According to the convolution theorem (Theorem 4, p. 52), this results in a convolution of the Fourier transform of the signal and the sum of the delta combs in Fourier space. The Fourier transform of a delta comb is again a delta comb ( R5). As the convolution of a signal with a delta distribution simply replicates the function value at the zero point of the delta functions, the Fourier transform of the sampled signal is simply a sum of shifted copies of the Fourier transform of the signal:

gˆ _s( k, ν ) =..gˆ ( k − r ˆ _v ) exp(− 2π i k ^T s _p).                                   (9.18)

The phase factor exp( 2π i k ^T s _p) results from the shift of the points in the elementary cell by s _p according to the shift theorem (Theorem 3, p. 52). The vectors r ˆ _v

−

r ˆ _v = v₁ b ˆ 1 + v₂ b ˆ 2 +... + v_D b ˆ D  with  v_d ∈ Z                                   (9.19)

are the points of the reciprocal lattice. The fundamental translation vectors in the space and Fourier domain are related to each other by

d

b ^T b ˆ d' = δ _{d− d}'.                                                    (9.20)

This basically means that a fundamental translation vector in the Fourier do- main is perpendicular to all translation vectors in the spatial domain except

242                                                        9 Digitization, Sampling, Quantization

 

for the corresponding one. Furthermore, the magnitudes of the corresponding vectors are reciprocally related to each other, as their scalar product is one. In 3-Dspace, the fundamental translations of the reciprocial lattice can therefore be computed by

1

×

bT (b  × b )2              3

b ˆ d =   b d + 1 ×   b d + 2 .                                                  (9.21)

The indices in the preceding equation are computed modulo 3, and b ^T ( b ₂ b ₃) is the volume of the primitive elementary cell in the spatial domain. All these equations are familiar to solid state physicists or crystallographers [96]. Math- ematicians know the lattice in the Fourier domain as the dual base or reciprocal base of a vector space spanned by a nonorthogonal base. For an orthogonal base, all vectors of the dual base show into the same direction as the corre- sponding vectors and the magnitude is given by   b ˆ d  = 1/ | b _d|. Then often the length of the base vectors is denoted by ∆ x_d, and the length of the reciprocal

....

vectors by □ k_d = 1/∆ x_d. Thus an orthonormal base is dual to itself.

+

Reconstruction of the continuous signal is performed again by a suitable in- terpolation of the values at the sampled points. Now the interpolated values g_r ( x ) are calculated from the values sampled at r_n s _p, weighted with suitable factors that depend on the distance from the interpolated point:

g_r ( x ) =..g_s( r _n + s _p)h( x − r _n − s _p).                                     (9.22)

Using the integral property of the δ distributions, we can substitute the sampled points on the right-hand side by the continuous values and then interchange summation and integration:

 

∞

g_r ( x ) =.. ∫ g( x ')h( x − x ')δ ( r_n + s _p − x ')d^W x'

p n − ∞

∞

=  ∫  h( x − x ')..δ ( r _n + s _p − x ')g( x ')d^W x'.

− ∞                             p n

The latter integral is a convolution of the weighting function h with a function that is the sum of the product of the image function g with shifted δ combs. In Fourier space, convolution is replaced by complex multiplication and vice versa. If we further consider the shift theorem and that the Fourier transform of a δ comb is again a δ comb, we fi nally obtain

gˆ _r ( k ) = hˆ ( k )..gˆ ( k − r ˆ _v ) exp(− 2π i k ^T s _p).                                (9.23)

The interpolated signal gˆ _r can only be equal to the original signal gˆ if its period- ical repetitions are not overlapping. This is exactly what the sampling theorem states. The Fourier transform of the ideal interpolation function is a box func- tion which is one within the fi rst Brillouin zone and zero outside, eliminating all replications and leaving the original band-limited signal gˆ unchanged.

9.4 Quantization                                                                            243

 

Quantization

Equidistant Quantization

After digitization (Section 9.2), the pixels still show continuous gray val- ues. For use with a computer we must map them onto a limited number Q of discrete gray values:

[0, ∞ [ ^Q g₀, g₁,..., g_{Q− 1}}= G.

− → {

This process is called quantization, and we have already discussed some aspects thereof in Section 2.2.4. In this section, we discuss the errors related to quantization. Quantization always introduces errors, as the true value g is replaced by one of the quantization levels g_q. If the quantization levels are equally spaced with a distance ∆ g and if all gray values are equally probable, the variance introduced by the quantization is given by

g_q+∆ g/2

σ 2 = 1

∫ (g − g_q)2dg =  1 (∆ g)2.                          (9.24)

q      ∆ g

12

g_q− ∆ g/2

 

This equation shows how we select a quantization level. We take the level g_q for which the distance from the gray value g, |g − g_q|, is smaller than the neighboring quantization levels q_{k− 1} and q_k+1. The standard deviation σ _q is about 0.3 times the distance between the quantization levels ∆ g.

Quantization with unevenly spaced quantization levels is hard to re- alize in any image processing system. An easier way to yield unevenly spaced levels is to use equally spaced quantization but to transform the intensity signal before quantization with a nonlinear amplifi er, e. g., a logarithmic amplifi er. In case of a logarithmic amplifi er we would ob- tain levels whose widths increase proportionally with the gray value.

 

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

Поделиться: