Motion Estimation Complexity Reduction

A method for reducing the computation in motion estimation for a target block in motion estimation comprising:

• a) creating a nested sequence of patterns(i, j) (i=0, 1, 2, . . . , N−1) for the search region candidate (SRC), j;
• b) initialization:
• setting i=0, j=0;
• calculating the distortion between the target block for all the patterns(i, 0), i=0, 1, 2, . . . , N−1;
• setting patterns(i, best)=patterns(i, 0), for all i's;
• c) moving to next search area candidate, j=j+1;
• d) setting i=0;
• e) calculating the distortion, D, between the target block and the patterns(i,j) of the said nested patterns;
• f) comparing the said result, D, to patterns(k,best) for k>=i;
• g) deciding to continue or stop the calculation based on the result of said comparison in (f);
• h) moving to the next pattern by increasing i by one (i=i+1);
• i) if i=N exiting with SRC j as the best match;
• j) otherwise going back to step (d).
• k) if patterns(N−1,j)<patterns(N−1,best), setting patterns(i,best)=patterns(i,j) for all i's;
• l) stopping if search area is exhausted;
• m) otherwise going to step (h)

A method for reducing the computation in motion estimation for a target block comprising:

• a) comparing the calculated distortion based on a fraction of total pixels in the block, D, for the search area candidate with an equal size or bigger fraction of best match;
• b) deciding on continuing or stopping the calculation for the rest of pixels in the block based on the said comparison;
• c) calculating the distortion for more pixels of the block, and going to step (a) if the distortion is not calculated for all the pixels in the block;
• otherwise;
• d) comparing the total distortion due to search area candidate to the total distortion due to the best match;
• if distortion is bigger, continue to the next search area candidate;
• otherwise declare the said search area candidate as the best match;
• e) if more search area candidate is still available, go to step (a) for the next search area candidate;
• otherwise declare the best match found.