DocumentCode :
387995
Title :
Binary search trees for vector quantisation
Author :
Lowry, A. ; Hossain, Sqama ; Millar, W.
Author_Institution :
Queen´´s University of Belfast, N Ireland
Volume :
12
fYear :
1987
fDate :
31868
Firstpage :
2205
Lastpage :
2208
Abstract :
This paper presents a data structure based on the k-d binary tree which substantially reduces the search complexity of a full search vector quantiser with negligible degradation in signal-to-noise ratio. The search complexity is 
rather than N for a codebook of dimension k and size N. Special features of the structure are (1) the use of a rotational transform prior to encoding and (2) the computational efficiency of the design algorithm due to the simple structure of the k-d tree.
rather than N for a codebook of dimension k and size N. Special features of the structure are (1) the use of a rotational transform prior to encoding and (2) the computational efficiency of the design algorithm due to the simple structure of the k-d tree.Keywords :
Algorithm design and analysis; Binary search trees; Binary trees; Clustering algorithms; Degradation; Distortion measurement; Encoding; Iterative algorithms; Tree data structures; Vector quantization;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Acoustics, Speech, and Signal Processing, IEEE International Conference on ICASSP '87.
Type :
conf
DOI :
10.1109/ICASSP.1987.1169380
Filename :
1169380
Link To Document :
