Fast R-D Optimal Packetization of Embedded Bitstreams into Independent Source Packets

This work addresses the rate-distortion (R-D) optimal packetization (OP) of embedded bitstreams into independent source packets, in order to limit error propagation in transmission over packet lossy channels. The input embedded stream is assumed to be an interleaving of K independently decodable basic streams. To form N independent source packets, each of L symbols, the set of basic streams is partitioned into N groups. The objective of R-D OP is to find the partitioning which minimizes the distortion when all packets are decoded. We present a fast divide and conquer algorithm to find the globally optimal solution, under the assumption that all basic streams have convex R-D curves. The proposed algorithm reduces the running time from O(K²(L + N)) achieved by the existing dynamic programming solution, to O(NKL log K). Experiments on SPIHT coded images show that the speed up is much higher than predicted theoretically, thus rendering the R-D OP feasible in practice.