Novel fast block motion estimation using diamond-arc-hexagon search patterns

This work presents a novel block motion estimation (ME) approach, diamond-arc-hexagon search (DAHS), which uses diamond, arc, and hexagon search patterns to accomplish the fast searching process. According to the characteristic of the center-based motion vector distribution for the real-world video sequence, DAHS employs a small diamond pattern extended hexagon search to refine the central area search. Furthermore for estimation in large motion situations, the strategy of the large diamond-to-arc search can preserve good performance. Experimental results indicate that DAHS is suitable for both (quasi-) stationary and large motion searches. DAHS outperforms the efficient three-step (E3SS) and hexagon-based search (HEXBS) in prediction quality, and improves the searching speed about 9% compared to E3SS. The proposed algorithm was tested using several sequences and delivered excellent performance in search speed and prediction of video quality. The DAHS can be applied to real-time video processes, such as H.264/MPEG-4 advanced video coding (AVC) and scalable video coding (SVC).