### Motion Estimation (1. comparission functions)

~~This months ;) ~~Todays blog entry is about motion estimation for block based video encoders, more precissely integer pel style, no half pel or qpel to keep this reasonable simple. In practice the sub-pel motion estimation (hpel/qpel…) is normaly done after normal integer pel anyway so we can nicely ignore sub pel today

Now how do we estimate the motion of a square or rectangular block of pixels?

Nothing easier then that you will likely say just find the best matching block in the reference frame for each block we need to encode, but what is “best” and how to find it?

#### Compare functions

To find the best matching block we first need to give each pair of blocks a score, there are several popular ways to do that:

SAD | Sum of absolute differences |
for(x=0; x<SIZE; x++){ for(y=0; y<SIZE; y++){ score += abs(reference[y][x] - current[y][x]); } } |

SSD | Sum of squared differences |
for(x=0; x<SIZE; x++){ for(y=0; y<SIZE; y++){ error= reference[y][x] - current[y][x]; score += error*error; } } |

SATD | Sum of absolute hadamard transformed differences |
for(x=0; x<SIZE; x++) for(y=0; y<SIZE; y++) difference[y][x]= reference[y][x] - current[y][x]; vertical_hadamard_transform(difference); horizontal_hadamard_transform(difference); // vertical and horizontal can be exchanged for(x=0; x<SIZE; x++) for(y=0; y<SIZE; y++) score += abs(difference[y][x]); |

And the theoretical ideal comparission function is to completely encode the block and then use the weighted sum of the number of bits and the distortion be it SSD or a psychovissual one as score

And how to find the best block with such a comparssion function will be the subject of another blog entry, dont fear, iam just trying to keep the blog entries small, selfcontained and easy digestable

Given this, what is your opinion about tranform based motion estimation?

Comment by Sarang K — 2008-01-02 @ 13:52