Regresar

Halftone image generation using evolutionary computation

Abstract:

In this chapter, we described several image halftoning schemes using evolutionary computation (EC). We first explained the basic approach that uses a simple GA "figure presented" "Table presented" to solve the halftoning problem, in which the input image is divided into small image blocks and the corresponding halftone block is generated by evolving chromosomes with two kinds of evaluation functions for (i) gray level precision and (ii) spatial resolution. This approach is promising in the sense that we can produce higher quality halftone images than conventional schemes such as ordered dithering, error diffusion, and so on. However, this scheme uses a substantial amount of computer memory and processing time that deprive it from practical implementations. To solve these drawbacks, next we presented an accelerated image halftoning scheme using an improved GA (GA-SRM) which uses two kinds of genetic operators, CM and SRM, and extinctive selection. If we introduce adaptive dynamic block (ADB) reduction with qualitative mutation for SRM, we can drastically reduce memory size and processing time to generate halftone images without compromising the image quality. Only 2% of the population size and 15% of the evaluations were required to attain the same image quality obtained by the basic scheme. Third, we focused on the multiobjective nature of the image halftoning problem "figure presented" to simultaneously generate halftone images having various combination of gray level precision and spatial resolution. The improved halftoning scheme using GASRM was extended to a multiobjective one for this purpose as well as to reduce total processing time. Consequently, we could reduce total processing time to 6% to generate simultaneously 11 halftone images with different weights for the two evaluation functions. Finally, we presented an interblock evaluation method to further reduce evaluation numbers in the GA-based image halftoning technique. We designed the algorithm to avoid noise in the fitness function by evolving all image blocks concurrently, exploiting the interblock correlation, and sharing information between neighbor image blocks. With this scheme, we could further reduce evaluation numbers to produce high-quality halftone images. Only 240 evaluations were required to surpass the reference value of image quality achieved by the basic scheme, which means only 0.6% of the total evaluation numbers required in the basic approach. We mainly focused on the reduction of computational cost and memory configuration in GA-based halftoning schemes. However, several possibilities exist for further improvement and extensions that should be investigated. For example, this scheme can be extended to multilevel halftone image generation [35, 36], and color halftone image generation which is now being investigated by the authors. In case of color halftoning, evaluation functions should be properly modified by considering CMYK representation of colors for printing devices. Also, another possibility is information security for halftone images by digital watermarking [13, 22, 26, 27]. One approach [31] shares a signature image into two halftone images. In this method, the embedded secret image can be decoded by optically overlapping the two images generated for authentication and delivery. These are only a few trials among several possibilities and the authors are looking forward to further improvement and development of this research field.