A Fast Image Encoding Algorithm Based on the Pyramid Structure of Codewords

Introduction

A standard vector quantization (VQ) is an efficient data compression technique that has been widely applied to image and speech coding (Gray, 1984; Linde, Buzo, & Gray, 1980). A vector quantizer of rate r bits/sample and dimension is a mapping from a -dimensional vector space into some finite subset of it, where, . The subset is called a codebook and its elements are called codewords or reproducing vectors. In the conventional full search method to encode an input vector , we have to find its distance from each of codewords, and then compare these distances to find the best-matched codeword.

A complete description of a vector quantization process includes three phases, namely training, encoding and decoding. The original signal is first segmented into individual vectors. The training phase is a codebook design procedure which tries to find the best set of representatives from a large set of input vectors using clustering algorithms like the generalized lioyd algorithm (GLA) (Gray, 1984; Linde, Buzo, & Gray, 1980). The GLA consists of alternatively applying the nearest neighbor condition and centroid condition to generate a sequence of codebooks with decreasing average distortion. The algorithm operates as follows: It begins with an initial codebook of size . It partitions the training set into sets of vectors using the nearest neighbor rule which associates each training vector with one of the codeword’s in the codebook. This partitioning defines the vector encoder mapping . Then, a new codebook is created with the new codeword’s being the centroids of each of the partition regions of input vectors. This new codebook defines the vector decoder mapping . The algorithm repeats these steps and calculates the average distortion for the new codebook over the entire training set at the end of each iteration. When the average distortion fails to decrease by a certain threshold amount, it is assumed that a local minimum in distortion has been reached and the algorithm terminates.