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

An apparatus for processing video signals through motion estimation of a video sequence comprising:

• a computer readable medium storing the video sequence comprising a plurality of video frames, each frame comprising a plurality of blocks;
• and
• a video signal processor comprising a multistage motion vector prediction engine configured to estimate a plurality of best block-matching motion vectors for each block in each video frame of the video sequence in a number of stages, wherein the estimating comprises:
• for each stage of the number of stages of motion vector estimation for a block of a video frame of the video sequence:
• selecting a test vector from a set of test vectors, wherein the set of test vectors is selected from a plurality of sets of vectors using at least one of a priori knowledge of the video sequence and a priori knowledge of a plurality video sequences stored in a database, and wherein the test vectors of a set of test vectors are arbitrary and sorted based on a distance between each test vector and a median test vector of the set of test vectors and each test vector is unique from other test vectors of the set of the test vectors;
• computing a distortion metric using the selected test vector;
• responsive to the test vector of the set of test vectors meeting a criterion of adaptive threshold criteria based on the computed distortion metric, the adaptive threshold criteria associated with the block of the video frame of the video sequence and derived based on a rate-distortion optimization measure:
• selecting the test vector as an individual best matched motion vector of the set of test vectors;
• and
• skipping motion vector estimation process for the remaining test vectors of the set of test vectors;
• responsive to the test vector of the set of test vectors not meeting a criterion of the adaptive threshold criteria based on the computed distortion metric:
• testing remaining test vectors of the set of test vectors in an order according to corresponding positions of the test vectors in the sorted set of the test vectors;
• and
• selecting a test vectors as an individual best matched motion vector of the set of test vectors based on the distortion metric associated with each test vector, the selected test vector having the minimum distortion among the test vectors;
• comparing the individual best matched motion vectors from the plurality of sets of test vectors to select a total best matched motion vector based on the comparison;
• applying a global threshold criterion to the selected total best matched motion vector;
• responsive to no global threshold criterion being satisfied, refining search area in the proximity of the total best matched motion vector and iteratively searching for best motion vector in the refined search area using additionally defined sets of test vectors and selection criteria;
• selecting a new best matched motion vector based on the search;
• testing the new best matched motion vector based on another global matching criterion;
• and
• accepting the new best matched motion vector responsive to the criterion being satisfied or a defined number of iterations of search being performed.