Mise en correspondance d’un couple de réseaux linéïques : application à l’analyse et au recalage de réseaux routiers extraits d’un couple carte/image SPOT

Mise en correspondance d’un couple de réseaux linéïques : application à l’analyse et au recalage de réseaux routiers extraits d’un couple carte/image SPOT

Matching of two line networks: application to the analysis and registration of road networks extracted from a couple map/SPOT image

Christine Hivernat Xavier Descombes  Sabine Randriamasy  Josiane Zerubia 

Ariana, projet commun CNRS/INRIA/UNSA, INRIA, 2004 route des Lucioles, BP93, 06902 Sophia Antipolis cedex, France

Alcatel CRC, route de Nozay, 91460 Marcoussis, France

Corresponding Author Email: 
Christine.Hivernat@inria.fr
Page: 
21-32
|
Received: 
20 January 1999
|
Accepted: 
N/A
|
Published: 
29 February 2000
| Citation

OPEN ACCESS

Abstract: 

We consider the problem of line graphs matching. The nodes correspond to segments characterized by their length and their angle. A Markov model allows us to embed the problem into a labelling problem. The derived model is invariant with respect to rotations and translations. The algorithm is applied to road networks extracted from a SPOT image and a cartographic database. The matching is performed after having chained the road pixels extracted from the image. After the matching, a qualification step provides a registration matrix and allows us to interpret the results in order to update the cartographic database.

Résumé

Nous traitons de la mise en correspondance de graphes linéïques, c’est-à-dire de graphes dont les nœuds représentent des segments caractérisés par leur longueur et leur angle. Un modèle markovien nous permet de considérer le problème comme un problème d’étiquetage. Le modèle définie est invariant par translation et rotation.

Cet algorithme est appliqué aux réseaux routiers issus d’une image et d’une base de données cartographique. La mise en correspondance est effectuée après une étape de chaînage des pixels « routes » extraits de l’image. A l’issue de la mise en correspondance, une étape de qualification des appariements obtenus permet à la fois de calculer une matrice de recalage et d’interpréter les résultats en vue d’une mise à jour cartographique.

Keywords: 

Graph matching, Markov Random Fields on graphs, Automatic validation, SPOT images, Cartography, Road networks

Mots clés

Mise en correspondance de graphes, Champs de Markov sur graphes, Validation automatique, Images SPOT, Cartographie, Réseaux routiers

1. Introduction
2. Mise En Correspondance De Réseaux Linéïques
3. Application Aux Réseaux Routiers D’un Couple Image SPOT/Carte
4. Résultats
5. Conclusion Et Perspectives
  References

[1] J. Besag, « Spatial interaction and the statistical analysis of lattice systems (with discussion) », Journal Roy. Statis. Soc. B., 36, 192-236, 1974.

[2] G.R. Cross et A.K. Jain, « Markov random field texture models », IEEE Trans. on Pattern Analysis and Machine Intelligence, 5, 1, 25-39, 1983.

[3] N. Ayache, et B. Faverjon, « Efficient registration of stereo images by matching graph descriptions of edge segments ». Rapport de recherche 559, inria, Août 1986.

[4] R. Azencott et C. Graffigne, « Non supervised segmentation using multi-level markov random fields ». In Int. Conf. Pattern Recognition, p. 201-204, 1992.

[5] S. Geman et D. Geman, « Stochastic relaxation, Gibbs distribution, and the Bayesian restoration of images ». IEEE Transaction on Pattern Analysis and Machine Intelligence, 6(6), 721-741, Novembre 1984.

[6] P. Gros, O. Bournez et E. Boyer, « Using geometric quasi-invariants to match and model images of line segments ». Rapport de recherche 2608, inria, Juillet 1995.

[7] R.C. Wilson et E.R. Hancock, « Structural matching by discrete relaxation, IEEE Transaction on Pattern Analysis and Machine Intelligence, 19(6), 634-648, Juin 1997.

[8] G. Medioni et R. Nevatia, « Matching images using linear features », IEEE Transaction on Pattern Analysis and Machine Intelligence, 6(6), 675-685, Novembre 1984.

[9] I. Gaudron, « Champs Markoviens et mise en correspondance de contours en imagerie », PhD thesis, Orsay, 1992.

[10] S. Mustiere, « Généralisation adaptative du linéaire basé sur la détection des empâtements, application au routier, Bulletin d’information de l’IGN, Vol. 69, 1998.

[11] F. Tupin, H. Maitre, J.F. Mangin, J.M. Nicolas and E.A. Pechersky, « Detection of linear feature in sar images : Application to road network extraction, IEEE Transactions on Geoscience and Remote Sensing, 36, 2, 434-453, 1998.

[12] W.P. Press, B.P. Flannery, S.A. Teukolsky and W.T. Vetterling, Numerical receipes in C : the art of scientific computing, chapter X, Cambridge University Press, 1988.