AN EFFICIENT METHOD OF CONSTRUCTING L_1-TYPE NORM FEATURE TO ESTIMATE EUCLIDEAN DISTANCE FOR FAST VECTOR QUANTIZATION

摘要

In order to speed up the search process of vector quantization (VQ), it is most important to avoid actually computing k-dimensional Euclidean distance as many as possible. In order to find a best-matched codeword (winner) in the codebook for a certain input vector, it is a general way to roughly estimate other than exactly compute Euclidean distance immediately for the purpose of rejecting a candidate codeword. The lower dimensional features of a vector such as sum or the mean (L_1—type norm) and L_2 norm are widely used for this purpose. Obviously, how to construct a suitable feature is a core problem for estimating Euclidean distance. In this paper, an efficient method of constructing L_1-type norm feature is proposed by introducing a reference vector. In addition, the criterion on how to select an optimal reference vector is also given. Experimental results confirmed the effectiveness of the proposed method.