A tabu search algorithm is proposed for the codebook generation in Vec
tor quantization. The key question is the definition of neighboring so
lution. Making random modifications to the current solution alone is n
ot sufficient. The proposed algorithm first makes non-local changes to
the codebook which is then fine-tuned by the generalized Lloyd algori
thm (GLA). For a set of gray-scale images, the new algorithm was bette
r than GLA alone, and its results were comparable to simulated anneali
ng. For binary images, the tabu search approach gave the best MSE-valu
es. (C) 1998 Pattern Recognition Society. Published by Elsevier Scienc
e Ltd. All rights reserved.