Image discreteness. Image sampling

In the previous chapter we studied linear spatially invariant systems in a continuous two-dimensional domain. In practice, we are dealing with images that have limited dimensions and at the same time are measured in a discrete set of points. Therefore, the methods developed so far need to be adapted, extended and modified so that they can be applied in such an area. Several new points also arise that require careful consideration.

The sampling theorem tells us under what conditions a continuous image can be accurately reconstructed from a discrete set of values. We will also learn what happens when its applicability conditions are not met. All this has direct bearing on the development of visual systems.

Methods that require moving to the frequency domain have become popular in part due to algorithms for fast computation of the discrete Fourier transform. However, care must be taken because these methods assume the presence of a periodic signal. We will discuss how this requirement can be met and what the consequences of violating it are.

7.1. Image Size Limit

In practice, images always have finite dimensions. Consider a rectangular image with width and height H. Now there is no need to take integrals in the Fourier transform over infinite limits:

It is interesting that we do not need to know at all frequencies to restore function. Knowing that at represents a hard constraint. In other words, a function that is nonzero only in a limited region of the image plane contains much less information than a function that does not have this property.

To see this, imagine that the screen plane is covered with copies of a given image. In other words, we extend our image to a function that is periodic in both directions

Here is the largest integer not exceeding x. The Fourier transform of such a multiplied image has the form

Using appropriately selected convergence factors in Ex. 7.1 it is proved that

Hence,

from where we see that it is equal to zero everywhere except for a discrete set of frequencies. Thus, to find it, it is enough for us to know at these points. However, the function is obtained by simply cutting off the section for which . Therefore, in order to restore it, it is enough for us to know only for everyone This is a countable set of numbers.

Note that the transformation of a periodic function turns out to be discrete. The inverse transformation can be represented as a series, since

Another way to see this is to consider a function as a function obtained by truncating some function for which inside the window. In other words, where the window selection function is defined as follows.

Analog and discrete image. Graphic information can be presented in analog or discrete form. An example of an analogue image is a painting whose color changes continuously, and an example of a discrete image is a pattern printed using an inkjet printer, consisting of individual dots of different colors. Analog (oil painting). Discrete.

Slide 11 from the presentation "Encoding and processing of information".

The size of the archive with the presentation is 445 KB.

Computer Science 9th grade

summary of other presentations

“Branching structure algorithms” - IF condition, THEN action. What do we know? Lesson structure. Branching algorithm. Complete the algorithm and fill out the table. The student who scores from 85 to 100 points, inclusive, advances to the second round of the competition. Enter the number of points and determine whether he made it to the second round. Find the largest number between a and b. Write a program in a programming language. A branching algorithm is an algorithm in which, depending on the condition, either one or another sequence of actions is performed.

“Creation of artificial intelligence” - Simulation approach. Approaches to building artificial intelligence systems. Evolutionary approach. Artificial intelligence. Can cohabit with many people, helping to cope with personal problems. Structural approach. Logical approach. Problems during development. Development prospects and areas of application.

“What is email” - Sender. E-mail address. Email history. The question of the appearance of e-mail. Letter structure. Mail routing. Letter. Email. Copy. Date of. X-mailer. Email. How email works.

“Working with email” - Email address. Mailbox. Email protocol. File sharing network. Address separation. Benefits of email. Mail clients. Inventor of email. Address. Email. Software for working with email. How email works. Teleconference. Mail server. File sharing.

“Processing in Photoshop” - Cool guys. How to distinguish a fake. Raster and vector images. Introduction. Top places. Adobe Photoshop program. Retouching. Competitions on working with Photoshop. Brightness adjustment. My friends. Practical part. Similar programs. Main part. Design. Unusual animals. Montage of multiple images.

As a rule, signals enter the information processing system in a continuous form. For computer processing of continuous signals, it is necessary, first of all, to convert them into digital ones. To do this, sampling and quantization operations are performed.

Image sampling

Sampling– this is the transformation of a continuous signal into a sequence of numbers (samples), that is, the representation of this signal according to some finite-dimensional basis. This representation consists of projecting a signal onto a given basis.

The most convenient and natural way of sampling from the point of view of organizing processing is to represent signals in the form of a sample of their values ​​(samples) at separate, regularly spaced points. This method is called rasterization, and the sequence of nodes at which samples are taken is raster. The interval through which the values ​​of a continuous signal are taken is called sampling step. The reciprocal of the step is called sampling rate,

An essential question that arises during sampling: at what frequency should we take signal samples in order to be able to reconstruct it back from these samples? Obviously, if samples are taken too rarely, they will not contain information about a rapidly changing signal. The rate of change of a signal is characterized by the upper frequency of its spectrum. Thus, the minimum allowable width of the sampling interval is related to the highest frequency of the signal spectrum (inversely proportional to it).

For the case of uniform sampling, the following holds true: Kotelnikov's theorem, published in 1933 in the work “On the capacity of air and wire in telecommunications.” It says: if a continuous signal has a spectrum limited by frequency, then it can be completely and unambiguously reconstructed from its discrete samples taken with a period, i.e. with frequency.

Signal restoration is carried out using the function .

.

Kotelnikov proved that a continuous signal that satisfies the above criteria can be represented as a series: This theorem is also called the sampling theorem. The function is also called sampling function or Kotelnikov

, although an interpolation series of this type was studied by Whitaker in 1915. The sampling function has an infinite extension in time and reaches its greatest value, equal to unity, at the point about which it is symmetrical. Each of these functions can be considered as a response of an ideal low pass filter

(low-pass filter) to the delta pulse arriving at time . Thus, to restore a continuous signal from its discrete samples, they must be passed through an appropriate low-pass filter. It should be noted that such a filter is non-causal and physically unrealizable. The above ratio means the possibility of accurately reconstructing signals with a limited spectrum from the sequence of their samples. Limited Spectrum Signals – these are signals whose Fourier spectrum differs from zero only within a limited portion of the definition area. Optical signals can be classified as one of them, because The Fourier spectrum of images obtained in optical systems is limited due to the limited size of their elements. The frequency is called Nyquist frequency

. This is the limiting frequency above which there should be no spectral components in the input signal.

Image quantization In digital image processing, the continuous dynamic range of brightness values ​​is divided into a number of discrete levels. This procedure is called quantization . Its essence lies in the transformation of a continuous variable into a discrete variable that takes a finite set of values. These values ​​are called quantization levels . In general, the transformation is expressed by a step function (Fig. 1). If the intensity of the image sample belongs to the interval (i.e., when – ), then the original sample is replaced by the quantization level, where. It is assumed that the dynamic range of brightness values ​​is limited and equal to .

Rice. 1. Function describing quantization

The main task in this case is to determine the values ​​of thresholds and quantization levels. The simplest way to solve this problem is to divide the dynamic range into equal intervals. However, this solution is not the best. If the intensity values ​​of the majority of image counts are grouped, for example, in the “dark” region and the number of levels is limited, then it is advisable to quantize unevenly. In the “dark” region it is necessary to quantize more often, and in the “light” region less often. This will reduce the quantization error.

In digital image processing systems, they strive to reduce the number of quantization levels and thresholds, since the amount of information required to encode an image depends on their number. However, with a relatively small number of levels in the quantized image, false contours may appear. They arise as a result of an abrupt change in the brightness of the quantized image and are especially noticeable in flat areas of its change. False contours significantly degrade the visual quality of the image, since human vision is especially sensitive to contours. When uniformly quantizing typical images, at least 64 levels are required.

Replacing a continuous image with a discrete one can be done in various ways. You can, for example, choose any system of orthogonal functions and, having calculated the coefficients of image representation using this system (using this basis), replace the image with them. The variety of bases makes it possible to form various discrete representations of a continuous image. However, the most commonly used is periodic sampling, in particular, as mentioned above, sampling with a rectangular raster. This discretization method can be considered as one of the options for using an orthogonal basis that uses shifted -functions as its elements. Next, following mainly, we will consider in detail the main features of rectangular sampling.

Let be a continuous image, and let be the corresponding discrete one, obtained from the continuous one by rectangular sampling. This means that the relationship between them is determined by the expression:

where are the vertical and horizontal steps or sampling intervals, respectively. Figure 1.1 illustrates the location of samples on a plane with rectangular sampling.

The main question that arises when replacing a continuous image with a discrete one is to determine the conditions under which such a replacement is complete, i.e. is not accompanied by a loss of information contained in the continuous signal. There are no losses if, having a discrete signal, it is possible to restore a continuous one. From a mathematical point of view, the question is therefore to reconstruct a continuous signal in two-dimensional spaces between nodes in which its values ​​are known or, in other words, to perform two-dimensional interpolation. This question can be answered by analyzing the spectral properties of continuous and discrete images.

The two-dimensional continuous frequency spectrum of a continuous signal is determined by a two-dimensional direct Fourier transform:

which corresponds to the two-dimensional inverse continuous Fourier transform:

The last relation is true for any values, including at the nodes of a rectangular lattice . Therefore, for the signal values ​​at the nodes, taking into account (1.1), relation (1.3) can be written as:

For brevity, let us denote by a rectangular section in the two-dimensional frequency domain. The calculation of the integral in (1.4) over the entire frequency domain can be replaced by integration over individual sections and summation of the results:

By replacing variables according to the rule, we achieve independence of the integration domain from the numbers and:

It is taken into account here that for any integer values ​​and . This expression is very close in form to the inverse Fourier transform. The only difference is the incorrect form of the exponential factor. To give it the required form, we introduce normalized frequencies and perform a change of variables in accordance with this. As a result we get:

Now expression (1.5) has the form of an inverse Fourier transform, therefore, the function under the integral sign is

(1.6)

is a two-dimensional spectrum of a discrete image. In the plane of non-standardized frequencies, expression (1.6) has the form:

(1.7)

From (1.7) it follows that the two-dimensional spectrum of a discrete image is rectangularly periodic with periods and along the frequency axes and, respectively. The spectrum of a discrete image is formed as a result of the summation of an infinite number of spectra of a continuous image, differing from each other in frequency shifts and . Fig. 1.2 qualitatively shows the relationship between the two-dimensional spectra of continuous (Fig. 1.2.a) and discrete (Fig. 1.2.b) images.

Rice. 1.2. Frequency spectra of continuous and discrete images

The summation result itself significantly depends on the values ​​of these frequency shifts, or, in other words, on the choice of sampling intervals. Let us assume that the spectrum of a continuous image is nonzero in some two-dimensional region in the vicinity of zero frequency, that is, it is described by a two-dimensional finite function. If the sampling intervals are chosen so that for , , then the overlap of individual branches when forming the sum (1.7) will not occur. Consequently, within each rectangular section only one term will differ from zero. In particular, when we have:

at , . (1.8)

Thus, within the frequency domain, the spectra of continuous and discrete images coincide up to a constant factor. In this case, the spectrum of a discrete image in this frequency region contains complete information about the spectrum of a continuous image. We emphasize that this coincidence occurs only under specified conditions, determined by a successful choice of sampling intervals. Note that the fulfillment of these conditions, according to (1.8), is achieved at sufficiently small values ​​of sampling intervals, which must satisfy the requirements:

in which are the boundary frequencies of the two-dimensional spectrum.

Relationship (1.8) determines the method of obtaining a continuous image from a discrete one. To do this, it is enough to perform two-dimensional filtering of a discrete image using a low-pass filter with a frequency response

The spectrum of the image at its output contains non-zero components only in the frequency domain and is equal, according to (1.8), to the spectrum of a continuous image. This means that the output image of an ideal low-pass filter is the same as .

Thus, ideal interpolation reconstruction of a continuous image is performed using a two-dimensional filter with a rectangular frequency response (1.10). It is not difficult to explicitly write down an algorithm for reconstructing a continuous image. The two-dimensional impulse response of the reconstruction filter, which can be easily obtained using the inverse Fourier transform from (1.10), has the form:

.

The filter product can be determined using a two-dimensional convolution of the input image and a given impulse response. Representing the input image as a two-dimensional sequence of -functions

after performing the convolution we find:

The resulting relationship indicates a method for accurate interpolation reconstruction of a continuous image from a known sequence of its two-dimensional samples. According to this expression, for accurate reconstruction, two-dimensional functions of the form should be used as interpolating functions. Relation (1.11) is a two-dimensional version of the Kotelnikov-Nyquist theorem.

Let us emphasize once again that these results are valid if the two-dimensional spectrum of the signal is finite and the sampling intervals are sufficiently small. The fairness of the conclusions drawn is violated if at least one of these conditions is not met. Real images rarely have spectra with pronounced cutoff frequencies. One of the reasons leading to the unlimited spectrum is the limited image size. Because of this, when summing in (1.7), the action of terms from neighboring spectral zones appears in each of the zones. In this case, accurate restoration of a continuous image becomes completely impossible. In particular, the use of a filter with a rectangular frequency response does not lead to accurate reconstruction.

A feature of optimal image restoration in the intervals between samples is the use of all samples of a discrete image, as prescribed by procedure (1.11). This is not always convenient; it is often necessary to reconstruct a signal in a local area, relying on a small number of available discrete values. In these cases, it is advisable to use quasi-optimal reconstruction using various interpolating functions. This kind of problem arises, for example, when solving the problem of linking two images, when, due to the geometric detuning of these images, the available readings of one of them may correspond to some points located in the spaces between the nodes of the other. The solution to this problem is discussed in more detail in subsequent sections of this manual.

Rice. 1.3. The influence of sampling interval on image reconstruction "Fingerprint"

Rice. Figure 1.3 illustrates the effect of sampling intervals on image restoration. The original image, which is a fingerprint, is shown in Fig. 1.3, a, and one of the sections of its normalized spectrum is in Fig. 1.3, b. This image is discrete, and the value is used as the cutoff frequency. As follows from Fig. 1.3, b, the value of the spectrum at this frequency is negligible, which guarantees high-quality reconstruction. In fact, observed in Fig. 1.3.a the picture is the result of restoring a continuous image, and the role of a restoring filter is performed by a visualization device - a monitor or printer. In this sense, the image in Fig. 1.3.a can be considered continuous.

Rice. 1.3, c, d show the consequences of an incorrect choice of sampling intervals. When obtaining them, the “continuous” image was “sampled” in Fig. 1.3.a by thinning out its counts. Rice. 1.3,c corresponds to an increase in the sampling step for each coordinate by three, and Fig. 1.3, g - four times. This would be acceptable if the values ​​of the cutoff frequencies were lower by the same number of times. In fact, as can be seen from Fig. 1.3, b, there is a violation of requirements (1.9), especially severe when the samples are thinned out four times. Therefore, the images restored using algorithm (1.11) are not only defocused, but also greatly distort the texture of the print.

Rice. 1.4. The influence of the sampling interval on the reconstruction of the “Portrait” image

In Fig. 1.4 shows a similar series of results obtained for an image of the “portrait” type. The consequences of stronger thinning (four times in Fig. 1.4.c and six times in Fig. 1.4.d) are manifested mainly in loss of clarity. Subjectively, the quality loss seems less significant than in Fig. 1.3. This is explained by the significantly smaller spectral width than that of a fingerprint image. The sampling of the original image corresponds to the cutoff frequency. As can be seen from Fig. 1.4.b, this value is much higher than the true value. Therefore, the increase in the sampling interval, illustrated in Fig. 1.3, c, d, although it worsens the picture, still does not lead to such destructive consequences as in the previous example.

Consider a continuous image - a function of two spatial variables x 1 and x 2 f(x 1 , x 2) on a limited rectangular area (Figure 3.1).

Figure 3.1 – Transition from continuous to discrete image

Let us introduce the concept of sampling step Δ 1 with respect to the spatial variable x 1 and Δ 2 by variable x 2. For example, one can imagine that at points distant from each other by a distance Δ 1 along the axis x 1 there are point video sensors. If such video sensors are installed over the entire rectangular area, then the image will be defined on a two-dimensional lattice

To shorten the notation, we denote

Function f(n 1 , n 2) is a function of two discrete variables and is called a two-dimensional sequence. That is, sampling an image by spatial variables translates it into a table of sample values. The dimension of the table (number of rows and columns) is determined by the geometric dimensions of the original rectangular area and the choice of sampling step according to the formula

Where the square brackets [...] denote the integer part of the number.

If the domain of definition of a continuous image is a square L 1 = L 2 = L, and the sampling step is chosen to be the same along the axes x 1 and x 2 (Δ 1 = Δ 2 = Δ), then

and the table dimension is N 2 .

An element of the table obtained by sampling an image is called " pixel" or " Countdown". Consider a pixel f(n 1 , n 2). This number takes on continuous values. Computer memory can only store discrete numbers. Therefore, to record in memory a continuous value f must be subjected to analog-to-digital conversion with step D f(see Figure 3.2).

Figure 3.2 – Continuous quantity quantization

The operation of analog-to-digital conversion (sampling a continuous value by level) is often called In digital image processing, the continuous dynamic range of brightness values ​​is divided into a number of discrete levels. This procedure is called. The number of quantization levels, provided that the values ​​of the brightness function lie in the interval _____ _ ____ ___, is equal to

In practical image processing problems, the quantity Q varies widely from Q= 2 (“binary” or “black and white” images) up to Q= 210 or more (almost continuous brightness values). Most frequently selected Q= 28, in which an image pixel is encoded with one byte of digital data. From all of the above, we conclude that the pixels stored in the computer’s memory are the result of sampling the original continuous image by arguments (coordinates?) and by levels. (Where and how many, and everything is discrete) It is clear that the sampling steps Δ 1 , Δ 2 must be chosen small enough so that sampling error is negligible and the digital representation retains essential image information.

It should be remembered that the smaller the sampling and quantization step, the greater the amount of image data that must be recorded in the computer memory. As an illustration of this statement, consider an image on a slide measuring 50x50 mm, which is entered into memory using a digital optical density meter (microdensitometer). If, upon input, the linear resolution of the microdensitometer (sampling step for spatial variables) is 100 microns, then a two-dimensional array of pixels of dimension N 2 = 500×500 = 25∙10 4. If the step is reduced to 25 microns, then the dimensions of the array will increase 16 times and amount to N 2 = 2000×2000 = 4∙10 6. Using quantization at 256 levels, that is, encoding the found pixel by byte, we find that in the first case, 0.25 megabytes of memory are required for recording, and in the second case, 4 megabytes.