# Genetic Programming to Remove Impulse Noise in Color Images
## 4 Methodology
### The Proposed Evolutionary Algorithm  
As part of the evolutionary process (also called training), the population of individuals produces offspring through crossover and mutation operators. The offspring have their fitness evaluated and compete for a place in the next generation. This process iterates until a certain number of generations is reached. This evolutionary process is described in Algorithm 1. ```
Input: A color image \(I_{N}\) perturbed by impulse noise. Output: A classification model trained to identify the noisy pixels of \(I_{N}\). 1: (Initialization) Generates a set of \(\mu\) individuals from the initial population. 2: (Evaluation) Evaluates the fitness of each individual of the initial population. 3:repeat
4: (Selection of parents) Builds a group of \(\lambda=P_{c}\mu\) individuals based on their fitness. 5: (Crossover) Recombines the pairs of selected parents to generate a set of \(\lambda\) offspring. 6: (Mutation) Mutates the offspring with a probability of \(P_{m}\) through the correction of the image. 7: (Evaluation) Evaluates the fitness of each individual of the \(\lambda\) offspring. 8: (Survivor selection) Builds a new generation of \(\mu\) individuals using deterministic fitness-based replacement. until it completes \(\tau\) generations;
9: return the fittest individual of the last generation. ```  
**Algorithm 1**The evolutionary process of the detection stage  
Line 1 of Algorithm 1 generates an initial population of \(\mu\) random individuals. To generate this population, we use the simplest and most popular full method to produce complete random trees. Each tree is generated recursively by randomly selecting primitives from the sets of functions and terminals. Primitives from the set of functions \(F\) are selected as the internal nodes of the tree, whereas those from the set of terminals \(T\) are selected as the  
Figure 2: The fitness computation process for an individual \(I_{F}\) of the population by comparing \(I_{F}\) to an original reference image \(I_{O}\). leaves. The maximum depth of each of the initial trees is constrained to three. Considering random trees of size \(O(m)\), the initial population generation requires \(O(\mu m)\) time. Lines 2 and 7 of Algorithm 1 perform the fitness evaluation of each individual of the population. The quality metrics MAE and PSNR, described in Section 3.2, are used for this aim. These metrics compare a filtered image \(I_{F}\), produced by the detection and correction stages according to each individual, with its noiseless version \(I_{O}\) (see Figure 2). The MAE indicates a better filter performance with a lower value, and the PSNR does the same with a higher value. Then, maximizing fitness is equivalent to maximizing the ratio between the MAE and PSNR. The fitness evaluation for all the \(\mu\) individuals of the population takes \(O(\mu mN)\) time. Note that the SSIM and FSIM are not considered in the fitness evaluation due to their higher computational complexity. Line 4 of Algorithm 1 performs a random selection of pairs of individuals with replacement until it generates a group of \(\lambda=P_{c}\mu\) individuals, where \(P_{c}\) denotes the crossover ratio. The tournament selection is used to randomly select three individuals from the population and then select the fittest two. Implementing the tournament selection requires \(O(\mu)\) time. Line 5 of Algorithm 1 recombines pairs of individuals from the group selected by Line 4. A one-point crossover is used, where a random vertex is chosen within two copies of parent individuals, and then they exchange the subtrees rooted at the selected vertices between them. Recombining the entire population requires \(O(\mu)\) time. Line 6 of Algorithm 1 implements the uniform mutation operator to introduce diversity in the population. This operator takes as input an individual with probability \(P_{m}\), and then it randomly selects a vertex of the tree to replace it with a new random subtree. Each subtree is generated using the full method in \(O(m)\) time.