Using both a probabilistic evolutionary graph and the evidence theory for color scene analysis

American Journal of Applied Sciences, Dec, 2008 by Nassim Ammour, Abderrezak Guessoum, Daoud Berkani

INTRODUCTION

The image color information is often primordial in the analysis and the decision-making during the robot evolution in its environment. Many tasks ask robots to move safely in scenarios with unknown obstacles. In this case, the motion strategies must rely on sensory information to compute the trajectories of the movements according to unforeseen circumstances. These strategies use the sensor-based motion planning methods. The challenge for these approaches is to deal with very cluttered, dense, and complex scenarios, which are usually the case in most robotic applications.

Image segmentation is a pre-treatment, which improves the state of the information contained in the scene, before the desired treatment and application. The objective is to separate, in the most faithfully possible way, the objects and the background which make the image (1), (2).

Image segmentation has applications in many practical fields, such as in forms recognition, objects detection, analysis of medical images, robotics (3), in the field of the satellite images and in still many others.

Several developed segmentation techniques are based on a preset number of classes in the initial stage of the algorithm, which ensures the classification of each image pixel in its most probable class. These are segmentation by region based approaches, segmentation by contours detection, segmentation by thresholds, and that based on the k-means method. There is also the classification by the theory of the obviousness, also called the Dempster-Shafer theory or the belief function theory. It makes it possible to process, on the one hand dubious data and on the other hand to combine information coming from several sources, before the use of the decision rules for the assignment class selection (4), (5), (6). We note also the classification by hidden Markov chains (7), (8) and the Bayesian classification, which is based on the determination of the conditional probabilities to estimate the individual membership to each class (9) and some other methods based on fuzzy classification (10).

In this research, we present a method for scene analysis which constitutes the first step in trajectory planning for robot environment identification. We present a new image segmentation method based on a probabilistic graph evolution, which traces the image occupant's regroupings.

MATERIALS AND METHODS

This research work rises from a project developed to realize an autonomous mobile robot. The objective of this work is to establish a fast color image analysis algorithm which translates a robot environment scene that can represent a real time intervention space. We implemented our algorithm on a computer PC. The images treated to test the effectiveness of the algorithm are of three different categories. The first image is a pure synthetic image used to check the detected classes' centers which are beforehand known during the creation of the image. The second image is a synthetic image strongly deteriorated by a Gaussian noise, used to introduce no null variances into the classes. The third treated image is a real image which is captured by a video sensor; it is selected to be put under the real conditions for the desired application.

The principle of this analysis is divided into two principal stages. The first phase consists in determining the number of classes contained in the image and to locate spatially the raw areas. The method rests on the course of the scene image and on the set up of a probabilistic graph which evolves along the course according to collected information. At the end of the course, the resulting graph represents the components descriptor of the scene to be analyzed. Each node of the graph represents a class. Edges describe the vicinity between two classes. The second phase consists in using the method of the belief functions to classify the pixels of the areas with strong variance and which constitute the noise zones and the transitions. These zones can deteriorate significantly the result of the processing.

THE GRAPH SET UP

The method consists in detecting the pure areas of the image, which represent a small disturbance and to generate a graph, which evolves according to the presence and the dissimilarity of these areas. The zones of strong variance are omitted and left for the second phase of the processing. The first phase of the segmentation suggested in this article gathers the following stages:

Course of the image: In order to avoid jumps in the sweeping, which can generate an area change without transitions detection, a path that scans the image is selected Fig. 1.

[FIGURE 1 OMITTED]

Initial state: The starting region is represented by a single node, which forms the graph in its initial state. At each step, and in order to measure the state of the path, a vector of attributes characterizing the site is calculated. It is composed of the central pixel color, the average and the standard deviation of the 3 by 3 vicinity window.

Detection of a transition: In the presence of a relatively significant fluctuation of the attribute standard deviation, the membership of the current site vicinity to a contour indicating the crossing of a new region border becomes very probable. A threshold is predetermined to indicate the existence of a transition.