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 noiseremoving 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. Colourbased 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 realtime 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^{[810]}. 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 crossover is performed on randomly selected couples of individuals by simply averaging their indexes: 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 crossover 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:
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: in which the indexes k_{1},k_{2} refer to the two parts identified by the cutting line, t_{1},t_{2} refer to the two bottles of the couple t.
The total fitness of a line k is:
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 bestfitting 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, 34 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.999.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 35 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 realtime 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 realtime 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 crossover 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 realtime 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 010102SF0011, which made this study possible. " target="_blank">View Fulltext
 Related
Articles  Back
