Device and method for fast block-matching motion estimation in video encoders

Abstract

A solution is provided to estimate motion vectors of a video. A multistage motion vector prediction engine is configured to estimate multiple best block-matching motion vectors for each block in each video frame of the video. For each stage of the motion vector estimation for a block of a video frame, the prediction engine selects a test vector form a predictor set of test vectors, computes a rate-distortion optimization (RDO) based metric for the selected test vector, and selects a subset of test vectors as individual best matched motion vectors based on the RDO based metric. The selected individual best matched motion vectors are compared and a total best matched motion vector is selected based on the comparison. The prediction engine selects iteratively applies one or more global matching criteria to the selected best matched motion vector to select a best matched motion vector for the block of pixels.

What is claimed is: 
     
         1 . A non-transitory computer-readable medium for encoding a video, the non-transitory computer-readable medium comprising instructions that when executed cause a processor to:
 receive a video comprising a plurality of video frames, each frame comprising a plurality of blocks;   estimate one or more best block-matching motion vectors of a block of a video frame of the plurality of video frames in a number of stages, the estimating comprising for each stage of the number of stages:
 selecting a center position motion vector as a best matched motion vector by iteratively checking a set of test motion vectors based on a first rate-distortion optimization (RDO)-based metric, the set of test motion vectors expected to include highly reliable predictors based on at least one of a priori knowledge of a video including the video frame and a priori knowledge of a plurality of video sequences stored in a database, the set of test motion vectors comprising one or more of a zero-motion vector, a motion vector predictor (MVP), and one or more individual motion vectors from neighboring blocks adjacent to the block, the MVP being a median of a plurality of motion vectors for a plurality of neighboring blocks adjacent to the block; and 
 iteratively applying one or more global matching criteria to the selected best matched motion vector to select a total best matched motion vector for the block, the iterative applying comprising:
 for each iteration of a plurality of iterations:
 determining whether a candidate total best matched motion vector for the iteration meets one or more first adaptive threshold criteria based on a second RDO-based metric; and 
 responsive to the candidate total best matched motion vector meeting the first adaptive threshold criteria, selecting the candidate total best matched motion vector as the total best matched motion vector and terminating the iterative applying; and 
 
 responsive to none of the candidate total best matched motion vectors meeting the first adaptive threshold criteria during the iterative applying, selecting a final candidate total best matched motion vector from a final iteration of the plurality of iterations as the total best matched motion vector; 
 
   encode the video frame as part of a compressed video stream, the encoded video frame including the selected total best matched motion vector for the block; and   perform at least one of: store the compressed video stream or transmit the compressed video stream.