New Phase Binary Pyramid Motion Estimation for MPEG2 and HDTV Encoding

A novel Fast Binary Pyramid Motion Estimation (FBPME) algorithm is presented in this paper. The proposed FBPME scheme is based on binary multiresolution layers, XOR Boolean block matching and a N-scale tiling search scheme. Each video frame is converted into a pyramid structure of K-1 binary layers with resolution decimation plus one integer layer at the lowest resolution. At the lowest resolution layer, the N-scale tiling search is performed to select initial motion vector candidates. Motion vector fields are gradually refined with the XOR Boolean block matching criterion and the n-scale tiling search schemes in higher binary layers. FBPME performs several thousands times faster than the conventional full search block matching scheme at the same PSNR performance and visual quality. It also dramatically reduces the bus bandwidth and on-chip memory requirement. Moreover, hardware complexity islow due to its binary nature. Fully functional software MPEG-2 MP@ML and ATSC HDTV encoders based on the FBPME algorithm have been implemented. FBPME hardware architecture has been developed and is being incorporated into single-chip MPEG encoders. A wide range of video sequences at various resolutions has been tested. The proposed algorithm is also applicable to other digital video compression standards such as H.261, H.263 and MPEG4.