Vector Quantization

Modeling the Computational Complexity of
Unconstrained Vector Quantization

Department of Electrical Engineering
CH-1015 Lausanne
Author: Stefan Gachter
Responsible assistant: Julien Reichel

 
back | home | abstract | contents | next



 
 
 
 
 
 

 

Vector quantization, as an image compression method, requires considerable computational complexity. The following report examines this complexity for the unconstrained vector quantization method, in especially for the partial search algorithm.

Unconstrained vector quantization, as a part of memoryless vector quantization, can be classified in full search and fast search algorithms. For the full search method the complete codebook is affected by encoding process, there for fast search methods only a fraction of the codebook is considered. Full search methods are the exhaustive search and partial search algorithms. Fast search methods are the triangular inequality and the vector-to-scalar elimination. For each method a description of the algorithm, the complexity and its inferior limit is given. A comparison shows that the fast search methods are always affected by a full search method. Therefor to get a model of complexity for unconstrained vector quantization, the partial distance search algorithm is simulated for different codebooks. The experimental results leads to a model with two parameters permitting the estimation of the computational complexity.

           
begin chapter | next chapter
 

back | home | abstract | contents | next chapter

Contents
1 Introduction 1.1 Principles of Vector Quantization 1.1.1 Encoder and Decoder
1.1.2 Distortion Measure
1.1.3 Codebook
  1.2 Classification of Vector Quantization 1.2.1 Vector Quantization without Memory Unconstrained Vector Quantization
Constrained Vector Quantization 1.2.2 Vector Quantization with Memory
  2 Unconstrained Vector Quantization

2.1 Full Search Vector Quantization

2.1.1 Exhaustive Search Algorithm Algorithm
Complexity 2.1.2 Partial Distance Search Algorithm Algorithm
Complexity
  2.2 Fast Search Vector Quantization 2.2.1 Triangular Inequality Elimination Algorithm
Complexity 2.2.2 Vector-to-Scalar Mapping Elimination Algorithm
Complexity 2.3 Conclusion

3 Modeling Unconstrained Vector Quantization Complexity

3.1 Complexity Structure of the Partial Search Algorithm

3.2 Parameter Estimating

3.2.1Existing Experimental Results Average Number of Iterations 3.2.2Proper Experimental Results Used Algorithm
Experimental Results
Average Number of Iterations
  3.3 Conclusion

A Parameter Calculation
 

 B MATLAB Files
  C Bibliography
  begin chapter | next chapter