spacer back contents
ERCIM News No.50, July 2002


Marked Point Processes in Image Analysis

by Xavier Descombes and Josiane Zerubia

The ARIANA research group at INRIA is developping new stochastic models based on the point process framework to tackle image analysis and feature extraction problems.

Bayesian approaches play a leading role in image analysis. They have been widely applied, among other things to quite numerous possible industrial applications, including image segmentation, image restoration and cartographic feature extraction. Basically, they consist of embedding the problem into a probabilistic framework by modelling each pixel as a random variable. Consider for instance the image segmentation problem. The goal is to obtain a partition of the image into regions which are homogeneous with respect to the image radiometry or some texture properties.

A prior, usually a Markov Random Field, is defined to model the knowledge about the expected result. In the case of segmentation, this prior can depend on the number of neighboring pixels belonging to two different regions. The prior will tend to minimize this number, penalizing partitions with numerous contours.

The data model is given by the likelihood. Without considering the neighborhood, the probability of one pixel to belong to a specific region depends on its radiometry. The result is then obtained by maximizing a Bayesian criterion such as Maximum A Posteriori which is the configuration which maximizes the product of the prior and the likelihood. This stochastic framework provides a powerful tool for the inclusion of constraints on the solution, such as homogeneity or smoothness, in the prior, leading to algorithms that are robust with respect to noise.

However, the pixelwise approach is not adequate in the case of high-resolution sensors, for which the object geometry is well defined. It seems useful to consider object level models to deal with data such as aerial images or that provided by the new generation of satellites, for example SPOT 5. In the segmentation case, these objects can be rectangles, triangles or more generally polygons, defining the geometry of objects present in the image.

To deal with this high resolution data, we study the Bayesian approach using marked point processes as priors. The main idea behind a marked point process is to model objects within a stochastic framework. These objects are random in number, are randomly localized, and their geometry is defined by random parameters. Interactions between objects are defined, allowing global properties to be embedded in the model. In addition, object shape is modelled by priors on the point parameters. In the ARIANA research group, we have developed models for image segmentation, extraction of road networks and extraction of buildings in dense urban areas. The aim of these applications is to provide tools for automatic cartography. Figures 1 and 2 show some preliminary results in road and building extraction respectively.

Figure 1

Figure 1:
Road network extraction from an aerial image
provided by the French Mapping Institute IGN
(result obtained by C. Lacoste).

Figure 3
Figure 2:
Left: Aerial image provided by the French Mapping Institute IGN.
Right: extracted buildings (result obtained by M. Ortner).

These models are defined on huge configuration spaces. Indeed, we do not know the number of objects. The configuration space is then the union of the spaces with a fixed number of objects. The usual Metropolis-Hasting algorithm cannot be directly applied to optimize such models. However, suitable extensions have been proposed along the same lines. The principle is to define a Markov Chain which converges to a target distribution. By including a simulated annealing scheme, the chain converges to the Maximum A Posteriori, which is the configuration which maximizes the target distribution. To define the Markov chain, an iterative process is computed. At each step, a new configuration is proposed following the so-called proposal density. This new configuration is accepted with a probability depending on an acceptance ratio which involves the target and the proposal distributions. Although convergence theorems have been proven, the efficiency of these algorithms needs to be improved in practice. A low acceptance ratio leads to a slow convergence speed. Therefore, the results obtained require huge CPU time. To fully appreciate the impact of marked point processes on image processing in term of real applications, further work on optimization techniques is necessary.

Marked point processes appear to be a promising tool for extracting objects from high-resolution remote sensing images. They define an interesting general framework for modelling cartographic features. To exploit fully their modelling power, new mathematical tools for optimizing the derived models are needed. We are currently working on this topic in ARIANA team. The ARIANA team is collaborating with Marie-Colette van Lieshout, CWI on this research topic, partially supported by ERCIM.


Please contact:
Xavier Descombes and Josiane Zerubia, INRIA
Tel: +33 4 92 38 78 57