5.1 Motion estimation

Motion estimation is the processes which generates the motion vectors that determine how each motion compensated predictionframe is created from the previous frame.

Block Matching (BM) is the most common method of motion estimation. Typically each macroblock ( $16\times 16$ pels) in the new frame is compared with shifted regions of the same size from the previous decoded frame, andthe shift which results in the minimum error is selected as the best motion vector for that macroblock. The motion compensatedprediction frame is then formed from all the shifted regions from the previous decoded frame.

BM can be very computationally demanding if all shifts of each macroblock are analysed. For example, to analyse shifts of upto $\pm (15)$ pels in the horizontal and vertical directions requires $31\times 31=961$ shifts, each of which involves $16\times 16=256$ pel difference computations for a given macroblock. This is known as exhaustive search BM .

Significant savings can be made with hierarchical BM , in which an approximate motion estimate is obtained from exhaustive search using a lowpass subsampled pair ofimages, and then the estimate is refined by a small local search using the full resolution images. Subsampling 2:1 in eachdirection reduces the number of macroblock pels and the number of shifts by 4:1, producing a computational saving of 16:1!

There are many other approaches to motion estimation, some using the frequency or wavelet domains, and designers have consideredscope to invent new methods since this process does not need to be specified in coding standards. The standards need onlyspecify how the motion vectors should be interpreted by the decoder (a much simpler process). Unfortunately, we do not havetime to discuss these other approaches here.