Assistant Professor

Department of CSE

UoK, North Campus,

 Delina, Bla 

Introduction

Digital image processing refers to the processing of digital images by means of the computer system. A digital image is made up of a finite number of elements, each of which has a specific value and position. These elements are referred as pixels (picture elements) [1]. Image segmentation is a field of image processing. To locate effectively tumors in human body, infected tissue volumes, fingerprint recognition, image retrieval etc. we use image segmentation. Segmentation partitions an image into its individual objects or areas. The problem being solved determines how much segmentation is used. In other words, once the objects of interest in an application have been identified, segmentation should come to an end. For instance, image analysis of the product is of interest in the automated inspection of electronic assemblies in order to identify the existence or non-existence of particular anomalies, like broken connection routes or missing components. While there are several segmentation algorithms available, the improved genetic algorithm (IGA) [4] offers the best threshold value for image segmentation. Choosing a suitable gray level threshold is essential for image segmentation in order to differentiate objects from their background. Pixels are split into two groups based on whether their gray levels are higher or lower than the threshold. As a result, the background and target are divided.  In [9], authors suggested an OTSU segmentation scheme using fruit fly optimization, which models the fruit fly’s olfactory search for food to obtain the optimal threshold and enhance both segmentation performance as well as computational speed. In [10] blood cell images are segmented using on genetic algorithm.  In [12], authors use genetic algorithm for the automatic grouping of tumor stage to enhance the classification accuracy. The study in [8] uses the improved genetic algorithm and suggests a two-dimensional OTSU inland ships multi-threshold image segmentation method. The selection of crossover rate and mutation rate play a vital role when using a genetic algorithm to determine the ideal threshold [11]. The adaptive basic genetic algorithm suggested in [13] uses the fitness to automatically adjust the crossover and mutation rates.

The problem considered is to extract objects from their background. One often used technique for segmenting grey level images is thresholding. The method is predicated on the idea that the gray level threshold of an image can be used to identify between background and object pixels. The original grayscale image's threshold value is utilized to divide an image into two classes, such as one object and one background. The approach may seem straightforward, yet it is a fundamental and significant one with broad applications. Determining a threshold at the grey value in the valley between the two peaks of the histogram is the goal for a two-class problem. It is not an easy process to determine these two peaks.  The histogram data is smoothed, modes are found, and thresholds are set at the minima between them as part of the automatic threshold scheme selection process. It was thought that the object and background regions, shown by the peaks of the histogram, had relatively constant gray levels and varied in average gray levels. The two peaks are also not located by the heuristic search method. Additionally, if the valley is flat, it is challenging to determine the precise threshold point. It is challenging to find the valley's bottom, though. A number of techniques have been put out to modify the histogram in order to deepen the valley or turn it into a peak. As a result, an effective threshold selection can be made. An improved genetic algorithm determines the ideal threshold value. This technique is effective even in flat valleys. Any valley sharpening technique that relies on the histogram's valley is not necessary. The experimental results of an image with a histogram having two peaks are limited to two class objects. These images’ histograms show two separate peaks. The approach yields favorable results if the provided image's histogram clearly shows two modes of any size, indicating that the image is a two class image (histogram with two peaks).

Image Segmentation

The image segmentation is one of the fundamental techniques of the image processing and is also an important component of the image analysis and visual system. In image segmentation process, the digital image is processed by the computer as shown in fig-1. First a threshold value of a gray digital image is determined. Based on the threshold of the gray values of the image the gray value matrix of image is changed into 0 and 1(binary matrix). This binary matrix is converted into the segmented image. To determine the threshold is important in image segmentation. The improved genetic algorithm is used to find the optimal threshold value for image segmentation. In genetic algorithm to determine crossover and mutation probability is critical. The improved genetic algorithm [4] automatically adjusts the mutation and crossover probability on the basis of the fitness of individuals.

Figure 1: Framework Model of Image Segmentation Process

Thresholding

Region-based segmentation locates areas within the image that have a common attribute (such as color or intensity). Statistical techniques, split and merge, clustering, region growth, thresholding, and clustering are examples of region-based procedures. The simplest method of image segmentation is thresholding, which assumes that the digital image's background and objects have different gray level distributions. Assuming this is true, there are two distinct peaks in the gray level histogram, and determining the threshold will be simple. In order to accomplish segmentation, regions with gray levels below the threshold are assigned to the background, and regions with gray values above the threshold are assigned to the object, or vice versa [3]. There are two types of threshold selection techniques: global techniques and local techniques.  A local thresholding approach divides the given image into several sub-images and sets a threshold for each sub-image, while a global thresholding technique uses the gray level histogram of the image to segment the entire image with a single threshold [5]. Implementing global thresholding techniques is simple. Applications for image processing that use global thresholding include text enhancement, biomedical image analysis, and automatic target recognition [6].    

System Overview

Segmentation slices an image into its individual objects or areas. The problem being solved determines how much segmentation is used. A variety of techniques can be used to segment an image. Improved genetic algorithm is used to determine the threshold value, based on the threshold value the image is segmented. The gray value matrix of digital image is converted into white and black (bi-level) image depending upon the threshold value say “T”. Thresholding involves looking at each pixel and deciding whether it is converted to “0” or “1”. Then we get a binary matrix and this binary matrix is converted into the segmented image. The segmentation of image is good if the threshold chosen is global optimal, the use of improved genetic algorithm try to find the global optimal solution. This system works efficiently where there is a well defined valley in the histogram of image. The overall data flow diagram of image segmentation process using IGA is shown in fig-2.

Figure 2: Data flow diagram of image segmentation process using IGA

Working of improved genetic algorithm

Based on the principles of genetics and natural selection, the genetic algorithm is an effective random probability searching technique. The population will be chosen using selection operator, crossover, and mutation in accordance with the method to produce fresh optimal populations until the ideal answer is found. The way a genetic algorithm searches differs from a traditional search strategy in that it begins with a set of randomly selected initial populations and proceeds to select, reproduce, crossover, and mutate based on each individual's fitness function. This process is crucial in determining each individual's chances of reproducing and truly reflects the survival of the fittest. Both crossover and mutation work to improve chromosomes by transferring individual information [2]. The most suitable chromosome will be produced as the number of generations rises, providing the solution to a problem. There is a distinction between an improved genetic algorithm and a genetic algorithm: in the former, crossover and mutation probability are set at program start, while in the latter, these values are automatically determined [4, 7]. These probabilities are automatically adjusted by an improved genetic algorithm according to the chromosomes' fitness.

Steps in improved genetic algorithm

i. Encoding

While implementing the improved genetic algorithm, the first decision is made on how to encode the solutions into chromosomes. Binary encoding is used in this work. Binary encoding is the most common form of encoding. In binary encoding every solution/chromosome is represented as a bit string of 0 and 1.

Eight bit binary coding is done in used in this work

             Chromosome-1    01010110

             Chromosome-2    01110011

ii. Initial group

The initial group of the individuals is random. The initial group of individuals and maximal number of generations depend upon the problem to be solved.

iii. Fitness Function

Fitness determines the quality of individual and is defined by the following Eq.(1) [4].

Where, p_{j =} the probability of the pixels with gray value j. ρ is variance between two classes. N is total no of pixels and n_j = the number of pixels with gray value j.

iv. Selection

The best selection procedure for deciding the parents that form the basis for new offsprings/chromosomes is often problem dependent. All selection procedures should however depict the basic idea that a higher fitness means a higher likelihood of being chosen. There are several selection strategies like roulette wheel selection, tournament selection, rank selection, and random selection etc.

v. Crossover

In order to produce new chromosomes, crossover is done between the parents once they have been chosen in accordance with the selection approach employed. Combining features from the chosen chromosomes to create a new chromosome is the goal of the crossover process. Crossover is basic operation in genetic algorithms and is generally employed with a probability greater than 0.5. While most strings are built from parents via crossover, some are created by directly inheriting every gene from a single parent. However, in the improved genetic algorithm [4, 7], the crossover probability p_c is automatically modified using following formula.

Where, where f_mi  is minimal fitness, f_mx is the maximal fitness and f_ag is average fitness value in the population. When f_ag / f_mx > a as well as f_mi / f_mx > b, the generation is supposed to be convergent, and p_c is adapted by its convergent degree, otherwise maintains the default setting. The  same conditions applies also applies to mutation probability (p_m).

vi. Mutation

Slight modifications are introduced through mutation operator to facilitate the examination of solution states not produced by crossover process. Individuals with different characteristics are born as a result of mutation. In improved genetic algorithm [4, 7], mutation probability p_m is automatically adjusted and is defined by the following equation:

vii. Re-insertion

The ratio of the new group's size to the old group's size is called gap. The existing group should be supplemented with a few new members to maintain the desired ratio. The method can be imposed by replacing the individuals whose fitness are less.

viii. Stopping Criteria

In improved genetic algorithm, we usually fix the number of generations as stopping criteria.

Pseudo-code of Genetic Algorithm

Procedure Genetic Algorithm

Start Procedure

i. Initialize population  

ii. Calculate fitness

for count :=1 to Generation_numb do begin

iii. Select population using some predefined selection procedure

iv. Apply cross-over operation                   

v. Apply mutation operation

vi. Apply Re-insertion operation

vii. Calculate fitness

end        

Select the best individual to serve as the solution after convergence.

 end

Results:

An infectious human tissue (RGB image, fig-3) is converted in grey scale image as shown in fig-4. When convergence/termination condition is met a threshold value is determined by the algorithm. The grey scale image is converted into binary matrix based on the threshold value. At the end the binary matrix is converted into the binary segmented image as depicted in fig-5.

Figure 3: Original Infectious Image

Figure 4: Grey scale image

Figure 5 : Segmented image

Summary:

The technique of segmenting an image into its individual objects or regions is known as image segmentation. The type of problem being solved determines how much segmentation is done. When the application's items of interest have been isolated, segmentation should come to an end. Choosing a suitable gray level threshold is essential for image segmentation in order to distinguish objects from their background. One often used technique for segmenting grey level images is thresholding. The improved genetic algorithm is employed to determine the threshold for segmenting images. The improved genetic algorithm automatically modifies its crossover and mutation probabilities based on the chromosomal fitness. Because of image uncertainty, there isn't a universal image segmentation method that produces the best results for a variety of images. There are two types of image segmentation techniques: image edge detection technology and image regions detection technology [2]. The threshold method belongs to image regions detection technology. The improved genetic algorithm determines the threshold for segmenting images. This approach divides the pixels into two groups based on how closely the gray level and threshold match. Pixels that fall below or over the threshold in terms of gray values are split into the corresponding class. As a result, the background and target are divided.

Bibliography:

1. Gonzalez, Rafael C. Digital image processing. Pearson education India, 2009.

2. Wang, Chun-mei, Su-zhen Wang, Chong-ming Zhang, and Jun-zhong Zou. "Maximum variance image segmentation based on improved genetic algorithm." In Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing (SNPD 2007), vol. 2, pp. 491-494. IEEE, 2007.

3. Sahoo, Prasanna K., and Gurdial Arora. "A thresholding method based on two-dimensional Renyi's entropy." Pattern Recognition 37, no. 6 (2004): 1149-1161.

4. Hui, Lei, Cheng Shi, Ao Min-si, and Wu Yi-qi. "Application of an improved genetic algorithm in image segmentation." In 2008 International Conference on Computer Science and Software Engineering, vol. 3, pp. 898-901. IEEE, 2008.

5. Jiang, Xiaonan, Xianlin Huang, Ming Jie, and Hang Yin. "Rock detection based on 2D maximum entropy thresholding segmentation and ellipse fitting." In 2007 IEEE International Conference on Robotics and Biomimetics (ROBIO), pp. 1143-1147. IEEE, 2007.

6. Chen, Z., Tao, Y., Chen, X. and Griffis, C., 2001. Wavelet-based adaptive thresholding method for image segmentation. Optical Engineering, 40(5), pp.868-874.

7. Lei, Wang, and Shen Tingzhi. "An Improved Adaptive Genetic Algorithm and its application to image segmentation." In Proceeding of 5th International Conference on Artificial Neural Network and Genetic Algorithms, pp. 112-119. 2004.

8. Peng, Zhongbo, Lumeng Wang, Liang Tong, Han Zou, Dan Liu, and Chunyu Zhang. "Multi-threshold image segmentation of 2D OTSU inland ships based on improved genetic algorithm." Plos one 18, no. 8 (2023): e0290750.

9. Huang, Chunyan, Xiaorui Li, and Yunliang Wen. "AN OTSU image segmentation based on fruitfly optimization algorithm." Alexandria Engineering Journal 60, no. 1 (2021): 183-188.

10. Ayoub, A. Y., Mohammed A. El-Shorbagy, I. M. El-Desoky, and A. A. Mousa. "Cell blood image segmentation based on genetic algorithm." In Proceedings of the International Conference on Artificial Intelligence and Computer Vision (AICV2020), pp. 564-573. Springer International Publishing, 2020.

11. Sun, Bo, Ping Jiang, G. R. Zhou, and D. Y. Dong. "AGV optimal path planning based on improved genetic algorithm. Comput." Eng. Des 41, no. 2 (2020): 550-556.

12. Bahadure, Nilesh Bhaskarrao, Arun Kumar Ray, and Har Pal Thethi. "Comparative approach of MRI-based brain tumor segmentation and classification using genetic algorithm." Journal of digital imaging 31 (2018): 477-489.

13. Javadi, Giti, and Ehsan Aminian. "A new method for tuning mutation and crossover rate in genetic algorithm." In Proceedings of the 9th International Conference on Machine Learning and Computing, pp. 217-220. 2017.