A fast full search block matching algorithm using three window search based on the statistical analysis of the motion vectors

The removal of temporal redundancy for reducing the bit rate of videos is the most time consuming part of video encoders. Our proposed algorithm, TWS, improves the encoder´s speed by at least 42 times with respect to the full search algorithm. Moreover, not only TWS (just like the full search algorithm) maintains MSE to its minimum value, but it also retains the encoded videos´ compression rate at the highest. The development of the proposed algorithm is based on the statistical data of motion vectors which are extracted from 5 long video sequences. According to the length of motion vectors, it is observed that they can be grouped in three distinctive ranges which constitutes the foundation for having three search windows in TWS. The TWS algorithm unlike the other fast algorithms does not have the problem of convergence towards the local minima of the distortion function. Our proposed algorithm has almost the same MSE values as the FS algorithm