A Graph-Based Road Conflation Method Preserving Connectivity
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| 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 | 10.5446/68991 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language | ||
| Production Year | 2022 |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
| |
| Keywords |
FOSS4G Firenze 2022252 / 351
1
7
13
22
25
31
33
36
39
41
43
44
46
52
53
55
58
59
60
76
80
93
98
104
108
127
128
133
135
141
142
143
150
151
168
173
176
178
190
196
200
201
202
204
211
219
225
226
236
242
251
258
263
270
284
285
292
00:00
Connectivity (graph theory)Graph (mathematics)Cartesian coordinate systemComputer animation
00:12
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
09:31
ResultantComputer animation
09:43
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
12:58
Multitier architectureConnectivity (graph theory)Software developerAlgorithmSet (mathematics)Graph (mathematics)Computer animation
Transcript: English(auto-generated)
00:01
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
00:22
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
00:42
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
01:02
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
01:23
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,
01:41
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,
02:03
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?
02:25
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.
02:43
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
03:03
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,
03:24
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
03:45
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,
04:02
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.
04:20
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.
04:41
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,
05:04
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.
05:21
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.
05:41
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,
06:02
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.
06:24
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
06:41
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
07:03
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
07:26
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?
07:42
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
08:04
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.
08:23
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,
08:42
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.
09:00
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
09:21
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.
09:41
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
10:05
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
10:21
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
10:40
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
11:00
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.
11:25
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.
11:40
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
12:00
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.
12:22
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
12:42
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
13:03
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.
13:21
Thank you.