IEEE Transactions on Consumer Electronics, Vol. 50, No. 3, AUGUST 2004 Contributed Paper Original manuscript received July 18, 2003 Revised manuscript received June 23, 2004 0098 3063/04/$20.00 © 2004 IEEE 968 Fast Sub-pixel Motion Estimation Techniques Having Lower Computational Complexity Jung W. Suh1 and Jechang Jeong2, Member, IEEE Abstract — This paper proposes fast sub-pixel motion estimation techniques having lower computational complexity. The proposed methods are based on mathematical models of the motion-compensated prediction errors in compressing moving pictures. Unlike conventional hierarchical motion estimation techniques, the proposed methods avoid sub-pixel interpolation and subsequent secondary search after the integer-precision motion estimation, resulting in reduced computational time. In order to decide the coefficients of the models, the motion-compensated prediction errors of the neighboring pixels around the integer-pixel motion vector are utilized. The prediction errors, here, were already obtained during the pixel accuracy motion search. Once the coefficients are determined, the models estimate motion compensated prediction errors at sub-pixel locations surrounding the integer-pixel motion vector, yielding the sub-pixel motion vector. The performance of the proposed methods, despite substantially lower computational complexity, is close to that of the conventional interpolation-and-search method. Index Terms — Half-pixel accuracy, Sub-pixel accuracy, Motion Estimation, Motion Compensation. I. INTRODUCTION To achieve efficient compression for video sequences, ME(Motion Estimation) and MC(Motion Compensation) are required to reduce temporal redundancy. ME is carried out using one of many well-known techniques such as BMA (Block Matching Algorithm), spatio-temporal constraint method [1], etc. ME and MC yield MVs(motion vectors) and prediction errors between the reference picture and the current picture to be coded. Since the integer-pixel accuracy ME has less accuracy than the sub-pixel accuracy case, ME is often performed at sub-pixel accuracy level for higher compression efficiency. In practice, precision of MVs is a priori specified. Half-pixel accuracy is, for instance, a typical choice as a tradeoff between reduced prediction errors and increased overheads for representing MVs. J. W. Suh1 is with the Bradley Department of Electrical and Computer Engineering, Virginia Polytechnic institute and State University, Blacksburg, VA 24061 USA (e-mail: jwsuh@ vt.edu). J. Jeong2 is with the Department of Electronic Communication Engineering, Hanyang University, Seoul, KOREA (e-mail: [email protected]). In conventional hierarchical ME, ME is first performed at integer pixel level and then half pixel level search is applied at eight half-pixel positions around the MV obtained at the first step [2]. This secondary search requires half-pixel interpolation in advance, which is also substantially time-consuming. In recent international standards such as MPEG-4, the half-pixel ME is far extended to 1/4-pixel or 1/8-pixel accuracy [3]. There have been various architectural attempts to implement real-time video encoders. Regardless of full hardware VLSI design [4] or RISC-based design with dedicated hardware modules [5], they tend to have limitation in performance due to high complexity of ME. Therefore, a number of efforts have been made to reduce time for ME since ME takes up a major portion of encoder complexity. The 2-D logarithmic search [6] or three-step search [7] consumes less computational time than the full search method but they may fall into local minimum positions. Half pixels (a.k.a. in-between pixels) are obtained by interpolating integer pixels, which increases computational complexity. There are half-pixel accuracy searching methods [8~13] to decrease complexity caused by interpolation. But these methods commonly yield large errors due to excessively simplified MC-error models. In this paper we propose fast sub-pixel ME techniques having lower computational complexity. The proposed methods are based on mathematical models of the mean-square MC prediction errors in compressing moving pictures. Unlike conventional hierarchical ME techniques, the proposed methods avoid sub-pixel interpolation and subsequent secondary search after the integer-precision ME, resulting in reduced computational time. In order to decide the coefficients of the models, the MC prediction errors of the neighboring pixels around the integer-pixel MV are utilized. The prediction errors, here, were already obtained during the pixel accuracy motion search. Once the coefficients are determined, the models estimate MC prediction errors at sub-pixel locations surrounding the integer-pixel MV, yielding the sub-pixel MV. The proposed mathematical models are referred to as Model 1, Model 2, Model 3, modified Model 2, and modified Model 3, respectively. Experimental results show that performance depends on the order of the models. The performance of the proposed methods, regardless of lower computational complexity, is close to that of the conventional interpolation-and-search method.J. W. Suh and J. Jeong: Fast Sub-pixel Motion Estimation Techniques Having Lower Computational Complexity 969II. PROPOSED METHODS AND MODELS We propose five mathematical models of mean-square MC prediction errors (For simplicity, we omit “mean-square” throughout this paper without loss of clarity). Using those models and integer-pixel level ME, we find sub-pixel accuracy MV by evaluating the values of the model function at sub-pixel positions neighboring the integer MV. This proposed method requires neither sub-pixel interpolation nor secondary search thereafter. Therefore the proposed methods tremendously reduce computational complexity in sub-pixel ME. A. Model 1 – Nonsingular case, Inverse matrix solution In Fig.1, ○ denotes integer pixels and ╳ denotes half pixels between integer pixels. Let the origin (0,0) denote the position of the integer-pixel accuracy MV selected via full search. Therefore, half-pixel accuracy MV is one of eight half pixel positions around (0, 0) or the origin (0, 0) itself, depending on MC prediction errors at those 9 positions. Here, we model the MC prediction error plane as 982762542322221),(cycycxcxcxycxycyxcyxcyxf++++++++= (1) The coefficients here can be determined using the MC prediction errors
View Full Document
Unlocking...