Geographic Map Understanding: Algorithms for Hydrographic and Road Networks Reconstruction. Interprétation de Cartes Géographiques: Algorithmes de Reconstruction des Réseaux Hydrographiques et Routiers

Geographic Map Understanding: Algorithms for Hydrographic and Road Networks Reconstruction

Interprétation de Cartes Géographiques: Algorithmes de Reconstruction des Réseaux Hydrographiques et Routiers

Robert Mariani Fabrice Lecourt  Marc Pierrot Deseilligny  Jacques Labiche  Yves Lecourtier 

IGN/DT/SR, Laboratoire MATIS 2 av. Pasteur, 94160 Saint-Mandé

LACP, Université de Caen Faculté des sciences . 14000 Caen

La3i-LACIS, Université de Rouen UFR des sciences et techniques 76821 Mont-Saint-Aignan

Page: 
317-335
|
Received: 
12 June 1996
|
Accepted: 
N/A
|
Published: 
30 June 1997
| Citation

OPEN ACCESS

Abstract: 

The FrenchInstitutGéographiqueNational (IGN) wants to develop an automated map understanding system, for the geographical maps at scale 1/25000. The aim is to automatically convert the 2000 cartographic paper-maps in a geographical objects database, directly usable by a GIS. This paper describes a high-level method for the automated reconstruction of the network graphs, represented on the French geographic maps. This method is applied to the hydrographic and road networks, symbolized with dashed lines, interrupted solid lines and fragmented textured areas. The graph theory paradigm is used, which allows to naturally model those networks by graphs, and to formalize the constraints for their reconstruction. A priori knowledges on natural and cartographic networks are directly used in the reconstruction process, and translated either as invariantsthe networks must verify during the reconstruction, either as quality criterion for the likely considered connexions. 

Résumé 

L'Institut Géographique National (IGN) a pour objectif de développer sur la carte IGN au 1/25000 un système d'interprétation totalement automatique et complet de la carte . Le but est de convertir automatiquement le fond de cartes existant sous forme papier, en une base de données d'objets géographiques directement manipulables par un SIG.Cet article décrit une méthode générale de haut niveau pour la reconstruction automatique des graphes des réseaux représentés sur les cartes géographiques. Elle a été appliquée aux réseaux hydrographiques et routiers qui sont essentiellement composés de lignes tiretées, de traits pleins interrompus et d'objets surfaciques interrompus. Le formalisme utiliséest celui de la théorie des graphes, qui permet de modéliser naturellement ces réseaux et d'expliciter les contraintes liées à leur reconstruction. Les connaissances a priori sur les réseaux réels et cartographiques sont directement intégrées dans le processus de reconstruction, et traduites soit comme des invariants que doivent vérifier les réseaux en cours de reconstruction, soit comme des mesures de qualité sur les connexions vraissemblables envisagées. 

Keywords: 

Geographic map understanding, Image analysis, Model, Minimum weighting spanning subtree, Network reconstruction, Polygonal clipping, Graph theory.

Mots clés 

Interprétation de cartes géographiques, Analyse d'image, Modélisation, Arbre recouvrant de poids minimum, Reconstruction de réseau, Découpage polygonal, Théorie des graphes.

1. Introduction
2. Méthodologie
3. Prétraitements de l'Image Initiale
4. Transformation des Lignes Tiretées en Traits Pleins
5. Connexion des Traits Pleins entre Eux
6. Extensions pour le Réseau Hydrographique
7. Résultats et Performances
8. Conclusion et Perspectives
  References

[1] M.Pierrot Deseilligny, Lecture Automatique de Cartes. Thèse, Université René Descartes, Centre Universitaire des Saints-Pères, UFR deMathématiques etInformatique, Paris V, Oct. 1994. 

[2] A. Khotanzad and E.Zink,"Color Paper Map Segmentation Using Eigenvector Line Fitting," inProceedings of the IEEE Southwest Symposium on Image Analysis and Interpretation, San Antonio, TEXAS (USA), pp. 190-194, Apr. 1996.

[3] L. Lefrère, Contribution au Développement d'Outilspourl'Analyse Automatiquede DocumentsCartographiques.Thèse, Université de Rouen, Rouen, Oct. 1993. 

[4] J. Ogier, Contribution à l'Analyse Automatique de Documents Cartographiques : Interprétation de Données Cadastrales.Thèse, Université de Rouen, Rouen, Jan. 1994. 

[5] L. Boatto and al., "An Interpretation System for Land Register Map,"IEEE Computer Society Press, vol. 25, pp. 25-33, July 1992.

[6] P. Vaxivière and K. Tombre, "Celesstin : CAD Conversion of Mechanicals Drawings,"IEEE Computer Society Press, vol . 25, pp. 46-54, July 1992. 

[7] S. Joseph and T. Pridmore, "Knowledge-Directed Interpretation of Mechanical Engineering Drawings," IEEE Transactions on PAMI, vol. 14, pp. 928940, Sept. 1992. 

[8] B. Couasnon, «Formalisation de laConnaissance Grammaticalea prioripour l'Analyse de Documents : Application aux Partitions d'Orchestre », in Actes I0ème CongrèsAFCET Reconnaissance des Formeset Intelligence Artificielle, Rennes, pp. 465-474, Jan. 1996. 

[9] I. Leplumey, J. Camillerapp, and G. Lorette, "A Robust Detector for Music Staves," in Proceedings of 2nd International Conference on Document Analysis and Recognition, Tsukuba (Japan), pp. 902-905, Oct. 1993. 

[10] R. Thomson, "Micrograph Analysis and Image Understanding," inProceedings of the IEEE Southwest Symposium on Image Analysis and Interpretation, San Antonio, TEXAS (USA), pp.48-53, Apr. 1996. 

[11] J. McDaniel and J. Balmuth, "Automatic Interpretation of Chemical Structure Diagrams," in Lecture Notes in Computer Sciences, vol . 1072, pp. 148158, 1996. 

[12] R.Mullot,F. Brisepierre, Y. Lecourtier, M. Collinas, and J. Ogier, "Méthode Robuste de Localisation de Vignettes Circulaires sur des Plans Techniques," inActes du Quatrième Colloque Nationalsur l'Écritetle Document, Nantes, pp. 77-84, July 1996. 

[13] G. Myers, P. Mulgaonkar, C. Chen, J. DeCurtins, and E. Chen, "VerificationBased Approach for Automated Text and Feature Extraction From RasterScanned Maps," in Proceedings of IAPR International Workshop on Graphics Recognition, Penn State Scanticon (USA), pp. 90-99,Aug. 1995. 

[14] J. Den Hartog, T. Ten Kate, and J. Gerbrands, "Knowledge-Based Segmentation for Automatic Map Interpretation," in Proceedings of IAPR International Workshop on Graphics Recognition, Penn State Scanticon (USA),pp. 71-80,Aug. 1995. 

[15] R. Mariani, M. PierrotDeseilligny, J. Labiche, Y. Lecourtier, and R.Mullot, "Geographic Map Understanding. Algorithms for HydrographieNetwork Reconstruction," in Lecture Notes in Computer Sciences, pp. 514-515, Dec. 1995. 

[16] M.PierrotDeseilligny, H.LeMen, and G. Stamon, "Map Understanding for GISData Capture. Algorithms for Road Network Graph Reconstruction," in Proceedings of 2nd International Conference on Document Analysis and Recognition, Tsukuba (Japan), pp. 676-679, Oct. 1993. 

[17] M. Gondran and M. Minoux, GraphesetAlgorithmes, pp. 1-33. Vol. 1 of de la Direction des Etudes et Recherches d'Electricité de France [43], 1985.

[18] L. O'Gorman and R. Kasturi, Document Image Analysis,pp. 101-105. Los Alamitos, California : IEEE Computer Society Press, 1995 .

[19] R . Duda and P. Hart, "Use of the Hough Transform to Detect Lines and Curves in Pictures," Communication of the Association of Computer Machinery, vol . 15, no. 1, pp. 11-15, 1972.

[20] H . Yamade, K. Yamamoto, and K. Hosokawa, "Directional Mathematical Morphology and Reformalized Hough Transformation for the Analysis of Topographies Maps," IEEE Transactions onPAMI, vol. 15, no. 4, pp. 380-387, 1993.

[21] G. Again, H. Luo, and I. Dinstein, "Morphological Approach for Dashed Lines Detection," in Proceedings of IAPR International Workshop on GraphicsRecognition, Penn Stale Scanticon (USA), pp.23-32,Aug. 1995. 

[22] T. Kasvand, "Linear Texture in Line Drawing," in Proceedings of 8th International Conference on Pattern Recognition, Paris (France), pp .398-401, Oct. 1986.

[23] C. Lai and R. Kasturi, "Detection of Dashed lines in Engineering Drawings and Maps," inProceedings of First International Conference on Document Analysis, Saint-Malo, France, pp. 507-514, 1991. 

[24] D. Dori, L. Wenyin, and M. Peleg, "How to Win a Dashed Line Detection Contest," inLecture Notes in Computer Sciences, vol. 1072, pp. 286-300, 1996. 

[25] T. Nagao, T. Agui, and M. Nakajima, "An Automatic Road Vector Extraction Method from Maps," in Proceedings of 9th International Conference on Pattern Recognition, Rome (Italy), pp.585-587, 1988. 

[26] D. Antoine, "A Technical Document Understanding System Based on a priori Knowledge," in Proceedings of 6th Scandinavian Conference on Image Analysis, Oulu (Finland), pp. 843-846, Dec. 1989. 

[27] O. Hori and A. Okasaki, "High Quality Vectorization Based on a Generic Object Model," in Pre-proceedings of 1APR Workshop on Syntactic and Structural Pattern Recognition, Murray Hill, NJ (USA), pp. 137-153,Aug. 1990. 

[28] J. Ogier, J. Labiche, R. Mullot, and Y. Lecourtier, "Attributes Extraction for French Map Interpretation," in Proceedings of 2nd International Conference on Document Analysis and Recognition, Tsukuba (Japan), pp. 672-675, Oct. 1993. 

[29] M. PierrotDeseilligny, H.LeMen, and G. Stamon, « Lectureautomatique des écritures sur cartes scannées », inActesdu Troisième Colloque National sur l'ÉcritetleDocument, Rouen, pp. 195-202, July 1994. 

[30] M. Sonka, V. Hlavac, and R. Boyle, Image Processing, Analysis and Machine Vision, pp. 477-506. London Glasgow Weinheim New-York Tokyo Melbourne Madras : Chapman and Hall Computing, 1994. 

[31] M. 31 and J. Chermant,Précisd'Analyse d'Images,pp. 82-86. Paris: Presses duCNRS, 1989. 

[32] E. Davies, "A Modified Hough Scheme for General Circle Location," Pattern Recognition Letters, vol.7, pp. 37-43, 1988. 

[33] S. Thomas and Y.Chan,"A Simple Approach for the Estimation of Circular Arc Center and Its Radius," in Computer Vision, Graphics and Image Processing, vol. 45, pp. 362-370, 1989. 

[34] R. Takiyama and N. Ono, "A Least Square Error Estimation of the Center and Radii of Concentric Arcs," in Pattern Recognition Letters, vol . 10, pp. 237-242, 1989. 

[35] D. De Brucq, M. Amara, and V. Ruiz, « Segmentation de Tracés Manuscrits par Arcs deCercle », inActesduQuatrième ColloqueNationalsur l'Écrit et leDocument, Nantes,pp. 155-161, July 1996. 

[36] S. Beucher and L. Vincent, "Introduction aux Outils Morphologiques de Segmentation," tech. rep., Centre de Morphologie Mathématique. Ecole desMines, 1989. 

[37] C. Maquair, « Reconnaissance des Plans de Réseau EDF : Etude de Faisabilité », tech. rep., ENSEA, Université de Cergy Pontoise, Sept. 1996.

[38] M. Pierrot Deseilligny, Annexes Lecture Automatique de Cartes. Thèse Université René Descartes, Centre Universitaire des Saints-Pères, UFR de Mathématiques et Informatique, Paris V, Oct. 1994.

[39] L. Vincent, Algorithmes Morphologiques à Base de Files d'Attentes et de  

Lacets. Extension aux Graphes. Thèse, Ecole Nationale Supérieure des Mines de Paris, Paris, 1990. 

[40] M. Gondran and M. Minoux, Graphes et Algorithmes, pp. 35-68. Vol. 1 of de la Direction des Etudeset Recherches d'Electricité de France [43], 1985.

[41] M. Gondran and M. Minoux, GraphesetAlgorithmes, pp. 112-115, Vol. I of de la Direction desEtudes etRecherches d'Electricité de France [431, 1985. 

[42] Y. 42,Elements de CAO. Matériels etLogiciels de Base, vol . I,pp. 179-197. Paris,Londres,Lausanne : Hermès, 1988.

[43] M. Gondran and M. Minoux, Graphes etAlgorithmes. Collection de la Direction des Etudes et Recherches d'Electricité de France, 1985.