An alternative cross-fusiform search algorithm for fast block matching motion

Block matching algorithm is generally used in motion estimation. How to search with different shape or size in block matching algorithms has enormous impact on their search speed and distortion performance. Based on analysis the difference of search patterns in block matching algorithms, an alternative cross fusiform search algorithm for fast block motion estimation is proposed in this paper. This algorithm basically employs cross-shaped search pattern in first step and then performs block matching by using a pair of fusiform-shaped search patterns in the subsequence steps. Experimental results show that the proposed ACFS algorithm performs about 20% faster than HEXBS in most of sequences, whereas similar distortion performance is still maintained. In some sequences with small motion, ACFS can even obtain up to 90% speed improvement over HEXBS. Thus, ACFS is particularly suitable for video sequences with small/medium motion.