Title :
Multi-direction search algorithm for block-based motion estimation
Author :
Po, Lai-Man ; Ng, Ka-Ho ; Wong, Ka-Man ; Cheung, Kwok-Wai
Author_Institution :
Dept. of Electron. Eng., City Univ. of Hong Kong, Kowloon
fDate :
Nov. 30 2008-Dec. 3 2008
Abstract :
Easily trapped in local minima is one of the well-known problems in search point pattern based fast block motion estimation algorithms. This problem is especially serious in one-at-a-time search (OTS) and block-based gradient descent search (BBGDS). These two algorithms can provide very high speedup ratio but with low robustness in prediction accuracy especially for sequences with complex motions. Multi-path search (MPS) using more than one path have been proposed to improve the robustness of BBGDS, but the computational requirement is much increased. To tackle this problem, a novel multi-directional gradient descent search (MDGDS) is proposed in this paper with use of multiple OTSs in eight directions. Basically, the proposed MDGDS performs eight one-dimensional gradient descent searches on the error surface and therefore can trace to the global minimum more efficiently. Experimental results show that a significant improvement in computation reduction can be achieved as compared with well-known fast block motion estimation algorithms.
Keywords :
block codes; gradient methods; motion estimation; search problems; video coding; block-based gradient descent search; block-based motion estimation; multidirectional gradient descent search algorithm; multipath search; one-at-a-time search; video coding; Accuracy; Distortion measurement; Electron traps; Encoding; Motion estimation; Performance evaluation; Robustness; Video coding; Video sequences;
Conference_Titel :
Circuits and Systems, 2008. APCCAS 2008. IEEE Asia Pacific Conference on
Conference_Location :
Macao
Print_ISBN :
978-1-4244-2341-5
Electronic_ISBN :
978-1-4244-2342-2
DOI :
10.1109/APCCAS.2008.4746308