motion estimation using orthogonal algorithm

The digital video application has become increasingly popular in mobile terminals such as cellular phones and personal digital assistance. Due to inherent data intensity, storage and transmission of raw video data is difficult. With the limited storage capacity and bandwidth, this data must be compressed to a transportable size. In videos, the changes in the subsequent frames are very less, which causes redundancy. This encourages video compression resulting in efficient usage of storage devices. But this comes at the cost of some quality degradation. Motion estimation is the process of determining motion vectors that describe the transformation from one 2D image to another; usually from adjacent frames in a video sequence. In all the applications, the demand is high for accurate estimates of motion requiring minimal computational cost. In our work, we have discussed different motion estimation techniques. We have focused on Block Matching Algorithms like exhaustive search, three step search, new three step search, diamond search, hexagonal search and octagonal search. For these algorithms, performance in terms of accuracy (PSNR) and number of computations required to obtain motion vectors is discussed. In existing algorithms Hexagonal Search provides significant PSNR with least number of computations. Also we have tried to classify the motion. To modify the existing Hexagonal Search Algorithm, we have proposed a new approach for early termination based on threshold to avoid redundant calculation when in point obtain in earlier step is good enough. Comparison of Existing algorithm and proposed approach in terms of PSNR and Computations required has been carried out. Significant speedup gain has been achieved over the current hexagon-based search algorithm while maintaining similar distortion performance.