One of the most powerful bit rate reduction techniques in video coding is motion-compensated interpolation for exploiting interframe redundancy. A prominent example of which is the bi-directional prediction scheme in the MPEG-1 and MPEG-2 video coding standards for digital storage media. Even though the bi-directional motion-compensated prediction can obtain a remarkable prediction efficiency, the bi-directional motion estimation is a formidable computational challenge to realize real-time implementation. To overcome this ploblem and improve the coding preformance of MPEG, this dissertation proposes three new algorithms associated with the bi-directional predictional scheme.
First, a fast block-matching algorithm(BMA) is proposed to reduce the computational complexity of bi-directional motion estimation for MPEG-video coding standard. If BMA starts from more probable candidate location, the estimated motion vector converges faster to the true movement within a small search range. The proposed algorithm is based on this concept. To estimate more reliable initial motion vector, the proposed algorithm exploits the property of high correlation among the motion vectors in the spatio-temporal direction and translational motion model suitable for bi-directional motion estimation in P/B pictures. Experimental results based on MPEG-2/TM5 show that the proposed algorithm achieves almost the same prediction and coding performance with very low computational complexity, and also obtains slightly better subjective quality and motion rendition.
Second, a new 2-step motion estimation and compensation algorithm is proposed to improve the prediction efficiency in B-pictures of MPEG. This algorithm provides two pairs of forward and backward motion vectors by successively combining independent search method and recursive joint serach method: one pair for uni-directional MCP mode, and another pair for bi-directional MCP mode. Experimental results based on MPEG-2/TM5 show that the prediction and coding preformances can be significantly improved for several scenes. Moreover, when the fast BMA is applied to the first step, the computational complexity of the proposed algorithm can be reduced about $\frac{1}{11}\sim\frac{1}{42}$ than that of the independent full search algorithm.
Finally, a block-based conditional replenishment coding is proposed to improve the overall coding performance of MPEG-video coding standard, that is applied only to 'non-intra' macroblock(MB) of B-picture. In this algorithm, the insignificant MBs whose MAE of prediction error is less than a predetermined CRC threshold are made to 'not coded' MBs enforcedly to reduce the number of coded bits of B-pictures. By using this strategy, the coding preformance of I/P pictures is improved significantly because of increase in the number of bits allocated for I/P pictures. Even though CRC is applied to B-pictures, the coding performance of B-pictures improves slightly because of increased prediction gain due to the improved I/P references and hence reduced quantization level in B-pictures.
