| With the impending approach of widespread broadband networks and high-definition television, efficient methods of encoding video are increasingly important. International organizations such as the ITU and MPEG provide video compression standards suitable for a variety of applications. However, each standard defines only a bitstream syntax and the corresponding instructions for reconstruction, leaving individual encoders to select an appropriate means of producing compliant bitstreams.; Due to the twin influences of a challenging problem and potential commercial success, encoders operating under “real-time” constraints have received much attention. These efforts generally address approximations and models tailored for the average case, assuming characteristics of the input data and imposing structure in order to simplify and accelerate the encoding process. Unlike in traditional estimation problems, video encoders have access to both original and noisy data, thus enabling the computation of optimal parameters and direct evaluation of model accuracy. Phrased another way, parameter selection algorithms obviate models, provided that the search may be completed within an allotted time.; This dissertation addresses studio-like environments where rate constraints are present but for which reconstruction quality dominates. In such environments, time and causality restrictions may be relaxed, allowing multiple frame encodings in any order, using computationally complex algorithms. Adaptive algorithms replace input data assumptions, and systematic parameter evaluation substitutes for models.; Critical encoder performance considerations are investigated, and methods for solving key encoder problems are proposed. Applicable to the underlying theory of all current video compression standards, these solutions are not specifically bound to any. A trellis structure facilitates the selection of frame types, respecting interdependencies and permitting high-level bit allocations to more accurately reflect the needs of consistent quality. Median filters applied to data elements introduce difficulties very similar to those presented by motion compensation in conjunction with a distortion target; a tree-based search is described that solves both problems. Merging the above algorithms, the final proposal uses Lagrange multipliers and a heuristic search to yield frames of consistent reconstruction quality, subject to a rate constraint. A refinement phase matches this consistent quality to an externally-defined distortion profile, while maintaining the constraint. |
