We address the bit allocation problem in scenarios where there exist two-dimensional (2D) dependencies in the bit allocation, i.e., where the allocation involves a 2D set of coding units (e.g., DCT blocks in standard MPEG coding) and where the rate-distortion (RD) characteristics of each coding unit depend on one or more of the other coding units. These coding units can be located anywhere in 2D space. As an example we consider MPEG-4 intra-coding where, in order to further reduce the redundancy between coefficients, both the DC and certain of the AC coefficients of each block are predicted from the corresponding coefficients in either the previous block in the same line (to the left) or the one above the current block. To find the optimal solution may be a time-consuming problem, given that the RD characteristics of each block depend on those of the neighbors.
Greedy search approaches are popular due to their low complexity and low memory consumption, but they may be far from optimal due to the dependencies in the coding. In this work, we propose an iterative message-passing technique to solve 2D dependent bit allocation problems. This technique is based on (i) Soft-in/Soft-out (SISO) algorithms first used in the context of Turbo codes, (ii) a grid model, and (iii) Lagrangian optimization techniques. In order to solve this problem our approach is to iteratively compute the soft information of a current DCT block (intrinsic information) and pass the soft decision (extrinsic information) to other nearby DCT block(s). Since the computational complexity is also dominated by the data
generation phase, i.e., in the Rate-Distortion (RD) data population process, we introduce an approximation method to eliminate the need to generate the entire set of RD points. Experimental studies reveal that the system that uses the proposed message-passing algorithm is able to outperform the greedy search approach by 0.57 dB on average. We also show that the proposed algorithm requires slightly more memory and higher complexity than the greedy search approach.
Multiple Description Coding (MDC) techniques have been explored in recent years as an alternative to other methods to provide robustness to multimedia information in the presence of losses. In a MDC approach some redundancy is preserved in the source coding so that, after appropriate packetization, if packet losses occur it is possible to recover by exploiting the redundancy (statistical or deterministic) between what was received and what was lost. While MDC techniques have shown some promising results, one potential drawback is the fact that changing their redundancy level may entail significant changes to the system. Since the level of redundancy should be adjusted to match the specific channel conditions, the difficulty in adapting can be a significant problem for time varying transmission scenarios. As an example, MDC techniques based on transform coding would require a modification of the transform at encoder and decoder each time the channel conditions change. In our previous work, we have proposed a simple approach for MDC that involves using a polyphase transform and deterministic redundancy (e.g., each sample of input data is transmitted several times, with different coding rates). This approach is useful in that it greatly simplifies the design of a MDC scheme, since the rate allocation determines the amount of redundancy. Moreover, it provides a great deal of flexibility as it enables the choice of redundancy to be almost arbitrary. To demonstrate the effectiveness of our system we introduce an optimal bit allocation algorithm that allows us to select the amount of redundancy to be introduced in the signal that best matches a given target packet loss rate. It is clear that such a trade- off exists, as the level of redundancy should increase when the packet loss rate increases, at the cost of some degradation in the corresponding error free performance. Our results show significant differences between optimal and suboptimal choices of redundancy. Moreover, given that the decoder remains unchanged when the bit allocation changes it is possible to adapt very simply to the changes in channel behavior without requiring a change in the packet sizes, or the structure of the decoder.