3.GENETIC ALGORITHM PRINCIPLES
Genetic algorithms are search algorithms based on the
mechanics of natural selection and natural genetics. They make
use of fittest survivals to exchanges information in randomized
manner. In every generation, a new set of strings is created
using operators like reproduction, crossover and mutation.
Genetic algorithm is most of the cases consists of three
operators namely,
a. Reproduction
b. Crossover
c. Mutation
Reproduction is the process in which the strings are copied
according to some fitness criteria suitable for particular field of
application. Reproduction operator can be implemented in
4. GENETIC ALGORITHM FOR RATE CONSTRAINED
VERSION OF JPEG
We start with initial sets of quantization tables which are
generated randomly. The input values for algorithm are image,
desired file size after compression, crossover and mutation
points, crossover and mutation points, maximum number of
iterations and error allowed in desired file size (aerror).
Algorithm implements the tournament selection method for
reproduction and single point crossover. Fitness criteria is a
function of error occurred in getting desired file size (ferror)
and the mean squared error (MSE). Equal weightage is given
for both of these factors. Implementation terminates either if
the error becomes less than allowable error or if the number of
iterations exceeds the specified one, whichever occurs first.
Provision is also made to specify the range of quantization
values and to sort these values in zigzag manner.
The algorithm is given below:
A. Get the required inputs from user (explained above)
B. Random generation of quantization tables
C. while (iterations « specified value) do
a. Compress and decompress image using new
candidate solutions
b. Calculate ferror and MSE
if(ferror <= aerror)
1. Output the quantization table and
corresponding images
2. Exit.
endif
c. Determine fitness values
d. Sorting according to fitness values
e. Determine the new population values according to
crossover and mutation probabilities.
f. Implement reproduction, crossover and mutation
operators to get new population
end while
5. RESULTS AND DISCUSSION
Two remote sensing images are used for the purpose of testing.
The first image is from IKONOS with Im resolution showing
part of Denver city, while other image is from IRS-1D, B4
showing part of Powai (Mumbai) area. The images are tested
IAPRS & SIS, Vol.34, Part 7, “Resource and Environmental Monitoring”, Hyderabad, India,2002
different ways like roulette wheel selection, tournament
selection etc.
In crossover, first the two strings from mating pool are selected
at random and the string values after the specified crossover
point are swapped. For example consider two strings S1, S2
and crossover point is 4,
A1=00110111
A2=10001010
After crossover,
Al’ =0011.10 1,0
A2'z10000111
Mutation is occasional random alteration of the value of the
string position. In binary coding, this simply means changing a
0 to 1 and vice versa in a string.
for different bit rates. The maximum number of iterations
permitted was 50. The results are shown in Table 1. Results
clearly show that the actual bit rates are very close to target bit
rates. Thus the algorithm gives the quantization table which can
be used to get the desired file size/compression ratio from
JPEG method. Different combinations of genetic algorithm
parameters can be tried to get still closer bit rates. Fig. 1 and
Fig. 2 show the compressed and original images. Tables 2 and
3 show sample quantization tables generated by the algorithm.
TABLE 1. PERFORMANCE OF THE ALGORITHM
FOR DESIRED BIT RATES
Test Target Actual Population
Images bitrate bitrate Size of
(bpp) (bpp) genetic alg.
1.600 1.599 50
Denver 0.800 0.804 200
0.533 0.530 100
0.400 0.401 200
0.800 0.796 50
Powai 0.533 0.533 50
0.400 0.401 50
Table 2. Quantization Table for Denver Image at 1:10
compression ratio
2231: 26 49.263... 95; +88: 138
29.39 54 68 822.89. 130; 138
33 53 70 73 96 134 139 207
4l 65 72 99 124 150 176 212
70: 72 108 122 144 183 215 235
72:116 127 155 180: 221-234 244
118 114 164 171 219. 236 : 247 +250
113 16l 162 228 230-252 253-250
WAL FA anal a) .d. 4
WINE OO BE ET pum
EEE ae»
i 4