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
OPEN ACCESS
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.
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] 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.