RU2656785C1 - Motion estimation through three-dimensional recursive search (3drs) in real time for frame conversion (frc) - Google Patents

Abstract

FIELD: computer engineering.

SUBSTANCE: invention relates to computer engineering. Method for motion estimation in video data comprising a plurality of frames, which comprises determining that the current unit of the frame, for which the motion estimation must be performed, is a double block, wherein the double block being a set of two neighboring frame blocks for which motion estimation has not yet been performed; and estimating the motion vector for the double block, the motion vector estimation step comprises the stages, at which a set containing spatial, temporal and random candidate vectors corresponding to the current double block is obtained, for each candidate vector the value of the trust function is calculated separately for each block of the pair and candidate vectors with the lowest value of the trust function are selected as the estimated motion vectors for the separate blocks of the current double block; and then the next frame unit is estimated; and a set of candidate vectors corresponding to one block from the current double block is used as a set of candidate vectors corresponding to the current double block.

EFFECT: technical result is frame conversion in real time on a mobile device with an improved combination of power consumption, quality and performance.

14 cl, 17 dwg, 1 tbl

Description

FIELD OF THE INVENTION

The present invention relates to video processing, and more specifically to motion estimation for the purpose of converting a video frame rate.

State of the art

Motion estimation is an important part of many algorithms used in video encoding, frame rate conversion (FRC) of video and creating a structure from a moving image (SfM). At the same time, motion estimation algorithms are highly dependent on the tasks assigned, therefore there is no single, universal algorithm that would be equally acceptable for any application. For example, when implementing motion estimation for FRC for video playback on mobile devices, there are some features and difficulties:

- performance limits (real-time operation),

- power consumption restrictions (to avoid a significant reduction in battery life),

- noisy video

- complex movement

- artifacts of movement,

- “twitching” (spasmodic, not smooth) movement.

At the same time, the requirements for motion estimation for FRC are constantly increasing, both in order to improve performance and to meet the increasing needs of users and improve the perception of video. Mobile devices often use video content with a low frame rate - for example, to save memory, reduce the required bandwidth of the Internet traffic channel, or reduce the requirements for the camera. The reproduction of such video content by itself, without additional processing, is not always acceptable for the user, because it may contain visible jerks and smooth movement. Thus, to increase the smoothness of motion in the reproduced video, an increase in the frame rate is necessary. At the same time, the FRC algorithm must satisfy the following requirements:

- noise resistance

- high speed

- proximity to the real movement,

- multithreading,

- mobility,

- work in real time,

- low power consumption.

In light of the above difficulties and requirements, good results for FRC are demonstrated by the 3D recursive search (3DRS) approach described in US Pat. scanning (104), called "meander" due to the similarity of the scanning path of the blocks of the frame with the meander (Fig. 1). The search results are stored in the ring buffer memory with a control unit adapted to the meander scan order when receiving the motion vector and the scan raster order (106) when the motion vector is output for the motion compensation unit (MC). The ring buffer supports the required amount of memory. However, this solution does not provide increased performance in the currently widely used multi-core systems.

In a slightly later solution, which is described in US Pat. No. 8,265,160 B2 (September 11, 2012, NXP BV), the meander scan order of the 3DRS search is divided into separate parts for individual processing streams, so that together these parts form a meander (Fig. 2 ) Motion estimation (ME) is performed for each of the individual parts at the same time. Several parallel threads increase computational performance when evaluating motion in multi-core systems. However, there are also a number of disadvantages to this approach. Firstly, the fact that the direction of scanning blocks in neighboring parts is opposite, leads to non-local access to memory, which leads to reduced performance. Secondly, the movement of odd and even block lines spreads from different directions, which can cause an “interlaced” effect at the boundaries of objects. Thirdly, in only one stream (stream ME1 and block A in Fig. 2), the basis for evaluating the movement are blocks adjacent to the current block, while in the remaining streams (streams ME2-ME4 and blocks B, C, D in FIG. . 2) instead of some adjacent blocks, blocks that are some distance from the current block are used for evaluation, which invariably leads to errors. Fourthly, motion estimation in some flows (ME2-ME4 flows in Fig. 2) is based on an assessment already made in other flows, which implies the need for strict synchronization of flows among themselves and the inability to make their processing completely independent, which is why performance is also declining.

There is also a solution described in US Pat. No. 6,996,177 B1 (02/07/2006, Koninklijke Philips Electronics NV), which approaches the objectives in a slightly different way and in which 3DRS motion estimation is performed using block motion estimation (BME) and global motion estimation (GME ) (Fig. 3). The GME uses motion vector statistics from the BME and provides candidate global motion vectors for the BME. However, this solution uses too simple statistics to estimate global movement (the first and second most frequently used motion vectors obtained using BME are taken), which is not enough to obtain a qualitative result. In addition, in this solution, the GME result is applied to the entire frame, while there are often cases when one or two global motion vectors are not suitable for different parts of the frame, as a result of which artifacts occur during the frame rate conversion, since the obtained motion fields do not correspond real fields of motion.

Thus, in the field of 3DRS motion estimation for FRC purposes in mobile devices, there are the following technical problems: relatively high computational complexity, inefficient memory access scheme, problematic or impossible parallelization, insufficiently detailed detection of global motion and its slow propagation.

SUMMARY OF THE INVENTION

In order to eliminate or mitigate at least some of the aforementioned disadvantages of the prior art, the present invention is directed to the creation of real-time three-dimensional recursive search (3DRS) motion estimation methods for frame rate conversion (FRC) and devices implementing these methods.

In one aspect of the present invention, there is disclosed a motion estimation method in video data containing a plurality of frames, comprising the steps of: determining that the current unit of the frame for which the motion estimation is to be performed is a double block, the double block being a set of two adjacent frame blocks for which motion estimation has not yet been performed; and evaluating the motion vector for the double block, the step of estimating the motion vector comprises the steps of: obtaining a set containing spatial, temporal and random candidate vectors corresponding to the current double block, calculating the value of the confidence function for each block separately for each block pairs, and candidate vectors with the lowest confidence function value are selected as estimated motion vectors for individual blocks of the current double block; and move on to the next unit of the frame; moreover, as a set of candidate vectors corresponding to the current double block, use a set of candidate vectors corresponding to one block from the current double block.

In one embodiment, the method further comprises the steps of: analyzing the values of the confidence function of the selected motion vectors of both blocks in a double block; decide whether it is required to evaluate the motion vector of another single block from a pair of blocks separately, based on the analysis; if it is decided that it is not necessary to process the second block of the current unit separately, then the best candidate vectors are assigned as estimated motion vectors for blocks of the current double block; and move on to the next unit of the frame.

In one embodiment, if a decision is made that it is necessary to process the second block of the current unit as a separate single block, then the best candidate vector for the first block is assigned as the estimated motion vector for the first block; evaluate the motion vector for another block from the current double block separately; and move on to the next unit of the frame.

In one embodiment, the motion vector estimate for said other block from the current double block comprises the steps of: obtaining a set containing spatial, temporal, and random candidate vectors corresponding to said other block from the current double block, calculating for each candidate vector the value of the confidence function, and the candidate vector with the smallest value of the confidence function is selected as the estimated motion vector for said other block from the current double block.

In one embodiment, the analysis of the values of the confidence function comprises the steps of: calculating a modulus of the difference between the value of the confidence function for said one block from the current double block and the value of the confidence function for another block from the current double block; and comparing the calculated modulus difference with a predetermined first threshold value.

In one embodiment, a decision is made that it is necessary to process another block of the current unit separately if the computed module has a difference greater than or equal to the first threshold value.

In one embodiment, the analysis of the values of the confidence function comprises the step of: comparing the value of the confidence function for another block from the current double block with a predetermined second threshold value.

In one embodiment, a decision is made that it is necessary to process another block of the current unit separately if the value of the trust function for another block from the current double block is higher or equal to the second threshold value.

In one embodiment, the selection of temporary candidate vectors when evaluating the forward motion field for the current frame is made from the inverted backward motion field estimated for the previous pair of frames, the selection of temporary candidate vectors when evaluating the backward motion field for the current frame is made from the inverted projected motion field forward rated for the current pair of frames.

In one embodiment, the motion field projection step comprises the steps of: selecting a motion vector for the current block of the projected motion field, writing the value of the selected motion vector to the block of the projected motion field, while the coordinates of this block are closest to the sum of the coordinates of the current block of the projected field motion and selected motion vector.

In another aspect of the present invention, there is disclosed a motion estimation method in video data containing a plurality of frames, comprising the steps of: determining a current unit of a frame for which a motion estimation should be performed; evaluating the motion vector for the current unit of the frame, and the step of evaluating the motion vector contains the stages in which: receive a set containing spatial, temporal and random candidate vectors corresponding to the current unit of the frame, calculate the value of the confidence function for each candidate vector, and select as estimated motion vectors for the current unit of the frame, candidate vectors with the lowest confidence function value; and move on to the next unit of the frame; moreover, the motion estimation is performed in relation to enlarged units of the frame, representing a set of neighboring units in a row, and the bypass of enlarged units of the frame is performed diagonally, starting from one of the corners of the frame, and the motion estimation is performed simultaneously in two or more processing streams, in each of which a single enlarged unit of the frame is processed.

In another aspect of the present invention, there is disclosed a method for estimating motion in video data containing a plurality of frames, comprising the steps of: analyzing a two-dimensional histogram of a previously estimated motion field; selecting SGMV vectors (candidate vectors based on semi-global motion) from said histogram; relative to the current frame, for each selected SGMV vector, a mask active in those parts of the frame where there is movement with the selected SGMV vector; determine the current unit of the frame for which the motion estimation should be performed; evaluating the motion vector for the current unit of the frame, and the step of evaluating the motion vector contains the steps in which: receive a set of candidate vectors corresponding to the current unit of the frame, calculate the value of the confidence function for each candidate vector, and select the estimated motion vectors for the current unit frame candidate vectors with the lowest value of the confidence function; and move on to the next unit of the frame; moreover, the step of obtaining a set of candidate vectors contains stages in which: spatial candidate vectors corresponding to the current unit of the frame are obtained, temporary candidate vectors corresponding to the current frame unit are obtained, random candidate vectors are obtained based on a zero motion vector and / or better on at this moment, candidate vectors corresponding to the current unit of the frame and random SGMV candidate vectors corresponding to the current unit of the frame and the composed mask are received.

In one embodiment, the step of obtaining random SGMV vectors comprises the step of: adding at least one random candidate vector to the set of candidate vectors for the current unit, obtained by adding a random offset to the SGMV vector whose mask is active in the current unit.

In one embodiment, the calculation of the confidence function comprises the steps of: calculating the MAD (average absolute difference) of the candidate vectors between the current block and the block pointed to by the candidate vector, calculating the final penalty function, and the final penalty function is the minimum of the penalty functions for all SGMV vectors, and the penalty functions depend on the distance between the candidate vector and the SGMV vector under consideration, and the penalty function is an increasing function bounded above, and you calculate the value of the confidence function by adding the MAD and the value of the total penalty function.

The present invention provides software for real-time frame rate conversion on a mobile device, which has a more efficient combination of power consumption, quality and performance compared to the prior art.

Improving efficiency is achieved through three key factors:

1) the processing is carried out in double blocks, that is, two blocks at once, which reduces the computational complexity of 3DRS and improves the memory access pattern,

2) execution of processing along the enlarged wavefront, which allows for a relatively high degree of parallelization (up to dozens of threads), and improves the memory access pattern,

3) the selection of candidates on the basis of semi-global movement, which allows for quick capture of several large objects with different movement and thereby improve the quality of the motion assessment.

Brief Description of the Drawings

FIG. 1-3 are solutions known in the art for 3DRS motion estimation.

FIG. 4 - Neighboring blocks containing candidate vectors used to form a set of candidate vectors for each of two neighboring blocks separately (basic 3DRS)

FIG. 5 is a diagram of the use of previously estimated motion fields when evaluating next motion fields.

FIG. 6 - blocks containing candidate vectors considered for a double block (advanced 3DRS)

FIG. 7 is a block diagram of an embodiment of a 3DRS search according to the present invention.

FIG. 8 is a traditional 3DRS with a full-frame meander scan order.

FIG. 9-3DRS with a scan order known as wavefront (or hyperplane) processing.

FIG. 10-3DRS with scan order according to the present invention.

FIG. 11 - An example of a scan order with an enlarged unit of three double blocks.

FIG. 12 - reverse order of frame scan.

FIG. 13 is another embodiment of a frame scan order.

FIG. 14-3DRS using additional semi-global candidate candidate vectors.

FIG. 15A-15C is an example of a semi-global motion application.

Detailed description

The present invention is based on a 3D recursive search (3DRS) algorithm. The algorithm searches for a block field of motion using sequential iterations over a pair of frames of a video sequence.

It should be understood that a motion field is a set of motion vectors, where each of the motion vectors is mapped to either each pixel (dense motion field) or a block of pixels (usually a square or rectangle of adjacent pixels) of the current frame. In the present invention, motion vectors belonging to the blocks are used, and accordingly, block motion fields are used.

The motion vector is the offset (two coordinates) between the blocks of the current and another frame. This offset can have both pixel accuracy and fractional pixel accuracy. Thus, each motion vector always points to some other frame. Accordingly, the motion field always implies the presence of two frames - the current and some other (for example, the next in time or the previous in time).

When evaluating the movement for each block, several candidate vectors are checked, that is, possible vectors that can serve as the basis for the resulting assessment. The candidate vector that has the best rating becomes the motion vector for the current block. The simplest set of candidates is all possible offsets available in the frame, but such a set is too large (if the accuracy of the motion vector is one pixel, then the full set of candidates will be equal to the number of pixels in the frame). In the 3DRS 1993 approach described in deHaan G., Biezen P, Huijgen H., Ojo O.A. True-Motion Estimation with 3-D Recursive Search Block Matching. IEEE Transactions on Curcuits and Systems for Video Technology Vol. 3, No. 5 (1993), a principle was proposed for the formation of a set of candidates in which the power of the set usually does not exceed a dozen candidate vectors.

When compiling a set of candidate vectors for the current block, we use both previously estimated motion vectors from neighboring blocks of the current motion field (the so-called spatial candidate vectors) and motion vectors belonging to some previously entirely calculated motion field (the so-called time vectors candidates). In addition, random offsets relative to the zero offset and random offsets relative to some other candidate vector (the so-called random candidate vectors) can be used. Also, global motion vectors can be included in the candidate set if global motion estimation is used (they can be called global candidate vectors). Random biases can also be added to global candidate vectors to obtain random candidate vectors.

The traditional (basic) 3DRS approach is more clearly shown in FIG. 4. As can be seen from the example in FIG. 4, a set of candidate vectors is generated for each block separately. For example, for block A (10), spatial candidate vectors are selected from blocks 1, 3, 5, 7, 9 in the current field of motion, and temporary candidate vectors are selected from blocks A (10), B (11), 13, 15 in the previously entirely computed motion field, that is, a total of 9 candidate vectors. In turn, for block B (11), spatial candidate vectors are selected from blocks 2, 4, 6, 8, A (10) in the current motion field, and temporary candidate vectors are selected from blocks B (11), 12, 14 , 16 in the previously entirely calculated motion field, that is, in total, there are also 9 candidate vectors.

The definition of blocks from which candidate vectors will be selected is performed according to the following rules.

1. The shape (pattern) of the arrangement of blocks must be such that the already estimated movement arrives at the current block from different directions, which (under certain conditions) provides the fastest convergence of the motion vector estimate to the real movement. This is the basic principle of 3DRS. At the moment, specialists in this field know many different patterns that satisfy this principle. For the purposes of the present invention, any suitable template may be selected.

2. The blocks from which the candidate temporary vectors are selected are located in that part of the current motion field where the motion vectors have not yet been estimated. Therefore, the previous motion field is used.

In FIG. 5 shows in more detail which previously estimated and current motion fields are used in the present invention to sample candidate temporal vectors.

According to the present invention, a forward motion field (FW) and a backward motion field (BW) are estimated for each pair of frames. A forward field (FW <N>) is a set of motion vectors for the current frame N, which are indicated in the next frame N + 1. The backward field (BW <N-1>) is a set of motion vectors for the current frame N, which indicate the previous frame N-1. When evaluating the forward motion field FW <N>, the selection of temporary candidates is made from the inverted (that is, taken with the opposite sign) backward motion field BW <N-1>, estimated for the previous pair of frames (N-1, N). When evaluating the backward motion field BW <N>, the selection of temporary candidates is made from the inverted projected forward motion field FW <N> estimated for the current pair of frames (N, N + 1).

The process of projecting a motion field contains the following steps: selecting a motion vector for the current block of the projected motion field and writing the value of the selected motion vector to the block of the projected motion field, the coordinates of this block being closest to the sum of the coordinates of the current block of the projected motion field and the selected motion vector.

To evaluate the backward field vectors BW <N> in the present invention, semi-global candidate vectors evaluated using the forward forward field FW <N> are used. More about this will be mentioned in the third aspect of the invention.

The first aspect of the invention

Unlike the traditional approach, the unit being processed in the method according to the present invention is a double block. A double block is a pair of neighboring blocks that are processed together. Only one set of candidate vectors is used for a double block, and each candidate vector is evaluated in one iteration of the cycle of traversing candidate vectors for both blocks of a pair at a time, which reduces computational overhead. In particular, in the example of FIG. 6, block A and block B are considered simultaneously in the framework of double block AB. For the double block AB, spatial candidate vectors are selected from blocks 1, 3, 5, 7, 9, and temporary candidate vectors are selected from blocks A (10), B (11), 13, 15, that is, a total of 9 blocks candidates. In essence, these are the same 9 candidate blocks that would have been considered in the traditional approach for a single block A. Thus, the number of sources of spatial and temporal candidates in the example shown is two times less than in the case of single blocks, the processing of which is shown in FIG. 4. As will be explained below, consideration of additional candidates for the second block of a pair (block B candidates) occurs only if the values of the PD confidence functions (MVcand, block) for a pair of blocks of a double block correspond to certain conditions (if there is a suspicion of a border )

It should also be noted that in terms of determining the blocks from which the spatial candidate vectors will be selected, in the present invention, the condition for the rightmost block to be absent at and beyond the wave front should be satisfied (since at the wave front and behind the wave front the vectors in the current field of motion not yet rated).

In FIG. 7 is a flowchart of an embodiment of a 3DRS search motion estimation method according to the present invention.

At step 100, a set of candidate vectors is generated by setting a set of retrieval rules so that it is subsequently possible to obtain another candidate vector for the current (considered) unit of the frame. Except in some cases, which will be explained below, such a unit is a double block. For example, as shown in FIG. 6, for the double block AB under consideration, the candidate vector from block 1 is first selected. The mentioned receipt rules are the same for all units of the frame and can be different for the backward and forward fields.

There are many different options for creating a set of retrieval rules. An example of a simple retrieval rule may be the following: take as a candidate vector a previously estimated vector from an adjacent block of the frame. In order to accurately identify the neighboring block, it is necessary to indicate the shift in block coordinates relative to the current block. An example of a more complex rule can be the following: take random displacements in the range [-3..3] along the x coordinate and in the range [-2..2] along the y coordinate as a candidate vector.

In more detail, a rule set can contain one or more of the following rules (the scanning order is meant from left to right, from top to bottom):

1) Take the estimated motion vector from the block of the previous motion field, the coordinates of which are equal to the coordinates of the current unit.

2) Take the estimated motion vector from the block of the estimated motion field, the coordinates of which are equal to the coordinates of the current unit plus an offset to the left by one block.

3) Take the estimated motion vector from the block of the estimated motion field, the coordinates of which are equal to the coordinates of the current unit plus an upward shift by one block.

4) Take the estimated motion vector from the block of the previous motion field, the coordinates of which are equal to the coordinates of the current unit plus an offset to the right by one block.

5) Take the estimated motion vector from the block of the previous motion field, the coordinates of which are equal to the coordinates of the current unit plus an offset down one block.

6) Take a random offset in the XY range: [-3..3] [- 2..2]

7) Take the best candidate vector from previously estimated and add to it a random offset in the XY range: [-3..3] [- 2..2].

The above list contains 7 rules; accordingly, for each unit of the frame, a maximum of 7 candidate vectors will be considered (at least 1 if the values of all candidate vectors are equal, since it makes no sense to evaluate the same offset several times). It should be understood that the present invention is not limited to the above specific rules for obtaining, and the specialist in this field will be able to draw up other rules for obtaining, without departing from the essence of the invention.

As a result of the implementation of these rules for obtaining and evaluating candidate vectors obtained by these rules, a set of candidate vectors will be obtained. Rule 7 does not allow the complete formation of a set of candidate vectors before processing the current unit, since it is not known in advance which of the candidate vectors will be the best, and this will become clear only after calculating the confidence function, which will be explained below.

Further, in the present disclosure, the formation of a list of rules will not be described separately, and when describing a set of candidate vectors, it will be assumed that it is fully known in advance.

At step 101, the next candidate vector is generated for the current unit of the frame from the set of candidate vectors generated at step 100 based on a given list of receiving rules.

Next, at step 102, the PD is calculated (MVcand, block) for each of the blocks of the unit in question (PD (MVcand, A), PD (MVcand, B)) if the unit in question is a double block, or for a given single block if the unit in question is a single block.

Trust function FD (MVcand, block) = MAD (MVcand, block) + f (Prior, MVcand), where

MAD is the average absolute difference:

f (Prior, MVcand) is a penalty function that uses previously calculated information (Prior) and is used for additional regularization of the motion field. As such previously calculated information, information on global or semi-global movement can serve.

MVcand is the candidate vector in question.

(block) - the coordinates or position of the block (current block) in the current frame.

The higher the value of the PD (), the less confidence in this candidate vector. A lower FD () value means greater confidence in the candidate vector in this block.

At step 103, the candidate vector for each block from the double block is stored in memory as the best if the PD (MVcand, block) has taken a lower value compared to the previously considered candidate vectors for the current block. Moreover, if the best candidate vector has not yet been stored in memory for the unit under consideration, then the current candidate vector is written as the best. When processing subsequent candidate vectors, when the memory contains the best candidate vector, the PD (MVcand, block) of the current candidate vector and the PD (MVcand, block) of the stored best candidate vector are compared with the best candidate vector the candidate vector is retained for which the value of the PD (MVcand, block) is lower. For example, if the candidate vector 1 is already stored in the memory as the best, and the current candidate vector 3 has a smaller PD value (MVcand, block), then the best candidate vector in the memory is overwritten.

At step 104, it is checked whether the obtained candidate vector was the last for the current unit (i.e., the last in a given set of candidate vectors). If not, the method returns to step 101, and the next candidate vector is taken into consideration. If yes, then the method proceeds to the next step, 105. Ultimately, after checking all the candidate vectors for the current unit, the candidate vector with the minimum value of the PD remains in memory (MVcand, block).

At step 105, an analysis of a pair of PD values (MVcand, block) is performed for each of the blocks of the current double block. In this case, the difference d (BA) between the PD (MVcand best B, B) for the second single block from the current unit and the PD (MVcand best A, A) for the first single block from the current unit is calculated. The calculated difference d (BA) is compared with a predetermined difference threshold value T _diff . Exceeding the threshold T _differently shows that the difference between the values of PD (MVcand best B, B) and PD (MVcand best A, A) is large, and this may mean that block A and block B are on the border of movement (belong to objects with different movements ) In addition, in step 105, the PD value (MVcand best B, B) for the second single block from the current unit is compared with a predetermined absolute threshold value T _abs , which indicates whether the PD value (MVcand best B, B) is too large.

It should be noted that when a particular candidate vector is considered, the value of the PD (MVcand, block) is calculated separately for each block of the pair. There are cases when for one block of a pair this value of the PD (MVcand, block1) will be less than for all previous candidate vectors applied to this block of the pair (block1), and then the current candidate vector will become the best for this block of the pair, and at the same time, for the other block of the pair (block2), the value of the PD (MVcand, block2) will be greater than the value of the PD (MVcand best2, block2) for some previously considered candidate vector MVcand best2. Thus, each of the blocks of a pair of blocks may contain different best vectors and values of the confidence function.

At step 106, based on the analysis made at step 105, a decision is made whether to consider the current unit as two separate single blocks, or whether the use of a double block is acceptable for the current application. In particular, the decision that it is necessary to consider two single blocks separately occurs when the value of d (BA) is greater than the value of T _different , and also when the value of the PD (MVcand best B, B) is greater than the value of T _abs . Pre-set values of T _different and T _abs allow you to observe a compromise between the quality of the motion field (in the sense of its proximity to the real motion field) and the speed of the method. That is, if you set relatively high values of T _different and T _abs , then the consideration of additional candidates will occur less frequently, and the speed of the method will increase, but the quality of the motion field may decrease somewhat, and vice versa, if you set the values of T _different and T _abs relative to low, then the consideration of additional candidates will occur more often, and the speed of the method will drop, while the quality of the field of motion can improve.

If at step 106 it was decided that the use of the double block is acceptable, the method proceeds to step 108, where the next unit is transferred (in this case, the double block located next to the current unit (double AB block) in the scanning order) , and in its relation all the above steps of the method are performed, that is, its consideration starts again from step 101.

If, at step 106, it was decided that consideration of two separate single blocks is required, the method proceeds to step 107, where a set of candidate vectors is generated for a single block B, calculation of PD values (MVcand B, B) for each candidate vector and choosing the best of them, that is, one that has a PD value (MVcand B, B) is minimal. After that, the method proceeds to the previously described step 108.

In the proposed method, two neighboring blocks (A and B) at steps 101-104 use a set of candidate vectors for block A (this was also shown above with respect to Fig. 6). This reduces the number of candidate vectors and, therefore, requires fewer PD calculations (), which increases the processing speed. In addition, the memory access pattern is improved. Reducing computational complexity and improving the memory access pattern also leads to lower power consumption.

The second aspect of the invention

In FIG. 8 is a diagram of a scan order divided into double blocks of a frame according to a conventional 3DRS search with a full-frame meander scan order. The usual meander scan order is the order in which the image is divided into lines of blocks, and scanning is done line by line - first the first line in one direction, then the second line in the other direction, etc. This approach makes parallelization impossible, since all previous blocks are in the dependency tree. For example, in FIG. 8 arrows from the current processing unit show which blocks the candidate vectors for the current unit are taken from. Thus, dependencies appear that show which blocks in the frame should already be processed at the time of processing the current unit. In the case of the traditional 3DRS search, all units following the current unit (they are shown in light color) depend on it, and all units preceding the current one must be processed earlier.

In FIG. Figure 9 shows the scanning order of a frame divided into double blocks according to a modification of the 3DRS search known in the prior art, in which the scanning order element is a group of blocks similar to rolling waves - in it the blocks are processed line-by-line, and diagonally, with the blocks in each diagonal being located (and scanned) in the order from right to top - left down.

In particular, the upper left unit (the first diagonal) is processed first, then the right unit adjacent to the upper left (that is, the second unit in the upper row), then the lower unit adjacent to the upper left (that is, the second unit in the left column), due to which it turns out the second diagonal. Next, go to the third unit in the top row, and from it again diagonally left down to the third unit in the left column, resulting in the third diagonal. All subsequent units are processed in the same way, diagonal by diagonal. The processing dependency in this case allows parallel processing. For example, as shown in FIG. 9, the units in the diagonal in bold lines are independent of each other, and therefore can be processed in parallel. However, the order of the processed units is such that the memory access is very fragmented, which inevitably leads to a significant loss in performance relative to the meander or raster scan order.

In FIG. 10 illustrates a scanning order of a double block frame according to the present invention. In the proposed scheme, the frame is conditionally divided into enlarged processing units, which are a set of neighboring units (for example, double blocks) in a row. The scanning order of such enlarged units can be the same as in the above-described wavefront processing method, i.e., the upper left enlarged unit (the first diagonal) is processed first, then the right enlarged unit adjacent to the upper left (that is, the second enlarged unit in the top row) , then the lower enlarged unit adjacent to the upper left (that is, the second enlarged unit in the left column), whereby a second diagonal of enlarged units is obtained, and so on. The processing dependency in this case also allows parallel processing. For example, as shown in FIG. 10, the enlarged units in the diagonal highlighted in bold lines are independent of each other, and therefore can be processed in parallel. At the same time, in comparison with the above-described known wavefront processing method, this method allows using a raster scan order element within a single stream, that is, sequentially processes several units in a row from left to right, which improves the memory access pattern, due to which the general the productivity of the method increases, while lower costs for synchronization of flows are required, and the quality of the motion field does not deteriorate. It should also be noted that memory access is critical to the effectiveness of the processor cache.

In FIG. 11 shows an example of a scan order with an enlarged unit of three double blocks. So, there are three processing streams, in the enlarged unit there is a set of three double blocks in one line. Within each enlarged unit in each thread, double blocks are processed sequentially, that is, access to memory is performed sequentially, more localized. This improves computing performance and reduces power consumption. Moreover, for a large part of the image (diagonal of enlarged units) independent parallel processing is allowed.

In relation to FIG. 8-11, it was described that the unit in question is a double block, however, it should be understood that the unit in question may also be a single block.

Other scanning options for the frame in the wavefront processing method with an enlarged processing unit are also possible. For example, in FIG. 12 shows a bypass scheme in which scanning does not start from the upper left enlarged unit, but from the lower right, that is, scanning is performed in the reverse order. This allows you to alternate the scan order from frame to frame (for one motion field - first from the top left, for the next motion field - first from the bottom right, and so on), and thereby improve the estimated motion field (that is, it becomes more like a real field movement). Since each motion field depends on a previously estimated motion field, and therefore generally on all previously estimated motion fields, the alternation of scan orders improves all motion fields except the very first one evaluated.

Further in FIG. 13 shows a scan order in which, as in FIG. 10-11, the upper left enlarged unit is processed first (the first diagonal), then the right enlarged unit adjacent to the upper left (that is, the second enlarged unit in the top row), then the lower enlarged unit adjacent to the upper left (that is, the second enlarged unit in the left column), whereby a second diagonal of enlarged units is obtained. Then, in contrast to the embodiment shown in FIG. 10-11, there is a transition not to the third enlarged unit in the upper row, but to the third enlarged unit in the left column, that is, directly to the neighboring lower enlarged unit with respect to the last processed unit. Following it, the units in the third enlarged diagonal are processed in order from right to top. Further, in a similar way, after processing the last unit in the third enlarged diagonal, a transition occurs directly to the neighboring enlarged unit, which is at the same time an extreme unit in the next, fourth enlarged diagonal. This version of the frame bypass provides even fewer hopping transitions within the frame, which allows even better to localize access to memory and improve the performance of the method.

The third aspect of the invention

In FIG. 14 shows yet another embodiment of the present invention in which additional semi-global motion candidate vectors are used in the 3DRS algorithm. In particular, in the set of candidate vectors, in addition to spatial candidate vectors from the current motion field and temporary candidate vectors from the previous motion field, additional candidate vectors obtained based on the estimated semi-global motion in the previous motion field are included.

To obtain additional candidate vectors, a two-dimensional histogram of the field of the previous movement is analyzed, and SGMV vectors (semi-global motion vectors) are extracted from it, step 109. For example, the coordinates of several peaks of a two-dimensional histogram can be selected as such vectors. An applicability mask is constructed for each SGMV vector, showing in which parts of the frame movement with such a vector can be present. In the framework of the present invention, it is considered that the mask for a given SGMV vector is active in a given unit if it is decided that movement corresponding to the SGMV vector may be present in this unit.

Further, during the passage of the cycle of steps 101-104, if the current unit (block or double block) falls into the region of the applicability mask of one or another SGMV vector, then this SGMV vector serves as the basis for an additional random candidate vector, which is included in the set candidates for this unit. In this case, a random offset is added to the SGMV vector, and the resulting random candidate vector is added to the set of candidate vectors. This is done for each SGMV vector whose applicability mask indicates the possible presence of this semi-global motion vector in the current unit.

For candidate vectors that are far (in the sense of the distance between the vectors calculated by any convenient method) from the nearest SGMV candidate found, an additional penalty is given at step 103.

For these purposes, some reasonable monotone penalty function is used, bounded above (VPmax), which decreases as the distance between the current candidate vector and the nearest SGMV vector decreases, reaching zero if the mask of the nearest SGMV vector is active, and some value (VPmin ) is greater than zero, but less than the maximum value of this function, if the mask of the nearest SGMV-vector is not active.

This acts as a regularization of the field of motion. In contrast to the aforementioned global motion known from the prior art, in which all the found global motion vectors are considered as additional candidate vectors for all units under consideration, in the present invention, only those whose applicability mask coincides with the location are selected as the basis for the additional candidate vectors current unit (i.e. the mask is active). Therefore, the movement in the present invention is called semi-global.

As the final penalty function, the minimum of the penalty functions for all SGMV vectors can be selected. Ultimately, the value of the confidence function can be calculated by adding the MAD and the value of the resulting penalty function.

In FIG. 15A-15C show an example of a semi-global motion application. In particular, in FIG. 15A shows a frame in which the estimated vectors of a previous motion field are shown for each unit in question. Due to the fact that the camera moves along with the rider (watching him), the rider and the horse in the frame remain almost motionless, and their movement as a whole corresponds to the vector SGMV2 = (1,1) (i.e. one pixel to the right, one pixel down ), while the background moves fast, and it generally corresponds to the vector SGMV1 = (8.1). An applicability mask is constructed for each of the vectors SGMV1 and SGMV2, as shown by the overlay of white in FIG. 15B and 15C, respectively.

The use of a PD with a regularizer based on semi-global movement avoids serious errors in the estimation of movement. For example, in cases where there are several objects in the frame moving in different ways, and when within a single mask there are blocks that, with equal success (that is, the MAD for these blocks are the same), several blocks with different shifting from another frame (for example, blocks without textures, which may be erroneously estimated as moving in a different way compared to the surrounding blocks), the use of a PD will lead to the selection of a candidate vector equal to one of the SGMVs that have an active mask in this block.

A complex approach

It should be noted that in one embodiment of the present invention, a complex 3DRS block diagram can be used with double block processing of the frame along the enlarged wavefront and using semi-global motion.

So, in step 109, semi-global motion is extracted from the previous motion field, and an applicability mask is constructed for each SGMV vector. Then, at step 100, a set of candidate vectors for the current unit is generated based on the acquisition rules. After that, the cycle of steps 101-104 is carried out taking into account additional SGMV vectors corresponding to the constructed applicability masks, and using penalty functions to regularize the field of motion. When all candidate vectors are considered for the current unit, the method proceeds to step 105, where the pair of values of the confidence function is analyzed for each of the blocks of the current unit. Based on this analysis, at step 106, it is determined whether processing is necessary for a single block. If such processing is not required, then step 108 is performed, in which the transition to the next unit occurs. If processing for a single block is necessary, then it is performed at step 107, after which step 108 is also performed. Steps 100-108 are executed in parallel in several threads, where a separate enlarged unit is processed in each thread. The enlarged units are circumvented diagonally, starting from one of the corners of the frame.

An integrated approach allows you to take full advantage of the proposed three aspects of the present invention and provides a significant acceleration of motion estimation for FRC without loss of quality.

Application

The motion estimation method of the present invention is software implemented and can be operated in real time on a mobile device for the purpose of converting low-power frame rate. The battery life of a mobile device increases, while the quality of the video being played does not deteriorate.

Examples of use may include, but not limited to, playback of FHD, FHD +, and WQHD content that requires conversion from 15 to 30 or from 30 to 60 frames per second; video communications, webinars, the use of FRC to restore the frame rate in case of losses in the transmission channel; use of slow motion playback - for example, with a 4-fold increase in the frame rate (for example, from 240 to 960) or smooth playback with a 32-fold slowdown.

Moreover, if we consider each aspect of the present invention separately in comparison with the prior art basic implementation of 3DRS with processing by single blocks at a conventional wavefront, you can get the following results on the Galaxy ™ S8 device with a processor frequency set to 1.1 GHz:

- the first aspect, processing with double blocks on a conventional wavefront reduces computational costs by 10-30% in processing speed with a slight decrease in the quality of interpolation (peak signal-to-noise ratio) by less than 0.1 dB.

- the second aspect, processing by single blocks along the enlarged wavefront - reduction of computing costs by 5-10% in processing speed without affecting the quality;

- the third aspect, the processing of single blocks on a normal wavefront using semi-global motion - an increase in PSNR by 0-0.3 dB.

The following is a summary table of measurement results for known 3DRS algorithms and algorithms according to the present invention for the above test.

Table 1

Algorithm Option Test results Time for a couple of frames [ms] The average PSNR on the internal data set [dB] Base 3DRS 22.96 34.73 Single-block processing on a conventional 1T wavefront (1 stream) 31.41 34.24 Single block processing on a conventional 2T wavefront (2 streams) 18.15 34.24 Single block processing along the enlarged wavefront 1T (1 stream) 28.19 34.24 Single block processing along the enlarged wavefront 2T (2 streams) 15.77 34.24 Processing by double blocks on the enlarged wavefront 2T 14.82 34.22 Processing by double blocks along the enlarged wavefront 2T using semi-global motion 15.91 34.61

Claims (64)

1. A method for estimating motion in video data containing multiple frames, comprising the steps of: determining that the current unit of the frame for which the motion estimation is to be performed is a double block, the double block being a set of two adjacent blocks of the frame for which the motion estimation has not yet been performed; and evaluate the motion vector for the double block, and the step of estimating the motion vector contains the stages in which: - get a set containing spatial, temporal and random candidate vectors corresponding to the current double block, - calculate for each candidate vector the value of the confidence function separately for each block of the pair and - candidate vectors with the smallest confidence function value are selected as estimated motion vectors for individual blocks of the current double block; and go to the next unit of the frame; moreover, as a set of candidate vectors corresponding to the current double block, use a set of candidate vectors corresponding to one block from the current double block. 2. The method according to claim 1, additionally containing stages in which: analyze the values of the confidence function of the selected motion vectors of both blocks in a double block; decide whether it is required to evaluate the motion vector of another single block from a pair of blocks separately, based on the analysis; if it is decided that it is not necessary to process the second block of the current unit separately, then the best candidate vectors are assigned as estimated motion vectors for blocks of the current double block; and go to the next unit of the frame. 3. The method according to claim 2, in which, if it is decided that it is necessary to process the second block of the current unit as a separate single block, the best candidate vector for the first block is assigned as the estimated motion vector for the first block; evaluate the motion vector for another block from the current double block separately; and go to the next unit of the frame. 4. The method according to claim 3, in which the estimation of the motion vector for said other block from the current double block comprises the steps of: - get a set containing spatial, temporal and random candidate vectors corresponding to the said other block from the current double block, - calculate for each candidate vector the value of the confidence function and - the candidate vector with the smallest value of the confidence function is selected as the estimated motion vector for said other block from the current double block. 5. The method according to claim 2, in which the analysis of the values of the confidence function contains the stages in which: calculating a difference module between the value of the confidence function for said one block from the current double block and the value of the confidence function for another block from the current double block; and comparing the calculated difference modulus with a predetermined first threshold value. 6. The method according to claim 5, in which they decide that it is necessary to process another block of the current unit separately if the calculated difference modulus is higher or equal to the first threshold value. 7. The method according to claim 2, in which the analysis of the values of the confidence function comprises the step of: comparing the value of the confidence function for another block from the current double block with a predefined second threshold value. 8. The method according to claim 7, in which they decide that it is necessary to process another block of the current unit separately if the value of the confidence function for another block from the current double block is higher or equal to the second threshold value. 9. The method according to claim 1, in which: - a selection of temporary candidate vectors when evaluating the forward motion field for the current frame is made from the inverted backward motion field estimated for the previous pair of frames, - a selection of temporary candidate vectors when evaluating the backward motion field for the current frame is made from the inverted projected forward motion field estimated for the current pair of frames. 10. The method according to claim 9, in which the step of projecting the motion field comprises the steps of: - choose a motion vector for the current block of the projected motion field, - write the value of the selected motion vector in the block of the projected motion field, while the coordinates of this block are closest to the sum of the coordinates of the current block of the projected motion field and the selected motion vector. 11. A method for estimating motion in video data containing multiple frames, comprising the steps of: determine the current unit of the frame for which the motion estimation should be performed; evaluate the motion vector for the current unit of the frame, and the step of evaluating the motion vector contains the steps in which: - get a set containing spatial, temporal and random candidate vectors corresponding to the current unit of the frame, - calculate for each candidate vector the value of the confidence function and - candidate vectors with the lowest confidence function value are selected as estimated motion vectors for the current unit of the frame; and go to the next unit of the frame; moreover, the motion estimation is performed in relation to the enlarged units of the frame, which are a set of neighboring units in a row, moreover, bypassing the enlarged units of the frame is performed diagonally, starting from one of the corners of the frame, moreover, motion estimation is performed simultaneously in two or more processing streams, in each of which a separate enlarged unit of the frame is processed. 12. A method for estimating motion in video data containing multiple frames, comprising the steps of: analyze a two-dimensional histogram of a previously estimated motion field; selecting SGMV vectors (candidate vectors based on semi-global motion) from said histogram; relative to the current frame, for each selected SGMV vector, a mask active in those parts of the frame where there is movement with the selected SGMV vector; determine the current unit of the frame for which the motion estimation should be performed; evaluate the motion vector for the current unit of the frame, and the step of evaluating the motion vector contains the steps in which: - receive a set of candidate vectors corresponding to the current unit of the frame, - calculate for each candidate vector the value of the confidence function and - candidate vectors with the lowest confidence function value are selected as estimated motion vectors for the current unit of the frame; and go to the next unit of the frame; moreover, the step of obtaining a set of candidate vectors contains stages in which: - receive candidate spatial vectors corresponding to the current unit of the frame, - receive temporary candidate vectors corresponding to the current unit of the frame, - receive random candidate vectors based on the zero motion vector and / or currently the best candidate vector corresponding to the current unit of the frame, and - receive random SGMV candidate vectors corresponding to the current unit of the frame and the composed mask. 13. The method of claim 12, wherein the step of obtaining random SGMV vectors comprises the step of: - add at least one random candidate vector to the set of candidate vectors for the current unit, obtained by adding a random offset to the SGMV vector whose mask is active in the current unit. 14. The method according to item 12, in which the calculation of the confidence function contains the steps in which: - calculate the MAD (average absolute difference) of the candidate vectors between the current block and the block pointed to by the candidate vector, - calculate the final penalty function, and the final penalty function is the minimum of the penalty functions for all SGMV vectors, and the penalty functions depend on the distance between the candidate vector and the SGMV vector under consideration, and the penalty function is an increasing function bounded above, and - calculate the value of the confidence function by adding the MAD and the value of the total penalty function.

Images