  Motion Estimation (ME) is one of the most time-consuming parts in video
coding. The use of multiple partition sizes in H.264/AVC makes it even more
complicated when compared to ME in conventional video coding standards. It is
important to develop fast and effective sub-pixel ME algorithms since (a) The
computation overhead by sub-pixel ME has become relatively significant while
the complexity of integer-pixel search has been greatly reduced by fast
algorithms, and (b) Reducing sub-pixel search points can greatly save the
computation for sub-pixel interpolation. In this paper, a novel fast sub-pixel
ME algorithm is proposed which performs a 'rough' sub-pixel search before the
partition selection, and performs a 'precise' sub-pixel search for the best
partition. By reducing the searching load for the large number of non-best
partitions, the computation complexity for sub-pixel search can be greatly
decreased. Experimental results show that our method can reduce the sub-pixel
search points by more than 50% compared to existing fast sub-pixel ME methods
with negligible quality degradation.
