Automatic Gap Filling in Road Extraction Using Radon Transformation and Spline Interpolation

Document Type : علمی - پژوهشی


1 Prof. of Remote Sensing & GIS Dep., Shahid Beheshti University

2 Lecturer of Remote Sensing & GIS Dep., Shahid Beheshti University

3 Ph.D. Candidate of Cognitive Telecommunications Group, Dep. of Electrical and Computer Engineering, Shahid Beheshti University


The availability ofinformation about roads has great importanceinvariousapplicationssuch as transportation,traffic controlsystems, automatic navigation system, etc. In recent years, designing new road extraction algorithms has become the target of many studies by researchers. Despite the achieved progress, there are some defects in this field. The gaps in detected roads are one the most important of them. The gaps are appeared due to getting placed under trees, shadow or any other reason. Since the continuity of roads is a momentous topological trait, so filling the gaps seems necessary. The main aim of this paper is to provide a method to automatic find and fill the existing gaps in the extracted road net. Our algorithm first applies the Radon transformation to find the source and destination endpoints of the gaps, then connect these points together using Spline interpolation. This algorithm is implemented on a real detected road which has 4 gaps in straight roads and 2 gaps in junctions. The experiment shows that the proposed algorithm can correctly fill all of the gaps in straight roads, but it is not able to fill the gaps in junctions. So, regardless of the location of the gap, straight road or junction, it can be said that about 66.7% of the existing gaps was filled by the algorithm. This gap filling algorithm is implemented in MATLAB software


  1. Akhras, M.S., Unemo, M., Thiyagarajan, S., Nyre´n, P., Davis, R.W., Fire, Z.A. & Pourmand, N., 2007, Connector Inversion Probe Technology: a powerful one-primer multiplex DNA amplification system for numerous scientific applications, PLoS ONE 2(9): e915. doi:10.1371/journal.pone.0000915.
  2. Chiang, Y., Knoblock, C. & Chen, C., 2005, Automatic Extraction of Road Intersections from Raster Maps, In GIS '05: Proceedings of the 13th annual ACM international workshop on Geographic information systems, Bremen, Germany,
  3. PP. 267-276.
  4. Chiang, Y., Knoblock, C., Shahabi, C. & Chen, C., 2008, Automatic and Accurate Extraction of Road Intersections from Raster Maps, GeoInformatica 13, PP. 121-157.
  5. Dirac, P.A.M., 1984, The Principles of Quantum Mechanics, Oxford University Press, Oxford.
  6. Faessel, M., Courtois, F., 2009, Touching Grain Kernels Separation by Gap-filling, Image Anal Stereol, 28, PP. 195–203.
  7. Fischler, M.A. & Heller, A.J., 1998, Automated Techniques for Road Network Modeling, In: Proceedings of DARPA Image Understanding Workshop, PP. 501–516.
  8. Garcia, A., Honda, A. & Meves, N., 2008, Gap Detection in Road Networks with Linear and Polynomial Models, UCLA Department of Mathematics, August 8th.
  9. Gardner, M., Roberts, D.A., Funk, Ch. & Noronha, V., 2001, Road Extraction from AVIRIS Using Spectral Mixture and Q-tree Filter Techniques, Technical Report, University of California, Santa Barbara, National Consortium on Remote Sensing and Transportation: Infrastructure.
  10. Hashemi, S., Valadan Zoej, M.J. & Mokhtarzadeh, M., 2011, Automatic Road Gap Detection Using Fuzzy Inference System, International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XXXVIII-4/W19, PP. 101-103.
  11. Henderson, T. & Linton, T., 2009, Raster Map Image Analysis, In ICDAR '09: Tenth International Conference on Document Analysis and Recognition, Catalonia, Spain, PP. 376-380.
  12. Khotanzad, A. & Zink, E., 2003, Contour Line and Geographic Feature Extraction from Usage Color Topographical Paper Maps, IEEE Transactions on Pattern Analysis and Machine Intelligence, 25, 1, PP. 18-31.
  13. Li, X., Zhang, Sh., Pan, X., Dale, P., Cropp, R., 2010, Straight Road Edge Detection from High-resolution Remote Sensing Images based on the Ridgelet Transform with the Revised Parallel-beam Radon Transform, International Journal of Remote Sensing, 31, 19, PP. 5041-5059.
  14. Massopust, P., 2010, Interpolation and Approximation with Splines and Fractals, Oxford University Press, January 14.
  15. Matkan, A., Sadeghian, S., Mohammadzadeh, A. & Hajeb, M., 2011, Road Detection from Lidar Data Using SVM Classification, International Conference on Sensor and Models in Photogrammetry and Remote Sensing (SMPR), May 18-19, Tehran, Iran.
  16. Maurya, R., Singh, Sh., Gupta, P.R., Sharma, M.K., 2011, Road Extraction Using K-mean Clustering and Morphological Operations, International Journal of Advanced Engineering Sciences and Technologies, 5(2), PP. 290-295.
  17. Mena, J.B., 2003, State of the Art on Automatic Road Extraction for GIS Update: A novel classification, Pattern Recognition Letters, 24(16), PP. 3037–3058.
  18. Miciak, M., 2010, Radon Transformation and Principal Component Analysis Method Applied in Postal Address Recognition Task, International Journal of Computer Science and Applications, 7, 3, PP. 33–44.
  19. Mnih, V., Hinton, G., 2010, Learning to Detect Roads in High-resolution Aerial Image, European Conference on Computer Vision, PP. 210-223.
  20. Mountrakis, G., Luo, L., 2011, Enhancing and spectral Information with Intermediate Structural Inputs: A case study on impervious surface detection, Remote Sensing of Environment, 115, 5, PP. 1162–1170.
  21. Murphy, L.M., 1986, Linear Feature Detection and Enhancement in Noisy Images via the Radon Transform, Pattern Recognition Letters, 4, PP. 279−284.
  22. Porikli, F., Keaton, T., 2000, Unsupervised Road Extraction Algorithm in Low-resolution Satellite Imagery, IAPR Pattern Recognition for Remote Sensing Workshop, Andorra.
  23. Pouderoux, J., Spinello, S., 2007, Global Contour Lines Reconstruction in Topographic Maps, In ICDAR '07: Proceedings of the Ninth International Conference on Document Analysis and Recognition, IEEE Computer Society, Washington, DC, USA, PP. 779-783.
  24. Radon, J. 1917, Über die Bestimmung von Funktionen durch ihre Integralwerte längs gewisser Mannigfaltigkeiten, Berichte über die Verhandlungen der Sächsische Akademie der Wissenschaften, Reports on the proceedings of the Saxony Academy of Science, 69, PP. 262−277.
  25. Risser, L., Plourabou´e, F., Descombes, X., 2008, Gap Filling of 3-d Microvascular Networks by Tensor Voting. IEEE Transactions on Medical Imaging, 27, 5, PP. 674-687.
  26. Rochery, M., Jermyn, I.H., Zerubia, J., 2004, Gap Closure in (road) Networks Using Higher-order Active Contours, In: Proc. IEEE International Conference on Image Processing, Singapore, October.
  27. Rochery, M., Jermyn, I.H., Zerubia, J., 2005, New Higher-order Active Contour Energies for Network Extraction, In: Proc. IEEE International Conference on Image Processing, Genoa, Italy, September.
  28. Rochery, M., Jermyn, I.H., Zerubia, J., 2006, Higher-order Active Contours, International Journal of Computer Vision, 69 (1), PP. 27–42.
  29. Rochery, M., Jermyn, I.H., Zerubia, J.B., 2007, Higher-order Active Contour Energies for Gap Closure, Journal of Mathematical Imaging and Vision, 29(1), PP. 1-20.
  30. Szymczak, A., Tannenbaum, A., Mischaikow, K., 2005, Coronary Vessel Cores from 3-D Imagery: A topological approach, in Proc. SPIE-Med. Image Process 2005, 5747,
  31. PP. 505–513.
  32. Terrades, O.R., Valveny, E., 2003, Radon Transform for Lineal Symbol Representation, The Seventh International Conference on Document Analysis and Recognition.
  33. Tesser, H., Pavlidis, T., 2000, Roadfinder front end: an automated road extraction system, in: Proc. 15th International Conference on Pattern Recognition, Barcelona, Spain, PP. 338–341.
  34. Toft, P., 1996, The Radon Transform - theory and implementation, Ph.D. Thesis, Dep. of Mathematical Modelling Section for Dsp of Technical University of Denmark.
  35. Zhang, Ch., Murai, Sh., Baltsavias, E., 1999, Road Network Detection by Mathematical Morphology, Proc. of International Workshop on 3D Geospatial Data Production: Meeting Application Requirements, Paris, PP. 185–200.
  36. Zhang, Q. & Culoigner, I., 2007, Accurate Centerline Detection and Line Width Estimation of Thick Lines using the Radon Transform, IEEE Transactions on Image Processing, 16, PP. 310−316.