Rate-computation optimized block based video coding

This dissertation reports on rate-distortion optimized and computation-constrained video coding algorithms which yield effective and efficient block-based video encoders. We first propose a new cost function for motion estimation which can achieve good tradeoffs among motion vector bit rate, compensation distortion, and number of computations. Based on the new cost function, we propose a predictive motion estimation algorithm which can effectively determine the size of the search region according to the statistics of the motion field. The proposed motion estimation algorithm allows control of the motion vector bit rate and the computational cost, simultaneously. We also develop two efficient rate-distortion optimized coding mode selection algorithms, based on thresholding and finite state machine (FSM) methods, respectively. The thresholding method can eliminate consideration of the computationally expensive modes. The FSM method determines the test orders of the modes and associated parameters by exploiting the local statistics of the input video sequence. The proposed two methods can reduce substantially the computation requirements as compared to the full search mode selection method. Based on the proposed motion estimation and mode selection algorithms, we implement an H.263-based video coder and an MPEG-2 compliant video coder for very low bit rate video applications, and high bit rate interlaced video applications, respectively. The resulting video coders achieve excellent tradeoffs among bit rate, quality, and computational complexity. In fact, experimental results show that our video coders outperform the best known video coders in terms of compression performance and encoding speed.Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat