85 VI. Image sampling For most image-formation systems, the output image5 (the optical image), can be completely described by a four-dimensional function n(x, y, t, l) that gives the mean quantum irradiance as a function of space (x, y), time (t) and wavelength (λ). This is usually a complete description because, in most situations, the image noise is that of an inhomogeneous Poisson process (which is completely determined by its mean or "intensity" function). All the image information available for performing a given visual task is carried in such four-dimensional functions. In biological vision systems, and in virtually all artificial (computer) vision systems, the images formed by the optical system must (because of hardware/wetware limitations) eventually be coded into a discrete representation in space, time, and wavelength. This image sampling process is a crucial step in visual processing that can, and often does, result in significant information loss. The loss results because it is often impossible to sample all four dimensions with sufficiently high resolution. Thus, compromises must always be struck. In the biological vision systems, the first stage of sampling is carried out by the photoreceptors, in artificial systems, usually by some other two-dimensional array of elements (e.g., a CCD array or an array of photodiodes). The principles of sampling are much the same in biological and artificial systems. A fundamental principle of sampling is captured by the so-called Wittaker-Shannon sampling theorem which is useful for understanding the information loss due to discrete sampling. A. The sampling theorem Below are statements of the Whittaker-Shannon sampling theorem for one and two dimensions. Similar statements hold for higher dimensions. The sampling theorem (one-dimensional case): If a one-dimensional function, f(x), is limited to frequencies below wc cycles per unit value of x, then the function can be completely reconstructed by taking 2wc evenly spaced samples per unit value of x. The sampling theorem (two-dimensional case): If a two-dimensional function, f(x, y), is limited to frequencies below uc cycles per unit value of x (in the x direction), and to frequencies below vc cycles per unit value of y (in the y direction), then the function can be completely reconstructed by taking 4ucvc samples per unit area on the x, y plane. In other words, what the sampling theorem says is that almost any smooth continuous function can be represented exactly, with perfect precision, by the values of the function 5 For example, there would be two images in a binocular optical system.86 at only at discrete set of points. This may seem rather surprising. It suggests that it is, in principle, possible to discretely sample an image without any loss of information. The minimum sampling rate required for perfect reconstruction (2wc for one dimensional functions and 4ucvc for two dimensional functions) is known as the Nyquist rate. It is not too difficult to demonstrate why the sampling theorem is true. Consider a one dimensional function f(x). To be concrete, think of x as representing time. A discretely sampled function can be described as the product of the original continuous function, and a sampling function, which is a collection of impulse (delta) functions. The locations of the impulse functions are the locations of the samples. For regularly spaced sampling, with spacing of 1 sec, the sampling function is a comb function, which is defined as follows: comb(x)=δ(x−i)i=−∞∞∑ (6.1) where δ(x) is the impulse (delta) function (which is an impulse located at 0). For regularly spaced sampling, with a spacing of 1/w sec, the sampling function is comb(wx)=δ(wx−i)i=−∞∞∑ (6.2) where w is the sampling rate in samples/sec. Thus, the discretely sampled version of f(x) is given by, ˆ f (x)=f(x)comb(wx) (6.3) Now consider the Fourier transform of the sampled function. Using the facts (a) that the Fourier transform of the product of two functions is the convolution of the Fourier transforms of the individual functions, (b) that the Fourier transform of a comb function is another comb function (see Figure 22), and (c) that convolution with the symmetrical comb function is equivalent to cross correlation, we have ˆ F (u)=F(u)⊗1wcomb(uw) (6.4) Figure 6.1 illustrates the implications of this result. The top line shows a Fourier transform of a hypothetical function, f(x). The assumption that f(x) is limited to frequencies less that wc is represented by the Fourier transform [F(u)] being zero beyond +/- wc Hz. The second line shows the Fourier transform of the sampling function when the sampling rate, w, equals 2wc; in this case, the spacing between impulses in the Fourier domain is 2wc. The rest of the lines in the figure illustrate the cross correlation of the functions in the first two lines.87 The cross correlation is carried out by moving the comb function to different positions (the position of the comb function is indicated by the X on one of the impulse functions), multiplying the comb function against the function in the top line [F(u)], integrating the product, and finally plotting the result at the location of the comb function. Because the spacing between the impulses is 2wc only one impulse function can fall under F(u) for a given position of the comb function. Thus, as the bottom line indicates, the cross correlation consists of an infinite string of replicas or copies of F(u) that just touch, but do not overlap. But, this implies that the original function f(x) can be exactly recovered from the sampled function by taking the Fourier transform of the sampled function, zeroing all frequencies outside of +/- W, and then inverse transforming. Therefore, a sampling rate of 2wc preserves all the information about the original function. Figure 6.1 Suppose that the sampling rate is greater than 2wc. Then the spacing between impulses in the second line of Figure 6.1 would be greater, and the replicas in the last line would be spaced further apart. Clearly, the original function could also be recovered in this case, although the extra samples are unnecessary. Suppose the sample rate is less than 2wc. Then the spacing between impulses in the second line of Figure 6.1 would be less than 2wc, and the replicas in the last line would overlap. Within the overlap regions the