Keywords

1 Introduction

With the continuous progress of urbanization, the traffic in urban areas is tending to or has reached saturation. Traffic management departments often implement various road optimization adjustment and road limit line measures, in order to improve the intersection efficiency and the overall road network capacity. For example, many roads have been banned from crossing, banning U-turn and so on. As a result, the traffic information of the road network changes. However, due to the lag of the updating of electronic map, the updating of these information is not timely or insufficient coverage. And it often brings inconvenience to the public. Therefore, we need more timely and effective traffic network change information. This paper analyzes the characteristics of the trajectory of the floating vehicle on the basis of the trajectory data of the floating vehicle. Which can identify the current steering rules of the intersection, thus detecting the section of the change of the limit line, alleviating the urban traffic pressure and improving the efficiency of the public travel.

2 Vehicle Road Matching Algorithm Based on Angular Distance Weighting Model

The track data of floating vehicle contains a series point sequence set, which is arranged in sequence according to the GPS receiving time. The set point in each element includes a plurality of zodiac, respectively: the vehicle terminal number, latitude and longitude, direction, speed, data transmission time and vehicle type. In this paper, we derive the experimental data from the real-time trajectory data of 150 thousand floating vehicles collected by Fujian Traffic Information Center (Table 1).

Table 1. Track data contents of floating vehicles
Full size table

We construct this weight model on the basis of the vehicle trajectory data. Its principal component consists of two pieces: the angle difference and the distance difference between the vehicle and the road. In the whole evaluation process, different weights are set for the relative importance of the two section, and then we obtain the synthetic matching similarity of each section and matching road section.

2.1 Angle Similarity

The angular difference in the weight model refers to the difference between the direction value in the vehicle GPS data and the geographical orientation of the candidate section. The weight formula is expressed as:

$$\begin{aligned} W_{a} = \lambda F(\varDelta \delta ) \end{aligned}$$
(1)

In this formula, \(\lambda \) is the angle weighting coefficient, \(F(\varDelta \delta ) = \cos (\varDelta \delta ) \), \(\varDelta \delta \) is the angle between the direction value of the vehicle trajectory data (Eight values, each representing a direction) and the geographical orientation of the road.

2.2 Distance Similarity

The distance in the weight model refers to the spatial distance between the latitude and longitude coordinates of the vehicle GPS data and the candidate section. The weight formula is expressed as:

$$\begin{aligned} W_{d} = \beta / F(d) \end{aligned}$$
(2)

In this formula, \(\beta \) is represented as distance weighting coefficient, F(d) is the shortest distance from the matching point to the candidate section of the vehicle. Assumed that the longitude and latitude coordinates of the points to be matched are (x, y), the shortest distance is calculated as follows as:

$$\begin{aligned} F(d)=\frac{ x(lat_{to}-lat_{from}) + y(lon_{to}-lon_{from}) + lon_{to}lat_{from} - lon_{from}lat_{to} }{\sqrt{((lat_{to}-lat_{from})^{2}+(lon_{to}-lon_{from})^{2}}} \end{aligned}$$
(3)

The minimum distance is the vertical distance of the matched points to the candidate section. When the pedal falls on the road when matching, the shortest distance is what we ask for F(d). Otherwise, they are calculated separately. The smaller the F(d) values, the higher distance similarity of candidate segment is. Conversely, the lower the distance similarity will be.

2.3 Weighted Similarity

The weighted similarity of candidate segments can be expressed by angle similarity and distance similarity:

$$\begin{aligned} W_{s} = W_{a} + W_{d} = \lambda F(\varDelta \delta ) + \beta F(d) \end{aligned}$$
(4)

As shown in the formula, \(\lambda \) and \(\beta \) are respectively the weight of angle and distance, and they satisfy the constraint condition of \(\lambda + \beta = 1\). Angle similarity has a relatively greater impact on vehicle road matching. Through the matching of ten thousand vehicle trajectories data and mathematical induction, we can draw the following conclusions. In this formula, we set the angle weight R as 0.6, distance weigh B as 0.4. When \(\varDelta \delta \rightarrow 0 \), \( F(d) \rightarrow 0 \), the matching degree of candidate \(W_{s} \rightarrow max \) sections, the likelihood of matching points to the candidate segment is greatest.

3 Design of Road Steering Change Detection Algorithm

3.1 Trajectory Feature Recognition Based on Vehicle Steering Angle

In order to identify the intersection turning rules in the outlet network, the vehicle trajectory characteristics can be determined by analyzing the vehicle trajectory characteristics and the vehicle movement trends. When the floating vehicle that conforms to this particular track characteristic and movement state reaches 1/4 of the total data, the steering rules of the road section and intersection can be judged.

Design of Trajectory Feature Extraction Algorithm. The track characteristic recognition algorithm based on vehicle steering angle mainly tracks and analyzes the change of steering angle of track data points of floating vehicles. Because the trajectory of a single floating vehicle can not fully represent the vehicle’s running trend and state, so we make an algorithm, this algorithm is based on a 22 point trajectory by 3 adjacent receiving chronological ordering of the steering angle calculation, by using the change of steering angle calculation formula, assign to the state of the vehicle.

In order to describe the feature extraction algorithm explicitly, the definition is as follows:

Definition 1

(Change of steering angle). The steering angle refers to the angle based on the trajectory of the vehicle ordered before and after the two track point the direction of travel form, to the north of 0\(^\circ \).

Definition 2

(Steering undetermined table). The storage table of intersection steering rules is used as storage format, which is used to record the change of steering angle.

As the limited and one-sided of single track point information representation, the vehicle trajectory feature extraction algorithm is mainly for the spatial information of 3 adjacent track points before and after the vehicle is calculated. In a cross section of a road network, the path of the vehicle on the road is shown in Fig. 1. The four curves, which are connected by a single locus of the vehicle received by the time series, represent the four running states of the vehicle: straight, left turn, right turn, and u-turn.

Fig. 1.
figure 1

Vehicle running state at intersection

Full size image

Assume that \(p_{1},p_{2},...,p_{n} \) are the continuous trajectory point data of a vehicle over a period of time. Each point of \(p_{i}\) contains several attributes: time \(t_{i}\), speed \(d_{i}\), direction \( [lon_{i},lat_{i}] \), and coordinates. In the formula, \(lon_{i}\) represents the vehicle longitude coordinates, \(lon_{j}\) latitude coordinates, \( Agl(lon_{i},lat_{i}) \) is the angle formed by the northward direction and the vector \(\overrightarrow{p_{i}p_{j}} \) which is composed by point \(p_{i}\) and point \(p_{j}\).

$$\begin{aligned} \triangle \varTheta =Agl(p_{i-1},p_{i}) - Agl(p_{i},p_{i+1}) \end{aligned}$$
(5)

In the formula, \(\triangle \varTheta \) is composed of the difference between the vector formed by the angle of track points of the vehicle and the north direction. That is, the steering variation during vehicle operation. \(\triangle \varTheta \) values vary, the vehicle’s driving conditions are different, the specific circumstances shown in Fig. 2.

Fig. 2.
figure 2

The basis of judging between \(\triangle \varTheta \) and vehicle running state

Full size image

As shown in the diagram, the vehicle running state is divided into three types: the left turn of the vehicle, the right turn of the vehicle and the U-turn of the vehicle. The left turn and right turn are mainly judged by the change of the steering angle. In contrast, The vehicle ’s U-turn is more complex.

When the vehicle turns around, not only the change of the steering angle needs to meet the corresponding conditions, but also the relative distance has some characteristics.

$$\begin{aligned} |\overrightarrow{p_{i-1},p_{i+1}}| = |\overrightarrow{p_{i-1},p_{i}} + \overrightarrow{p_{i},p_{i+1}}|<max(\overrightarrow{p_{i-1},p_{i}}, \overrightarrow{p_{i},p_{i+1}}) \end{aligned}$$
(6)

In this formula, \( p_{i-1},p_{i},p_{i+1} \) represent the three contiguous points of the vehicle. When the vehicle is moving straight or left and right, the \(|\overrightarrow{p_{i-1},p_{i+1}}| \) at both ends must be greater than \(|\overrightarrow{p_{i-1},p_{i}}|\) and \(|\overrightarrow{p_{i},p_{i+1}}|\), which represent respectively as the distance from the starting point to the middle point and the distance from the middle point to the stopping point. The relative distance between them is growing positively. When the vehicle is in a U-turn, the running track of the vehicle will turn back. In this process, its relative driving distance is a negative growth state.

For a floating vehicle running in the network, if its running state meet to GPS trajectory point criterion in the sequence, then we can judge the steering and steering section of the vehicle. At the same time, according to the data storage format of the designed steering rules, we can increase the number of turns in the database of the steering rules by combining nodes and sections. As shown in this formula, if \(\{ p_{i-1},p_{i},p_{i+1} \}\) is a sequence of floating car points that satisfies the left turn condition in the table, and can be used to determine that the vehicle is moving from the current section to another.

Effective Determination of Steering Rules. The positioning system of a floating vehicle is prone to error when it is positioned under the influence of the outside environment such as the dense building area or the weather. If only the trajectory points of the voucher car are used to judge the actual turning rules of the intersection, the credibility of the results obtained is very low. In order to reflect the actual turning rules of the road network and deal with several floating vehicles at the same time, a mathematical statistic model is needed to determine the effectiveness of the turning rules.

$$\begin{aligned} C_{n,r_{i}} \ge M , \frac{C_{n,r_{i},r_{j}}}{ C_{n,r_{i}}} \ge \eta \end{aligned}$$
(7)

In this formula \( C_{n,r_{i}} \) represents the sum of the number of turns in the N network node with \(r_{i}\) as the same starting section. Among them, the experience value of M is 100. \(C_{n,r_{i},r_{j}}\) indicates the number of times a vehicle moves from the initial section \(r_{i}\) to the \(r_{i}\) section at the node N connection. \(\frac{C_{n,r_{i},r_{j}}}{ C_{n,r_{i}}}\) represents the proportion of specific steering, and the ratio of the empirical value \( \eta \) is 5%. As shown in Table 2 of the steering rules, at a crossing, if the ratio of a particular turn to the sum of all turns exceeds the set threshold A, then the steering rule can be determined to be valid; otherwise, the decision is invalid.

Table 2. Steering rules
Full size table

3.2 Change Detection of the Turning Rules for the Intersection

Whether the road network information changes or not depends on whether the information of the road map, the road network information and the vehicle data detected by the floating vehicle are consistent. The same goes for the change of rules at the intersection. The detection of the change of lane limit can be transformed to the comparison between the electronic map and the steering rule of the actual road network. The algorithm firstly extracts the rule list of the database stored in the database by node ID, and then traverses all the nodes. In this process, it can extract all the steering rules data of this node and process them one by one, and determine whether it is valid or not. If this validity is true, then the network topology information table obtained by searching the primary key map for querying the electronic map is consistent with the actual result, and that means the information has not changed. However, if the result is different, the change in the steering rules is indicated, and the change result is recorded and stored in a temporary list.

The pseudo code for the implementation of this algorithm is represented as follows:

figure a

The detection link of road steering limit change is mainly based on the original electronic map spatial data table and the actual road network steering rule table, and it needs to be queried through the primary key index. At the same time, it creates a new table that meets the requirements of the test to store the contrast results. The time complexity of the algorithm is expressed as (n), and the algorithm is scalable.

4 Conclusion

In this paper, an improved matching algorithm based on weight model and topological relation is proposed for real-time road change detection. We can use in different types of vehicle road limit line dynamic detection, including Road ban, left turn, right turn, straight line, U-turn, and one-way limit line and speed limit detection. The algorithm in this paper can be used for the change detection of the road steering limit line, and can build a more objective and effective verification method for the large area of the road network limit line rules change, so as to improve the verification efficiency and reduce the workload.