Block-matching algorithm

This can be used to discover temporal redundancy in the video sequence, increasing the effectiveness of inter-frame video compression by defining the contents of a macroblock by reference to the contents of a known macroblock which is minimally different.

A block matching algorithm involves dividing the current frame of a video into macroblocks and comparing each of the macroblocks with a corresponding block and its adjacent neighbors in a nearby frame of the video (sometimes just the previous one).

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.

A metric for matching a macroblock with another block is based on a cost function.

This algorithm calculates the cost function at each possible location in the search window.

The resulting motion compensated image has highest peak signal-to-noise ratio as compared to any other block matching algorithm.

TDLS is closely related to TSS however it is more accurate for estimating motion vectors for a large search window size.

The algorithm can be described as follows, TSS uses a uniformly allocated checking pattern and is prone to miss small motions.

NTSS [4] is an improvement over TSS as it provides a center biased search scheme and has provisions to stop halfway to reduce the computational cost.

It was one of the first widely accepted fast algorithms and frequently used for implementing earlier standards like MPEG 1 and H.261.

The algorithm runs as follows: Thus this algorithm checks 17 points for each macro-block and the worst-case scenario involves checking 33 locations, which is still much faster than TSS The idea behind TSS is that the error surface due to motion in every macro block is unimodal.

However a unimodal surface cannot have two minimums in opposite directions and hence the 8 point fixed pattern search of TSS can be further modified to incorporate this and save computations.

However the peak signal-to-noise ratio achieved is poor as compared to TSS as the error surfaces are not strictly unimodal in reality.

Four Step Search is an improvement over TSS in terms of lower computational cost and better peak signal-to-noise ratio.

Similar to NTSS, FSS [6] also employs center biased searching and has a halfway stop provision.

Adaptive rood pattern search (ARPS) [8] algorithm makes use of the fact that the general motion in a frame is usually coherent, i.e. if the macro blocks around the current macro block moved in a particular direction then there is a high probability that the current macro block will also have a similar motion vector.

The main advantage of ARPS over DS is if the predicted motion vector is (0, 0), it does not waste computational time in doing LDSP, but it directly starts using SDSP.

Furthermore, if the predicted motion vector is far away from the center, then again ARPS saves on computations by directly jumping to that vicinity and using SDSP, whereas DS takes its time doing LDSP.