Image Segmentation Of Irregular Shaped Binary Images Biology Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

The segmentation technique basically divides the spatial domain, on which the image is defined in 'meaningful' parts or regions. The current approach segment the regular shaped images using Genetic Algorithm (GA). The drawback of the current techniques is the prior knowledge of the object shape is required. In the proposed method, has been overcome above drawback by considering irregular shaped images for image segmentation using GA. In this paper used an optimization technique based on the GA. The GA generated the initial population set randomly, each individual is a possible solution for image segmentation. In reproduction step of GA, that used morphological operations at random. Over the several generations, populations are evolved to get the near optimal results. The proposed algorithms present the experimental results of image segmentation using GA for corrupted noisy irregular shape images.

General Terms

Image Processing, Pattern Recognition.


Image Segmentation, Genetic Algorithm and Morphological Operators.


A Genetic algorithm is a search heuristic procedure of natural evolution. The heuristic procedure is used to generate solutions to optimization problems. GA technique belongs to evolutionary algorithms (EA). GA is inspired by natural evolution, such as selection, crossover and mutation. Genetic algorithm was developed by John Holland and his associates and is briefly characterized by three main concepts. First, a fitness function which determines a fitness of each individual chromosome. Second, selection operation which selects individuals for recombination according to their fitness. Third, recombination operation which creates new offspring's based on the genetic structure of their parents. We have reviewed different techniques, which are used for objective optimization. The genetic algorithm is able to overcome many of the defects in other optimization techniques such as exhaustive techniques, calculus based techniques, and knowledge based techniques (heuristic methods, production rule system) [1]. They search from a population of individuals (search points). They do not required domain specified knowledge. GA has been used to solve various problems in computer vision, including image processing, image matching, and object recognition and feature selection. The genetic algorithm has many important properties that play

decisive role in its performance. Genetic algorithms work for a population of solutions not for a single point. Thus we can achieve a globally optimum solution by using diversity in GA. GA use probabilistic rules not deterministic rules. Thus GA is necessary to use as an efficient technique to solve the problem of complex primitive detection. These include the size of population, crossover and mutation probabilities.

Image segmentation is one of the steps in image analysis. GA based image segmentation have been used in various image analysis applications [ 2 - 8].

Phulpagar and Kulkarni [9] have proposed a genetic algorithm technique for reconstruction of 2-D images containing regular shaped objects with prior knowledge of structuring element (SE). In this paper, the GA-based approach has been extended for reconstruction of 2-D images containing irregular shaped objects without prior knowledge of SE. The results obtained using GA-based approach at times better than those obtained using the approach of existing techniques.


Image segmentation is a process by which a given 2-D image is partitioned into two different regions, where each region is homogeneous and connected, and the union of two spatially adjacent regions is homogeneous. Each region in a segmented image needs to satisfy the properties of homogeneity and connectivity [10 - 11]. A region is considered homogeneous if all of its pixels satisfy a homogeneity criterion defined over one or more pixel attributes such as color, intensity and texture etc. A region is considered as connected [12], if there exists a connected path between any two pixels within the region. In this paper, the images are considered on two constant gray levels and corrupted by the different types of noises i. e. Salt and Pepper, Gaussian and Poisson noises, which may occur in noisy image transmission with impulsive noise. The reconstruction of 2-D image is formed by using two constant gray levels and gray levels are varied from image to image.

SNR of 2-D image i.e. M X N is defined as the ratio of average signal power to average noise power. SNR is mean-squared error measures and unit is decibel dB.

SNR (dB) = 10log10 (1)

Where, A(i, j) denotes pixel (i , j) of the original image and B(i, j) denotes pixel (i, j) of the noisy image.

Image Segmentation Using GA

Assume the size of the irregular shaped binary image is (64 X 64) pixels, therefore the search space is 264X64. The image is divided into sub-images before performing image segmentation to increase the speed of the search process. The size of each sub-image is considered as a (16 X 16) pixels, so that the segmentation using GA algorithm is performed on (16 X 16) sub-images which are later combined to obtain the entire irregular shaped segmented 2-D image. The length of the chromosomes is fixed i. e. L, where L is the number of pixels in one chromosome. The GA consists a set of chromosomes and different genetic operators. A chromosome represents a segmented 2-D image. The structure of the chromosome is a two dimensional i. e. (16 X 16) sub-image is converted using raster scan technique into a vector. Vector consists of total pixels i. e. , Chromosome size (16 X 16 = 256), each gene of chromosome representing among of two constant gray levels i. e. background (0), irregular shaped object (1).

Initial Population Set

The size of initial population is the size of each sub image. The initial population of chromosomes is randomly generated. The set of individuals of the first generation represents the initial population in the search space as

{ipi,j , . . . , ipM, N} Where, i = 1, 2, . . . , M, j = 1, 2, . . . , N.

ip = Initial population, M = Population size, N = Chromosome size.

The set is randomly chosen to form two gray classes i. e. background and object of M population size. The solution depends upon the size of populations, therefore the population size is an important factor in the algorithm.

Fitness Function to Population Set

The objective function returns the value associated with each individual indicating how fit the objects is in a given segmented image. In the paper, the original sub-image is represented as

Pj = [P1 , P2 , . . . , P256 ] and

the fitness function definition is as fitness(ipi) = 1 / (1+(X(ipi)/256)) (2)

Where X(ipi) = and X(ipi) is used to measure the difference between individual and original noisy image. Above fitness function is used to find out the fitness of each individual chromosome. The role of that function is to reduce high frequency noise in segmented results. The next step is a selection function to produce children from selected parents.

Selection Function

After the evaluation of the fitness of individuals, the fitter individuals must be selected to be parents for producing offsprings, which as a set of populations in the next successive generations. In this method, we have used roulette wheel selection [13], which is conducted by spinning a biased roulette wheel sized in proportional to the fitness of each chromosome. The main idea is to select best fitness value from the set of fitness values i. e. improved segmented sub-image. The next step is reproduction to improve the segmented sub-image for successive generations.

Reproduction Operator

In GA reproduction is another step that generates the population of qualified individuals in the successive generations. In this paper it consists of three functions i.e. Morphological, Cross-over and Mutation.

Theoretical background of Morphological Operators

Morphology is a technique of image processing based on shapes. The value of each pixel in the output image is based on a comparison of the corresponding pixel in the input image with its neighbors. It has been used to process binary and grayscale images. To represent connectivity properties of an image, we used morphological operation to selected individuals. Let P be an image and Q be a structuring element in Z2. The template size of the structuring element Q is a 3 X 3 or 5 X 5 with an appropriate intensity structure. The size and shape of Q depend on the solution of the segmented 2-D image. Basic binary morphological operators [10] are defined as, let A and B are two different binary images of the same sizes.

Translation of B by x:

The translation of a set B by point x =(x1, x2). If B is a set of pixels representing an object in an image.

Reflection of B:

Dilation and erosion are based on two set operations namely translation and reflection.

Dilation: It adds pixels to the boundaries of objects in an image. Dilation of an input image A by a structuring element B is defined as follows:

Dilation of A by B:

Erosion: It removes pixels on object boundaries in an image. The erosion of an input image A by a structuring element B is defined as follows:

Erosion of A by B:

Closing: It consists of dilation followed by erosion with the same structuring element. The closing of an input image A by a structuring element B is defined as follows:

Closing of A by B:

Closing a triangle A by a disk B (the origin is at the center of the disk) yields the same triangle.

Opening: Morphological opening of an image is erosion followed by dilation using the same structuring element for both operations. Opening of an input image A by a structuring element B is defined as follows:

Opening of A by B:

The opening of a triangle A by a disk B (the origin coincides with the center of the disk) is the triangle A with rounded corners.

In this paper, it selected a random morphological operator among the following set of morphological operators used in reproduction step. Thus it is useful for noise reduction and feature detection in the reproduction process.

Set of morphological operators = {Dilation, Erosion, Opening, Closing, Opening followed by Closing, Closing followed by opening}.

It also selected a structuring element as a random in the give set of SE's for the above set of morphological operators.

In the presented method randomly selected morphological operator is not fixed for entire image.

Crossover Operator

The crossover routine [13] creates two new offspring strings, from two parent strings by swapping parts of parent chromosomes. Generally, the two new offsprings are created from two parents. The crossover routines are one-point, two-point, n-point and uniform crossovers. The one point crossover is explained as below.

One-point crossover:

Two-point crossover:

The above two points crossover operator randomly selects two crossover points within a chromosome then interchanges the two parent chromosomes between these points to produce two new child's.

In this paper initially parents are selected to produce children's, by using the roulette wheel method. If crossover probability i.e. 0.60 is greater than the randomly generated probability using the following procedure otherwise consider parents as a children's. The procedure is, finds the local fitness and average local fitness of each parent. The local fitness is defined as


The average local fitness of each parent is as


Where, j=1, 2, ... , N.

If local fitness is greater than the average local fitness then the first parent will be transferred to an offspring, similarly for the second parent.

Mutation Operator

This operator improves the fitness of an individual. Mutation is used to process one individual gene in the chromosome. It does not produce a new offspring. In this paper, that used the concept of the median filter. It replaces the center value in the window with the median of all the pixel values in the window.

In order values: 0, 2, 3, 4, 6, 12, 14 and 87.

The window size is variable i. e. 3X3, 5X5, 7X7 and 9X9. Selection of the window size is random.

Termination Criterion

The termination criterion is, when the program does not change the fitness value to the subsequent generation's i.e. N number of generations.

Experimental Results

The proposed method tested to extract object in one hand and background on the other hand in the irregular shaped images. In this experiment, the presented method works on synthetic images with two classes having pixel values 50 and 150. The salt and pepper noise is added to the original image to obtain noisy images. We have assumed the density range of salt and pepper noise is in between (0.03, 0.05 and 0.20). The image of size (64 X 64) is divided into sub-images of size (16 X 16), thus each individual in GA is encoded as a matrix size (16 X 16), crossover probability in between (0.56 to 0.60), selected a structuring element as a random in the given set of SE's, population size is 360 and the reconstructed images shown are obtained after 72 generations.

Figure 7(c, d) shows the experimental results using proposed GA after 10 and 72 generations, with density of salt and pepper noise is 0.03, populations = 360 and 76 dB SNR. It may be observed that the quality of reconstructed image Figure 7(c) is poor (classification of pixel accuracy is 92%) and Figure 7(d) (classification of pixel accuracy is 97%) shows the nearer to original image Figure 7(a).

Figure 8 shows graphs of GA convergence for this experiment Figure 7 (b) at 76 dB SNR, where Error in the solution is plotted against the number of Generations. The sum of errors on each generation for each segmented sub-image is an error. We observe a very fast initial convergence followed by a very slow convergence. It may be noted that from 1-15 iterations is very fast and from 16-72 iterations the reduction in the error is very small.

The proposed GA is also tested with higher density salt and pepper noise to illustrate the GA performance and to obtained reconstruction quality nearer to Figure 7(a). Figure 9 (a), (c) shows images with higher density noises 0.05 and 0.20 and Figure 9 (b), (d) shown the reconstructed images are obtained after 120 and 100 iterations.

The proposed GA is tested for the Gaussian and Poisson noises. The Figure 10(a) is corrupted image is obtained by adding density 0.20 of Gaussian noise to Figure 7(a). The GA parameters are populations = 360, generations = 150, mutation probability = 0.06, crossover probability = 0.6 and 2.5436 dB SNR. The Figure 10(b) through Figure 10(d) shows the improvement of GA result to the reconstruction of Figure 10(a).

Figure 10(d) shows the structure obtained after 150 generations and it is nearer to initial structure Figure 7(a). The misclassification pixels between Figure 7(a) and Figure 10(d) are 276 i.e. (classification of pixel accuracy is 93%).

The following Figure 11 shows the experimental results with the proposed GA methodology using Poisson noise, (a) at 8.5946 dB SNR. Figure 11(b) through Figure 11(d) shows the improvement of classifications between object and background using proposed GA method in Figure 11(a). Figure 11(d) shows the segmented image after 150 generations and its misclassification pixels are 149. The classification of object and background pixel accuracy is 96%.

Thus, the experimental results show that the proposed method leads to some enhancement in the process of different types of noise reduction in the irregular shaped segmented images. The proposed GA methodology shows the classification of object and background pixel accuracy is in the range between 91% to 97%.


That segment the irregular shaped images successfully by using proposed GA method for different types of noises, which are Salt and Pepper, Gaussian and Poisson. Required more generations and large populations, when the noise level increases. In the reproduction step of the presented method that select the morphological operator and SE as a random among the set of morphological operators and set of structuring elements. A prior knowledge of the object's shape is not required. The selected morphological operator and SE are not same for each sub-image. In this method mutation operator is implemented by using the concept of the median filter.