A fast exact GLA based on code vector activity detection

Author

Kaukoranta, Timo ; Fränti, Pasi ; Nevalainen, Olli

Author_Institution

Dept. of Comput. Sci., Turku Univ., Finland

Volume

9

Issue

8

fYear

2000

fDate

8/1/2000 12:00:00 AM

Firstpage

1337

Lastpage

1342

Abstract

This paper introduces a new method for reducing the number of distance calculations in the generalized Lloyd algorithm (GLA), which is a widely used method to construct a codebook in vector quantization. Reduced comparison search detects the activity of the code vectors and utilizes it on the classification of the training vectors. For training vectors whose current code vector has not been modified, we calculate distances only to the active code vectors. A large proportion of the distance calculations can be omitted without sacrificing the optimality of the partition. The new method is included in several fast GLA variants reducing their running times over 50% on average

Keywords

image classification; image coding; search problems; vector quantisation; VQ; code vector activity detection; codebook; distance calculations reduction; fast exact GLA; generalized Lloyd algorithm; image coding; reduced comparison search; running time reduction; training vectors classification; vector quantization; Application software; Clustering algorithms; Computer science; Genetic algorithms; Image coding; Image generation; Iterative algorithms; Iterative methods; Partitioning algorithms; Vector quantization;

fLanguage

English

Journal_Title

Image Processing, IEEE Transactions on

Publisher

ieee

ISSN

1057-7149

Type

jour

DOI

10.1109/83.855429

Filename

855429