Next: Progressive Transmission of Motion Up: A Theory of Bit Previous: Bit Allocation Analysis

# Practical and Computational Significance

We can now use the imputed profit vector at any time in order to make a choice from the set of efficient points. For example, given competing quantizers , let be a set of allocation processes holding Axiom 1 through Axiom 4. From Axiom 1 and Axiom 3 we have that is a convex set of allocation processes. Hence, by Theorem 1, the concept of efficient allocation process'' is now characterized by profit maximization. That is, maximization of with respect to over the set of allocation processes at any given time . Given that is a compact set (by Axiom 1 and Axiom 3), the existence of solution for this maximization problem is guaranteed by the Weierstrass Theorem since the inner product is a continuous function.

From Axiom 1 we have that

with , . Following Axiom 2 through Axiom 4 the basic allocation processes may, for example, have the form

with being the cost of quantization (bits per pixel) for at the given time. The fraction is a normalized measure of bit consumption when using . Recall that a proper definition of the basic allocation processes should take into account of the technological possibilities in a given problem of bit allocation.

Since we then have that assigns bits to quantizer , , with a total bit consumption of , assuming :

Then, it follows that the bit allocation set

with resource limitation at time , can be characterized by linear inequalities such as:

where ; denotes the 's resource limitation at this time , with ; and is the available bit consumption at .

Then the problem of finding which maximizes

where , subject to the constraints

is a typical linear programming problem, of which the computational method is the simplex'' method. Hence the theory of bit allocation analysis has practical and computational significance for bit allocation.

We shall consider an example of these problems. It solves the bit allocation analysis among three quantizers at a certain time . We have that the respective cost of quantization for each quantizer is: bpp; bpp; and bpp.

The three basic allocation processes are (Table I):

and

For example, if these three basic allocation processes are operated at intensity expressing quantizers' allocation choices, the resultant allocation process (representing a new combination of bit allocation and total consumption):

 (4)

Table I:
 Allocation Allocation Allocation Basic Alloc. Processes 1 0 0 0 1 0 0 0 1

For this example we assume that the imputed profit vector is

The bit allocation set is characterized by available bit consumption and resources at this time: (i) resource limitation at is bits; (ii) resource limitation at is bits; (iii) resource limitation at is bits; and (iv) available bit consumption at time is bits.

For this example the bit allocation analysis can be represented by:

subject to

By Theorem 1, the efficient combination of allocations up to the bit resource limitation at this time is the solution of this linear programming problem (where represents the efficient allocation for quantizer ): (i) bits; (ii) bits; and (iii) bits. No desired bit allocation for a particular quantizer can be increased without decreasing other desired quantizer allocation or increasing bit consumption, at the given profit vector.

Next: Progressive Transmission of Motion Up: A Theory of Bit Previous: Bit Allocation Analysis
J. Fdez-Valdivia 2006-03-13