An improved full-search-equivalent vector quantization method using the law of cosines

Vector quantization (VQ) is a well-known signal compression method. In VQ, the search process to find the winner for an input vector either at the codebook generation stage or the VQ encoding stage is extremely time consuming. By using the law of cosines to estimate the Euclidean distance first, Mielikainen has developed a highly efficient full-search-equivalent algorithm. However, some computational redundancies still exist in it. In this letter, we introduce an additional new estimation for the Euclidean distance and then optimize the computing way given by Mielikainen. Mathematical analyses show that our proposed search method can improve Mielikainen´s method. And experimental results of VQ encoding demonstrate that the proposed method is very search effective.