RU2408160C1 - Method for finding vectors of part movement in dynamic images and device for its realisation - Google Patents

Abstract

FIELD: information technologies.

SUBSTANCE: method to search for vectors of part movement in dynamic images includes the following actions: transformation of image frame sequence into digital form, memorising discrete counts of brightness in current and reference frames, breaking current frame into macroblocks and searching for movement vector of each macroblock of current frame relative to reference frame by means of minimisation of control sum of this macroblock by considered multitude of movement vectors, and this sum is the sum of norms of pixel-by-pixel difference of levels in current and reference frames, the reference macroblock is re-digitised to increase spatial resolution with the help of direct and reverse two-dimensional discrete Fourier transformation and expansion of produced Fourier spectrum with coefficients equal to zero.

EFFECT: increased accuracy of part movement vectors search in dynamic images by spatial coordinates and improved quality of reproduction of quickly moving parts.

2 cl, 8 dwg

Description

The invention relates to the field of video information technology and can find application in the development of digital encoding devices for video telephony, video conferencing, standard and high definition digital television broadcasting.

Terms used below.

The term macroblock of a television image for the MPEG-2 standard can be found in, for example, the Dictionary of Terms “Television and Radio Broadcasting”, authors V. A. Khleborodov, P. P. Oliferenko / edited by prof. M.I. Krivosheeva - "Era", Zhukovsky, 1999, p.21, 76.

The sizes of macroblocks can be different (16 × 16, 8 × 8 pixels). (See, for example, Mandal M.K., Chan E., Panchanathan S. "Multiresolution Motion Estimation Techniques for Video Compression", Optical Engineering, vol. 35, no. 1, pp. 128-136, Jan., 1996).

The term Motion Vector is defined, for example, in K.R. Rao, J.J. Hwang, "Techniques and Standards for Image, Video and Audio Coding", 1996, Prentice-Hall PTR, ISBN 0-13-309907-5.

Many methods are known for analyzing the motion vectors of parts in dynamic images.

The simplest and most accurate way is to search for macroblock motion vectors based on the exhaustive search algorithm (KRRao, JJHwang, "Techniques and Standards for Image, Video and Audio Coding", 1996, Prentice-Hall PTR, ISBN 0-13-309907-5 )

рассматривается норма разницы сигналов яркости двух макроблоков в текущем и опорном кадрах SAD со сдвигом на вектор движения:To search for a motion vector

the norm of the difference of the brightness signals of two macroblocks in the current and reference SAD frames with a shift by the motion vector is considered:

для которого норма SAD имеет наименьшее значение, принимается за искомый вектор. Векторы движения ищутся методом полного перебора в некоторой ограниченной окрестности:Here F is the brightness value, (x, y) are the spatial coordinates of the point in the frame, t is the temporal index of the frame, summation is performed over all points of the macroblock. Value

for which the SAD norm has the least value, is taken as the sought vector. Motion vectors are searched by exhaustive search in some limited neighborhood:

-A <V _x , V _y <A.

This method is usually used as a reference for assessing the quality of other methods for analyzing the motion vectors of parts in dynamic images.

A more effective way of analyzing motion vectors with accuracy to a pixel is the method (A.V. Dvorkovich, V.P. Dvorkovich, Yu.B. Zubarev, A.Yu.Sokolov, RF Patent No. 2137194 “Method for the analysis of motion vectors of parts in dynamic images ”), Which includes converting the sequence of image frames into digital form, storing discrete samples of brightness of the current and neighboring (reference) frames, dividing the current frame into macroblocks, and searching for the motion vector of each of the macroblocks of the current frame relative to the reference frame by minimizing over the considered set of motion vectors the checksum of this macroblock, which is the sum of the norms of the pixel-by-pixel level difference in the current and reference frames, and the said checksum is calculated taking into account the motion vector, that is, when matching the pixels in the current macroblock to the pixels in the search area in the reference frame shifted relative to the position of the pixels of the current macroblock by the estimated motion vector taken with the opposite sign.

The limitation of this known method is to find the motion vectors only up to an integer number of pixels horizontally and vertically, while the real motion of the objects in the frame is characterized by non-integer components of the motion vector. This limitation manifests itself in the fact that there are characteristic double contours corresponding to moving objects on the difference signal obtained between the reference and the current frame taking into account the motion vectors found up to an integer number of pixels. The intensity of these contours is proportional to the magnitude of the discarded fractional part of the object’s motion vector and can be reduced by using a reference frame oversampled to increase the clarity.

The closest in technical essence is the method (ISO / IEC 14496-10. ITU-T Recommendation H.264, Geneva, 2008), in which the motion vectors are searched with accuracy to fractions of a pixel, the intermediate points being obtained by linear interpolation, as a result where the values of the calculated samples can differ significantly from the true values, which, in turn, leads to a decrease in the accuracy of the data obtained.

The objective of the present invention is to provide a method for finding the motion vectors of parts in dynamic images and a device for its implementation, which allows to increase the accuracy of oversampling the search area in the reference frame and, accordingly, the accuracy of determining the motion vectors of parts by spatial coordinates and, therefore, to reduce the information entropy of the encoded differential signal and improving the quality of reproduction of fast moving parts with the same stream of encoded data.

To achieve this goal, a method for searching motion vectors of parts in dynamic images according to claim 1 is proposed, including converting a sequence of image frames into digital form, storing discrete samples of brightness of the current and reference frames, dividing the current frame into macroblocks, and searching for the motion vector accurate to an integer number of pixels of each of the macroblocks of the current frame relative to the reference frame by minimizing the considered set of motion vectors to the control sum of this macroblock, which is the sum of the norms of the pixel-by-pixel level difference in the current and reference frames, the reference operations are performed on each pair of reference - the current macroblock:

1) an extension of one pixel from all four sides of the macroblock of the reference frame to obtain the search area of the updated motion vector;

2) the implementation of a two-dimensional discrete Fourier transform (DFT) over the expanded macroblock of the reference frame;

3) changing the resulting matrix of Fourier coefficients by adding zero coefficients to it, corresponding to the values of spatial frequencies exceeding the boundary frequencies of the original macroblock, in such an amount that the changed matrix is N times larger than the original in the respective spatial sizes, both in rows and in columns ;

4) the implementation of the inverse two-dimensional FFT on the changed matrix, which results in a resampled reference macroblock with the number of discrete samples N times larger in rows and columns containing the true values of the image levels at the intermediate points of the samples obtained between the original pixels with increasing spatial resolution in N times horizontally and vertically;

5) refinement of the motion vector by sorting the checksums of the pixel-by-pixel level differences in the current and reference frames, the position of the minimum of which corresponds to the desired specified motion vector.

To implement this method, a device for finding motion vectors of parts in dynamic images is proposed, comprising a series-connected analog-to-digital converter connected to the input of the dynamic image signal, a memory block of the brightness signal of the current frame and a memory block of the reference frame, and also connected to the output of the memory block of the brightness signal of the current the memory block of the current macroblock and the memory block of the motion search area connected to the output of the memory block of the reference frame, the outputs of the blocks The names of the current macroblock and the memory of the current macroblock are connected to the inputs of the motion analysis block up to a pixel, the output of which, as well as the second output of the memory block of the motion search area, is connected to the memory block of the extended reference macroblock, the output of which excludes the discrete Fourier transform block, the block expansion of the Fourier spectrum, a block of the inverse discrete Fourier transform and a block of refined analysis of motion, to the second input of which the second output of the current memory block is connected about the macroblock, and to the third input is the output of integer motion vectors of the motion analysis block accurate to a pixel, while all of these blocks are connected to the control unit.

Figure 1 shows a block diagram of a device for implementing the inventive method of searching for motion vectors of parts in dynamic images.

Figure 2 shows examples of the current (a) and reference frames (b) from the video sequence "Flower Garden".

Figure 3 shows as an example:

- figa - matrix expanded macroblock size 4 × 4 pixels from the reference frame shown in figb;

- fig.3b - matrix of the current macroblock with a size of 2 × 2 pixels from the current frame shown in figa;

- figv - image of the envelope surface of the expanded reference macroblock.

Figure 4 shows:

- figa - matrix of FFT coefficients of the reference extended macroblock;

- figb - a modified matrix of FFT coefficients of the reference macroblock, expanded 4 times in rows and 4 times in columns;

- figv - matrix resampled macroblock;

- Fig.4g - image of the envelope surface of the oversampled reference macroblock.

Figure 5 shows the structural diagram of the expansion of the two-dimensional matrix of Fourier coefficients, carried out by oversampling the reference macroblock.

Figure 6 shows an example of difference frames during motion compensation using integer motion vector (a) and the motion vector calculated with a precision up to _^1/4 pixels (b).

The device shown in figure 1, contains connected to the input of the dynamic image signal 1 in series connected analog-to-digital Converter 2, the memory unit of the brightness signal of the current frame 3 and the memory block of the reference frame 4, connected to the output of the memory unit of the brightness signal of the current frame, the current memory unit the macroblock 5, and the memory block of the motion search area 6 connected to the output of the memory block of the reference frame 4. The outputs of blocks 5 and 6 are connected to the inputs of the motion analysis block accurate to pixel 7, the output of which, as well as The second output of the memory block 6 of the motion search area is connected to the memory block of the extended reference macroblock 8, the output of which is connected in series to the Discrete Fourier Transform block 9, the Fourier spectrum expansion block (add zero coefficients) 10, the Inverse Discrete Fourier Transform block 11, and the refined analysis block motion 12, to the second input of which the second output of the memory block 5 of the current macroblock is connected, and the output of the integer motion vectors of block 7 is connected to the third input. These motion vectors are fed to the output of the device 13. The operation of the device is regulated by the control unit 14.

The essence of the proposed method for finding motion vectors is as follows.

The dynamic image signal from the input of the device 1 (Fig. 1) through an analog-to-digital converter (ADC) 2 is supplied to the brightness signal block of the current frame 3 and through it to the memory block of the reference (for example, the previous) frame 4. We assume that in blocks 3 and 4 the frames of the images shown in figa and figb respectively. Through the memory block of the current macroblock 5 and the memory of the motion search area 6, discrete samples of the corresponding pixels are sent to the motion analysis block accurate to pixel 7, in which, using the standard method, the motion vector is determined with an accuracy of an integer number of pixels.

Next, the step of refining the found motion vector occurs.

In the memory block of the expanded reference macroblock 8, an increase of one pixel from all four sides of the macroblock of the reference frame is performed to obtain the search area of the updated motion vector by reading the necessary data from block 6.

For example, let the correspondence of the position of the current matrix shown in FIG. 3b be found to the center (indicated by a frame in FIG. 3a) extended by one pixel from all four sides of the reference macroblock, and the checksum of the pixel difference is:

SAD = (| 133-132 | + | 133-117 | + | 42-24 | + | 116-171 |) = 1 + 16 + 18 + 55 = 90

Figure 3c shows an image of the envelope surface of this expanded reference macroblock.

The spatial resolution transformation of the sample matrix is explained first with the example of processing a one-dimensional sequence of real samples {x ₀ , x ₁ , ... x _K-1 }, K is an even number:

discrete Fourier transform of a given sequence is determined by the relation:

u=0,…K-1,

u = 0, ... K-1,

Where

The sequences of real and imaginary Fourier coefficients (for even K) are respectively equal:

ReF _u = {Re F ₀ , Re F ₁ , ... Re F _{K / 2-1} , Re F _{k / 2,} Re F _{K / 2 + 1} , ... Re F _K-1 };

ImF _u = {0, Im F ₁ , ... Im F _{K / 2-1} , 0, Im F _{K / 2 + 1} , ... Im F _K-1 }.

Moreover, according to the FFT properties:

Re F _Kk = Re F _k , and Im F _Kk = -Im F _k , k = 1, ... K / 2-1,

so we have:

ReF _u = {Re F ₀ , Re F ₁ , ... Re F _{K / 2-1} , Re F _{K / 2} , Re F _{K / 2-1} , ... Re F ₁ };

lmF _u = {0, Im F ₁ , ... Im F _{K / 2-1} , 0, -Im F _{K / 2-1} , ... -Im F ₁ }.

Dividing the central coefficient F _{K / 2} , corresponding to the boundary frequency, by two and adding between them zeros in the amount of K (N-1) -1, we get:

That is, the formed spectrum contains N times more samples than the initial one.

A resampled sequence {y ₀ , y ₁ , ... _NK-1 } can be obtained by applying the inverse Fourier transform:

k = 0, ... NK-1

,Where

,

moreover, _Nk = x _k , and the number of samples in a given interval increased N times.

In the case of two-dimensional data, the DFT leads to the following relations:

Where

and everywhere u = 0 ... K-1, v = 0 ... K-1.

Having performed an operation for the four component sequences similar to that described above for the one-dimensional model, we can obtain the required expansion of the Fourier spectrum for the two-dimensional case.

Considering that two-dimensional DFT is a separable transformation, it is possible to carry out a one-dimensional operation first, for example, first in rows, and after adding rows with zero coefficients, perform FFT in columns and add rows of zero coefficients in the vertical middle of the resulting matrix, resulting in the required coefficient matrix Fourier.

In the DFT block (block 9 of FIG. 1), the Fourier transform operation of the extended macroblock obtained from the output of block 8 is performed.

The algorithm of these transformations is illustrated in figure 4 and in General form also in figure 5.

The matrix of coefficients of the Fourier spectrum of the expanded macroblock is shown in figa. The expansion of the matrix of FIG. 4a by zero Fourier spectrum coefficients (performed by the Fourier spectrum expansion unit 10 of FIG. 1) is shown in FIG. After the inverse DFT of the matrix of FIG. 4b (this operation is performed in the inverse discrete Fourier transform block 11 of the circuit of FIG. 1), a plurality of samples of the oversampled extended reference macroblock are reproduced, as shown in FIG. 4c, and its envelope surface is shown in FIG. In general terms, the spatial structure of the macroblock extension is illustrated in FIG. 5a, its DFT in FIG. 5 (b, c), and the result of oversampling in FIG. Note that the dimensions of the physical correspondence of the original extended (Fig. 5a) and oversampled (Fig. 5g) macroblocks remain unchanged.

In this case, the expansion of the matrix of Fourier coefficients by adding zero coefficients to them is carried out in accordance with the formulas (the dimensions of the matrix horizontally and vertically must be even):

F1 _ij = F0 _ij for i <n / 2, j <n / 2;

F1 _{i + n · (N-1) j + n · (N-1)} = F0 _ij for i> n / 2, j> n / 2;

F1 _{i + n · (N-1) j} = F0 _ij for i> n / 2, j <n / 2;

F1 _{ij + n · (N-1)} = F0 _ij for i <n / 2, j> n / 2;

F1 _{n / 2j} = F1 _{n / 2 + n · (N-1) j} = 0.5 · F0 _{n / 2j} for j <n / 2;

F1 _{n / 2j + n · (N-1)} = F1 _{n / 2 + n · (N-1) j + n · (N-1)} = 0.5 · F0 _{n / 2j} for j <n / 2;

F1 _{in / 2} = F1 _{in / 2 + n · (N-1)} = 0.5 · F0 _{in / 2} for i <n / 2;

F1 _{i + n · (N-1) n / 2} = F1 _{i + n · (N-1) n / 2 + n · (N-1)} = 0.5 · F0 _{in / 2} for i <n / 2;

F1 _{n / 2 n / 2} = F1 _{n / 2 n / 2 + n · (N-1)} = F1 _{n / 2 + n · (N-1) n / 2} = F1 _{n / 2 + n · (N- 1) n / 2 + n · (N-1)} = 0.25 · F0 _{n / 2 n / 2} ;

F1 _ij = 0 for n / 2 <i <n / 2 + n · (N-1) or n / 2 <j <n / 2 + n · (N-1),

where F0 _ij and F1 _ij are the Fourier coefficients of the two-dimensional DFT over the extended macroblock of the reference frame before and after oversampling, respectively, n is the size of the expanded macroblock (and the matrix of its DFT coefficients) of the reference frame horizontally and vertically, n · N is the size of the expanded macroblock ( and the matrix of its DFT coefficients) of the reference frame horizontally and vertically after oversampling.

Thus, when performing the inverse two-dimensional DFT over the formed matrix, a resampled reference macroblock is created.

Shifting the original current macroblock (Fig. 3b) along the rows and columns by the newly obtained intervals equal to 1 / N-th fractions of the initial inter-pixel distance, calculating the corresponding checksums and then finding the minimum of them, you can get the value of the motion vector with increased accuracy. This operation is performed in the unit of the refined analysis of motion 12 of Fig. 1, after which the refined motion vectors 13 are derived from the device for implementing the proposed method for further receiving differential signals and their compression.

In this example, by estimating the minimum pixel-by-pixel difference, it was found that the motion vector should be shifted relative to the calculated integer number of pixels by -0.5 pixels per row and -0.25 pixels per column. The combination of the samples of the current macroblock depicted in Fig.3b, with the samples of the resampled reference macroblock depicted in Fig.3c, in accordance with the motion vector found to within an integer number of pixels, and in accordance with the motion vector found to an accuracy of a quarter of a pixel , marked in figv highlighting in bold and font, respectively.

In this case, the checksum of the pixel difference is equal to:

SAD = (| 133-132 | + | 133-133 | + | 42-42 | + | 116-106 |) = 1 + 0 + 0 + 10 = 11.

The effect of reducing the informational entropy of the difference signal resulting from motion compensation using the updated motion vectors obtained in the aforementioned manner can be observed in FIG. 6 by comparing images (a) and (b).

With a further increase in the resolution of the support areas of the motion search, one can obtain even greater accuracy in determining motion vectors.

Thus, the implementation of this method of finding the motion vectors of parts in dynamic images using the described device can significantly improve the processing efficiency of digital video sequences.

Figure 1 presents a block diagram of a device for implementing the proposed method.

Figure 2 presents an example of the current (a) and reference (b) frames from the video sequence "Flower Garden".

Figure 3 presents an example of the current and extended reference macroblock.

Figure 4 presents an example of the transformation of the matrix of FFT coefficients of the extended reference macroblock.

Figure 5 presents an example of an expansion scheme of a two-dimensional matrix of Fourier coefficients, implemented for oversampling the reference macroblock.

Figure 6 presents the difference frames in the motion compensation using integer motion vector (a) and the motion vector calculated with a precision up to _^1/4 pixels (b).

List of items

(Figure 1 - Block diagram of a device for implementing the proposed method)

1. Dynamic image signal

2. An analog-to-digital converter (ADC)

3. The memory block of the brightness signal of the current frame

4. The reference frame memory unit

5. The memory block of the current macroblock

6. The memory block of the motion search area

7. The block of the analysis of the movement with an accuracy of a pixel

8. The memory block extended reference macroblock

9. Block of discrete Fourier transform

10. Fourier spectrum expansion unit

11. Block inverse discrete Fourier transform

12. Block refined motion analysis

13. Motion vectors accurate to fractions of a pixel

Claims (2)

1. A method for finding motion vectors of parts in dynamic images, including converting a sequence of image frames into digital form, storing discrete pixel samples of the current and reference frames, dividing the current frame into macroblocks, and searching for the motion vector of each of the macroblocks of the current frame relative to the reference frame by finding the minimum the considered set of motion vectors of the checksum of a given macroblock, which is the mean-square norm of the pixel-by-pixel different between the levels in the current and reference frames, characterized in that the found block in the reference frame, corresponding to a motion vector with an accuracy of one pixel and equal in size to the macroblock in the current frame, is expanded by one pixel from all four sides, a two-dimensional DFT is subjected, the resulting matrix Fourier coefficients is expanded by adding zero coefficients to it, corresponding to the values of spatial frequencies exceeding the boundary frequency of the original macroblock, in such an amount that the resulting matrix is Fourier coefficients is N times larger than the original horizontally and vertically, respectively, then the inverse two-dimensional DFT is performed over the resulting matrix, resulting in the formation of a resampled N-fold with increasing spatial resolution horizontally and vertically reference macroblock, relative to which it is similar to the procedure used in the estimation motion vectors with an accuracy of a pixel, taking into account N times lower resolution of the macroblock of the current frame, differential control systems are calculated We, the position of which corresponds to a minimum proximate the desired motion vector with a precision up to 1 / N of pixels horizontally and vertically. 2. A device for locating parts motion vectors in dynamic images, comprising an analog-to-digital converter connected to the input of the dynamic image signal, a luminance signal memory block of the current frame and a reference frame memory block, and a memory block connected to the output of the luminance signal memory block of the current frame the current macroblock and the memory block of the motion search area connected to the output of the memory block of the reference frame, the outputs of the memory blocks of the current macroblock and the memory of the current ma the croblock are connected to the inputs of the motion analysis block accurate to a pixel, the output of which, as well as the second output of the memory block of the motion search area, is connected to the memory block of the expanded reference macroblock, the output of which is connected in series to the discrete Fourier transform block, the Fourier spectrum expansion block, the inverse block discrete Fourier transform and refined motion analysis unit, to the second input of which the second output of the current macroblock memory unit is connected, and the integer output is connected to the third input pixel motion vectors of a motion analysis block accurate to a pixel.

Images