Two Fast Nearest Neighbor Searching Algorithms for Vector Quantization
Summary :
In this paper, two efficient codebook searching algorithms for vector quantization (VQ) are presented. The first fast search algorithm utilizes the compactness property of signal energy of orthogonal transformation. On the transformed domain, the algorithm uses geometrical relations between the input vector and codeword to discard many unlikely codewords. The second algorithm, which transforms principal components only, is proposed to alleviate some calculation overhead and the amount of storage. The relation between the principal components and the input vector is utilized in the second algorithm. Since both of the proposed algorithms reject those codewords that are impossible to be the nearest codeword, they produce the same output as conventional full search algorithm. Simulation results confirm the effectiveness of the proposed algorithms.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.10 pp.2569-2575
- Publication Date
- 2001/10/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Algorithms and Data Structures
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
SeongJoon BAEK, Koeng-Mo SUNG, "Two Fast Nearest Neighbor Searching Algorithms for Vector Quantization" in IEICE TRANSACTIONS on Fundamentals,
vol. E84-A, no. 10, pp. 2569-2575, October 2001, doi: .
Abstract: In this paper, two efficient codebook searching algorithms for vector quantization (VQ) are presented. The first fast search algorithm utilizes the compactness property of signal energy of orthogonal transformation. On the transformed domain, the algorithm uses geometrical relations between the input vector and codeword to discard many unlikely codewords. The second algorithm, which transforms principal components only, is proposed to alleviate some calculation overhead and the amount of storage. The relation between the principal components and the input vector is utilized in the second algorithm. Since both of the proposed algorithms reject those codewords that are impossible to be the nearest codeword, they produce the same output as conventional full search algorithm. Simulation results confirm the effectiveness of the proposed algorithms.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_10_2569/_p
Copy
@ARTICLE{e84-a_10_2569,
author={SeongJoon BAEK, Koeng-Mo SUNG, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Two Fast Nearest Neighbor Searching Algorithms for Vector Quantization},
year={2001},
volume={E84-A},
number={10},
pages={2569-2575},
abstract={In this paper, two efficient codebook searching algorithms for vector quantization (VQ) are presented. The first fast search algorithm utilizes the compactness property of signal energy of orthogonal transformation. On the transformed domain, the algorithm uses geometrical relations between the input vector and codeword to discard many unlikely codewords. The second algorithm, which transforms principal components only, is proposed to alleviate some calculation overhead and the amount of storage. The relation between the principal components and the input vector is utilized in the second algorithm. Since both of the proposed algorithms reject those codewords that are impossible to be the nearest codeword, they produce the same output as conventional full search algorithm. Simulation results confirm the effectiveness of the proposed algorithms.},
keywords={},
doi={},
ISSN={},
month={October},}
Copy
TY - JOUR
TI - Two Fast Nearest Neighbor Searching Algorithms for Vector Quantization
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2569
EP - 2575
AU - SeongJoon BAEK
AU - Koeng-Mo SUNG
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E84-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2001
AB - In this paper, two efficient codebook searching algorithms for vector quantization (VQ) are presented. The first fast search algorithm utilizes the compactness property of signal energy of orthogonal transformation. On the transformed domain, the algorithm uses geometrical relations between the input vector and codeword to discard many unlikely codewords. The second algorithm, which transforms principal components only, is proposed to alleviate some calculation overhead and the amount of storage. The relation between the principal components and the input vector is utilized in the second algorithm. Since both of the proposed algorithms reject those codewords that are impossible to be the nearest codeword, they produce the same output as conventional full search algorithm. Simulation results confirm the effectiveness of the proposed algorithms.
ER -
English
