On the Design of a Hierarchical BTC-VQ Compression System

Pasi Fr?nti, Timo Kaukoranta and Olli Nevalainen
Department of Computer Science, University of Turku
Lemmink?isenkatu 14 A, FIN-20520 Turku, FINLAND
E-mail: franti@utu.fi

In the present paper we study the use of vector quantization in the BTC-VQ image compression system. We propose an inverted order of proceeding in the BTC-VQ algorithm, so that the interaction of coding the bit plane and the quantization data will be taken into consideration. The quality of the image depends radically on the codebook used in VQ. The use of frequencies in the selection of the initial codebook turns out to be superior to random selection.

Key words: image compression, vector quantization, quantization methods, hierarchical decomposition, codebook construction.

1. INTRODUCTION

Block truncation coding (BTC) [2] is a simple way to compress digital gray-scale images. The basic idea in the method is to divide the pixel matrix into blocks and quantize the pixels to two different values, a and b. These along with a bit plane (bit matrix), indicating the choice between a and b, are transmitted as a compressed image.

A large number of variants of the basic BTC-algorithm have been proposed during the past fifteen years [6]. Their performance can be compared using the bit rate (bits per pixel), the mean square error (MSE) of the reconstructed image, and the overall complexity of the algorithm. Efficient variants of BTC typically achieve bit rates of the order of magnitude 1.25 with MSE 32.5 for the test image Lena [5, 13].

Several approaches have been proposed for reducing the volume of the bit plane by the use of vector quantization (VQ) [3, 17, 19, 20, 21] or a similar ad hoc technique [13]. The basic idea of VQ is to select a small set of representative vectors (binary blocks) and to code all possible vectors by an index to this set. The codebook is generated off-line on the basis of training vectors by using a suitable algorithm, like the generalized Lloyd algorithm [7, 12].

The representative for a bit plane can be chosen by a full search, i.e. by testing each candidate codevector and selecting the one which minimizes the given distortion function. A localized search was proposed by Weitzman and Mitchell [19]. They divide the codebook into several overlapping sub-codebooks. For each bit plane, its combination index is calculated. It determines the sub-codebook in which the search is performed.