Game Theoretical Models And Algorithms For Rate Control In Video Compression

Abstract

This thesis investigates game theory based rate control algorithms for optimizing the bit allocation in video compression. The first algorithm utilizes the cooperative bargaining game in a MB level rate control algorithm to optimize the perceptual quality while guaranteeing "fairness" in bit allocation among macroblocks. The algorithm first allocates the target bits to frames based on their coding complexity; a method to estimate the coding complexity of the remaining frames is proposed. Next, macroblocks of a frame play cooperative games such that each macroblock competes for a share of resources (bits) to optimize its quantization scale while considering the human visual system (HVS) perceptual property. Since the whole frame is an entity perceived by viewers, macroblocks compete cooperatively under a global objective of achieving the best quality with the given bit constraint. The major advantage of the proposed approach is that the cooperative game leads to an optimal and fair bit allocation strategy based on the Nash Bargaining Solution. Another advantage is that it allows multi-objective optimization with multiple decision makers (e.g., macroblocks). The algorithm achieves accurate bit rate with good perceptual quality, and to maintain a stable buffer level. The second algorithm based on a non-cooperative strategic game is aimed for video object level bit allocation. We formulate a two-player bi-matrix game, in which the utilities of the players are pre-determined by a set of available strategies (i.e., the possible quantization parameters). The game is non-deterministic in which the players' strategies are bound to a probability distribution over the set of available actions. The outcome of the game is a mixed strategy Nash equilibrium. The proposed algorithm achieves accurate bit rate regulation and smooth buffer occupancy.