[OPTICAL REVIEW Vol. 12, No. 3 (2005) 161-169]
© 2005 The Optical Society of Japan

Fast Encoding Method for Image Vector Quantization Based on Multiple Appropriate Features to Estimate Euclidean Distance

Zhibin PAN, Koji KOTANI1 and Tadahiro OHMI

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

1Department 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), L2 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