Vessel Trajectory Similarity Based on Cubic B-spline Interpolation + Time-constrained Hausdorff Algorithm

The spatio-temporal trajectory data sampling period is large, and the general trajectory similarity is not suitable. This paper proposes a new algorithm, cubic B-spline interpolation + time-constrained Hausdorff algorithm to calculate the trajectory distance. This paper compares the time-constrained Hausdorff algorithm, cubic B-spline interpolation algorithm and cubic B-spline interpolation + time-constrained Hausdorff algorithm. The experimental results show that the cubic B-spline interpolation + time-constrained Hausdorff algorithm is significantly higher than other algorithms in the accuracy of vessel trajectory similarity.


Introduction
With the rapid development of technology and the wide application of a variety of sensors, massive data is rapidly accumulating. These data play an important role in all aspects of national defense and technological development. In recent years, the navigation has developed rapidly, generating a large amount of spatio-temporal trajectory data. The analysis of vessel trajectory data can dig out the potential useful information of the target. In order to optimize the trajectory when displaying the target trajectory, we need to integrate the trajectory data obtained by different observation sources.
The trajectory similarity is the basis of multi-source data fusion. The accuracy of the similarity directly affects the fusion result. Therefore, it is necessary to study the trajectory similarity specifically. However, most of the current research objects in the trajectory similarity are people or vehicles. These trajectories are carried out on the road network, which is quite different from the vessel trajectory at sea. Wu Cong et al. [1] used the similarity function based on difference and feature point set to analyze the similarity between moving target trajectories; Wang Haiqi et al. [2] used the trajectory similarity method dominated by the motion direction to calculate the similarity between vehicle trajectories; Liu Kun et al. [3] used the improved edit distance to calculate the similarity of human or vehicle trajectories. In this search, the time attribute of trajectory data were not considered; Zhang Chengde et al. [4] proposed a Hausdorff distance calculation method with time constrains for the three-dimensional spatio-temporal trajectory, so as to match the vehicle and achieve the purpose of carpooling; Liu Lei et al. [5] proposed an average distance between the trajectories, combined with the vessel's trajectory heading and speed characteristics, which constituted the comprehensive distance the There are many sources of trajectory data, mainly relying on shore-based radar and ship-based radar. Remote sensing satellites, electronic reconnaissance satellites, and Beidou satellites are also important data sources. In the environment where satellites and radars cannot detect, artificial reporting is also used. Different sources of data can cause very different sampling periods. The sampling period of the spatio-temporal trajectory data is quite different, so it is necessary to design an algorithm for this situation.

Time-constrained Hausdorff algorithm
The Hausdorff algorithm calculates the similarity between two sets of unordered points. . The Hausdorff distance can be expressed as: The general Hausdorff algorithm does not take into account the time attribute, so it is not suitable for processing spatio-temporal trajectory data. The trajectory data is sorted according to the time attribute, and the distance between the point p on the trajectory A and the point q on the trajectory B is calculated, and the q point corresponds to the p point time. Using a one-to-three method, the distance between p and q, the distance between p and a point before q, and the distance between p and a point behind q are calculated. The distance between p and q takes the minimum value between the three [8].

Cubic B-spline interpolation algorithm
In finance, spline interpolation is used to estimate the dependent variable values of independent variables that are not included in the original observation point. When calculating the distance between the trajectories, in addition to knowing the position value at the sampling time [9], the value at any time is also known, so the data needs to be interpolated. This paper uses the cubic B-spline interpolation algorithm to process the trajectory data.

Algorithm improvement ideas
3.1.1. Improved cubic B-spline interpolation algorithm. The spatio-temporal trajectory data processed in this paper has different sources and different sampling periods. It can not guarantee that the time attributes of the trajectory points can correspond one-to-one. Therefore, the influence of time attributes on the similarity of the entire trajectory may be ignored. The spline curve of the trajectory is obtained by the cubic B-spline interpolation algorithm, and the position of the trajectory at any time is obtained through the B-spline curve. Considering the similarity of the B-spline curves of similar trajectories, when calculating the similarity between trajectory A and trajectory B, the predicted position of trajectory B is obtained by using the B-spline curve parameters of trajectory A. Calculate the distance between the predicted position of the trajectory B and the real position as the distance between

Improved algorithm in this paper
3.2.1. Data preprocessing. In this paper, we use the marinecadastre.gov/ais/ public data set. However, the format of the data set cannot be directly processed by our algorithm, so it is necessary to preprocess the original data set. The AIS data contains attributes such as MMSI, time, longitude, latitude, speed, direction, etc. MMSI is the unique identifier of a vessel. We first extract the trajectory of each vessel through MMSI, then remove the abnormal points in the trajectory, and then extract the three attributes of time, longitude and latitude we need. When we remove the abnormal point, we consider the drift of the position of the trajectory point, so we simply handle the trajectory point. The theoretical distance travelled by the vessel can be obtained by calculating the product of the current travel speed of the vessel and the time interval. Taking the current position of the vessel as the middle position, the theoretical exercise distance plus a certain threshold is used as the radius. If the neighbour is not in the circle, it is considered to be an abnormal drift point and should be deleted [10].

Cubic B-spline interpolation algorithm for calculating trajectory similarity.
When we calculate the similarity between the trajectory A and the trajectory B, the sampling period of the interpolation curve parameter sequence is 15, and the verification data sampling period is 11. For the trajectory A, the one-dimensional curve B-spline representation of the longitude and latitude is obtained from the time t in the interpolation parameter list.
Using the time-constrained Hausdorff algorithm, the distance AB distance between the real position of the samplingTraA and the predicted position at the time corresponding to the samplingTraB is calculated. Similarity, the distance BA distance from trajectory B to the trajectory A is calculated.
Then the trajectory distance shol  , the trajectories are considered similar. Figure 1:

Experimental results and comparison
In this paper, the time-constrained Hausdorff algorithm, cubic B-spline interpolation algorithm, cubic B-spline + time-constrained Hausdorff algorithm are used to calculate the similarity between two trajectories, and the accuracy of the three algorithms is compared.

Time-constrained Hausdorff algorithm
The time-constrained Hausdorff algorithm calculates the trajectory spatial distance, sorts the trajectory points according to the time attribute, and calculates the distance between the trajectory points by a one-to-three method. The time-constrained Hausdorff algorithm takes into account the effect of time attribute on similarity. However, when calculating the distance between the trajectory points, the nearest point of the time distance is first searched, so the calculation speed is slow, and the accuracy of the similarity needs to be further improved.

Cubic B-spline interpolation algorithm
The time-constrained Hausdorff algorithm takes a while to find the closest point of the time attribute when calculating the distance of the trajectory point. The result is a certain error.
The B-spine curve is obtained by the cubic B-spine interpolation algorithm, and the position of the trajectory at any time is obtained, which can improve the calculation speed. According to the cubic Bspline curve of one track, the predicted value of another trajectory at a certain moment is obtained. The difference between the predicted position and the real position is taken as the distance between the two trajectories, which ensures the accuracy of the similarity to a certain extent.

Cubic B-spline + time-constrained Hausdorff algorithm
According to the cubic B-spline interpolation algorithm, the distance between the predicted position of the trajectory point and the real position is calculated as the trajectory distance. Although the running speed is increased, the similarity accuracy rate is decreased.
Cubic B-spline interpolation obtains the position of the trajectory at any time point and increases the calculation speed. The time-constrained Hausdorff algorithm calculates the trajectory distance to ensure the accuracy of the similarity. It is proved that the trajectory similarity of the cubic B-spline interpolation + time-constrained Hausdorff algorithm used in this paper has certain application value.

Experimental comparison result
In order to verify the accuracy of the new algorithm proposed in this paper, a different sampling interval of a certain trajectory is sampled as a sub-trajectory. The similarity of the sub-trajectory is calculated by the time-constrained Hausdorff algorithm, the cubic B-spline interpolation algorithm, the cubic B-spline interpolation + time-constrained Hausdorff algorithm. And the results are compared.
In this paper, 11144 trajectories are verified, and different trajectory distance thresholds are set to judge the accuracy of the similarity. The threshold values are: 0.5, 0.6, 0.7, 0.8, 1.0. If the distance between the trajectories is within the threshold range, it is considered similar. The similarity accuracy of each algorithm is shown in Figure 2. The speed comparison of various algorithms to calculate similarity is shown in Figure 3.  Figure 3. Calculating time of similarity accuracy. Algorithm-1 represents the time-constrained Hausdorff algorithm, Algorithm-2 represents the cubic B-spline interpolation algorithm, and Algorithm-3 represents the cubic B-spline interpolation + timeconstrained Hausdorff algorithm.
As it can be seen from Figure 2, the accuracy of the similarity of the cubic B-spline interpolation + time-constrained Hausdorff algorithm is significantly higher than other algorithms under different distance thresholds. Figure 3 shows that the cubic B-spline interpolation algorithm and the cubic Bspline + time-constrained Hausdorff algorithm are significantly faster than the time-constrained Hausdorff algorithm.

Conclusion
The time-constrained Hausdorff algorithm takes into account the time attribute of the vessel trajectory data, and the similarity has a good accuracy, but the running speed is not high. The B-spline interpolation algorithm significantly improves the speed of similarity calculation, but the accuracy rate decreases. The cubic B-spline interpolation + time-constrained Hausdorff algorithm proposed in this paper improves the accuracy of trajectory similarity and increases the calculation speed.