High-performance algorithms and architectures for motion-compensated hybrid video coding

Motion-compensated (MC) hybrid video coding has been widely adopted by current industrial standards due to its effectiveness in achieving high compression. Although numerous encoding techniques have been proposed and implemented, the task of designing algorithms and architectures to meet the needs of a wide variety of applications still remains challenging. One of the key reasons is that a proper choice depends heavily on the application as well as its constraints on performance, power, and costs. In this dissertation we develop two classes of application-specific motion estimation algorithms where block-based processing schemes are employed. The aim of one class of algorithms is to optimize implementation costs for applications where complexity and/or power are highly constrained; on the other hand, the intended applications for the other class are low-bit-rate and high quality coding systems.; For complexity- and/or power-constrained applications, a computationally efficient block-matching motion estimation algorithm using the predictive logarithmic search is proposed. While retaining the low computational complexity of traditional logarithmic schemes, the proposed algorithm virtually alleviates the local-minimum problems commonly encountered in conventional fast search algorithms by exploiting motion correlation among neighboring segmented blocks, both spatially and temporally. In addition, a parallel VLSI architecture based on a new dataflow arrangement for the logarithmic search algorithm is described. By taking advantage of interblock data dependency, the proposed architecture minimizes input bandwidth requirements as well as the complexity of its supporting memory structure, thereby providing a cost-effective single-chip solution.; For low-bit-rate applications, our focus is to examine the problem of bit allocation between motion information and the residual image. The objectives in our research in low bit-rate applications are two-fold: (1) to study the bit allocation problem of the MC hybrid video coding systems from a theoretical standpoint such that an optimal operating point in the rate-distortion (R-D) space can be located, and (2) to explore the complexity issue of the proposed optimization schemes and develop algorithms to allow for efficient software and hardware realizations.; We develop a general R-D optimization framework that can provide an optimal solution for a given system configuration, assuming that sufficient computation power, memory, and delay are available. In the case of MPEG coding techniques, an optimal bit allocation strategy, based on dynamic programming, is proposed by explicitly considering dependence relations between adjacent blocks. Additionally, we present a new variable block-size motion compensation system in which R-D optimal motion vectors can be obtained by a polynomial-time procedure. Furthermore, efficient optimization schemes are investigated for the systems where more complicated motion compensation schemes are used.