poster

Improved Road Network Reconstruction using Discrete Morse Theory

Authors:

Yusu WangAuthors Info & Claims

SIGSPATIAL '17: Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

Article No.: 58, Pages 1 - 4

https://doi.org/10.1145/3139958.3140031

Published: 07 November 2017 Publication History

Abstract

With the rapid growth of publicly available GPS traces, robust and efficient automatic road network reconstruction has become a crucial task in GIS data analysis and applications. In [20], an effective and robust road network reconstruction algorithm was developed based on the discrete Morse theory, which has the state-of-the-art performance in automatic road-network reconstruction. Based on a discrete Morse-based graph reconstruction framework, we provide two improvements of the previous algorithm [20]: (1) we further simplify it and obtain a better empirical time performance; and (2) we develop a simple but effective editing strategy that helps adding missing road segments in the output reconstruction.

References

[1]

M. Ahmed, S. Karagiorgou, D. Pfoser, and C. Wenk. 2015. A comparison and evaluation of map construction algorithms using vehicle tracking data. GeoInformatica 19, 3 (2015), 601--632.

Digital Library

[2]

M. Ahmed and C. Wenk. 2012. Constructing Street Networks from GPS Trajectories. In Proc. 20th Ann. Euro. Sympos. on Algo. 60--71.

Digital Library

[3]

U. Bauer, C. Lange, and M. Wardetzky. 2012. Optimal Topological Simplification of Discrete Functions on Surfaces. Discr. Comput. Geom. 47, 2 (2012), 347--377.

Digital Library

[4]

J. Biagioni and J. Eriksson. 2012. Map inference in the face of noise and disparity. In Proc. 20th ACM SIGSPATIAL. 79--88.

Digital Library

[5]

L. Cao and J. Krumm. 2009. From GPS traces to a routable road map. In Proc. 17th ACM SIGSPATIAL. 3--12.

Digital Library

[6]

D. Chen, L. J. Guibas, J. Hershberger, and J. Sun. 2010. Road network reconstruction for organizing paths. In Proc. 21st ACM-SIAM Symp. on Discr. Algo. 1309--1320.

Digital Library

[7]

J. J. Davies, A. R. Beresford, and A. Hopper. 2006. Scalable, Distributed, Real-Time Map Generation. IEEE Pervasive Computing 5, 4 (Oct. 2006), 47--54.

Digital Library

[8]

O. Delgado-Friedrichs, V. Robins, and A. Sheppard. 2015. Skeletonization and Partitioning of Digital Images Using Discrete Morse Theory. IEEE Trans. Pattern Anal. Machine Intelligence 37, 3 (March 2015), 654--666.

[9]

T.K. Dey, K. Li, C. Luo, P. Ranjan, I. Safa, and Y. Wang. 2010. Persistent heat signature for pose-oblivious matching of incomplete models. Computer Graphics Forum 29, 5 (2010), 1545--1554.

[10]

S. Edelkamp and S. Schrödl. 2003. Route planning and map inference with global positioning traces. In Computer Science in Perspective. Springer, 128--151.

Digital Library

[11]

H. Edelsbrunner and J. Harer. 2010. Computational Topology - an Introduction. American Mathematical Soc. I--XII, 1--241 pages.

[12]

H. Edelsbrunner, D. Letscher, and A. Zomorodian. 2002. Topological persistence and simplification. Discr. Comput. Geom. 28 (2002), 511--533.

Digital Library

[13]

R. Forman. 1998. Morse theory for cell complexes. Advances in mathematics 134, 1 (1998), 90--145.

[14]

A. Gyulassy, M. Duchaineau, V. Natarajan, V. Pascucci, E. Bringa, A. Higginbotham, and B. Hamann. 2007. Topologically Clean Distance Fields. IEEE Trans. Visualization Computer Graphics 13, 6 (Nov 2007), 1432--1439.

Digital Library

[15]

F. Iuricich and L. De Floriani. 2017. Hierarchical Forman Triangulation: a Multi-scale Model for Scalar Field Analysis. Computers & Graphics (2017).

[16]

S. Karagiorgou and D. Pfoser. 2012. On Vehicle Tracking Data-Based Road Network Generation. In Proc. 20th ACM SIGSPATIAL. New York, NY, USA, 89--98.

Digital Library

[17]

V. Robins, P. J. Wood, and A. P. Sheppard. 2011. Theory and Algorithms for Constructing Discrete Morse Complexes from Grayscale Digital Images. IEEE Trans. Pattern Anal. Machine Intelligence 33, 8 (Aug 2011), 1646--1658.

Digital Library

[18]

W. Shi, S. Shen, and Y. Liu. 2009. Automatic generation of road network map from massive GPS vehicle trajectories. In Proc. 12th International IEEE Conference on Intelligent Transportation Systems. 48--53.

[19]

T. Sousbie. 2011. The persistent cosmic web and its filamentary structure - I. Theory and implementation. 414 (June 2011), 350--383. arXiv:astro-ph.CO/1009.4015

[20]

S. Wang, Y. Wang, and Y. Li. 2015. Efficient map reconstruction and augmentation via topological methods. In Proc. 23rd ACM SIGSPATIAL. ACM, 25.

Digital Library

Cited By

Song YFellegara RIuricich FDe Floriani L(2024)Parallel Topology-aware Mesh Simplification on Terrain TreesACM Transactions on Spatial Algorithms and Systems10.1145/365260210:2(1-39)Online publication date: 13-Mar-2024
https://dl.acm.org/doi/10.1145/3652602
Feng HXu XDe Floriani L(2024)ImplicitTerrain: a Continuous Surface Model for Terrain Data Analysis2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)10.1109/CVPRW63382.2024.00095(899-909)Online publication date: 17-Jun-2024
https://doi.org/10.1109/CVPRW63382.2024.00095
Cai CVlassis NMagee LMa RXiong ZBahmani BWong TWang YSun W(2023)EQUIVARIANT GEOMETRIC LEARNING FOR DIGITAL ROCK PHYSICS: ESTIMATING FORMATION FACTOR AND EFFECTIVE PERMEABILITY TENSORS FROM MORSE GRAPHInternational Journal for Multiscale Computational Engineering10.1615/IntJMultCompEng.202204226621:5(1-24)Online publication date: 2023
https://doi.org/10.1615/IntJMultCompEng.2022042266
Show More Cited By

Index Terms

Improved Road Network Reconstruction using Discrete Morse Theory
1. Information systems
  1. Information systems applications
    1. Spatial-temporal systems
      1. Geographic information systems
2. Theory of computation
  1. Theory and algorithms for application domains

Recommendations

Road Network Reconstruction from satellite images with Machine Learning Supported by Topological Methods
SIGSPATIAL '19: Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

Automatic Extraction of road network from satellite images is a goal that can benefit and even enable new technologies. Methods that combine machine learning (ML) and computer vision have been proposed in recent years which make the task semi-automatic ...
On vehicle tracking data-based road network generation
SIGSPATIAL '12: Proceedings of the 20th International Conference on Advances in Geographic Information Systems

Road networks are important datasets for an increasing number of applications. However, the creation and maintenance of such datasets pose interesting research challenges. This work proposes an automatic road network generation algorithm that takes ...
Virtual running model for locating road intersections using GPS trajectory data
IMCOM '17: Proceedings of the 11th International Conference on Ubiquitous Information Management and Communication

Map construction from vehicle trajectories has been an active challenge topic due to the progress of positioning technologies and high cost of map constructions since last decades. In our work, we focus on road network generation from a massive GPS data ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSPATIAL '17: Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 2017

677 pages

ISBN:9781450354905

DOI:10.1145/3139958

Copyright © 2017 Owner/Author.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

SIGSPATIAL: ACM Special Interest Group on Spatial Information

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 November 2017

Check for updates

Author Tags

Qualifiers

Poster
Research
Refereed limited

Conference

SIGSPATIAL'17

Sponsor:

SIGSPATIAL

SIGSPATIAL'17: 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 7 - 10, 2017

CA, Redondo Beach, USA

Acceptance Rates

SIGSPATIAL '17 Paper Acceptance Rate 39 of 193 submissions, 20%;

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
209
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)4

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Song YFellegara RIuricich FDe Floriani L(2024)Parallel Topology-aware Mesh Simplification on Terrain TreesACM Transactions on Spatial Algorithms and Systems10.1145/365260210:2(1-39)Online publication date: 13-Mar-2024
https://dl.acm.org/doi/10.1145/3652602
Feng HXu XDe Floriani L(2024)ImplicitTerrain: a Continuous Surface Model for Terrain Data Analysis2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)10.1109/CVPRW63382.2024.00095(899-909)Online publication date: 17-Jun-2024
https://doi.org/10.1109/CVPRW63382.2024.00095
Cai CVlassis NMagee LMa RXiong ZBahmani BWong TWang YSun W(2023)EQUIVARIANT GEOMETRIC LEARNING FOR DIGITAL ROCK PHYSICS: ESTIMATING FORMATION FACTOR AND EFFECTIVE PERMEABILITY TENSORS FROM MORSE GRAPHInternational Journal for Multiscale Computational Engineering10.1615/IntJMultCompEng.202204226621:5(1-24)Online publication date: 2023
https://doi.org/10.1615/IntJMultCompEng.2022042266
Shen WWu WMao JChen JCao SZhao LZhou AZhou L(2023)SAMI: A Shape-Aware Cycling Map Inference Framework for Designated Driving Service2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00251(3269-3281)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00251
Corcoran PJones C(2023)Topological data analysis for geographical information science using persistent homologyInternational Journal of Geographical Information Science10.1080/13658816.2022.215565437:3(712-745)Online publication date: 4-Jan-2023
https://doi.org/10.1080/13658816.2022.2155654
Vitalis SLabetski ALedoux HStoter J(2022)From road centrelines to carriageways—A reconstruction algorithmPLOS ONE10.1371/journal.pone.026280117:2(e0262801)Online publication date: 22-Feb-2022
https://doi.org/10.1371/journal.pone.0262801
Song YFellegara RIuricich FDe Floriani L(2021)Efficient topology-aware simplification of large triangulated terrainsProceedings of the 29th International Conference on Advances in Geographic Information Systems10.1145/3474717.3484261(576-587)Online publication date: 2-Nov-2021
https://dl.acm.org/doi/10.1145/3474717.3484261
He EBai FHay CChen JBhagavatula V(2021)A Map Inference Approach Using Signal Processing from Crowd-sourced GPS DataACM Transactions on Spatial Algorithms and Systems10.1145/34317857:2(1-23)Online publication date: 15-Jan-2021
https://dl.acm.org/doi/10.1145/3431785
Corcoran PJones C(2021)A persistent homology model of street network connectivityTransactions in GIS10.1111/tgis.1284426:1(155-181)Online publication date: 27-Oct-2021
https://doi.org/10.1111/tgis.12844
Chao PHua WMao RXu JZhou X(2020)A Survey and Quantitative Study on Map Inference Algorithms from GPS TrajectoriesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.2977034(1-1)Online publication date: 2020
https://doi.org/10.1109/TKDE.2020.2977034

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents