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 k is a mapping from a k-dimensional vector space R^h into some finite subset of it, Y = {y_i; i = 1, 2, …, N} where, N = 2^kr. The subset Y is called a codebook and its elements are called codewords or reproducing vectors. In the conventional full search method to encode an input vector x = (x₁, x₂, …, x_k), we have to find its distance from each of N 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 N. It partitions the training set into N sets of vectors using the nearest neighbor rule which associates each training vector with one of the N codeword’s in the codebook. This partitioning defines the vector encoder mapping Q(.). Then, a new codebook is created with the new codeword’s being the centroids of each of the N 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.

The encoding phase finds the best matched codeword for a test vector and uses the index of the codeword to represent it. A full codebook search could be used in an encoder of vector quantization to find the codeword which is the nearest neighbor to test vector. The decoding phase is simply a table look-up procedure which uses the received index to deduce the reproduction codeword. The particularly simple table look-up decoding procedure makes VQ an attractive method of data compression in practice. Both of the training and encoding phases are computation-intensive procedures. This limits the applicability of VQ.