[go: up one dir, main page]
Next Article in Journal
Assessing Performance of Three BIM-Based Views of Buildings for Communication and Management of Vertically Stratified Legal Interests
Next Article in Special Issue
Integrating Decentralized Indoor Evacuation with Information Depositories in the Field
Previous Article in Journal
Using Latent Semantic Analysis to Identify Research Trends in OpenStreetMap
Previous Article in Special Issue
A Multiple Ant Colony Optimization Algorithm for Indoor Room Optimal Spatial Allocation
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
Journals
IJGI
Volume 6
Issue 7
10.3390/ijgi6070197
ijgi-logo
Submit to this Journal Review for this Journal Propose a Special Issue
► Article Menu

Article Menu

share Share announcement Help format_quote Cite question_answer Discuss in SciProfiles thumb_up
...
Endorse textsms
...
Comment
first_page
settings
Order Article Reprints
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

A Novel Semantic Matching Method for Indoor Trajectory Tracking

by
Sheng Guo
,
Hanjiang Xiong
* and
Xianwei Zheng
*
State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing (LIESMARS), Wuhan University, Wuhan 430072, China
*
Authors to whom correspondence should be addressed.
ISPRS Int. J. Geo-Inf. 2017, 6(7), 197; https://doi.org/10.3390/ijgi6070197
Submission received: 15 May 2017 / Revised: 29 June 2017 / Accepted: 29 June 2017 / Published: 1 July 2017
(This article belongs to the Special Issue 3D Indoor Modelling and Navigation)
Browse Figures
Figure 1
<p>Link-node model of an indoor map [<a href="#B5-ijgi-06-00197" class="html-bibr">5</a>]. (<b>a</b>) The link-node model of the first floor; (<b>b</b>) The link-node model of the second floor.</p> "> Figure 2
<p>The semantic-rich link-node model.</p> "> Figure 3
<p>The semantic-rich information of node T1.</p> "> Figure 4
<p>Step detection.</p> "> Figure 5
<p>Location estimation.</p> "> Figure 6
<p>Using the DT algorithm to recognize activities. (<b>a</b>) Decision tree for HAR; (<b>b</b>) The classification process of a trajectory [<a href="#B5-ijgi-06-00197" class="html-bibr">5</a>].</p> "> Figure 7
<p>Trajectory segmentation. S and E represent the start and end points, respectively. The red dots indicate the detected door nodes, and the yellow dots represent the detected turn nodes.</p> "> Figure 8
<p>Semantic matching process. (<b>a</b>) The first floor; (<b>b</b>) The second floor.</p> "> Figure 9
<p>Semantic matching result. (<b>a</b>) The raw trajectory and semantics; (<b>b</b>) The matched trajectory.</p> "> Figure 10
<p>Trajectories (<math display="inline"> <semantics> <mrow> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>–</mo> <msub> <mi>T</mi> <mn>5</mn> </msub> </mrow> </semantics> </math>) with the same semantics. (<b>a</b>) Original trajectories and segmentation; (<b>b</b>) Trajectories after the matching.</p> "> Figure 11
<p>Trajectories (<math display="inline"> <semantics> <mrow> <msub> <mi>T</mi> <mn>6</mn> </msub> <mo>–</mo> <msub> <mi>T</mi> <mrow> <mn>10</mn> </mrow> </msub> </mrow> </semantics> </math>) with the same semantics. (<b>a</b>) Original trajectories and segmentation; (<b>b</b>) Trajectories after the matching.</p> "> Figure 12
<p>Localization error of the trajectories’ end points.</p> "> Figure 13
<p>Examples of short trajectories.</p> ">
Versions Notes

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. A S indicates the adjacent doors ( A 5 – A 9 ) on the south side of the corridor, A N represents doors ( A 0 – A 4 ) on the north side of the corridor, A E and A W represent the east doors ( A 13 – A 16 ) and the west doors ( A 17 – A 18 ), respectively. Similarly, B E , B E , B E , and B E indicate the corresponding nodes on the second floor. R S , R N , T S , and T 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 ( ∅ ). 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 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 S 0 indicates the starting point, l 1 and θ 1 represent the step length and angle of the first step, respectively. The locations of the first and second steps ( S 1 and 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 = ( s e g s − 1 ,   n 1 , s e g 1 − 2 ,   n 2 ,   … n m , s e g m − e ) ,
where T represents the trajectory, n indicates the special node in the trajectory. s e g denotes the trajectory segment between two special nodes. Specially, s e g s − 1 and s e g m − e represent the starting and ending segment of a trajectory, respectively. Similarly, the corresponding semantics are expressed as follows:
S [ T ] = { S [ s e g s − 1 ] , S [ n 1 ] , S [ s e g 1 − 2 ] , S [ n 2 ] ,   …   S [ n m ] , S [ s e g m − e ] } .
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 ( A ) of the trajectory can be expressed as follows:
A = { Standing , Walking , Opening   a   door , Walking , Opening   a   door , Standing } .
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 ( U ) of the trajectory in Figure 7 is obtained as follows:
U = { Turn   left   ( South − East ) , Turn   left ( East − North ) , Turn   left ( North − West ) , Turn   right ( West − North ) , Turn   right ( North − East ) , Turn   left ( East − North ) , Turn   left ( North − West ) } .
According to the above information, special nodes in the trajectory can be acquired. In detail, door nodes and stair nodes can be extracted from A , and the turning nodes can be obtained from 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 ( ∅ ). Thus, the trajectory semantics S [ T e ] in Figure 7 are obtained as follows:
S [ T e ] = { [ “ ∅ ”   ( “ South ” ) ] ,         [ “ Opening   a   door ”   ( “ South ” ) ] ,   [ “ ∅ ”   ( “ South ” ) ] ,   [ “ Turn   left ”   ( “ South         − East ” ) ] ,   [ “ Go   straight ”   ( “ East ” ) ] ,   [ “ Turn   left ”   ( “ East − North ” ) ] ,         [ “ Go   straight ”   ( “ North ” ) ] ,         [ “ Turn   left ”   ( “ North − West ” ) ] ,   [ “ ∅ ”   ( “ West ” ) ] ,   [ “ Turn   right ”   ( “ West − North ” ) ] ,         [ “ Go   straight ”   ( “ North ” ) ] ,   [ “ Turn   right ”   ( “ North − East ” ) ] ,   [ “ ∅ ”   ( “ East ” ) ] ,         [ “ Turn   left ”   ( “ East − North ” ) ] ,   [ “ ∅ ”   ( “ North ” ) ] ,   [ “ Turn   left ”   ( “ North − West ” ) ] ,         [ “ Go   straight ”   ( “ West ” ) ] ,       [ “ Opening   a   door ”   ( “ West ” ) ] ,   [ “ ∅ ”   ( “ West ” ) ] } .

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).
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 [ T e ] 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 , A 19 , B S , B N , 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 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 B 2 , B 3 , B 7 , B 8 , B 22 , and B 23 , we need to use the distance information to exactly match the trajectory. Through the length (10.8 m) of the trajectory segment [ s e g U 1 – U 2 ] estimated by the PDR, we can easily determine that node D 1 in the trajectory corresponds to node 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 ( A 0 – 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 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 O ( N ) . 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 O ( 4 ) . 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, 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.

Acknowledgments

This work is supported by The National Key Research and Development Program of China [grant number 2016YFB0502203], Mapping geographic information industry research projects of public interest Industry [grant number 201512009] and the LIESMARS special Research Funding.

Author Contributions

Sheng Guo conceived and designed the experiments, performed the experiments and analyzed the data; Hanjiang Xiong and Xianwei Zheng supervised the work and revised the paper; Sheng Guo, Xianwei Zheng and Hanjiang Xiong wrote the paper.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Xu, G.; Gao, S.; Daneshmand, M.; Wang, C.; Liu, Y. A Survey for Mobility Big Data Analytics for Geolocation Prediction. IEEE Wirel. Commun. 2017, 24, 111–119. [Google Scholar] [CrossRef]
  2. Feng, Z.; Zhu, Y. A Survey on Trajectory Data Mining: Techniques and Applications. IEEE Access 2016, 4, 2056–2067. [Google Scholar] [CrossRef]
  3. Miller, H.J.; Han, J. Geographic Data Mining and Knowledge Discovery; CRC Press: Boca Raton, FL, USA, 2009; pp. 1–27. [Google Scholar]
  4. Lam, L.D.; Tang, A.; Grundy, J. Predicting indoor spatial movement using data mining and movement patterns. In Proceedings of the 2017 IEEE International Conference on Big Data and Smart Computing (BigComp), Jeju, Korea, 13–16 February 2017; pp. 223–230. [Google Scholar]
  5. Guo, S.; Xiong, H.; Zheng, X.; Zhou, Y. Activity Recognition and Semantic Description for Indoor Mobile Localization. Sensors 2017, 17, 649. [Google Scholar] [CrossRef] [PubMed]
  6. Tian, B.; Morris, B.T.; Tang, M.; Liu, Y.; Yao, Y.; Gou, C.; Shen, D.; Tang, S. Hierarchical and networked vehicle surveillance in its: A survey. IEEE Trans. Intell. Transp. Syst. 2017, 18, 25–48. [Google Scholar] [CrossRef]
  7. Ochieng, W.Y.; Quddus, M.A.; Noland, R.B. Map-matching in complex urban road networks. Braz. J. Cartogr. 2003, 55, 1–14. [Google Scholar]
  8. Blazquez, C.; Vonderohe, A. Simple map-matching algorithm applied to intelligent winter maintenance vehicle data. Transp. Res. Rec. 2005, 1935, 68–76. [Google Scholar] [CrossRef]
  9. Ascher, C.; Kessler, C.; Wankerl, M.; Trommer, G.F. Dual IMU indoor navigation with particle filter based map-matching on a smartphone. In Proceedings of the 2010 International Conference on Indoor Positioning and Indoor Navigation, Zurich, Switzerland, 15–17 September 2010; pp. 1–5. [Google Scholar]
  10. Ishikawa, T.; Kourogi, M.; Okuma, T.; Kurata, T. Economic and synergistic pedestrian tracking system for indoor environments. In Proceedings of the International Conference on Soft Computing and Pattern Recognition, Malacca, Malaysia, 4–7 December 2009; pp. 522–527. [Google Scholar]
  11. Gusenbauer, D.; Isert, C.; Krösche, J. Self-contained indoor positioning on off-the-shelf mobile devices. In Proceedings of the 2010 International Conference on Indoor Positioning and Indoor Navigation, Zurich, Switzerland, 15–17 September 2010; pp. 1–9. [Google Scholar]
  12. Lan, K.; Shih, W. Using Smart-Phones and Floor Plans for Indoor Location Tracking. IEEE Trans. Hum. Mach. Syst. 2014, 44, 211–221. [Google Scholar]
  13. Quddus, M.A.; Ochieng, W.Y.; Noland, R.B. Current map-matching algorithms for transport applications: State-of-the art and future research directions. Trans. Res. Part C Emerg. Technol. 2007, 15, 312–328. [Google Scholar] [CrossRef]
  14. Greenfeld, J.S. Matching GPS observations to locations on a digital map. In Proceedings of the Transportation Research Board 81st Annual Meeting, Washington, DC, USA, 13 January 2002. [Google Scholar]
  15. Jiménez, A.R.; Seco, F.; Zampella, F.; Prieto, J.C.; Guevara, J. Improved heuristic drift elimination with magnetically-aided dominant directions (MiHDE) for pedestrian navigation in complex buildings. J. Locat. Based Ser. 2012, 6, 186–210. [Google Scholar] [CrossRef]
  16. Link, J.A.B.; Smith, P.; Viol, N.; Wehrle, K. Footpath: Accurate map-based indoor navigation using smartphones. In Proceedings of the 2011 International Conference on Indoor Positioning and Indoor Navigation (IPIN 2011), Guimaraes, Portugal, 21–23 September 2011; pp. 1–8. [Google Scholar]
  17. Yin, H.; Wolfson, O. A weight-based map matching method in moving objects databases. In Proceedings of the 16th International Conference on Scientific and Statistical Database Management, Santorini Island, Greece, 21–23 June 2004; pp. 437–438. [Google Scholar]
  18. Pink, O.; Hummel, B. A statistical approach to map matching using road network geometry, topology and vehicular motion constraints. In Proceedings of the 11th International IEEE Conference on Intelligent Transportation Systems, Beijing, China, 12–15 October 2008; pp. 862–867. [Google Scholar]
  19. Liu, J.; Wolfson, O.; Yin, H. Extracting semantic location from outdoor positioning systems. In Proceedings of the 7th International Conference on Mobile Data Management, Nara, Japan, 9–13 May 2006; p. 73. [Google Scholar]
  20. Brakatsoulas, S.; Pfoser, D.; Tryfona, N. Modeling, storing and mining moving object databases. In Proceedings of the International Database Engineering and Applications Symposium (IDEAS 2004), Coimbra, Portugal, 7–9 July 2004; pp. 68–77. [Google Scholar]
  21. Spaccapietra, S.; Parent, C.; Damiani, M.L.; de Macedo, J.A.; Porto, F.; Vangenot, C. A conceptual view on trajectories. Data Knowl. Eng. 2008, 65, 126–146. [Google Scholar] [CrossRef]
  22. Li, Q.; Zheng, Y.; Xie, X.; Chen, Y.; Liu, W.; Ma, W. Mining user similarity based on location history. In Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Irvine, CA, USA, 5–7 November 2008; p. 34. [Google Scholar]
  23. Ying, J.J.; Lu, E.H.; Lee, W.; Weng, T.; Tseng, V.S. Mining user similarity from semantic trajectories. In Proceedings of the 2nd ACM SIGSPATIAL International Workshop on Location Based Social Networks, San Jose, CA, USA, 3–5 November 2010; pp. 19–26. [Google Scholar]
  24. Ying, J.J.; Lee, W.; Weng, T.; Tseng, V.S. Semantic trajectory mining for location prediction. In Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Chicago, IL, USA, 1–4 November 2011; pp. 34–43. [Google Scholar]
  25. Liu, J.; Zhu, L.; Wang, Y.; Liang, X.; Hyyppä, J.; Chu, T.; Liu, K.; Chen, R. Reciprocal Estimation of Pedestrian Location and Motion State toward a Smartphone Geo-Context Computing Solution. Micromachines 2015, 6, 699–717. [Google Scholar] [CrossRef]
  26. Newson, P.; Krumm, J. Hidden Markov map matching through noise and sparseness. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Seattle, WA, USA, 1–4 November 2009; pp. 336–343. [Google Scholar]
  27. Yuan, J.; Zheng, Y.; Zhang, C.; Xie, X.; Sun, G. An interactive-voting based map matching algorithm. In Proceedings of the 11th International Conference on Mobile Data Management, Kanas City, MO, USA, 23–26 May 2010; pp. 43–52. [Google Scholar]
  28. Obradovic, D.; Lenz, H.; Schupfner, M. Fusion of map and sensor data in a modern car navigation system. J. VLSI Sig. Proc. 2006, 45, 111–122. [Google Scholar] [CrossRef]
  29. Quddus, M.A.; Noland, R.B.; Ochieng, W.Y. A high accuracy fuzzy logic based map matching algorithm for road transport. J. Intell. Transp. Syst. Technol. Plann. Oper. 2006, 10, 103–115. [Google Scholar] [CrossRef]
  30. Kim, S.; Kim, J. Adaptive fuzzy-network-based C-measure map-matching algorithm for car navigation system. IEEE Trans. Ind. Electron. 2001, 48, 432–441. [Google Scholar]
  31. Walder, U.; Bernoulli, T. Context-adaptive algorithms to improve indoor positioning with inertial sensors. In Proceedings of the 2010 International Conference on Indoor Positioning and Indoor Navigation (IPIN 2010), Zurich, Switzerland, 15–17 September 2010; pp. 965–970. [Google Scholar]
  32. Wang, H.; Sen, S.; Elgohary, A.; Farid, M.; Youssef, M.; Choudhury, R.R. No need to war-drive: Unsupervised indoor localization. In Proceedings of the 10th International Conference on Mobile Systems, Applications, and Services, Ambleside, UK, 25–29 June 2012; pp. 197–210. [Google Scholar]
  33. Li, F.; Zhao, C.; Ding, G.; Gong, J.; Liu, C.; Zhao, F. A reliable and accurate indoor localization method using phone inertial sensors. In Proceedings of the 2012 ACM Conference on Ubiquitous Computing, Pittsburgh, PA, USA, 5–8 September 2012; pp. 421–430. [Google Scholar]
  34. Leppäkoski, H.; Collin, J.; Takala, J. Pedestrian navigation based on inertial sensors, indoor map, and WLAN signals. J. Sig. Proc. Syst. 2013, 71, 287–296. [Google Scholar] [CrossRef]
  35. Wang, H.; Lenz, H.; Szabo, A.; Bamberger, J.; Hanebeck, U.D. WLAN-based pedestrian tracking using particle filters and low-cost MEMS sensors. In Proceedings of the 4th Workshop on Positioning, Navigation and Communication (WPNC 07), Hannover, Germany, 22 Marth 2007; pp. 1–7. [Google Scholar]
  36. Xiao, Z.; Wen, H.; Markham, A.; Trigoni, N. Lightweight map matching for indoor localisation using conditional random fields. In Proceedings of the 13th International Symposium on Information Processing in Sensor Networks (IPSN-14), Berlin, Germany, 15–17 April 2014; pp. 131–142. [Google Scholar]
  37. Zhou, B.; Li, Q.; Mao, Q.; Tu, W.; Zhang, X.; Chen, L. ALIMC: Activity Landmark-Based Indoor Mapping via Crowdsourcing. IEEE Trans. Intell. Transp. Syst. 2015, 16, 2774–2785. [Google Scholar] [CrossRef]
  38. Gilliéron, P.; Merminod, B. Personal navigation system for indoor applications. In Proceedings of the 11th IAIN World Congress, Smart Navigation—Systems and Services, Berlin, Germany, 21–24 October 2003; pp. 21–24. [Google Scholar]
  39. Incel, O.D.; Kose, M.; Ersoy, C. A Review and Taxonomy of Activity Recognition on Mobile Phones. Bionanoscience 2013, 3, 145–171. [Google Scholar] [CrossRef]
  40. Zhuang, Y.; Lan, H.; Li, Y.; El-Sheimy, N. PDR/INS/WiFi Integration Based on Handheld Devices for Indoor Pedestrian Navigation. Micromachines 2015, 6, 793–812. [Google Scholar] [CrossRef]
  41. Kang, W.; Han, Y. SmartPDR: Smartphone-Based Pedestrian Dead Reckoning for Indoor Localization. IEEE Sens. J. 2015, 15, 2906–2916. [Google Scholar] [CrossRef]
  42. Shoaib, M.; Bosch, S.; Incel, O.; Scholten, H.; Havinga, P. A Survey of Online Activity Recognition Using Mobile Phones. Sensors 2015, 15, 2059–2085. [Google Scholar] [CrossRef] [PubMed]
  43. Masiero, A.; Guarnieri, A.; Pirotti, F.; Vettore, A. A Particle Filter for Smartphone-Based Indoor Pedestrian Navigation. Micromachines 2014, 5, 1012–1033. [Google Scholar] [CrossRef]
  44. Wilk, P.; Karciarz, J. Optimization of map matching algorithms for indoor navigation in shopping malls. In Proceedings of the 2014 International Conference on Indoor Positioning and Indoor Navigation (IPIN 2014), Busan, Korea, 27–30 October 2014; pp. 661–669. [Google Scholar]
  45. Zampella, F.; Ruiz, A.R.J.; Granja, F.S. Indoor positioning using efficient map matching, RSS measurements, and an improved motion model. IEEE Trans. Veh. Technol. 2015, 64, 1304–1317. [Google Scholar] [CrossRef]
Ijgi 06 00197 g001 550
Figure 1. Link-node model of an indoor map [5]. (a) The link-node model of the first floor; (b) The link-node model of the second floor.
Figure 1. Link-node model of an indoor map [5]. (a) The link-node model of the first floor; (b) The link-node model of the second floor.
Ijgi 06 00197 g001
Ijgi 06 00197 g002 550
Figure 2. The semantic-rich link-node model.
Figure 2. The semantic-rich link-node model.
Ijgi 06 00197 g002
Ijgi 06 00197 g003 550
Figure 3. The semantic-rich information of node T1.
Figure 3. The semantic-rich information of node T1.
Ijgi 06 00197 g003
Ijgi 06 00197 g004 550
Figure 4. Step detection.
Figure 4. Step detection.
Ijgi 06 00197 g004
Ijgi 06 00197 g005 550
Figure 5. Location estimation.
Figure 5. Location estimation.
Ijgi 06 00197 g005
Ijgi 06 00197 g006 550
Figure 6. Using the DT algorithm to recognize activities. (a) Decision tree for HAR; (b) The classification process of a trajectory [5].
Figure 6. Using the DT algorithm to recognize activities. (a) Decision tree for HAR; (b) The classification process of a trajectory [5].
Ijgi 06 00197 g006
Ijgi 06 00197 g007 550
Figure 7. Trajectory segmentation. S and E represent the start and end points, respectively. The red dots indicate the detected door nodes, and the yellow dots represent the detected turn nodes.
Figure 7. Trajectory segmentation. S and E represent the start and end points, respectively. The red dots indicate the detected door nodes, and the yellow dots represent the detected turn nodes.
Ijgi 06 00197 g007
Ijgi 06 00197 g008 550
Figure 8. Semantic matching process. (a) The first floor; (b) The second floor.
Figure 8. Semantic matching process. (a) The first floor; (b) The second floor.
Ijgi 06 00197 g008
Ijgi 06 00197 g009 550
Figure 9. Semantic matching result. (a) The raw trajectory and semantics; (b) The matched trajectory.
Figure 9. Semantic matching result. (a) The raw trajectory and semantics; (b) The matched trajectory.
Ijgi 06 00197 g009
Ijgi 06 00197 g010 550
Figure 10. Trajectories ( T 1 – T 5 ) with the same semantics. (a) Original trajectories and segmentation; (b) Trajectories after the matching.
Figure 10. Trajectories ( T 1 – T 5 ) with the same semantics. (a) Original trajectories and segmentation; (b) Trajectories after the matching.
Ijgi 06 00197 g010
Ijgi 06 00197 g011 550
Figure 11. Trajectories ( T 6 – T 10 ) with the same semantics. (a) Original trajectories and segmentation; (b) Trajectories after the matching.
Figure 11. Trajectories ( T 6 – T 10 ) with the same semantics. (a) Original trajectories and segmentation; (b) Trajectories after the matching.
Ijgi 06 00197 g011
Ijgi 06 00197 g012 550
Figure 12. Localization error of the trajectories’ end points.
Figure 12. Localization error of the trajectories’ end points.
Ijgi 06 00197 g012
Ijgi 06 00197 g013 550
Figure 13. Examples of short trajectories.
Figure 13. Examples of short trajectories.
Ijgi 06 00197 g013
Table
Table 1. Semantic weight in trajectory T e .
Table 1. Semantic weight in trajectory T e .
Semantic InformationAttributesFrequency (f1) 1Frequency (f2)Weight
“Opening a door” (“South”)Node33High
“Turn left” (“South-East”)Node34High
“Go straight” (“East”)Link67Medium
“Turn left” (“East-North”)Node46Medium
“Go straight” (“North”)Link89Low
“Turn left” (“North-West”)Node46Medium
“Turn right” (“West-North”)Node35Medium
“Turn right” (“North-East”)Node35Medium
“Go straight” (“West”)Link68Medium
“Opening a door” (“West”)Node87Medium
1 Frequency indicates the number of occurrences of the semantics in the first layer model.
Table
Table 2. Semantic matching results.
Table 2. Semantic matching results.
TrajectoryTrajectory SegmentSemanticsTime ComplexityNumber 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 ( seg U 1 − U 2 )“Go straight” (“East”)O(4)2
Node 3 (U2)“Turn left” (“East–North”)O(4)2
Segment 3 ( s e g U 2 − U 3 )“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 ( s e g U 4 − U 5 )“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 ( s e g U 7 − D 2 )“Go straight” (“West”)O(1)1
Node 9 (D2)“Opening a door” (“West”)O(1)1
1 The number of trajectories after semantic matching.
Table
Table 3. Comparison of matching methods.
Table 3. Comparison of matching methods.
FeatureGeometric-Based MethodsTopology-Based ApproachAdvance MethodsOur Method
RequirementIndoor mapsIndoor maps, (link-node network)Indoor maps, (radio sensors)Indoor maps
InputSpatial networkDistance information; angle informationRestrictionsSemantic-rich link-node model
Matching algorithmsPoint-to-point matching; point-to-curve matching; curve-to-curve matchingGeometric similarity; shape similarityKalman filters; particle filters; Hidden Markov model; conditional random fieldSemantics search
OutputLocationLocation and shapeLocationLocation and semantics
AdvantagesSimple and fastRich structure informationHigh precisionSimple calculation and good scalability
DisadvantagesRequire high data accuracy; error-proneLow efficiencyComputational complexityModel construction time-consuming

Share and Cite

MDPI and ACS Style

Guo, S.; Xiong, H.; Zheng, X. A Novel Semantic Matching Method for Indoor Trajectory Tracking. ISPRS Int. J. Geo-Inf. 2017, 6, 197. https://doi.org/10.3390/ijgi6070197

AMA Style

Guo S, Xiong H, Zheng X. A Novel Semantic Matching Method for Indoor Trajectory Tracking. ISPRS International Journal of Geo-Information. 2017; 6(7):197. https://doi.org/10.3390/ijgi6070197

Chicago/Turabian Style

Guo, Sheng, Hanjiang Xiong, and Xianwei Zheng. 2017. "A Novel Semantic Matching Method for Indoor Trajectory Tracking" ISPRS International Journal of Geo-Information 6, no. 7: 197. https://doi.org/10.3390/ijgi6070197

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop