Line Searches for Fast Block Motion Estimation

Search point pattern-based fast block motion estimation algorithms provide significant speedup for motion estimation but usually suffer from being easily trapped in local minima. This may lead to low robustness in prediction accuracy particularly for video sequences with complex motions. This problem is especially serious in one-at-a-time search (OTS) and block-based gradient descent search (BBGDS), which provide very high speed up ratio. A multipath search using more than one search path has been proposed to improve the robustness of BBGDS but the computational requirement is much increased. To tackle this drawback, a line searches search (LS) algorithm using multiple OTSs and gradient descent searches on the error surface in different directions is proposed in this letter. The search point patterns in each stage depend on the minima found in these different directions, and thus the global minimum can be traced more efficiently. Experimental results show that DADDGDS (LINE SEARCH) reduces computation load significantly compared with the well-known fast block motion estimation algorithms.