How to use the genetic algorithm for image reconstruction?

The genetic algorithm is inspired by the biological evolution of chromosomes and is mainly used in the optimal selection of characteristics for various types of problems. Genetic algorithm basically follows the approach of heuristic algorithms to find the best possible solution close to the optimal one. This algorithm has a variety of applications in all fields, mostly in optimization problems. It can also be used for image reconstruction to get the images back to their original form. This article focuses on the application of genetic algorithm for this interesting image reconstruction application.

Contents

  1. Introduction to Genetic Algorithms
  2. What is image reconstruction?
  3. Image reconstruction using genetic algorithms
  4. Summary

Introduction to Genetic Algorithms

Genetic algorithms are basically used in optimization tasks where these algorithms follow the metaheuristic approach to get the best optimal solution among all the candidate solutions. Genetic algorithms work on the hierarchy of biological chromosomes and the algorithm tries to get the best most suitable solution to pass on to the next generation.

Are you looking for a comprehensive repository of Python libraries used in data science, check here.

Genetic algorithms initially operate on a cluster of the best possible solutions called the initial population where the cluster contains the best possible solution to the problem. Each of the solutions in the cluster is classified by certain parameters and is called Genoa in Genetic Algorithms, the genes of Genetic Algorithm will be ranked according to defined parameters. The genes that have all the defined abilities will be passed to a fitness function to determine the fitness of the best possible solutions selected from the pool of candidate solutions to the problem. If the best possible solution has the ability to inherit all the functionality of the fitness function, that solution will be passed on to the next set of generations. The overall operation of genetic algorithms takes place at three levels: selection, mutation and crossover. Let’s try to understand these standard genetic algorithm terminologies.

Selection

Selection in genetic algorithms is a standard terminology used to select the best possible solution among candidate solutions. Selection plays an important role in genetic algorithms as it would be responsible for picking out the best possible solutions, which would be passed on to subsequent generations for further process. Thus, the selection phase in genetic algorithms is a very important phase in genetic algorithms.

crossing

The crossover phase of the genetic algorithm is basically responsible for setting a certain threshold at random places in the genes and the crossover will be responsible for exchanging genes between the two random solutions obtained in the selection phase . Thus, the information must be transmitted to the individual solutions until the crossover of the genes is achieved.

Mutation

The mutation phase in genetic algorithms ensures that crossover occurs with a higher random probability within genes. Thus, the mutation will be responsible for setting higher random threshold values ​​in the genes so that the information passed between the solutions is considerable and the mutation phase is also necessary to maintain the diversity between the best possible solutions selected for the problem.

What is image reconstruction?

Image reconstruction is an iterative process of evolving through the different image pixels and attempting to obtain the original image by evolution. Image reconstruction finds its main applications in medical imaging, reverse imaging and original image restoration tasks.

Similarly, genetic algorithms can be used for image reconstruction in which the algorithm tries to reconstruct the image close to the original image. Genetic algorithms essentially follow a metaheuristics-based approach and the algorithm iterates over the best possible ways to reconstruct the image close to the original image. Pygad is one such genetic algorithm library which is structured and designed to reconstruct images close to the original image.

Reconstruction of images using a genetic algorithm

Image reconstruction in genetic algorithms can be resumed using the Pygad library which is specially designed for image reconstruction using genetic algorithm principles.

So let’s see how to perform an image reconstruction with Pygad.

Let’s first install the library and import the library into the working environment.

!pip install pygad
import pygad

As the library is imported into the working environment, let’s visualize the original image using the matplotlib library.

import matplotlib.pyplot as plt
img=plt.imread('/content/drive/MyDrive/Colab notebooks/GA_Img_reconstruction/tiger.jpeg')
plt.imshow(img)
plt.show()

The image must be scaled down to standard scale values ​​to pass the original image to the genetic algorithm. So let’s resize the image using the numpy library.

img = np.asarray(img/255, dtype=np.float)

Once the image is scaled, we will need to use a library named GARI [Genetic Algorithm for Reproducing Image] which is a library designed to decompose the original image into chromosomes and also reshape the original image accordingly, it can be passed to genetic algorithms. So it can be said that GARI is one of the sub-modules of Pygad and it should be made available in the working environment by cloning in the respective Github repository.

!git clone 'https://github.com/ahmedfgad/GARI'
%cd /content/drive/MyDrive/Colab notebooks/GA_Img_reconstruction/GARI
import gari

Thus, once the gari library has been imported into the working environment, the library must be used to decompose the image into chromosomes which will be in the group of the initial population of the best possible image to be reconstructed close to the original image. So let’s see how to decompose the original image into a set of possible reconstruction images.

target_chromosome = gari.img2chromosome(img)

So here the “img2chromosome” function should be used to decompose the original image into the best possible reconstruction images. So, once the original image is reconstructed, we will need to create a fitness function to produce only the best fit solutions that can be passed to the Pygad instance to reconstruct the image. So let’s create a fitness function that considers the maximum difference between the original image and the reconstructed image so that the reconstructed image is close to the original image.

def fitness_fun(solution, solution_idx):
 fitness = np.sum(np.abs(target_chromosome-solution))
 fitness = np.sum(target_chromosome) - fitness
 return fitness

So here a user defined function is used to create a fitness function which will be responsible for producing a fitness score which is used to validate the fitness score among the candidate solutions in the population and the solutions that pass the fitness score will be taken into account for the mutation to reconstruct the image.

Now let’s create a Genetic Algorithm instance using Pygad with some parameters declared for efficient optimization and to reconstruct the image close to the original image.

ga_instance = pygad.GA(num_generations=15000,
                      num_parents_mating=4,
                      fitness_func=fitness_fun,
                      sol_per_pop=10,
                      num_genes=img.size,
                      init_range_low=0.0,
                      init_range_high=1.0,
                      mutation_percent_genes=0.01,
                      mutation_type="random",
                      mutation_by_replacement=True,
                      random_mutation_min_val=0.0,
                      random_mutation_max_val=1.0)

Here an instance of Genetic Algorithm is created using Pygad library where in some parameters like the number of generations the algorithm has to evolve using the candidate solutions present in the population, the number of parents is mating represents the set of solutions that will be responsible for information sharing (mutation) until the crossover point is reached and all solutions that will be mutated must pass the parameters applied in the fitness function and many others. So, with a genetic algorithm instance being created, the instance has to be iterated using the underlying principle of heuristic algorithms and in the process of iteration, the instance tries to find the best possible solution, this which implies that the image is reconstructed closer to the original image.

ga_instance.run()

The fitness score increases with an increase in the number of generations and the same can be visualized using the built-in “plot_result” function.

ga_instance.plot_result()
plt.show()

The fitness score increases with the increase in the number of generations because the candidate solutions will try to evolve with respect to different factors, declared in the fitness function and try to reproduce the best optimal solution that can be transmitted for mutation.

The best solution which is produced close to the optimal solution can be visualized using the Pygad instance. Here, the image being reconstructed can be viewed using the built-in “chromosome2img” function of the GARI library, as shown below.

solution, solution_fitness, solution_idx = ga_instance.best_solution()
print("Fitness value of the best solution = {solution_fitness}".format(solution_fitness=solution_fitness))
print("Index of the best solution : {solution_idx}".format(solution_idx=solution_idx))
 
if ga_instance.best_solution_generation != -1:
   print("Best fitness value reached after {best_solution_generation} generations.".format(best_solution_generation=ga_instance.best_solution_generation))
 
result = gari.chromosome2img(solution, img.shape)
plt.imshow(result)
plt.title("PyGAD & GARI for Reproducing Images")
plt.show()

Here we can see that after iterating through the 15,000 candidate solutions, the Pygad instance attempted to reconstruct the image close to the original image as shown above.

Comparison of the reconstructed image and the original image

Here we can clearly see how the genetic algorithm tries to reconstruct the image closer to the original image. The reconstructed image will be better with the increase in the number of generations and with the increase in the number of mutations. Indeed, the algorithm goes through all the candidate solutions of the cluster and the most suitable solutions which will be transmitted for the mutation will be more numerous. This allows the algorithm to reconstruct the image closer to the original image.

Summary

Genetic algorithms are mainly used for the optimization of various problems and in this article we have seen how images can be reconstructed using genetic algorithms. The more the number of generations and the more the number of mutations is optimal, this is the solution provided by the algorithm. The process of optimization of genetic algorithms is time consuming and that is why it finds its main use in evolutionary algorithms, where the optimal solution is the main requirement of evolutionary algorithms.

References

Source link

About Laura J. Bell

Check Also

Scientists use JWST image to measure galaxy distance

The first image the James Webb Space Telescope (JWST) showed us was the galaxy cluster …