Zhibin PAN, Koji KOTANI¹ and Tadahiro OHMI

New Industry Creation Hatchery Center, Tohoku University, Aza-aoba 10, Aramaki, Aoba-ku, Sendai 980-8579, Japan

¹Department of Electronic Engineering, Graduate School of Engineering, Tohoku University, Aza-aoba 10, Aramaki, Aoba-ku, Sendai 980-8579, Japan

(Received August 19, 2004; Revised November 3, 2004; Accepted February 15, 2005)

The encoding process of finding the best-matched codeword (winner) for a certain input vector in image vector quantization (VQ) is computationally very expensive due to a lot of k-dimensional Euclidean distance computations. In order to speed up the VQ encoding process, it is beneficial to firstly estimate how large the Euclidean distance is between the input vector and a candidate codeword by using appropriate low dimensional features of a vector instead of an immediate Euclidean distance computation. If the estimated Euclidean distance is large enough, it implies that the current candidate codeword could not be a winner so that it can be rejected safely and thus avoid actual Euclidean distance computation. Sum (1-D), L₂ norm (1-D) and partial sums (2-D) of a vector are used together as the appropriate features in this paper because they are the first three simplest features. Then, four estimations of Euclidean distance between the input vector and a codeword are connected to each other by the Cauchy–Schwarz inequality to realize codeword rejection. For typical standard images with very different details (Lena, F-16, Pepper and Baboon), the final remaining must-do actual Euclidean distance computations can be eliminated obviously and the total computational cost including all overhead can also be reduced obviously compared to the state-of-the-art EEENNS method meanwhile keeping a full search (FS) equivalent PSNR.

Key words: fast encoding, image vector quantization, low dimensional features, Euclidean distance estimation