PSOTSC: A Global-Oriented Trajectory Segmentation and Compression Algorithm Based on Swarm Intelligence

Abstract

Linear approximate segmentation and data compression of moving target spatio-temporal trajectory can reduce data storage pressure and improve the efficiency of target motion pattern mining. High quality segmentation and compression need to accurately select and store as few points as possible that can reflect the characteristics of the original trajectory, while the existing methods still have room for improvement in segmentation accuracy, reduction of compression rate and simplification of algorithm parameter setting. A trajectory segmentation and compression algorithm based on particle swarm optimization is proposed. First, the trajectory segmentation problem is transformed into a global intelligent optimization problem of segmented feature points, which makes the selection of segmented points more accurate; then, a particle update strategy combining neighborhood adjustment and random jump is established to improve the efficiency of segmentation and compression. Through experiments on a real data set and a maneuvering target simulation trajectory set, the results show that compared with the existing typical methods, this method has advantages in segmentation accuracy and compression rate.

1. Introduction

With the continuous development of global positioning technology, wireless communication technology and the wide application of mobile terminals, enormous volumes of mobile target trajectory data have appeared. Trajectory data contains rich information of target space-time characteristics. Through data mining and depth analysis, we can find high-value information, such as target activity law, behavior characteristics, interest habits, abnormal changes [1,2,3,4,5,6], etc. However, the rapid growth of trajectory data also brings many challenges to the data service based on the target space-time location, including the increase in data transmission load, the pressure of data storage, the reduction of data query efficiency and the decline of data analysis performance [7]. Trajectory data compression is an effective way of solving the above problems, and the main way to achieve compression is to segment the trajectory, i.e., to obtain trajectory segments with uniform and homogeneous internal motion behavior or semantic characteristics based on certain partition criteria. The compressed trajectory only stores feature points and segment feature information, which can not only meet the user’s requirements of similarity with the original trajectory, but also reduce the amount of data storage.

The existing methods of trajectory data compression can be divided into three categories [8,9,10,11]. The first is a trajectory data compression based on line segment simplification [12,13,14,15,16,17]; the trajectory in free space is segmented linearly by constraints, and only two end points of each approximate segment are stored to achieve compression. The second is a trajectory data compression based on road network structure [18,19,20,21,22]; the trajectory points are mapped onto the road network, and the original trajectory is represented by a grid structure to reduce the amount of data. However, this kind of method is not suitable in a scenario where there is a lack of road network information, such as at sea and in the air, and it is also difficult to apply to the ground target with high degree of motion freedom. The last method is a trajectory data compression based on semantic information [23,24,25,26,27,28,29,30,31,32]. Semantic features are extracted from the trajectory data, and the trajectory is transformed into a semantic sequence. However, this kind of method often ignores the movement characteristics of the target, and it is difficult to obtain the semantic features of the trajectory.

In our application, the main reason for trajectory data compression is that the long-term accumulated target-historical trajectories occupy a lot of storage resources, and the unsimplified data set is very difficult to use in the deep mining of target motion features. Because a large number of different types of sensors have been deployed for target reconnaissance, the data sampling rates of these sensors are generally different, and some may be very frequent, such as radar gaze tracking of targets. Therefore, the same target may get multiple trajectories, and the data of one trajectory may be very dense, so there is a lot of information redundancy in the whole database. At the same time, most of the targets we focus on are free moving targets on land, sea and air. Their activities often do not follow the road network, and it is difficult for us to know the intention of the activities, i.e., the trajectory semantic information is unknown. Therefore, among the three methods above, the trajectory data compression based on line segment simplification is the most suitable in our application, and it is also the most popular one, because it has a clear technical route, simple method, easy implementation and wide application. Therefore, the method proposed in this paper belongs to the line segment simplification type, and the following analysis is mainly focused on the research of this kind of method.

Trajectory data compression based on line segment simplification can be subdivided into two types: global-oriented method and local forward method. The representative global-oriented method is the Douglas–Peucker (DP) algorithm [12] and its related improvements [13,14,15,16]. The DP algorithm uses the perpendicular Euclidean distance to measure the error. First, the straight line formed by the start and end points of the trajectory is regarded as the approximate trajectory, and the perpendicular Euclidean distance from the point to the line is calculated for all the points in the middle; the point with the largest distance is selected. If the maximum distance exceeds the preset distance threshold, the point is regarded as the segment feature point, and then the original trajectory is divided into two segments. The above steps are to be repeated for the two segments, respectively, until the maximum perpendicular Euclidean distance calculated by all sub trajectories is less than the distance threshold, or until there are only the start and end points in the trajectories. The DP algorithm is simple and practical. When the distance threshold is set well, it can meet the user’s requirements for the similarity between the compressed trajectory and the original trajectory. At the same time, it can achieve high data compression rate. However, the distance threshold is often difficult to set and needs to be adjusted and tried repeatedly.

Based on the DP algorithm, Hershberger [33] established the trajectory point batch processing mode, which reduced the time complexity from $O(N^2)$ to $O(N\times \log N)$, but it is difficult to realize the batch processing mode in many real trajectory data compression processing instances. Top-Down Time-Ratio (TD-TR) algorithm [34,35] is an improvement on the basis of the DP algorithm. The main difference is that it uses the spatial distance of time scale as the distance function, finds the position corresponding to the original trajectory point on the approximate line segment according to the time scale and then calculates the Euclidean distance between the approximate point and the original trajectory point, so as to obtain a more accurate approximate trajectory. Muckell [36] compared the performance of the DP algorithm with TD-TR, Bellman [37], STTrace [38] and other algorithms. Finally, the DP algorithm has better performance in time efficiency, compression ratio and accuracy on multiple data sets. Liu [39] used convex hull to optimize the time complexity of the DP algorithm for segmentation of online trajectory data stream.

The local forward methods start from the initial point of the trajectory, and the trajectory points that meet the constraints can be classified as a local approximate line segment. On the contrary, the trajectory points that do not meet the conditions can continue to search forward as the initial point of the new segment [40]. The constraint condition can be defined as the distance function between the trajectory point and the approximate line segment, or the direction change function between the segments. A typical algorithm whose constraint condition is the distance function is the segment simplification part of the trajectory clustering (TRACLUS) algorithm proposed by Lee [41]. The algorithm defines three indexes: perpendicular distance, parallel distance and angle distance, and the trajectory segmentation solution is approximately solved based on the principle of minimum description length (MDL). The segmentation method has been applied in [42,43,44]. Yuan [45] divides the trajectory into a set of stationary sub-trajectory (SST) based on the detection and evaluation of trajectory position disturbance. The HTRACLUS_DL algorithm proposed by Liu [46] improved the accuracy of TRACLUS algorithm, in which a sub-trajectory parallel boundary method is constructed. Zhang [47] is also based on the MDL principle, which transforms the trajectory segmentation problem into the shortest path problem of undirected graph and then uses Dijkstra algorithm to get the best segmentation, which has higher complexity.

The distance index is used to measure the difference between the trajectory segments in the above methods, and Yuan [48,49] defines the corner index to measure the angle difference between the trajectory segments, which represents the movement trend of the trajectory, and realizes the local forward segmentation and compression based on direction change. In view of the shortcomings of position-preserving trajectory segmentation algorithm in some scenarios, Cheng [50] proposed a direction-preserving trajectory segmentation simplification algorithm, which uses the maximum angle difference instead of the average angle difference to better maintain the trajectory shape to obtain a better segmentation solution.

The prominent advantage of the local forward methods is that it has less computation, but the existing problems are mainly reflected in two aspects. The first is searching from the first point, which can only obtain local optimal segmentation, and the resulting lack of the overall consideration of the segmentation problem. The selection of feature points is difficult to ensure global optimization, which affects the accuracy of segmentation and reduces the similarity between the compressed trajectory and the original trajectory. The second is that there are dimensions in the distance and direction to measure the homogeneity and difference between the trajectories, which are very sensitive to the setting of threshold parameters.

Considering that our application pursues high trajectory approximation accuracy in order to improve the quality of subsequent trajectory data mining, rather than the segmentation and compression speed, we prefer the global-oriented method. Therefore, can segmentation accuracy be further improved without increasing the compression rate? This problem can be solved by finding the trajectory segmentation feature points that can better represent the original trajectory, and the swarm intelligence (SI) algorithm can not only meet the need of global search, but also help to find the trajectory segmentation optimization solution quickly and accurately.

Swarm intelligence, a major branch of artificial intelligence, was rendered to model the collective behavior of social swarms in nature. SI methods [51,52,53] have been widely used to solve global search problems, and particle swarm optimization (PSO) is the main paradigm [54,55]. The original idea of the PSO came from Kennedy and Eberhart’s observation of birds looking for food by sharing knowledge. They then proposed applying this evolutionary approach to the optimization of nonlinear problems [56,57]. Due to its simplicity, PSO has been successfully utilized in many fields, such as computer vision [58], path planning [59], signal processing [60] and other fields. The PSO variants mainly focus on parameter optimization [61,62,63,64] and multi-objective search [65,66,67], which improve the convergence speed, stability and applicability.

In summary, trajectory segmentation and compression mainly face the problem of how to balance trajectory segmentation accuracy and trajectory data compression rate. Intuitively, to improve the accuracy of trajectory segmentation, one can set more segmentation feature points, i.e., retain as many original trajectory points as possible; however, this will have negative impact on the trajectory data compression rate. Similarly, the local forward method can improve compression efficiency of trajectory segmentation, but it would sacrifice the accuracy of trajectory segmentation to a certain extent. Therefore, the basic consideration of this paper is to provide a better trajectory segmentation and compression method, which can obtain lower trajectory compression rate under certain trajectory approximation accuracy requirements. In other words, compared with the existing methods, this method can approximate the original trajectory with fewer trajectory points but without losing the accuracy. It will bring another potential advantage, i.e., under a certain trajectory compression rate level, the trajectory points retained by this method can better reflect the characteristics of the original trajectory, and the compressed trajectory is more similar to the original trajectory. In this way, the subsequent trajectory clustering analysis and motion feature mining will attain better accuracy.

A moving target trajectory segmentation and compression algorithm based on particle swarm optimization is proposed, which is named the PSOTSC algorithm. The general idea of the algorithm is to transform the trajectory data processing problem into a global optimization problem by using the swarm intelligence method. The prominent feature of the algorithm is to establish a mapping relationship between particles and trajectories, which gives full play to the advantages of the particle swarm optimization algorithm for global search and makes it easy to obtain the optimal solution. On this basis, a new particle update strategy for fast optimization of trajectory segmentation solution is designed and named the neighborhood adjustment and random jump (NARJ). Based on this strategy, high-quality particles can evolve into better particles faster, while low-quality particles can change in time to try new segmentation possibilities, which can not only improve the overall efficiency of the algorithm, but also prevent the algorithm from falling into local search.

The basic steps of PSOTSC are as follows. First, a trajectory segmentation optimization framework based on PSO is established. Second, the algorithm starts the search and optimization of trajectory segmentation solution, which involves many key processes, including initialization of particles, definition of particle fitness function based on fitting degree of trajectory profile and updating based on NARJ. Finally, each trajectory in the data set completes the optimal segmentation, which realizes the overall data compression. Hurricane real trajectory data set, ungulate location real data set and maneuvering target simulation trajectory data set [68] are used to verify the effectiveness of the algorithm. The comparative experiments with DP, TRACLUS and TCSS algorithms can prove the advantages of the PSOTSC algorithm.

In summary, the contributions of this paper are as follows:

• We propose a technical route based on swarm intelligence to solve the problem of trajectory segmentation and compression, and few similar studies are currently available. The heuristic search and optimization of the trajectory segmentation solution based on population behavior can quickly and accurately find the global optimal segmentation feature point set without user intervention, which lays the foundation for the application of intelligent optimization algorithm in moving target trajectory data processing.
• The proposed algorithm based on PSO has the advantage of global segmentation and compression and does not need to adjust the threshold parameters repeatedly. Compared with the local forward segmentation and compression methods, our algorithm is more accurate on the feature points selection, and the compressed trajectory has better similarity with the original trajectory.
• We propose a new NARJ particle update strategy, which can not only make the local optimal segmentation solution evolve into a better solution efficiently, but can also make the bad solution update quickly to try new segmentation possibilities. Compared with the classical particle swarm optimization method, the generation efficiency of the optimal solution is improved.
• We define the trajectory profile fitting degree as the similarity evaluation index between the compressed trajectory and the original trajectory and apply it to segmentation solution optimization. This index has no dimension, which effectively solves the difficulty in setting the parameters, such as distance threshold and direction change threshold. Therefore, it improves the applicability of the algorithm.

The rest of the paper is organized as follows. Section 2 gives the related definitions and establishes the evaluation index of trajectory profile fitting degree. Section 3 proposes a trajectory segmentation and compression algorithm based on PSO. Section 4 presents the results of experimental evaluation. Finally, Section 5 concludes the study.

2. Evaluation Index of Segmentation Accuracy

2.1. Related Definitions

First, the definitions of trajectory, trajectory segment, approximate compression of line segments and trajectory compression ratio are given.

Definition 1.

A trajectory is a set of ordered points in a multidimensional space, which can be expressed as $TR=\{P_1,P_2,\dots ,P_{len}\},1\le i\le len$, where $P_i$ is a multi-dimensional trajectory point and $len$ is the trajectory length. For different trajectories in a data set, the values of $len$ may be different. The points can be expressed as $P_i=(x_i,y_i,t_i)$, in which $x_i$ and $y_i$ are the coordinates of the trajectory point and $t_i$ is the recording time.

Definition 2.

A trajectory segment is a continuous subset of trajectory points, which can be expressed as $TRSub=(P_u,P_{u+1},\dots ,P_{u+n})$, where $P_u$ and $P_{u+n}(1\le u\le len-n)$ are the two ends of the segment called segment feature points. The length of the trajectory segment is $n+1$.

Definition 3.

The approximate compression of line segments is that the segments are approximated as straight-line segments connected by end points. Thus, the compressed trajectory only stores the first and last two points of the original trajectory and segment feature points, represented as $T{R}^{\prime }=\{P_1,P_{u_1},P_{u_2},\dots ,P_{u_k},P_{len}\}$ or $\{P_{u_0},P_{u_1},P_{u_2},\dots ,P_{u_k},P_{u_{k+1}}\}$, where $P_{u_1},P_{u_2},\dots ,P_{u_k}$ are segment feature points. The trajectory is divided into $k+1$ segments, and the compression ratio of trajectory data is ${\delta }_C=(k+2)/len$.

2.2. Profile Fitting Degree

The segmentation accuracy of the compressed trajectory is evaluated by the trajectory profile fitting degree, and the definition is given as follows.

Definition 4.

The profile fitting degree is the fitting degree between the compressed trajectory and the original trajectory after the trajectory is linearly approximated to a set of straight lines, which is recorded as $OF$. It is affected by the projection angle factor and the projection distance factor. The projection angle factor is a function of the projection length of the original trajectory and the length of the original trajectory. It describes the influence of the angle change of the approximate line segment on the similarity, which is recorded as $O{F}_{ang}$. The projection distance factor is a function of the projection length of the original trajectory and the distance from the original trajectory to the approximate line segment, which describes the influence of the distance difference between the approximate line segments on the similarity and is recorded as $O{F}_{dis}$. Figure 1 shows an example of the linear approximation of the original trajectory segment $TRSu{b}_1=\{P_1,P_2,\dots ,P_8\}$ to $TRSu{b}_1^{\prime }=\{P_1^{\prime },P_8^{\prime }\}$.

The projection of the original trajectory sub segment $P_1{P}_2$ is $P_1^{\prime }{P}_2^{\prime }$, the projection of the sub segment $P_2{P}_3$ is $P_2^{\prime }{P}_3^{\prime }$, etc., all together constitute the approximate trajectory segment $TRSu{b}_1^{\prime }$. For the original sub segment $P_i{P}_{i+1}$, the projection angle factor and the projection distance factor are defined as

$$O{F}_{ang}(P_i{P}_{i+1})=d(P_i^{\prime }{P}_{i+1}^{\prime })/d(P_i{P}_{i+1})$$

(1)

$$O{F}_{dis}(P_i{P}_{i+1})=\{\begin{array}{l}1-e^{-d(P_i^{\prime }{P}_{i+1}^{\prime })/d_{Min}(P_i,P_{i+1})},d_{Min}(P_i,P_{i+1})>0\\ 1,d_{Min}(P_i,P_{i+1})=0\end{array}$$

(2)

where $d(P_i{P}_{i+1})$ is the distance of the original trajectory segment $P_i{P}_{i+1}$, $d(P_i^{\prime }{P}_{i+1}^{\prime })$ is the distance of the projection $P_i^{\prime }{P}_{i+1}^{\prime }$, and $d(P_i^{\prime }{P}_{i+1}^{\prime })\le d(P_i{P}_{i+1})$. $le{n}_S$ is the length of the original trajectory sub segment and $0\le i\le le{n}_S-1$. We define $d_{Min}(P_i,P_{i+1})=\min [d(P_i{P}_i^{\prime }),d(P_{i+1}{P}_{i+1}^{\prime })]$, and the solution of $d(P_i{P}_i^{\prime })$ is based on Helen formula, as shown in Figure 1. The area of $\Delta P_1^{\prime }{P}_i{P}_8^{\prime }$ is

$$S_{\Delta }=\sqrt{p(p-a)(p-b)(p-c)}=\frac{1}{2}\cdot h\cdot c$$

(3)

where $p$ is the half perimeter, $a,b,c$ is the side length $d(P_1{P}_i),d(P_8{P}_i),d(P_1{P}_8)$, and $h$ is $d(P_i{P}_i^{\prime })$.

Obviously, $O{F}_{ang}(P_i{P}_{i+1})$ describes the influence of the angle $\theta (0\le \theta \le \pi /2)$ between $P_i{P}_{i+1}$ and $P_i^{\prime }{P}_{i+1}^{\prime }$ on the degree of trajectory approximation. The smaller the angle is, the closer the distance of $P_i{P}_{i+1}$ and $P_i^{\prime }{P}_{i+1}^{\prime }$ is, and tends to 1, while the larger the angle is, $O{F}_{ang}(P_i{P}_{i+1})$ tends to 0. In $O{F}_{dis}(P_i{P}_{i+1})$ calculation, $d(P_i{P}_i^{\prime })$ and $d(P_{i+1}{P}_{i+1}^{\prime })$ are the distance from the two endpoints of the original sub segment to the projection, and $d_{Min}(P_i,P_{i+1})$ takes the smaller value of both, because the difference between them reflects the change of angle, which has been reflected in the calculation of $O{F}_{ang}(P_i{P}_{i+1})$. It can be seen that $O{F}_{dis}(P_i{P}_{i+1})$ describes the influence of distance on trajectory approximation. The smaller the distance is, the closer $P_i{P}_{i+1}$ and $P_i^{\prime }{P}_{i+1}^{\prime }$ are, and $O{F}_{dis}(P_i{P}_{i+1})$ tends to 1. The larger the distance is, the farther away $P_i{P}_{i+1}$ and $P_i^{\prime }{P}_{i+1}^{\prime }$ are, and $O{F}_{dis}(P_i{P}_{i+1})$ tends to 0.

The above calculation of $O{F}_{ang}(P_i{P}_{i+1})$ and $O{F}_{dis}(P_i{P}_{i+1})$ is applicable to the case where the original trajectory points are on the same side of the compressed trajectory. As shown in Figure 2, the original trajectory points $P_i,P_{i+1}$ are on both sides of the compressed trajectory. The calculation of $O{F}_{ang}(P_i{P}_{i+1})$ and $O{F}_{dis}(P_i{P}_{i+1})$ are described as follows.

The projection angle factor $O{F}_{ang}(P_i{P}_{i+1})$ is defined as the ratio of the projection length $d(P_i^{\prime }{P}_{i+1}^{\prime })$ to the original sub segment length $d(P_i{P}_{i+1})$, and $d(P_i{P}_{i+1})=d(P_i^{″}{P}_{i+1}^{\prime })$, therefore $O{F}_{ang}(P_i{P}_{i+1})=d(P_i^{\prime }{P}_{i+1}^{\prime })/d(P_i^{″}{P}_{i+1}^{\prime })=d(P_i^{\prime }{P}_{i+1}^{\prime })/d(P_i{P}_{i+1})$ can reflect the influence of $\theta$ on the trajectory approximation degree, and the calculation of $O{F}_{ang}(P_i{P}_{i+1})$ is consistent with the situation of the same side of the trajectory point. However, the original sub segment $P_i{P}_{i+1}$ and projection $P_i^{\prime }{P}_{i+1}^{\prime }$ intersect at point $O$, and the influence of distance $d(P_i{P}_i^{\prime }),d(P_{i+1}{P}_{i+1}^{\prime })$ on the trajectory similarity has been considered in the calculation of $O{F}_{ang}(P_i{P}_{i+1})$, therefore $O{F}_{dis}(P_i{P}_{i+1})=0$.

The method of the vector cross product is used to judge whether the projection $P_i^{\prime }{P}_{i+1}^{\prime }$ intersects with the original sub segment $P_i{P}_{i+1}$. We define

$$\begin{array}{l}{c}_1=\overrightarrow{P_i{P}_i^{\prime }}\times \overrightarrow{P_i{P}_{i+1}},c_2=\overrightarrow{P_i{P}_{i+1}^{\prime }}\times \overrightarrow{P_i{P}_{i+1}}\\ c_3=\overrightarrow{P_i^{\prime }{P}_i}\times \overrightarrow{P_i^{\prime }{P}_{i+1}^{\prime }},c_4=\overrightarrow{P_i^{\prime }{P}_{i+1}}\times \overrightarrow{P_i^{\prime }{P}_{i+1}^{\prime }}\end{array}$$

(4)

when $P_i{P}_{i+1}$ intersects $P_i^{\prime }{P}_{i+1}^{\prime }$, $c_1$ and $c_2$ have different signs, and $c_3$ and $c_4$ are the same.

The projection angle factor and distance factor of the original trajectory segment $TRSu{b}_1$ and the approximate trajectory segment $TRSu{b}_1^{\prime }$ can be expressed by the aggregation of the calculation results of each sub segment:

$$O{F}_{ang}(TRSu{b}_1)={\displaystyle \sum _{i=1}^{le{n}_{s1}-1}{\omega }_i\cdot O{F}_{ang}(P_i{P}_{i+1})}$$

(5)

$$O{F}_{dis}(TRSu{b}_1)={\displaystyle \sum _{i=1}^{le{n}_{s1}-1}{\omega }_i\cdot O{F}_{dis}(P_i{P}_{i+1})}$$

(6)

where ${\omega }_i$ is the occupancy of the original sub segment $P_i{P}_{i+1}$ in the trajectory segment, which is expressed by its length proportion as

$${\omega }_i=d(P_i{P}_{i+1})/{\displaystyle \sum _{j=1}^{le{n}_{s1}-1}d(P_j{P}_{j+1})}$$

(7)

Based on the above calculation, the projection angle factor and distance factor of the whole trajectory can be obtained:

$$O{F}_{ang}(TR)={\displaystyle \sum _{n=1}^{Ns}{\epsilon }_n\cdot O{F}_{ang}(TRSu{b}_n)}$$

(8)

$$O{F}_{dis}(TR)={\displaystyle \sum _{n=1}^{Ns}{\epsilon }_n\cdot O{F}_{dis}(TRSu{b}_n)}$$

(9)

where $N_s$ is the number of segments of the trajectory, and ${\epsilon }_n$ is the occupancy of the original trajectory segment $TRSu{b}_n$ in the trajectory $TR$, which can also be expressed by its length proportion.

Finally, the trajectory profile fitting degree is defined as $OF={\phi }_{ang}\cdot O{F}_{ang}+{\phi }_{dis}\cdot O{F}_{dis}$, ${\phi }_{ang}$ and ${\phi }_{dis}$ are the importance weights of projection angle factor and projection distance factor respectively, and the sum of them is 1.

In summary, the calculation of trajectory profile fitting degree is an aggregation process from sub segment trajectory segment to the whole trajectory, which fully reflects the influence of the angle and distance difference between the approximate trajectory and the original trajectory on the similarity. At the same time, the trajectory profile fitting degree, the projection angle factor and the projection distance factor are all dimensionless, and the values are normalized, thus the applicability is better.

3. The PSOTSC Algorithm

The PSOTSC algorithm is developed in this section where the high-quality segmentation solution is found through particle swarm optimization to achieve better segmentation accuracy and compression rate. First, the overall framework of the algorithm is introduced. Then some key processing links in the algorithm are illustrated in detail, such as particle swarm segmentation optimization method, particle update strategy based on NARJ and the satisfaction judgment method.

3.1. Overall Framework

Trajectory segmentation and compression need to deal with the contradiction or balance between segmentation accuracy and compression rate. Retaining more original trajectory points can bring better similarity, but at the expense of compression rate. On the contrary, excessive pursuit of data compression rate will deteriorate the quality of approximate trajectory, which loses the significance of similar compression. How to optimize the whole effect of trajectory segmentation and compression? The PSOTSC algorithm is developed, which takes the selection of trajectory segmentation feature points as the starting point, and gives full play to the global optimization advantages of PSO. A better target trajectory segmentation and compression solution can be found. Compared with the results obtained by previous algorithms, the new solution can achieve better data compression rate on the same degree of trajectory similarity, i.e., fewer original trajectory points are retained. From another point of view, it can make the compressed trajectory more similar to the original trajectory under the same data compression rate level. The framework of PSOTSC is shown in Algorithm 1.

Algorithm 1 PSOTSC

Input: A set of trajectories $STR=\{T{R}_1,T{R}_2,\dots ,T{R}_N\}$

Output: A set of compressed trajectories $ST{R}^{\prime }=\{T{R}_1^{\prime },T{R}_2^{\prime },\dots ,T{R}_N^{\prime }\}$

A compression ratio of ${\delta }_C$ and a segmentation accuracy of ${\delta }_P$

01: for each $TR\in STR$ do

02: Number of segments $N_S=1$;

03: while $true$ do

04:    Search optimal segmentation solution $SegSol=PSOSegSearch(N_S)$;

05:   Calculate the compression ratio ${\delta }_{CTR}$ and segmentation accuracy ${\delta }_{PTR}$ of $TR$;

06:    Satisfaction judgment $SJ=TSCSuccess({\delta }_{PTR},{\delta }_{CTR})$;

07:    if $SJ=1$

08:     break;

09:    Increase number of segments $N_S=N_S+1$;

10: end while

11: end for

12: Generate a set of compressed trajectories $ST{R}^{\prime }$

13: Calculate ${\delta }_C$ and ${\delta }_P$ of $ST{R}^{\prime }$

First, the input and output of the PSOTSC algorithm should be clarified. In general, the input of the algorithm is the original trajectory data set, which contains many trajectories with large amount of data. The output of the algorithm is the compressed trajectory data set and the evaluation values of data compression rate and segmentation accuracy. The compressed data set contains approximately processed trajectories, which are one-to-one corresponding to the trajectories in the original data set. The key links in the internal processing of the algorithm also have parameters that need to be set by the user, such as the scale of particle swarm, the number of search iterations, etc., which will be described in the subsequent parts of this section. Second, the basic method of trajectory segmentation optimization based on PSO is established (line 4), which can complete the search of the optimal segmentation solution under a fixed number of segments. After that, the fixed number of segments will start from 1 and increase from small to large to search for the corresponding optimal segmentation solution (line 2–10). By calculating and evaluating the compression ratio and segmentation accuracy, a solution meeting the satisfaction requirements will be found (line 5–8). Finally, each trajectory in the original data set is optimized by the above method (line 1–11), the compressed trajectory data set can be generated (line 12), and the compression ratio and segmentation accuracy are given (line 13).

3.2. Particle Swarm Segmentation Optimization

Particle swarm optimization is an evolutionary computation technology based on swarm intelligence. It originated from biologists’ observation and research on the behavior of birds’ foraging process. It has the characteristics of fast calculation speed, good robustness, strong global convergence ability, being easy to understand, easy to realize, etc. In the PSO algorithm, the potential solution of each optimization problem is a bird in the search space, which is called the “particle”. The particle has a fitness value representing whether it is close to the target and a speed value representing its update speed and search direction. The flow of PSO algorithm is shown in Figure 3.

The algorithm is initialized as a group of random particles (random solution) and finds the optimal solution through iteration. The quality of the solution is evaluated by the fitness of the particles. In each iteration, each particle tracks two “optimal particles” to update itself; one is the local optimal particle found by itself, the other is the global optimal particle found by the swarm. The particles follow them to search in the solution space. The advantage of the PSO algorithm is that there is no crossover and mutation operation, and it relies on particle speed and fitness evaluation to complete the search. In the iterative evolution, only the optimal particle transmits information to other particles, therefore the optimization speed is fast and the solution accuracy is high. At the same time, the structure of the algorithm is simple and easy to implement.

$PSOSegSearch$ method is designed to realize the application of PSO in trajectory segmentation solution search, which is the core of the PSOTSC algorithm shown in Algorithm 2. $PSOSegSearch$ method needs to solve two key problems: one is how to establish the mapping relationship between the trajectory and the particle; the other is what kind of driving mechanism particles use to update and quickly optimize. To solve the first problem, $PSOSegSearch$ method maps the compressed trajectory to the particle, which is expressed as a one-dimensional sequence with the same length as the original trajectory. The original trajectory points to be retained and discarded in the sequence are assigned different values. In this way, the problem is simplified, and the process seems simple and straightforward. However, if the length of the original trajectory is very long, it will increase the length of the particle and affect the effect of the algorithm, which leads to the second problem mentioned above. $PSOSegSearch$ method proposes a NARJ particle update strategy, which can speed up the search of segmentation solution and improve the efficiency of the PSOTSC algorithm. The content of NARJ will be described in detail in Section 3.3.

Algorithm 2  $PSOSegSearch$

Input: Trajectory points ordered by time $TR=\{P_1,P_2,\dots ,P_{len}\}$

A set of parameters of PSO $Para\_PSO=\{N_P,N_I,C_1,C_2,W_{\max },W_{\min },V_{\max },V_{\min }\}$

A threshold of trajectory profile fitting $TP{F}_{\min }$

A number of compressed trajectory segments $N_S$

Output: Compressed trajectory points ordered by time $T{R}^{\prime }=\{P_{u_0},P_{u_1},P_{u_2},\dots ,P_{u_{s-1}},P_{u_s}\}$

01: Initial particle swarm and velocity $ps=\{p_1,p_2,\dots ,p_{Np}\}$, $v\_ps=\{v{p}_1,v{p}_2,\dots ,v{p}_{Np}\}$

02: while $n\le N_I$ and $gTP{F}_{best}<TP{F}_{\min }$ do

03:  for each $p\in ps$ do

04:    Calculate fitness $fp=TraProfileFitting(TR,p)$;

05:  end for

06:  Find Current best particle $pbest\in ps$ and best fitness $pTP{F}_{best}$ with maximum $fp$;

07:  Update global best particle $gbest$ and best fitness $gTP{F}_{best}$;

08:  for each $p\in ps$ do

09:    Calculate velocity $vp$ using $gbest$;

10:    Update particle based on $NARJ$ strategy $pe=NARJParUpdate(p)$;

11:  end for

12: end while

13: Construct compressed trajectory $T{R}^{\prime }$;

The input of the algorithm is the original trajectory $TR=\{P_1,P_2,\dots ,P_{len}\}$. The basic parameters of PSO include the number of particles $N_P$, the maximum number of iterations $N_I$, the learning factor $C_1,C_2$, the maximum and minimum inertia weight $W_{\max },W_{\min }$ and the maximum and minimum velocity $V_{\max },V_{\min }$.The threshold of trajectory profile fitting degree is $TP{F}_{\min }$, and $N_S$ is the number of trajectory segments. First, the algorithm needs to complete the initialization of particle swarm (line 1), and the premise is to define the particle format. For trajectory $TR$, the compressed trajectory is expressed as $T{R}^{\prime }=\{P_1,P_{u_1},P_{u_2},\dots ,P_{u_k},P_{len}\}$, where $P_{u_1},P_{u_2},\dots ,P_{u_k}$ is the segment feature point. Then, the trajectory $TR$ with $k$ segment feature points can be mapped into a sequence of 0 and 1, and the position of 1 in the sequence is $P_1,P_{u_1},P_{u_2},\dots ,P_{u_k},P_{len}$. Therefore, we define the particle format as sequence $p=\{1,\Phi ,1\}$ and the length is $len$. $\Phi$ is a sequence of 0 and 1 with the length of $len-2$, and the number of 1 in the sequence is $k$. Random particle means randomizing the position of 1 or the number of 1, representing a random segmentation solution. If the number of trajectory segments is fixed, only the position of 1 needs to be randomized. In order to simplify the calculation, the particle can also be defined as $p=\Phi$, which is transformed into $p=\{1,\Phi ,1\}$ when the algorithm finally outputs the compressed trajectory.

The algorithm will keep on searching for optimization, as long as the number of iterations $n$ is no more than $N_I$ and the trajectory profile fitting degree of the global optimal segmentation solution is less than $TP{F}_{\min }$ (line 2). In each iteration, the fitness $fp$ is calculated for all particles (line 3–5), i.e., the fitting degree of the compressed trajectory represented by the particles and the original trajectory. The fitness function is defined as $TraProfileFitting$. The original trajectory TR and particle p are the inputs of this function. The calculation of the function has been described in detail in Section 2.2. The particle $pbest$ with the highest fitness is selected to update the global optimal particle $gbest$ and optimal fitness $gTP{F}_{best}$ (line 6–7). Then, the speed of all particles is modified according to the global optimal particle $gbest$ (line 9), and the particle state is updated based on the particle update strategy of NARJ, which will be discussed later. Finally, the algorithm ends the iteration and outputs the compressed trajectory $T{R}^{\prime }$.

3.3. NARJ Particle Update Strategy

In PSO, particle updating is driven by whether the quality of the current particle is close to the quality of the optimal particle. For a particle used to represent a compressed trajectory, the quality of the particle is its profile fitting degree with the original trajectory. The higher the fit, the better the quality of the particle. Therefore, the first problem to be solved is how to evolve a high-quality particle into a better one. A high-quality particle means that the selection of trajectory segmentation feature points is basically reasonable. It only needs to adjust the position of segmentation feature points a little to try to obtain a better solution on the original basis, while excessive or random adjustment of a reasonable segmentation solution may destroy the original balance. Will this fall into the dilemma of local search? What about low-quality particles? These are the next two problems to be solved. The segmentation solution represented by a low-quality particle is not reasonable and needs to be greatly adjusted to try new possibilities. Some segmentation feature points can be selected randomly in the solution and can jump to other positions randomly. Such changes can not only solve the problem of rapid disintegration and the updating of low-quality particles, but also ensure that the PSOTSC algorithm will not fall into local optimization.

Thus, the basic consideration of NARJ particle update strategy is that the segment feature points of high-quality particles are adjusted in their neighborhood, and the probability of evolving into better particles will be larger than that of feature points randomly adjusted. Meanwhile, low-quality particles need to adjust the feature points randomly in a large range to get rid of the current state and try a new segmentation solution to improve the search efficiency. Algorithm 3 gives the $NARJParUpdate$ of particle update strategy.

Algorithm 3  $NARJParUpdate$

Input: A particle $p\in ps$ and its fitness $fp$

A neighborhood adjustment span $Sp$

A number of adjusted feature points $N_a$

Output: An evolved particle $pe$

01: Select $N_a$ feature points;

02: Evaluate the quality of particle $p$ with its fitness $fp$;

03: if $p$ is high-quality then

/* Neighborhood Adjustment*/

04:   Change the feature points in $\pm Sp$ range;

05: else

/* Random Jump */

06:  Change the feature points randomly;

07: end if

08: Set the value of the new points to 1 and the old points to 0;

09: Replace the old particle $p$ with the evolved one $pe$;

The input of the algorithm is particle $p$ and its fitness $fp$, the neighborhood adjustment span $Sp$ and the number of adjusted feature points $N_a$. In the evolution process, whether it is neighborhood adjustment or random jump, the segment feature points that change the position are randomly selected (line 1), generally 1~2, so that the search efficiency will not be affected because of the strong randomness. High-quality particles adjust the neighborhood of segment feature points, while low-quality particles adjust the position of segment feature points randomly (line 2–7). The direction of feature point adjustment is random, which can be adjusted forward or backward. In neighborhood adjustment, each feature point is taken as the center, and the feature point position is changed within the range $\pm Sp$ (line 4). The span $Sp$ depends on the total length of the trajectory and the interval of the trajectory points. If the trajectory is long, the interval of the trajectory points is small or the number of points is large, it is necessary to increase the span appropriately to improve the search speed. However, if the interval of trajectory points is larger, and the number of trajectory points is less, the span should be reduced. The algorithm outputs the evolved particle $pe$ and replaces the original particle $p$.

An example is given to illustrate various situations in the process of particle update, as shown in Figure 4. Only one feature point is adjusted for each evolution, and the neighborhood adjustment span is 1.

For a high-quality particle, neighborhood adjustment will produce two possible results. One is the evolution into a better particle, which is obviously the expected result. The other is that the quality becomes worse. The solution is to restore the particle to its original state, so that in the next round of evolution it will try to adjust again based on a good state. In Figure 4, the segment feature points of high-quality particle are $P_2$ and $P_5$, and adjusting $P_2$ to $P_3$ may lead to a better solution. However, adjusting $P_5$ to $P_6$ will generate a bad solution, so it is necessary to restore $P_6$ to $P_5$. In the next evolution, $P_5$ will try to adjust to $P_4$ with a certain probability.

For a low-quality particle, the neighborhood adjustment of feature points cannot change the bad state fundamentally, but random jump can bring the possibility of “reversal”. Of course, it may also make the quality worse. In Figure 4, the selection of segment feature point for a low-quality particle is $P_4$ and $P_7$. After evolution, $P_7$ jumps to $P_5$, which brings a better solution. The subsequent evolution can adjust the feature points in the neighborhood, such as the high-quality particle. The jump from $P_4$ to $P_2$ further worsens the quality, and the particle will directly enter the next evolution to reflect the randomness and globality.

3.4. Satisfaction Judgment

If the number of segments of the trajectory is 1, i.e., there are no segment feature points except the first and last two points of the trajectory, then the compression ratio of the original trajectory is the best. On the contrary, the segmentation accuracy can be improved by setting as many segmentation feature points as possible and retaining the profile information of the original trajectory, but a certain data compression ratio will be sacrificed. Therefore, we need to find a balance between the number of segments and the accuracy of segmentation. When the satisfaction is reached, we judge that the trajectory segmentation and compression is complete.

Definition 5.

Compression–accuracy contribution rate is the contribution to the trajectory segmentation accuracy at the expense of a certain data compression rate, expressed as

$$CPCR=\frac{{\delta }_P(i+1)-{\delta }_P(i)}{{\delta }_C(i+1)-{\delta }_C(i)},1\le i\le len-2$$

(10)

where${\delta }_P(i)$is the segmentation accuracy of the trajectory divided into$i$segments, which is expressed by the trajectory profile fitting degree, and${\delta }_C(i)$is the data compression ratio after the trajectory is divided into$i$segments, i.e., the ratio of the number of compressed trajectory points to the number of original trajectory points.

Therefore, the satisfaction decision function $TSCSuccess$ can be expressed by the compression–accuracy contribution rate, and the input of the function is the segmentation accuracy and data compression rate of the compression trajectory. When the rate declines continuously, it means that the improvement of segmentation accuracy by sacrificing compression rate is not obvious, and segmentation can be terminated at this time. Users can also set the threshold directly to control the segmentation and compression process according to their own separate requirements for compression rate and segmentation accuracy. When the compression rate or segmentation accuracy reaches the threshold, the process will be stopped, and the satisfaction judgment can be customized.

4. Results and Discussion

4.1. Experimental Setting

We use two real trajectory data sets and one simulated trajectory data set of maneuvering target to verify the effectiveness of the PSOTSC algorithm. The first real data set is the Atlantic hurricane data set from the National Hurricane Center (NHC). It contains all the hurricane movement data from 1851 to 2019. This paper uses all the trajectory data with more than two sampling points, including 1861 trajectories and 51,807 sampling points. The longest trajectory has 133 sampling points, and the average length is 27.8, as shown in Figure 5.

Another real data set is the Starkey ungulate telemetry data set. It contains radio-telemetry locations of elk (Cervus elaphus), mule deer (Odocoileus hemionus) and cattle collected at the Starkey Experimental Forest and Range in northeastern Oregon between 1993 and 1996. We randomly selected 67 targets in the data set, including 102,976 location data. Some trajectories are shown in Figure 6. If each target is represented by only one trajectory, the number of points of the longest one is 4007.

The maneuvering target simulation trajectory data set is based on the maneuvering target tracking simulation model in Section 4.2 of [31], which generates 50 trajectories, each with a length of 50. Figure 7 shows all the trajectories of the simulation data set and some typical trajectories. It can be seen that the trajectories generated by the simulation reflect stronger target motion changes and contain certain randomness, which are in line with the motion characteristics of maneuvering targets in the battlefield.

The PSOTSC algorithm in this paper and the compression algorithms such as DP, TRACLUS and TCSS used for comparison were edited and implemented in MATLAB R2016b. All experiments were carried out on Windows 7 operating system with Intel^® Core™ i5-7500, memory size 8 GB.

4.2. Results of Segmentation Accuracy

4.2.1. Real Trajectory Data

We use real data to test the segmentation and compression effect of this algorithm under different numbers of particles and iterations. First, some representative long trajectories in the hurricane data set are segmented. It can be seen from Figure 8 that the segmented trajectories keep the profile features of the original trajectories. By increasing the number of particles from 20 to 50 and the number of iterations from 10 to 20, the segmentation effect is obviously better.

One hundred Monte-Carlo statistical experiments were carried out on the whole hurricane data set to analyze the compression effect of the PSOTSC algorithm; the statistical analysis results are shown in

Table 1. Performance with different parameter values in hurricane data set experiments.

Particles	Iterations	m_CR	sd_CR	m_AY	sd_AY
5	5	23.1972%	0.0237%	98.3321%	0.0102%
10	5	22.5092%	0.0211%	98.354%	0.0069%
20	10	21.6146%	0.0182%	98.3918%	0.0062%
40	15	21.2099%	0.0171%	98.4182%	0.0047%

. Let the mean values of compression rate and accuracy be m_CR and m_AY, respectively, and the standard deviation values be sd_CR and sd_AY. When the segmentation accuracy is controlled at around 98.3%, the overall trajectory compression rate increases with the increase in the number of particles or the number of iterations, which means that the particle swarm optimization can find a better segmentation and compression solution while maintaining the segmentation accuracy. It can be found from the standard deviation results that the standard deviation gradually decreases with the increase in the number of particles and iterations, which indicates that the stability of the optimal search is also increasing.

For ungulate data set, the experiments of the PSOTSC algorithm were also carried out to test the performance. Unlike the experiments for hurricane data set, which uses fixed trajectory segmentation accuracy to find the change of trajectory data compression rate, this time the compression rate is stable at a certain level, i.e., it retains the same number of trajectory points, and finds the change of trajectory segmentation accuracy with the numbers of particles and iterations. One hundred Monte-Carlo statistical experiments were carried out on the whole data set, and the results are shown in

Table 2. Performance with different parameter values in ungulate data set experiments.

Particles	Iterations	Compression Ratio	m_AY	sd_AY
5	5	20%	82.7117%	0.0431%
10	5	20%	83.1876%	0.0368%
20	10	20%	84.1799%	0.0249%
5	5	30%	86.6399%	0.0347%
10	5	30%	87.4521%	0.0254%
20	10	30%	88.6618%	0.0189%

. It can be seen that whether the compression ratio is controlled to 20% or 30%, we can get better trajectory segmentation accuracy with the expansion of particle swarm size and the increase in iteration times. At the same time, we also note that for the ungulate data set, the segmentation accuracy is generally lower than that of the hurricane data set. This is because the trajectories in the ungulate data set have obvious polyline characteristics. Intuitively, the points constituting these polylines should be trajectory feature points, therefore the proportion of redundant data is lower than that of hurricane trajectories, which can be seen from Figure 6.

The advantages of NARJ particle update strategy are verified, and the segmentation accuracy of PSOTSC with NARJ is compared with that of standard PSOTSC with the same number of segments (the same compression ratio), particles and iterations. One hundred Monte-Carlo statistical experiments were carried out on typical trajectories in hurricane and ungulate data sets. The number of particles and iterations is 20 and 10, respectively, and the number of segment feature points increases. The average segmentation accuracy comparison of the two methods under different number of segment feature points is obtained, as shown in Figure 9. When the numbers of particles, iterations and reserved trajectory feature points are the same, the PSOTSC algorithm using NARJ strategy can obtain higher trajectory segmentation accuracy than the standard PSO algorithm. In other words, the neighborhood adjustment and random jump make the particle swarm to search the trajectory segmentation solution in a more reasonable mode.

4.2.2. Maneuvering Target Simulation Data

The profile of hurricane trajectory is relatively simple, and the trajectory generated by the maneuvering target tracking simulation model has more obvious motion changes, including sharp turning, moving along the arc, etc. The segmentation and compression experiments were carried out for typical maneuvering trajectories. As shown in Figure 10, the segmented trajectory generated by PSOTSC can fit the original trajectory profile well.

4.3. Results of Algorithm Comparison

Compared with DP, TRACLUS and TCSS typical segmentation and compression algorithms, the advantage of the PSOTSC algorithm is verified on real trajectory data set and maneuvering target simulation data set. The experimental results are shown in Figure 11. In the experiment of real trajectory data set, the number of initialization particles $N_P$ is 15 and the maximum number of iterations $N_I$ is 5. The DP algorithm needs to adjust the distance threshold to obtain the optimal segmentation, and the threshold sampling point in the experiment is $d_{DP}=[8,6,4,3,2,1.5,1,0.7,0.5,0.3]$. The segmentation algorithm in TRACLUS will be affected by trajectory scaling, and different scaling ratios will affect the segmentation accuracy. The scaling ratio in the experiment is $r_{TRACLUS}=[1,2,3,5,10,15,20,25,30]$. The segmentation accuracy of the TCSS algorithm is affected by the angle threshold setting, and the angle threshold setting in the experiment is $a_{TCSS}=[80,70,60,50,40,30,20,15,10]$. In the experiment of maneuvering target simulation data set, the parameters $d_{DP}$, $r_{TRACLUS}$ and $a_{TCSS}$ still need to be adjusted.

As shown in Figure 11, the segmentation accuracy compression ratio curve obtained by the PSOTSC method is at the bottom of all comparison method curves, which can not only show that the PSOTSC method can achieve the lowest compression ratio under the same segmentation accuracy level, but can also show that the PSOTSC method can obtain the highest segmentation accuracy under the same compression ratio requirements. Therefore, this method has advantages over typical methods in segmentation accuracy and compression ratio.

5. Conclusions

In this paper, we discussed the technical route of swarm intelligence algorithm to solve the problem of trajectory segmentation and compression, and propose a PSOTSC algorithm based on particle swarm optimization, which transforms the trajectory segmentation problem into the global optimization problem of segment feature points. The PSOTSC algorithm makes the selection of feature points more accurate and improves the accuracy of trajectory segmentation. Meanwhile, the particle update strategy based on NARJ is established, which can effectively improve the search efficiency of trajectory segmentation solution. Compared with the standard particle swarm optimization method, the trajectory segmentation accuracy is higher under the same compression rate. The effectiveness of the proposed method is verified by real data set and simulation data set. The experimental results show that the PSOTSC algorithm can obtain a satisfactory segmentation and compression solution, and the compression ratio and segmentation accuracy are better than those in typical algorithms, such as DP, TRACLUS, and TCSS. Because the PSOTSC algorithm belongs to the global-oriented segmentation and compression method, the computational complexity will increase greatly when facing the long trajectory with more sampling points. In future, we will focus on reducing the time complexity of the algorithm and consider the long trajectory pre-segmentation, search by segment and synthesis optimization to expand the applicability of the algorithm. The PSOTSC algorithm takes advantage of SI to obtain the optimization solution through global search, but the problem inherent in the global search algorithm is the large computation. An intuitive and easy solution is that long trajectories can be divided into several short trajectories to search and optimize respectively and then complete the aggregation and overall optimization, but there may be some better way to deal with this issue. Therefore, the next research will focus on the long trajectory global segmentation and compression based on SI methods.