# The way search motion vectors parts in the dynamic image based on the two-dimensional discrete spectral transformations

The invention relates to a video system technology. Its application in digital encoding devices allows to obtain a technical result in higher quality playback of fast moving parts by reducing the number of computational operations and increase the search area of the motion vectors of the parts in the dynamic images. The method includes converting a sequence of frames of images in digital form, storing the discrete samples of the pixels of the current and reference frames, split the current frame into blocks and the search for a motion vector of each block of the current frame relative to the reference frame by minimizing the checksum of the block, i.e., the sum of the norms elementwise difference levels, characterizing the terrain blocks in frames. The technical result is due to the fact that as levels, characterizing the topography of the block in the current frame, choose some maximum coefficients of two-dimensional discrete spectral conversion block in the current frame, and as levels, characterizing the topography of the block in the reference frame, select the corresponding coefficients of the discrete spectral transform the General invention relates to a video system technology and may find application in the design and implementation of digital encoding devices for video telephony, video conferencing, digital television broadcasting standard and high definition, and more particularly to a method of searching motion vectors parts in the dynamic images.

There are many ways of analyzing the motion vectors of the parts in the dynamic images. The easiest and most accurate way is to search motion vectors of the macroblocks based on the algorithm of exhaustive search (K. R. Rao and J. J. Hwang, "Techniques and Standards for Image, Video and Audio Coding", 1996, Prentice-Hall PTR, ISBN 0-13-309907-5, pages 89-91). According to the method for searching for the motion vector V=(V_{x}V_{y}) is considered the norm of the difference (SAD) of the luminance signal of the two macroblocks in the current and reference (adjacent time frames with a shift on the motion vector.

Here f is the brightness value, (x,y) spatial coordinates of a point in frame t is the time index of the current frame, t-t is the time index of the reference frame, the sum is performed on all pixels of the macroblock C.

The value of V for which the norm has the smallest SAD value is the desired vector. The motion vectors are searched by brute force in a limited neighborhood: min<V_{x}V_{y}< max.

In this spacedata x and y required order 3·256·(2N+1)^{2}operations. In terms of one pixel of the macroblock requires 3·(2N+1)^{2}operations that, when the search area is within ±16 (N=16) is quite a significant amount more than 3000 operations per pixel.

This method is usually used as a benchmark for assessing the quality of other ways of finding the motion vectors of the parts in the dynamic images.

The disadvantage of this method is the required large number of computational operations and consequently poor performance.

The closest in technical essence to the claimed technical solution is the way to search motion vectors parts in dynamic images (RF Patent No. 2182727 from 20.05.2002, G 06 K 9/00, G 06 T 7/20), including the conversion of a sequence of frames of images in digital form, storing the discrete samples of the pixels of the current and neighboring time (reference) frames, split the current frame into macroblocks and search motion vector for each macroblock of the current frame relative to the reference frame by minimizing this variety of motion vectors checksum of the given macroblock, is the sum of the norms of the pixel difference between the current and reference katale values of the macroblock, and mentioned the checksum is calculated only for the selected reference pixels, and the coordinates of the selected pixels in the macroblock is determined using the values of all the pixels of the macroblock.

The present of the invention is to provide a method of searching motion vectors parts in dynamic images, allowing to reduce the number of computational operations with relatively large (N>16) search areas. This will reduce the complexity of the device to calculate motion vectors at the hardware level, to improve the performance of the coding device and, consequently, search traffic details dynamic images in large areas, reducing the amount of compressed data and improving the quality of the playback moving parts.

This problem is solved by way of search motion vectors parts in dynamic images based on the discrete two-dimensional spectral conversion, including converting a sequence of frames of images in digital form, storing the discrete samples of the pixels of the current and reference frames, split the current frame into blocks and the search for a motion vector of each block of the current is of the checksum of the block, is the sum of the norms elementwise difference a small number of levels, characterizing the topography of the blocks in the current and reference frames, whereas the levels characterizing the topography of the block in the current frame, is the choice of several maximum coefficients of two-dimensional discrete spectral (cosine, Hadamard, etc) conversion block in the current frame, and as levels, characterizing the topography of the block in the reference frame, selects the corresponding coefficients of the discrete cosine transform block in the reference frame.

Hereinafter the present invention will be further disclosed by a more detailed description of the method of searching motion vectors parts in the dynamic image based on the DCT, devices that implement the inventive method, and explanatory drawings.

In Fig.1 shows a block diagram of a device for implementing the method of searching motion vectors parts in the dynamic image based on the two-dimensional discrete spectral transformations.

Fig.2 shows the average distribution of energy in the spectrum of the discrete cosine transform 8×8 on its frequency coefficients.

In Fig.3 shows a plot of Sredna taken to restore maximum coefficients of DCT blocks of 8×8 pixels.

Fig.4(a) shows comparative data on the quality of the search and motion compensation blocks 8×8 pixels between the direct method (SAD) and the method based on the DCT blocks of 8×8 pixels with different number of coefficients for video sequences “Football”.

Fig.4(b) shows comparative data on the quality of the search and motion compensation blocks 8×8 between the direct method (SAD) and the method based on DCT 8×8 with different number of coefficients for the video sequence “flower Garden”.

The block diagram of the device search motion vectors shown in Fig.1 and contains connected to input 1 in parallel, the synchronization unit 2 and connected in series analog-digital Converter 3, scheme 4 brightness signal, connected in series memory block 5 of the current frame and the block of memory 6 of the supporting frame connected to the outputs of the memory block of the current frame connected in series, the memory unit 7 of the current block, the block of calculation of the spectral conversion 8, the memory block of transform coefficients of the current block, the block search index N of the maximum conversion factors 10, the memory block of the reference block 11, block calculate the spectral transformation 12, the memory block CoE coefficients 14, the minimum search block checksum 15, the memory block motion vectors 16, the outputs of the synchronization unit 2 is connected to the control inputs of units 3 and 4, as well as through the control unit 17 inputs the synchronization operation blocks 5-16.

In this way the reduction of the computational cost is achieved due to the more compact representation of the blocks. Information about the unit's storage by using part of its spectral coefficients of the transformation. As the spectral conversion you can use a two-dimensional discrete cosine transform (DCT), a two-dimensional Hadamard transform, and others.

Consider as an example two-dimensional discrete cosine transformation.

Since DCT is a linear operation and the signal energy equal to the energy of the DCT spectrum of this signal, the comparison of the two signals using regenerational measures in spatial domain and frequency domain equivalent. This allows the use of the frequency components of the DCT to search for correlations between blocks.

As can be seen from Fig.2, on average, the energy distribution of the spectrum DCT has a substantially uneven concentration of energy in the low frequencies. From this it follows that PE is that in most cases will be low. Selection of the most significant factors can be carried out on the basis of several largest absolute values of the coefficients.

In Fig.3 shows the average dependence of the accuracy of the recovery unit by using the inverse DCT on the length of the signature number of the most significant coefficients of the DCT blocks of 8×8 pixels). As can be seen from the graph of Fig.3, to a good approximation it is enough to have 8-16 DCT coefficients. What similar units should have a similar set to the largest module of coefficients allows us to compare the blocks with each other only by a small General the selected set of coefficients, thereby reducing the computational cost.

Thus, the task of comparing block from the current block by block from the reference frame consists of nding a similarity measure between a set of several maximum DCT coefficients of one block with the corresponding set (with the same index) DCT coefficients of the second. As a similarity measure, it is advisable to use the sum of absolute differences as the least time-consuming operation:

Here F_{cur}matrix of DCT coefficients of the block in the current frame, F_{ref}matrix of DCT coefficients bioindex spectral coefficients in the transformation matrices the sum is performed over the set of indices FmaxIndx corresponding to multiple maximum coefficients of the matrix F_{cur}. The value of V for which the norm SAD_{dct}has the smallest value, is taken as the desired vector. The motion vectors can be searched by brute force in a limited neighborhood: min <V_{x}V_{y}< max, and any of the known fast search methods: hierarchical, logarithmic spiral, orthogonal and others

As a result, the number of operations in the analysis of similarities blocks compared with the conventional method of pixel-by-pixel subtraction of the two blocks can be reduced to 8 or more times depending on the block size and quantity of recovered transform coefficients. Naturally, a significant part of the computational costs will require DCT, however, it is possible to carry out rapid methods and only once in each frame for all sorts of blocks, and then make the comparison only on the received signatures. In this case, the computational cost of DCT will not depend on the size of the search area of the motion vectors and with relatively large areas (about 32×32 or more) become insignificant as compared to poiska motion vectors from the search area 32×32 compared with the conventional method based on pixel-by-pixel difference between two macroblocks) 4-5 times for blocks of size 8x8 pixels using 8 of 64 DCT coefficients.

In the tables of Fig.4 provides comparative data on the quality of the search and motion compensation for 8x8 blocks of Pickalov between the direct method (SAD) and the method based on the DCT transform for the two test sequences with different number of coefficients (DCT(8/64) - 8 coefficients of the 64 DCT(16/64) - 16 of 64 and so on). A comparison was made between the frames of the original sequence and the recovered frames on detected motion vectors of the respective reference frames of the original sequence. The table shows a quantitative assessment of three measures: the root mean square error (CME), Sredneuralskaya error (MAE) and the signal-to-noise ratio (PSNR).

The comparison results show that these methods when using 8 or more DCT coefficients is slightly inferior in the quality of the reconstructed frames (compensated using the motion vectors for the reference frame) and can successfully be applied in the search for motion vectors.

The device for realization of the proposed method of searching motion vectors is as follows.

To the input 1 of the device (Fig.1) receives the analog image signal, for example a complete color television signal of the standard system signals and provides the formation of the sampling pulses, and analog-to-digital Converter (ADC), in which discrete samples of the signal is converted into a digital code supplied to the selection scheme of the luminance signal 4 that corrects the color subcarriers of the complete color television signal. The selection of the luminance signal is necessary because in accordance with MPEG standards, search traffic details image is carried out only when the luminance of the image. Synchronizing operation of the circuit 4 is also diskretiziruetsya the pulses coming from the synchronization unit 2.

Digital stream of the luminance signal from the circuit 4 sequentially supplied to the memory unit 5 of the current frame and the block of memory 6 of the supporting frame, in which are memorized the discrete samples of the luminance signal of the current frame, the motion search block which is carried out in respect of the relevant structures of the reference frame.

The output unit 5 is connected to the inputs of the block 7 to the memory of the current block, the motion search is. In this unit, remember the values of all pixels of the block.

After calculating the motion vector of the 1st block corresponding to the upper left corner of the image, in memory of this block introduces an array of brightness values sleduiushaia brightness of the block is fed to the input two-dimensional spectral transformations 8.

The resulting transformation matrix is stored in the block 9 and is fed to the input unit 10, where it searches N maximum spectral coefficients and their indexes.

The outputs of the block 6 is connected to the input unit 11 to the memory support unit, which compares the current block. After calculating and comparing the checksum in blocks 14 and 15 in memory of this block introduces an array of brightness values for the next block of the search scope.

In block 12 is made of two-dimensional spectral transformation of the reference block, and the resulting matrix of spectral coefficients stored in the memory block of coefficients 13.

The indexes stored in the block 10, of the memory blocks of coefficients 9 and 13 are extracted N corresponding spectral component and an input unit 14.

In block 14 above them, the computation of the sum rules (checksum) elementwise difference according to the formula

,

where F_{cur}- extracted factors from block 9, F_{cur}- extracted the coefficients of the block 13.

The received checksum is stored in the block 15 and is compared with the following checksum received from the current block and the next oporn the means for the desired vector.

The found motion vector of the current block is stored in the memory block 16 motion vectors.

A gradual transition from block to block in the current frame, forming vectors and choosing appropriate coordinates of the reference blocks and the operations of various units of the device in the above-described sequence is set by the control unit 17, synchronized by pulses from the output of the synchronization unit.

Claims

The way search motion vectors parts in the dynamic image based on the two-dimensional discrete spectral conversion, including converting a sequence of frames of images in digital form, storing the discrete samples of the pixels of the current and reference frames, split the current frame into blocks and the search for a motion vector of each block of the current frame relative to the reference frame by minimizing this variety of motion vectors checksum of the block, which is the sum of the norms elementwise difference a small number of levels, characterizing the topography of the blocks in the current and reference frames, characterized in that the quality levels that characterize the topography of the block in centralnego conversion block in the current frame, and as levels, characterizing the topography of the block in the reference frame, selects the corresponding coefficients of the discrete spectral conversion block in the reference frame.

**Same patents:**

**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

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: 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