Full-Searching-Equivalent Vector Quantization Using Two-Bounds Triangle Inequality

Article type: Research Article

Authors: Chang, Chin-Chen | Chen, Chang-Chu

Affiliations: Department of Information Engineering and Computer Science, Feng Chia University, Taichung, Taiwan, 40724. E-mail: ccc@cs.ccu.edu.tw | Department of Computer Science and Information Engineering, National Chung Cheng University, Chiayi, Taiwan 621. E-mails: ccz@cs.ccu.edu.tw; ccchen@ctust.edu.tw

Abstract: The encoding process of vector quantization (VQ) is indeed computational complex and time consuming. Compared with actual Euclidean distance computation, some inequalities can generate estimations with less computation to filter out the impossible codevectors as well as to reduce the computation time. In this paper, we introduce a new estimation for the Euclidean distance using two-bounds triangle inequality. The experimental results show that our proposed scheme can reduce Euclidean distance computation by 71% to 94% for full search. Having been proved, our proposed scheme can reduce the computing time by 42% to 51%.

Keywords: Full-searching-equivalent, triangle inequality, vector quantization (VQ)

Journal: Fundamenta Informaticae, vol. 76, no. 1-2, pp. 25-37, 2007