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