CN115265555B - Map matching correction method and system based on hidden Markov multi-noise perception - Google Patents

Abstract

The invention provides a map matching correction method and a system based on hidden Markov multi-noise perception, which are used for obtaining a smooth track by gridding an area; inputting the smoothed track into a hidden Markov model for matching; calculating fluctuation conditions of observation points in the matching process; deleting the current observation point when the fluctuation amplitude exceeds a threshold value; deleting continuous track points in the adjacent area, predicting the positions of the deleted points, evaluating the error range of the predicted positions and the observed positions, and judging that the map error exists at the section of sampling track when the error is smaller than a threshold value; and taking the deleted points as the input of a map generator, dividing the deleted road segments into a series of sections according to the calculated inflection point positions, and calculating the line segments passing through the inflection points in the sections. The invention creatively provides a map matching framework capable of detecting map errors and deleting low-quality sampling points, which can be combined with a map matching algorithm based on a hidden Markov model to correct matching results and improve matching accuracy.

Description

Map matching correction method and system based on multi-noise perception of hidden Markov

Technical Field

The present invention relates to the technical field of intelligent transportation, and in particular, to a map matching and correction method and system based on hidden Markov multi-noise perception. In particular, it preferably relates to a map matching and correction framework based on hidden Markov model multi-noise perception.

Background technique

In recent years, with the rapid development and widespread application of online taxi platforms, various companies have launched their own taxi apps, and almost all taxis are equipped with GPS devices to obtain information such as the location and direction of the vehicle. Many functions such as taxi route navigation, location and route prediction and identification, and abnormal behavior detection require accurate positioning and tracking.

Most of the early research on map matching algorithms was based on geometric similarity, which cannot handle situations with large sampling errors. Many matching algorithms based on hidden Markov models proposed later defined transition probabilities with the help of the limitations of the road network itself, thereby avoiding situations where the wrong road sections are selected due to large sampling errors. However, these algorithms lack consideration of the complexity of the road network and the simultaneous occurrence of large sampling errors, resulting in incorrect matching results such as reverse motion. At the same time, since the real road network itself is constantly updated, the lack of road sections makes it impossible to select real road sections during map matching.

In addition to the hidden Markov model, there have been other improvements in map matching algorithms in recent years. With the introduction of more indicators, some algorithms based on scoring models have also achieved good results. For example, support vector machines are used to classify each GPS point and remove low-quality sampling points. In general, the matching accuracy of various algorithms is sufficient for practical scenarios when the sampling error is low or the road network restrictions are met.

The Chinese invention patent document with publication number CN113639757A discloses a map matching method and system based on a two-way scoring model and a backtracking correction mechanism, including: selecting candidate points based on the collected GPS point location information according to the map path information; scoring the measured position, direction and speed of the GPS point based on the two-way scoring model and assigning different weights to the position, direction and speed to obtain the score of the candidate point to the GPS point; when the score of the GPS point is lower than the threshold, it is determined to be a low-quality point, and the current low-quality point is deleted and does not participate in the matching; when the continuous GPS points are determined to be low-quality points and deleted, the deleted GPS points are reversely evaluated using the first subsequent GPS point that has not been deleted, and the deleted GPS points are re-detected to see if they are low-quality points; the matching probability of each candidate point and the currently retained GPS point is calculated based on the two-way scoring model, and the candidate point with the largest probability value is selected as the matching candidate point; according to the matching candidate points, a unique map matching result is generated based on the shortest path principle.

With respect to the above-mentioned related technologies, the inventors believe that the currently proposed algorithms ignore map errors and large sampling errors, which leads to erroneous matching results such as frequent interruptions or detours in actual applications.

Summary of the invention

In view of the defects in the prior art, the object of the present invention is to provide a map matching correction method and system based on hidden Markov multi-noise perception.

According to the present invention, a map matching correction method based on hidden Markov multi-noise perception includes the following steps:

Region windowing step: By gridding the region, the irregular drift of the trajectory is limited to obtain a smooth trajectory;

Map matching step: the smoothed trajectory is input into the hidden Markov model with deleted points and map correction frame for matching;

Probability fluctuation detection step: during the matching process, the fluctuation of the Viterbi decoding probability of each observation point is calculated; if the fluctuation amplitude exceeds the threshold, the current observation point is deleted;

Trajectory evaluation step: If continuous trajectory points are deleted in the adjacent area, the Kalman filter and the retained trajectory points are used to predict the position of the deleted points, and the error range between the predicted position and the observed position is evaluated. If the error is less than the threshold, it is determined that there is a map error in the sampling trajectory;

Steps for generating missing road segments: Use the deleted points as the input of the map generator, divide the missing road segments into a series of intervals according to the calculated turning point positions, and use the linear regression model to calculate the line segments passing through the turning points within the intervals.

Preferably, in the region windowing step, the geographical region is first divided into grid units;

If a vehicle does not spend a predetermined travel time in a grid cell, the vehicle is not allowed to transition from that grid cell;

In each grid cell, a variation of the DP algorithm is used to smooth the trajectory, replacing the original trajectory with an approximated line segment;

If the replacement does not meet the specified error requirement, the original problem is recursively divided into two sub-problems by using the selected position point as the partition point, and then it is judged whether the replacement meets the specified error requirement until the error between the approximate trajectory and the original trajectory is lower than the specified error threshold;

The DP algorithm uses orthogonal Euclidean distance as the error metric to maintain the directional trend in the approximate trajectory;

Limit the velocity variation in a grid cell by removing partition points whose distance is greater than a threshold.

Preferably, in the map matching step, in the map matching stage, the smoothed GPS points are obtained from the region windowing step as input, and the smoothed GPS points are mapped to road segments on the digital map, and a hidden Markov model is used to determine a road segment sequence corresponding to a timestamp sequence of the GPS raw data;

A hidden Markov model is a discrete-time Markov process with candidate states and observations;

Use the index grid to search for candidate states, each candidate state is the point closest to the observation point in the road segment, and generates an observation probability The observation probability/> Defined as the GPS sampling point p _i and the candidate point calculated based on the Gaussian noise model/> Possibility of matching:

where σ is the standard deviation and d is defined as p _i and The projection distance between them, _pi is the sampling point at time i, /> is the jth candidate point of _pi ;

in, is the jth candidate road segment of p _i , c is the edge/> For any point on , dist( _pi ,c) is the Euclidean distance between _pi and c;

The hidden Markov model allows transitions from the previous candidate state to the current candidate state, and the transitions are controlled by transition probabilities;

As a rule of thumb, the Hidden Markov Model assumes that the shortest path between consecutive candidate states has a transition probability

Therefore, the transition probability The calculation is as follows:

in, is the candidate point of the current observation; /> is the candidate point of the previous observation; D is the point from/> To/> The absolute value of the difference between the shortest path length and the Euclidean distance between observations;

Then, an online Viterbi decoding algorithm is used to find the maximum likelihood sequence of the road segments corresponding to the variable sliding window of the input sequence.

Preferably, in the probability fluctuation detection step, by defining the observation probability and the transition probability, a hierarchical graph is gradually constructed by adding new nodes and weighted edges after receiving the GPS sampling points;

If the matching accuracy decreases when adding new GPS samples to the layer map, it is considered that there is a measurement error or map error;

Given a set of candidate points, the hidden Markov model will calculate the maximum likelihood path using the Viterbi decoding algorithm;

When the candidate set contains the true location of the observation, the hidden Markov model infers the correct path;

When there are map errors or measurement errors, the shortest path between two consecutive candidates is not the true path and will be circuitous;

The collected points that do not contain the true position in the candidate set are regarded as low-quality points, and the detection model will delete the detected low-quality points;

The calculation process of the Viterbi algorithm is to maximize the product of the observation probability and the transition probability when adding new GPS sampling points;

Sampling errors or map errors cause fluctuations in the amplitude of the optimal decoding probability;

Take the logarithm of the original value to make the fluctuation more obvious;

When the sampling of newly added points causes the fluctuation of the matching probability to exceed the preset threshold, the newly added points are deleted;

Limit the number of consecutive points removed when there are map errors;

When a series of consecutive sample points in an area are removed beyond a limit, the algorithm evaluator will evaluate the unmatched samples to detect whether there are map errors and, if so, use the map generation model to fit the missing roads.

Preferably, in the trajectory evaluation step, a series of GPS points that are successively removed from the detection model are used as input, and the quality of the entire sequence is evaluated to determine the reasons for removal;

Evaluate the motion pattern of this series of GPS-removed samples under position and velocity constraints;

If the detected anomaly is caused by a motion pattern that does not conform to the actual driving situation, the change in matching probability is considered to be caused by measurement error and the corresponding point is deleted; the remaining points are re-added to the matching sequence to continue matching;

If removing points to form driving patterns is allowed in the evaluation model, the removed GPS sample points are restored and the missing roads are generated using the points that could not be matched;

Use Kalman filtering to predict the direction and position of the vehicle, and then use the estimated points as new matching points to determine whether there are any abnormalities;

The speed and direction information of the road section near the sampling point is used as the input of the motion trajectory physical model to calculate the ideal position of the vehicle at the next moment. The sampled trajectory direction and speed information is used as the motion model input to calculate the position at the next moment as the measurement value.

Based on the error between the weighted estimate and the true value of the system, the Kalman gain is calculated, and the position estimate at the next moment is obtained as follows:

xt _|t ＝ _{Ktzt +} ( _IKtH )xt _|t-1

Where _xt|t is the system estimate, _xt|t-1 is the ideal state value of the system, _zt is the measured value, _Kt is the Kalman gain, I is the identity matrix, and H is the state space transformation matrix;

The predicted position value is compared with the sampled position value, and the average distance between the predicted position value and the sampled position value is calculated. If the distance is less than the threshold Δd, it is considered that the sampling is caused by a map error.

Preferably, in the missing road segment generation step, the digital map is composed of an attributed undirected graph; intersections are represented as vertices with a degree greater than two, and road segments are represented as a series of edges; bidirectional roads are regarded as single paths; high-order attributes are defined to supplement the graph; geometric features are displayed as part of the map description; and local geometric shape information about the road is provided;

Use a map generation model based on clustering techniques to automatically infer road and traffic characteristics;

The map generation model fits the GPS sampling points that cannot be matched, and the generated topology is close to the actual missing roads;

According to the position of the turning point, the unmatched GPS points are divided into different intervals;

The distance of the inflection point is measured by the Euclidean distance variable of the perpendicular Euclidean distance;

In each segment, a linear regression model is used to fit the missing roads;

In order to determine the location of the turning point, the parameters θ _G and d _G are set;

Connect the first and last points in the sequence, and then project all other points onto the connecting line;

If the specified projection distance is greater than the threshold d _G , the point with the specified distance is the corner point of the real road segment;

Connect the first point and the last point with the points with the specified projection distance, and continue to calculate the angle between the lines; if the angle is greater than the threshold θ _G , divide the sequence into two parts and iterate.

According to the present invention, a map matching correction system based on hidden Markov multi-noise perception includes the following modules:

Regional windowing module: By gridding the region, the irregular drift of the trajectory is limited to obtain a smooth trajectory;

Map matching module: The smoothed trajectory is input into the hidden Markov model with deleted points and map correction frame for matching;

Probability fluctuation detection module: during the matching process, the fluctuation of the Viterbi decoding probability of each observation point is calculated; if the fluctuation amplitude exceeds the threshold, the current observation point is deleted;

Trajectory evaluation module: If continuous trajectory points are deleted in the adjacent area, the Kalman filter and the retained trajectory points are used to predict the position of the deleted points, and the error range between the predicted position and the observed position is evaluated. If the error is less than the threshold, it is determined that there is a map error at that location;

Missing road segment generation module: The deleted points are used as the input of the map generator. According to the calculated turning point positions, the missing road segments are divided into a series of intervals. The linear regression model is used to calculate the line segments passing through the turning points within the intervals.

Preferably, in the regional windowing module, the geographical area is first divided into grid units;

If a vehicle does not spend a predetermined travel time in a grid cell, the vehicle is not allowed to transition from that grid cell;

In each grid cell, a variation of the DP algorithm is used to smooth the trajectory, replacing the original trajectory with an approximated line segment;

If the replacement does not meet the specified error requirement, the original problem is recursively divided into two sub-problems by using the selected position point as the partition point, and then it is judged whether the replacement meets the specified error requirement until the error between the approximate trajectory and the original trajectory is lower than the specified error threshold;

The DP algorithm uses orthogonal Euclidean distance as the error metric to maintain the directional trend in the approximate trajectory;

Limit the velocity variation in a grid cell by removing partition points whose distance is greater than a threshold.

Preferably, in the map matching module, in the map matching stage, the smoothed GPS points are obtained from the region windowing step as input, and the smoothed GPS points are mapped to road segments on the digital map, and a hidden Markov model is used to determine a road segment sequence corresponding to a timestamp sequence of the GPS raw data;

A hidden Markov model is a discrete-time Markov process with candidate states and observations;

Use the index grid to search for candidate states, each candidate state is the point closest to the observation point in the road segment, and generates an observation probability The observation probability/> Defined as the GPS sampling point p _i and the candidate point calculated based on the Gaussian noise model/> Possibility of matching:

where σ is the standard deviation and d is defined as p _i and The projection distance between them, _pi is the sampling point at time i, /> is the jth candidate point of _pi ;

in, is the jth candidate road segment of p _i , c is the edge/> For any point on , dist( _pi ,c) is the Euclidean distance between _pi and c;

The hidden Markov model allows transitions from the previous candidate state to the current candidate state, and the transitions are controlled by transition probabilities;

As a rule of thumb, the Hidden Markov Model assumes that the shortest path between consecutive candidate states has a transition probability

Therefore, the transition probability The calculation is as follows:

in, is the candidate point of the current observation; /> is the candidate point of the previous observation; D is the point from/> To/> The absolute value of the difference between the shortest path length and the Euclidean distance between observations;

Then, an online Viterbi decoding algorithm is used to find the maximum likelihood sequence of the road segments corresponding to the variable sliding window of the input sequence.

Preferably, in the probability fluctuation detection module, by defining the observation probability and the transition probability, a hierarchical graph is gradually constructed by adding new nodes and weighted edges after receiving the GPS sampling points;

If the matching accuracy decreases when adding new GPS samples to the layer map, it is considered that there is a measurement error or map error;

Given a set of candidate points, the hidden Markov model will calculate the maximum likelihood path using the Viterbi decoding algorithm;

When the candidate set contains the true location of the observation, the hidden Markov model infers the correct path;

When there are map errors or measurement errors, the shortest path between two consecutive candidates is not the true path and will be circuitous;

The collected points that do not contain the true position in the candidate set are regarded as low-quality points, and the detection model will delete the detected low-quality points;

The calculation process of the Viterbi algorithm is to maximize the product of the observation probability and the transition probability when adding new GPS sampling points;

Sampling errors or map errors cause fluctuations in the amplitude of the optimal decoding probability;

Take the logarithm of the original value to make the fluctuation more obvious;

When the sampling of newly added points causes the fluctuation of the matching probability to exceed the preset threshold, the newly added points are deleted;

Limit the number of consecutive points removed when there are map errors;

When a series of consecutive sample points in an area are removed beyond a limit, the algorithm evaluator will evaluate the unmatched samples to detect whether there are map errors and, if so, use the map generation model to fit the missing roads.

Compared with the prior art, the present invention has the following beneficial effects:

1. The present invention innovatively proposes a map matching framework that can detect map errors and delete low-quality sampling points, which can be combined with a map matching algorithm based on a hidden Markov model to correct the matching results and improve their matching accuracy;

2. Since the previous map matching algorithm did not take into account the factor of map error, it would cause matching interruption and other problems in the actual application process. The present invention uses the sampled trajectory to detect and update the map database during the matching process, avoiding the previous map update process that requires a lot of manpower consumption;

3. Based on the matched locations, the present invention can predict the traffic conditions around a specific area and recommend upcoming points of interest to users.

BRIEF DESCRIPTION OF THE DRAWINGS

Other features, objects and advantages of the present invention will become more apparent from the detailed description of non-limiting embodiments made with reference to the following drawings:

FIG1 is an application architecture diagram of the present invention;

Fig. 2 is a diagram of the matching process of the present invention;

Figure 3 is a diagram of the trajectory error after window smoothing;

FIG4 is a schematic diagram of candidate point selection;

FIG5 is a schematic diagram of the decoding probability fluctuation within a trajectory.

Figure symbols: Moving vehicles with GPS sensors represents moving vehicles with sensors; Wireless network represents wireless network; GPS records represents sampling records; Data center represents data center; Route planning represents route recommendation; Traffic estimation represents traffic flow estimation; Point of interest represents point of interest; End devices running LBS represents terminal devices running location-based services; Map database represents map database; Windowing represents window technology; Map matching represents map matching; Detection model represents detection model; Evaluation model represents evaluation model Generation model represents generation model; With windowing represents the use of window technology; Without windowing represents the use of window technology; CDF represents the cumulative distribution of position error probability; Radius r represents the candidate radius; Sequence number of points represents the sequence number of sampling points; Variation of probability represents probability fluctuation.

Detailed ways

The present invention is described in detail below in conjunction with specific embodiments. The following embodiments will help those skilled in the art to further understand the present invention, but are not intended to limit the present invention in any form. It should be noted that, for those of ordinary skill in the art, several changes and improvements can also be made without departing from the concept of the present invention. These all belong to the protection scope of the present invention.

The embodiment of the present invention discloses a map matching correction method based on hidden Markov multi-noise perception, as shown in FIG1 and FIG2, comprising the following steps:

Regional windowing step: By gridding the region, the irregular drift of the trajectory is limited and a smooth trajectory is obtained. First, the geographical area is divided into grid cells;

If a vehicle does not spend a predetermined travel time in a grid cell, the vehicle is not allowed to transition from that grid cell;

In each grid cell, a variation of the DP algorithm is used to smooth the trajectory, replacing the original trajectory with an approximate line segment. If the replacement does not meet the specified error requirement, the original problem is recursively divided into two sub-problems by using the selected position point as the partition point, and then judging whether the replacement meets the specified error requirement until the error between the approximate trajectory and the original trajectory is below the specified error threshold. The DP algorithm uses orthogonal Euclidean distance as the error metric to maintain the directional trend in the approximate trajectory. The velocity variation in the grid cell is limited by removing partition points with a distance greater than the threshold. Figure 3 shows the cumulative distribution function (CDF) distribution of the position error of the collected GPS data. DP is the full name of Douglas–Peucker in English, and its Chinese translation is Douglas-Peucker algorithm.

Map matching step: The smoothed trajectory is input into the hidden Markov model with deleted points and map correction framework for matching. In the map matching stage, the smoothed GPS points are taken from the regional windowing step as input and mapped to the road segments on the digital map. The hidden Markov model is used to determine the road segment sequence corresponding to the timestamp sequence of the GPS raw data. The hidden Markov model is a discrete-time Markov process with candidate states and observations. An index grid is used to search for candidate states, as shown in Figure 4. Each candidate state is the point closest to the observation point in the road segment and generates an observation probability. The observation probability/> Defined as the GPS sampling point p _i and the candidate point calculated based on the Gaussian noise model/> Possibility of matching:

where σ is the standard deviation and d is defined as p _i and The projection distance between them, _pi is the sampling point at time i, /> is the jth candidate point of _pi .

in, is the jth candidate road segment of p _i , c is the edge/> For any point on , dist( _pi ,c) is the Euclidean distance between _pi and c.

The hidden Markov model allows transitions from the previous candidate state to the current candidate state, and the transition is controlled by the transition probability. As a rule of thumb, the hidden Markov model assumes that the shortest path between consecutive candidate states has a transition probability

Therefore, the transition probability The calculation is as follows:

in, is the candidate point of the current observation; /> is the candidate point of the previous observation; D is the point from/> To/> The absolute value of the difference between the shortest path length and the Euclidean distance between observations.

Then, an online Viterbi decoding algorithm is used to find the maximum likelihood sequence of the road segments corresponding to the variable sliding window of the input sequence.

Probability fluctuation detection step: during the matching process, the fluctuation of the Viterbi decoding probability of each observation point is calculated; if the fluctuation amplitude exceeds the threshold, the current observation point is deleted.

By defining the observation probability and transition probability, a hierarchical graph is gradually constructed by adding new nodes and weighted edges after receiving GPS sampling points. If the matching accuracy decreases when adding new GPS samples to the hierarchical graph, it is considered that there is a measurement error or map error. Given a set of candidate points, the hidden Markov model will use the Viterbi decoding algorithm to calculate the maximum likelihood path. When the candidate set contains the true location of the observation, the hidden Markov model infers the correct path. When there is a map error or measurement error, the shortest path between two consecutive candidates is not the true path and will be circuitous. The collection points whose candidate set does not contain the true location are regarded as low-quality points, and the detection model will delete the detected low-quality points. The calculation process of the Viterbi algorithm is to maximize the product of the observation probability and the transition probability when adding new GPS sampling points. Sampling errors or map errors cause fluctuations in the amplitude of the optimal decoding probability. Take the logarithm of the original value to make the fluctuation more obvious. When sampling a newly added point causes the fluctuation of the matching probability to exceed the preset threshold, the newly added point is deleted. Since the map error will cause the decoding probability fluctuation of all subsequent points to exceed the threshold, it is necessary to limit the number of consecutively removed points. When a series of consecutive sample points in an area are removed beyond a limit, the algorithm evaluator will evaluate the unmatched samples to detect whether there are map errors and, if so, use the map generation model to fit the missing roads.

Trajectory evaluation steps: If continuous trajectory points are deleted in the adjacent area, the Kalman filter and the retained trajectory points are used to predict the position of the deleted points, and the error range between the predicted position and the observed position is evaluated. If the error is less than the threshold, it is determined that there is a map error in this sampling trajectory.

A series of GPS points that are continuously removed from the detection model are used as input, and the quality of the entire sequence is evaluated to determine the reason for removal. The motion pattern of this series of removed GPS samples is evaluated under position and speed constraints. If the detected anomaly is caused by a motion pattern that does not conform to the actual driving situation, the change in matching probability is considered to be caused by measurement error, and the corresponding point is deleted; the remaining points are re-added to the matching sequence for continued matching. If the removed points are allowed to form a driving pattern in the evaluation model, the removed GPS sample points are restored and the unmatched points are used to generate the missing roads. The Kalman filter is used to predict the direction and position of the vehicle, and then the estimated point is used as a new matching point to determine whether there is an anomaly. The speed and direction information of the road section adjacent to the sampling point is used as the input of the motion trajectory physical model to calculate the ideal position of the vehicle at the next moment, and the sampled trajectory direction and speed information is used as the motion model input to calculate the position at the next moment as the measurement value. Based on the error between the weighted estimate and the true value of the system, the Kalman gain is calculated, and the position estimate at the next moment is obtained as follows:

xt _|t ＝ _{Ktzt +} ( _IKtH )xt _|t-1

Where xt _|t is the system estimate, _xt|t-1 is the ideal system state value, _zt is the measured value, _Kt is the Kalman gain, I is the identity matrix, and H is the state space transformation matrix.

The predicted position value is compared with the sampled position value, and the average distance between the predicted position value and the sampled position value is calculated. If the distance is less than the threshold Δd, it is considered that the sampling is caused by a map error.

Steps for generating missing road segments: Use the deleted points as the input of the map generator, divide the missing road segments into a series of intervals according to the calculated turning point positions, and use the linear regression model to calculate the line segments passing through the turning points within the intervals.

The digital map consists of an attributed undirected graph; intersections are represented as vertices with degree greater than two, and road segments are represented as a series of edges; bidirectional roads are considered as single paths; high-order attributes are defined to supplement the graph; geometric features are displayed as part of the map description; and local geometric shape information about roads is provided. A map generation model based on clustering technology is used to automatically infer road and traffic characteristics. The map generation model fits the unmatched GPS sampling points, and the generated topological structure is close to the actual missing roads. According to the location of the turning point, the unmatched GPS points are divided into different intervals. The distance of the turning point is measured by the Euclidean distance variable of the perpendicular Euclidean distance. In each segmented part, a linear regression model is used to fit the missing roads. In order to determine the location of the turning point, parameters θ _G and d _G are set. The first and last points in the sequence are connected, and then all other points are projected to the connecting line. If the specified projection distance is greater than the threshold d _G , the point with the specified distance is the corner point of the real road segment. The points with the specified projection distance are connected to the first and last points respectively, and the angle between the connecting lines is continued to be calculated; if the angle is greater than the threshold Δ _G , the sequence is divided into two parts and iterated.

The embodiment of the present invention discloses a multi-noise-aware map matching and correction framework based on a hidden Markov model, as shown in FIG1 , which shows a high-level system model of a typical location-based service.

1. Framework application: In most ubiquitous computing applications, the measured position of a mobile vehicle is reported to a server via wireless communication. The sampling interval varies in the same trajectory, depending on the driving environment. If there are too many outliers in the GPS trajectory, filtering preprocessing such as median filtering, Kalman filtering, and particle filtering is required. The server runs a map matching algorithm that uses noisy GPS points to find the actual road section where the user is driving. Once the driving route is determined, other LBS applications can query the results to meet their requirements. For example, based on the matched locations, traffic conditions around a specific area can be predicted, and upcoming points of interest can be recommended to users. The full name of LBS in English is Location Based Services, and the Chinese translation is location-based services.

2. Matching process:

As shown in Figure 2, the processing flow of the invention framework is detailed. In order to save energy while driving, low-energy devices are usually used to collect and transmit GPS records. These collection devices may have problems with back-and-forth conversion. Therefore, we first use windowing technology to smooth the trajectory data. After smoothing, the trajectory data without back-and-forth conversion is output and can be sent as input to the map matching module. This patent regards map matching and map updating as a collaborative optimization process.

Specifically, when the matching result accuracy is low, the framework proposed in this invention evaluates whether it is caused by GPS measurement error or map error. If the cause is the first factor, the outliers in the GPS trajectory can be simply deleted or calibrated. Otherwise, the missing segments are generated using a generator, which are then used to correct the matching results and update the map database. This process improves map matching accuracy and map quality by dynamically detecting map errors and automatically updating the map database, and prevents detours and matching interruptions during the matching process.

The system includes the following modules:

(1) Regional windowing module: By gridding the region, the irregular drift of the trajectory is limited and a smooth trajectory is obtained.

The first module is a regional windowing template. In order to simplify the smoothing process, the geographic area is first divided into uniform square grid cells G of a fixed size. If the vehicle does not spend enough driving time in the grid cell, the vehicle is not allowed to transition from the grid cell. In each grid cell, this patent uses a variant of the Douglas–Peucker (DP) algorithm to smooth the trajectory, which is usually used to simplify the trajectory. The basic idea is to replace the original trajectory with an approximate line segment. If the replacement does not meet the specified error requirements, it will recursively divide the original problem into two sub-problems by selecting the position point with the most errors as the partition point. This process will continue until the error between the approximate trajectory and the original trajectory is lower than the specified error threshold. The goal of the DP algorithm is to use orthogonal Euclidean distance as an error metric to maintain the directional trend in the approximate trajectory. The implementation of the present invention is different from the previous method because the present invention removes partition points with a distance greater than the threshold to limit the speed change in one grid cell. Figure 3 shows the cumulative distribution function (CDF) distribution of the position error of the collected GPS data. DP is the full name of Douglas–Peucker in English, and its Chinese translation is Douglas-Peucker algorithm.

(2) Map matching module: The smoothed trajectory is input into the hidden Markov model with deleted points and the map correction frame for matching.

In the map matching stage, a series of smoothed GPS points from the regional windowing module are taken as input and mapped to road segments on the digital map. The framework proposed in this invention uses a hidden Markov model (HMM) to determine the road segment sequence corresponding to the timestamp sequence of the GPS raw data. The HMM is a discrete-time Markov process with a set of candidate states and observations. The present invention uses an index grid to search for candidate states, as shown in Figure 4. Each state is the point closest to the observed point in the road segment and produces an observation probability, which is defined as the probability of the GPS sampling point p _i and the candidate point calculated based on the Gaussian noise model. Possibility of matching:

where σ is the standard deviation and d is defined as p _i and The projection distance between them, _pi is the sampling point at time i, /> is the jth candidate point of _pi .

in, is the jth candidate road segment of p _i , c is the edge/> For any point on , dist( _pi ,c) is the Euclidean distance between _pi and c.

HMM allows transitions from the previous candidate state to the current candidate state, and this transition is controlled by the transition probability. Based on experience, HMM assumes that the shortest path between two consecutive candidate states has a larger transition probability. Therefore, the transition probability is usually calculated as follows:

in, and/> are the candidate points of the previous observation and the current observation respectively, and D is the candidate point from/> To/> The absolute value of the difference between the shortest path length and the Euclidean distance between observations. Then, using an online Viterbi decoding algorithm, the maximum likelihood sequence of the path segments corresponding to a variable sliding window of the input sequence can be found.

(3) Probability fluctuation detection module: During the matching process, the fluctuation of the Viterbi decoding probability of each observation point is calculated; if the fluctuation amplitude exceeds the threshold, the current observation point is deleted.

By defining observation probabilities and transition probabilities, a hierarchical graph can be gradually constructed by adding new nodes and weighted edges after receiving GPS sample points. This model aims to improve the robustness and matching accuracy of HMM-based map matching algorithms in the face of realistic and complex scenarios. In other words, if the matching accuracy decreases when adding new GPS samples to the hierarchical graph, it is considered that there is a measurement error or map error. Given a set of candidate points, the HMM will calculate the maximum likelihood path using the Viterbi decoding algorithm. However, a disadvantage of this approach is that it is unaware of the quality of the current observations. The HMM can only infer the correct path if the candidate set contains the true location of the observation. When there is a map error or measurement error, the shortest path between two consecutive candidates can never be the true path and will result in a long detour.

The present invention regards the collected points whose candidate set does not contain the real position as low-quality points, which may be caused by measurement error or map error. The detection model will delete the detected low-quality points. The calculation process of the Viterbi algorithm is to maximize the product of observation probability and transition probability when adding new GPS sampling points. Since map errors or measurement errors usually lead to lower observation probability and transition probability, and the maximum value of Viterbi decoding probability is related to observation probability and transition probability, sampling error or map error usually causes large fluctuations in the optimal decoding probability. Figure 5 shows the change of the difference between the maximum matching probability of the current GPS point and the previous GPS point in a trajectory. The present invention takes the logarithm of the original value to make the fluctuation more obvious. These points can be deleted when they cause a large change in matching probability, which is usually caused by map error or measurement error. If there is a map error, this process may delete all subsequent GPS sampling points. Therefore, we should limit the number of consecutively removed points. Limit the number of consecutively removed points due to map errors. When a series of consecutive sampling points in a certain area are removed, the algorithm evaluator will evaluate these unmatched samples to detect whether there is a map error, and if so, the map generation model can be used to fit the missing road.

(4) Trajectory evaluation module: If continuous trajectory points are deleted in the adjacent area, the Kalman filter and the retained trajectory points are used to predict the position of the deleted points, and the error range between the predicted position and the observed position is evaluated. If the error is less than the threshold, it is determined that there is a map error at that location.

This module takes as input a series of GPS points that are continuously removed from the detection model and evaluates the quality of the entire sequence to determine whether they were removed due to map errors or measurement errors. This patent evaluates the movement pattern of this series of removed GPS samples under position and speed constraints. If the detected anomaly is caused by a movement pattern that does not conform to the actual driving situation, the large change in the matching probability is considered to be caused by the measurement error, and the corresponding point is deleted. The remaining points are rejoined to the matching sequence to continue matching. If the driving pattern formed by these removed points is allowed in the evaluation model, the removed GPS sample points are restored and these unmatched points are used to generate the missing roads. This patent uses Kalman filtering to predict the vehicle's direction of movement and position, and then uses these estimated points as new matching points to determine whether there are anomalies.

The present invention uses the speed and direction information of the road section near the sampling point as the input of the motion trajectory physical model to calculate the ideal position of the vehicle at the next moment, and uses the sampled trajectory direction and speed information as the motion model input to calculate the position at the next moment as the measurement value. Based on the minimum error between the weighted estimate and the true value of the system, the Kalman gain is calculated, and the estimated value of the position at the next moment is obtained as follows:

xt _|t ＝ _{Ktzt +} ( _IKtH )xt _|t-1

Where _xt|t is the system estimate, _xt|t-1 is the ideal state value of the system, _zt is the measurement value, _Kt is the Kalman gain, I is the identity matrix, and H is the state space conversion matrix. The position prediction value is compared with the position sampling value, and the average distance between them is calculated. If the distance is less than the threshold Δd, it is considered that the sampling of this segment is caused by map error.

(5) Missing road segment generation module: The deleted points are used as the input of the map generator. According to the calculated turning point positions, the missing road segments are divided into a series of intervals. The linear regression model is used to calculate the line segments passing through the turning points within the intervals.

Digital maps are usually composed of attributed undirected graphs. Intersections are represented as vertices with degree greater than 2, and road segments are represented as a series of edges. Because the graph is undirected, the path has no direction. Therefore, a two-way road is considered a single path. Higher-order attributes can be defined to supplement the graph. Geometric features such as width and curvature can be displayed as part of the map description. These features are critical for road safety applications because they provide detailed information about the local geometry of the road. It is much easier to infer the structure of the road network than these high-order road segment information. In addition, this patent uses a map generation model based on clustering technology with general applicability to automatically infer road and traffic characteristics (such as speed limit, road type and lane structure). The goal of the map generation model is to fit those GPS sampling points that cannot be matched, and generate missing roads with a topological structure closer to the actual one. The challenge of map generation is that the measurement error causes the sampling points to not fall accurately on the road. If the GPS sampling points are directly used as the intersection of the road segment, the generated road segment will appear jagged. According to the position of the inflection point, the unmatched GPS points are divided into different sequences (similar to several subsequences). The maximum distance of the turning point is measured by a Euclidean distance variable called the perpendicular Euclidean distance. In each segmented part, this patent uses a linear regression model to fit the missing roads. In order to determine the location of the turning point, two parameters θ _G and d _G are set. Connect the first and last points in the sequence, and then project all other points to this line. If the maximum projection distance is greater than the threshold d _G , the point with the maximum distance may be the corner point of the real road segment. Continue to calculate the angle between the point with the maximum projection distance and the first and last points. If the angle is also greater than the threshold θ _G , the sequence is divided into two parts. This process can be iteratively completed, and the threshold d _G of the projection distance decreases as the total distance of the points in the interval decreases, and the angle threshold increases as the distance decreases.

3. Algorithm implementation:

The present invention applies the algorithm to the open source map matching platform GraphHopper, and the map network information comes from OpenStreetMap. On the simulation platform, this patent combines the implemented framework with three classic map matching based on the hidden Markov model, and conducts a large number of experiments on a trajectory data set of 79,670.6 km in four cities, verifying the accuracy, recall rate and other indicators of the matching results. The experimental results show that after combining with the framework proposed by this patent, these indicators of the three algorithms are improved by about 20%. In addition, in terms of the proportion of trajectories with an accuracy higher than 95% and 90%, the algorithm proposed by this patent is improved by about 30% compared with the original matching algorithm based on the hidden Markov model. The framework detected 1,962 map errors on the Shanghai data set, randomly selected 200 trajectories, and manually verified the accuracy of the algorithm for map error detection. It was found that the accuracy rate was about 60% near residential areas in residential communities, and the accuracy rate reached about 80% on roads with dense road networks.

The invention greatly improves the accuracy of the map matching algorithm in complex traffic networks, and the algorithm of the invention can sense map errors, automatically correct the map matching results based on the sampled trajectories, and update the map database. These features improve the robustness and accuracy of the map matching algorithm.

The present invention first limits the irregular drift of the trajectory by gridding the region. The smoothed trajectory is input into a hidden Markov model with a deletion point and a map correction framework for matching. During the matching process, the fluctuation of the Viterbi decoding probability of each observation point is calculated. If the fluctuation amplitude exceeds the threshold, the current observation point is deleted. If continuous trajectory points are deleted in the adjacent area, the Kalman filter and the retained trajectory points are used to predict the position of the deleted point, and the error range of the predicted position and the observed position is evaluated. If the error is less than the threshold, it is determined that the position (the sampling trajectory section) has a map error. The deleted points are used as the input of the map generator, and the missing road sections are divided into a series of intervals according to the calculated inflection point positions. The linear regression model is used within the interval to calculate the line segment with the smallest error between the inflection points. Since the distance error between the evaluation position and the observation position is small, it means that the sampling quality is relatively high, and the fluctuation of the decoding probability is not caused by the sampling error, but by the map error.

Based on the hidden Markov model adopted by most current map matching algorithms, this paper proposes a map matching framework that is resistant to multiple noises and can handle low-precision trajectory sampling and map errors. The low precision here is different from the focus of the existing hidden Markov model. The current algorithm is based on the maximum likelihood estimation of the collaborative optimization of the observation probability and the transition probability under the constraint of the road network. However, it ignores the fact that the candidate radius may not contain the real candidate road section due to sampling errors.

The present invention is based on limiting the fluctuation amplitude of the Viterbi decoding algorithm and deleting sampling points with large fluctuation amplitudes. For a series of adjacent deleted points, the movement position and direction of the deleted points are estimated based on the Kalman filter and the current retained points, and compared with the situation of the sampling points, and the presence of map errors is identified according to the error range. When a map error is detected, the deleted points are used as inputs of the map generator, and the missing road sections are divided into a series of intervals according to the calculated inflection point positions, and the line segments with the smallest errors between the inflection points are calculated within the intervals using a linear regression model.

The present invention relates to intelligent transportation, trajectory processing, and map matching algorithms, and discloses a map matching framework based on a hidden Markov model that is resistant to multiple noises, can process low-precision GPS sampling trajectories, and detect and correct errors existing on current electronic maps. In the era of big data, we can sample a large amount of GPS location data, which is very important for real-time tracking of the current location of the vehicle. However, due to the errors in GPS trajectory sampling itself, a reliable algorithm is needed to accurately correspond it to the road network to support other traffic applications, such as predicting whether a certain road section will be blocked. At present, due to the accelerated urbanization process, countries are constantly building new roads, which makes the road network update speed increase every year. Traditional maps are slow to update and rely heavily on manpower, so when they are applied to location-based services, they are often unable to provide reliable positioning and navigation services due to the problem of missing road sections.

Therefore, sampling errors and map errors are the biggest challenges currently faced by map matching algorithms. Most current matching algorithms are based on hidden Markov models, which do not take into account the problem that there are no real road sections in the candidate set due to sampling errors and the map is inaccurate. In order to solve the above problems, this patent proposes a map matching and map correction framework that is resistant to multiple noises based on the hidden Markov model, correcting the map matching results to improve the accuracy of the map matching algorithm based on the hidden Markov model.

Those skilled in the art know that, in addition to realizing the system and its various devices, modules, and units provided by the present invention in a purely computer-readable program code, it is entirely possible to realize the same functions in the form of logic gates, switches, application-specific integrated circuits, programmable logic controllers, and embedded microcontrollers by logically programming the method steps. Therefore, the system and its various devices, modules, and units provided by the present invention can be considered as a hardware component, and the devices, modules, and units included therein for realizing various functions can also be regarded as structures within the hardware component; the devices, modules, and units for realizing various functions can also be regarded as both software modules for realizing the method and structures within the hardware component.

The above describes the specific embodiments of the present invention. It should be understood that the present invention is not limited to the above specific embodiments, and those skilled in the art can make various changes or modifications within the scope of the claims, which does not affect the essence of the present invention. In the absence of conflict, the embodiments of the present application and the features in the embodiments can be combined with each other arbitrarily.

Claims (8)

1. The map matching correction method based on the hidden Markov multi-noise perception is characterized by comprising the following steps of:

a region windowing step: by gridding the region, the irregular drift of the track is limited, and a smooth track is obtained;

Map matching step: inputting the smoothed track into a hidden Markov model with a deleting point and a map correcting frame for matching;

Probability fluctuation detection step: calculating fluctuation conditions of the Viterbi decoding probability of each observation point in the matching process; if the fluctuation amplitude exceeds the threshold value, deleting the current observation point;

Track evaluation step: if the continuous track points are deleted in the adjacent area, predicting the deleted point positions by using a Kalman filter and the reserved track points, evaluating the error range of the predicted positions and the observed positions, and if the error is smaller than a threshold value, judging that the map error exists at the section of sampling track;

A missing road section generation step: taking the deleted points as the input of a map generator, dividing the deleted road sections into a series of sections according to the calculated inflection point positions, and calculating line segments passing through the inflection points in the sections by using a linear regression model;

In the map matching step, in the map matching stage, smooth GPS points obtained from the regional windowing step are taken as input, the smooth GPS points are mapped to road segments on a digital map, and a hidden Markov model is used for determining a road segment sequence corresponding to a time stamp sequence of GPS original data;

The hidden markov model is a discrete time markov process with candidate states and observations;

searching candidate states using an index grid, each candidate state being a point closest to an observation point in a road segment, and generating an observation probability The observation probability/>Is defined as a GPS sampling point p _i and a candidate point/>, calculated based on a Gaussian noise modelPossibility of matching:

Wherein σ is the standard deviation and d is defined as p _i and The projection distance between the two points, p _i is the sampling point at the moment i,/>Is the j-th candidate point of p _i;

Wherein, Is p _i th candidate road segment, c is edge/>At any point above, dist (p _i, c) is the Euclidean distance between p _i and c;

the hidden markov model allows a transition from a previous candidate state to a current candidate state, and the transition is controlled by a transition probability;

empirically, the hidden Markov model assumes that the shortest path between successive candidate states has transition probabilities

Thus, transition probabilityThe calculation is as follows:

Wherein, Is a candidate point of current observation; /(I)Is a candidate point for the previous observation; d is from/>To/>An absolute value of a difference between the shortest path length and the euclidean distance between observations;

and then, using an online Viterbi decoding algorithm to find the maximum likelihood sequence of the road section corresponding to the variable sliding window of the input sequence.

2. The map matching correction method based on hidden markov multi-noise perception according to claim 1, wherein in the region windowing step, a geographical region is first divided into grid cells;

If the vehicle does not spend a predetermined travel time in the grid cell, the vehicle is not allowed to transition from the grid cell;

In each grid cell, a variation of the DP algorithm is used to smooth the trajectory, replacing the original trajectory with an approximate line segment;

if the replacement does not meet the specified error requirement, recursively dividing the original problem into two sub-problems by taking the selected position point as a dividing point, and judging whether the replacement meets the specified error requirement or not until the error between the approximate track and the original track is lower than a specified error threshold;

The DP algorithm uses the orthogonal Euclidean distance as an error measure to keep the direction trend in the approximate track;

by removing partition points whose distance is greater than a threshold value, speed variation in the grid cells is limited.

3. The map matching correction method based on hidden markov multi-noise perception according to claim 1, wherein in the probability fluctuation detection step, a hierarchical map is gradually constructed by adding new nodes and weighted edges after receiving GPS sampling points by defining observation probabilities and transition probabilities;

If the matching accuracy is reduced when a new GPS sample is added in the layered graph, the measurement error or map error is considered to exist;

Given the candidate point set, the hidden Markov model will calculate the maximum likelihood path using the Viterbi decoding algorithm;

When the candidate set contains the observed real position, the hidden Markov model deduces the correct path;

when there is a map error or a measurement error, the shortest path between two consecutive candidates is not a real path, and may detour;

taking the acquisition points of which the candidate set does not contain the real position as low-quality points, and deleting the detected low-quality points by a detection model;

The calculation process of the Viterbi algorithm is to maximize the product of the observation probability and the transition probability when a new GPS sampling point is added;

the sampling error or map error causes amplitude fluctuation of the optimal decoding probability;

taking the logarithm of the original value to make the fluctuation more obvious;

deleting the newly added point when the fluctuation of the matching probability caused by the newly added point sampling exceeds a preset threshold value;

Limiting the number of consecutive removal points when there is a map error;

When a series of consecutive sampling points for a region is removed beyond a limit number, the algorithm evaluator will evaluate the unmatched samples, detect if there is a map error, and if so, use a map generation model to fit the missing road.

4. The map matching correction method based on hidden markov multi-noise perception according to claim 1, wherein in the trajectory evaluation step, a series of GPS points continuously removed from the detection model are taken as input, and the quality of the entire sequence is evaluated, and the reason for the removal is judged;

evaluating the series of motion patterns under position and velocity constraints that remove GPS samples;

if the detected abnormality is caused by a motion pattern that does not conform to the actual driving situation, then the change in the matching probability is considered to be caused by a measurement error, and the corresponding point is deleted; the rest points are added into the matching sequence again to continue matching;

Restoring the removed GPS sampling points and generating a missing road by using points which cannot be matched if the removed points are allowed to form a driving mode in the evaluation model;

Predicting the movement direction and position of the vehicle by using Kalman filtering, and then judging whether an abnormality exists by taking the estimated points as new matching points;

Taking the speed and direction information of the road section adjacent to the sampling point as the input of a motion trail physical model, calculating the ideal position of the vehicle at the next moment, and taking the sampled trail direction and speed information as the input of the motion model to calculate the position at the next moment as a measured value;

based on the error between the weighted estimated value and the true value of the system, the Kalman gain is calculated, and the position estimated value at the next moment is obtained as follows:

x_t|t＝K_tz_t+(I-K_tH)x_t|t-1

Wherein x _t|t is a system estimation value, x _t|t-1 is a system ideal state value, z _t is a measurement value, K _t is Kalman gain, I is an identity matrix, and H is a state space conversion matrix;

Comparing the position predicted value with the position sampling value, calculating the average distance between the position predicted value and the position sampling value, and if the distance is smaller than the threshold value delta d, considering the sampling to be caused by map errors.

5. The hidden markov based map matching correction method according to claim 1, wherein in the missing road section generating step, a digital map is composed of an attributed undirected graph; the intersection points are represented as vertices with a degree greater than two, and the road segments are represented as a series of edges; treating the bi-directional link as a single path; defining high-order attributes to supplement the graph; the geometric features are displayed as part of the map description; providing local geometry information about the road;

automatically deducing road and traffic characteristics by using a map generation model based on a clustering technology;

Fitting the GPS sampling points which cannot be matched by the map generation model, wherein the generated topological structure is close to an actual missing road;

dividing the GPS points which cannot be matched into different sections according to the positions of the inflection points;

The distance of the inflection point is measured by a euclidean distance variable of the vertical euclidean distance;

at each segment, fitting the missing road using a linear regression model;

In order to determine the position of the turning point, parameters θ _G and d _G are set;

connecting a first point and a last point in the sequence, and then projecting all other points to the connecting line;

If the specified projection distance is greater than the threshold d _G, the point with the specified distance is a corner point of the real road segment;

connecting points with specified projection distances with a first point and a last point respectively, and continuously calculating angles between the connecting points; if the angle is greater than the threshold θ _G, the sequence is split into two parts and iterated.

6. A hidden markov based multi-noise aware map matching correction system comprising the following modules:

region windowing module: by gridding the region, the irregular drift of the track is limited, and a smooth track is obtained;

And a map matching module: inputting the smoothed track into a hidden Markov model with a deleting point and a map correcting frame for matching;

Probability fluctuation detection module: calculating fluctuation conditions of the Viterbi decoding probability of each observation point in the matching process; if the fluctuation amplitude exceeds the threshold value, deleting the current observation point;

Track evaluation module: if the continuous track points are deleted in the adjacent area, predicting the positions of the deleted points by using a Kalman filter and the reserved track points, evaluating the error range of the predicted positions and the observed positions, and if the error is smaller than a threshold value, judging that the positions have map errors;

the missing road section generation module: taking the deleted points as the input of a map generator, dividing the deleted road sections into a series of sections according to the calculated inflection point positions, and calculating line segments passing through the inflection points in the sections by using a linear regression model;

In the map matching module, in the map matching stage, smooth GPS points are obtained from the regional windowing step as input, the smooth GPS points are mapped to road segments on a digital map, and a hidden Markov model is used for determining a road segment sequence corresponding to a time stamp sequence of GPS original data;

The hidden markov model is a discrete time markov process with candidate states and observations;

searching candidate states using an index grid, each candidate state being a point closest to an observation point in a road segment, and generating an observation probability The observation probability/>Is defined as a GPS sampling point p _i and a candidate point/>, calculated based on a Gaussian noise modelPossibility of matching:

Wherein σ is the standard deviation and d is defined as p _i and The projection distance between the two points, p _i is the sampling point at the moment i,/>Is the j-th candidate point of p _i;

Wherein, Is p _i th candidate road segment, c is edge/>At any point above, dist (p _i, c) is the Euclidean distance between p _i and c;

the hidden markov model allows a transition from a previous candidate state to a current candidate state, and the transition is controlled by a transition probability;

empirically, the hidden Markov model assumes that the shortest path between successive candidate states has transition probabilities

Thus, transition probabilityThe calculation is as follows:

Wherein, Is a candidate point of current observation; /(I)Is a candidate point for the previous observation; d is from/>To/>An absolute value of a difference between the shortest path length and the euclidean distance between observations;

and then, using an online Viterbi decoding algorithm to find the maximum likelihood sequence of the road section corresponding to the variable sliding window of the input sequence.

7. The hidden markov based multi-noise aware map matching correction system of claim 6 wherein in the region windowing module, the geographic region is first divided into grid cells;

If the vehicle does not spend a predetermined travel time in the grid cell, the vehicle is not allowed to transition from the grid cell;

In each grid cell, a variation of the DP algorithm is used to smooth the trajectory, replacing the original trajectory with an approximate line segment;

if the replacement does not meet the specified error requirement, recursively dividing the original problem into two sub-problems by taking the selected position point as a dividing point, and judging whether the replacement meets the specified error requirement or not until the error between the approximate track and the original track is lower than a specified error threshold;

The DP algorithm uses the orthogonal Euclidean distance as an error measure to keep the direction trend in the approximate track;

by removing partition points whose distance is greater than a threshold value, speed variation in the grid cells is limited.

8. The map matching correction system based on hidden markov multi-noise perception according to claim 6, wherein in the probability fluctuation detection module, a hierarchical map is gradually constructed by defining an observation probability and a transition probability and adding new nodes and weighted edges after receiving GPS sampling points;

If the matching accuracy is reduced when a new GPS sample is added in the layered graph, the measurement error or map error is considered to exist;

Given the candidate point set, the hidden Markov model will calculate the maximum likelihood path using the Viterbi decoding algorithm;

When the candidate set contains the observed real position, the hidden Markov model deduces the correct path;

when there is a map error or a measurement error, the shortest path between two consecutive candidates is not a real path, and may detour;

taking the acquisition points of which the candidate set does not contain the real position as low-quality points, and deleting the detected low-quality points by a detection model;

The calculation process of the Viterbi algorithm is to maximize the product of the observation probability and the transition probability when a new GPS sampling point is added;

the sampling error or map error causes amplitude fluctuation of the optimal decoding probability;

taking the logarithm of the original value to make the fluctuation more obvious;

deleting the newly added point when the fluctuation of the matching probability caused by the newly added point sampling exceeds a preset threshold value;

Limiting the number of consecutive removal points when there is a map error;

When a series of consecutive sampling points for a region is removed beyond a limit number, the algorithm evaluator will evaluate the unmatched samples, detect if there is a map error, and if so, use a map generation model to fit the missing road.