A fast full search equivalent encoding method for vector quantization by using appropriate features

The encoding process of vector quantization (VQ) is very heavy and it constrains VQ's application a great deal. In order to speed up VQ encoding, it is most important to avoid unnecessary Euclidean distance computation (k-D) as much as possible by the difference check that uses simpler features (low dimensional) while winner searching is going on. Sum (1-D) and partial sums (2-D) are used together as the appropriate features in this paper because they are the first 2 simplest features. Then, sum difference and partial sum difference are computed as the estimations of Euclidean distance and they are connected to each other by the Cauchy-Schwarz inequality so as to reject a lot of codewords. For typical standard images with very different details (Lena, F-16, Pepper and Baboon), the final must-do Euclidean distance computation using the proposed method can be reduced to less than 10% as compared to full search (FS) meanwhile keeping the PSNR not degraded.

1. INTRODUCTION

Vector quantization (VQ) [1] is a classical but still very promising method for image compression, especially for images such as computer graphics or digitized documents that have many abrupt discontinuities. VQ uses a look-up table (called codebook) principle by template matching so as to find a closest item (winner) to an image block within the table according to a certain distortion measure (usually Manhattan distance or Euclidean distance). Then VQ only transmits the winner index instead of the winner itself to reduce the amount of image data. Because an exactly the same table (code book) is also available at the receiver, the image can be decoded easily in an inverse look-up table way by using the received winner index and then the winner itself is pasted to the corresponding position of the image to reconstruct it. Therefore, VQ has a very heavy encoding process due to a lot of distance computation for matching and a very simple decoding process. For practical purposes, one of the primary limitations to encode an image by VQ is the computational complexity.