closest codeword search algorithms for vector quantization
Chang-Hsing Lee, Ling‐Hwei Chen · 1995
One of the most serious problems for vector quantization is the high computational complexity involved in searching for the closest codeword through a codebook in both codebook design and encoding phases. In this paper, based on the assumption that the distortion is measured by the squared Euclidean distance, two high-speed search methods will be proposed to speed up the search process. The first one uses the difference between the mean values of two vectors to reduce the search space. The second is to find the Karhunen-Loeve transform (KLT) for the distribution of the set of training vectors and then applies the partial distortion elimination method to the transformed vectors. Experimental results show that the proposed methods can reduce lots of mathematical operations. Zusammenfassung Eines der schwerstwiegenden Probleme bei der Vektorquantisierung ist die hohe rechnerische Komplexitlt, die mit der Suche des ngchstliegenden Kodewortes innerhalb eines Kodebuches verbunden ist, sowohl beim Entwurf des Kodebuches, als such bei der Kodierphase. In dieser Arbeit werden unter der Voraussetzung des quadriatischen Euklidischen Abstandes als Verzerrungsmaa zwei sehr schnelle Suchmethoden vorgeschlagen, urn den Suchprozelj zu beschleunigen. Die erste Methode verwendet die Differenz zwischen den Mittelwerten zweier Vektoren, urn den Suchraum zu verkleinern. Die zweite Methode besteht darin, zunIchst die Karhunen-Loeve Transformation (KLT) fiir die Verteilung der Menge der Trainingsvektoren zu finden. Danach wird die partielle Verzerrungseliminierungsmethode auf die transformierten Vektoren angewendet. Experimentelle Ergebnisse zeigen, dal3 die vorgeschlagenen Methoden die Anzahl der mathematischen Operationen erheblich vermindern kiinnen.