Library

1 Digital sampling

In chapter 1 we already mentioned that when acquiring an image of a real scene it is discretized in two ways: sampling and quantization. Figure 1 shows sampling and quantization of a one-dimensional signal on a uniform grid1. The signal is sampled at ten positions (x = 0, ..., 9), and each sampled value is then quantized to one of seven levels (y = 0, ..., 6).

Figure 1- Sampling and quantization of a one-dimensional continuous signal

Sampling and quantization of images is done in exactly the same way, except that sampling is now done in more than one dimension. An example is shown in figure 2. Here, we see a continuous signal of two variables (top left), and the corresponding image with signal strength converted to grey values (bottom left). On the right, the signal is shown after sampling on a discrete grid and quantization of the grey values onto five levels.

Note: even though this is a book about image processing, we will often use examples taken from one-dimensional signal processing wherever this simplifies matters.

Figure 2 - Sampling and quantization of a two-dimensional image

By simply looking at figure 2, it is clear that the digital picture is not a very good representation of the original. Obviously the density of the sampling grid and the number of levels we choose in the quantization are important quality factors. These factors are called resolution: the spatial resolution equals the number of pixels used, and the intensity resolution equals the number of grey levels used. In digital images, both types of resolution are finite. The effect of lowering the spatial resolution can be seen in figure 3.

There is another kind of resolution called the optical resolution, which is the smallest spatial detail a visual system can see. Optical and spatial resolution are often used without their adjectives in texts, and what type of resolution is meant should be determined from the context.

Figure 3 - Effect of lowering the spatial resolution. From top to bottom and from left to right: original image with a resolution of 256 x 256 pixels, then resolutions 128 x 128; 64x 64; 32 x 32; 16 x 16; and 8 x 8.

2 The Nyquist frequency

If we sample an image, is it possible to make the image exactly the same as the original? And if so, how many samples are necessary? Before we can answer these questions, we need the concept of spatial frequency. The frequency of a sinusoid is defined as the number of cycles it makes per unit length. For example, the family of functions f(x) =sin(ax) has frequency a/2П . Figure 3.4 shows three sinusoids of different frequency and the corresponding image. There is a relationship between spatial frequency and the level of detail in images: a high level of detail corresponds to a high frequency, and a lack of details corresponds to low frequencies. A high level of detail is made up of relatively large contrast, i.e., the image intensity cycles fast from dark to light and vice versa, just like a high frequency sinusoid does. This relationship between frequency and image detail is at the heart of many image processing applications and will be explored further in the chapter on the Fourier transform.

Figure 4 - Example of three different spatial frequencies

We already noted that, in a digital image, the spatial and intensity resolution are finite. Hence the finest detail that can be represented is limited, and the range of spatial frequencies occurring in the image is also limited. This implies that the number of samples we must take of an image in order to exactly reproduce all the details is also finite.

This observation is linked to spatial frequency by the sampling theorem: “To capture the highest frequencies (i.e., the smallest details) of a continuous image, the sampling rate must be or faster, where equals the highest frequency occurring in the original image. Is called the Nyquist frequency.”

Note: many books use “band” terms when discussing frequencies. If the frequency has a limited range, it is called bandlimited. The range of frequency values itself is called the bandwidth.

If we sample an image below the Nyquist frequency, details will be lost. Oversampling, on the other hand, will not increase the level of detail: all of the details are already captured when sampling exactly at the Nyquist frequency.

Example: consider the following line taken from an image:

Figure 5 - The line taken from the image

The pattern has a frequency of 1/2 per pixel –i.e., there are 2 in a pattern cycle–so the Nyquist frequency is
2* 1/2 =1 per pixel. In the above, we have sampled the image line with this frequency, and, obviously, the result equals the original. If we lower the sampling frequency to 4/5 per pixel –i.e., 4 samples in 5 pixels– details are lost:

Figure 6 - Sampling the line taken from the image

Если уменьшить частоту дискретизации до 1/3 за пиксель, то полученный образ будут иметь детали отсутствовавшие в подлинном изображении:

Figure 7 - Distortion the line taken from the image

3 Aliasing

The phenomenon occurring at the end of the example above is called aliasing: if we sample an image at a rate that is below half the Nyquist frequency, high frequency patterns in the original are translated to lower frequency patterns that are absent in the original image. In the example above, we see that a pattern with frequency 1/2 per pixel is mapped to a pattern with frequency 1/6 per pixel.

Example: figure 8 shows another example of aliasing.

Figure 8 - Example of aliasing. The same two-dimensional function was sampled four times: using 400x400 points (top left), 100x100 points (top right), 50x50 points (bottom left), and 25x25 points (bottom right)

We sampled the function f(x; y) = on the domain в области which has decreasing frequency as we move from the top to the bottom line: frequency 25 per line on the top line, and frequency 1 per line on the bottom line. The function was sampled four times using different sampling frequencies. The aliasing effect at the lowest sampling frequency is so strong, that the high image frequencies at the top of the image get mapped to the same frequencies as the low ones at the bottom of the image.

4 Sampling and convolution

Until now we have assumed that we can sample an image with infinite precision. In practice this is an impossibility, since practical imaging devices cannot have an infinite precision. For example: if we use a camera to take samples of some infinitely small image location (x,y)y), then the camera will gather its sample in a small neighborhood around (x,y). There is in fact another reason why sampling with infinite precision is impossible: cameras need the energy from incoming light rays to detect these rays.

Even if it were possible to point the camera with infinite precision at only the infinitely small point ((x,y), the energy of the incoming light rays would be reduced to zero, and we would detect nothing. There is a tradeoff here: on the one hand we would like our sampling to be as precise as possible, so a small sampling area, but on the other hand the sampling area cannot be too small, or it will not give off enough energy for proper detection.

Library

Source: "http://www.ii.metu.edu.tr/~ion528/demo/lectures/6/2/index.html" Digital image acquisition (sampling, quantization, color models)