UC San Diego

The complexity of video coding standards has increased significantly from H.262/MPEG-2 to H.264/AVC in order to increase coding efficiency. Complexity mainly was increased more by architecture than by algorithms: One 16x16 MB type in MPEG-2 was partitioned into various MB types such as 16x16, 8x16, 8x8, 4x4. Half pixel accuracy motion estimation was extended to support quarter pixel accuracy, and various simple directional filters were applied for intra prediction. In this dissertation, we consider optimization and learning methods to solve video coding problems. In our approaches, complexity is mainly increased by algorithms to improve coding efficiency. Especially, we apply these methods for the Rate-Distortion (RD) optimization problem in H.264 and intra prediction as a new video coding scheme because they are highly related with numerical optimization and regression theories. For the RD optimization problem, we propose a general framework with consideration of temporal prediction dependency using the primal-dual decomposition and subgradient projection methods. As a result, optimality conditions among the Lagrange multipliers $\lambda$ are derived for the optimal bit allocation. The proposed method is compared with the Rate Control (RC) algorithm in the reference software model (JM model) of H.264. In order to reduce the complexity of the proposed method, an adaptive Lagrange multiplier selection method is proposed in the RC algorithm using the Classification-Maximization (CM) algorithm. In addition, two variations of the CM algorithm, that is, Relaxed CM (RCM) and Incremental CM (ICM) are proposed to improve the performance and avoid iterations. We compare [lambda] of the proposed adaptive Lagrange multiplier selection methods with ones of the JM model and the greedy search. Finally, we propose a new video coding scheme using learning methods. In particular, learning methods such as support vector regression and locally weighted learning are applied for intra prediction by means of batch and online learning. We present that online learning based intra prediction is better for video coding because of limited training time and nonstationary video sequences even though batch learning based intra prediction can achieve significant improvement in low- motion sequences. Experimental results show that online learning based video coding is promising for future video coding