Block-based motion estimation using a novel orthogonal logarithmic search algorithm

The paper presents a novel orthogonal logarithmic search (OLS) algorithm for block based motion estimation. The performance of the algorithm is evaluated using benchmark video sequences and the results are compared to a traditional well-known full search algorithm (FSA) and a sub-optimal method, three step search (3SS). The evaluation considers the accuracy of the matching procedure with respect to the time required. Using benchmark QCIF video sequences, the results show that the average speed of operation for OLS is 1.04 seconds, for 3SS it is 2.63 seconds and for FSA it is 21.36. Consequently, OLS is nearly 21 times faster than FSA and nearly 3 times as fast as 3SS. The quality of the reconstructed frame is comparable with that of the full search method and 3SS. Furthermore, the PSNR of the OLS method is as good as that of the full search method and 3SS. Therefore, OLS is a better alternative to FSA and 3SS.