Block Based All Directional Smart Search Algorithm for Optimized Motion Estimation in Video Data

The Block Based Motion Estimation (BBME) algorithms were proposed to estimate motion between consecutive frames of a video. A number of search point based BBME algorithms were suggested, Full Search (FS) being most robust in terms of Peak Signal to Noise Ratio (PSNR) but taking maximum number of computations. To reduce the computations, many BBME algorithms were introduced. The most prominent among these were Block Based Gradient Descent Search (BBGDS) and Directional Gradient Descent Search (DGDS) which searched in all eight directions. To reduce the number of computations without affecting the PSNR, we propose a Block Based All Directional Smart Search Algorithm (BBADSS). The BBADSS is block based in nature and performs the search of best matched block in all eight directions by restricting the searching process to maximum of three steps with seven possible cases of computing the blocks. The algorithm is further improved by introducing a threshold and eliminating the irrelevant blocks. Our algorithm provides 95.7% increase in speed when compared with FS, 40% in comparison to DGDS and 36.9% over BBGDS. BBADSS is further restricted to step 1 or step2 to minimize the number of computations without significantly affecting the PSNR. This makes our algorithm smarter.