Genetic algorithm with deterministic crossover for vector quantization

Pattern Recognition LettersPublished 1 January 2000

Pasi Fränti

DOI10.1016/s0167-8655(99)00133-6

Source URL

Citations72

SJR quartileQ1

SJR score1.00

SNIP1.43

TL;DR

A new deterministic crossover method based on the pairwise nearest neighbor method is introduced that shows that high quality codebooks can be obtained within a few minutes instead of several hours as required by the previous GA-based methods.

Abstract

Genetic algorithm (GA) provides high quality codebooks for vector quantization (VQ) at the cost of high running time. The crossover method is the most important choice of the algorithm. We introduce a new deterministic crossover method based on the pairwise nearest neighbor method. We show that high quality codebooks can be obtained within a few minutes instead of several hours as required by the previous GA-based methods. The method outperforms all comparative codebook generation methods in quality for the tested training sets.

Keywords

Computer ScienceEngineering

IEEE Transactions on Evolutionary ComputationNo free lunch theorems for optimization

13,936 Citations1997David H. Wolpert, William G. Macready

A framework is developed to explore the connection between effective optimization algorithms and the problems they are solving and a number of "no free lunch" (NFL) theorems are presented which establish that for any algorithm, any elevated performance over one class of problems is offset by performance over another class.

IEEE Transactions on CommunicationsAn Algorithm for Vector Quantizer Design

7,183 Citations1980Y. Linde, A. Buzo +1 more

An efficient and intuitive algorithm is presented for the design of vector quantizers based either on a known probabilistic model or on a long training sequence of data.

Vector Quantization and Signal Compression

7,039 Citations1992A. Gersho, Robert M. Gray

The author explains the design and implementation of the Levinson-Durbin Algorithm, which automates the very labor-intensive and therefore time-heavy and expensive process of designing and implementing a Quantizer.

IEEE Transactions on Acoustics Speech and Signal ProcessingA new vector quantization clustering algorithm

405 Citations1989W. Equitz

The pairwise nearest neighbor (PNN) algorithm is presented as an alternative to the Linde-Buzo-Gray (1980, LBG) (generalized Lloyd, 1982) algorithm for vector quantization clustering.

The Computer JournalGenetic Algorithms for Large-Scale Clustering Problems

92 Citations1997Pasi Fränti

This work considers the clustering problem in the case where the distances between elements are metric and both the number of attributes and thenumber of clusters are large, and introduces three new and efficient crossover techniques.

Pattern RecognitionTabu search algorithm for codebook generation in vector quantization

40 Citations1998Pasi Fränti, Juha Kivijärvi +1 more

The proposed algorithm first makes non-local changes to the codebook which is then fine-tuned by the generalized Lloyd algorithm, and for a set of gray-scale images, the new algorithm was better than GLA alone, and its results were comparable to simulated annealing.

Electronics LettersStochastic relaxation algorithm for improved vector quantiser design

38 Citations1989K. Zeger, A. Gersho

An easily implementable stochastic relaxation algorithm for vector quantisation design is given, which generalises the usual Lloyd iteration in codebook design by perturbing the computed entroids with independent multidimensional noise, whose variance diminishes as the algorithm progresses.

Fast implementation of the optimal PNN method

11 Citations2002Pasi Fränti, Timo Kaukoranta

This work considers the codebook generation problem involved in the design of a vector quantizer, and proposes a fast O(/spl tau/N/sup 2/) time implementation of the optimal PNN, where /spl tAU/ is observed to be significantly smaller than N in practice.

Reduced comparison search for the exact GLA

5 Citations1999Timo Kaukoranta, Pasi Fränti +1 more

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, that detects the activity of the code vectors and utilizes it on the classification of the training vectors.