A Novel Semantic Matching Method for Indoor Trajectory Tracking

Abstract

The rapid development of smartphone sensors has provided rich indoor pedestrian trajectory data for indoor location-based applications. To improve the quality of these collected trajectory data, map matching methods are widely used to correct trajectories. However, these existing matching methods usually cannot achieve satisfactory accuracy and efficiency and have difficulty in exploiting the rich information contained in the obtained trajectory data. In this study, we proposed a novel semantic matching method for indoor pedestrian trajectory tracking. Similar to our previous work, pedestrian dead reckoning (PDR) and human activity recognition (HAR) are used to obtain the raw user trajectory data and the corresponding semantic information involved in the trajectory, respectively. To improve the accuracy and efficiency for user trajectory tracking, a semantic-rich indoor link-node model is then constructed based on the input floor plan, in which navigation-related semantics are extracted and formalized for the following trajectory matching. PDR and HAR are further utilized to segment the trajectory and infer the semantics (e.g., “Turn left”, “Turn right”, and “Go straight”). Finally, the inferred semantic information is matched with the semantic-rich indoor link-node model to derive the correct user trajectory. To accelerate the matching process, the semantics inferred from the trajectory are also assigned weights according to their relative importance. The experiments confirm that the proposed method achieves accurate trajectory tracking results while guaranteeing a high matching efficiency. In addition, the resulting semantic information has great application potential in further indoor location-based services.

1. Introduction

Research into indoor location-based services has attracted a great deal of attention in recent years. Many of these services have been developed based on trajectory data [1,2,3,4], such as people’s movement patterns, location prediction, and route planning. Compared to other methods of acquiring indoor trajectories, built-in smartphone sensors provide a more convenient and less expensive method of collecting indoor trajectory data [5]. However, the trajectory data collected directly from the smartphone are prone to be inaccurate and incomplete, which prevents their immediate use and the analysis of the trajectory data. Thus, more research on indoor trajectory tracking and correction techniques is required.

Map matching has been widely accepted as a common approach for trajectory tracking and correction. By using the road network information as the constraint for vehicles, considerable achievements have been made in the field of outdoor vehicle navigation systems [6,7,8]. Compared with the outdoors, the constraints of the indoor environment are much more complicated. Indoor navigation systems not only need to consider a variety of special elements (e.g., doors, corridors, and stairs) but also need to take more flexible direction information into account. Many indoor matching techniques [9,10,11,12] have been proposed, including approaches based on particle filter, hidden Markov models (HMMs), and geometric similarity. However, the applicability and accuracy of these methods are still limited. The development of a robust map matching approach for user trajectory tracking that takes into account both accuracy and efficiency remains an open challenge.

Compared with the outdoor environment, indoor space provides richer constraint information. Indoor space consists of a variety of indoor elements, such as rooms, doors, stairs, walls, corridors, floors, etc. The geometric constraints between these indoor elements are far more complicated than outdoor European space and network space. In addition, topological constraints, such as adjacency, association, and inclusion relationships are more common indoors. Based on this, we conclude that the semantic information obtained from the indoor space is more abundant. In general, making use of this information can effectively improve the efficiency of indoor trajectory tracking.

In this paper, we proposed a novel semantic matching method for indoor trajectory tracking. The proposed method is actually an extension of our previous work [5], which further improves the efficiency and accuracy for user trajectory tracking by combining a semantic-rich link-node model derived from an indoor plan with the semantic information extracted from the trajectory. In contrast to the conventional link-node model, which only considers geometric and topological information, the proposed model further fuses the activity semantics (e.g., “Turn left”, “Turn right”, “Go upstairs”, “Go downstairs”, and “Go into a room”) and direction information (e.g., “East”, “South”, “West”, and “North”) obtained from the floor plan. With the construction of the semantic-rich link-node model, the key to implementing semantic matching lies in the acquisition and recognition of the user’s trajectory data. Pedestrian dead reckoning (PDR), which uses data from built-in sensors in the smartphone to track pedestrians, is a suitable way to acquire trajectory data. In addition, human activity recognition (HAR), which recognizes user activity by sensor data, can be utilized to obtain semantic information about user trajectory.

The remainder of this paper is structured as follows. Section 2 briefly reviews the previous work. Section 3 introduces the link-node model. Section 4 and Section 5 present the semantics extraction steps and the semantic matching process, respectively. Section 6 analyzes and discusses the experimental results. Finally, Section 7 present conclusions and recommendations for future work.

2. Related Work

Map matching is the process of matching trajectory data with the map network, and it can be used to correct the error of the moving object’s trajectory. The information from the map is of great importance to the map matching process, and this aspect has been studied by many researchers. Geometric information such as Euclidean space and geometric shape is the simplest and most commonly used constraint. The main research in this area has taken into consideration road networks [13] and section shapes [14]. In particular, the magnetic field information [15] and direction information [16] of the indoor building are analyzed and extracted to reduce the PDR error and match the pedestrian trajectory. Moreover, topology information, including the relationship between road networks, was considered in [17]. In addition, probability information [7] has also been used when there is uncertainty in the network data. To obtain richer and more comprehensive information, the above information is usually utilized in combination [18].

In addition to map information, semantic information has attracted a great deal of attention from researchers. In many cases, semantic information can be used to provide applications that are more meaningful and convenient. To achieve this purpose, Liu et al. [19] automatically derived semantic locations from the user trajectory and then used them to infer the activities contained in the trajectory. Similarly, Brakatsoulas et al. [20] constructed a semantic-rich, moving-object model, which was useful for further analysis and data extraction. Spaccapietra et al. [21] proposed a fully conceptual approach to modeling the moving objects that supported trajectory semantics. In addition, semantic information can also be used for trajectory similarity analysis and location prediction. In [22], the semantic meaning of the position where the user stayed for a short time was mined to compare the similarity of people’s trajectories. In [23], the longest common subsequence (LCSS) algorithm was used to determine the semantic similarity. A follow-on study [24] then considered both geometric similarity and semantic similarity. More semantic information like motion state and mobility context in [25] can also be of great value to the indoor localization process. Although the semantics of the trajectory have been used in recent studies, the semantic information in the map has not been fully utilized, and how to obtain useful semantic information from the map is worth exploring.

The map matching process can be implemented by a variety of algorithms, ranging from simple search to sophisticated mathematical tools. The main purpose of these algorithms is to improve the accuracy and efficiency of the matching process. According to the global optimal idea (i.e., the cumulative error is minimal), methods based on the HMM [26] or interactive voting [27] can be used to improve the accuracy of the map matching. On the other hand, the matching efficiency can also be optimized by incremental calculations [8,14], but this will reduce the accuracy. In addition, some complex machine learning methods and data mining methods (e.g., the Kalman filter [28], fuzzy theory [29], and artificial neural networks [30]) can also be utilized to address the problem of map matching. Although these algorithms can achieve a high precision in a particular situation, they require a large quantity of data to be trained. In general, an efficient and highly accurate matching method still needs to be further studied.

In an indoor setting, the map matching process involves matching the pedestrian trajectory to the floor plan. Although the indoor environment is more restrictive, it also brings more useful information. For example, walls and corridors can provide geometric information to limit the user’s movement [9], and doors, stairs, and other indoor elements are key information for map matching [12]. Walder et al. [31] described in detail how these elements were used to correct position. These features can also be used as landmarks, for example, Wang et al. [32] used mobile devices to sense indoor landmarks, which can be used to recalibrate pedestrian’s indoor location. Compared to the outdoor environment, indoor map matching algorithms are more complex. Particle filter-based approaches have been commonly used to match indoor maps. In [33], the user’s step length and heading direction were integrated with the floor map by a particle filter algorithm. In further research [34,35], Wi-Fi, map information, and the inertial data were combined by a particle filter to achieve pedestrian tracking in an indoor environment. However, approaches based on particle filters require significant computational resources. To reduce computational complexity, Xiao et al. [36] used a conditional random field model, which combines maps and state observations, to track indoor pedestrian.

In our previous work [5], we combined PDR, HAR and landmarks to obtain semantic-rich indoor trajectory data. However, the previous method uses geometric distance to match the landmark and correct the trajectory, which is still undesirable in both computation efficiency and error elimination for applications. In order to overcome these problems, a new semantic matching method is proposed, and some optimization measures are used in the matching process. In detail, a link-node model is first abstracted from the floor plan, and rich navigation-related semantics are incorporated into the model. The semantics extracted from the trajectory are then used to match the nodes in the link-node model. The matching method can not only efficiently track pedestrian trajectories, but it can also accurately describe them.

3. Semantic-Rich Indoor Link-Node Model

The link-node model [37,38] has a significant advantage in the expression of indoor spaces. Since special attribute points and points of interest (POIs) can be easily abstracted from the map, and people usually walk along the center line between two nodes in a narrow space, a link-node model is constructed, as shown in Figure 1. The nodes are normally door points, stair points, and turning points, and links are composed of starting nodes and ending nodes. To simplify the proposed model and increase its computational efficiency, some nodes with the same semantics are abstracted as a flag. ${\mathrm{A}}_{\mathrm{S}}$ indicates the adjacent doors ($\mathrm{A}5$–$\mathrm{A}9$) on the south side of the corridor, ${\mathrm{A}}_{\mathrm{N}}$ represents doors ($\mathrm{A}0$–$\mathrm{A}4$) on the north side of the corridor, ${\mathrm{A}}_{\mathrm{E}}$ and ${\mathrm{A}}_{\mathrm{W}}$ represent the east doors ($\mathrm{A}13$–$\mathrm{A}16$) and the west doors ($\mathrm{A}17$–$\mathrm{A}18$), respectively. Similarly, ${\mathrm{B}}_{\mathrm{E}}$, ${\mathrm{B}}_{\mathrm{E}}$, ${\mathrm{B}}_{\mathrm{E}}$, and ${\mathrm{B}}_{\mathrm{E}}$ indicate the corresponding nodes on the second floor. ${\mathrm{R}}_{\mathrm{S}}$, ${\mathrm{R}}_{\mathrm{N}}$, ${\mathrm{T}}_{\mathrm{S}}$, and ${\mathrm{T}}_{\mathrm{N}}$ represent the turning nodes in the corridors.

Semantic information can not only express the attributes of a node but can also describe the pedestrian movement behavior of the corresponding links. These semantics are of great value for the description of the indoor location and the pedestrian trajectory tracking. It therefore makes a lot of sense to integrate semantics into the model and to use this for pedestrian trajectory matching. In order to correspond to the pedestrian’s indoor navigation elements, attributes such as “Turn”, “Stair”, and “Door” are assigned to each node, and semantics such as “Turn right”, “Turn left”, and “Go straight” are added to each link. When the straight line distance is long enough (>5 m), the “Go straight” link is added; otherwise, the semantics are left empty ($\varnothing$). In addition to the basic semantic information, distance and direction information (e.g., “North”, “East”, “South”, and “West”) is also added to further enrich the proposed model.

Figure 2 describes the semantic-rich link-node model, in which a semantic node is determined by five basic information elements. The Id is the identifier of a node. An attribute is a set of stairs, a turn, or a door. Adjacent links present the distance, direction, and semantics between the current node and the next nodes. Direction information indicates the change of direction when the user passes through the node. Similarly, the semantic description represents the detected semantic information in this process. Figure 3 shows the semantic-rich information of node $\mathrm{T}1$ as an example.

4. Trajectory Information Collection

4.1. PDR-Based Information Acquisition

The popularity and ease of use of smartphones turn them into a perfect platform for trajectory data collection [39]. Using built-in smartphone sensors to obtain indoor pedestrian trajectories is a less expensive and more convenient approach compared to the methods relying on additional infrastructure [40]. Smartphone-based pedestrian dead reckoning (SmartPDR) [41] has the advantage of providing a continuous trajectory across the entirety of an indoor space. PDR uses built-in smartphone inertial sensors, including the accelerometer, gyroscope and magnetometer, to track the user’s trajectory. The trajectory’s distance and directional information can be obtained at the same time. Since Smartphone-based PDR uses built-in smartphone inertial sensors to track the user’s trajectory, random hand movement may cause data to be unavailable. Thus, similar to most indoor localization methods based on smartphone inertial sensors, we assume that the user is holding the phone in a horizontal posture, with the orientation of the phone toward the user’s walking direction.

As we have detailed in our previous work [5], the main processes of the PDR include step detection, step length estimation and direction estimation. Peak step detection and zero-crossing step detection algorithms are combined to provide accurate step detection results. An example is shown in Figure 4; the detected peaks are marked with red dots, and the beginning or end points of steps are marked with blue dots. The step length is estimated by a nonlinear model, and the walking direction is determined by a smartphone’s gyroscope and magnetometer. After the step length and direction information are obtained, the pedestrian trajectory is tracked as shown in Figure 5, where ${\mathrm{S}}_0$ indicates the starting point, ${\mathrm{l}}_1$ and ${\mathsf{\theta }}_1$ represent the step length and angle of the first step, respectively. The locations of the first and second steps (${\mathrm{S}}_1$ and ${\mathrm{S}}_2$) are thus inferred. For easier understanding, direction information includes “North” (0 ≤ θ < 30, 330 < θ < 360), “East” (60 ≤ θ < 120), “South” (150 ≤ θ < 210), and “West” (240 ≤ θ < 300) is used to describe the user’s walking direction. In the experiment, the accelerometer and magnetometer are combined to perform directional calculations. According to the calculation function provided by Android, the azimuth of the phone can be obtained, and the average azimuth reading of the first second is used to determine the user’s initial direction.

4.2. HAR-Based Information Recognition

In order to obtain the semantic information in the pedestrian trajectory, HAR is used to recognize the user’s mobile activity. HAR can not only use the synthetic three-axis accelerometer data in PDR but can also modify the PDR parameters according to different activities (walking, going upstairs or downstairs).

HAR’s main process includes segmentation, feature extraction, and classification; we have detailed these processes in our previous work [5]. Different from our previous k-nearest neighbor (KNN) classification method, the decision tree (DT) algorithm [42] is used to classify four walking behaviors (standing, going up or down stairs, walking, and opening a door) because of its simplicity and efficiency. In the classification process, the barometer and magnetometer data can be used to further improve the accuracy of the activity classification. Changes in barometer readings can effectively identify going up or down stairs, and the pattern change characteristics of the magnetometer can also help identify the door-opening activities. Figure 6 shows the proposed approach. The top level identifies the door-opening activity based on its unique magnetometer pattern. For example, when a pedestrian uses his right hand to open a door, where the door handle is to the left, his body turns left at an angle and is then restored in the process of opening the door. When the user opens a door (doors are assumed to be closed in the experiment), the magnetometer readings change significantly within a short time and then quickly return to their previous readings. Although opening a door in different ways will produce different magnetometer readings, we are still able to determine the door-opening activity by the changing pattern of magnetometer readings over a period of time. Using this observation, door-opening activities can be identified effectively. Then, we set two different thresholds based on the standard deviation (Std) of the acceleration readings (Acc.) to determine the user’s activity. A small threshold value is used to distinguish between standing and the other two activities (walking and going up (or down) stairs). These two activities are further determined by a large threshold value. Finally, barometer readings (baro) are used to distinguish between going upstairs and going downstairs.

5. Semantic Matching

5.1. Trajectory Segmentation

A trajectory can be denoted by a series of special nodes and segments. The special nodes include turning points, stairs and door points, while the trajectory between them is a special segment. Thus, a trajectory can be expressed as follows,

$$T=\left(se{g}_{s-1}, n_1,se{g}_{1-2}, n_2, \dots n_m,se{g}_{m-e}\right),$$

(1)

where $T$ represents the trajectory, $n$ indicates the special node in the trajectory. $seg$ denotes the trajectory segment between two special nodes. Specially, $se{g}_{s-1}$ and $se{g}_{m-e}$ represent the starting and ending segment of a trajectory, respectively. Similarly, the corresponding semantics are expressed as follows:

$$S\left[T\right]=\left\{S\left[se{g}_{s-1}\right],S\left[n_1\right],S\left[se{g}_{1-2}\right],S\left[n_2\right], \dots S\left[n_m\right],S\left[se{g}_{m-e}\right]\right\}.$$

(2)

The special nodes include door nodes, stair nodes, and turning nodes, which are detected by HAR and the direction sensors. In addition, the HAR method can be used to obtain the user’s activity information in a trajectory. For example, a trajectory generated by PDR is shown in Figure 7. The activity information ($\mathrm{A}$) of the trajectory can be expressed as follows:

$$\mathrm{A}=\left\{\mathrm{Standing},\mathrm{Walking},\mathrm{Opening}\mathrm{a}\mathrm{door},\mathrm{Walking},\mathrm{Opening}\mathrm{a}\mathrm{door},\mathrm{Standing}\right\}.$$

(3)

To identify the turn nodes, the gyroscope and magnetometer are used to provide angle changes and direction information, respectively. Due to the instability of the sensors and the movement state, only large directional changes are detected. The direction information ($\mathrm{U}$) of the trajectory in Figure 7 is obtained as follows:

$$\begin{gathered} \mathrm{U}=\{\mathrm{Turn}\mathrm{left}\left(\mathrm{South}-\mathrm{East}\right),\mathrm{Turn}\mathrm{left}\left(\mathrm{East}-\mathrm{North}\right),\mathrm{Turn}\mathrm{left}\left(\mathrm{North}-\mathrm{West}\right), \\ \mathrm{Turn}\mathrm{right}\left(\mathrm{West}-\mathrm{North}\right),\mathrm{Turn}\mathrm{right}\left(\mathrm{North}-\mathrm{East}\right),\mathrm{Turn}\mathrm{left}\left(\mathrm{East}-\mathrm{North}\right), \\ \mathrm{Turn}\mathrm{left}\left(\mathrm{North}-\mathrm{West}\right)\}. \end{gathered}$$

(4)

According to the above information, special nodes in the trajectory can be acquired. In detail, door nodes and stair nodes can be extracted from $\mathrm{A}$, and the turning nodes can be obtained from $\mathrm{U}$. Moreover, the semantic information of the trajectory segments can be extracted from the PDR. Similar to the link-node model, if the distance of the segment is long enough (>5 m), the semantics of “Go straight” are assigned; otherwise, the semantics are left empty ($\varnothing$). Thus, the trajectory semantics $S\left[T_e\right]$ in Figure 7 are obtained as follows:

$$\begin{array}{l}\mathrm{S}\left[T_e\right]=\{\left[“\varnothing ”\left(“\mathrm{South}”\right)\right],\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left[“\mathrm{Opening}\mathrm{a}\mathrm{door}”\left(“\mathrm{South}”\right)\right], \left[“\varnothing ”\left(“\mathrm{South}”\right)\right],[“\mathrm{Turn}\mathrm{left}”(“\mathrm{South}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}-\mathrm{East}”)\left],\left[“\mathrm{Go}\mathrm{straight}”\left(“\mathrm{East}”\right)\right],\right[“\mathrm{Turn}\mathrm{left}”\left(“\mathrm{East}-\mathrm{North}”\right)],\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left[“\mathrm{Go}\mathrm{straight}”\left(“\mathrm{North}”\right)\right],\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left[“\mathrm{Turn}\mathrm{left}”\left(“\mathrm{North}-\mathrm{West}”\right)\right],\left[“\varnothing ”\left(“\mathrm{West}”\right)\right],\left[“\mathrm{Turn}\mathrm{right}”\left(“\mathrm{West}-\mathrm{North}”\right)\right],\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left[“\mathrm{Go}\mathrm{straight}”\left(“\mathrm{North}”\right)\right],\left[“\mathrm{Turn}\mathrm{right}”\left(“\mathrm{North}-\mathrm{East}”\right)\right],\left[“\varnothing ”\left(“\mathrm{East}”\right)\right],\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left[“\mathrm{Turn}\mathrm{left}”\left(“\mathrm{East}-\mathrm{North}”\right)\right],\left[“\varnothing ”\left(“\mathrm{North}”\right)\right],\left[“\mathrm{Turn}\mathrm{left}”\left(“\mathrm{North}-\mathrm{West}”\right)\right],\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left[“\mathrm{Go}\mathrm{straight}”\left(“\mathrm{West}”\right)\right],\left[“\mathrm{Opening}\mathrm{a}\mathrm{door}”\left(“\mathrm{West}”\right)\right],\left[“\varnothing ”\left(“\mathrm{West}”\right)\right]\}.\end{array}$$

(5)

5.2. Semantics-Based Trajectory Matching

The core idea of semantics-based trajectory matching is to find the semantic information corresponding to the trajectory in the link-node model. The special nodes and segments in the trajectory correspond to the nodes and links in the model, respectively. Therefore, matching the obtained semantics in the trajectory with the semantics in the model can map the trajectory to the model. However, some nodes and links in the model have the same semantics. Therefore, we need continuous semantics to uniquely determine the trajectory. To perform efficient semantic matching, the semantics of trajectory $T_e$ in the model are graded according to the frequency of occurrence (see

Table 1. Semantic weight in trajectory $T_e$.

Semantic Information	Attributes	Frequency (f1) 1	Frequency (f2)	Weight
“Opening a door” (“South”)	Node	3	3	High
“Turn left” (“South-East”)	Node	3	4	High
“Go straight” (“East”)	Link	6	7	Medium
“Turn left” (“East-North”)	Node	4	6	Medium
“Go straight” (“North”)	Link	8	9	Low
“Turn left” (“North-West”)	Node	4	6	Medium
“Turn right” (“West-North”)	Node	3	5	Medium
“Turn right” (“North-East”)	Node	3	5	Medium
“Go straight” (“West”)	Link	6	8	Medium
“Opening a door” (“West”)	Node	8	7	Medium

¹ Frequency indicates the number of occurrences of the semantics in the first layer model.

).

The first step in semantic matching is selecting the highest-weight semantics in the trajectory to match the proposed model. The adjacent semantics are then matched forward and backward. In the end, the beginning and ending points of the trajectory are decided using the PDR. The matching process for $S\left[T_e\right]$ is shown in Figure 8, and the matching process is shown below.

• Select the highest-weight semantic information (“Opening a door” (“South”)) and match this with the model. There are six nodes ($A_S$, $A_N$, $\mathrm{A}19$, $B_S$, $B_N$, $\mathrm{B}15$) that meet this condition; they are marked in red in Figure 8. We use the serial numbers (1–6) to represent the possible trajectories.
• Match the second semantics (“Turn left” (“South–East”)) in the nodes adjacent to the previous nodes; four nodes ($R_S$, $R_N$, $T_S$, $T_N$) match the semantics. Since the trajectory segments $A_S–R_S$ and $B_S–T_S$ do not satisfy the directional semantics (“South”), the 2nd and 5th trajectories are excluded.
• Match the third semantics (“Go straight” (“East”)); only the 1st and 4th trajectories meet the semantic conditions. Continue to match the semantics; node $\mathrm{S}0$ does not satisfy the sixth semantic (“Turn left” (“North$–$West”)); the trajectory is thus uniquely determined.
• By matching the remaining semantics in turn, the trajectory is presented at the corresponding position in the map.
• Since $B_S$ is used on behalf of the door nodes $\mathrm{B}2$, $\mathrm{B}3$, $\mathrm{B}7$, $\mathrm{B}8$, $\mathrm{B}22$, and $\mathrm{B}23$, we need to use the distance information to exactly match the trajectory. Through the length (10.8 m) of the trajectory segment $\left[se{g}_{U1–U2}\right]$ estimated by the PDR, we can easily determine that node $\mathrm{D}1$ in the trajectory corresponds to node $\mathrm{B}3$ in the proposed model.
• Finally, the start position (S) and end point (E) of the trajectories are also estimated by PDR.

An experiment with longer trajectory has been used to verify the proposed semantic matching method. A user goes from point S to point E; the trajectory estimated by smartphone PDR is shown in Figure 9a. By analyzing the trajectory data, a series of special nodes and their corresponding semantics are acquired. The red and yellow dots represent the door and turn nodes, respectively. The green points indicate the upstairs process. In the semantic matching process, semantics “Go up stairs” as the most important semantics are first matched with the proposed link-node model. Since there is only one staircase in our experimental environment, the user’s upstairs trajectory segment is quickly determined. The remaining trajectory segments are easily matched by adjacent semantics. Similar to the matching process of trajectory $T_e$, distance information is used to determine the specific door nodes. The final result is shown in Figure 9b. It is worth noting that if a door is open, the door node cannot be determined by the magnetometer. In this situation, the trajectory can still be matched by other semantics. By comparing the matched trajectory with the proposed link-node model, we can easily estimate the door nodes in the trajectory. In our experiment, the doors are closed.

6. Discussion

6.1. Localization Error

The start and end positions of a trajectory are used to analyze the location error. If a trajectory is completely matched to the link-node model, the matched trajectory will be very similar to the real trajectory. To better analyze this problem, a number of trajectory matching experiments were carried out. As shown in Figure 10a and Figure 11a, there were 10 trajectories ($T_1–T_{10}$) from the turn node S to each door ($\mathrm{A}0–\mathrm{A}9$) on the first floor. These trajectories were segmented by the turn points ($u_1–u_{10}$) and the door points ($d_1–d_{10}$), which were detected by HAR and the direction sensors. Subsequently, the distance from the starting point to the turning point in the trajectory was used to match it to the corresponding link in the proposed model, and the shortest-distance method was used. The results of the experiments are shown in Figure 10b and Figure 11b, where the blue points are the start and end points of the trajectories, and the yellow dots and the red dots indicate the turn nodes and the door nodes in the link-node model, respectively.

Although PDR has the disadvantage of accumulating error when the trajectory is long, trajectory matching can effectively reduce cumulative error. After trajectory matching, the PDR needs only to estimate the last segments of the user’s trajectories, as shown in Figure 10b and Figure 11b. Therefore, the proposed method can achieve high localization accuracy in our experimental environment. Figure 12 shows the original errors of the end points of the trajectories ($T_1–T_{10}$) and the errors after matching, showing that the average error is reduced from 0.79 m to 0.21 m, which indicates that the proposed method is more stable than using PDR alone.

It is worth noting that if a trajectory is too short, it cannot be uniquely matched. As shown in Figure 13, trajectories $T_a$/$T_b$ and $T_c/T_d$ have exactly the same semantic and distance information, and thus we cannot uniquely determine their location. Nevertheless, we can still narrow the location area where the trajectory may exist. The proposed method could be more suitable for environments with good constraints. In the case of large open spaces with less constraints, we will extract some virtual landmarks from the trajectories for map matching.

In general, although certain special circumstances result in a larger error, the proposed method achieves a good accuracy in most cases.

6.2. Time Complexity

Time complexity is used to evaluate the performance of our algorithm.

Table 2. Semantic matching results.

Trajectory	Trajectory Segment	Semantics	Time Complexity	Number 1
$T_e$	Node 1 (D1)	“Opening a door” (“South”)	O(N)	6
	Node 2 (U1)	“Turn left” (“South–East”)	O(4)	4
	Segment 2 (${\mathit{seg}}_{\mathrm{U}1-\mathrm{U}2}$)	“Go straight” (“East”)	O(4)	2
	Node 3 (U2)	“Turn left” (“East–North”)	O(4)	2
	Segment 3 ($se{g}_{U2-U3}$)	“Go straight” (“North”)	O(4)	2
	Node 4 (U3)	“Turn left” (“North–West”)	O(2)	1
	Node 5 (U4)	“Turn right” (“West–North”)	O(1)	1
	Segment 5 ($se{g}_{U4-U5}$)	“Go straight” (“North”)	O(1)	1
	Node 6 (U5)	“Turn right” (“North–East”)	O(1)	1
	Node 7 (U6)	“Turn left” (“East–North”)	O(2)	1
	Node 8 (U7)	“Turn left” (“North–West”)	O(3)	1
	Segment 8 ($se{g}_{U7-D2}$)	“Go straight” (“West”)	O(1)	1
	Node 9 (D2)	“Opening a door” (“West”)	O(1)	1

¹ The number of trajectories after semantic matching.

shows the time complexity in the trajectory-matching process. In the first semantic matching process, each node must be traversed once; therefore, the time complexity is $\mathrm{O}\left(\mathrm{N}\right)$. After matching the semantics in the proposed semantics-rich link-node model, six nodes satisfy the condition “Opening a door” (“South”). The next semantic matching process only requires the traverse of adjacent semantics nodes or links for the previous nodes that satisfy the conditions. The nodes adjacent to the matched nodes are $R_S$, $R_N$, $T_S$, and $T_N$, so the time complexity is $\mathrm{O}\left(4\right)$. According to the semantic information, the number of trajectories satisfying the condition can be judged, and the remaining matching process follows this method.

It can be seen from the experimental results that the proposed semantic matching method can determine a trajectory quickly and achieve satisfactory efficiency. As we can see from Table 2, the semantic matching process does not need to traverse all the states every time, except for the first semantic match. Compared to some commonly used map matching methods, such as the particle filter-based method [43] and HMM-based method [36], which need to carry out a large number of state calculations, the proposed method uses less computational complexity to achieve trajectory tracking. The elapsed time of the entire trajectory matching process is three milliseconds, of which the first semantics match takes the longest computation time, which is about one millisecond.

6.3. Method Comparison

Following [44,45], the map matching methods can be classified as geometric-based methods, topology-based methods, and advance methods. We compare them with the proposed semantic matching method. As shown in

Table 3. Comparison of matching methods.

Feature	Geometric-Based Methods	Topology-Based Approach	Advance Methods	Our Method
Requirement	Indoor maps	Indoor maps, (link-node network)	Indoor maps, (radio sensors)	Indoor maps
Input	Spatial network	Distance information; angle information	Restrictions	Semantic-rich link-node model
Matching algorithms	Point-to-point matching; point-to-curve matching; curve-to-curve matching	Geometric similarity; shape similarity	Kalman filters; particle filters; Hidden Markov model; conditional random field	Semantics search
Output	Location	Location and shape	Location	Location and semantics
Advantages	Simple and fast	Rich structure information	High precision	Simple calculation and good scalability
Disadvantages	Require high data accuracy; error-prone	Low efficiency	Computational complexity	Model construction time-consuming

, our method uses the simplest algorithm (semantics search), and obtains rich information (location and semantics).

7. Conclusions

In this paper, a semantics-based map matching method was proposed for accurate and efficient indoor user trajectory tracking. Differing from the previous methods, we provided an appropriate formalism to model the rich semantics related to indoor navigation systems. Thus, a semantic-rich indoor link-node model was constructed from the floor plan and used as the map basis for the following trajectory matching. For the acquirement of the continuous indoor pedestrian trajectory, smartphone-based PDR technology was applied. Given the collected trajectory data, an HAR approach was adopted to identify the user indoor activity. Based on this information, a trajectory could be logically segmented and the semantic information and distance information could be inferred. The inferred information was finally utilized to match the inaccurate trajectories with the proposed link-node model. In addition, the matching process was accelerated by first using the most important semantic information. The conducted experiments confirmed that the proposed method can achieve an accurate trajectory tracking result while guaranteeing a high matching efficiency.

In practical applications, buildings serve different functional purposes and may have different layouts and structures. The motion patterns among different users may also show large differences. In order to further improve the applicability of the proposed method, more complex indoor environments and more types of trajectories will be considered in our future work. Furthermore, extending the proposed semantics-based trajectory tracking to real-time applications is a potential direction for further improvement. It is also an interesting research area to restore the missing indoor features by analyzing the trajectory data.