
BioIngenium
Group
Centro de Telemedicina
Universidad Nacional de Colombia 





Distributed Genetic Algorithm for Subtraction
Radiography 





4. Results
Experiments were performed using a set of ten radiographs pairs. Figure 1 shows a pair of radiographs to be subtracted
(top row). The bottom row displays subtraction without (left) and with (right) geometric correction. Null intensity level
is shifted to 128 because it makes tissue changes easily observed. In this particular example can be appreciated that
the match is precise enough to make objective measurements in spite of the fact that in the second radiograph the fifth
tooth (from left to right) is nearly hidden. The small spot, likely an artifact, that appears in both images is observed
in the resultant image in white indicating that a pure difference is present. In the resultant image can be observed also
that at the root of the second and third teeth appears a difference which corresponds to new tissue developed after a
treatment. These changes are impossible to be observed at the raw difference image (bottom left). Similarly, in this image
the bone pattern is blurred and impossible to be distinguished, while in the resultant image the trabecular bone pattern
reappears. For the entire set of test images, matching has been visually assessed by two experts in the domain who have
judged that the alignment is sufficiently accurate to get objective measurements, while maintaining acceptable computation
times. 








Experiment 
CR = 0.6930445526033042 
max_iterations = 30 
An = 09.9258612306013260 
population_size = 120 
Sc = +00.9916349314121947 
tournament_size = 20 
Tx = 08.9033643041469650 
max_inner_iterations = 20 
Ty = +25.3018759289678400 
crossover_probability = 0.65 

mutation_probability = 0.21 










Experiment 
CR = 0.8957161050262891 
max_iterations = 30 
An = +01.7920319632026953 
population_size = 120 
Sc = +00.9954482032883614 
tournament_size = 20 
Tx = 04.4339406498523300 
max_inner_iterations = 20 
Ty = +04.2145305568715540 
crossover_probability = 0.71 

mutation_probability = 0.15 







Experiment 
CR = 0.7212351655930667 
max_iterations = 30 
An = 04.5802579406513200 
population_size = 120 
Sc = +00.9775187636040109 
tournament_size = 20 
Tx = 05.7638645832618330 
max_inner_iterations = 20 
Ty = 01.3525751915174202 
crossover_probability = 0.61 

mutation_probability = 0.17 







Parameter Analysis 


The first analysis was conducted to determine
two basic parameters of the GA: population size and selection scheme used to choose the parents for crossover. Two common
options for the selection phase are tournament and elitism. In tournament selection of size N, N individuals
are selected at random and the fittest is selected. Elitism is a particular case of tournament where the size of the tournament
equals the size of the population, so the best individual is always preserved.
Figure 4 shows the experiments performed to find the most appropriate population size. Most appropriate population size
was found to be 120 in an average of the ten radiographs pairs subtracted. Over this value, the process slows down and
no better results are obtained. 





Figure 4. 








Fig 5 shows that for this particular problem,
tournament is the best strategy when selecting the parents for a new generation. Best selection scheme was found to be
tournament of size 20 in average. The other parameters for analysis are the crossover and mutation probabilities. The
combination of probabilities that yielded the best results were 0.65 and 0.21 respectively. 





Figure 5. 








The average time to compute an experiment with
a population of 120 individuals is about 48 minutes if run on a single machine. This time was reduced to less than three
minutes using the parallel implementation of the GA. The speedup obtained by parallelizing the algorithm is then near
17 and can be explained by examining the timing profile of the sequential GA (Fig. 6), where about 95 percent of the time
is spent on applying the affine transformation and computing the correlation ratio. 





Figure 6. 

















> conclusions 


< algorithm 






