18-09-2012, 10:20 AM
Generating Test Images and Halftoning Filters with Co-Evolutionary GA
1Generating Test.pdf (Size: 300.03 KB / Downloads: 42)
Abstract:
In this paper, we evaluate the potentials of using co-evolutionary optimization method to automatically generate
both halftoning filters for the image processing software and test images for them. One genetic algorithm generates halftone
filters and at the same time, another genetic algorithm tries to create the hardest test image for each filter. The best filter being
the one for which the hardest test image, when dithered, differs least from the original. An image population defines the
fitness of halftoning filters and respectively filter population defines the fitness of test image.
Introduction
There does not seem to be much systematic research in the
field of test image evaluation. How to determine that a
particular test image is good for testing some specific
image-processing algorithm? What are the essential
characteristics of a good test image? Much more often than
not researchers rely on commonly used and unfortunately
very limited test image sets. We encountered this problem,
when we wanted to test an image halftoning system we
implemented for an ink jet marking machine [1]. In other
study [2] we used genetic algorithms (GA) for software
testing purposes. In this work we try to combine these two
previous studies in order to use GAs for generating test
images in order to test the quality of the halftoning
software.
Genetic Algorithms And Co-Evolution
Genetic algorithms [4] are optimization methods that are
based on simplified computational models of evolutionary
biology in nature. A GA forms a kind of electronic
population, the members of which fight for survival,
adapting as well as possible to the environment, which is an
optimization problem. GAs use genetic operations, such as
selection, crossover, and mutation in order to generate
solution trials that meet the given optimization constraints
ever better. Surviving and crossbreeding possibilities
depend on how well individuals fulfill the target function.
Dithering And Image Comparison
Digital halftoning [7], or dithering, is a method used to
convert continuous tone images into images with a limited
number of tones, usually only two: black and white. The
main problem is to do the halftoning so that the bi-level
output image does not contain prominent artifacts, such as
alias, moiré, lines or clusters, caused by dot placement. The
average density of the halftoned dot pattern should
interpolate as precisely the original tones as possible.
Dithering methods include static methods, where each pixel
is compared to a threshold value, obtained e.g. from a
threshold matrix
Related Work
Co-evolution is mostly applied in game playing research,
however it seem to be getting more applications in the
technical research also. Goulermas and Liatsis [12] have
applied co-evolution for feature-based matching of edges in
stereo imaginary. They applied parallel GA, where each
individual GA aims local optimum, while information
exchange between neighboring GAs are applied to achieve
symbiotic co-evolution towards global optimum. They think
that searching global and local level optimums concurrently
has advantages compared to other approaches.
Miyojim and Cheng [13] proposed that test images with
characteristics close enough to the reality could be
generated with computer and applied for testing pattern
recognition algorithms. We agree with their statement
“researchers often reuse the same few available test images,
which may compromise the thoroughness of the
investigation”. They also conclude that the proposed
approach can be very useful for the development of
computer vision, image processing and pattern recognition
algorithms.
Experimental Results
The results were generated by running five test runs with
two different dithering method implementations, threshold
matrix TH and error diffusion ER, and two different ways to
initialize the population, random RD and given GV. The
primary goal was not to find the best possible results after
several test runs, but to see whether the results have some
similarities in common or not, i.e. to test the stability of the
proposed method.
Figure 4 shows as an example typical fitness
development curves when optimizing test images and
threshold matrices concurrently. We are trying to maximize
the image fitness values. At the same time, we are also
trying to minimize the filter fitness values. We can assume
that the species, towards which optimization direction the
curves bends, is dominating the optimization process.
Conclusions and Future
The results with the threshold matrix optimization showed
that good threshold matrices are difficult to optimize.
Exceeding the performance of the well-known ordered
threshold is difficult. Good error diffusion coefficients are
easier to generate, therefore results with them may be more
fruitful. It seems that co-evolution creates hard test images
for error diffusion, and vice versa, the coefficients that
halftones them better than those filters represented in
literature.