in the image is called motion compensation. The combination of motion estimation and motion compensation is a key part of video compression as used by MPEG 1, 2 and 4 as well as many other video codecs. Motion estimation based video compression helps in saving bits by sending encoded difference images which have inherently less entropy as opposed to sending a fully coded frame. However, the most computationally expensive and resource extensive operation in the entire compression process is motion estimation. Hence, fast and computationally inexpensive algorithms for motion estimation is a need for video compression. Evaluation Metrics A metric for matching a macroblock with another block is based on a cost function. The most popular in terms of computational expense is: Mean difference or Mean Absolute Difference (MAD) = Mean Squared Error (MSE) = where N is the size of the macro-block, and and are the pixels being compared in current macroblock and reference macroblock, respectively. The motion compensated image that is created using the motion vectors and macroblocks from the reference frame is characterized by Peak signal-to-noise ratio (PSNR), Algorithms Block Matching algorithms have been researched since mid-1980s. Many algorithms have been developed, but only some of the most basic or commonly used have been described below. Exhaustive Search This algorithm calculates the cost function at each possible location in the search window. This leads to the best possible match of the macro-block in the reference frame with a block in another frame. The resulting motion compensated image has highest peak signal-to-noise ratio as compared to any other block matching algorithm. However this is the most computationally extensive block matching algorithm among all. A larger search window requires greater number of computations. Optimized hierarchical block matching (OHBM) The optimized hierarchical block matching (OHBM) algorithm speeds up the exhaustive search based on the optimized image pyramids. Three Step Search It is one of the earliest fast block matching algorithms. It runs as follows: Start with search location at center Set step size S = 4 and search parameter p = 7 Search 8 locations +/- S pixels around location (0,0) and the location (0,0) Pick among the 9 locations searched, the one with minimum cost function Set the new search origin to the above picked location Set the new step size as S = S/2 Repeat the search procedure until S = 1 The resulting location for S=1 is