Practical and Computational Significance

We can now use the imputed profit vector $p$ at any time $t$ in order to make a choice from the set of efficient points. For example, given $m$ competing quantizers $Q_1 \cdots Q_j \cdots Q_m$, let $Y$ be a set of allocation processes holding Axiom 1 through Axiom 4. From Axiom 1 and Axiom 3 we have that $Y$ is a convex set of allocation processes. Hence, by Theorem 1, the concept of ``efficient allocation process'' $\hat{y}$ is now characterized by profit maximization. That is, maximization of $p \cdot y$ with respect to $y$ over the set of allocation processes $Y$ at any given time $t$. Given that $Y$ 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 $p \cdot y$ is a continuous function.

From Axiom 1 we have that

$$y = A \cdot \lambda = [a^1, a^2, \cdots, a^m] \cdot \left( \b... ...lambda_m \end{array} \right) = \sum_{j} \lambda_j \cdot a^j$$

with $\lambda_j \geq 0$, $j=1, 2, \cdots, m$. Following Axiom 2 through Axiom 4 the basic allocation processes $a^j$ may, for example, have the form

$$a^j = ( 0, \cdots, 0, \overbrace{1}^{j} , 0, \cdots, 0; \overbrace{-1/Cost_{Q_j}}^{m+1} )^T \ , \ \ j=1, 2, \cdots, m$$

with $Cost_{Q_j}$ being the cost of quantization (bits per pixel) for $Q_j$ at the given time. The fraction $-1/Cost_{Q_j}$ is a normalized measure of bit consumption when using $a^j$. 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 $y = \sum_{j} \lambda_j \cdot a^j$ we then have that $y$ assigns $\lambda_j$ bits to quantizer $Q_j$, $j=1, 2, \cdots, m$, with a total bit consumption of $- \sum_{j=1}^m \frac{\lambda_j}{Cost_{Q_j}}$, assuming $a^j = ( 0, \cdots, 0, \overbrace{1}^{j} , 0, \cdots, 0; \overbrace{-1/Cost_{Q_j}}^{m+1} )^T$:

$$y = \sum_{j} \lambda_j \cdot a^j= (\lambda_1 , \cdots, \lambda_m, - \sum_{j=1} ^{m} \frac{\lambda_j}{Cost_{Q_j}})^T.$$

Then, it follows that the bit allocation set $Y$

$$Y \equiv \{ y \ : \ y = A \cdot \lambda; \ \lambda \stackrel{... ...lambda_j \cdot a^j_i \vert \leq R_i, \ i= 1, \cdots, m+1 $} \}$$

with resource limitation $\left\vert \sum_{j} \lambda_j \cdot a^j_i \right\vert \leq R_i$ at time $t$, can be characterized by linear inequalities such as:

$$\begin{eqnarray*} \lambda_1 & \leq & R_1 \\ \lambda_2 & \leq & R_2 \\ & \vd... ... \\ \sum_{j=1}^m \frac{\lambda_j}{Cost_{Q_j}}& \leq & R_{m+1} \end{eqnarray*}$$

where $R = (R_1, R_2, \cdots, R_m; R_{m+1})^T$; $R_j$ denotes the $Q_j$'s resource limitation at this time $t$, with $j=1, 2, \cdots, m$; and $R_{m+1}$ is the available bit consumption at $t$.

Then the problem of finding $\lambda_1 , \cdots, \lambda_m$ which maximizes

$$p \cdot y$$

where $y = \left(\lambda_1 , \cdots, \lambda_m, - \sum_{j=1} ^{m} \frac{\lambda_j}{Cost_{Q_j}} \right)^T$, subject to the constraints

$$\begin{eqnarray*} \lambda_j & \leq & R_j, \ j=1, \cdots, m \\ \sum_{j=1}^m \frac{\lambda_j}{Cost_{Q_j}} & \leq & R_{m+1} \end{eqnarray*}$$

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 $Q_1, Q_2, Q_3$ at a certain time $t$. We have that the respective cost of quantization $Cost_{Q_j}$ for each quantizer $Q_j$ is: $Cost_{Q_1} = 0.2$ bpp; $Cost_{Q_2} = 0.1$ bpp; and $Cost_{Q_3} = 0.5$ bpp.

The three basic allocation processes are (Table I):

$$a^1 = (1,0,0,-1/Cost_{Q_1})^T = (1,0,0,-5)^T,$$

$$a^2 =(0,1,0,-1/Cost_{Q_2})^T = (0,1,0,-10)^T,$$

and

$$a^3 =(0,1,0,-1/Cost_{Q_3})^T= (0,0,1,-2)^T.$$

For example, if these three basic allocation processes are operated at intensity $(\lambda_1 , \lambda_2, \lambda_3)^T = (144, 0, 31)^T$ expressing quantizers' allocation choices, the resultant allocation process (representing a new combination of bit allocation and total consumption):

$$y = [a^1, a^2, a^3] \cdot \left( \begin{array}{c} \lambda_1... ...( \begin{array}{c} 144 \\ 0 \\ 31 \\ - 782 \end{array} \right)$$ (4)

Table I:

$a^j_i, \ i=1,\cdots, 4$	Basic Alloc. Processes
	$a^1$	$a^2$	$a^3$
$Q_1$ Allocation	1	0	0
$Q_2$ Allocation	0	1	0
$Q_3$ Allocation	0	0	1
$- \frac{1}{ \mbox{Cost of Quantization (bpp)} }$	$-\frac{1}{0.2}$	$-\frac{1}{0.1}$	$-\frac{1}{0.5}$

For this example we assume that the imputed profit vector $p$ is

$$( p_1, p_2, p_3; p_4)^T = (0.3, 0.4, 0.2; 0)^T.$$

The bit allocation set $Y$ is characterized by available bit consumption and resources at this time: (i) $Q_1$ resource limitation at $t$ is $R_1 = 50$ bits; (ii) $Q_2$ resource limitation at $t$ is $R_2 = 50$ bits; (iii) $Q_3$ resource limitation at $t$ is $R_3 = 25$ bits; and (iv) available bit consumption at time $t$ is $R_4= 350$ bits.

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

$$\mbox{ Select } \ (\lambda_1 , \lambda_2, \lambda_3) \ \mbox{ to }$$

$$\mbox{ maximize} \ 0.3 \lambda_1 + 0.4 \lambda_2 + 0.2 \lambda_3$$

subject to

$$\begin{eqnarray*} \lambda_1 & \leq & 50\\ \lambda_2 & \leq & 50 \\ \lambda_... ...& 25 \\ 5 \lambda_1 + 10 \lambda_2 + 2 \lambda_3 & \leq & 350 \end{eqnarray*}$$

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 $\lambda_j$ represents the efficient allocation for quantizer $Q_j$): (i) $\lambda_1 = 50$ bits; (ii) $\lambda_2 = 5$ bits; and (iii) $\lambda_3 = 25$ 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.