# Image compression method

FIELD: information technology.

SUBSTANCE: image compression method, based on excluding a certain portion of information, wherein the information is excluded from the space domain through numerical solution of Poisson or Laplace differential equations, and subsequent estimation of the difference between the obtained solution and actual values at discrete points of the image; generating an array of boundary conditions, which includes a considerable number of equal elements which is compressed, and the image is reconstructed by solving Poisson or Laplace partial differential equations using the array of boundary conditions.

EFFECT: eliminating loss of image integrity, high efficiency of compressing images having large areas of the same tone or gradient and maintaining contrast of boundaries between different objects of an image.

2 cl, 16 dwg

The invention relates to the field of digital signal processing and can be used for compression of static and dynamic images, that is, transform the data in order to reduce their volume as lossless and lossy pieces of information.

In today's world there is mushrooming of media content, therefore, data compression is an important direction of research.

Known methods of lossless data compression based on the use of statistical information (repetition, autocorrelation), and lossy compression, based on removing excess material or non-critical) information (D. Vatolin, Ratushnyak A., Smirnov, M., Jukin Century Methods of data compression. M: Dialog - MIFI, 2003; Salomon D. data Compression, image and sound. M: TECHNOSPHERE, 2004). Apply these methods separately and in various combinations. Lossless compression is applied to two-level (one-bit), multi-level and full-color images. The most common implementation of algorithms-oriented bitmap compression, lossless (GIF S.Blackstock. LZW and GIF explained. http://www.martinreddy.net/gfx/2d/GIF-comp.txt) (static and dynamic images) and PNG (PNG home page. http://www.libpng.org/pub/png/png.html). In data-driven methods are dictionary based encoding modification conversion Huff is Ana and LZ77, LZ78 (LZW - Lempel, Ziv, Welch).

Known fractal compression method of images, based on the fact that the image can be represented more compactly by using coefficients iterative functions (D.Saupe, R.Hamzaoui, H.Hartenstein. Fractal image compression - An introductory overview, in: Fractal Models for Image Synthesis, Compression, and Analysis, D.Saupe, J.Hart (eds.), ACM SIGGRAPH'96 Course Notes).

Known methods, in which the image using the "brush fire" (forest fire), form the skeleton of the polygon thickness of 1-2 pixels, which is the Voronoi diagram. To difficulties in the practical implementation of such methods include: the correct formation of the skeleton in the form of a coherent graph (Skien C. Algorithms. Design guide. - 2nd ed. TRANS. from English. - SPb.: BHV-Petersburg, 2011).

Known interpolation method for compressing a television signal (RF patent No. 2131172, the priority date of 10.12.1996, IPC H04N 5/335, published 27.05.1999 g), which is based on artificial exclusion of fragments of signal lines and restore using interpolation in fragments is not excluded parts of rows that will reduce the redundancy of a television signal.

There is a method of lossy compression based on discrete cosine transform (DCT), which is designed for static and dynamic images, which is the closest to the essential features of the claimed ability is Boo and adopted as a prototype (Steven Smith. Digital signal processing. A practical guide for engineers and scientists. TRANS. from English. Of ya, A., Vityazeva SV, Gusinsky I.S.): Dodeca-XXI, 2011, str). In this way a common format JPEG uses compression discrete cosine transform (DCT), followed by the modified conversion Huffman. The basis of JPEG compression is the spatial spectrum of the image with subsequent exclusion of some part of the spectral components, allowing subsequently to restore an image of sufficient quality. The spectrum of the image due to the fact that it may contain a significant number of duplicate individual items and chains, effectively compress.

When JPEG compression spatial spectrum is obtained by two-dimensional DCT matrix image U of size M×N in accordance with the expression:

where 0≤p≤M-1, 0≤q≤N-1;

The value of B_{pq}called DCT matrix U.

The inverse DCT is implemented with the under expression:

where 0≤m≤M-1, 0≤n≤N-1;

In the implementation of the algorithm of JPEG compression original image after conversion from the color space RGB to YCrCb is divided into square blocks of size 8×8 or less 16×16, which is DCT. The coefficients of the discrete cosine transformation is filtered to remove some (depending on the compression ratio) values, cancerous, and then encoded using a modified conversion Huffman. As a result of these transformations is obtained dataset is considerably smaller than the original image containing information by which you can restore the original image with some, depending on the degree of compression accuracy. The recovery image is in reverse order: first compressed image is subjected to inverse modified conversion Huffman, then the inverse DCT. The disadvantage of JPEG compression on the OS is ove DCT is the loss of integrity of the image, the resulting specific artifacts "blocking" (contrast highlighting regions of 8×8 or 16×16) in the restored image. Artifact "blocking" is a consequence of the lack of "smooth blending" of the areas highlighted for DCT. The next disadvantage is the loss of contrast that is manifested in the "blur" the boundaries between different objects of the image and is the result of filtering (removal of the compression of high-frequency components. Artifact "blur" for example in photographic images, but in some types of images, such as satellite images, the images for printing, where you want to save the contrast, blur is unacceptable. When lossless compression in JPEG format you can save the contrast of the boundaries of objects, the size of the compressed image remains quite large, which is also a disadvantage. The JPEG format does not provide effective compressing images that contain large areas of single colors or a smooth gradient.

The invention eliminates the loss of integrity of the image, increases the efficiency of compressing images that contain large areas of single colors or gradient colors, brightness), preserves the contrast of the boundaries between different objects of the image.

This problem is solved due to the fact that the images(static or dynamic) are considered as a discrete field structure, a complete numerical description of which (i.e. values at all discrete points in the coordinate space and / or time) can be determined by solving equations Laplace or Poisson, with initial data as a boundary (boundary) conditions.

The invention consists in that, when compressing an image (static or dynamic) is the determination of the dataset named in the framework of the invention "pattern", which is an array of boundary conditions and allowing with a given degree of accuracy by numerical solution of the equations of Laplace or Poisson, restore the original image. The resulting pattern contains some (in most cases quite significant) number of repetitive elements, and sequences that can effectively compress pattern by standard methods, for example based on the modification of the conversion Huffman, or LZ78, or arithmetic coding. When applied to the pattern formation and restore the image of the Poisson equation, to be determined function of the right side, the right selection which can significantly contribute to image compression.

The proposed method differs from the methods JPEG because it to compress the image is not used to obtain the spatial spectrum, and which is of boundary conditions for solutions of differential equations (Poisson or Laplace), allows you to restore the picture. This may be taken into account and spatial range, if for the pattern formation and restore the image chosen by the Poisson equation, and if the right side of the Poisson equation contains a function (or functional number), allowing to take into account the spatial spectrum. Thus, the proposed method allows for the preservation of a small number of low-frequency components to maintain small (high-frequency) part of the image by the pattern boundary conditions. Application of differential equations of the second order allows you to track changes changes (amplitude when moving from point to point (pixel to pixel), which describes the brightness, saturation, or other characteristic of the image depending on the selected color scheme) and to keep only those values, which changes the changes are significant, i.e. superior numerically specified value that determines the compression ratio. Thus, in contrast to JPEG-convert to compact and repair the image is not spatial spectrum of the image and its spatial "differential structure", i.e. the availability and the numerical value changes changes that can effectively compress the area gradation (color, brightness, etc) and in some cases, p is aizvaditi more efficient compression compared to JPEG.

Image (static or dynamic) is considered to be spatially indivisible, multi-dimensional field structure. In the case of a static image is two-dimensional (similar to the plane-parallel field), in the case of dynamic image - three-dimensional (similar three-dimensional field or plane-parallel fields, time-varying). Thus, the image can be described by partial differential equations.

For two-dimensional case:

- Laplace equation:

- Poisson's equation:

For the three-dimensional case (for dynamic images, video):

- Laplace equation:

- Poisson's equation:

where the following notation is used: x, y - prostranstvennye coordinates, t - third spatial coordinate or time, the U - value of the amplitude component of the selected color space of the image, f is the function that relates patterns of change in image with the change of spatial coordinates.

Image compression is solved the inverse problem to the solution of equations (3)-(6), that is, is the determination of the boundary conditions. Such an array of boundary conditions in the framework of the present invention is referred to as a pattern image or brief pattern. In the case of the choice of the Poisson equations is also subject to the determination of the function f. After the formation of the pattern to him may be applied the standard method of compression applied to data sets containing a large number of recurring characters, for example, based on the modification of the conversion Huffman, or LZ78, or arithmetic encoding.

Unzipping compressed image is the removal of the pattern (and the function f in the case of Poisson equations) from the archives (on the basis of the previously selected method of archiving), then the solution of equations of the Laplace or Poisson is based on the known boundary conditions, for example, the finite difference method.

The inventive method is illustrated in the drawings, which shows:

figure 1 - possible choices of templates derivation for two-dimensional (x,y) and three-dimensional (x,y,t) space, Breakfast is STV;

figure 2 - the original image is black and white with grayscale from 0 to 255, the length of the array image 152100 bytes. The image contains small and large spatial elements;

figure 3 - visualization of array boundary conditions named in the framework of the method "pattern", pattern contains 42639 elements boundary conditions (different from zero) and 109461 zeros;

figure 4 - the result of image reconstruction for 20 iterations, pattern (figure 3), without pedaltrain;

figure 5 is the result of image reconstruction for 20 iterations, pattern (figure 3), with the use of prefiltration;

6 is graphs of the sum of residuals for all points of the lattice, the nodes of which are the pixels of the image. On the vertical axis the amount of residuals in the horizontal iteration number. Displays graphs for the case of image reconstruction: using prefiltration; without the use of prefiltration. It is obvious that the use of prefiltration allows us to accelerate the convergence of the iteration process, i.e., the speed of image reconstruction;

Fig.7 - the original full color image 800×654, the number of bytes in a 24-bit palette - 1353600;

Fig pattern is obtained for the color palette RGB, the number of significant bytes - 307358, zeros - 1046242. The ratio of the number of significant elements (bytes) of the pattern to the volume of the original image (bytes): 0,2271;

Fig.9 - the restored image is agenie pattern (Fig), you should pay attention to the fact that despite a significant reduction in the volume of information is small (high frequency) details (texture tablecloths) survived;

figure 10 - the pattern obtained for the YCrCB color palette, the number of significant bytes - 141449, zeros - 1212151, at about the same quality of the reconstructed images (figures 9 and 11). The ratio of the number of significant elements (bytes) of the pattern to the volume of the original image (bytes): 0,1045. The number of significant elements in 2.17 times less than in the pattern on Fig;

11 - restored image pattern (Figure 10). You should pay attention to the fact that despite a significant reduction in the volume of information is small (high frequency) details (texture tablecloths) survived;

Fig is one of the standard test images from The USC-SIPI Image Database http://sipi.usc.edu/database/), the original image on the left (size, bmp 24-bit, 196608 bytes), restored to the right;

Fig - pattern image (Fig), the number of excluded items (zeros) 134831;

Fig is one of the standard test images (in bmp format 24-bit), size very sophisticated panel contains 786,432 bytes;

Fig - pattern image (Fig), the number of excluded items (zeros) 535552;

Fig - restored image pattern (Fig).

For disclosure of the method let us consider the sequence of the compression procedure and the procedure of image reconstruction. Procedures the and compression on the basis of the equations of Laplace is to find the boundary conditions for the solution of partial differential equations (in accordance with the previously selected template). Template selection depends on the particular implementation of the proposed method. The determination of the boundary conditions (pattern) is performed by calculating the values of the partial derivatives of the second order at each point of the image, and then calculating the difference with the actual values of the corresponding pixel. The resulting difference is the criterion for making the decision to leave this point for the pattern or exclude, the numerical value of the criterion would correspond to the "degree" of compression. When the zero value of the criterion is lossless compression. For color images, the conversion can be made in any pre-selected color space such as RGB or YCrCb. The transformation is performed separately for each channel of the color palette. Special studies have shown that in YCrCb color palette, for some images, you can achieve a higher degree of compression than in RGB.

Write the entire procedure in a formal form for two-dimensional static image when the selected template (figure 1). In the General case, the template may be of any configuration that allows you to effectively solve partial differential equations. Let a two-dimensional array image is characterized by a set of values U_{x,y}where x, y - coordinates of the corresponding point. Will make the calculation of the differential value is fakticheskoi values U_{
x,y}in the image array, and the solution of the Laplace equation:

When the selected criteria h, let's compare |ΔU_{x,y}| (absolute value of) the difference with the value of h if the condition (|ΔU_{x,y}|≥h) is true, then U_{x,y}will be part of the pattern, if false, U_{x,y}excluded from the pattern and place U_{x,y}have written some (numerical) characteristic (e.g., zero) by which it can be determined that the point with coordinates (x,y) is not a boundary condition, and requires the calculation. It is obvious that the result of the calculation is the transition from integer values of U for floating point values. This can be avoided by replacing the division operation by the bit shift operation. The solution to the set of integers can significantly speed up the procedure of formation of the pattern. When choosing implement the need to take into account conditions specific tasks and the availability of computing resources.

It should be noted that the points located on the edges of the image (for static two-dimensional images of the four vectors)are the boundary conditions for them are described calculations are not applied, it may be directly copied into the array boundary conditions or consideration of the points located on the edges of the image, as one-dimensional vectors, to which you can apply equation of the form

In the case of a dynamic image, the fundamental approach remains the same. The equation of calculating the difference will be the following:

The planes bounding the region, can be applied to the above-described method of forming a pattern for a two-dimensional image or a direct copy in the array boundary conditions.

When used as the basis for the calculation of the pattern of the Poisson equation, the question arises in the definition of the right side of the function f(x,y) for two-dimensional case, f(x,y,t) for the three-dimensional case. The function f should be chosen in such a way that the calculated pattern contained the smallest number of elements, which is the boundary conditions. In this case, the function will be defined by a set of coefficients, which may require a significant amount of memory. The solution can be defined as the minimization of the number of boundary elements forming the pattern, and the coefficients of the function f, while maintaining sufficient quality of the recovered image. Consider some of the options functions f:

- plane: f(x,y)=ax+by+C;

- inverse discrete cosine transformation (see (2)), the whole space of the picture is the situation:

various wavelet functions using a set of wavelet coefficients allows to calculate with precision the values in the image space;

- an array of discrete values, corresponding to the average values in the areas obtained by dividing the image into rectangles (in the two-dimensional case) or parallelepipeds (in the three-dimensional case).

Obviously, as the right part can be selected and any other functions (functional layers), the most suitable for a specific case. As an example, let us consider in more detail the DCT. DCT depending on the degree of image compression allows you to save, you exclude occasione (small) details but the proposed method can preserve the "small" detail. Thus, it is possible to use multiple low-frequency component of the DCT as the right-hand side of the Poisson equation. Similarly, you can use the wavelet transform as the right-hand side of the Poisson equation, which allows to take into account the peculiarities of the spatial spectrum of the image.

With a limited number of places on the preservation of one channel of a color scheme, there is a restriction on the possible values. For example, if eight bits for each channel in the color scheme RGB valid values limited to the range 0-255. The boundary values in the pattern are written by copying the corresponding values from the source image, and other values in the pattern are filled with pre-selected value, for example zero. If the point pattern will occur zero, to distinguish it from other zeros, which recorded points that are not boundary conditions, will be impossible. For human readability gradation within 1/256 will be invisible, but if you must have the ability to save images without losses, then the error must be corrected, for correction, you can use a bitmask of the image.

The result of the above transformations is formed a pattern that contains a significant number what about the duplicate items such a pattern can be effectively used compression algorithms based on the standard transformations: Huffman, LZ78, arithmetic encoding.

The inverse transform is to restore the original image pattern. The most obvious solution is to use an iterative method, finite difference, boundary conditions for the solution is the pattern. In this approach, the computation time to restore the image in a sufficiently high quality can be significant, especially for large image sizes. Therefore, in the present method it is proposed to use the pre-filtering. The meaning of prefiltration is to accelerate convergence of the iterative process of calculation by finite difference method. Consider the option of implementing prefiltration, for example, two-dimensional image. Pre-filtering is performed sequentially, first in the X direction, and then in the Y direction, or Vice versa. So, take a pass on the first (the first of those to which you've applied differential method of forming a pattern, the outer lines are the boundary conditions, see above) prompt, if you find an item that is an element of the boundary conditions, we store the value and move further until you meet the next item, which is the boundary s is imposed. Knowing the importance of the two boundary elements in the same vector used approximation (e.g., linear) to calculate the values of the elements located between them. Thus, approximate all values within a single row. Consistently go through all rows in the X direction, and then made the same pass through all the rows in the y direction When passing through the rows in the Y direction into account the previously obtained values (when iterating X) and calculated the actual value as the average between the passage in the direction of X and Y.

It is possible to add przefiltrowane passes diagonally.

When using Poisson equations as functions of carrying out "pre-filtering", you can use the equation right side together with the above passage in the directions X and Y.

The result of this prefiltration is an array of data that can be considered as part of the computation is obtained as a result of performing an iterative approximation. The above-described pre-filtering can significantly speed up the convergence of the iterative process, and thus to accelerate the process of image reconstruction. Further iterative calculations can be performed by a finite difference method. The criterion for completion of the calculations can serve as a numerical estimation of the residuals. This hike is allows quickly enough to form an image (for example, on the monitor screen) and sequentially, continuing the iteration, and periodically update the image to improve its visual quality (progressive decoding).

The described method may be applied to dynamic (three-dimensional) images, using as another time coordinates f(x,y,t). Possible application of the method in other multidimensional images, for example in three-dimensional television, where depending on the implementation can be from four (three spatial and time) or more coordinates.

To implement the proposed method requires a sequence of actions that meet all the characteristics of the algorithm.

The order method is strictly defined and determined.

A generalized algorithm for compression of two-dimensional static image (using the Laplace equation). In the description of the algorithm the image pattern are integers, two-dimensional arrays of values (in units of the grid of image pixels).

1. The generated pattern image, which is an array of boundary conditions for the solution of the equations of Laplace or Poisson during recovery. If applied to the Poisson equation, we calculate the necessary coefficients, clearly describing the right side of the Poisson equation.

2. If you want to save images without losses generated by the bit matrix (array), enabling the adjustment of the image when restoring. A bitmask is also compressible, for example, a method of run-length encoding of RLE.

3. Applied to the received pattern standard compression mechanism to more efficiently compress the data, containing a large number of repetitive elements.

The generalized algorithm of image reconstruction:

1. Produced by the operation of extracting pattern in accordance with the method of packing. In case of necessity produced by extracting coefficients (in the case of the Poisson equation) and bitmap (to restore the image without loss).

2. Produced by the pre-filtering using the obtained (in paragraph 1) pattern. The purpose of prefiltration is accelerating the convergence of iterative process of image reconstruction on the pattern.

3. We calculate (recovery) image pattern, using as the restoration (array, which will be obtained reconstructed image array obtained at the stage prefiltration. The criterion for the end of the calculations can be specified number of iterations or the value of the residuals (controlling the convergence of the iterative process).

4. If you want to restore the image without loss, make corrections using a bitmask.

Thus, the proposed method eliminates the loss of integrity of the image, increases the efficiency of compressing images that contain large areas of single colors or gradient colors, brightness), and stores the contrast of the boundaries between different objects of the image.

1. The compression method of the image based on the exclusion of certain pieces of information, wherein information is excluded from the spatial domain by numerical solution of differential equations Poisson's or Laplace and subsequent evaluation of the differences between the obtained solution and the actual values at discrete points in the image, form an array of boundary conditions, containing a large number of equal elements, which is compressed, and to restore the image to solve differential equations in partial derivatives of the Poisson or Laplace, using an array of boundary conditions.

2. The method according to claim 1, characterized in that to produce the pre-filtering array boundary conditions, filling many points on the image does not belong to the boundary conditions, the value function approximation, calculated by the well-known points of the boundary conditions.

**Same patents:**

FIELD: information technologies.

SUBSTANCE: method to compress binary data in the form of structured information blocks, which consists in the fact that for an input flow of binary data, which contains symbols represented by bit sequences of identical fixed size, they count frequency of symbol recurrence, then to indicate frequently and rarely occurring symbols of the input flow of binary data, they accordingly perform generation of shorter and longer bit sequences, which are combined in a total bit sequence of alternating size, differing by the fact that from the total bit sequence they exclude bit sequences, which correspond to recurring symbols of the input flow of binary data.

EFFECT: improved properties of compression of structured information blocks.

3 dwg

FIELD: information technology.

SUBSTANCE: invention relates to encoding/decoding of digital signals, especially using permutation codes, accompanied by calculation of combinatorial expressions. According to the invention, the combinatorial expressions are represented by prime factor power decompositions and are determined by reading of pre-recorded representations of decompositions of selected integers.

EFFECT: efficient decoding of permutation codes.

13 cl, 9 dwg, 18 tbl, 7 app

FIELD: information technology.

SUBSTANCE: invention relates to encoding/decoding of digital signals, especially using permutation codes, accompanied by calculation of combinatorial expressions. According to the invention, the combinatorial expressions are represented by prime factor power decompositions and are determined by reading of pre-recorded representations of decompositions of selected integers.

EFFECT: efficient decoding of permutation codes.

8 cl, 9 dwg, 18 tbl, 7 app

FIELD: information technology.

SUBSTANCE: disclosed are a context-based arithmetic encoding apparatus and method and a context-based arithmetic decoding apparatus and method. The context-based arithmetic decoding apparatus may determine a context of a current tuple of N elements to be decoded, determine a most significant bit (MSB) context corresponding to an MSB symbol of the current tuple of N elements, and determine a probability model using the context of the tuple of N elements and the MSB context. The context-based arithmetic decoding apparatus may then perform decoding for a MSB based on the determined probability model, and perform decoding for a least significant bit (LSB) based on a bit depth of the LSB derived from the decoding process for an escape code.

EFFECT: high efficiency of encoding and reducing the amount of memory required for encoding.

79 cl, 29 dwg

FIELD: information technology.

SUBSTANCE: invention relates to symbol encoding/decoding and more specifically to an entropy encoding/decoding method based on Huffman coding and employs multidimensional codewords. In the symbol encoding method, it is determined whether a symbol can be encoded with a codeword of a first codebook. If so, the codeword for the symbol is selected from the first codebook. Otherwise the codeword is selected from the first codebook which indicates that the symbol cannot be encoded with the codeword of the first codebook, and the symbol is divided into a plurality of first sub-symbols, and for at least one of the first sub-symbols, the codeword is selected from a second codebook. A corresponding decoding method is described.

EFFECT: increase in number of dimensions of the symbol to provide better adaptation of the length of the codeword to symbol probability and better use of statistical relationships between neighbouring sub-symbols.

15 cl, 13 dwg

FIELD: information technologies.

SUBSTANCE: device for data compression-decompression comprising a transmitting side and a receiving side, which additionally comprises: an L-digit input register of the transmitting part, an L-digit output register of the receiving part, an [L+1]-digit output register of the transmitting part, an [L+1]-digit input register of the receiving part, a digital switchboard and a digital processor with memory; an information input of the digital processor via the digital switchboard is connected to outputs of the L-digit input register of the transmitting part and the [L+1]-digit input register of the receiving part, the information output of the digital processor via the digital switchboard is connected to inputs of the [L+1]-digit output register of the transmitting part and the L-digit output register of the receiving part, the control input of the digital switchboard is connected to the control output of the digital processor.

EFFECT: simplified calculations due to absence of procedures of multiple multiplication and analogue-to-digital operations.

3 cl, 2 dwg

FIELD: radio engineering, communication.

SUBSTANCE: method of compressing digital information using a reference electrical signal, which employs a preselected electrical compression signal S(N) and a reference electrical restoration key signal K(N), which are altered by an arithmetic logic unit (ALU) using electrical signals which correspond to information elements, the digital codes of which are compressed, resulting in an altered reference electrical compression signal S(n) and an altered reference electrical restoration key signal K(n), through which restoration of initial electrical signals is subsequently carried out, said initial electrical signals corresponding to information elements whose digital codes were compressed, wherein during compression, digital positions of the reference electrical signal represent any changes in the reference signal and therefore contain full information on electrical signals coming in for compression.

EFFECT: faster compression and restoration of electrical signals.

FIELD: radio engineering, communication.

SUBSTANCE: system (100) of non-linear conversion of data includes an input for reception of a digitised signal AC, an output for discharge of a non-linearly converted signal and a system (104) of processing connected with the input and the output. The processing system (104) is configured as capable of receiving the digitised signal AC, non-linear conversion of the digitised signal AC using a predetermined transfer function, to create a non-linearly converted signal, besides, the predetermined transfer function creates a non-linearly converted signal relative to the predetermined point, and transfer of a non-linearly converted signal to the output.

EFFECT: improved efficiency of signal transfer.

14 cl, 11 dwg

FIELD: information technology.

SUBSTANCE: to find maximum sections in a finite sequence of characters x[i] (0≤i≤N) of a finite alphabet, which are repetitions of previously encountered sections, two bit arrays beg[i] and end[i] are created in computer memory. All elements of said bit arrays are populated with zeros. The sequence s1[i] is calculated for all N values of indices i, where s1[i] is the maximum length of the linear section of said data sequence. All said maximum sections are defined as all intervals x[m,n] for which the initial index m satisfies the condition s1[m]>sl[m-1]-1, and the final index n is equal to m+sl[m]-1, for which, for each value i, the fulfillment of the condition s1[i]>sl[i-1]-1 is checked, and if the condition is met, values beg[i]=1 and end[i+s1[i]]=1 are set in the bit arrays beg[i] and end[i]. The set of all said maximum sections is recovered on the two bit arrays beg[i] and end[i].

EFFECT: reduced amount of memory required to display all maximum repeating sections.

3 cl, 2 dwg

FIELD: information technology.

SUBSTANCE: apparatus includes an analogue-to-digital converter, an integrator, a storage device, a unit for calculating autoregression coefficients, a unit for calculating exponent parameters which depend on time, a unit for calculating exponent parameters independent of time, a unit for calculating oscillation parameters, a signal restoration unit and a timer.

EFFECT: lower noise level in the restored signal.

3 cl, 1 dwg

FIELD: information technology.

SUBSTANCE: method is carried out by realising automatic computer formation of a prediction procedure which is appropriately applied to an input image. The technical result is achieved by making an image encoding device for encoding images using a predicted pixel value generated by a predetermined procedure for generating a predicted value which predicts the value of a target encoding pixel using a pre-decoded pixel. The procedure for generating a predicted value, having the best estimate cost, is selected from procedures for generating a predicted value as parents and descendants, where the overall information content for displaying a tree structure and volume of code estimated by the predicted pixel value, obtained through the tree structure, is used as an estimate cost. The final procedure for generating a predicted value is formed by repeating the relevant operation.

EFFECT: high efficiency of encoding and decoding, and further reduction of the relevant volume of code.

12 cl, 14 dwg

FIELD: information technologies.

SUBSTANCE: in the method of processing of raster images, including compression of an image by the method of "cut block coding" or its modifications, before the procedure of compressing coding they perform digital filtration, which increases sharpness of the compressed image, and after the decoding procedure they perform smoothing digital filtration of the decoded image.

EFFECT: improved quality of decoded raster images when methods used for their compressing coding on the basis of cut block coding or their modifications, improved current formalised criteria.

3 cl, 8 dwg

FIELD: radio engineering, communication.

SUBSTANCE: method of encoding transform coefficients includes: encoding the position and value of a last non-zero coefficient of a block; encoding at least one coefficient in accordance with a first coding mode if the amplitude of said at least one coefficient is less than or equal to a threshold; and determining a cumulative sum of amplitudes of previously coded non-zero coefficients that are greater than the threshold; and if the cumulative sum is less than a cumulative threshold value, and the position of the last non-zero coefficient is less than a location threshold: coding a subsequent coefficient in accordance with the first coding mode; otherwise, coding a subsequent coefficient in accordance with a second coding mode.

EFFECT: high encoding efficiency.

22 cl, 8 dwg

FIELD: information technology.

SUBSTANCE: methods and systems for processing document object models (DOM) and processing video content are provided. Information content which is represented by a DOM and which includes a scripting language associated with the information content is received and original content of the DOM is stored after execution of the scripting language. Further, video content is adapted for client devices. The scripting language associated with the information content can be sent to client device along with a modified DOM and processed video content. Pre-processing of the scripting language is carried out to identify nodes related to video content and to maintain all other original nodes, for example.

EFFECT: easier processing of video data.

23 cl, 12 dwg

FIELD: information technology.

SUBSTANCE: video camera has a portable housing having a light focusing lens, a light-sensitive device which converts the focused light into source video data, a storage device installed in the housing, and an image processing system configured to introduce predistortions into the source video data and compression thereof, wherein the compressed source video data remain essentially visual without loss after decompression, and also configured to store compressed source video data in the storage device.

EFFECT: reduced loss of quality of a compressed image during decompression and display.

22 cl, 18 dwg

FIELD: information technologies.

SUBSTANCE: device comprises a processor arranged as capable of realisation of a set of commands for calling a facility of intracycle filtration of blocking effect deletion and for universal correction of blocking effect in a decoded output signal during operation of a post-cycle filtration using the facility of intracycle filtration of blocking effect deletion, at the same time the universal correction of blocking effect includes the following: performance of an operation of strong filtration in respect to units in a decoded output signal for correction of an inherited blocking effect, at the same time units contain missed macrounits and units with a template of a coded unit, equal to zero, and inclusion of a facility of intracycle filtration of blocking effect removal for edges of a fragment of an image of fixed size, which are not arranged on the border of the unit of the appropriate intermediate macrounit, for correction of the inherited blocking effect; and a memory connected to the processor.

EFFECT: development of a method of universal correction of blocking effect, including inherited blocking effect.

19 cl, 23 dwg, 7 tbl

FIELD: information technology.

SUBSTANCE: method of encoding a graphic display to provide a unique, distinctive machine-readable code for a plurality of commodities involves obtaining an image of part of the graphic display. An electronic image of the temporary boundary around a certain part of the graphic display is formed relative a fixed trigger point. Part of the obtained image lying inside that boundary is processed to obtain a descriptor. Data are assigned to the descriptor. Further, that relationship is stored in a storage. The graphic display is fixed for a plurality of commodities and the temporary boundary is different for each commodity such that part of the graphic display which forms the code is different for each commodity.

EFFECT: high protection from copying, forgery or unauthorised reading of a graphic code.

7 cl, 10 dwg

FIELD: information technology.

SUBSTANCE: in the method, conversion of radiation intensity of matrix elements into binary codes is carried out in parallel and synchronously with all matrix elements at the same time, represented by triads of "radiation brightness-to-code" converters of three fundamental colours R, G, B, which convert radiation brightness to binary codes at the speed of light, and digitisation of the frame image ends with the end of the frame interval.

EFFECT: high speed of digitisation.

2 cl, 5 dwg

FIELD: physics.

SUBSTANCE: two-dimensional presentation of the inspected electronic image is divided into overlapping blocks; k-level wavelet transformation is performed on each block; horizontal, vertical, high-frequency and low-frequency coefficients of the performed wavelet transformation of a block are generated; statistical characteristics of the wavelet transformation coefficients are calculated, from which a vector of statistical characteristics of a block is formed; the vector of statistical characteristics of a block is compared with previously formed vectors of statistical characteristics of knowingly modified electronic images and with previously formed vectors of statistical characteristics of knowingly modified electronic images; a block is identified as modified if the difference between its vector of statistical characteristics and the closest previously formed vector of statistical characteristics of knowingly modified electronic images.

EFFECT: high accuracy of determining coordinates of the modified part of an electronic image.

5 cl, 6 dwg

FIELD: information technology.

SUBSTANCE: block transform-based digital media codec more efficiently encodes wide dynamic range transform coefficients in two parts: a normalised coefficient and bin address. The normalised coefficient relates to a grouping of coefficient values of the wide dynamic range into bins, whereas the bin address is an index of the coefficient value within a bin. With careful selection of the bin size, the normalised coefficients have a probability distribution roughly similar to narrow range transform coefficients, which is better suited to variable length entropy coding. The codec uses variable length entropy coding to encode the normalised coefficients in a 'core' of the compressed bitstream, and fixed length coding to encode the bin address as a separate optional layer that can be omitted. The codec further adaptively varies the bin size of the grouping based on a backward adaptation process to adjust the normalised coefficients towards a probability distribution well suited for efficient variable length entropy coding.

EFFECT: efficient compression of wide-range transform coefficients.

29 cl, 12 dwg

FIELD: systems for encoding and decoding video signals.

SUBSTANCE: method and system for statistical encoding are claimed, where parameters which represent the encoded signal are transformed to indexes of code words, so that decoder may restore the encoded signal from aforementioned indexes of code words. When the parameter space is limited in such a way that encoding becomes inefficient and code words are not positioned in ordered or continuous fashion in accordance with parameters, sorting is used to sort parameters into various groups with the goal of transformation of parameters from various groups into indexes of code words in different manner, so that assignment of code word indexes which correspond to parameters is performed in continuous and ordered fashion. Sorting may be based on absolute values of parameters relatively to selected value. In process of decoding, indexes of code words are also sorted into various groups on basis of code word index values relatively to selected value.

EFFECT: increased efficiency of compression, when encoding parameters are within limited range to ensure ordered transformation of code word indexes.

6 cl, 3 dwg