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

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

Ahmed A. Radwan (Minia University, Egypt), Ahmed Swilem (Minia University, Egypt) and Mamdouh M. Gomaa (Minia University, Egypt)
DOI: 10.4018/978-1-60960-563-6.ch015


This article presents a very simple and efficient algorithm for codeword search in the vector quantization encoding. This algorithm uses 2-pixel merging norm pyramid structure to speed up the closest codeword search process. The authors first derive a condition to eliminate unnecessary matching operations from the search procedure. Then, based on this elimination condition, a fast search algorithm is suggested. Simulation results show that, the proposed search algorithm reduces the encoding complexity while maintaining the same encoding quality as that of the full search algorithm. It is also found that the proposed algorithm outperforms the existing search algorithms.
Chapter Preview


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 Rh into some finite subset of it, Y = {yi; i = 1, 2, …, N} where, N = 2kr. 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 = (x1, x2, …, xk), 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.

Complete Chapter List

Search this Book: