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.
 
     
 
Figure 1.  
 
 
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  
 
     
 
Figure 2.  
 
 
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  
 
 
   
Figure 3.  
   
 
 
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  
   
     
   
     
      > Aviso Legal