We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

A Graph-Based Road Conflation Method Preserving Connectivity

00:00

Formal Metadata

Title
A Graph-Based Road Conflation Method Preserving Connectivity
Title of Series
Number of Parts
351
Author
Contributors
License
CC Attribution 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language
Production Year2022

Content Metadata

Subject Area
Genre
Abstract
Connectivity of roads in a map is essential for many use cases including navigation. We present a graph-based solution to the road conflation problem which takes into account the connectivity of the road network. First, we generate a road network graph in both sources based on bifurcation points. Second, we carry out node and edge matching between the graphs where we follow shortest distance as a matching criterion. This is followed by the merging stage where graph edges with matching end nodes get conflated. Newly added roads are connected with the graph based on node and edge matching. We carry out experiments on conflating open source footway datasets from multiple cities with the OSM. The resulting conflated map contains up to 16x map feature improvements per city with geometrically accurate and smooth results around road junctions. Future work involves using different graph matching criteria to improve on the conflated output.
Keywords
202
Thumbnail
1:16:05
226
242
Connectivity (graph theory)Graph (mathematics)Cartesian coordinate systemComputer animation
Connectivity (graph theory)Graph (mathematics)Graph (mathematics)String (computer science)ResultantVertex (graph theory)Open setDirected graphMatching (graph theory)CASE <Informatik>Connectivity (graph theory)Line (geometry)AreaProjective planeMatching (graph theory)Marginal distributionAdditionAlgorithmGeometrySoftwareArtificial neural networkData structureSlide ruleLevel (video gaming)Rule of inferenceGraph coloringFigurate numberPartial derivativeState observer2 (number)Augmented realitySimilarity (geometry)MathematicsCategory of beingOpen sourceRepresentation (politics)Wave packetVirtual realityFunction (mathematics)Local ringSet (mathematics)Process (computing)InformationFocus (optics)Goodness of fitÜberlastkontrolleRange (statistics)Multiplication signPresentation of a groupPredictabilityMathematical optimizationMetric systemLoop (music)Computer animation
ResultantComputer animation
Open sourceSpur <Mathematik>Graph (mathematics)Matching (graph theory)String (computer science)Extension (kinesiology)outputProcess (computing)Vertex (graph theory)Connectivity (graph theory)ResultantRight angleProcess (computing)outputString (computer science)Variety (linguistics)Different (Kate Ryan album)MereologyMedical imagingLine (geometry)Graph (mathematics)Vertex (graph theory)Multiplication signElectronic mailing listTerm (mathematics)AreaPresentation of a groupData conversionSet (mathematics)Complete metric spaceMappingPoint (geometry)WeightBitStandard deviationPreprocessorComputer animation
Multitier architectureConnectivity (graph theory)Software developerAlgorithmSet (mathematics)Graph (mathematics)Computer animation
Transcript: English(auto-generated)
Hi, my name is Esra, so I will be talking about our work on graph-based road conflation and its application on footways. So here is a brief agenda. I'll first start by giving motivation, like why connectivity-preserving conflation
is important for us, and then how does this graph-based conflation method work. Junzi will continue with results and then we'll conclude the presentation. So our major motivation in this work is improving road network coverage, and this impacts a
wide range of use cases, from transportation, accessibility, routing and navigation as indicated in the previous talk, talking about city planning, traffic and congestion prediction, all these relate to a good road network coverage, and recently there are a lot of augmented
reality or virtual reality use cases, which requires a good comprehensive coverage of the city using outdoor map data. The focus in this work is on footways. There is a big reason about it, because especially in the areas that we are focusing
in the U.S., we do not have good OSM coverage for pedestrian features. I'm talking about sidewalks, crosswalks, pathways, you know, anything that you would go by foot, like in this beautiful city, I think we are used to having this nice map, but yeah,
I mean the coverage oftentimes is pretty scattered and minimal in most cities that we were researching. We encountered, city GIS departments are providing open source data sets for footways. They are manually created, they are pretty fresh, like, you know, recent data sets,
and these data sets can definitely help improve the coverage. Then the question is, okay, we have OSM data, and we don't want to basically go away from this huge opportunity, like, you know, huge ecosystem that OSM provides by only, like, you know, using open map data, so how do we merge these two different sources?
How do we create a merged map at the end? For this, when we were looking at the literature, how, you know, this map conflation problem solved, especially for line string-based features, we can categorize the methods into two.
There are local feature matching-based methods where you are looking at these road network, these line strings, you are looking at locally spatial area and trying to find some similarity between the two networks. So this obviously would not consider the overall global, like, you know, network structure
and might lose some information during the process. The second category of methods are graph matching-based methods, and this is pretty much, like, studied well in math. So often in these methods, when we apply these methods into map merging or map conflation,
people use geometric features around graph nodes and edges, define some similarity metrics, and some of these methods can involve optimization, like how these, you know, similarities should be minimized, maximized, and we can constrain these methods on preserving the
graph structure itself. So by looking at the motivation about preserving connectivity in this overall network, we went with the graph matching-based algorithms in our work. During the literature search, we also came across some deep learning-based methods recently,
but, I mean, creating a training set, ground truth, is also, you know, a hard task here. So we, again, proceeded with graph matching methods. So there are two major steps here when we are talking about matching.
The first one is, yeah, we have OSM nodes and ways, but we need to construct a graph out of this, you know, data representation. So this representation actually was a really easy thing to use for us because the rule that we put here was, okay, we are going to look at each node.
If that node appears in multiple ways, then that means it should be a graph node. This is how we, you know, created the nodes of the graph, and anything in between those selected nodes are considered graph edges in this case, which are basically line strings. So at the next step, we continued with matching the nodes and edges,
which I'll continue in the next slides. Before that, so I would like to also mention all the figures that you are seeing here are based on Boston open sidewalk data that's provided by Boston's city GIS department.
So an example here on how we constructed the graph on an example area in Boston again. So the colors represent different edges in the graph. So by looking at this graph, we were like pretty pleased about, you know, what we are seeing.
You know, it was able to create really meaningful nodes for us. But one observation we had was, especially at the places where there are partial matches between line strings, there might be some missing nodes, like missing matching nodes in this case. So it would be hard for us to do edge matching or node matching, like, you know,
considering these partial matches. So as a solution, what we did was we revised our graph by generating these intermediate nodes by doing some projections to the nearest line strings. So this provided us a great base for continuing with node and edge matching.
So for matching nodes, we started simple. We said we are going to do nearest neighbor search. But in this case, I would like to highlight, like, at this example on the figure, you are seeing a really simple intersection. But oftentimes, when we looked at how the sidewalks were delineated around these
intersections, it was really various, you know, various styles you would see. So there might be additional line strings coming out of sidewalks and connecting to crosswalks. So every mapper has his or her own style. So we ended up doing one-to-many matching for nodes in this case to handle these
intersection cases. For matching edges, similarly, we are using a predefined margin. And based on this margin, we are searching for line strings that are close to the graph edge, basically. So overall, by doing edge matching, we are trying to discard unnecessary edges at
the merged data structure while node matching is providing us the connectivity. Like, if there are new edges coming in, how do we connect to the main, like, you know, OSM network structure?
So here is the summary of the overall algorithm. Like, after constructing the graph and then finding the matches between nodes and edges, we proceeded with what we call conflation. So the output of this step is the merged road network structure, which can be used
for any of the use case that we mentioned. So the reference network, reference graph here is, we consider it as OSM. And the source network is coming from open map data sources. So what we do is we first look at each edge.
And if there is a matching edge in the reference graph, then that means that edge needs to be discarded. So we are conflating that edge. If not, then we are looking at the nodes. And if the nodes have some matching nodes in the reference network, then that means,
you know, that edge was missing from the merged result. So we are adding this edge. Oh, before, well, we need to check whether that edge exists in the reference graph. So if it exists in the reference graph, we conflate that.
If it doesn't, we add this as a new edge. So for all other cases, if there is no matching, basically, this is an area that's not covered with OSM. We are adding this as a new edge. And at each, at the end of this loop, we are doing connectivity fix. Because now we have, you know, new line strings, new edges coming into this
merged network, merged result. And we are using node matching when we are doing the connection of these new line strings to the network. I'm placing the microphone to Yunzi here. She'll talk about the results.
Thank you. Yeah, so the conflation result itself actually is quite promising. At this point, we applied these experiments of graph-based conflation on more than four cities. Each result was rooted and curated by our mapping team. We do find that there's significant increase in terms of the pedestrian way
of coverage in these cities. For example, Austin has more than 16 times increase, and Boston has around five times increase. There's also some cities we didn't list here, which is Denver and Houston. They even have more than 30 times increase in terms of the coverage
of pedestrian way. So let's take a closer look at the results to understand this conflation process better. So we start with the node matching only. Here's one example. We extract the intersection nodes from both datasets and do the node
pairings of these intersecting nodes and apply the node matching on that, on the conflation. You can see the results looks pretty good in this urban area. But this is a node matching only. In some area, if we apply the node matching only, there's still some
issues remained. For example, look at the middle image here. You can see there's some duplicate road segments as part of the roads. So we apply the edge matching for conflation process. And now look at the right image here. After apply the edge matchings, the conflation results is even better to handle the duplicated part.
Working on the conflations, we observe there are different variety of pedestrian dataset. So we realize that some preprocessing to standardize the input data is pretty beneficial.
Here's examples about connectivity fix. When the dataset does not have common nodes between the intersecting line string, we intersecting the line string and apply the intersecting nodes. And then we remove the extra small edges as the tiny green edges show
on the left image. And then on the right image is an example that when the edges does not connect at corner, we extend these line strings and connect them. Here's the example showing that before and after the connectivity fix for the conflation process.
So in the middle two image, you can see before we applied the connectivity fix to standardize input data, the results still looks a little bit off. The connection is not that good. After apply the connectivity fix, and sometimes we also apply smoothing fix for the dataset, the conflation results has
significant improvement. We didn't include it in our presentation today here, but we also have post-processing steps, which is also working on connectivity fix and smoothing fix to make the results, a conflation result, more accurate. So in conclusion, we observed these graph-based conflation
algorithms actually pretty great for preserving the connectivity. And in the future, like given the diversity of pedestrian datasets, we also plan to develop more, have more development on the pre-processing step to standardize the datasets.
Thank you.