Efficient inner search for faster diamond search

The paper presents a new scheme for improving the speed of the widely used diamond search (DS) in block motion estimation. It is known that the DS algorithm makes a full inner search around the center within a large diamond region, which, in our opinion, is inefficient. By exploiting the distortion information of the evaluated points in the large diamond, a new triple-based fast inner search is proposed to speed up the localized inner search with quantitative and experimental justifications. Compared with other popular fast algorithms including the original and predictive DS, enhanced DS incorporating the proposed fast inner search can achieve a significant speedup gain while maintaining similar or smaller distortion, which is clearly demonstrated in our extensive experiments on 10 video sequences.