New fast binary pyramid motion estimation for MPEG2 and HDTV encoding

A novel Fast Binary Pyramid Motion Estimation (FBPME) algorithm is presente d in this paper. The proposed FBPME scheme is based on binary multiresoluti on layers, exclusive-or (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 sear ch is performed to select initial motion vector candidates, Motion vector f ields are gradually refined with the XOR Boolean block-matching criterion a nd the N-scale tiling search schemes in higher binary layers. FBPME performs several thousands times faster than the conventional full-se arch block-matching scheme at the same PSNR performance and visual quality. It also dramatically reduces the bus bandwidth and on-chip memory requirem ent. Moreover, hardware complexity is low due to its binary nature. Fully functional software MPEG-2 MP@ML encoders and Advanced Television Sta ndard Committee High Definition Television encoders based on the FBPME algo rithm 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 algori thm is also applicable to other digital video compression standards such as H.261, H.263, and MPEG4.