Back to main page

Bit Allocation

The first step in compressing an image is to segregate the image data into different classes. Depending on the importance of the data it contains, each class is allocated a portion of the total bit budget, such that the compressed image has the minimum possible distortion. This procedure is called Bit Allocation.

The Rate-Distortion theory is often used for solving the problem of allocating bits to a set of classes, or for bitrate control in general. The theory aims at reducing the distortion for a given target bitrate, by optimally allocating bits to the various classes of data. One approach to solve the problem of Optimal Bit Allocation using the Rate-Distortion theory is given in [1], which is explained below.

1. Initially, all classes are allocated a predefined maximum number of bits.
2. For each class, one bit is reduced from its quota of allocated bits, and the distortion due to the reduction of that 1 bit is calculated.
3. Of all the classes, the class with mininum distortion for a reduction of 1 bit is noted, and 1 bit is reduced from its quota of bits.
4. The total distortion for all classes D is calculated.
5. The total rate for all the classes is calculated as R = p(i) * B(i), where p is the probability and B is the bit allocation for each class.
6. Compare the target rate and distortion specifications with the values obtained above. If not optimal, go to step 2.

In the approach explained above, we keep on reducing one bit at a time till we achieve optimality either in distortion or target rate, or both. An alternate approach which is also mentioned in [1] is to initially start with zero bits allocated for all classes, and to find the class which is most 'benefitted' by getting an additional bit. The 'benefit' of a class is defined as the decrease in distortion for that class.

Fig 1. 'Benefit' of a bit is the decrease in distortion due to receiving that bit.

As shown above, the benefit of a bit is a decreasing function of the number of bits allocated previously to the same class. Both approaches mentioned above can be used to the Bit Allocation problem.

Resources related to Bit Allocation

1. E. A. Riskin, "Optimum bit allocation via the generalized BFOS algorithm,''
   IEEE Transactions on Information Theory, vol. 37, pp. 400-402, Mar. 1991
2. Liang-jin Lin, Antonio Ortega, "Bit-Rate Control Using Piecewise Approximated Rate-Distortion Characteristics", 
   IEEE Transactions on Circuits and Systems for Video Technology, vol. 8, No. 4, pp. 446-459 , Aug. 1998
3. A. Ortega, "Optimal rate allocation under multiple rate constraints'', 
   Data Compression Conference'96, Snowbird, UT, Mar. 1996

Quantization

Entropy coding