Asian Science Citation Index is committed to provide an authoritative, trusted and significant information by the coverage of the most important and influential journals to meet the needs of the global scientific community.  
ASCI Database
308-Lasani Town,
Sargodha Road,
Faisalabad, Pakistan
Fax: +92-41-8815544
Contact Via Web
Suggest a Journal
Journal of Computer Science
Year: 2009  |  Volume: 5  |  Issue: 10  |  Page No.: 711 - 716

A Genetic Algorithm for the Segmentation of Known Touching Objects

Edgar Scavino, Dzuraidah Abdul Wahab, Hassan Basri, Mohd Marzuki Mustafa and Aini Hussain    

Abstract: Problem statement: Segmentation is the first and fundamental step in the process of computer vision and object classification. However, complicate or similar colour pattern add complexity to the segmentation of touching objects. The objective of this study was to develop a robust technique for the automatic segmentation and classification of touching plastic bottles, whose features were previously stored in a database. Approach: Our technique was based on the possibility to separate the two objects by means of a segment of straight line, whose position was determined by a genetic approach. The initial population of the genetic algorithm was heuristically determined among a large set of cutting lines, while further generations were selected based on the likelihood of the two objects with the images stored in the database. Results: Extensive testing, which was performed on random couples out of a population of 50 bottles, showed that the correct segmentation could be achieved in success rates above 90% with only a limited number of both chromosomes and iterations, thus reducing the computing time. Conclusion: These findings proved the effectiveness of our method as far as touching plastic bottles are concerned. This technique, being absolutely general, can be extended to any situation in which the properties of single objects were previously stored in a database.

Figure 1(top) shows a typical image of bottles as they appear on a conveyor belt. No previous process is performed neither to sort the bottles by size, colour or shape, nor to orient them. The separation of the background is performed by thresholding on each colour of the RGB image and standard noise-removing filters are applied. The resulting binary image is shown in Fig. 1 (bottom). Standard techniques of image analysis provide separation and feature extraction of each distinct object; however the automatic classification is impossible in those cases where the object is not a single bottle, but rather a cluster.


Fig. 1:

(Top) Typical image of plastic bottles on a conveyor belt. (Bottom) Binarized image of the bottles

Various segmentation techniques have been attempted for the separation of two or more objects in contact, namely the Hough, Euclidean distance and the standard watershed transforms[7], but all proved to be excessively sensitive to noise pixels on the objects' edge and the complex shape of some bottles. The watershed transform showed its usefulness in cases of short contact lengths. However, in many cases it was not possible to identify two major minima in the distance transform and the watersheding resulted in no segmentation at all. Also the colour difference has not been chosen as a segmentation criterion as many bottles in the database are very similar in colour and some present contrasting internal patterns, as shown in Fig. 2. Moreover, experiments with different lighting conditions showed an alteration of the real colours in the images.

Unlike many applications in which the objects to be inspected have a standard position and shape, this case presents the additional difficulties of a random position and orientation, random time of arrival in the camera observation field and likely presence of other meaningless objects on the conveyor belt. Therefore, the aim of this study is to present a genetic algorithm technique which addresses the particular case of object identification in which the input image contains two plastic bottles in contact. The following assumptions are made.


Fig. 2: Example of touching bottles of similar colour but with contrasting label. Colour-based segmentations would separate the upper bottle from its label and join its bottom to the lower bottle, thus providing the segmentation of 3 meaningless objects

The cluster is made of two touching bottles: All the bottles appearing in an image are stored in a database, containing features such as dimensions, aspect ratios, momentums and edge profiles.

The separation and identification of two bottles in a cluster can be obtained by drawing a straight line, i.e., the shapes of the two touching objects are supposed to be mainly convex.

This technique has been developed with the intention of integrating it in a real-time application for plastic bottle recognition and sorting. Consequently, particular attention has been given to the computation time of the algorithm.

MATERIALS AND METHODS

The goal of the genetic algorithm technique presented in this study is to find a satisfying straight line which correctly separates a binarized cluster of two touching bottles into two subsets, each corresponding to one of the bottles. Genetic algorithms are based on the Darwinian theory of transformation of a population of individual objects into new generations in which only the fittest ones are kept[8-10]. New individuals are usually generated by crossing over the features of parent individuals and by random mutations, then selected to keep a constant population. While this selection retains only the individuals that best approximate the solution of the problem, the mutations allow random exploration of other possible approximations.

In this study, a genetic algorithm is used in image segmentation as an efficient optimisation tool since it appears to be a natural candidate to solve the cluster separation problem. This is due to its generality and capability to heuristically overcome situations where an exhaustive solution would be too demanding in terms of computation.

Population: The population P of individuals consists of straight lines, initially generated by choosing at random a number of couples of pixels belonging to the perimeter of the image to split. In order to speed up the process, it was considered to start with a large initial population and to select only a fairly small number of individuals for the subsequent generations while all other individual are immediately discarded. A large initial population increases the probability to have a fairly fit subset already at the beginning of the genetic process. Typical values, for a perimeter of 1000 pixels, are an initial population of 100 lines and subsequent populations of just 10 lines.

The genetic coding of the population P is simply the couple of indexes which identify the pixels of the perimeter of the object. The pixels are sorted and indexed in anticlockwise order around the centroid of the perimeter so nearby pixels have near indexes.

Each individual of the population has a gene of the type where , M being the number of the perimeter pixels and for all individuals. Figure 3 shows a random initial population, out of which few individuals are chosen to produce further generations.

Crossover and mutation: The cross-over is performed on randomly selected couples of individuals by simply averaging their indexes:

(1)

As a consequence of the pixel sorting procedure, this operation generates a new offspring whose vertices are approximately halfway between the vertices of the parents. While this cross-over operation allows the diversification of the possible image cuts, it does not guarantee that the new individuals inherit or improve the fitness value of their parents. For this reason the two best individuals of a population are transmitted to the new generation without changes, in a process known as elitism.


Fig. 3: Initial population of 50 lines, connecting random couples of perimeter pixels. The 10 fittest individuals, drawn in black in the picture, are kept as parents to produce new generations

The mutation is coded as random changes in the values of the pixels’ indexes, up to a maximum predefined extent equal to 2% of the total number of pixels:

(2)

This mutation, which is applied to all new individuals, is more meant to explore the vicinity of existing groups of similar individuals rather than explore different and faraway segmentations.

Fitness: In this problem, the fitness of a line has to be somehow related to its effectiveness in cutting the original binarized image into two fragments, both very similar to two of the bottle images stored in the database. The evaluation of the similarity involves the process of feature extraction and classification which is common in image classification technology; however the choice of a large number of features as well as of those which are particularly demanding in terms of computing may result in a too slow procedure for fast applications. In this algorithm, the calculation of the fitness is based on the comparison of the width and length of the two parts, defined by the cutting line, with the width and length of the bottles stored in the database.


Fig. 4:

The dashed line splits the object in two fragments, which are measured along their principal axes

Each line k divides the binarized image in two fragments, as shown in Fig. 4. The length Δl and width Δh of both fragments are measured along their principal axes. The dividing line is added to both parts to avoid the displacement of the centroid with respect to the centroid position of the complete perimeter. Then, for each possible couple of bottles t, a fitness value is calculated as the sum of exponentials of the absolute errors:

(3)

in which the indexes k1,k2 refer to the two parts identified by the cutting line, t1,t2 refer to the two bottles of the couple t.

The total fitness of a line k is:

fk = max(fkt)

(4)

Tests have been performed with other features in addition, or in substitution, to the length and width of the two fragments. The use of the area of each part appeared to be too slow for fast applications, while using the length or the square momentum of the perimeter resulted in totally wrong cuts associated with high fitness values.

RESULTS

The segmentation technique based on this genetic algorithm was tested on images of touching bottles.


Fig. 5: Final result of the segmentation in two examples of touching bottles, as performed by the genetic algorithm the initial population of 50 lines was reduced to 10 after the first screening. The solid lines represent the population after the first selection, the dotted lines are the final population and the thick black line is the best-fitting element

We performed a visual inspection of the final segmentations to establish its quality and to rule out possible false positives, in which a high fitness level would correspond to wrong cuts. Figure 5 shows two examples of successful segmentations, obtained with an initial population of 50 lines which were reduced to 10 prior to implementation of the actual genetic algorithm. Twenty iterations were performed in both examples and fitness values of f =3.69 and f = 3.66 were obtained. It was also observed that a line may have a high fitness level and provide a correct segmentation even without having its vertices lying exactly on the corner points common to both bottles.

The efficiency and the speed of this genetic algorithm were tested on a set of about 150 images depicting couples of bottles in contact. Fifty distinct couples were formed by choosing randomly out of a set of 50 bottles, whose features were stored in the database. For each couple, 3-4 separate images were taken in different contact patterns.

A selection of the candidate couples was performed by calculating the total area of the binarized image of touching bottles. Extensive testing showed that in all cases this area lay in the range 98.9-99.5% of the sum of the areas of the two bottles alone, as per values recorded in the database. This criterion, together with a check of all possible couples, showed a single worst case scenario in which 8 couples had to be taken into consideration. As shown in Fig. 6, in most cases 3-5 couples would be required as candidates.


Fig. 6:

The possible number of candidate couples of bottles as a function of the area of the binary cluster



Fig. 7:

The success rate of the genetic algorithm as a function of the number of generations

During the test the touching bottles were put on the conveyor belt, both in motion and at rest. The images were taken with a standard webcam; its exposure time and the surrounding lighting were adapted to reduce blurring due to the motion of the conveyor belt.

The rate of successful segmentation is shown in Fig. 7. Each configuration was tested 100 times, with 20, 50 and 200 generations in the genetic algorithm. Each result was visually inspected for false positives or correct recognitions associated to bad segmentations.

DISCUSSION

The segmentation technique based on this genetic algorithm showed that high fitness values (f>3.6) correspond to good segmentations and correct identification (i.e., no false positives were recorded), while low ones (f<3.2) were associated with meaningless segmentations and random identification. Intermediate values of the fitness would lead to a correct identification but approximate segmentation. With just 50 iterations the average success rate climbs over 85% while more iteration provides only a marginal improvement. For the case when the parts in contact are long, success rates of more than 97% are obtained within just 20 generations.

Emphasis on the computing time performance of the algorithm was also considered to ensure possible real-time applications. The computing time was found to be roughly proportional to the number of candidate couples, as the initial line selection was much faster than the genetic algorithm itself. When using 50 iterations and 10 lines for the genetic algorithm, the average time was found to be around 80 ms per candidate couple, in Matlab environment. In real-time applications involving the recognition of bottles on a conveyor belt, this procedure may be considered to be sufficiently fast and unlikely to be the bottleneck of the system. If a faster version is needed, a compiled version of the algorithm may reduce the computing time.

CONCLUSION

In this study, we have successfully implemented a genetic algorithm based segmentation technique to separate touching bottles images of a waste sorting system that facilitates the identification of plastic bottle type. Typical issues in genetic algorithms, such as selection of initial line population, parameters for fitness calculation as well as the cross-over and mutation optimisation were addressed. Results show that our genetic algorithm implementation could provide a success rate above 85% with reasonable computing time for possible real-time applications. Using just 50 initial chromosomes, 10 selected chromosomes and 50 generations achieve the goal of 80 ms per candidate couple of bottles.

ACKNOWLEDGEMENT

The researchers acknowledge the Minister of Science, Technology and Innovation for the Research Fund MOSTI Grant 01-01-02-SF0011, which made this study possible.

" target="_blank">View Fulltext    |   Related Articles   |   Back
   
 
 
 
  Related Articles

 
 
 
 
 
Copyright   |   Desclaimer   |    Privacy Policy   |   Browsers   |   Accessibility