# Message compression and recovery method

FIELD: electrical communications; data digital computation and processing including reduction of transferred information redundancy.

SUBSTANCE: proposed message compression and recovery method includes pre-generation of random quadrature matrix measuring m x m constituents and k random key matrices measuring N x m and m x N constituents on transmitting and receiving ends, and generation of quantum reading matrix of fixed half-tone video pattern measuring M x M constituents. Matrices obtained are transformed to digital form basing on addition and averaging of A images, each image being presented in the form of product of three matrices, that is, two random rectangular matrices measuring N x m and m x N constituents and one random quadrature matrix measuring m x m constituents. Transferred to communication channel are constituents of rectangular matrix measuring N x m constituents. Matrix of recovered quantum readings of fixed half-tone video pattern measuring M x M constituents is generated basing on rectangular matrix measuring N x m constituents received from communication channel as well as on random quadrature matrix measuring m x m constituents and random rectangular matrix of m x N constituents, and is used to shape fixed half-tone video pattern.

EFFECT: enhanced error resistance in digital communication channel during message compression and recovery.

2 cl, 26 dwg, 1 app

The invention relates to telecommunications, and in particular to methods of digital computing and data processing with the reduction of the redundancy of the transmitted information. The proposed method can be used for the transmission of a fixed video via digital communication channels with errors. The invention relates to the class of encodings-based recovery conversion.

Known methods of encoding video images on the basis of pulse code modulation, differential pulse code modulation, statistical coding and coding with prediction, see, for example, the book: Upref. Digital image processing. Part 2. - M.: Mir, 1982, s-688. These methods involve the coding of images with elementwise processing when a continuous signal is converted into a sequence of quantized samples, and then submitted to the code words in the form of zeros and ones.

Also known coding techniques based on the transformation, see, for example, the book: Nahmed, Crra. Orthogonal transformations in the processing of digital signals. - M.: Radio and communication, 1980, p.á192-201, including the execution of three operations: first, the image is subjected to two-dimensional orthogonal transformation, the resulting conversion factors quantuum and encode for transmission over the channel is connected.

The disadvantage of the above methods - analogues is relatively low transmission rate of messages at a given quality of their recovery, and low resistance to errors in digital communication channel.

There is a method of compression and recovery of voice messages, described in the patent of the Russian Federation No. 224463, IPC^{7}G 10 L 19/00, 2005, which provides for the correction of errors in the transmitted digital sequence under the influence of the instability of the parameters of the communication channel and allows the transmission of information via low-speed digital communication channels. The disadvantage of this method is the relatively low quality of the retrieval of the data when the probability of errors in the channel 10^{-4}.

The closest to the technical nature of the claimed method is a method of compression and recovery of voice messages, described in the patent of the Russian Federation No. 2244963, IPC^{7}N 04 N 7/30, 2005

The known method is the prototype, which consists in the fact that preliminary on transmitting and receiving sides is identical generate random square matrix of size m×m elements. Represent digital information signal in the form of a matrix of normalized values. Generate a random rectangular matrix of size N×m m×N elements, convert them by dividing the elements of ka the DOI string of random rectangular matrix of size Nxm elements on the amount of units of the corresponding row and dividing the elements of each column of a random rectangular matrix of size m× N elements on the amount of units of the corresponding column. Then calculate the resulting matrix of size N×N elements, by successive multiplication of the transformed random rectangular matrix of size Nxm on a random square matrix of size m×m and the transformed random rectangular matrix of size m×N elements. Next, calculate the mean square error between the elements of the output matrix of size NxN elements and the elements of the matrix of normalized values of size N×N elements. And then invert each element of random rectangular matrices of size N×m m×N elements, and after the inversion of each element in a random rectangular matrix transform it by dividing the elements of each row of a random rectangular matrix with inverse element of size N·m items in the amount of units of the corresponding row and dividing the elements of each column of a random rectangular matrix with inverse element size m×N elements on the amount of units of the corresponding column. Re-calculate the resulting matrix of size N×N elements, by successive multiplication of the transformed random rectangular matrix with the inverse element of size N×m on a random square matrix times the leader in m× m and the transformed random rectangular matrix with the inverse element of size m×N. then compute the RMS error between the elements recomputed the output matrix of size N×N elements with the elements of the matrix of normalized values of size N×N elements. Transmit over the communication channel random rectangular matrix of size N×N. Take the link to this matrix and on the receiving end converts the received random rectangular matrix N×m m×N by dividing the elements of each line of a random rectangular matrix of size N×m items in the amount of units of the corresponding row and dividing the elements of each column of a random rectangular matrix of size m×N elements on the amount of units of the corresponding column. Calculate rezultirase matrix of size N×N elements, by successive multiplication of the transformed random rectangular matrix of size N×m on a random square matrix of size m×m and the transformed random rectangular matrix of size m×N. Form the digital information signal. On the receiving and transmitting sides additionally generate k random key matrix of size N×m m×N elements. Each element of a random square matrix of size mxm elements is anaglesic range -500 ÷ +500, as digital information signal is received by k matrices of the quantized samples fixed grayscale image sizes M×M, where k>1.

Generating at the receiving and transmitting sides identical normalization matrix of size N×N items, where C(i,j) is calculated by the formulawhere i=1, 2, ..., N, j=1, 2, ..., N. as a random rectangular matrix of size mxN elements take on a transmitting side transposed random rectangular matrix of size N×m elements. Form k matrices of coefficients of two-dimensional discrete cosine transform of size M×M elements by successive multiplication of the matrix of the discrete cosine transform of size M×M elements in each matrix of the quantized samples fixed grayscale video size M×M elements and the transposed matrix of the discrete cosine transform of size M×M elements. Next, form the k matrices of coefficients of two-dimensional discrete cosine transform of size N×N elements, according to the formula A_{g}(i,j)=L_{g}(i,j), where i=1, 2, ..., N, j=1, 2, ..., N, g=1, 2, ..., k, Lg(i,j)-i,j-th element of g-th matrix of the coefficients of the two-dimensional discrete cosine transform of size M×M elements, Ag(i,j)-i,j-th element of g-th matrix to which fficient two-dimensional discrete cosine transform of size N×
N elements, and choose N<M. Then form k matrix of normalized values of size N×N elements by multiplying each coefficient of the matrix of coefficients of two-dimensional discrete cosine transform of size N×N items in A_{g}(I,j) to the corresponding element of the normalization matrix of size N×N elements. Each of the key matrices of dimensions N×m m×N elements sum modulo 2, respectively, with direct and transposed random rectangular matrix of dimensions N×m m×N elements, and after calculating the root mean square error between the corresponding elements of each of the output matrix of size N×N elements and a matrix of normalized values of size N×N elements, calculate their total amount. After inverting each element of a random rectangular matrix of size N×m the resulting sum is compared with the previous total. The communication channel transmit a random rectangular matrix of size N×m elements, and at the receiving side after multiplying k random matrices with dimensions N×m by a random matrix of size m×m and k random matrices with dimensions m×N convert the resulting matrix sizes N×N elements by element-by-element division of their elements to the corresponding elements Nemirovich the th matrix of size N×
N elements. The obtained k matrix of reconstructed coefficients of size N×N elements complement with zeros to the size of a M×M elements. Restore k matrices fixed grayscale images by successive multiplication of the transposed matrix of the discrete cosine transform of size M×M elements by k matrices restored coefficients of two-dimensional discrete cosine transform of size M×M elements and a matrix of discrete cosine transform of size M×M elements. For the formation of k matrices of the quantized samples fixed grayscale video size M×M elements, each element of S_{g}(x,y), where x=1, 2, ..., M, I=1, 2, ..., M, g=1, 2, ..., k, assigned a quantized value of the corresponding pixel g fixed grayscale images of size N×N. To represent k matrices of the quantized samples fixed grayscale video size M×M elements in the form of k fixed grayscale images, each pixel k fixed grayscale video assign the value of the corresponding element of k matrices restored quantized samples fixed grayscale images of size M×M elements.

Prototype method allows, without compromising the quality of the restored what I messages to increase the data transmission rate to the amount at which you can maintain video information exchange on low-speed digital communication channels.

The disadvantage of this method-prototype is a relatively low resistance to errors in digital communication channel. This is because at the receiving side of the digital sequence shall be deemed accepted without errors, when inversion of symbols in the transmitted digital sequence under the influence of the instability of the parameters of the communication channel messages will be restored with certain distortions.

The aim of the invention is to develop a method of compression and message recovery, providing increased stability to the errors in a digital communication channel in compressing and restoring messages.

This objective is achieved in that in the known method for compressing and restoring messages previously on transmitting and receiving sides is identical generate random square matrix of size m×m elements, each element of which belongs to the range -500 ÷ +500. Generate k random key matrix of size N×m m×N elements. Then form the normalization matrix of size N×N items, where C(i,j) is calculated by the formulawhere i=1, 2, ..., N, j=1, 2, ..., N, and form the matrix of quantized samples fixed grayscale video size M×
M elements, where each element of S(x,y) is assigned a quantized value of the corresponding pixel fixed grayscale video size M×M pixels, where x=1, 2, ..., M; y=1, 2, ..., m. Next, form the matrix of coefficients of two-dimensional discrete cosine transform of size M×M elements by successive multiplication of the matrix of the discrete cosine transform of size M×M elements of the matrix of quantized samples fixed grayscale video size M×M elements and the transposed matrix of the discrete cosine transform of size M×M elements. Form the matrix of coefficients of two-dimensional discrete cosine transform of size N×N elements, according to the formula A(i,j)=L(i,j), where L(ij)-i,j-th element of the matrix of coefficients of two-dimensional discrete cosine transform of size M×M elements A(i,j)-I, j-th element of the matrix of coefficients of two-dimensional discrete cosine transform of size N×N elements, and choose N<M, then form the matrix of normalized values of size N×N elements by multiplying each coefficient of the matrix of coefficients of two-dimensional discrete cosine transform of size N×N elements A(i,j) to the corresponding element of the normalization matrix of size N#x000D7;
N elements. Then generate a random rectangular matrix of size N×m elements, and as a random rectangular matrix of size m×N elements take transposed random rectangular matrix of size N×m elements, then each of the key matrices of dimensions N×m m×n elements sum modulo 2, respectively, with direct and transposed random rectangular matrix of dimensions N×m m×N elements. Transform matrix obtained by dividing the elements of each row of a random rectangular matrix of size N×m items in the amount of units of the corresponding row and dividing the elements of each column of a random rectangular matrix of size m×N elements on the amount of units of the corresponding column. Next, calculate k the resulting matrices V(g), where g=1, 2, ..., k, N×N elements by successive multiplication of the k transformed random rectangular matrices of size N×m on a random square matrix of size m×m and k of the transformed random rectangular matrices of size m×N elements. Sequentially invert each element of random rectangular matrices with dimensions N×m m×N elements and after the inverse transform by dividing the elements of each row of a random rectangular matrix with inverted the th element of size N×
m elements on the amount of units of the corresponding row and dividing the elements of each column of a random rectangular matrix with inverse element size m×N elements on the amount of units of the corresponding column. Re-calculate k the resulting matrices of size N×N elements, by successive multiplication of the k transformed random rectangular matrices with inverted element size N×m on a random square matrix of size m×m and k of the transformed random rectangular matrices with inverted element size m×N. Transmit over the communication channel random rectangular matrix of size N×m and take the link to this matrix. Then each of the key matrices of dimensions N×m m×N elements sum modulo 2, respectively, with direct and transposed random rectangular matrices of size N×m m×N elements. Convert the received random rectangular matrix of dimensions N×m m×N by dividing the elements of each line of a random rectangular matrix of size N×m items in the amount of units of the corresponding row and dividing the elements of each column of a random rectangular matrix of size m×N elements on the amount of units of the corresponding column. Then calculate k restored the resulting matrices
where g=1, 2, ..., k, N×N elements by successive multiplication of the k transformed random rectangular matrices of size N×m on a random square matrix of size m×m and k of the transformed random rectangular matrices of size m×N, respectively, and the matrix of reconstructed coefficients of size N×N elements complement with zeros to the size of a M×M elements. Get the matrix of reconstructed coefficients of the discrete cosine transform of size M×M elements, restore the matrix fixed halftone image by successively multiplying the transposed matrix of the discrete cosine transform of size M×M elements of the matrix of reconstructed coefficients of two-dimensional discrete cosine transform of size M×M elements and a matrix of discrete cosine transform of size M×M elements. Form a digital information signal, each pixel^{}fixed grayscale video assign the value of the corresponding matrix element of the restored quantized samples fixed grayscale images of size M×M elements. After calculation of the k resulting matrix calculates the total matrix size N×N elements of V_{s}according to the formula
Then calculate the mean square error between the elements of the matrix of normalized values of size N×N elements and elements of the total matrix V_{s}size N×N elements. After inversion of each element of random rectangular matrices with dimensions N×m m×N re-calculate k of the resulting matrices, the total matrix V_{s}and a root mean square error between the elements of the matrix of normalized values of size N×N elements and elements of the re-calculated total matrix V_{s}size N×N elements. The obtained RMS error is subtracted from the previous standard error and in the case of a positive difference remember the inverted element, and after calculation of the k recovered resulting matricescalculate restored^{}the total matrix size N×N_{s}according to the formulaand to obtain the matrix of reconstructed coefficients of size N×N elements convert the recovered total matrix size N×N elements by element-by-element division of its elements to the corresponding elements of the normalization matrix of size N×N elements.

Thanks to the new essential features due to the imp is in a discrete cosine transform on the matrix of quantized samples fixed grayscale video is go to view the video in the form of the coefficient matrix of the two-dimensional
discrete-cosine transform. To reduce the digital representation of the video encode and transmit not all DCT coefficients, but only the N^{2}the DCT coefficients of the spectrum with maximum energy, and to increase resilience to errors in a digital communication channel, the compensation of errors in digital communication channel is based on the summation and averaging k of the resulting matrices. Marked provides resistance to errors, compression and recovery of messages, thus improving the quality of recovery of the message during transmission over the communication channel with errors.

The analysis of the level of technology has allowed to establish that the analogues, characterized by a set of characteristics is identical for all features of the claimed technical solution is available, which indicates compliance of the claimed method the condition of patentability "novelty".

Search results known solutions in this and related areas of technology in order to identify characteristics that match the distinctive features of the prototype of the characteristics of the claimed method, showed that they do not follow explicitly from the prior art. The prior art also revealed no known effect provided the essential features of the claimed invention transformations on the achievement of specified order is the result. Therefore, the claimed invention meets the condition of patentability "inventive step".

The claimed method is illustrated by drawings.

- Figa. The formation of a random square matrix of size m×m elements.

- Figb. A variant of a random square matrix of size m×m elements.

- 2. The formation of the matrix of coefficients of two-dimensional discrete cosine transform of size M×M elements.

- 3. The formation of the matrix of coefficients of two-dimensional discrete cosine transform of size N×N elements.

- Figa, 4B. The formation of the normalization matrix of size N×N elements.

- 5. Forming a matrix of normalized values of size N×N elements.

- Figa. The formation of k random key matrix of size Nxm elements.

- Figb. Option k random key matrix of size N×m elements.

- Figv. The formation of k random key matrix of size m×N elements.

- High Option k random key matrix of size m×N elements.

- Fig 7a. The formation of a random rectangular matrix of size N×m elements.

- Figb. Variation of random rectangular matrices of size N×m elements.

- Figv. The formation of k random rectangular matrices of size N×m elements.

- Fig g Formation sluchainyh rectangular matrices of size m× N elements.

- Figd. The transformation of k random rectangular matrices of size N×m elements.

- Five. The transformation of k random rectangular matrices of size m×N elements.

- Fig. The formation of k the resulting matrices of size N×N elements.

- Figa. A variant of the inverse element of a random rectangular matrix of size N×m elements.

- Figure 10. Transmission of a random rectangular matrix of size N×m items of digital communication channel.

- Figa. A variant of the coefficient matrix of the two-dimensional discrete cosine transform of size M×M elements.

- Figb. The graph of the absolute values of the first row of the coefficient matrix of the two-dimensional discrete cosine transform of size M×M elements.

- Fig. The formation of the matrix of reconstructed coefficients of two-dimensional discrete cosine transform of size N×N elements.

- Fig. The formation of the matrix of reconstructed coefficients of two-dimensional discrete cosine transform of size M×M elements.

- Fig. Forming a matrix of the restored quantized samples fixed grayscale image.

The possibility of implementing the inventive compression method and message recovery is explained by the following. If necessary, the transmission channel of communication messages is, the volume of which exceeds the capacity of the communication channel or transmission which requires unacceptably large time interval, use various methods to reduce the volume of transmitted messages.

For example, (see the book: U. Prett. Digital image processing. Part 1. - M.: Mir, 1982, pp.96-118) of the encoded message are as a product of matrices of the reference vectors in a matrix of coecients. For this purpose, use one of the known methods: the discrete cosine transform, fast Fourier transform, transformation of karunen-Loev, Wavelet transform, and others.

This technique causes some reduction in the amount of information required for transmission over the communication channel and the simultaneous achievement of the required quality.

At the receiving end the received message restore.

Thus, when a deterioration in the quality of information transmitted reduce the amount of information required for transmission. At the same time, the volume of transmitted information about the matrix of support vectors and the matrix of coecients is still large, which does not meet the requirements of modern communication channels, while maintaining the required quality, and these techniques do not provide resistance to errors in the communication channel. For increasing resilience to errors in the channel is due to apply error-correction coding, described, for example, in the book: U. Peterson, E. Weldon. Error-correcting codes. - M.: Mir, 1976. This error-correction coding based on the division of all possible code combinations on permitted and prohibited. This approach involves the introduction into the transmitted digital sequence redundancy. This leads to a significant reduction in the degree of compression of the transmitted information and, accordingly, increase of requirements to the transmission speed of the digital communication channel. Also known way of dealing with interference-based accumulation method, described, for example, in the book: Art. Combating interference. - M.: YFML, 1963. This method is based on transmission of a single message across multiple independent channels. This method increases the signal-to-interference in k times without increasing the signal power. However, for this advantage comes at the expense of k-fold use of the channel. If time division multiplexing is increased to k times the transmission time, at a frequency k times occupied bandwidth, etc.

In the proposed method solves the problem of reducing the amount of transmitted data and ensuring the sustainability of the restored image to the influence of errors on the basis of the accumulation method for a single channel.

The proposed method is implemented as follows.

The formation of transmitting priemnoi sides of a random square matrix of size m×
m elements (hereinafter denote it as [B]_{m×m}), each element of which belongs to the range -500 ÷ +500 (see figa, 1B). Size m matrix [B]_{m×m}chosen empirically based on the size of the message) Experimental studies show that the quality of approximation of the transmitted message size m is 1/5-1/4 of the size of the message. The operation of forming the matrix [B]_{m×m}can be performed using a random numbers generator. To fulfill the requirements of the identity matrix [B]_{m×m}the receiver is similar to the matrix of the transmitter elements of the matrix [V]_{m×m}can be generated on the transmission side and transmitted over a digital communication channel at the receiving side, for example, as part of synchrophasing.

As the message to be compressed and recovery, next the fixed grayscale images, which form the matrix of quantized samples fixed grayscale video size M×M elements, assigning each element S(x,y), where x=1, 2, ..., M; y=1, 2, ..., M, the quantized value of the corresponding pixel fixed grayscale image (see Fig).

In order to reduce the amount of information transmitted over the communication channel, using discrete casinodeapuestasenlinea, described, for example, in the book: Nahmed, Crra. Orthogonal transformations in the processing of digital signals. - M.: Communication, 1980, s-159.

The matrix of coefficients of two-dimensional discrete cosine transform of size M×M elements are formed on the basis of the expression

[L(x,y)]_{M×M}=[G([x,y)]_{M×M}×[S(x,y)]_{M×M}, ([G(x,y)_{M×M}where [L(x,y)]_{M×M}matrix of coefficients of two-dimensional discrete cosine transform fixed grayscale video size M×M elements, [S(x,y)]_{M×M}matrix quantized samples fixed grayscale video size M×M elements [G(x,y)]_{M×M}matrix direct discrete cosine transform, [G(x,y)]'_{M×M}matrix inverse discrete cosine transform (see figure 2).

The most informative from the point of view of recovery live video, are the coefficients of the two-dimensional discrete cosine transform with maximum energy, located in the upper left quadrant of the matrix of coefficients of two-dimensional discrete cosine transform of size M×M elements (see figa). They emit, forming a matrix of coefficients of two-dimensional discrete cosine transform of size N×N elements (hereinafter denote it as []_{
N×N}), on the basis of the expression A(i,j)=L(i,j), where i=1, 2, ..., N, j=1, 2, ..., N, L(i,j)-i,j-th element of the matrix of coefficients of two-dimensional discrete cosine transform fixed grayscale video size M×M elements A (i,j)-i,j-th element of the matrix of coefficients of two-dimensional discrete cosine transform fixed grayscale video size N×N elements, and choose N≤M (see figure 3).

The magnitude of the coefficients of two-dimensional discrete cosine transform to a large extent depends on their sequence numbers, which can be determined from the graph (see figb), where x-axis is the sequence number of the coefficients of the first row of the coefficient matrix of the two-dimensional discrete cosine transform of size M×M elements, and the y - axis of their absolute values. In order to eliminate the dependence of the elements of the coefficient matrix of the two-dimensional discrete cosine transform of size N×N items from their location in the matrix and in the future more accurately they can be approximated, it is necessary to perform the operation of rationing. The essence of this operation is that on the transmitting and receiving sides of the identical form of normalization matrix of size N×N elements (hereinafter denote it as [s]_{N×N}), the elements of which is Oh, C(i,j) is calculated by the formula
(see figure 4)obtained experimentally. When this takes into account the peculiarity of the coefficient matrix of the two-dimensional discrete cosine transform of size M×M elements, which consists in the arrangement of the coefficients with the maximum energy in the upper left quadrant and the dependence of coefficient values from their ordinal numbers (i and j).

Then form the matrix of normalized values of the two-dimensional discrete cosine transform of size N×N elements (hereinafter denote it as [V]_{N×N}) by multiplying each element A(i,j) matrix of coefficients of two-dimensional discrete cosine transform fixed grayscale video size N×N elements on the corresponding element C(i,j) normalization matrix of size N×N elements (see figure 5).

Further, similarly to the method prototype used an approach based on the representation of the g-th - the output matrix of size NxN elements (hereinafter denote it as) as a product of three matrices: the converted rectangular matrix of size N×m elements (hereinafter denote it as), a random square matrix of size m×m items [B]_{m×m}and converted to a rectangular matrix of size m×N elements (hereinafter denote the e as
(see Fig):where [Y_{pr}(g)] and [X_{pr}(g)] are such that the total matrix size N×N elements (hereinafter denote it as [V_{s}]_{N×N}) obtained by summing the corresponding elements of all matricesand dividing by k, was closest to the specified criteria to the matrix [V]_{N×N}.

Matrixandformed by summing modulo 2 of a random rectangular matrix [E]_{N×m}with a random key matrix [Y_{CL}(g)]_{N×m}and transposed rectangular matrix [E]^{T} _{N×m}with a random key matrix [X_{CL}(g)]_{m×N}accordingly, where the matrix [Y_{CL}(g)]_{N×m}and [X_{CL}(g)]_{m×N}are identically generated at the transmitting and receiving sides dimensions N×m m×N, respectively (see figv, 7 g), where the signmeans summation modulo 2.

Feature matrixandis that they can be easily converted to digital form. This is achieved by the fact that the elements of these matrices has the following limitations:

- matrix elementsand accept values in the range from zero to one;

- non-zero elements in each row of the matrixequal in amount to form a unit;

- non-zero elements of each column of the matrixequal in amount to form a unit;

With such restrictions, if the elements of each row of the matrixmultiply by the number of nonzero elements in this row, it will obtain the matrix [Y_{pr}(g)]_{N×m}the elements of which are defined only on the set of "1" and "0". Similarly, if the elements of each column of the matrixmultiply by the number of nonzero elements in the column, it will obtain the matrix [X_{pr}(g)]_{m×N}the elements of which are defined only on the set of "1" and "0".

The procedure that implements a search on the transmission side of the optimal matricesanddescribed in detail in the method-prototype (see RF patent №2244963, IPC^{7}N 04 N 7/30, 2005).

Thus, the representation matrix of the normalized values of the two-dimensional discrete cosine transform of size N×N elements [V]_{N×N}in digital form on the transmission side is carried out on the basis of generating a set of zero and unit elements in the form of lucini rectangular matrix of size N×
m (matrix [E]_{N×N}) (^{sm}- figa, 7b) and k is a random key matrix of size m×N and N×m elements (matrix [X_{CL}(g)] and [Y_{CL}(g)]_{N×m}(see figb, 6g) Then a random rectangular matrix [X(g)_{m×N}] and [Y(g)]_{N×m}convert by dividing the elements of each row of a random rectangular matrix of size N×m items in the amount of units of the corresponding row, i.e. its weight - v_{y}(g) (see the book: E. Berlekamp. Algebraic coding theory. - M.: Mir, 1971. C.12) (see Figg) and dividing the elements of each column of a random rectangular matrix of size m×N elements on the amount of units of the corresponding column, i.e., the weight of v_{x}(g). Thereby form the matrixand(see Figg, 7E).

Similarly, the method prototype calculate k the resulting matrices of size N×N elements, i.eby successive multiplication obtained after the conversion of rectangular matrix of size N×mrandom square matrix of size m×m items [B]_{m×m}and obtained from the conversion of rectangular matrix of size m×N(see Fig).

Next, the resulting the resulting matrix summarize on the rights of the DRS where- i,j - element of g St the resulting matrix.

The matrix [V_{s}]_{N×N}should be closest to the matrix [V]_{N×N}according to a certain criterion. It is known (see, for example, the book: Upref. Digital image processing. Part I. - M.: Mir, 1982, s-127)that one of the major objective criteria proximity is the standard error. Minimizing the mean square error achieved minimal differences between matrices [V]_{N×N}and [V_{s}]_{N×N}. Therefore, calculate the sum of squared differences between the elements of the total output matrix of size N×N elements [V_{s}]_{N×N}and the corresponding matrix elements of the normalized values of the two-dimensional discrete cosine transform of size N×N elements [V]_{N×N}. Then invert each element of a random rectangular matrix of size N×m elements (see Fig.9) and convert them in a similar manner as was described for the transformation matrix [Y(g)]_{N×m}and [X(g)]_{m×N}(see figb, 7b, 7G, 7D, 7E). Consistently Peremohy obtained after transformation of k random rectangular matrix of size Nxm elements, a random square matrix of size m×m elements and obtained after transformation of k random direct ogolnych matrices of size m×
N elements. The obtained k the resulting matrixsize N×N elements element-by-element sum and average according to the formula

Since the matrix [E]_{N×m}contained inverted element, after transformation has led to changes in the values of matrix elements [Y(g)]_{N×m}and [X(g)]_{m×N}and consequently led to changes in the matrixandchange the values of the elements of the output matrixthus changing the values of the matrixThen, to evaluate the degree of approximation of the matrixto [V]_{N×N}re-calculate the sum of squared differences between the elements of the total output matrix of size N×N elements and the elements of the matrix of normalized values of the two-dimensional discrete cosine transform of size N×N elements. Then subtract the resulting sum of squares of a difference from similar amounts received in the previous step. In case of a positive difference, i.e. reduce the standard error, retain the inverted value of the item, and otherwise perform his repeated inversion.

Similarly produce inversion of all bits in m is tricy [E]_{
N×m}and achieve the minimum mean-square error between matricesand [V]_{N×N}that clearly indicates the optimality of the generated matrices [Y(g)]_{N×m}, [X(g)]_{m×N}andandi.e. achieving the best quality at a given fixed amount of transmitted information.

Transmit the set of zero and unit elements of a random rectangular matrix [E]_{N×m}the communication channel (see figure 10). Figure 10 character · denotes matrix multiplication.

At the receiving side is the channel of communication many of the zero and unit elements of a random rectangular matrix [E]_{N×m}. Then calculate the matrix [Y(g)]_{N×m}and [X(g)]_{m×N}by summing modulo 2 matrix [E]_{N×m}the matrix [Y_{CL}(g)]_{N×m}and summation modulo 2 transposed matrix [E]_{N×m}the matrix [X_{CL}(g)]_{m×N}respectively. Then transform matrix [Y(g)]_{N×m}and [X(g)]_{m×N}by dividing the elements of each row of a rectangular matrix of size N×m items in the amount of units of the corresponding row, i.e. the weight of v_{y}(see figa) and dividing the elements of each column of a rectangular matrix of size m×N elements on the amount of units within the relevant column
i.e. the weight of v_{x}(see Figg). Thus, at the receiving side form the matrixand

Form k restored the resulting matrices of size N×Nby successive multiplication of k random rectangular matricesrandom square matrix [B]_{m×m}and k random rectangular matrix(see Fig). Then form the matrix of the restored normalized values of the two-dimensional discrete cosine transform of size N×Nby summing and averaging the k matrices restored the resulting matrices of size N×Naccording to the formula

To obtain the recovered coefficients of real dimension should be done dekorirovaniya. Given that at the receiving side was formed normalization matrix [C]_{N×N}the matrix reconstructed values of the two-dimensional discrete cosine transform of size N×N elements (hereinafter denote it as_{M×M}) formed by dividing the value of each i,j-th element of the matrix
the corresponding element of the normalization matrix of size N×N elements (see Fig).

To recover the transmitted message it is necessary to form the matrix of reconstructed coefficients of two-dimensional discrete cosine transform of size M×M elements (hereinafter denote it as). This operation is carried out by assigning each i,j-th element of the matrix of reconstructed coefficients of two-dimensional discrete cosine transform of size N×N elements each i,j-th element of the matrix of reconstructed coefficients of two-dimensional discrete cosine transform of size M×M elements, as well as other items write zeros (see Fig).

Next, form the matrix of the restored quantized samples fixed grayscale video by multiplying the transposed matrix of the discrete cosine transform of size M×M elements of the matrix of reconstructed coefficients of two-dimensional discrete cosine transform of size M×M elements and a matrix of discrete cosine transform of size M×M elements (see Fig), i.e. on the basis of the formula: [(x,y)]_{M×M}=[G(x,y)]'_{M×M}×[(x,y)]_{M×M}
×[G(x,y)]_{M×M}wherematrix restored quantized samples fixed grayscale video size MHM elements.

At the last stage are the matrixin a still grayscale of the video image by setting each pixel to a fixed grayscale video the value of the corresponding element of the matrix

To assess the possibility of achieving the formulated technical result when using the inventive method of compression and message recovery was conducted simulation on the PC. The size of the random square matrix [B]_{m×m}was 128×128 elements. This size of the matrix [B]_{m×m}chosen on the assumption that the original message used fixed grayscale image of size 512×512 pixels. In the proposed method, a high compression ratio of the original message is achieved due to the fact that formation at the receiving side fixed grayscale video in a digital communication channel, you need to pass the number of binary units, defined by the dimensions of the matrix [E]_{N×m}. To improve noise immunity approach was used, which

based on the method in which opline,
compensation of errors due to the summation and averaging of k images recovered messages, which were formed on the basis of known transmitting and receiving sides of k independent random key matrix and received from the communication channel one matrix [E]_{N×m}thus the accumulation method was implemented without multiple transmission matrix [E]_{N×m}. In the General case, the matrix [E]_{N×m}is rectangular. But during simulation N is taken equal to 128 and m=128. This value of N due to the requirements to the quality of the reconstructed video. Empirical studies show that when leaving 1/16 spectral coefficients of two-dimensional discrete cosine transform of the upper left quadrant of the matrix of coefficients of two-dimensional discrete cosine transform 512×512 elements peak signal-to-noise ratio for the original and the restored video is about 30 dB. During simulation parameter number k was chosen empirically, k=12, the decrease of this parameter leads to a sharp decrease in the compensation of errors. When increasing this parameter, the win is increased slightly, but the quality of the repair fixed the halftone image is reduced.

Reaches the range of the compression ratio can be found by the formula:

Figure 8 in the numerator of the specified formula says that for coding directly fixed grayscale of the video image, i.e. the value of each pixel lies within the range 0÷255, requires 8 bits. When N=128, m=128 and M=512, the resulting compression ratio amounted to 16 times. When using the prototype method for compressing messages resulting ratio was 16 times at peak signal-to-noise ratio of the order of 29.5 dB, but when simulating errors in the communication channel quality of recovery was 16 dB. Objective assessment of the quality of the restored using the inventive method, the video shows that the peak signal-to-noise ratio for the original and the restored video is of 28.4 dB and simulated errors in the communication channel 10^{-2}peak signal-to-noise ratio for the original and the restored video is of the order of 25.8 dB. Received the restored video shown on Fig.

The analysis of computational complexity have shown that the complexity of the proposed procedure coding/decoding is approximately proportional to the value of m^{2}. Therefore, the proposed method of compression and recovery messages can be implemented on modern processors signal processing.

1. The compression method and restored what I messages namely, that pre-on transmitting and receiving sides is identical generate random square matrix of size m×m elements, each element of which belongs to the range -500 ÷ +500, generate k random key matrix of size N×m m×N elements, form the normalization matrix of size N×N items, where C(i, j) is calculated by the formula

where i=1, 2, ..., N, j=1, 2, ..., N, form a matrix of quantized samples fixed grayscale video size M×M elements, where each element of S(x,y) is assigned a quantized value of the corresponding pixel fixed grayscale video size M×M pixels, where x=1, 2, ..., M; I=1, 2, ...,M, form the matrix of coefficients of two-dimensional discrete cosine transform of size M×M elements by successive multiplication of the matrix of the discrete cosine transform of size M×M elements of the matrix of quantized samples fixed grayscale video size M×M elements and the transposed matrix of the discrete cosine transform of size M×M elements, form the matrix of coefficients of two-dimensional discrete cosine transform of size N×N elements, fo the mule A(i,j)=L(i,j),
where L(i,j)-i,j-th element of the matrix of coefficients of two-dimensional discrete cosine transform of size M×M elements A(i,j)-i,j-th element of the matrix of coefficients of two-dimensional discrete cosine transform of size N×N elements, and choose N×M, then form the matrix of normalized values of size N×N elements, by multiplying each coefficient of the matrix of coefficients of two-dimensional discrete cosine transform of size N×N elements A(i,j) to the corresponding element of the normalization matrix of size N×N elements, generate a random rectangular matrix of size N×m elements, and as a random rectangular matrix of size m×N elements take transposed random rectangular matrix of size N×m elements, then each of the key matrices of dimensions N×m m×N elements sum modulo 2, respectively, with direct and transposed random rectangular matrix of dimensions N×m m×N elements of the transform matrix obtained by dividing the elements of each row of a random rectangular matrix of size N×m items in the amount of units of the corresponding row and dividing the elements of each column of a random rectangular matrix of size m×N elements on the amount of units of the corresponding stabs is,
calculate k the resulting matrices V(g), where g=1, 2, ..., k, N×N elements, by successive multiplication of the k transformed random rectangular matrices of size N×m on a random square matrix of size m×m and k of the transformed random rectangular matrices of size m×N elements, sequentially invert each element of random rectangular matrices with dimensions N×m m×N elements, and after inversion transform them by dividing the elements of each row of a random rectangular matrix with inverse element of size N×m items in the amount of units of the corresponding row and dividing the elements of each column of a random rectangular matrix with inverse element size m×N elements on the amount of units of the corresponding column, re-calculate k the resulting matrices of size N×N elements, by successive multiplication of the k transformed random rectangular matrices with inverted element size N×m on a random square matrix of size m×m and k of the transformed random rectangular matrices with inverted element size m×N transmit over the communication channel random rectangular matrix of size N×m, take the link to this matrix, then each of the key matrices of dimensions N×m m×N e the elements of sum modulo 2, respectively, with direct and transposed random rectangular matrices of size N×
m and m×N elements, convert the received random rectangular matrix of size N×m m×N by dividing the elements of each line of a random rectangular matrix of size N×m items in the amount of units of the corresponding row and dividing the elements of each column of a random rectangular matrix of size m×N elements on the amount of units of the corresponding column, calculate k restored the resulting matrices(g)where g=1, 2, ..., k of size N×N elements, by successive multiplication of the k transformed random rectangular matrices of size N×m on a random square matrix of size m×m and k of the transformed random rectangular matrices of size m×N, respectively, the matrix of reconstructed coefficients of size N×N elements complement with zeros to the size of a M×M items, get the matrix of reconstructed coefficients of the discrete cosine transform of size M×M elements, restore the matrix fixed halftone image, by successive multiplication of the transposed matrix of the discrete cosine transform of size M×M elements of the matrix of reconstructed coefficients of two-dimensional discrete cosine transform of size M×M elements and a matrix of discrete cosine of the CSOs transform size M×
M elements, form the digital information signal, each pixel fixed grayscale video assign the value of the corresponding matrix element of the restored quantized samples fixed grayscale images of size M×M elements, characterized in that after calculation of the k resulting matrices, calculate the total matrix size N×N elements of V_{s}by the formula

then calculate the mean square error between the elements of the matrix of normalized values of size N×N elements and elements of the total matrix V_{s}the size of N×N elements, and after the inversion of each element of random rectangular matrices with dimensions N×m m×N re-calculate k of the resulting matrices, the total matrix V_{s}and a root mean square error between the elements of the matrix of normalized values of size N×N elements and elements of the re-calculated total matrix V_{s}size N×N elements, and the resulting RMS error is subtracted from the previous standard error and in the case of a positive difference remember the inverted element, and after calculation of the k recovered resulting matrices(g) calculate restored su the total matrix size N×
N_{s}by the formula

2. The method according to claim 1, characterized in that to obtain the matrix of reconstructed coefficients of size N×N elements convert the recovered total matrix size N×N elements by element-by-element division of its elements to the corresponding elements of the normalization matrix of size N×N elements.

**Same patents:**

FIELD: technology for encoding multimedia objects.

SUBSTANCE: method for encoding a multimedia object includes following stages: multimedia object is encoded for producing a bit stream and information about quality is added to bit stream, while information about quality denotes quality of multimedia object relatively to given position or relatively to given part of bit stream, while information about quality is provided in quality tags, aforementioned quality tag provides a values of quality tag, and value of quality tag characterizes distortion in encoded multimedia object being reproduced, when bit stream is truncated in point, related to quality tag.

EFFECT: development of improved and efficient method/system for encoding multimedia objects.

13 cl, 2 dwg

FIELD: data filtration technologies, in particular, signaling adaptive filtration for lower blocking effect and contour noise.

SUBSTANCE: during forming of frame of blocks of given size, following operations are performed: production of blocking information for decreasing blocking noise and production of contouring information for decreasing contour noise of coefficients of previously given pixels of upper and left threshold areas of data block, when frame, received by decomposition of image data in the stream of binary digits for inverse quantizing is an internal frame, and adaptive filtration of image data passing through inverse quantizing and inverse discontinuous cosine transformation, in accordance to produced blocking information and contouring information. Thus, blocking effect and contouring noise can be removed from image, restored from image on basis of blocks, improving the image restored from compression.

EFFECT: decreased blocking effect and contouring noise of encoding with high compression level.

2 cl, 7 dwg

FIELD: data filtration technologies, in particular, signaling adaptive filtration for lower blocking effect and contour noise.

SUBSTANCE: during forming of frame, following operations are performed: production of blocking information for decreasing blocking noise and production of contouring information for decreasing contouring noise of coefficients of previously given pixels of upper and left threshold areas of data block, when frame, received by decomposition of image data in the stream of binary digits for inverse quantizing is an internal frame, and adaptive filtration of image data passing through inverse quantizing and inverse discontinuous cosine transformation, in accordance to produced blocking information and contouring information. Thus, blocking effect and contouring noise can be removed from image, restored from image on basis of blocks, improving the image restored from compression.

EFFECT: decreased blocking effect and contouring noise of encoding with high compression level.

2 cl, 7 dwg

FIELD: technologies for data filtering.

SUBSTANCE: when a frame is formed of blocks of preset size, following operations are performed: generation of blocking information for decrease of blocking effect and contouring information for decrease of contouring noise from coefficients of preset pixels of upper and left limiting areas of data block, when a frame, received by decomposition of image data in a stream of binary bits for inverse quantizing, is an inner frame, and adaptive filtering of image data, passing through inverse quantizing and inverse discontinuous cosine transformation, in accordance to generated information of blocking and information of contouring. That is why blocking effect and contouring noise can be removed from an image, restored from image on basis of blocks, to improve the image, restored from compression.

EFFECT: decreased blocking effect and contouring noise.

2 cl, 7 dwg

**FIELD: electrical communications; data processing including reduction of data redundancy.**

**SUBSTANCE: proposed process includes similar way of generation of random quadrature matrix measuring m x m items and k random key matrices measuring N x m and m x N items on sending and receiving ends. Then k matrices of quantum readings of motionless gray-level video picture measuring M x M items are formed from k motionless gray-level video pictures which are then converted into product of three following matrices: random rectangular matrix measuring N x m items, random square matrix measuring m x m items, and random rectangular matrix measuring m x N items; in the process items of rectangular matrix measuring N x m items are transferred to communication channel. On receiving end k matrices of recovered quantum readings of motionless gray-level video pictures measuring M x M items are formed around random matrix measuring N x m items received from communication channel, as well as around random quadrature matrix measuring m x m items, and random rectangular matrix measuring m x N items, and motionless gray-level video pictures are produced from mentioned k matrices of recovered quantum readings.**

**EFFECT: enhanced data transfer speed at desired quality of recovered messages.**

**4 cl, 24 dwg**

**FIELD: electrical communications; data processing including reduction of data redundancy.**

**SUBSTANCE: proposed process includes similar way of generation of random quadrature matrix measuring m x m items and k random key matrices measuring N x m and m x N items on sending and receiving ends. Then k matrices of quantum readings of motionless gray-level video picture measuring M x M items are formed from k motionless gray-level video pictures which are then converted into product of three following matrices: random rectangular matrix measuring N x m items, random square matrix measuring m x m items, and random rectangular matrix measuring m x N items; in the process items of rectangular matrix measuring N x m items are transferred to communication channel. On receiving end k matrices of recovered quantum readings of motionless gray-level video pictures measuring M x M items are formed around random matrix measuring N x m items received from communication channel, as well as around random quadrature matrix measuring m x m items, and random rectangular matrix measuring m x N items, and motionless gray-level video pictures are produced from mentioned k matrices of recovered quantum readings.**

**EFFECT: enhanced data transfer speed at desired quality of recovered messages.**

**4 cl, 24 dwg**

FIELD: technologies for data filtering.

SUBSTANCE: when a frame is formed of blocks of preset size, following operations are performed: generation of blocking information for decrease of blocking effect and contouring information for decrease of contouring noise from coefficients of preset pixels of upper and left limiting areas of data block, when a frame, received by decomposition of image data in a stream of binary bits for inverse quantizing, is an inner frame, and adaptive filtering of image data, passing through inverse quantizing and inverse discontinuous cosine transformation, in accordance to generated information of blocking and information of contouring. That is why blocking effect and contouring noise can be removed from an image, restored from image on basis of blocks, to improve the image, restored from compression.

EFFECT: decreased blocking effect and contouring noise.

2 cl, 7 dwg

FIELD: data filtration technologies, in particular, signaling adaptive filtration for lower blocking effect and contour noise.

SUBSTANCE: during forming of frame, following operations are performed: production of blocking information for decreasing blocking noise and production of contouring information for decreasing contouring noise of coefficients of previously given pixels of upper and left threshold areas of data block, when frame, received by decomposition of image data in the stream of binary digits for inverse quantizing is an internal frame, and adaptive filtration of image data passing through inverse quantizing and inverse discontinuous cosine transformation, in accordance to produced blocking information and contouring information. Thus, blocking effect and contouring noise can be removed from image, restored from image on basis of blocks, improving the image restored from compression.

EFFECT: decreased blocking effect and contouring noise of encoding with high compression level.

2 cl, 7 dwg

SUBSTANCE: during forming of frame of blocks of given size, following operations are performed: production of blocking information for decreasing blocking noise and production of contouring information for decreasing contour noise of coefficients of previously given pixels of upper and left threshold areas of data block, when frame, received by decomposition of image data in the stream of binary digits for inverse quantizing is an internal frame, and adaptive filtration of image data passing through inverse quantizing and inverse discontinuous cosine transformation, in accordance to produced blocking information and contouring information. Thus, blocking effect and contouring noise can be removed from image, restored from image on basis of blocks, improving the image restored from compression.

EFFECT: decreased blocking effect and contouring noise of encoding with high compression level.

2 cl, 7 dwg

FIELD: technology for encoding multimedia objects.

SUBSTANCE: method for encoding a multimedia object includes following stages: multimedia object is encoded for producing a bit stream and information about quality is added to bit stream, while information about quality denotes quality of multimedia object relatively to given position or relatively to given part of bit stream, while information about quality is provided in quality tags, aforementioned quality tag provides a values of quality tag, and value of quality tag characterizes distortion in encoded multimedia object being reproduced, when bit stream is truncated in point, related to quality tag.

EFFECT: development of improved and efficient method/system for encoding multimedia objects.

13 cl, 2 dwg

FIELD: electrical communications; data digital computation and processing including reduction of transferred information redundancy.

SUBSTANCE: proposed message compression and recovery method includes pre-generation of random quadrature matrix measuring m x m constituents and k random key matrices measuring N x m and m x N constituents on transmitting and receiving ends, and generation of quantum reading matrix of fixed half-tone video pattern measuring M x M constituents. Matrices obtained are transformed to digital form basing on addition and averaging of A images, each image being presented in the form of product of three matrices, that is, two random rectangular matrices measuring N x m and m x N constituents and one random quadrature matrix measuring m x m constituents. Transferred to communication channel are constituents of rectangular matrix measuring N x m constituents. Matrix of recovered quantum readings of fixed half-tone video pattern measuring M x M constituents is generated basing on rectangular matrix measuring N x m constituents received from communication channel as well as on random quadrature matrix measuring m x m constituents and random rectangular matrix of m x N constituents, and is used to shape fixed half-tone video pattern.

EFFECT: enhanced error resistance in digital communication channel during message compression and recovery.

2 cl, 26 dwg, 1 app

FIELD: video communications, in particular, technology for masking decoder errors.

SUBSTANCE: in accordance to one variant of invention, system and method decode, order and pack video information to video data packets for transfer via communication line with commutated channels, due to which system conceals errors, caused by loss of video data packets, when system receives, unpacks, orders and decodes data packets. In accordance to another variant, system and method decode and pack video information so that adjacent macro-blocks may not be positioned in same data packets. Also, system and method may provide information, accompanying packets of video data for simplification of decoding process. Advantage of described scheme is that errors caused due to data loss are distributed spatially across whole video frame. Therefore, areas of data, surrounding lost macro-blocks, are decoded successfully, and decoder may predict movement vectors and spatial content with high degree of precision.

EFFECT: improved quality of image.

4 cl, 10 dwg

FIELD: method for decreasing visual distortions in frame of digital video signal, which is encoded in blocks and then decoded.

SUBSTANCE: block type is determined in accumulator to encoding method for block, selected in accordance to given set of encoding type. For achieving technical result, i.e. decreasing visual distortions caused by limit of block, filtration is performed in the method, which is carried out depending on frame blocks types around the limit of block.

EFFECT: decreased visual distortions, increased reliability and efficiency.

9 cl, 6 dwg, 2 tbl

FIELD: radio engineering, possible use for digital processing of video signals, transferring the image.

SUBSTANCE: in accordance to the invention, the image being processed is divided on blocks with following transformation of each block using discontinuous quantum transformation, result coefficients are quantized and encoded, supporting points are computed and linear interpolation is performed, while before the stage of supporting point selection, one of the supporting points on edge limit of block is selected and a supporting point on opposite limit block is calculated using additional low frequency filters, after that linear interpolation is performed between thus computed supporting points.

EFFECT: improved quality of compressed video image with insignificant CPU resource costs.

2 cl, 4 dwg

FIELD: engineering of systems for encoding digital video signals, in particular, indication of values of quantization parameters in video encoding system.

SUBSTANCE: method and device for encoding a digital video series are claimed, where indication of quantization parameter is given out in encoded bit stream for use during decoding. Indication of information concerning the quantization parameter is ensured by insertion of SQP value - series level quantization parameter value. In particular, instead of encoding absolute values of parameters of quantization of image/section, indication of difference ΔQP between series level quantization parameter SQP and QP of image/section, is given out.

EFFECT: increased efficiency when encoding digital video signals and reduced speed of data transmission in bits.

4 cl, 8 dwg