Tree-Structured Index Grouping Algorithm for Lossless Coding of VQ Index Map

Abstract

In this paper, a new algorithm is proposed for removing the spatial redundancy of the index values of the codevectors after encoding the image using Vector Quantization. This algorithm, called the Tree-Structured Index Grouping algorithm (TSIG), employs a combination of multipath search and the Index Grouping algorithm to encode the index map in a lossless fashion. After each search, based on the index values occurred in the search path, a particular bit pattern is transmitted. The performance of this algorithm is investigated on still 8-bit grayscale images and compared with the Index Grouping algorithm results. Also, a Finite State Vector Quantization (FSVQ) reordering procedure for selecting the subcodebook is investigated and the performance of the encoder is measured in terms of BPP, PSNR and encoding time. Further, to improve the performance of the algorithm, a combination of FSVQ and TSIG algorithm is proposed.

Indexing terms:

• Vector quantization
• FSVQ
• Index grouping
• Tree-structured index grouping
• Codebook
• Subcodebook

Additional information

Notes on contributors

Satish Singh

Satish Singh born in 1980 and is a final year student of Electronics and Communication Engineering in the Indian Institute of Technology, Guwahati. Worked in a project under the supervision of Dr B Chanda in the Indian Statistical Institute, Calcutta in 2001. His research interests are Communication Systems and Image Processing.

Bhabatosh Chanda

Bhabatosh Chanda born in 1957. Received BE in Electronics and Telecommunication Engineering and PhD in Electrical Engineering from University of Calcutta in 1979 and 1988 respectively. Received “Young Scientist Medal” of Indian National Science Academy in 1989 and “Computer Engineering Division Medal” of the Institution of Engineers (India) in 1998. He is also recepient of UN fellowship, UNESCO-INRIA fellowship and Diamond Jubilee fellowship of National Academy of Science, India. He worked at Intelligent System lab, University of Washington, Seattle, USA as a visiting faculty from 1995 to 1996. He has published more than 70 technical articles. His research interest includes Image Processing, Pattern Recognition, Computer Vision and Mathematical Morphology. Currently working as Professor in the Indian Statistical Institute, Calcutta, India.