Wróblewski J., 1995. Genetic approach to scalar quantisation. Proceedings of the International Workshop on Intelligent Information Systems IV, Augustów 1995. Instytut Podstaw Informatyki PAN, Warszawa.
DETAILED ABSTRACT
The scalar quantisation problem can be formulated as follows: for the probability distribution H(z), z from [a , b], find n representatives and n+1 breakpoints such that the mean-square error of quantisation is minimal. The classical algorithm for optimal quantisation (centroid algorithm )was developed in 1960 by J. Max, but the results are very sensitive to the initial state, and sometimes they are far from the global optimum. The existing methods for obtaining good initial states are useless, when we have no explicit formula for H, or if the distribution H is discrete.
Genetic Algorithm (GA) is one of the non-deterministic search method, based on the Darwinian principle of natural selection. This method can successfully find the global optimum by combining two processes: the local search on the neighbourhood of the good solutions and the global search on the distant areas with a low probability. GA finds the individual s from the state space S, that maximises the fitness value F(s), for the given positive function F. First, the population of N random objects from S is selected. Then, the population is changed T times by the selection process (individuals with the low value of F are replaced by these with the higher value of F) and by the genetic operators (mutation: small, random change of individual; crossing-over: exchange of the "genetic material" between two individuals). The best individual of the last population is taken as a result of optimisation.
In the GA approach to the quantisation problem every individual (scalar quantiser) is represented as an ordered set of representatives - floating point values in the ascending order. The initial population is created randomly with the probability distribution H. The fitness value for each individual is defined as a function of its mean-square error. The mutation affects one position of each individual with the probability Pm. The new value is selected randomly with the uniform distribution. The crossing-over operator is constructed so as the order of the values in chromosome is not disturbed: the random cross point k is selected, and the descendant of the random individuals 1 and 2 from population is combined from k elements of individual 1 and n-k+1 ones of individual 2. The centroid algorithm is applied to the whole or a part of population as an additional technique. This time-consuming optimisation is done once, after a few generations (usually after 20% of total number of generations). In the "promising objects" method, we attempt to predict the final result of the classical centroid algorithm after a few iteration. This method can be used to improve properties of the genetic algorithm (GA-PO). The fitness function is based not on the error value of the individual, but on the error value after several (usually 2 or 4) iterations of the centroid algorithm. The result of GA-PO - the best individual - is optimised then by the centroid algorithm. The method of "promising objects" can be used separately as the new search technique (PO): we can randomly choose a set of individuals, select the "most promising" of them and use the centroid algorithm to bring it to the local minimum.
A few of grey-scale images were used as a source of data for experiments. All the algorithms were tested on the discrete distributions of 256 values, which are to be reduced to n = 16 levels. The experimental results show, that GA-PO method is more effective than the standard centroid algorithm, and (for most of the tested images) centroid algorithm and GA, working during the same time (especially when the distribution H is irregular). This method (in the discrete version) can be used to scalar image quantisation (e.g. from the 8-bit grey scale to the 4-bit one), when the accuracy is more important, than the time complexity.
Bibliography:
Bucklew J.A., Gallagher N.C.Jr., 1982. A Note on the Computation of Optimal Minimum Mean-Square Error Quantizers. IEEE Transactions on Communications, Vol. COM-30, No. 1, January 1982.
Goldberg D.E., 1989. GA in Search, Optimisation, and Machine Learning. Addison-Wesley.
Holland J.H., 1975. Adaptation in natural and artificial systems. The MIT Press, Cambridge, 1992.
Jain A. K., 1989. Fundamentals of digital image processing. Prentice-Hall International, Englewood Cliffs NJ.
Koza J.R., 1992. Genetic Programming: On the Programming of Computers by Means of the Natural Selection. The MIT Press.
Max J., 1960. Quantizing for minimum distortion. IRE Trans. Inform. Theory, IT-6, 7-12.
Skarbek W., 1993. Metody reprezentacji obrazów cyfrowych. Akademicka Oficyna Wydawnicza PLJ, Warszawa.