Dual optimization of monochrome images tone approximation using parallel evolutionarily genetic search

The paper considers the optimization problem of tone approximation for monochrome (for example: in grayscale palette) images. The procedure of tone approximation implies the reduction of approximated image’s number of tones, which are used in image displaying, compared to number of tones in the original image. The point of the procedure optimization consists of minimization of visual quality loses that estimated according to total or mean deviation between the same pixels of original image and approximated one. As a tool of the optimization the hybrid algorithm is used. It was developed and investigated by authors. The hybrid algorithm combines heuristic and deterministic algorithms of searching the best structure of approximating palette according to criterion of deviations minimization. The heuristic algorithm is based on evolutionarily-genetic paradigm. The main goal of heuristic stage is the reduction of search area of approximating palette’s structures that are the closest to optimum. Such role for heuristic stage was defined according to its fast computational time. The goal of deterministic algorithm of directed exhaustive search is to find the nearest extreme for the result that was obtained by previous algorithm. The developed hybrid algorithm allows to provide dual optimization of tone approximation. It means that the algorithm provides a result, in which two different criteria become optimal relative to each other. The current investigation is devoted to consideration of possibility to increase the effectiveness of hybrid algorithm on the level of heuristic stage. The possibility of implementation the parallel model of evolutionarily-genetic algorithm with different settings is considered. The results of initial experiments are discussed and compared with known algorithm of tone approximation.