# Control Optimization of Scenic Spot Navigation System Based on Map Matching Algorithm

Authors: Wenjing Cui
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

In order to solve the problem that the smart phone GPS positioning technology cannot guarantee the location accuracy in the scenic spot navigation system, a tourist spot matching method based on the improved HMM model was proposed. Firstly, the traditional linear road model is improved in electronic map design. Secondly, the concept of minimum peripheral error rectangle is proposed based on the theory of error ellipse. Then, combined with location data, road data, and scenic spot data, the improved HMM model is used to calculate the matching road. Finally, Matlab simulation experiment and comparison experiment are carried out. The results show that the accuracy of the map matching algorithm based on the improved HMM model can reach 94.5%, and the average accuracy can reach 93.1%, which is 3.6% higher than that of the traditional HMM model. The test results show that the proposed algorithm is correct and practical and has a good application prospect.


---

## Body

## 1. Introduction

The development of smart tourism in foreign countries is relatively early. The basic information of scenic spots is collected mainly by “3S” technology (Global Positioning System—GPS, Geographic Information System—GIS, and Remote Sensing technology—RS). The collected information is processed and analyzed to provide location services for tourists and staff and realize intelligent monitoring and visual management of scenic spots and intelligent navigation services (Figure1), so as to properly divert and control the personnel and vehicles in scenic spots [1]. In the past 30 years of reform and opening up in China, with the rapid economic development, cultural tourism industry is also full of vitality. Some large and medium-sized tourist attractions have begun to try to use “3S” technology to establish a relatively perfect intelligent tourism integration network and to connect the tourists around the world via the Internet, which become gradually prominent in the office, ticket, monitoring, map positioning, online tour, and other aspects. However, many small and medium-sized scenic spots are still in the initial stage of comprehensive information construction. The scenic spot portal website has been basically established to introduce and publicize the scenic spot through multimedia and web pages. In general, smart tourism is still in its infancy in China, scenic spots have not fully adapted to the coming Internet thinking, and technological changes have not fully spread to small and medium-sized scenic spots [2]. However, smart tourism is the direction, and Internet thinking is changing traditional industries little by little [3].Figure 1
Scenic area navigation system.Smart tourism has developed rapidly in recent years, and the Touring Navigation Service (TNS) has higher and higher requirements. The high-precision real-time positioning function is very important for walking tourists [4]. However, there is still room for improvement in the positioning and navigation functions provided by existing mobile location service applications in scenic spots. These map applications cannot provide the same schedule as in urban traffic roads. Due to clock synchronization, propagation delay, electromagnetic interference, and other factors, there will be a lot of errors. The general approach is to use different and various filtering methods to eliminate errors. In spite of this, the horizontal error range for civil standard positioning system is still 20 m~30 m. In order to further improve positioning accuracy and map display effect, map matching technology arises at the historic moment [5].Navigation and location service is an indispensable part of tourism navigation system. With the development of 3D technology, 3D scenic navigation system has become one of the key development directions. By building 3D virtual scenes, it provides tourists with more intuitive and clearer location and direction, greatly improving the navigation experience [6]. But at the same time, GPS data error and map system error exist in 3D map positioning using mobile phone GPS technology. GPS data quality will be affected by the satellite itself, signal transmission and reception, positioning environment, and other aspects, leading to positioning deviation. However, in the process of manual map design, road information cannot be completely consistent with the reality, and there is conversion error when GPS position is projected onto the map [7]. In the 3D scenic navigation system, positioning points often fall in buildings or trees due to positioning errors, resulting in the inability to judge the location and direction. Therefore, it is of certain significance to introduce map matching technology to improve the positioning accuracy of scenic navigation system [8].


## 2. Literature Review

GPS positioning technology developed earlier in foreign countries. From the 1970s when the U.S. Department of Defense built GPS satellite navigation system, it has been widely used in many fields after nearly 40 years of application practice and continuous improvement and innovation. Since the US government cancelled the policy of selective availability (SA) in May 2000, the precision of civil GPS positioning has been greatly improved, and other countries in the world have also begun to apply it in space technology, transportation, geological remote sensing exploration, and communication fields on a large scale. In order to further improve GPS positioning accuracy and reduce the impact caused by various errors, various optimization algorithms have been proposed, including filtering algorithm for GPS positioning signal and map matching algorithm with electronic map information [9]. Both have been widely studied in the field of vehicle navigation equipment. In the navigation field of mobile devices, the matching algorithm also needs to consider the real-time positioning under high dynamic conditions, which puts forward higher requirements for the computational complexity and operational efficiency of map matching algorithm. Therefore, in recent years, map matching technology has gradually become a research hotspot [10].In the past two decades, scholars have developed a large number of map matching algorithms. These algorithms are generally divided into simple methods, topological methods, weight-based methods, probabilistic methods, and advanced theory methods. The simple method mainly considers only one factor, such as the nearest distance (including the nearest distance from point to line segment and the nearest distance from line segment to line segment). This method is simple and fast. The topological method not only considers these geometric relations but also considers the topological relations of the road network. This method has better performance in dealing with parallel and intersection sections than the simple method. The weight-based method also considers other factors, such as speed, direction, and path topology, so as to achieve a good balance between complexity and accuracy. The probabilistic method uses the error ellipse region to determine the candidate road segment, and the error ellipse parameters are derived from the error variance-covariance matrix of positioning equipment. Advanced theoretical methods include evidence theory, fuzzy logic, and neural network. Generally, such methods require more input and sacrifice performance while obtaining higher accuracy [11].In this article, through the research and summary of GPS positioning technology and existing matching algorithm, map matching technology is introduced to improve the positioning accuracy, so that moving objects can correctly display location information, and a scenic spot map matching algorithm based on improved HMM model is proposed to improve the positioning accuracy of scenic spot navigation.


## 3. Research Methods

### 3.1. Overview of Key Technologies

#### 3.1.1. Overview of GPS Positioning Technology

GPS system is a global real-time positioning and navigation system developed by the US military in the 1970s through artificial satellites, which is mainly composed of GPS satellite constellation, ground monitoring system, and GPS signal receiver [12]. The basic principle of GPS positioning is as follows: the user receives signals from the satellite, gets the position and clock data of the satellite, and uses the method of space distance intersection to calculate the user’s three-dimensional position. The distance between the user and the satellite can be solved by the product of the time interval between the transmitting and receiving of the satellite signal and the propagation speed of the radio wave and can also be calculated by the distance formula according to the user coordinates and the satellite coordinates [13].


#### 3.1.2. Overview of Kalman Filter Technology

From the positioning principle of GPS system above, it can be seen that the accuracy of GPS is affected by various errors. In essence, there is a probability distribution of GPS errors. On the other hand, GPS signal in map matching can be regarded as a random time series with discrete and Gaussian noise distribution. Therefore, it is feasible to choose a suitable mathematical model to establish GPS error correction model. However, Kalman filter is a state-space time-domain filtering method based on Gaussian linear system. It processes the nonstationary and multidimensional input signals by defining the state model equation and observation model equation and then recursively calculates the minimum mean square error estimation and outputs the corrected value [14].


#### 3.1.3. Map Matching Principle

Kalman filter corrects the position of the original GPS by establishing the data error model; although Kalman filter can reduce the error caused by GPS satellite and signal receiver, it cannot eliminate the error caused by the mapping of anchor points to the map, so map matching technology is used in navigation system. Its working principle is as follows: assuming that the user is always moving on the road, the road data of the electronic map is used to analyze the correlation between the registration point and the road, and the positioning information is associated with the road information by the theoretical algorithm or mathematical model, so as to determine which road the user is most likely to be on and which position on the road [15]. The map matching principle is shown in Figure 2.Figure 2
Map matching principle.


### 3.2. Scenic Area Electronic Map Design and GPS Data Processing

Electronic map is the database of map matching technology, which organically combines the actual geospatial data and nonspatial attribute information to provide users with the required positioning and navigation functions. In the navigation system of scenic spot, the design of electronic map mainly follows the following steps: first, analyze the composition of map data, and build a road model in line with the characteristics of scenic spot, next, an improved model of rectangular road is proposed, and then, the corresponding map database storage structure is designed. Finally, the electronic map of scenic spot is completed to realize the visualization of spatial data of scenic spot. Due to GPS data acquisition process, it will produce errors and affect the result of map matching. Therefore, proper GPS data processing is essential before map matching. Firstly, the drifting or missing data are repaired and processed, and then, the improved Kalman filtering method is used to filter GPS data. Finally, numerical methods are adopted to reduce the error of coordinate transformation in the process of coordinate transformation [16].Kalman filter has become a mature error correction tool. So this article uses Kalman filter method to denoise GPS data. However, with the increase of observation data, the estimated variance of Kalman filter may produce infinite results, which causes the filter to diverge. In order to solve the problem of filtering divergence, this article proposed improvements based on Kalman filter by adding fading factor method [17]. The fading factor λk+1 is defined in the following formula.
(1)λk+1=1λ0≥a,1λ0+b&&λ0<a.Meanwhile,λ0 satisfies the following equation:
(2)λ0=∑j=03∑i=03fabskij.Then, in the equation of one-step prediction variance, the fading factorλk+1 is introduced, and equation (3) is obtained.
(3)Pk+1/k=λk+1Φk+1,kPkΦk+1,kT+Qk.Among which,a is the given system threshold value, b is the compensation coefficient, fabs. is taking the absolute value, kij is the gain value of the gain matrix of the ith row and j column. By adjusting a,b values to ensure that the fading factor increases the gain, it reduces the divergence of filtering. As GPS data is collected in a relatively low-speed environment, the values of a,b can be taken as a=2,b=0.5.


### 3.3. Design and Implementation of Scenic Spot Map Matching Algorithm

#### 3.3.1. Overall Framework of the Algorithm

The input data of the algorithm includes map data and location data. Map data includes road, road topology, and landscape feature information, and location data includes GPS latitude and longitude and time information. In order to reduce the impact of data on the matching process, it is necessary to conduct error correction preprocessing and coordinate transformation processing for data to provide effective data sources for map matching and ensure the feasibility of map matching algorithm [18]. The error area is used to reduce the number of candidate sections, and the calculation is related to the positioning accuracy of GPS. In this article, the minimum peripheral error rectangle is proposed based on probability and statistics method to determine the error region. Then, the section intersecting the error rectangle is calculated as the candidate section. The selection of the candidate section is not only related to the error area but also related to the width of the road. After the candidate road section is determined, the improved HMM model is used to select the optimal matching road section [19]. In order to improve the matching accuracy, historical anchor points and scenic spot information are added in the calculation of transfer probability and observation probability. Finally, the vertical projection method is directly selected to calculate the position of projection points on the matched section, and the anchor points are matched to the road [20].


#### 3.3.2. Selection of Error Area

In order to improve the efficiency of map matching, reducing the search scope of road is a fast and effective method. The emergence of the concept of error ellipse makes many researchers take it as one of the search methods for candidate sections. The basic idea of this method is that there are positioning errors in the measurement of anchor points, and the distribution of anchor points is always scattered in the error area with a certain probability, that is, in this error area, it is very likely to contain the real location of the anchor points. Therefore, sections appearing in the error region can be selected as candidate sections. According to the law of probability and statistics, the distribution of registration points is elliptic, so it is called error ellipse. Formula (4) is defined as follows:
(4)a=σ^012σx2+σy2+σx2−σy2+4σxy2,b=σ^012σx2−σy2+σx2−σy2+4σxy2,Φ=π2−12arctan2σxyσx2−σy2.a and b distributions are represented as the major axis and the minor axis of the error ellipse. σx2 is the error variance in the east-west direction, σy2 is the error variance in the north-south direction, σ^0 is the adjustment error of the weight, σxy is the covariance of the error, and Φ is the angle between the major axis of the ellipse and the y-axis, by adjusting the size of σ^0 to obtain different confidence, so as to control the range of error region. When σ^0=3.03, the error ellipse can obtain 99% confidence [21].In this article, linear roads are extended to rectangular roads, so the complexity of calculating candidate roads needs to be considered. In order to reduce the calculation effort, an improved minimal peripheral error rectangle (MEER) is proposed based on the error ellipse, as shown in Figure3. The rectangle is tangent to the vertices of the long and short axes of the error ellipse, and its length and width can be calculated by formula (5) as follows:
(5)l=2σ^012σx2+σy2+σx2−σy2+4σxy2,w=2σ^01/2σx2−σy2+σx2−σy2+4σxy2.Figure 3
Minimum peripheral error rectangle.In general, the center of the error area is the user’s GPS anchor point obtained. In the preprocessing stage of GPS data, the location of the anchor point is modified to correct the obtained GPS information to a more close to the real position. Therefore, the corrected position is taken as the center of the error region when calculating the error rectangle.


#### 3.3.3. Improve Matching Algorithm of HMM Model

The map matching process has two basic steps: one is to determine which road the location point is on. The second is to determine the exact location of the position point on the road. Therefore, the key of map matching is the correct matching of the lock-in section. Considering the matching efficiency and matching accuracy of the algorithm, as well as the behavior characteristics of tourists in scenic spots, this article proposes a matching algorithm based on the improved HMM model. The most important thing in HMM model construction is to define state transition probability and observation probability. The specific innovation points of the scenic spot matching algorithm include the following two points: the activity characteristics of tourists are taken into account in the calculation of the transfer probability, and the correlation factor between sections and scenic spots is added to reduce the error of intersection matching. When calculating the observation probability, the influence of historical anchor point on the current observation variable is considered in HMM model for the first time, so as to improve the accuracy of road matching [22].The traditional HMM model consists of five basic elements, which are implicit state set, observation variable set, state transition probability, observation probability, and initial state probability. In the improved HMM algorithm for scenic spot map matching, GPS track sequenceP=ptt=1,2,3,⋯,m is the set of observation variables. According to each GPS track point pt, the corresponding candidate road section set Rt=rtii=1,2,3,⋯,n is the recessive state set. State transition probability Prtjrt−1i represents the probability that the recessive state of t−1 at the previous time will transfer to the recessive state of t at the next time. In the traditional HMM model, observation probability represents the probability of obtaining observation points in the current recessive state. However, in this article, observation probability not only depends on the state at the current moment but also depends on the influence of historical observation points at the previous moment on the current observation point, denoted as Pptrtj,pt−1. Finally, Viterbi algorithm is used to obtain the sequence of road sections with the maximum joint probability corresponding to trajectory P, which is called the optimal matching road section, denoted as R∗=rt∗t=1,2,⋯,m.


## 3.1. Overview of Key Technologies

### 3.1.1. Overview of GPS Positioning Technology

GPS system is a global real-time positioning and navigation system developed by the US military in the 1970s through artificial satellites, which is mainly composed of GPS satellite constellation, ground monitoring system, and GPS signal receiver [12]. The basic principle of GPS positioning is as follows: the user receives signals from the satellite, gets the position and clock data of the satellite, and uses the method of space distance intersection to calculate the user’s three-dimensional position. The distance between the user and the satellite can be solved by the product of the time interval between the transmitting and receiving of the satellite signal and the propagation speed of the radio wave and can also be calculated by the distance formula according to the user coordinates and the satellite coordinates [13].


### 3.1.2. Overview of Kalman Filter Technology

From the positioning principle of GPS system above, it can be seen that the accuracy of GPS is affected by various errors. In essence, there is a probability distribution of GPS errors. On the other hand, GPS signal in map matching can be regarded as a random time series with discrete and Gaussian noise distribution. Therefore, it is feasible to choose a suitable mathematical model to establish GPS error correction model. However, Kalman filter is a state-space time-domain filtering method based on Gaussian linear system. It processes the nonstationary and multidimensional input signals by defining the state model equation and observation model equation and then recursively calculates the minimum mean square error estimation and outputs the corrected value [14].


### 3.1.3. Map Matching Principle

Kalman filter corrects the position of the original GPS by establishing the data error model; although Kalman filter can reduce the error caused by GPS satellite and signal receiver, it cannot eliminate the error caused by the mapping of anchor points to the map, so map matching technology is used in navigation system. Its working principle is as follows: assuming that the user is always moving on the road, the road data of the electronic map is used to analyze the correlation between the registration point and the road, and the positioning information is associated with the road information by the theoretical algorithm or mathematical model, so as to determine which road the user is most likely to be on and which position on the road [15]. The map matching principle is shown in Figure 2.Figure 2
Map matching principle.


## 3.1.1. Overview of GPS Positioning Technology

GPS system is a global real-time positioning and navigation system developed by the US military in the 1970s through artificial satellites, which is mainly composed of GPS satellite constellation, ground monitoring system, and GPS signal receiver [12]. The basic principle of GPS positioning is as follows: the user receives signals from the satellite, gets the position and clock data of the satellite, and uses the method of space distance intersection to calculate the user’s three-dimensional position. The distance between the user and the satellite can be solved by the product of the time interval between the transmitting and receiving of the satellite signal and the propagation speed of the radio wave and can also be calculated by the distance formula according to the user coordinates and the satellite coordinates [13].


## 3.1.2. Overview of Kalman Filter Technology

From the positioning principle of GPS system above, it can be seen that the accuracy of GPS is affected by various errors. In essence, there is a probability distribution of GPS errors. On the other hand, GPS signal in map matching can be regarded as a random time series with discrete and Gaussian noise distribution. Therefore, it is feasible to choose a suitable mathematical model to establish GPS error correction model. However, Kalman filter is a state-space time-domain filtering method based on Gaussian linear system. It processes the nonstationary and multidimensional input signals by defining the state model equation and observation model equation and then recursively calculates the minimum mean square error estimation and outputs the corrected value [14].


## 3.1.3. Map Matching Principle

Kalman filter corrects the position of the original GPS by establishing the data error model; although Kalman filter can reduce the error caused by GPS satellite and signal receiver, it cannot eliminate the error caused by the mapping of anchor points to the map, so map matching technology is used in navigation system. Its working principle is as follows: assuming that the user is always moving on the road, the road data of the electronic map is used to analyze the correlation between the registration point and the road, and the positioning information is associated with the road information by the theoretical algorithm or mathematical model, so as to determine which road the user is most likely to be on and which position on the road [15]. The map matching principle is shown in Figure 2.Figure 2
Map matching principle.


## 3.2. Scenic Area Electronic Map Design and GPS Data Processing

Electronic map is the database of map matching technology, which organically combines the actual geospatial data and nonspatial attribute information to provide users with the required positioning and navigation functions. In the navigation system of scenic spot, the design of electronic map mainly follows the following steps: first, analyze the composition of map data, and build a road model in line with the characteristics of scenic spot, next, an improved model of rectangular road is proposed, and then, the corresponding map database storage structure is designed. Finally, the electronic map of scenic spot is completed to realize the visualization of spatial data of scenic spot. Due to GPS data acquisition process, it will produce errors and affect the result of map matching. Therefore, proper GPS data processing is essential before map matching. Firstly, the drifting or missing data are repaired and processed, and then, the improved Kalman filtering method is used to filter GPS data. Finally, numerical methods are adopted to reduce the error of coordinate transformation in the process of coordinate transformation [16].Kalman filter has become a mature error correction tool. So this article uses Kalman filter method to denoise GPS data. However, with the increase of observation data, the estimated variance of Kalman filter may produce infinite results, which causes the filter to diverge. In order to solve the problem of filtering divergence, this article proposed improvements based on Kalman filter by adding fading factor method [17]. The fading factor λk+1 is defined in the following formula.
(1)λk+1=1λ0≥a,1λ0+b&&λ0<a.Meanwhile,λ0 satisfies the following equation:
(2)λ0=∑j=03∑i=03fabskij.Then, in the equation of one-step prediction variance, the fading factorλk+1 is introduced, and equation (3) is obtained.
(3)Pk+1/k=λk+1Φk+1,kPkΦk+1,kT+Qk.Among which,a is the given system threshold value, b is the compensation coefficient, fabs. is taking the absolute value, kij is the gain value of the gain matrix of the ith row and j column. By adjusting a,b values to ensure that the fading factor increases the gain, it reduces the divergence of filtering. As GPS data is collected in a relatively low-speed environment, the values of a,b can be taken as a=2,b=0.5.


## 3.3. Design and Implementation of Scenic Spot Map Matching Algorithm

### 3.3.1. Overall Framework of the Algorithm

The input data of the algorithm includes map data and location data. Map data includes road, road topology, and landscape feature information, and location data includes GPS latitude and longitude and time information. In order to reduce the impact of data on the matching process, it is necessary to conduct error correction preprocessing and coordinate transformation processing for data to provide effective data sources for map matching and ensure the feasibility of map matching algorithm [18]. The error area is used to reduce the number of candidate sections, and the calculation is related to the positioning accuracy of GPS. In this article, the minimum peripheral error rectangle is proposed based on probability and statistics method to determine the error region. Then, the section intersecting the error rectangle is calculated as the candidate section. The selection of the candidate section is not only related to the error area but also related to the width of the road. After the candidate road section is determined, the improved HMM model is used to select the optimal matching road section [19]. In order to improve the matching accuracy, historical anchor points and scenic spot information are added in the calculation of transfer probability and observation probability. Finally, the vertical projection method is directly selected to calculate the position of projection points on the matched section, and the anchor points are matched to the road [20].


### 3.3.2. Selection of Error Area

In order to improve the efficiency of map matching, reducing the search scope of road is a fast and effective method. The emergence of the concept of error ellipse makes many researchers take it as one of the search methods for candidate sections. The basic idea of this method is that there are positioning errors in the measurement of anchor points, and the distribution of anchor points is always scattered in the error area with a certain probability, that is, in this error area, it is very likely to contain the real location of the anchor points. Therefore, sections appearing in the error region can be selected as candidate sections. According to the law of probability and statistics, the distribution of registration points is elliptic, so it is called error ellipse. Formula (4) is defined as follows:
(4)a=σ^012σx2+σy2+σx2−σy2+4σxy2,b=σ^012σx2−σy2+σx2−σy2+4σxy2,Φ=π2−12arctan2σxyσx2−σy2.a and b distributions are represented as the major axis and the minor axis of the error ellipse. σx2 is the error variance in the east-west direction, σy2 is the error variance in the north-south direction, σ^0 is the adjustment error of the weight, σxy is the covariance of the error, and Φ is the angle between the major axis of the ellipse and the y-axis, by adjusting the size of σ^0 to obtain different confidence, so as to control the range of error region. When σ^0=3.03, the error ellipse can obtain 99% confidence [21].In this article, linear roads are extended to rectangular roads, so the complexity of calculating candidate roads needs to be considered. In order to reduce the calculation effort, an improved minimal peripheral error rectangle (MEER) is proposed based on the error ellipse, as shown in Figure3. The rectangle is tangent to the vertices of the long and short axes of the error ellipse, and its length and width can be calculated by formula (5) as follows:
(5)l=2σ^012σx2+σy2+σx2−σy2+4σxy2,w=2σ^01/2σx2−σy2+σx2−σy2+4σxy2.Figure 3
Minimum peripheral error rectangle.In general, the center of the error area is the user’s GPS anchor point obtained. In the preprocessing stage of GPS data, the location of the anchor point is modified to correct the obtained GPS information to a more close to the real position. Therefore, the corrected position is taken as the center of the error region when calculating the error rectangle.


### 3.3.3. Improve Matching Algorithm of HMM Model

The map matching process has two basic steps: one is to determine which road the location point is on. The second is to determine the exact location of the position point on the road. Therefore, the key of map matching is the correct matching of the lock-in section. Considering the matching efficiency and matching accuracy of the algorithm, as well as the behavior characteristics of tourists in scenic spots, this article proposes a matching algorithm based on the improved HMM model. The most important thing in HMM model construction is to define state transition probability and observation probability. The specific innovation points of the scenic spot matching algorithm include the following two points: the activity characteristics of tourists are taken into account in the calculation of the transfer probability, and the correlation factor between sections and scenic spots is added to reduce the error of intersection matching. When calculating the observation probability, the influence of historical anchor point on the current observation variable is considered in HMM model for the first time, so as to improve the accuracy of road matching [22].The traditional HMM model consists of five basic elements, which are implicit state set, observation variable set, state transition probability, observation probability, and initial state probability. In the improved HMM algorithm for scenic spot map matching, GPS track sequenceP=ptt=1,2,3,⋯,m is the set of observation variables. According to each GPS track point pt, the corresponding candidate road section set Rt=rtii=1,2,3,⋯,n is the recessive state set. State transition probability Prtjrt−1i represents the probability that the recessive state of t−1 at the previous time will transfer to the recessive state of t at the next time. In the traditional HMM model, observation probability represents the probability of obtaining observation points in the current recessive state. However, in this article, observation probability not only depends on the state at the current moment but also depends on the influence of historical observation points at the previous moment on the current observation point, denoted as Pptrtj,pt−1. Finally, Viterbi algorithm is used to obtain the sequence of road sections with the maximum joint probability corresponding to trajectory P, which is called the optimal matching road section, denoted as R∗=rt∗t=1,2,⋯,m.


## 3.3.1. Overall Framework of the Algorithm

The input data of the algorithm includes map data and location data. Map data includes road, road topology, and landscape feature information, and location data includes GPS latitude and longitude and time information. In order to reduce the impact of data on the matching process, it is necessary to conduct error correction preprocessing and coordinate transformation processing for data to provide effective data sources for map matching and ensure the feasibility of map matching algorithm [18]. The error area is used to reduce the number of candidate sections, and the calculation is related to the positioning accuracy of GPS. In this article, the minimum peripheral error rectangle is proposed based on probability and statistics method to determine the error region. Then, the section intersecting the error rectangle is calculated as the candidate section. The selection of the candidate section is not only related to the error area but also related to the width of the road. After the candidate road section is determined, the improved HMM model is used to select the optimal matching road section [19]. In order to improve the matching accuracy, historical anchor points and scenic spot information are added in the calculation of transfer probability and observation probability. Finally, the vertical projection method is directly selected to calculate the position of projection points on the matched section, and the anchor points are matched to the road [20].


## 3.3.2. Selection of Error Area

In order to improve the efficiency of map matching, reducing the search scope of road is a fast and effective method. The emergence of the concept of error ellipse makes many researchers take it as one of the search methods for candidate sections. The basic idea of this method is that there are positioning errors in the measurement of anchor points, and the distribution of anchor points is always scattered in the error area with a certain probability, that is, in this error area, it is very likely to contain the real location of the anchor points. Therefore, sections appearing in the error region can be selected as candidate sections. According to the law of probability and statistics, the distribution of registration points is elliptic, so it is called error ellipse. Formula (4) is defined as follows:
(4)a=σ^012σx2+σy2+σx2−σy2+4σxy2,b=σ^012σx2−σy2+σx2−σy2+4σxy2,Φ=π2−12arctan2σxyσx2−σy2.a and b distributions are represented as the major axis and the minor axis of the error ellipse. σx2 is the error variance in the east-west direction, σy2 is the error variance in the north-south direction, σ^0 is the adjustment error of the weight, σxy is the covariance of the error, and Φ is the angle between the major axis of the ellipse and the y-axis, by adjusting the size of σ^0 to obtain different confidence, so as to control the range of error region. When σ^0=3.03, the error ellipse can obtain 99% confidence [21].In this article, linear roads are extended to rectangular roads, so the complexity of calculating candidate roads needs to be considered. In order to reduce the calculation effort, an improved minimal peripheral error rectangle (MEER) is proposed based on the error ellipse, as shown in Figure3. The rectangle is tangent to the vertices of the long and short axes of the error ellipse, and its length and width can be calculated by formula (5) as follows:
(5)l=2σ^012σx2+σy2+σx2−σy2+4σxy2,w=2σ^01/2σx2−σy2+σx2−σy2+4σxy2.Figure 3
Minimum peripheral error rectangle.In general, the center of the error area is the user’s GPS anchor point obtained. In the preprocessing stage of GPS data, the location of the anchor point is modified to correct the obtained GPS information to a more close to the real position. Therefore, the corrected position is taken as the center of the error region when calculating the error rectangle.


## 3.3.3. Improve Matching Algorithm of HMM Model

The map matching process has two basic steps: one is to determine which road the location point is on. The second is to determine the exact location of the position point on the road. Therefore, the key of map matching is the correct matching of the lock-in section. Considering the matching efficiency and matching accuracy of the algorithm, as well as the behavior characteristics of tourists in scenic spots, this article proposes a matching algorithm based on the improved HMM model. The most important thing in HMM model construction is to define state transition probability and observation probability. The specific innovation points of the scenic spot matching algorithm include the following two points: the activity characteristics of tourists are taken into account in the calculation of the transfer probability, and the correlation factor between sections and scenic spots is added to reduce the error of intersection matching. When calculating the observation probability, the influence of historical anchor point on the current observation variable is considered in HMM model for the first time, so as to improve the accuracy of road matching [22].The traditional HMM model consists of five basic elements, which are implicit state set, observation variable set, state transition probability, observation probability, and initial state probability. In the improved HMM algorithm for scenic spot map matching, GPS track sequenceP=ptt=1,2,3,⋯,m is the set of observation variables. According to each GPS track point pt, the corresponding candidate road section set Rt=rtii=1,2,3,⋯,n is the recessive state set. State transition probability Prtjrt−1i represents the probability that the recessive state of t−1 at the previous time will transfer to the recessive state of t at the next time. In the traditional HMM model, observation probability represents the probability of obtaining observation points in the current recessive state. However, in this article, observation probability not only depends on the state at the current moment but also depends on the influence of historical observation points at the previous moment on the current observation point, denoted as Pptrtj,pt−1. Finally, Viterbi algorithm is used to obtain the sequence of road sections with the maximum joint probability corresponding to trajectory P, which is called the optimal matching road section, denoted as R∗=rt∗t=1,2,⋯,m.


## 4. Result Analysis

This article has introduced the scenic spot map matching algorithm based on the improved HMM model in detail. In this section, GPS data will be selected to verify the algorithm in the Matlab simulation environment. The validity of the data, the availability of the algorithm, and the correctness of the matching results are tested and analyzed [23].In order to verify the matching accuracy of the proposed algorithm, this article selects a map matching algorithm based on HMM model for comparative experiment. The traditional algorithm is also used to correct and match the location of low-speed moving objects, which mainly considers the information of registration points, distance of sections, and topology information of roads. Based on these characteristics, the traditional algorithm has a good comparison with the improved algorithm in this article.In the experiment, this article chooses three different paths for the experiment: (1) path 1 passes near a tall building, but the signal effect is not particularly ideal; (2) path 2 passes through many intersections; (3) path 3 passes through many scenic spots [24]. Through these three experiments, not only the accuracy of the algorithm, but also the adaptability of the algorithm is verified. In the simulation experiment, the data contents of three groups of positioning tracks are shown in Table 1.Table 1
Experimental track data.
Total number of original registration pointsTotal number of registration points after data preprocessingSampling intervalTrack 11591515 sTrack 21731655 sTrack 32152025 sThe experimental results of track 1 are shown in Figure4. The weak GPS signal leads to a large positioning offset, and the traditional algorithm makes errors in the matching process. However, the improved algorithm in this article shows better matching effect.Figure 4
The experimental results of track 1.Figure5 shows the experimental results of track 2. At the intersection, the improved algorithm in this article not only considers the topological information of the road, but also the similarity between the track direction and the road direction. Therefore, considering the trajectory direction can improve the matching accuracy [25].Figure 5
Map matching results of track 2.The matching accuracy of the improved algorithm and the traditional algorithm in this article is shown in Table2, which, respectively, shows the matching accuracy of the three trajectories.Table 2
Matching accuracy of the three trajectories.
Track 1Track 2Track 3Average accuracyImproved algorithm in this article94.5%91.1%93.8%93.1%Traditional algorithm90.1%89.8%88.6%89.5%It can be concluded from Table2 that the accuracy rate of the scenic spot map matching algorithm using the improved HMM model can reach 94.5% and 93.1% on average, which is 3.6% higher than the map matching algorithm of the traditional HMM model. Experimental results show that the proposed algorithm has good accuracy and adaptability.


## 5. Conclusion

Aiming at the problem of inaccurate positioning in the navigation system of scenic spots, this article introduces map matching technology to improve the accuracy of positioning, so that the moving object can display the location information correctly. By studying the development status of map matching technology at home and abroad, combining the characteristics of scenic spot location and the source of location error, this article proposes a scenic spot map matching algorithm based on hidden Markov model (HMM). The algorithm extends the design of road model and location error area, improves the probability calculation function of HMM model, and evaluates the location effect of map matching algorithm by using GPS data collected. Experiments show that the algorithm in this article has good adaptability and correctness.Although the map matching algorithm studied in this article has been verified in simulation experiment and system application, showing good accuracy and practicability, there are still many shortcomings, mainly manifested as the following points:(1)
The algorithm proposed in this article adopts fixed window size to segment GPS sequence in HMM model modeling. In the application, the window size should be dynamically adjusted according to the actual data to achieve adaptive matching process. On the other hand, tourists’ behavior patterns can be further studied, which is conducive to further improving the accuracy of matchingIn the final matching point projection stage, this article adopts the direct vertical projection method to project the anchor point onto the center line of the road. This method can reduce the error of the anchor point perpendicular to the direction of the road section, but not along the direction of the road section. In the future, the projection process of matching points should be further studied to solve this problem.



---

*Source: 5958782-2022-07-28.xml*