| Block-based motion estimation is widely used for exploiting temporal redundancies in arbitrarily shaped video objects, which is computationally the most demanding part within the MPEG-4 standard. One of the main differences of MPEG-4 video in comparison to previously standardized video coding schemes is the support of arbitrarily shaped video objects for which the numerous existing fast motion estimation algorithms are not suitable. The conventional fast motion estimation algorithm works well for the opaque macroblocks. This is not the case for boundary macroblocks which contain a large number of local minima on their error surfaces. In view of this, we propose a fast search algorithm which incorporates the binary alpha-plane to accurately predict the motion vectors of boundary macroblocks. Besides, these accurate motion vectors can be used to develop a novel priority search algorithm which is an efficient search strategy for the remaining opaque macroblocks. Experimental results show that our approach requires simple computational complexity, and it gives a significant improvement in accuracy on motion-compensated video object planes as compared with conventional algorithms, such as the diamond search. Numerically, a speed-up of about 27 times as compared with the full search algorithm is obtained in our tested VOs.; Although many fast search algorithms can achieve low computational load and acceptable encoding quality requirement, it is always desirable to look for identical searching results as compared with that of the conventional full search algorithm. For instance, high quality digital video product and object tracking applications need to estimate motion activities accurately. To develop a fast full search algorithm, we have made use of our observation that pixel matching errors with similar magnitudes tend to appear in clusters for natural video sequences on average. Subsequently an adaptive partial distortion search algorithm has been proposed. The algorithm significantly improves the computation efficiency of the original partial distortion search. In terms of the number of operations, our experimental results show that the computational efficiency of the algorithm outperforms other algorithms. The algorithm can have a speed-up of 3 to 9 as compared with the Full Search Algorithm (FSA). In terms of real-time measurement, our algorithm can speed up the search for about 3.38 times as compared to the FSA on average, which is again better than other tested algorithms including Successive Elimination Algorithm for encoding sequences with high motion activities and arbitrarily shaped video objects. (Abstract shortened by UMI.)... |
