• Transition from continuous signals and transformations to discrete ones. Analog and discrete image

    Analog and discrete image. Graphic information can be represented in analog or discrete form. An example of an analogue image would be a painting whose color changes continuously, and an example of a discrete image printed using inkjet printer a pattern 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.

    “Cyclic programs” - Digital. Loop with precondition. Find the amount. Loop with postcondition. Loop with a parameter. Euclid's algorithm. Cyclic programs. Find the sum of natural numbers. The concept of a cycle. Down payment. 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 email” - Sender. Email address. Email history. The question of the appearance of e-mail. Letter structure. Mail routing. Letter. Email. Copy. Date. X-mailer. E-mail. How it works e-mail.

    “Working with email” - Email address. Mailbox. Email protocol. File sharing network. Address separation. The benefits of email. Mail clients. Inventor of email. Address. E-mail. 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. Prize places. Adobe program Photoshop. Retouching. Competitions on working with Photoshop. Brightness adjustment. My friends. Practical part. Similar programs. Main part. Design. Unusual animals. Montage of multiple images.

    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 fast calculation algorithms discrete transform Fourier. However, care must be taken as these methods require the presence of 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:

    Interestingly, 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 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

    By using in a suitable manner 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

    Image sampling.

    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 remote friend from each other at 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 square brackets[…] stand for the integer part of a 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 quantization. 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 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 digital meter optical density (microdensitometer). If, when entering, the linear resolution of the microdensitometer (sampling step for spatial variables) is 100 microns, then the two-dimensional array pixel 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.

    Images consisting of discrete elements, each of which can take only a finite number of distinguishable values ​​that change over a finite time, are called discrete. It should be emphasized that the elements of a discrete image, generally speaking, may have an unequal area and each of them may have an unequal number of distinguishable gradations.

    As was shown in the first chapter, the retina transmits discrete images to the higher parts of the visual analyzer.

    Their apparent continuity is just one of the illusions of vision. This “quantization” of initially continuous images is not determined by the limitations associated with resolution optical system eyes and not even the morphological structural elements of the visual system, but the functional organization of nerve networks.

    The image is divided into discrete elements by receptive fields that unite one or another number of photoreceptors. Receptive fields produce the primary selection of useful light signal by spatial and temporal summation.

    The central part of the retina (fovea) is occupied only by cones; in the periphery outside the fovea there are both cones and rods. Under night vision conditions, the cone fields in the central part of the retina have approximately the same size (about 5" in angular measure). The number of such fields in the fovea, whose angular dimensions are about 90", is about 200. The main role in night vision is played by the rod fields, which occupy the entire remaining surface of the retina. They have an angular size of about 1° over the entire surface of the retina. The number of such fields in the retina is about 3 thousand. Not only detection, but also viewing of dimly lit objects under these conditions is carried out by the peripheral areas of the retina.

    As illumination increases, another system of storage cells—the cone receptive fields—begins to play a major role. In the fovea, an increase in illumination causes a gradual decrease in the effective field strength until, at a brightness of about 100 asb, it is reduced to one cone. At the periphery, with increasing illumination, the rod fields gradually turn off (inhibit) and the cone fields come into action. The cone fields in the periphery, like the foveal fields, have the ability to decrease depending on the light energy incident on them. Largest quantity cones, which cone receptive fields can have with increasing illumination, grows from the center to the edges of the retina and at an angular distance of 50-60° from the center reaches approximately 90.

    It can be calculated that in good daylight conditions the number of receptive fields reaches about 800 thousand. This value approximately corresponds to the number of fibers in the human optic nerve. Discrimination (resolution) of objects during daytime vision is carried out mainly by the fovea, where the receptive field can be reduced to one cone, and the cones themselves are most densely located.

    If the number of storage cells of the retina can be determined to a satisfactory approximation, then there is not yet sufficient data to determine the number of possible states of the receptive fields. Only some estimates can be made based on the study of differential thresholds of receptive fields. The threshold contrast in the foveal receptive fields in a certain operating illumination range is of the order of 1. In this case, the number of distinguishable gradations is small. Throughout the entire range of restructuring of the cone foveal receptive field, 8-9 gradations differ.

    The period of accumulation in the receptive field - the so-called critical duration - is determined on average by a value of about 0.1 second, but at high levels lighting may apparently be significantly reduced.

    In fact, the model describing the discrete structure transmitted images, should be even more difficult. One would have to take into account the relationship between receptive field sizes, thresholds and critical duration, as well as the statistical nature of visual thresholds. But for now there is no need for this. It is enough to imagine as an image model a set of elements of equal area, the angular dimensions of which are smaller than the angular dimensions of the smallest detail resolved by the eye, the number of distinguishable states of which is greater than the maximum number of distinguishable gradations of brightness, and the time of discrete change of which is less than the flickering period at the critical flicker fusion frequency.

    If you replace images of real continuous objects in the external world with such discrete images, the eye will not notice the substitution.* Consequently, discrete images of this kind contain at least no less information than the visual system perceives. **

    * Color and volume images can also be replaced with a discrete model.
    ** The problem of replacing continuous images with discrete ones is important for film and television technology. Time quantization is the basis of this technique. In pulse-code television systems, the image is also divided into discrete elements and quantized by brightness.

    Digital photography or other raster image is an array of numbers recorded by brightness level sensors in a two-dimensional plane. Knowing that, from a mathematical point of view, a thin lens performs a Fourier transform of images placed in focal planes, it is possible to create image processing algorithms that are analogous to image processing by a classical optical system.

    The formula for such algorithms will look like this:

    1. Z=FFT(X) – direct two-dimensional Fourier transform
    2. Z′=T(Z) – application of a function or transparency to the Fourier transform of an image
    3. Y=BFT(Z′) – inverse two-dimensional Fourier transform
    To calculate Fourier transforms, fast discrete Fourier transform algorithms are used. Although the optical system of lenses carries out the Fourier transform on the continuous range of the argument and for the continuous spectrum, but when moving to digital processing data, the Fourier transform formulas can be replaced by the discrete Fourier transform formulas.

    Implementation examples

    • Image Blur Algorithm
    The implemented algorithms are part of an open source library source code FFTTools. Internet address: github.com/dprotopopov/FFTTools

    Image Blur Algorithm

    In optical systems, the diaphragm, located in the focal plane, is a simple hole in the screen. As a result of passing luminous flux through the diaphragm, high frequency waves (shorter wavelengths) pass through the obstacle, and the waves low frequencies(with longer wavelengths) are cut off by the screen. This increases the sharpness of the resulting image. If you replace a hole in the screen with an obstacle in the screen, the result will be blurry image, since it will be formed from frequencies of long wavelengths.

    Algorithm:

    1. Calculate the array Z′=T(Z), where T is the zeroing of the rows and columns located in the given internal areas of the argument matrix corresponding to high 5. frequencies (that is, the zeroing of the Fourier expansion coefficients corresponding high frequencies)

    Image sharpening algorithm

    In optical systems, the diaphragm, located in the focal plane, is a simple hole in the screen. As a result of the passage of light through the diaphragm, high-frequency waves (with shorter wavelengths) pass through the obstacle, and low-frequency waves (with longer wavelengths) are cut off by the screen. This increases the sharpness of the resulting image.

    Algorithm:

    1. Let X(N1,N2) be an array of image pixel brightnesses.
    2. Calculate Px = average (rms) brightness of pixels in array X
    3. Calculate array Z=FT(X) – direct two-dimensional discrete Fourier transform
    4. Save the value L=Z(0,0) – corresponding to the average brightness of the pixels of the original image
    5. Calculate the array Z′=T(Z), where T is the zeroing of rows and columns located in the given external areas of the argument matrix, corresponding to low 6. frequencies (that is, zeroing of the Fourier expansion coefficients corresponding to low frequencies)
    6. Restore the value Z’(0,0)=L – corresponding to the average brightness of the pixels of the original image
    7. Calculate array Y=RFT(Z′) – inverse two-dimensional discrete Fourier transform
    8. Calculate Py = average (rms) brightness of pixels in array Y
    9. Normalize the array Y(N1,N2) by the average brightness level Px/Py

    Image scaling algorithm

    In optical systems, the luminous flux in the focal plane of the system is a Fourier transform of the original image. The size of the image obtained at the output of the optical system is determined by the ratio of the focal lengths of the lens and eyepiece.

    Algorithm:

    1. Let X(N1,N2) be an array of image pixel brightnesses.
    2. Calculate Px = average (rms) brightness of pixels in array X
    3. Calculate array Z=FT(X) – direct two-dimensional discrete Fourier transform
    4. Calculate the array Z′=T(Z), where T is either adding zero rows and columns of the matrix corresponding to high frequencies, or removing rows and columns of the matrix corresponding to high frequencies to obtain the required size of the final image
    5. Calculate array Y=RFT(Z′) – inverse two-dimensional discrete Fourier transform
    6. Calculate Py = average (rms) brightness of pixels in array Y
    7. Normalize the array Y(M1,M2) by the average brightness level Px/Py
    Software used
    • Microsoft Visual Studio 2013 C# - environment and programming language
    • EmguCV/OpenCV – C++ library of structures and algorithms for image processing
    • FFTWSharp/FFTW – C++ library implementing fast discrete Fourier transform algorithms

    Image Blur Algorithm

    Algorithm code

    ///

    /// Clear internal region of array /// /// Array of values /// Internal blind region size private static void Blind(Complex[,] data, Size size) ( int n0 = data.GetLength(0); int n1 = data.GetLength(1); int n2 = data.GetLength(2); int s0 = Math. Max(0, (n0 - size.Height)/2); int s1 = Math.Max(0, (n1 - size.Width)/2); int e0 = Math.Min((n0 + size.Height)/ 2, n0); int e1 = Math.Min((n1 + size.Width)/2, n1);< e0; i++) { Array.Clear(data, i*n1*n2, n1*n2); } for (int i = 0; i < s0; i++) { Array.Clear(data, i*n1*n2 + s1*n2, (e1 - s1)*n2); } for (int i = e0; i < n0; i++) { Array.Clear(data, i*n1*n2 + s1*n2, (e1 - s1)*n2); } } /// /// Blur bitmap with the Fastest Fourier Transform /// /// Blured bitmap public Bitmap Blur(Bitmap bitmap) ( using (var image = new Image (bitmap)) ( int length = image.Data.Length; int n0 = image.Data.GetLength(0); int n1 = image.Data.GetLength(1); int n2 = image.Data.GetLength(2); var doubles = new double; Buffer.BlockCopy(image.Data, 0, doubles, 0, length*sizeof (double)); double power = Math.Sqrt(doubles.Average(x => x*x)); = new fftw_complexarray(doubles.Select(x => new Complex(x, 0)).ToArray()); var output = new fftw_complexarray(length); fftw_plan.dft_3d(n0, n1, n2, input, output, fftw_direction. Forward, fftw_flags.Estimate).Execute(); complex complex= output.GetData_Complex(); var data = new Complex; var buffer = new double; GCHandle complexHandle = GCHandle.Alloc(complex, GCHandleType.Pinned); GCHandle dataHandle = GCHandle.Alloc(data, GCHandleType.Pinned); IntPtr complexPtr = complexHandle.AddrOfPinnedObject(); IntPtr dataPtr = dataHandle.AddrOfPinnedObject(); Marshal.Copy(complexPtr, buffer, 0, buffer.Length); Marshal.Copy(buffer, 0, dataPtr, buffer.Length); Blind(data, _blinderSize); Marshal.Copy(dataPtr, buffer, 0, buffer.Length); Marshal.Copy(buffer, 0, complexPtr, buffer.Length); complexHandle.Free(); dataHandle.Free(); input.SetData(complex); fftw_plan.dft_3d(n0, n1, n2, input, output, fftw_direction.Backward, fftw_flags.Estimate).Execute(); double array2 = output.GetData_Complex().Select(x => x.Magnitude).ToArray(); double power2 = Math.Sqrt(array2.Average(x => x*x)); doubles = array2.Select(x =>

    Image sharpening algorithm

    Algorithm code

    ///

    /// Clear external region of array /// /// Array of values /// External blind region size private static void Blind(Complex[,] data, Size size) ( int n0 = data.GetLength(0); int n1 = data.GetLength(1); int n2 = data.GetLength(2); int s0 = Math. Max(0, (n0 - size.Height)/2); int s1 = Math.Max(0, (n1 - size.Width)/2); int e0 = Math.Min((n0 + size.Height)/ 2, n0); int e1 = Math.Min((n1 + size.Width)/2, n1);< s0; i++) { Array.Clear(data, i*n1*n2, s1*n2); Array.Clear(data, i*n1*n2 + e1*n2, (n1 - e1)*n2); } for (int i = e0; i < n0; i++) { Array.Clear(data, i*n1*n2, s1*n2); Array.Clear(data, i*n1*n2 + e1*n2, (n1 - e1)*n2); } } /// /// Sharp bitmap with the Fastest Fourier Transform /// /// sharp bitmap public Bitmap Sharp(Bitmap bitmap) ( using (var image = new Image (bitmap)) ( int length = image.Data.Length; int n0 = image.Data.GetLength(0); int n1 = image.Data.GetLength(1); int n2 = image.Data.GetLength(2); var doubles = new double; Buffer.BlockCopy(image.Data, 0, doubles, 0, length*sizeof (double)); double power = Math.Sqrt(doubles.Average(x => x*x)); = new fftw_complexarray(doubles.Select(x => new Complex(x, 0)).ToArray()); var output = new fftw_complexarray(length); fftw_plan.dft_3d(n0, n1, n2, input, output, fftw_direction. Forward, fftw_flags.Estimate).Execute(); Complex complex = output.GetData_Complex(); Complex level = complex; var buffer = new double; GCHandle.Alloc(complex, GCHandleType.Pinned) ; GCHandle dataHandle = GCHandle.Alloc(data, GCHandleType.Pinned); IntPtr complexPtr = complexHandle.AddrOfPinnedObject(); IntPtr dataPtr = dataHandle.AddrOfPinnedObject(); Copy(buffer, 0, dataPtr, buffer.Length); Blind(data, _blinderSize); Marshal.Copy(dataPtr, buffer, 0, buffer.Length); Marshal.Copy(buffer, 0, complexPtr, buffer.Length); complexHandle.Free(); dataHandle.Free(); complex = level; input.SetData(complex); fftw_plan.dft_3d(n0, n1, n2, input, output, fftw_direction.Backward, fftw_flags.Estimate).Execute(); double array2 = output.GetData_Complex().Select(x => x.Magnitude).ToArray(); double power2 = Math.Sqrt(array2.Average(x => x*x)); doubles = array2.Select(x => x*power/power2).ToArray(); Buffer.BlockCopy(doubles, 0, image.Data, 0, length*sizeof (double)); return image.Bitmap; ) )

    Image scaling algorithm

    Algorithm code

    ///

    /// Copy arrays /// /// Input array /// Output array private static void Copy(Complex[,] input, Complex[,] output) ( int n0 = input.GetLength(0); int n1 = input.GetLength(1); int n2 = input.GetLength(2); int m0 = output.GetLength(0); int m1 = output.GetLength(1); int ex0 = Math.Min(n0, m0)/2; , m1)/2; int ex2 = Math.Min(n2, m2); Debug.Assert(n2 == m2);< ex2; k++) { for (int i = 0; i <= ex0; i++) { for (int j = 0; j <= ex1; j++) { int ni = n0 - i - 1; int nj = n1 - j - 1; int mi = m0 - i - 1; int mj = m1 - j - 1; output = input; output = input; output = input; output = input; } } } } /// /// Resize bitmap with the Fastest Fourier Transform /// /// Resized bitmap public Bitmap Stretch(Bitmap bitmap) ( using (var image = new Image (bitmap)) ( int length = image.Data.Length; int n0 = image.Data.GetLength(0); int n1 = image.Data.GetLength(1); int n2 = image.Data.GetLength(2); var doubles = new double; Buffer.BlockCopy(image.Data, 0, doubles, 0, length*sizeof (double)); double power = Math.Sqrt(doubles.Average(x => x*x)); = new fftw_complexarray(doubles.Select(x => new Complex(x, 0)).ToArray()); var output = new fftw_complexarray(length); fftw_plan.dft_3d(n0, n1, n2, input, output, fftw_direction. Forward, fftw_flags.Estimate).Execute(); complex complex = output.GetData_Complex(); using (var image2 = new Image (_newSize)) ( int length2 = image2.Data.Length; int m0 ​​= image2.Data.GetLength(0); int m1 = image2.Data.GetLength(1); int m2 = image2.Data.GetLength(2); var complex2 = new Complex; var data2 = new double; GCHandle complexHandle = GCHandle.Alloc(complex, GCHandleType.Pinned); ); IntPtr complexPtr = complexHandle.AddrOfPinnedObject(); IntPtr dataPtr = dataHandle.AddrOfPinnedObject(); Marshal.Copy(complexPtr, buffer, 0, buffer.Length); complexHandle.Free(); Copy(data, data2); complexHandle = GCHandle.Alloc(complex2, GCHandleType. Pinned); complexPtr = complexHandle.AddrOfPinnedObject(); dataPtr = dataHandle.AddrOfPinnedObject(); Marshal.Copy(dataPtr, buffer, 0, buffer.Length); complexHandle.Free(); dataHandle.Free(); var input2 = new fftw_complexarray(complex2); var output2 = new fftw_complexarray(length2); fftw_plan.dft_3d(m0, m1, m2, input2, output2, fftw_direction.Backward, fftw_flags.Estimate).Execute(); double array2 = output2.GetData_Complex().Select(x => x.Magnitude).ToArray(); double power2 = Math.Sqrt(array2.Average(x => x*x)); double doubles2 = array2.Select(x => x*power/power2).ToArray(); Buffer.BlockCopy(doubles2, 0, image2.Data, 0, length2*sizeof (double)); return image2.Bitmap; ) ) )

    Read more: