Share Email Print

Proceedings Paper

Message-passing algorithm for two-dimensional dependent bit allocation
Author(s): Phoom Sagetong; Antonio Ortega
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

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.

Paper Details

Date Published: 7 May 2003
PDF: 11 pages
Proc. SPIE 5022, Image and Video Communications and Processing 2003, (7 May 2003); doi: 10.1117/12.476708
Show Author Affiliations
Phoom Sagetong, Univ. of Southern California (United States)
Antonio Ortega, Univ. of Southern California (United States)

Published in SPIE Proceedings Vol. 5022:
Image and Video Communications and Processing 2003
Bhaskaran Vasudev; T. Russell Hsing; Andrew G. Tescher; Touradj Ebrahimi, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?