Discrete image. Discretization image

Replace continuous image discrete can be performed different ways. You can, for example, choose any orthogonal function system and, calculate the image representation coefficients on this system (on this basis), replace the image. The diversity of bases makes it possible to form various discrete submissions of the continuous image. However, periodic discretization is most commonly used, in particular, as mentioned above, sampling with a rectangular raster. This method of discretization can be considered as one of the uses of an orthogonal basis that uses the shifted-features as its elements. Further, following, mostly, consider in detail the main features of rectangular sampling.

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

where - the vertical and horizontal steps or sampling intervals. Fig.1.1 illustrates the location of samples on the plane at rectangular sampling.

The main question that occurs when the continuous image is replaced by discrete, consists in determining the conditions under which such a replacement is full, i.e. Not accompanied by loss of information contained in a continuous signal. Losses are absent if, having discrete Signal, You can restore continuous. From a mathematical point of view, the question is thus lies in the restoration of the continuous signal in two-dimensional intervals between the nodes, in which its values \u200b\u200bare known or, in other words, in the implementation of two-dimensional interpolation. You can answer this question by analyzing the spectral properties of continuous and discrete images.

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

which responds a two-dimensional reverse continuous transformation Fourier:

The last ratio is true for any values, including in the nodes of the rectangular grille . Therefore, for the values \u200b\u200bof the signal in nodes, given (1.1), the relation (1.3) can be written as:

Denote for shorts through the rectangular area in the two-dimensional frequency domain. The calculation of the integral in (1.4) throughout the frequency domain can be replaced by integration in separate areas and summation of the results:

Performing the replacement of variables by rule, we achieve independence of the area of \u200b\u200bintegration from numbers and:

It is taken into account that For any integers and. This expression is very close to the Fourier reverse transformation. The difference consists only in the improper form of an exponential factor. To give it the necessary species, we introduce normalized frequencies and execute according to this replacement of variables. As a result, we get:

Now the expression (1.5) has the Fourier reverse transformation form, therefore, standing under the integral sign

(1.6)

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

(1.7)

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

Fig. 1.2. Frequency spectra of continuous and discrete images

The result of summation itself significantly depends on the values \u200b\u200bof these frequency shifts, or in other words, from the selection of sampling intervals. Suppose that the spectrum of a continuous image is differ from zero in some two-dimensional region in the vicinity of zero frequency, i.e. is described by a two-dimensional finite function. If at the same time the sampling intervals are chosen so that When,, the imposition of individual branches in the formation of the amount (1.7) will not happen. Consequently, within each rectangular section, only one term will differ from zero. In particular, when we have:

with ,. (1.8)

Thus, within the frequency domain, the spectra of continuous and discrete images with an accuracy of a constant multiplier coincide. In this case, the spectrum of the discrete image in this frequency domain contains full information About the spectrum of a continuous image. We emphasize that this coincidence takes place only under the agreed conditions defined by the successful choice of sampling intervals. Note that the implementation of these conditions according to (1.8) is achieved with sufficiently small values \u200b\u200bof the sampling intervals, which must meet the requirements:

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

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

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

Thus, the ideal interpolation restoration of the continuous image is performed using a two-dimensional filter with a rectangular frequency response (1.10). It is easy to record explicitly algorithm for restoring a continuous image. The two-dimensional pulse characteristics of the restoring filter, which is easy to obtain using the Fourier reverse transformation from (1.10), has the form:

.

The filtering product can be determined using a two-dimensional convection of the input image and this impulse characteristic. Representing the input image in the form of a two-dimensional sequence -function

after completing the convolution, we find:

The ratio obtained specifies the method of accurate interpolation recovery of a continuous image along a known sequence of its two-dimensional samples. According to this expression, two-dimensional functions of the species should be used to accurately recovery as interpolating functions. The ratio (1.11) is a two-dimensional version of the Kotelnikov-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 made is violated if at least one of these conditions is fulfilled. Real images rarely have spectra with pronounced boundary frequencies. One of the reasons leading to the unlimited spectrum is the limited image size. Because of this, when summing in (1.7), each of the zones show the action of the components of the adjacent spectral zones. In this case, the exact recovery of continuous image becomes at all impossible. In particular, does not lead to precise recovery and use of a filter with a rectangular frequency response.

A feature of the optimal recovery of the image in the intervals between the counts is the use of all samples of the discrete image, as prescribed by the procedure (1.11). It is not always convenient, it is often necessary to restore a signal in the local area, based on some small amount of discrete values. In these cases, it is advisable to apply a quasi-optimal recovery using various interpolating functions. Such a task arises, for example, when solving the problem of binding two images, when, due to the geometric absorption of these images, the available counts of one of them can correspond to some points that are between the nodes of the other. The solution to this task is discussed in more detail in the subsequent sections of this manual.

Fig. 1.3. Impact of the sampling interval for image recovery "Fingerprint"

Fig. 1.3 illustrates the effect of sampling intervals for image recovery. The original image, which is a fingerprint, is shown in Fig. 1.3, and, and one of the cross sections of its normalized spectrum - in Fig. 1.3, b. This image is discrete, and the value is used as a boundary frequency. As follows from fig. 1.3, B, the value of the spectrum at this frequency is negligible, which guarantees high-quality recovery. In essence, observed in Fig. 1.3.And the picture and is the result of restoring the continuous image, and the role of the reducing filter performs the visualization device - the monitor or printer. In this sense, the image of rice. 1.3.A may be considered continuous.

Fig. 1.3, B, g show the consequences from improper selection of sampling intervals. When they were received, "Discretization of a continuous" image of rice was carried out. 1.3.And by thinning its counts. Fig. 1.3, B corresponds to an increase in the sampling step for each coordinate of three, and Fig. 1.3, g - four times. It would be permissible if the boundary frequency values \u200b\u200bwere lower than the same number. In fact, as can be seen from fig. 1.3, B, there is violation of the requirements (1.9), especially rough during four-time thinning of the counts. Therefore, the images restored using an algorithm (1.11) are not only defocused, but also strongly distort the texture of the imprint.

Fig. 1.4. The impact of the sampling interval for the image recovery "Portrait"

In fig. 1.4 shows a similar series of results obtained for a portrait type image. The consequences of stronger thinning (four times in fig. 1.4.In and six times in fig. 1.4.g) manifest themselves mainly in loss of clarity. Subjectively loss of quality seems less significant than in Fig. 1.3. It finds its explanation in a significantly smaller spectrum width than the fingerprint image. The sampling of the original image corresponds to the boundary frequency. As can be seen from fig. 1.4.B, this value is much higher than the true meaning. Therefore, an increase in the sampling interval illustrated in Fig. 1.3, in, g, although it worsens the picture, still does not lead to such devastating consequences as in the previous example.

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

Discretization of images

Sampling - This is a conversion of a continuous signal into a sequence of numbers (samples), that is, the presentation of this signal according to any finite-dimensional basis. This view is in the design of the signal to this basis.

The most convenient to organize processing and the natural way of sampling is the representation of signals in the form of sampling their values \u200b\u200b(samples) in separate, regularly located points. This method is called rastrier, and the sequence of nodes in which the counts are taken - raster. The interval through which the continuous signal values \u200b\u200bare called sampling step. The reverse step is called sampling frequency,

A significant question arising during sampling: What frequency to take the signal counts in order to be the possibility of its reverse recovery on these references? Obviously, if you take the counts too rarely, then they will not contain information about the rapidly changing signal. The speed of the signal change is characterized by the upper frequency of its spectrum. Thus, the minimum allowable sampling interval width is associated with the highest frequency of the signal spectrum (inversely proportional to it).

For the case of uniform sampling is valid theorem Kotelnikov, published in 1933 in the work "about bandwidth Ether and wire in telecommunication. " It reads: if a continuous signal has a spectrum bounded by the frequency, then it can be completely and uniquely restored by its discrete references taken with a period, i.e. With frequency.

Signal recovery is carried out using a function. . Kotelnikov It was proved that a continuous signal that satisfies the above criteria can be represented as a series:

.

This theorem is also also called the counting theorem. The function is called back countdown or kotelnikovAlthough the interpolation series of this species studied still Whitaker in 1915. The reading function has an infinite length of time and reaches the greatest value equal to one, at a point, with respect to which it is symmetric.

Each of these functions can be viewed as a response of the perfect filter low frequency (FNH) on delta-impulse, which came at the time of time. Thus, to restore the continuous signal from its discrete samples, they must be skipped through the corresponding FNF. It should be noted that such a filter is anegous and physically unrealized.

The reduced ratio means the ability to accurately restore signals with a limited spectrum on the sequence of their samples. Limited spectrum signals - These are signals, the Fourier spectrum is different from zero only within a limited area of \u200b\u200bthe definition area. Optical signals can be attributed to 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 the frequency of Nyquista. This limit frequency above which there should be no spectral components in the input signal.

Quantization of images

With digital image processing, the continuous dynamic range of brightness values \u200b\u200bis divided into a number of discrete levels. This procedure is called quantization. Its essence is to convert a continuous variable to a discrete variable that takes the final set of values. These values \u200b\u200bare called quantization levels. In general, the transformation is expressed by a stepped function (Fig. 1). If the image countdown intensity belongs to the interval (i.e., when ), the initial countdown is replaced by the quantization level, where – quantization thresholds. It assumes that the dynamic range of brightness values \u200b\u200bis limited and is equal.

Fig. 1. Function describing quantization

The main task is to determine the values \u200b\u200bof thresholds and quantization levels. The simplest way solutions to this task is to break dynamic range At the same intervals. However, such a decision is not the best. If the intensity values \u200b\u200bof most image samples 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 follows quantum more often, and in "light" less often. This will reduce quantization error.

In digital image processing systems, they seek to reduce the number of levels and quantization thresholds, since the amount of information required for encoding the image depends on their quantity. However, with a relatively small number of levels on a quantized image, false contours may appear. They arise due to the jump-like change in the brightness of the trocked image and are especially noticeable on the gentle plots of its change. False contours significantly worsen the visual image quality, since the sight of a person is especially sensitive to contours. With uniform quantization of typical images, at least 64 levels are required.

Analog and discrete ways of presenting images and sound

The person is able to perceive and store information in the form of images (visual, sound, tactile, taste and olfactory). Visual images can be saved in the form of images (drawings, photos and so on), and sound - fixed on plates, magnetic tapes, laser disks and so on.

Information, including graphic and sound, can be represented in analog or discrete form. With analog representation, the physical value takes an infinite set of values, and its values \u200b\u200bchange continuously. With a discrete view, the physical value takes a finite set of values, and its value changes jumps like.

We give an example of an analog and discrete presentation of information. The position of the body on the inclined plane and on the staircase is set to the values \u200b\u200bof the coordinates X and Y. When the body moves along the inclined plane, its coordinate can take an infinite set of continuously changing values \u200b\u200bfrom a certain range, and when the stairs moves, only a certain set of values, and changing jump-like (rice . 1.6).

An example of an analog presentation of graphical information can serve, for example, a picturesque cloth, the color of which changes continuously, and the discrete - the image printed using inkjet printer and consisting of separate points of different colors. An example of analog storage sound information It is a vinyl record (the sound track changes its form continuously), and the discrete - audio component (which contains sections with different reflectivity).

Convert graphic and sound information from analog form to discrete is made by discretization, that is, partitioning a continuous graphic image and continuous (analog) sound signal on the separate elements. In the sampling process, coding is made, that is, the assignment to each element of a specific value in the form of code.

Sampling - This is a conversion of continuous images and sound in a set of discrete values \u200b\u200bin the form of codes.

Questions for reflection

1. Give examples of analog and discrete methods Representations of graphic and sound information.

2. What is the essence of the discretization process?

Analog and discrete image. Graphic information It can be represented in analog or discrete form. Example analog image A picturesque canvas can serve, the color of which changes continuously, and an example of a discrete image, printed using an inkjet printer. Figure, consisting of separate points of different colors. Analog (oil painting). Discrete.

Slide 11. From the presentation "Coding and processing of information". The size of the archive with a presentation of 445 Kb.

Informatics 9 class

Summary of other presentations

"Environmental structures" algorithms "- if the condition is then the action. What we know. The structure of the lesson. Branched algorithm. Perform the algorithm and fill in the table. The second round of the competition passes the student, who scored from 85 to 100 points inclusive. Enter the number of points and determine whether it went to the second round. Find the highest number between A and B. Make a program in programming language. A branching algorithm is an algorithm in which, depending on the condition, either one or another sequence of actions is performed.

"Creating an artificial intelligence" is a simulation approach. Approaches to building artificial intelligence systems. Evolutionary approach. Artificial Intelligence. It can cohabit with many people helping to cope with personal problems. Structural approach. Logical approach. Problems when developing. Prospects for development and scope.

"Cyclic programs" - a digit. Cycle with precondition. Find the amount. Cycle with postband. Cycle with parameter. Algorithm Euclida. Cyclic programs. Find the sum of natural numbers. Cycle concept. An initial fee. Tabulization function. Calculate. Example. Dividers. Computer science. Find the number of numbers. To find. Find the number of three-digit natural numbers. Three digits. Find a variety of function values. Dollars translation table.

"What is email" - the sender. E-mail address. History of email. The question of e-mail. Letter structure. Mail march. Letter. Email. Copy. Date. X-Mailer. Email. How does it work email.

"Work with email" - an email address. Mailbox. Email protocol. File sharing network. Address split. Advantages of email. Postal clients. Email inventor. Address. Email. Software to work with email. How e-mail works. Teleconference. Mail server. File sharing.

"Photoshop processing" - cool guys. How to distinguish fake. Raster and vector images. Introduction Top places. Program Adobe Photoshop.. Retouching. Contests for working with "Photoshop". Adjusting brightness. My friends. Practical part. Similar programs. Main part. Design. Unusual animals. Installation of multiple images.