 step. The procedures are designed to find local optimal pel-recursive methods are very complex and inaccurate, solutions and cannot guarantee selection of the global which restrict their use in video encoders. Natural digital optimal solution within the search neighborhood. The image sequences generally display ambiguous object logarithmic search [18] algorithm proceeds in the di- motions that adversely affect the convergence properties rection of minimum distortion until the final optimal of pel-recursive algorithms. This has led to the in- value is found. Logarithmic searching has been imple- troduction of block-matching motion estimation which is mented in some MPEG encoders. The three-step search tailored for encoding image sequences. Block-matching [19] is a very simple technique that proceeds along a best motion estimation assumes that the objective motion match path in three steps in which the search being predicted is rigid and non-rotational. The block size of the BMA for the MPEG, H.261, and H.263 encoders Search Neighborhood is defined as 16 X 16 luminance pixels. MPEG-2 also supports 16 X 8 pixel blocks. 1k-1(i+x,j+y) BMAs predict the motion of a block of pixels between two frames in an image sequence. The prediction gen- erates a pixel displacement or motion vector whose size is constrained by the search neighborhood. The search neighborhood determines the complexity of the algo- MV (m=x, n=y) rithm. The search for the best prediction ends when the Best Match in best block match is determined within the search Frame k-1 neighborhood. The best match can be chosen as the minimum MSE, which for a full search is computed for each block in the search neighborhood, i.e., (i,j) MatchMSE = min m.n ] i=1j=1 (7.4.12) where k is the frame index, l is the temporal displace- ment in frames, M is the number of pixels in the hori- zontal direction and N is the number of pixels in the Figure 7.4-6 Best match motion estimate. CHAPTER 7.4 Video compression Electrotechnical Commission (IEC), and the In- ternational Te