An ANNs-Based Method for Automated Labelling of Schematic Metro Maps

Abstract

Schematic maps are popular for representing transport networks. In the last two decades, some researchers have been working toward automated generation of network layouts (i.e., the network geometry of schematic maps), while automated labelling of schematic maps is not well considered. The descriptive-statistics-based labelling method, which models the labelling space by defining various station-based line relations in advance, has been specially developed for schematic maps. However, if a certain station-based line relation is not predefined in the database, this method may not be able to infer suitable labelling positions under this relation. It is noted that artificial neural networks (ANNs) have the ability to infer unseen relations. In this study, we aim to develop an ANNs-based method for the labelling of schematic metro maps. Samples are first extracted from representative schematic metro maps, and then they are employed to train and test ANNs models. Five types of attributes (e.g., station-based line relations) are used as inputs, and two types of attributes (i.e., directions and positions of labels) are used as outputs. Experiments show that this ANNs-based method can generate effective and satisfactory labelling results in the testing cases. Such a method has potential to be extended for the labelling of other transport networks.

1. Introduction

Schematic network maps (often simply called schematic maps) are popular for the representation of transport networks (e.g., metro, bus, and high-speed railway networks). Such maps provide linear abstractions of functional networks [1], in which the relationships between the edges (such as topological relationships) are of more consequence than the geographical position, size, or shape [2]. One famous example of schematic maps is the London Underground map designed by Harry Charles Beck in the 1930s, where congested areas are enlarged, and lines are re-orientated along octilinear (i.e., horizontal, vertical, and diagonal) directions with the preservation of topological relationships. Such a design improves the clarity and readability of the map, thus allowing people to quickly and accurately perform route planning and orientation tasks.

Schematic maps are often generated by a computer-aided approach that requires skilled map designers. In the past two decades, some researchers from various disciplines (e.g., cartography and computer science) have been working toward the automated generation of schematic maps. Generally, the automated generation of schematic maps is treated as an optimization problem, and most researchers prefer to optimize network layouts (i.e., network geometry) and name labels separately because optimizing these two aspects simultaneously is still intractable. It is found that automated generation of network layouts is extensively studied [3,4,5,6,7,8,9,10,11], while automated labelling of schematic maps (i.e., the placement of name labels) is not well considered. Although a variety of existing cartographic labelling methods are available (details about these methods are given in Section 2.1), they may not be the most appropriate solutions for the automated labelling of schematic maps. This is because the labelling space of schematic metro maps is strictly constrained by the connecting lines of stations, which is different from the labelling space of other maps. Lan, et al. [12] have modelled the labelling space of schematic maps based on descriptive statistics (DS) and then integrated it into a greedy algorithm. However, this DS-based method has a limitation, i.e., lack of “learn” ability. That is, if a certain station-based line relation (i.e., connection relations between a station and corresponding connecting edges) is not predefined in the database, the DS-based methods may not be able to infer suitable labelling positions under this relation.

Artificial neural networks (ANNs) have the ability to infer unseen relations on unseen data (i.e., the ability of generalization). ANNs have been widely used in spatial data modelling, analysis, and visualization, such as simulation of urban growth [13,14,15,16] and cartographic generalization and mapping [17,18,19,20,21]. It is noticed that station-based line relations of schematic maps are suitable characteristics (often called “features” in machine learning) for modelling input and output attributes of ANNs. In this study, we aim to develop an ANNs-based labelling method for schematic metro maps.

The remainder of this article is organized as follows. Section 2 introduces the existing automated labeling methods and analyzes the artificial neural network techniques applied in spatial sciences. Section 3 introduces the input and output attributes employed in this ANNs-based method. Section 4 presents the training and testing details of using ANNs. In Section 5, experiments are conducted to evaluate this ANNs-based labelling method. Finally, some conclusions are made in Section 6.

2. Automated Labelling of Maps: An Analysis of Existing Methods and a Strategy

2.1. Analysis of Existing Automated Labelling Methods for Maps

Name labels are indispensable elements of maps, and they have great influences on the readability and clarity of maps. According to the shapes of spatial features, name labels can be generally divided into three types, i.e., name labels of point features, name labels of line features, and name labels of area features [22]. We have found that most of the name labels on schematic metro maps are for stations, while only a few are for other features (e.g., background features). In this study, we focus on the name labels of point features (e.g., stations of schematic metro maps). The point feature label placement (PFLP) is a fundamental task in cartography. Generally, two types of automated methods for the labelling of point features on schematic maps are available. One is the traditional point feature label placement (PFLP) method for general reference maps, and the other is the labelling method for schematic network maps.

Since Yoeli proposed the first automated cartographic labelling method [23], a variety of PFLP methods have been developed, such as those based on fixed-position models [24,25,26,27,28,29] and slider models [30,31,32,33,34,35,36]. However, these PFLP methods are not intended for schematic maps. That is, these PFLP methods may not be the most appropriate solutions for schematic metro maps. This is because the requirement of labelling for schematic maps is different from other maps. An example has been given to illustrate this problem. On the schematic metro map (see Figure 1a), the connecting lines of stations are re-orientated into horizontal, vertical, and diagonal directions. For those labels belonging to the same line, they are placed at the same side as much as possible. By contrast, the lines of the navigation map with undistorted lines are zigzag and of many directions (see Figure 1b). The directions of name labels on such maps are diverse, and the labels of the same line are not placed at the same side. From this example, it is noticed that the regularized station-based line relations (i.e., those between stations and the connecting edges) are important characteristics for the labelling of schematic maps.

Despite the PFLP methods, some automated labelling for schematic maps has been developed. The mixed-integer programming (MIP) methods [37,38] optimized network layouts and name labels simultaneously. Such methods require a large number of constraints. As a result, it is time-consuming to find the optimal solution. The multiple-criteria optimization method [39], the graph cuts method [40], and the flow-network-based labelling method [41] are essentially based on fixed-position models where some predefined positions are employed as the candidate positions for labels. However, these predefined positions do not integrate the various station-based line relations of schematic maps. The descriptive-statistics-based method [12] models some station-based line relations and acquires preference of the candidate positions in these station-based line relations from the existing representative maps. However, if a certain station-based line relation is not predefined in the database, this descriptive-statistics-based method is not able to infer suitable labelling positions under this relation.

2.2. A Strategy Based on Artificial Neural Networks

Artificial neural networks (ANNs) have the ability to infer unseen relations on unseen data (i.e., the ability of generalization). Nowadays, ANNs have been widely used in spatial science. In remote sensing, ANNs are useful for image classification and segmentation [42,43], image registration and matching [44,45], image fusion [46,47], and image reconstruction [48,49]. In geographical information science, ANNs have been applied in simulation of urban growth [13,14,15,16], spatial interpolation [50,51,52,53], spatial clustering [54,55], and spatial regression and prediction [56,57,58]. In cartography, ANNs have potential to improve map generalization [17,59,60,61], generate map production [62,63], optimize map design [64], and detect map objects [20,21].

The station-based line relations on schematic metro maps are suitable characteristics for modelling inputs and outputs of samples in ANNs. ANNs may be a suitable technique for the automated labelling of schematic maps. Based on ANNs, a new strategy for automated labelling is proposed:

• The samples of name label placement are extracted from existing schematic maps;
• The acquired samples are used to train and test artificial neural networks for automated labelling.

The whole process of using ANNs for automated labelling of schematic maps is summarized in Figure 2.

3. Models, Input, and Output of ANNs for Automated Labelling

3.1. Basic Models and Parameters of ANNs

In this study, automated labelling of schematic network maps is treated as a supervised learning task (surrounding information around stations as inputs and the attributes of name labels as outputs). Multilayer feedforward (MLF) neural networks are popular neural networks for supervised learning tasks [65]. MLF neural networks have the advantages of being very robust, non-linear, and having input-output mapping.

After determining the ANNs model, two questions arise: “how many neurons in the hidden layers should I choose?” and “how many hidden layers should I choose?”. Many researchers use a “trial-by-error” method to adjust such a number dynamically [66]. That is, neural networks with different numbers of hidden neurons are trained first, and an evaluation is made in terms of the generalization error before they are finally selected. It was also reported that an MLF neural network with one hidden layer can approximate continuous functions with arbitrary accuracy if the number of neurons in the hidden layer is adequate [67,68,69]. In terms of activation functions, non-linear ones are preferred. The ReLU is computationally efficient and non-linear, and this activation function is used in this study. The neural network diagram of the ANNs model that we used in this study is shown below in Figure 3.

3.2. Input Attributes for ANNs

• Station-Based Line Relations

On schematic metro maps, each name label is associated with an independent station. The most distinguishing characteristics of placing such name labels are the station-based line relations between stations and the connecting lines (or edges). Under the octilinear design of lines, edges can be orientated into eight directions (i.e., two horizontal, two vertical, and four diagonal directions). According to the combinations in mathematics, there are a total of 255 types of station-based line relations under the octilinear design:

$${\mathrm{C}}_8^1+{\mathrm{C}}_8^2+{\mathrm{C}}_8^3+{\mathrm{C}}_8^4+{\mathrm{C}}_8^5+{\mathrm{C}}_8^6+{\mathrm{C}}_8^7+{\mathrm{C}}_8^8=255$$

(1)

The frequencies of these 255 types of station-based line relations have been counted based on the representative schematic metro maps, and some commonly used station-based line relations are presented in Figure 4a. For a given station-based line relation, eight variables are required to represent eight directions (see Figure 4b). In this study, eight non-negative decimal variables (i.e., $x_1$, $x_2$, $x_3$, $x_4$, $x_5$, $x_6$, $x_{7,}$ and $x_8$) are employed to distinguish these station-based line relations. An example is given to explain such quantitative relations (see Figure 4c).

• Connection relations between adjacent stations and edges

On schematic metro maps, each station is connected with at least one other station. Because of this, the labelling space of a given station is also restricted by the adjacent stations. For a given station, there are eight adjacent stations at most (see Figure 5a). Each adjacent station has eight connecting edges at most. Therefore, we need to employ 64 non-negative decimal variables (i.e., $x_9$, $x_{10}$, …, and $x_{72}$) to quantitatively describe the connection relations between eight adjacent stations and their corresponding edges. In Figure 5b, an example has been given to illustrate the quantitative representation of such connection relations.

• Lengths of name labels

Name labels are composed of language characters. Generally, on a schematic metro map, the size of language characters is the same. One non-negative decimal variable (i.e., $x_{73}$) is given to store the lengths of name labels. In this study, the length of a name label is calculated as follows:

$$x_{73}=N\times L$$

(2)

where $N$ refers to the number of language characters and $L$ refers to the length of language character. Some examples of name labels with different lengths have been given in Figure 6.

• Directions of operation lines

An operation line (or route) is made up of stations and edges when a train travels from a starting station to an ending station. On schematic metro maps, name labels for stations of the same operation line are usually placed at the same side as far as possible to improve the aesthetics. This inspires us to employ variables to indicate “the directions of operation lines”. The operation directions are classified into five types (i.e., horizontal, vertical, left diagonal, right diagonal, and hybrid). Correspondingly, five binary variables (i.e., $x_{74}$, $x_{75}$, $x_{76}$, $x_{77,}$ and $x_{78}$) are then created to represent these directions. Some examples have been given to illustrate the directions of operation lines (see Figure 7).

• Coordinates of points

The essential attribute of a station is its coordinates. By modelling the coordinates of stations into input attributes, the spatial relativity among stations is stored, which is helpful to improve the inference ability of ANNs. Therefore, it is natural to use coordinates of stations as input attributes of samples. More precisely, two decimal variables ($x_{79}$ and $x_{80}$) are created to represent the coordinates of stations.

3.3. Output Attributes for ANNs

Two attributes of name labels are employed to model the outputs of ANNs. One is the direction of name labels. We have observed that the name labels on the representative schematic metro maps are at horizontal or vertical directions. A positive integer variable (i.e., $y_1$) is thus employed to represent the directions of name labels. The other attribute is the position of name labels. All the potential positions under different directions are predefined (see Figure 8). A positive integer variable (i.e., $y_2$) is employed to represent these potential positions.

4. Training and Testing ANNs Models for Automated Labelling

4.1. Training and Testing Dataset

An increasing number of cities in the world have constructed metro operation systems, and a large number of existing schematic metro maps are available. Some maps may use octilinear and non-overlap label design, while others may use curved and overlap label design. To avoid the effects of design differences, we only use those official schematic maps under octilinear and non-overlap label design. More precisely, 15 representative schematic metro maps from different cities in the world (i.e., London, New York, Madrid, Singapore, Chengdu, Guangzhou, Hong Kong, Nanjing, Shenzhen, Suzhou, Tianjin, Wuhan, Beijing, Xiamen, and Chongqing) are employed to acquire samples for ANNs (see Figure 9). A total of 3050 samples have been collected from these maps.

These samples are divided into two types: training samples and testing samples. To avoid overfitting, the samples used as training samples cannot then be used as testing samples. Finally, 2491 samples from London, New York, Madrid, Suzhou, Nanjing, Guangzhou, Chengdu, Wuhan, and Shenzhen are used as training samples, while 559 samples from Beijing, Tianjin, and Hong Kong are used as testing samples.

4.2. Implementation of the ANNs-Based Method for Automated Labelling

The whole process of using the ANNs-based method for the automated labelling of schematic network maps is given in Figure 10. Five key stages are identified: preprocessing of the original data, constructing the ANNs model, training the ANNs, testing the ANNs, and eliminating overlaps.

• Preprocessing the original data

The original digital schematic network maps are collected from the internet in the form of pictures. To improve the efficiency of acquiring the dataset, these pictures are vectorized by ArcGIS software to “shapefile” format. It should be noted that map projection coordinate systems are not given on these schematic network maps. That is, all vectorized data are at the default coordinate systems. When we put two digital schematic maps into one spatial coordinate system, the maps are of different sizes. Therefore, it is necessary to adjust the size of the employed schematic maps to make sure they have similar size of name labels (i.e., the same size of language characters in name labels). The lengths of the characters used on these schematic maps are used as benchmarks to guide the “zoom in” or “zoom out” function of these vectorized network layouts. That is, the side lengths of the minimum bounding rectangle (MBR) of the characters on different schematic network maps should be equal under the unknown coordinate system in ArcGIS. This is achieved by an operation in which all coordinates of the points (i.e., $x^{\prime }$ and $y^{\prime }$) on a schematic network map are divided by the length of the MBR of a character (i.e., $l_c$).

• Constructing the ANNs model using Python and PyTorch

In the most recent ten years, Python has become the most popular programming language for AI because it has the advantages of a great library ecosystem, low entry barrier, platform independence, and good visualization options [70]. “PyTorch” is an open-source machine learning library developed by the Facebook AI Research lab. In this study, we used “Spyder” (a free and open-source environment) as the integrated development environment (IDE) and constructed the ANNs model using “PyTorch” and other necessary libraries.

• Training and testing the ANNs model

Before starting the training and testing process, we need to set the initial values of parameters and hyperparameters. Usually, the parameters (i.e., weights and bias) of the ANNs model are randomly initialized and dynamically optimized in the training process. The hyperparameters (e.g., learning rate and batch size) are set manually. The final values of the hyperparameters used in the ANNs model for the final placement of the name labels are listed in

Table 1. Final values of hyperparameters used in the ANNs model.

Hyperparameters	Value	Explanation
Learning rate	0.005	Controls how quickly the ANNs model is adapted to the problem
Batch size	5	The number of training examples utilized in one iteration by gradient descent
Momentum	0.9	Helpful to jump from a local minimum
Step size	7	Affects the change of learning rate
gamma	0.1
Number of epochs	50	The number of times all of the training data are used once to update the weights

.

It should be noted that the traditional measure “accuracy” is not suitable for evaluating the testing results in this study because the output attributes of training samples with the same input attributes may be different. This is because the designers of schematic network maps may have their own preferences.

• Eliminate overlaps

Avoiding overlaps among labels, stations, and edges has not been explicitly modelled into inputs and outputs of ANNs, which leads to the appearance of overlaps in the resultant labels, especially when the labelling space is not adequate. To improve the quality of resultant labels, it is necessary to eliminate overlaps as far as possible. Based on the predefined positions of labels shown in Section 3.3, the labels can be further optimized by the following progressive strategy:

Step 1: sort the acquired name labels by their feature identifiers (i.e., FIDs);

Step 2: obtain a name label from the sorted name labels by FIDs and put it onto the schematic network;

Step 3: if this label has overlap with other labels, it should be moved to the best non-overlapped position according to the predefined positions of labels;

Step 4: go back to Step 2 until all the name labels have been placed.

5. Experimental Evaluation

5.1. Experimental Design

• Experimental data and benchmark

“Maplex” is a label engine in ArcGIS, and it has been widely employed to place name labels of spatial features on general reference maps. The descriptive-statistics-based labelling method, which models the labelling space by defining various station-based line relations in advance, is specially developed for the labelling of schematic maps (Lan et al. 2020). In this study, name labels placed by these two methods are used as the benchmarks. More precisely, the name labels of Beijing, Tianjin, and Hong Kong metro networks (with 316, 150, and 93 stations, respectively) placed by the ANNs-based method (see Figure 11c, Figure 12c and Figure 13c) will be compared with those placed by the Maplex method (see Figure 11a, Figure 12a and Figure 13a) and the descriptive-statistics-based labelling method (see Figure 11b, Figure 12b and Figure 13b).

• Measures

The placed name labels are measured from two aspects. The first is the number of overlaps among labels, stations, and edges. It is noticed that counting the number of overlaps has been regarded as a fundamental performance to evaluate labelling methods [71]. In this study, we have used two overlap-based measures. One is the total number of overlaps at the map level, and the other is the number of overlaps in the name labels whose station-based line relations are not predefined in the database.

The second aspect is the satisfaction level (an important part of usability). In this study, satisfaction level is measured by a psychological test through questionnaire. Five different levels (i.e., very dissatisfied, dissatisfied, neutral, satisfied, and very satisfied of 1, 2, 3, 4, and 5 marks, respectively) have been designed, and participants in the questionnaire should give marks to the placed name labels.

5.2. Experimental Results

The statistical results for the number of overlaps are shown in

Table 2. Statistical results of name labels placed by three automated labelling methods.

Metro Name	Number of Stations	Number of Stations Whose Station-Based Line Relations Are Not Predefined	Labelling Method	Total Number of Overlaps	Number of Overlaps in the Stations Whose Station-Based Line Relations Are Not Predefined
Beijing	316	7	Maplex	67	4
			DS	13	2
			ANNs	8	0
Tianjin	150	4	Maplex	20	1
			DS	4	4
			ANNs	0	0
Hong Kong	93	1	Maplex	10	0
			DS	0	0
			ANNs	0	0

Note: DS refers to the descriptive-statistics-based labelling method.

. It is found that the name labels placed by Maplex have the largest number of overlaps in all three metro networks (i.e., 67, 20, and 10 in Beijing, Tianjin, and Hong Kong metro, respectively), while those placed by the ANNs-based method have the smallest number of overlaps (i.e., 8, 0, and 0 in Beijing, Tianjin, and Hong Kong metro, respectively). The Maplex method has employed constraints to avoid overlap among name labels, while avoiding overlap between name labels and edges and between name labels and stations is not well considered. By contrast, the progressive strategy for avoiding overlap in the ANNs-based method considers all types of overlap. From the result for the number of overlaps in the stations whose station-based line relations are not predefined, it is found that the ANNs-based method also performs better (i.e., with the smallest number of overlaps in the stations whose station-based line relations are not predefined).

In terms of satisfaction level, a psychological test has been conducted through an online questionnaire platform named “Wenjuanxing”. Participants can join this test through computers or smart phones. We have collected 217 effective records from 217 participants (i.e., 127 males and 90 females). In total, 88% of participants (i.e., 192 participants) are between 18 and 40 years old, and 29% of participants (i.e., 63 participants) have ever learned map design. The experimental result of this test has been given in

Table 3. Average scores and paired t-test results in the questionnaire.

Metro	Questionnaire		Paired t-Test
	Labelling Method	Average Score	Comparison Objects	p-Value	The Difference Is Significant?
Beijing	Maplex	3.65	ANNs vs. Maplex	0.008	Yes
	DS	3.71	ANNs vs. DS	0.075	No
	ANNs	3.84	Maplex vs. DS	0.519	No
Tianjin	Maplex	3.68	ANNs vs. Maplex	0.001	Yes
	DS	3.76	ANNs vs. DS	0.021	Yes
	ANNs	3.94	Maplex vs. DS	0.353	No
Hong Kong	Maplex	3.84	ANNs vs. Maplex	0.145	No
	DS	3.84	ANNs vs. DS	0.139	No
	ANNs	3.95	Maplex vs. DS	1	No

Note: significance level is set as 0.05.

. It is found that the average scores of the name labels placed by the ANNs-based method are all larger than those placed by the Maplex method and the descriptive-statistics-based method. Significance tests (i.e., paired t-tests) have been employed to indicate whether average scores of the satisfaction level in the name labels by the ANNs-based method are significantly larger than those by the Maplex method and the descriptive-statistics-based method. The results of paired t-tests indicate that the differences are significant in Beijing and Tianjin metro but not significant in Hong Kong metro. This is because the labelling space of Hong Kong metro network is adequate, and all three labelling methods can place high-quality labels for Hong Kong metro network.

6. Conclusions

In this study, an ANNs-based labelling method has been proposed for schematic metro maps. Samples are first extracted from representative schematic maps, and then they are employed to train and test ANNs models. More precisely, five different types of attributes (i.e., station-based line relations, connection relations between adjacent stations and edges, label length, operation line directions, and station coordinates) are employed to model inputs of samples, while directions and positions of name labels are employed to model outputs of samples. The training and testing samples are collected from 15 representative schematic metro maps in the world. After that, a multilayer feedforward model has been trained and tested with the collected datasets. With the trained model, name labels of stations on schematic maps can be automatically placed.

The proposed ANNs-based labelling method is evaluated from two aspects, i.e., the number of overlaps among labels, edges, and stations and the satisfaction level by questionnaire. Compared with the Maplex method and the descriptive-statistics-based method, it is found that the labelling results by this ANNs-based method are effective and satisfactory. From the above results, it may be concluded that this ANNs-based labelling method has potential to place name labels for schematic metro maps. This ANNs-based labelling method can be extended to place name labels of other spatial (e.g., bus and high-speed railway networks) and non-spatial networks (e.g., power transmission networks and knowledge graphs) if enough samples are available.

There are some limitations of this ANNs-based labelling method. Firstly, only two directions (i.e., vertical and horizontal) of name labels are modelled in this ANNs-based method. In some cases, name labels are better placed at diagonal directions. In the future, more label directions should be modelled and integrated into this ANNs-based method. Secondly, this ANNs-based labelling method is not fully automated. Avoiding overlap between name labels and other features is not explicitly modelled into ANNs, and an extra progressive process of eliminating overlap is required. The effectiveness of using such an eliminating overlap process should be further validated. Thirdly, labelling results of this ANNs-based labelling method greatly depend on the quality of samples. How to select appropriate samples from existing schematic maps needs further exploration.