2006/09/22 by Xiang Huang, Xiaolin Wu, Huang, Xiang +1
Computer Science · Mathematics · #Advanced Data Compression Techniques #Advanced Image and Video Retrieval Techniques #FOS: Computer and information sciences #Image Retrieval and Classification Techniques #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.cs/0609123
Submitted to IEEE Trans. on Information Theory, Sep 2006 (30 pages, 7 figures)
arxiv created 2006/09/22 · openalex publication_date 2006/09/22 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the design of multiple description lattice vector quantizers (MDLVQ), index assignment plays a critical role. In addition, one also needs to choose the Voronoi cell size of the central lattice v, the sublattice index N, and the number of side descriptions K to minimize the expected MDLVQ distortion, given the total entropy rate of all side descriptions Rt and description loss probability p. In this paper we propose a linear-time MDLVQ index assignment algorithm for any K >= 2 balanced descriptions in any dimensions, based on a new construction of so-called K-fraction lattice. The algorithm is greedy in nature but is proven to be asymptotically (N -> infinity) optimal for any K >= 2 balanced descriptions in any dimensions, given Rt and p. The result is stronger when K = 2: the optimality holds for finite N as well, under some mild conditions. For K > 2, a local adjustment algorithm is developed to augment the greedy index assignment, and conjectured to be optimal for finite N. Our algorithmic study also leads to better understanding of v, N and K in optimal MDLVQ design. For K = 2 we derive, for the first time, a non-asymptotical closed form expression of the expected distortion of optimal MDLVQ in p, Rt, N. For K > 2, we tighten the current asymptotic formula of the expected distortion, relating the optimal values of N and K to p and Rt more precisely.