A Review of the Minimum Maximum Criterion for Optimal Bit Allocation among Dependent Quantizers
---
paper_title: Object-adaptive vertex-based shape coding method

paper_content:

The paper presents a new technique for compactly representing the shape of a visual object within a scene. This method encodes the vertices of a polygonal approximation of the object's shape by adapting the representation to the dynamic range of the relative locations of the object's vertices and by exploiting an octant-based representation of each individual vertex. The object-level adaptation to the relative-location dynamic range provides the flexibility needed to efficiently encode objects of different sizes and with different allowed approximation distortion. At the vertex-level, the octant-based representation allows coding gains for vertices closely spaced relative to the object-level dynamic range. This vertex coding method may be used with techniques which code the polygonal approximation error for further gains in coding efficiency. Results are shown which demonstrate the effectiveness of the vertex encoding method. The rate-distortion comparisons presented show that the technique's adaptive nature allows it to operate efficiently over a wide range of rates and distortions and across a variety of input material, whereas other methods are efficient over more limited conditions.
---
paper_title: MPEG-4 and Rate-Distortion-Based Shape-Coding Techniques

paper_content:

We address the problem of the efficient encoding of object boundaries. This problem is becoming increasingly important in applications such as content-based storage and retrieval, studio and television postproduction, and mobile multimedia applications. The MPEG-4 visual standard will allow the transmission of arbitrarily shaped video objects. The techniques developed for shape coding within the MPEG-4 standardization effort are described and compared first. A framework for the representation of shapes using their contours is presented next. Such representations are achieved using curves of various orders, and they are optimal in the rate-distortion sense. Finally, conclusions are drawn.
---
paper_title: Bit allocation for dependent quantization with applications to multiresolution and MPEG video coders.

paper_content:

We address the problem of efficient bit allocation in a dependent coding environment. While optimal bit allocation for independently coded signal blocks has been studied in the literature, we extend these techniques to the more general temporally and spatially dependent coding scenarios. Of particular interest are the topical MPEG video coder and multiresolution coders. Our approach uses an operational rate-distortion (R-D) framework for arbitrary quantizer sets. We show how a certain monotonicity property of the dependent R-D curves can be exploited in formulating fast ways to obtain optimal and near-optimal solutions. We illustrate the application of this property in specifying intelligent pruning conditions to eliminate suboptimal operating points for the MPEG allocation problem, for which we also point out fast nearly-optimal heuristics. Additionally, we formulate an efficient allocation strategy for multiresolution coders, using the spatial pyramid coder as an example. We then extend this analysis to a spatio-temporal 3-D pyramidal coding scheme. We tackle the compatibility problem of optimizing full-resolution quality while simultaneously catering to subresolution bit rate or quality constraints. We show how to obtain fast solutions that provide nearly optimal (typically within 0.3 dB) full resolution quality while providing much better performance for the subresolution layer (typically 2-3 dB better than the full-resolution optimal solution).
---
paper_title: A Video Compression Scheme with Optimal Bit Allocation Among Segmentation , Motion , and Residual Error

paper_content:

We present a theory for the optimal bit allocation among quadtree (QT) segmentation, displacement vector field (DVF), and displaced frame difference (DFD). The theory is applicable to variable block size motion-compensated video coders (VBSMCVC), where the variable block sizes are encoded using the QT structure, the DVF is encoded by first-order differential pulse code modulation (DPCM), the DFD is encoded by a block-based scheme, and an additive distortion measure is employed. We derive an optimal scanning path for a QT that is based on a Hilbert curve. We consider the case of a lossless VBSMCVC first, for which we develop the optimal bit allocation algorithm using dynamic programming (DP). We then consider a lossy VBSMCVC, for which we use Lagrangian relaxation, and show how an iterative scheme, which employs the DP-based solution, can be used to find the optimal solution. We finally present a VBSMCVC, which is based on the proposed theory, which employs a DCT-based DFD encoding scheme. We compare the proposed coder with H.263. The results show that it outperforms H.263 significantly in the rate distortion sense, as well as in the subjective sense.
---

Title: A Review of the Minimum Maximum Criterion for Optimal Bit Allocation among Dependent Quantizers

Section 1: Introduction
Description 1: Provide an overview of the paper’s purpose, the problems being addressed, and the significance of the MINMAX criterion in contrast to the MINAVE criterion.

Section 2: Notation, Assumptions and Problem Formulation
Description 2: Introduce the necessary notation, underlying assumptions, and the mathematical formulation of the optimal bit allocation problem in a dependent coding framework.

Section 3: The MINAVE Criterion
Description 3: Explain how the optimal bit allocation problem can be solved for the MINAVE criterion using the Lagrange multiplier method and dynamic programming (DP).

Section 4: The MINMAX Criterion
Description 4: Describe the general algorithm for optimal bit allocation among dependent quantizers for the MINMAX criterion, including the minimum rate problem, the minimum distortion problem, and methods for breaking ties.

Section 5: Applications
Description 5: Present several examples from different areas of data compression to compare the MINAVE and MINMAX approaches, including still-frame compression, inter-mode frame compression, and shape coding.

Section 6: Conclusions
Description 6: Summarize the comparison between the MINAVE and MINMAX criteria, highlighting the advantages of the MINMAX approach and its potential applications in various coding schemes.