Analog and discrete ways of representing images and sound. Image Sampling Limiting Image Sizes

Replacing a continuous image with a discrete one can be done in various ways. It is possible, for example, to choose some system of orthogonal functions and, having calculated the image representation coefficients for this system (for 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, rectangular raster sampling. This discretization method can be considered as one of the options for using an orthogonal basis that uses shifted -functions as its elements. Further, following mainly, we will consider in detail the main features of rectangular discretization.

Let be a continuous image, and let be the corresponding discrete image, obtained from the continuous one by means of rectangular discretization. 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 readings on the plane with rectangular discretization.

The main question that arises when a continuous image is replaced by a discrete one is to determine the conditions under which such a replacement is complete, i.e. is not accompanied by the 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 issue is thus to reconstruct a continuous signal in two-dimensional gaps between nodes where 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 the two-dimensional direct Fourier transform:

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

The last relation is true for any values ​​of , 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, denote by a rectangular area 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 summing the results:

Performing the change of 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 in its form is very close to the inverse Fourier transform. The only difference is the wrong 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 the inverse Fourier transform, therefore, the function under the integral sign

(1.6)

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

(1.7)

It follows from (1.7) 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 summing an infinite number of spectra of a continuous image, which differ 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 result of the summation itself essentially 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 different from zero in some two-dimensional region in the vicinity of zero frequency, i.e., it is described by a two-dimensional finite function. If, in addition, the sampling intervals are chosen so that for , , then there will be no overlapping of individual branches in the formation of the sum (1.7). Consequently, within each rectangular section, only one term will differ from zero. In particular, for 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 domain contains complete information about the spectrum of a continuous image. We emphasize that this coincidence takes place only under specified conditions determined by a good choice of sampling intervals. Note that the fulfillment of these conditions, according to (1.8), is achieved for sufficiently small values ​​of sampling intervals , which must satisfy the requirements:

where are the boundary frequencies of the two-dimensional spectrum.

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

The spectrum of the image at its output contains nonzero components only in the frequency domain and, according to (1.8), is equal to the spectrum of the continuous image . This means that the output image of an ideal filter low frequencies matches with .

Thus, the ideal interpolation reconstruction of a continuous image is performed using a two-dimensional filter with a rectangular frequency response (1.10). It is easy to write down in an explicit form the algorithm for restoring a continuous image. 2D impulse response restoring filter, which is easy to obtain 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 convolution we find:

The resulting relation 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 exact restoration, two-dimensional functions of the form should be used as interpolating functions. Relation (1.11) is a two-dimensional version of the Kotel'nikov-Nyquist theorem.

We 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 validity 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 unboundedness of the spectrum is the limited size of the image. Because of this, summation in (1.7) in each of the bands shows the action of terms from neighboring spectral bands. In this case, the exact restoration of a continuous image becomes generally impossible. In particular, the use of a filter with a rectangular frequency response does not lead to accurate restoration.

A feature of optimal image reconstruction 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 required to restore the signal in the local area, based on a small number of available discrete values. In these cases, it is advisable to apply quasi-optimal recovery using various interpolating functions. This kind of problem arises, for example, when solving the problem of linking two images, when, due to the geometric mismatches of these images, the available readings of one of them can correspond to some points located in the gaps 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. Effect of Sampling Interval on Image Recovery "Fingerprint"

Rice. 1.3 illustrates the effect of sampling intervals on image recovery. The original image, which is a fingerprint, is shown in fig. 1.3, a, and one of the sections of its normalized spectrum is shown in Fig. 1.3, b. This image is discrete, and the value is used as the cutoff frequency. As follows from Fig. 1.3b, the value of the spectrum at this frequency is negligibly small, which guarantees high-quality reconstruction. In fact, as seen in Fig. 1.3.a, the picture is the result of restoring a continuous image, and the role of the 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 as continuous.

Rice. 1.3, c, d show the consequences of the wrong choice of sampling intervals. When they were obtained, “discretization of the continuous” image (Fig. 2) was carried out. 1.3.a by thinning its readings. Rice. 1.3, c corresponds to an increase in the sampling step for each coordinate by three, and fig. 1.3, d - 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, the requirements (1.9) are violated, especially rough when the samples are thinned four times. Therefore, the images reconstructed using algorithm (1.11) are not only defocused, but also strongly distort the texture of the imprint.

Rice. 1.4. Influence of the sampling interval on the restoration of the "Portrait" image

On fig. 1.4 shows a similar series of results obtained for an image of the "portrait" type. The consequences of a stronger thinning (four times in Fig. 1.4.c and six times in Fig. 1.4.d) appear mainly in the loss of clarity. Subjectively, the loss of quality seems to be less significant than in Fig. 1.3. This is explained by the much smaller spectrum width than that of a fingerprint image. The discretization 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 of . Therefore, the increase in the sampling interval, illustrated in Fig. 1.3, c, d, although it worsens the picture, it still does not lead to such devastating consequences as in the previous example.

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 counted 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 this area. There are also several new points that require careful consideration.

The sampling theorem says under what conditions a continuous image can be accurately restored from a discrete set of values. We will also learn what happens when the conditions for its applicability are not met. All this is directly related to the development of visual systems.

Techniques that require going to the frequency domain have become popular in part due to algorithms for fast calculation of the discrete Fourier transform. However, care must be taken as these methods assume the presence of a periodic signal. We will discuss how this requirement can be satisfied and the consequences of violating it.

7.1. Image Size Limit

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

Curiously, in order to restore the function, we do not need to know at all frequencies. Knowing what at is 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, let's imagine that the screen plane is covered with copies of a given image. In other words, we expand our image to a function that is periodic in both directions

Here, is the largest integer less than x. The Fourier transform of such a multiplied image has the form

With the help of suitably chosen convergence factors in ex. 7.1 it is proved that

Consequently,

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

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

Another way to see this is to consider a function as a function obtained by cutting off 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 represented in analog or discrete form. An example of an analog image is a painting, the color of which changes continuously, and an example of a discrete image, printed with inkjet printer dot pattern different color. Analog (oil painting). Discrete.

slide 11 from the presentation "Coding and processing of information". The size of the archive with the presentation is 445 KB.

Informatics Grade 9

summary of other presentations

"Branching structure algorithms" - IF condition, THEN action. What do we know. Lesson structure. Branching algorithm. Run the algorithm and fill in the table. A student who scores from 85 to 100 points inclusive passes to the second round of the competition. Enter the number of points and determine if he passed 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.

"Creating Artificial Intelligence" - Simulation Approach. Approaches to the construction of 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. Prospects for development and scope.

"Cyclic programs" - Digit. Loop with precondition. Find the amount. Loop with postcondition. Cycle with a parameter. Euclid's algorithm. Cyclic programs. Find the sum of natural numbers. The concept of a cycle. An initial fee. Function tabulation. Calculate. Example. Dividers. Informatics. Find the number of numbers. Find. Find the number of three-digit natural numbers. Three digit numbers. Find the set of function values. Dollar conversion table.

"What is e-mail" - Sender. E-mail address. Email history. The issue of e-mail. The structure of the letter. Mail routing. Letter. Email. Copy. The date. X mailer. Email. How does it work Email.

"Working with e-mail" - E-mail address. Mailbox. Email protocol. file sharing network. Separation of addresses. Benefits of email. Email clients. Email Inventor. Address. Email. Email software. 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. Program Adobe Photoshop. Retouching. Photoshop Contests. Brightness adjustment. My friends. Practical part. Similar programs. Main part. Design. Unusual animals. Multiple image montage.