# A Multilevel Road Alignment Model for Spatial-Query-by-Sketch
## 3 Materials and Methods
### Characteristics and Matching Approach for Individual Roads
#### 3.2.1 Extraction of Main Roads  
Main roads are the principal routes for regional traffic. According to analysis by [PERSON] et al. [24], main roads exhibit a high similarity between a sketch map and a metric map. The proposed approach attempts to extract the main roads from sketch maps and match them with the roads shown in a metric map. The method reported by [PERSON] and [PERSON] [43] is considered, which is an expansion of the approach proposed by [PERSON] [44] to classify streets in an urban street network using three factors:  
1. The degree centrality (\(DC\)), also known as the connectivity, indicates the number of roads connected to a certain road. A given road is considered more important if a larger number of roads are connected to it. In Figure 1a, R2' has three roads connected to it (R0', R1', and R3'); therefore, the \(DC\) of R2' is 3. R3' has only one road (R2') connected to it, and therefore, the corresponding \(DC\) is 1. Consequently, R2' is more important than R3' in terms of \(DC\).  
Figure 1: Representation of a road scene and its corresponding connectivity matrix. (**a**) A road scene showing four individual roads (black line segments: R0’, R1’, R2’, and R3’); one composite road (yellow line: R0’ and R1’); and five individual road endpoints (blue circles) and their IDs (black and blue colors correspond to roads and endpoints, respectively). (**b**) Connectivity matrix of the road network shown in Figure 1a.  
Figure 2: Framework for sketched road matching.  
2. The betweenness centrality (\(BC\)) is a measure of the frequency at which a certain road is passed in all the shortest paths of a given location. A higher frequency indicates a greater connectivity of a road. In the proposed approach, \(BC\) is determined by calculating the shortest path from one endpoint of a certain road to the endpoints of all the other roads and considering the occurrence frequency of a road in all the shortest paths as the \(BC\) in that road in a given location. According to Figure 1b, the occurrence frequencies for each road that appeared in all the shortest paths are 4 (R0\({}^{\prime}\)), 4 (R1\({}^{\prime}\)), 6 (R2\({}^{\prime}\)), and 4 (R3\({}^{\prime}\)). This demonstrates that R2\({}^{\prime}\) is more important than the other roads in this location, in terms of the \(BC\).
3. The closeness centrality (\(CC\)), in graph theory, is based on the degree to which a point is close to all the other points. In terms of roads, the \(CC\) indicates the shortest distance from a given road to all the other roads. Because the objective of this study is to determine the main roads in a given location, this factor is not calculated when extracting the main roads.  
Specifically, the proposed approach adopts the \(DC\) and \(BC\) to extract the main roads from a sketch map. Roads with higher values of \(DC\) and \(BC\) can be considered as the main roads in a location. For example, according to the above analysis, R2\({}^{\prime}\) is a main road in the considered location, as it corresponds to the highest \(DC\) and \(BC\) values.  
Figure 3 shows a road from a sketch (represented by R0) and the corresponding road from OpenStreetMap (OSM, OpenStreetMap: [[https://www.openstreetmap.org/](https://www.openstreetmap.org/)]([https://www.openstreetmap.org/](https://www.openstreetmap.org/))). Note that, OSM is a map of the world, and the roads in it are models of real-world roads.  
Certain roads extracted from OSM (represented by R1, R2, R3, R4, and R5 in Figure 4) were extracted for further calculation and comparison, as discussed in the subsequent sections.