Title :
Nearly optimal vector quantization via linear programming
Author :
Lin, Jyh-Hun ; Vitter, Jeffrey Scott
Author_Institution :
Dept. of Comput. Sci., Brown Univ., Providence, RI, USA
Abstract :
The authors present new vector quantization algorithms. The new approach is to formulate a vector quantization problem as a 0-1 integer linear program. They first solve its relaxed linear program by linear programming techniques. Then they transform the linear program solution into a provably good solution for the vector quantization problem. These methods lead to the first known polynomial-time full-search vector quantization codebook design algorithm and tree pruning algorithm with provable worst-case performance guarantees. They also introduce the notion of pseudorandom pruned tree-structured vector quantizers. Initial experimental results on image compression are very encouraging.<>
Keywords :
data compression; image coding; linear programming; vector quantisation; 0-1 integer linear program; image compression; linear program solution; linear programming; polynomial-time full-search; pseudorandom pruned tree-structured vector quantizers; relaxed linear program; tree pruning algorithm; vector quantization algorithms; vector quantization codebook design; Algorithm design and analysis; Approximation algorithms; Clustering algorithms; Computer science; Contracts; Image coding; Iterative algorithms; Linear programming; Partitioning algorithms; Vector quantization;
Conference_Titel :
Data Compression Conference, 1992. DCC '92.
Conference_Location :
Snowbird, UT, USA
Print_ISBN :
0-8186-2717-4
DOI :
10.1109/DCC.1992.227479