Classification method of marine target motion pattern based on spatial-temporal trajectories

Abstract

Classifying the motion pattern of marine targets is of important significance to promote target surveillance and management efficiency of marine area and to guarantee sea route safety. This paper proposes a moving target classification algorithm model based on channel extraction-segmentation-LCSCA- $l_{{p}}$ norm minimization. The algorithm firstly analyzes the entire distribution of channels in specific region, and defines the categories of potential ship motion patterns; on this basis, through secondary segmentation processing method, it obtains several line segment trajectories as training sample sets, to improve the accuracy of classification algorithm; then, it further uses the Leastsquares Cubic Spline Curves Approximation (LCSCA) technology to represent the training sample sets, and builds a motion pattern classification sample dictionary; finally, it uses $l_{{p}}$ norm minimized sparse representation classification model to realize the classification of motion patterns. The verification experiment based on real spatial-temporal trajectory dataset indicates that, this method can effectively realize the motion pattern classification of marine targets, and shows better time performance and classification accuracy than other representative classification methods.

Keywords

Marine target spatialtemporal trajectory motion pattern sparse reconstruction collaborative representation

1. Introduction

As economic globalization and “ocean century” have come, marine transportation with the merits of large volume of freight traffic, low cost and less energy consumption has become an important bond and bridge of economic trade in the world [1, 2]. In view of that frequent shipping activities caused by increasing ship amount make the global maritime environment to be more complicated and changeable, so how to explore ship’s motion patterns and analyze different ship behaviors is useful to enhance marine surveillance, ship safety and management technology [3]. For example, mastering the motion pattern of various ships near the port can help maritime sectors to recognize abnormal behaviors [4]; surveilling ships with the same motion pattern can timely discover and warn them their dangerous sailing behavior, and prevent ship accident; and finding out different ships’ motion pattern can timely identify illegal fishing activities [5]. Therefore, more and more scholars start to attach importance to the classification of ship motion patterns.

Recently, automatic identification system (AIS) base station and coastal radar station have been established in many coastal areas, which generate numerous dynamic and static ship information. In general conditions, ships’ real-time state can be easily identified according to above information, meanwhile, the marine traffic and ship’s behavior mode can be inferred from historical data to facilitate marine supervision, the discovery of abnormal behavior and the construction of port infrastructures. However, some illegal ships may escape from marine supervision by turning off transponder, tampering location or deliberately transmitting wrong data; at the same time, AIS and radar devices still have the problems of poor data quality and difficulty in identifying target. Due to above reasons, it is usually hard to find out the real type or identity of some ships from historical data, which not only brings challenges to marine surveillance and security defense, but also challenges the data mining work. Thus, correctly classifying and identifying various ship motion patterns has become a crucial task.

In the research of ship motion pattern classification, one of the most common means is the detection technology based on ship pictures or videos collected by monitoring equipment [6]. But monitoring equipment has limited view and is unable to feedback information with strong timeliness, so it is very difficult and highly-cost to timely collect ship pictures and video information in to-be-identified sea area [7]. As all kinds of trajectory data collection systems rise, exploring marine targets’ characteristic pattern by mining spatial-temporal trajectories has become one research hotspot at present [8, 9, 10]. For example, it is feasible to find out attractive marine region from trajectories, further extract and analyze frequent traffic flow activity routes [11, 12]; discover potential periodic activity rule of ships [13]; use the obtained ship characteristic knowledge to discover abnormal ships, including abnormal on/off of AIS device [14], aberrant risk assessment [15], ship traffic changes due to extreme weather [16]; marine traffic flow prediction [17], etc.

From above research results, it is discovered that in the process of mining target trajectory characteristic pattern, the targets with similar property show certain spatial-temporal similarity in their motion tracks, which provides certain support for our classifying target motion pattern by trajectory mining. Recently, trajectory motion pattern classification is mainly applied in traffic planning of smart city and identification of users’ traffic trajectory and motion behavior [18, 19]. For example, identify if a user goes out by bike, by bus or drives out [20]; identify if a taxi is carrying passengers, is empty, or stops at some place [21]; identify human action such as walking, jogging, clapping, etc. [22] Gonzalez et al. [23] utilized neural network to automatically identify travelling mode, retained more important trace point information on the basis of filtering out unnecessary GPS data, and took average speed and stay time as network input to realize the classification of travelling mode. Sun et al. built test program Hidden Markov Model (BP-HMM) to identify various human motion patterns [24]. Fielda et al. used Gaussian mixture clustering algorithm to dynamically time align trajectories, and developed an unsupervised classification method to describe and classify human motion trajectory [25]. Santos et al. depended on practical human motion trajectory, used Dynamic Bayesian network (DBN) model to classify human behaviors, and applied sliding window method to improve model performance and validity [26]. Chen et al. utilized Matching Pursuit – Fletcher Reeves (MPFR) method to explore the classification of ship motion pattern in inland waterway [27].

Above research is heuristic to our exploring the classification of marine target motion patterns. But considering that marine region is a free moving space, which is different from road network limiting vehicle and human motion, and there is no sea lanes for ships in sea area [28], so it is more difficult to discover valuable knowledge from marine trajectory. Based on above idea, this paper extracts channel distribution in sea area, proposes an $l_{{p}}$ norm minimization based sparse representation classification model ( $l_{{p}}$ -SRC), and takes training sample sets of known identifiers as the over-complete basis of trajectory dictionary to classify ship trajectory in standard channel. In the end, the paper runs the proposed algorithm by real AIS shipping data, and verifies the validity of algorithmic model, which can realize the classification of motion mode of marine targets in specific sea area.

2. Problem modeling

Ship trajectory is the sequential trace points of sampling data points ranked according to time sequence. Suppose there are N targets in selected specific time interval and region coverage R, in which the ship trajectory of target $i$ is expressed as $T_{i}=\langle{p_{i,1},p_{i,2},\ldots,p_{i,n}}\rangle$ , $p_{i,k}=({l_{i,k},t_{i,k},s_{i,k},c_{i,k}})({k\in\{{1,2,\ldots,n}\}})$ represents the location $l_{i,k}$ , speed $s_{i,k}$ and steering angle $c_{i,k}$ of target at moment $t_{i,k}$ . Unlike traffic roads on land, marine traffic flow has a wide sailing range but no explicit limit to sailing route; in the meantime, due to the existence of a lot of small and medium-sized operation vessels such as fishing boats and tugboats, the ship trajectory distribution in the region is more random and scattered. In order to study the motion pattern of marine target, it is first to ensure such motion pattern has certain periodic rule, purposiveness and representativeness [4]. Hence, mining hot channels in the region and screening out ship trajectories with representative channel are one of our preliminary treatment means to analyze target motion pattern within sea area coverage. The paper uses meshes to divide trajectory data of ships within sea areas, proposes wavelet clustering based ship channel extraction algorithm, and chooses representative tracks from main channels for further analysis. Related research will be introduced in Section 2.1 in details.

Figure 1.

Schematic diagram of similar sub-segments.

In real conditions, because of different ships’ moving time, route, and trajectory position data distribution frequency, the motion trajectory of each sailing segment has different lengths. Meanwhile, generally, it is hard to find out highly similar representative tracks from a whole channel, and similar tracks always only exist in sub-segments which satisfies similar constraint of time and space [29], as shown in Fig. 1. In order to form various standard motion pattern trajectory training samples, we need to accurately describe each representative similar sub-segment, and obtain fixed-length vector as over-complete basis function. The paper adopts the secondary segmentation based Least-squares Cubic Spline Curves Approximation (LCSCA) technology to describe the sub-motion trajectory in samples. Related research will be introduced in Section 2.2 in details.

Figure 2.

Framework of classifying motion pattern of maritime target.

Regarding the obtained training sample sets and unclassified tracks containing a great number of motion trajectory labels, we build a marine target motion pattern classification model by establishing trajectory dictionary consultation, label the linear combination of training samples to approximate all unknown tracks, and figure out the residue and minimum of unknown track under over-complete basis through $l_{{p}}$ -SRC algorithm. The track with minimum value belongs to such motion pattern. Related research will be introduced in Section 2.3 in details.

The framework of entire motion pattern classification is shown in Fig. 2. The classification process can be summarized as: first, obtain common channels in selected sea area, determine the motion pattern categories in this region and the beginning and ending boundary of trajectories; second, use secondary segmentation method to obtain the sub-tracks with similar characteristics in each trajectory category, describe each trajectory segment by LCSCA algorithm, and obtain training sampling sets with fixed length as over-complete basis of trajectory dictionary; third, obtain the residual sum between to-be-classified trajectories and each kind of over-complete basis by $l_{{p}}$ -SRC model, in which that has the minimal residual sum falls into such kind of motion pattern.

3. Algorithm overview

3.1 Wavelet clustering based sea area channel extraction

Figure 3.

Difference maps between road network and sea area traffic trajectory distribution.

Now, the research of classification of target’s motion pattern has been widely used in taxi’s passenger carrying behavior analysis [30], bicycle-sharing behavior rule [31], traffic jam rule, etc. The precondition of analyzing the spatial-temporal trajectory big data generated by such moving objects is to understand the road distribution information they have traveled. As shown in Fig. 3, compared to on-land roads, there is no man-made channels in the sea, and the marine situation is more complex due to various external influential factors such as climate, ocean current and accidence [34]. So, in order to analyze the motion pattern of marine targets, the first thing is to acquire the channel distribution in sea area. Generally, channel extraction has two problems: 1) since the offshore region and the region near ports are required to report to navigation management department or avoid ships, and high seas region is very broad, so the magnitude of ships’ trajectory data in different regions at the same time scope differs apparently, which makes channel pattern extraction to become very complicated; 2) in big data environment, the clustering of trajectories has the problems such as large calculation amount, long response time and needing to define cluster number, which is particularly bad for our quickly adapting to channel pattern extraction. This section raises a wavelet clustering based sea area channel extraction algorithm, as shown in Fig. 4. The research starts from four respects: 1) data preprocessing; 2) meshing processing; 3) wavelet transform; 4) search for connected region and construct cluster.

Figure 4.

Steps of traffic pattern extraction based on wavelet clustering.

3.1.1 Data preprocessing

Track preprocessing is mainly to remove large-range track hopping, track point landing and other noise points resulted from physical factors like equipment failure and startup & shutdown abnormality and external factors like geographic environment and weather. It also detects the stay point of ships when they are located in berth and anchorage, and individually analyzes the ship tracks generated during sailing to ensure the accuracy of subsequent channel pattern extraction.

(1) Remove wrong data

Remove illogical track points caused by mechanical equipment, etc., which include track points distributed on land; track points with the longitude $>$ 180 ${}^{\circ}$ or $<$ $-$ 180 ${}^{\circ}$ and the latitude $>$ 90 ${}^{\circ}$ or $<$ $-$ 90 ${}^{\circ}$ ; track points with navigational speed of negative value or greater than 30 knots/hour; the neighboring track points of the same target which has large-range hopping of distance within a short time.

(2) Detect and remove mooring

When a ship docks at a port or a mooring, a large number of data points with minimal location error may generate which are more frequent compared to those generate during sailing. These points will not only interfere our selection of threshold in channel extraction, but also affect region segmentation precision and increase calculation amount. So, we deem the track point of the same target with navigational speed less than 3 knots/hour and adjacent points distance less than 0.1 ${}^{\circ}$ as the mooring point, and analyze them separately.

3.1.2 Meshing processing

The data structure form applicable to wavelet clustering calculation is shown in Eq. (3.1.2). The track points taking vector chain as subject are evidently not applicable to wavelet clustering. Meanwhile, to improve data processing efficiency and reduce data quantity, it is necessary to perform rasterization processing of regional data, and generate quantified characteristic space for further analysis.

$\displaystyle\qquad\qquad\qquad\qquad\quad\textit{Dimension}$ $\displaystyle R=\left[\begin{array}[]{*{20}c}{r_{1}}\\ {r_{2}}\\ \vdots\\ \vdots\\ {r_{n}}\\ \end{array}\right]\begin{array}[]{*{20}c}\rightarrow\\ \rightarrow\\ \\ \\ \rightarrow\\ \end{array}\left[\begin{array}[]{*{20}c}{a_{11}}&{a_{12}}&{a_{13}}&\ldots&{a_{% 1m}}\\ {a_{21}}&{a_{22}}&{a_{23}}&\ldots&{a_{2m}}\\ {a_{31}}&{a_{32}}&{a_{33}}&\ldots&{a_{3m}}\\ \vdots&\vdots&\vdots&&\vdots\\ {a_{n1}}&{a_{n2}}&{a_{n3}}&\ldots&{a_{nm}}\\ \end{array}\right],({n\times m})$ (1)

The to-be-analyzed region $R$ is divided into $n\times n$ meshes, and the number of track points in unit area of each mesh is the ship density of this unit. The mesh width is shown in Eq. (2).

$\displaystyle\Delta\textit{lon}=\frac{\textit{lon}_{\max}-\textit{lon}_{\min}}% {n}$ (2) $\displaystyle\Delta\textit{lat}=\frac{\textit{lat}_{\max}-\textit{lat}_{\min}}% {n}$

in which, $\textit{lon}_{\max}$ , $\textit{lon}_{\min}$ , $\textit{lat}_{\max}$ and $\textit{lat}_{\min}$ are the longitude and latitude boundaries of a track point in data space. Figure out the number of track points in each mesh, then the density quantification characteristic matrix can be obtained.

$\displaystyle M_{n\times n}=\textit{count}\left({\begin{array}[]{l}\textit{lon% }_{\min}+({n-1})\Delta\textit{lon}<\textit{lon}<\textit{lon}_{\min}+n\Delta% \textit{lon}\\ \textit{lat}_{\min}+({n-1})\Delta\textit{lat}<\textit{lat}<\textit{lon}_{\min}% +n\Delta\textit{lat}\\ \end{array}}\right)$ (3)

3.1.3 Wavelet transform

Wavelet transform is an essential step in wavelet clustering. Through wavelet transform, the mesh characteristic space can be transformed to the transformation space of frequency domain, to reduce data scale and facilitate clustering operation. A mesh characteristic space M composed by density quantification characteristic matrix receives two-dimensional discrete wavelet transform of 1 scaling, as shown in Fig. 5. The unit in mesh space M keeps a same-position constant-proportion mapping relationship with the low-frequency unit LL ${}_{1}$ in one-dimensional discrete wavelet transform and the low-frequency unit LL ${}_{2}$ in two-dimensional discrete wavelet transform.

Figure 5.

Two-dimensional discrete wavelet transform.

Suppose the selected basis function and scaling function are $\psi({x,y})$ and $\varphi({x,y})$ , respectively. For mesh space $M_{n\times n}$ , we have forward transform,

$\displaystyle W_{\varphi}({j_{0},n})=\frac{1}{n}\sum_{x=1}^{n}{\sum_{y=1}^{n}{% M({x,y})\varphi_{j_{0},n}}}({x,y})$ (4) $\displaystyle W_{\psi}^{l}({j,n})=\frac{1}{n}\sum_{x=1}^{n}{\sum_{y=1}^{n}{M({% x,y})\psi_{{}_{j,n}}^{l}}}({x,y})$

in which, $j_{0}$ is the initial dimension, $l\in\{{1,2,3}\}$ . The discrete wavelet transform adopts down-sampling processing method. Every time being decomposed, the size of low-frequency mesh will be half of the last level, but the width will be twice [33]. Then, the transform space Q is acquired. In view of Haar wavelet function has orthogonal property and discrete transform property, in particular, it has finite compact property in time and frequency domain, it is very appropriate for transform of massive spatial-temporal trajectory big data spatial feature. So this paper chooses Haar wavelet as the basis function.

3.1.4 Extract connected channel

After obtaining the transform space Q, we have to search for connected regions as regional channel based on the idea of density, to build channel clusters. Here, it is required to set the transform unit density threshold $\delta$ , define the mesh unit greater than threshold $\delta$ as “significant unit”, the mesh unit less than threshold $\delta$ as “non-significant unit”, and unit with value of zero as “zero unit” [34].

Definition 1 Regarding any two mesh units $d_{i}$ and $d_{j}$ in transform space Q, if there is adjacent fixed point or adjacent edge between them, then the spatial position relationship between the two is called adjacent relation;

Definition 2 Take any one “significant unit” as a starting point. If there is a “significant unit” in 8 regional units of its adjacent meshes, then we deem them as the connected part and continue to search until the surroundings are “non-significant units” or “zero units”. We will take this connected region as a channel cluster.

Multiple connected channel clusters in transform space Q are labelled in sequence. Due to the mapping relation between unit and special type of space in transform space, we can easily obtain the cluster label of data in original characteristic space, and take the points without cluster label as abnormal or noise point, to complete the extraction of channel distribution features in the region.

3.2 Secondary segmentation based least square cubic spline curve trajectory description

Figure 6.

Basic motion mode of vessel trajectory.

Ship’s motion trajectory with difference lengths can’t be directly used in the classification of ship motion patterns. In order to obtain the fixed length vector of motion trajectory, we can use the Least Square Cubic Spline Curve Approximation (LCSCA) technology [36] to extract the same quantity of sample description trajectories. In Fig. 6, generally speaking, a ship trajectory has three behaviors: berthing, steering and line navigation. When the steering area of a mobile target is too large, or its turning angle is too large, the curve fitting is easy to show over-fitting condition, and the obtained curve by fitting fails to precisely describe real trajectory. Thus, we need to conduct secondary segmentation on all trajectories in the region: first, set speed and time thresholds according to trajectory features of mooring region, divide the trajectory $T_{i}$ of target $i$ into several voyages $T_{i}=\langle{t_{1},t_{2},\ldots}\rangle$ , and each voyage should has similar mooring region; second, set steering threshold, divide voyage $t_{j}$ into several line sub-trajectories $t_{j}=\langle{\textit{sub}\_t_{1},\textit{sub}\_t_{2},\ldots}\rangle$ , ensure the similarity of sub-track segment in training samples, and guarantee track over-fitting will not occur in LCSCA processing.

Take sub-trajectory $\textit{sub}\_t_{j}$ as an example. Use its trajectory data $\textit{sub}\_t_{j}=\langle{p_{j,1},p_{j,2},\ldots,p_{j,m}}\rangle$ to calculate the coefficient parameters of cubic B-spline basis function according to the recurrence Eq. (3.2):

$\displaystyle k_{j,1}=\left\{{\begin{array}[]{ll}1&\text{if }l_{j-1}<l_{j}<l_{% j+1}\\ 0&\text{otherwise}\\ \end{array}}\right.$ (5) $\displaystyle k_{j,m}=\frac{l-l_{j}}{l_{j+m}-l_{j}}k_{j,m-1}(l)+\frac{l_{j+m+1% }-l_{j}}{l_{j+m+1}-l_{j+1}}k_{j+1,m-1}(l)$

in which, $l_{j,m}$ is the position coordinates of trajectory points, thus, we can obtain the reconstruction curvilinear equation of trajectory. Take $n$ points as the fixed length $C_{j}^{X,Y}=\langle({C_{j,1}^{X},C_{j,1}^{Y}}),({C_{j,2}^{X},C_{j,2}^{Y}}),% \ldots,\linebreak({C_{j,n}^{X},C_{j,n}^{Y}})\rangle$ of trajectory sample, thereby, we successfully transform the linear sub-trajectory $\textit{sub}\_t_{j}$ into a training sample points set $C_{j}^{X,Y}$ with unified length and interval.

$\displaystyle C^{X,Y}=\phi_{j}^{-1}l_{j}$ (6)

in which, $\phi_{j}$ is shown in Eq. (7).

$\displaystyle\phi_{j}^{=}\left[\begin{array}[]{*{20}c}{k_{1,1}}&\cdots&{k_{1,m% }}\\ \vdots&\ddots&\vdots\\ {k_{j,1}}&\cdots&{k_{j,m}}\\ \end{array}\right]$ (7)

3.3

l_{p}

norm minimization-based sparse representation motion pattern classification model

This section mainly introduces the $l_{p}$ norm minimization-based sparse representation classification method. The essence of sparse representation classification is to put different types of objects into training set and build category dictionary. When you need to classify one test sample object, each type of sample object in training set is taken as over-complete basis function, to describe this unknown type of object through linear combination, and calculate its residual sum with respect to various objects. When the residual sum shows one category is very small while other categories are very large, this test sample trajectory belongs to such motion pattern. In the research of this paper, the sample data is the ship trajectories, and each training sample trajectory can be described as the segmentation LCSCA processing based isometric reconstruction vector $d=\langle{({C_{1}^{X},C_{1}^{Y}}),({C_{2}^{X},C_{2}^{Y}}),\ldots,({C_{n}^{X},C% _{n}^{Y}})}\rangle$ .

Suppose there are ships with $J$ types of motion pattern in the research range, $D_{i}=\{d_{1,1},d_{1,2},\ldots,\linebreak d_{1,K}\}$ , $i\in({1,J})$ is the trajectory set of each type of motion pattern in the region, in which, $K$ denotes to the sample number of the $i^{\text{th}}$ type of trajectory, then the description of SRC dictionary is shown in Eq. (8).

$\displaystyle D=[{D_{1},D_{2},\ldots,D_{J}}]=[{d_{1,1},\ldots,d_{1,K},\ldots,d% _{J,1},\ldots,d_{J,K},}]$ (8)

All test trajectories $Y=[{y_{1},y_{2},\ldots,y_{\eta}}]$ can be represented as spline trajectory set by dictionary

$\displaystyle Y=D\Psi$ (9)

in which, $\Psi$ denotes to the coefficient matrix of test trajectory $Y$ in sample dictionary $D$ . Considering there are a lot of zero factors in the $\Psi$ matrix in practical application, so it can be also said that $\Psi$ is the sparse representation of trajectory $Y$ in dictionary set. Generally, non-zero elements can be solved through $l_{0}$ norm minimization model. The solution model is constructed as shown in Eq. (10).

$\displaystyle\hat{\Psi}=\mathop{\arg\min}\limits_{\Psi}\{{\|{y-D\Psi}\|_{2}^{2% }+\lambda\|\Psi\|_{0}}\}$ (10)

in which, $\|\Psi\|_{0}$ is the zero norm of $\Psi$ , $\lambda$ is the correction coefficient. By figuring out the residual sum of all training sample categories in the dictionary to test trajectory, we can finally determine that the test trajectory category is the sample category with the minimal residual sum, to realize the classification of motion pattern of unknown test samples.

$\displaystyle R=\|{y-D\hat{\Psi}}\|_{2}$ (11) $\displaystyle\textit{Classification}(y)=\mathop{\arg\min}\limits_{i}({R_{i}}){% i\in({1,2,\ldots,J})}$

Nevertheless, in practical solving process, the model 10 has NP-hard problem, that’s to say, a lot of time will be spent in the process of solving the minimum vale [27], which is not applicable to our practical application. At the same time, the specific regional analysis selected by us belongs to small sample classification problem, which could not represent all motion patterns in this region within the specific time period of the research, and different type of trajectories always has certain local similarity. Thereby, we consider to convert $l_{0}$ sparse representation problem into $l_{p}$ norm based collaborative representation problem [36], and utilize Tikhonov regularization to determine correction coefficient and coefficient vector, as shown in Eq. (12).

$\displaystyle\hat{\Psi}=\mathop{\arg\min}\limits_{\Psi}\{{\|{y-D\Psi}\|_{2}^{2% }+\tilde{\lambda}\|{L\Psi}\|_{p}}\}$ (12)

In the equation, $L$ is Tikhonov regularization matrix, and $\tilde{\lambda}$ is the regularization parameter. Determining $\tilde{\lambda}\|{L\Psi}\|_{p}$ by regular term could not only add certain sparse constraint to final solution, and the calculation process is obviously better than model 10, so it is more suitable to solve the problem in this paper; in the meantime, Tikhonov regular term can add a small disturbance to every diagonal element of non-full rank covariance matrix, making singular covariance matrix inversion change to non-singular matrix inversion, so as to realize stable optimal solution and add certain sparse constraint. This can’t be satisfied by pure $l_{p}$ norm regular term. Similar to $l_{p}$ norm based classification method, we use Eq. (3.3) to calculate residual sum and judge the category of test trajectory. According to these, through segmenting and reconstructing LCSCA trajectory, SRC dictionary is constructed to realize the entire steps of classifying motion pattern of marine target, as shown in Fig. 7.

Figure 7.

Trajectory moving target classification based on channel extraction-segmentation-LCSCA- $l_{p}$ -norm minimization model.

4. Experimental results and analysis

4.1 Experimental environment

The stock spatial-temporal trajectory data used in the experiment are all AIS information broadcast by marine ships including location information. The data region is the Bohai Sea-Yellow Sea region in China (with east longitude of 120 ${}^{\circ}$ $\sim$ 122 ${}^{\circ}$ and northern latitude of 37.5 ${}^{\circ}$ $\sim$ 39 ${}^{\circ}$ ). The data was collected on January 2019. There are 2,658,701 AIS data in total. The whole data distribution is shown in Fig. 8a. The original data includes a small number of error data and a large number of mooring trace points, and the regional sailing data distribution obtained by preprocessing according to Section 2.1.1 is shown in Fig. 8b. The experiment takes 80% data as training sample set and 20% data as test dataset to verify the applicability of algorithmic model.

In order to study the motion pattern of targets, first, we need to perceive the channel distribution of concerned region, extract representative periodic trajectory in the channel. According to the requirement of trajectory classification, every training sample target needs to be segmented into several sub-trajectories according to voyage number and maneuver times, and constitutes the classification dictionary over-complete basis with fixed length through trajectory description method. Through consulting “dictionary”, we can obtain the residual sum of test trajectory under over-complete basis of several types of targets, and that with minimum corresponding residual sum is such type of ships, so as to realize the classification of test targets. The experimental results are shown in Section 3.2.

Table 1
Comparison of LCSCA accuracy between primary and secondary segmentation

Algorithm	Least square cubic spline root-mean-square error (RMSE)
	Training set 1	Training set 2	Training set 3	Training set 4
Primary segmentation	0.1058	0.0852	0.2239	0.0622
Secondary segmentation	0.0257	0.0129	0.0312	0.0202

Figure 8.

Experimental data distribution and channel distribution.

Figure 9.

Four motion mode trajectories and trajectory distribution after one or two LCSCA algorithm trajectory descriptions.

4.2 Experimental results

In the experimental process, we divide the region into 100 meshes, use Harr wavelet to conduct scale transformation twice, take 20% of maximum value of trace points in mesh region as deviation threshold to divide regional channel distribution, as shown in Fig. 8c. In the figure, the region meshes where blue points are distributed are our identified channel distribution meshes, and red points are deviation points. It can be seen from the figure that, ignoring two passing channels extending from northwest to southeast, the entire region has four channels stretching across the Bohai Sea-the Yellow Sea area, which can represent four motion patterns. From these channels, we select 289 representative target trajectories in total from every channel segment to compose the training sample set. The distribution condition of them in the region is shown in Fig. 8d. The trajectory distribution of four motion patterns is shown in Fig. 9a.

The trajectory distribution of adopting primary and secondary segmentation LCSCA trajectory description methods is shown in Fig. 9b. It can be seen from the figure that the LCSCA trajectory description after secondary distribution according to steering points is more accurate than that after the primary distribution. Especially under the third type of motion pattern, when the trajectory maneuver time is very frequent, it is worth discussing on the accuracy of overall trajectory description of primary voyage. We measure the accuracy between the two methods by working out the root-mean-square error (RMSE) between fitting trajectory and real trajectory, as shown in Table 1. It shows that the LCSCA algorithm after secondary segmentation is more accurate than that after primary segmentation, so it is essential to conduct secondary segmentation for us to build over-complete basis.

4.3 Performance analysis

In order to better evaluate the algorithmic performance in this paper, the algorithmic classification accuracy is measured by true positive rate (TPR).

$\displaystyle\textit{TPR}=\frac{TP}{TP+FN}$ (13)

in which, TP is the number of A-type ship motion that is correctly classified as type A, while FN is the number of A-type ship motion that is wrongly recognized as other categories. TPR can state the accuracy of correctly classifying as A-type ship motion pattern. Table 2 compares the proposed algorithm, the nearest neighbor classification algorithm (knn), the linear kernel function support vector machine algorithm (svm-linear) and the Gaussian radial basis kernel function support vector machine algorithm (svm-rbf). In the table, the proposed algorithm has the highest classification accuracy than the other three motion patterns, and its overall classification accuracy is higher than the other three algorithms. Compared to other methods, the proposed algorithm has better performance and stability in classifying various motion patterns and is superior to other existing algorithms.

Table 2

Algorithm classification accuracy comparison

Motion pattern	Classification accuracy (TPR)/%
	knn	svm-linear	svm-rbf	Proposed algorithm ( $l_{p}$ -SRC)
Motion pattern 1	97.75	100	100	98.04
Motion pattern 2	92.34	84.64	83.25	98.21
Motion pattern 3	91.60	94.81	95.44	95.83
Motion pattern 4	96.51	82.38	85.90	97.62
Total	95.04	91.36	92.20	97.45

Table 3 summarizes the comparison of four algorithms on running time. It is discovered that the proposed algorithm is better than other algorithms in time performance. When it is applied in the motion pattern classification with mass data, the calculating time-efficient advantage of its algorithm will be more evident, which is more in line with our requirement on spatial-temporal big data mining.

Table 3

Comparison of running time of different algorithms

Method	Running time/(s)
knn	12.5267
svm-linear	4.3269
svm-rbf	9.7131
Proposed algorithm ( $l_{p}$ -SRC)	3.6632

Through above contrast experiment, we can come to the following conclusion:

(1)

It is feasible to use spatial-temporal trajectory data to classify motion patterns of marine targets;

(2)

The proposed trajectory moving object classification algorithm model based on channel extraction-segmentation-LCSCA- $l_{p}$ norm minimization can better solve the classification of marine target motion pattern in terms of classification accuracy and time performance.

5. Conclusions

This paper mainly lies on the idea of spatial-temporal trajectory data mining, and solves the classification problem of marine target motion pattern. The proposed trajectory moving object classification algorithm model based on channel extraction-segmentation-LCSCA- $l_{p}$ norm minimization defines multiple type of motion patterns through analyzing the channel distribution condition in specific sea area. On this basis, it uses LCSCA algorithm with secondary segmentation to build over-complete basis “dictionary” of each type of motion pattern with fixed length. Finally, the idea of $l_{p}$ norm minimization is introduced in the sparse representation classification, to judge the motion pattern category of to-be-tested trajectory. Through the verification of real dataset, the proposed algorithm performs well in classification accuracy and time efficiency, and has a good stability when responding to different types of motion patterns.

This classification method can be applied in trajectory analysis and behavior recognition of targets under complicated sea area environment. Through mastering the motion pattern of normal traffic flow in the region, it monitors and alerts the marine target with special and abnormal behavior pattern, and assists to complete the daily sea area control of relevant departments.

References

Fan

, The Spatial-temporal Evolution of the World Marine Transportation Pattern, Ph.D. Dissertation, East China Normal University, 2014.

and Guo

H.R.

, Empirical analysis of the influencing factors of China’s maritime trade competitiveness, International Business Research 000(3) (2013), 46–53.

Zhou

S.B.

and Xu

W.X.

, Research progress on anomaly detection in vessel trajectory, Journal of Electronic and Instrumentation 31(3) (2017), 329–337.

Wei

Z.K.

Zhou

Wei

and Shi

G.Y.

, Ship motion pattern recognition and application based on AIS data, Journal of Shanghai Maritime University 37(2) (2016), 17–22, 71.

Zhang

Jin

Zhang

et al., Distribution of bottom trawling effort in the yellow sea and east China sea, Plos One 11(11) (2016), e0166640.

Liu

Z.J.

, Research on Major Characteristics of Marine Traffic Based on AIS Data, Ph.D. Dissertation, Dalian Maritime University, 2019.

Cui

T.T.

Wang

G.L.

and Gao

, Ship trajectory classification method based on 1DCNN-LSTM, Computer Science 9 (2020), 175–184.

Jeung

Yiu

M.L.

Zhou

et al., Path prediction and predictive range querying in road network databases, LDB Journal 19(4) (2010), 585–602.

Wei

L.Y.

Zheng

and Peng

W.C.

, Constructing popular routes from uncertain trajectories, in: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing, 2012, pp. 195–203.

10.

Xue

A.Y.

Zhang

Zheng

et al., Destination Prediction by Sub-Trajectory Synthesis and Privacy Protection Against Such Prediction, in: IEEE International Conference on Data Engineering, 2013, pp. 254–265.

11.

Liu

Q.E.

Xiao

J.C.

Ding

Z.M.

et al., Discovery of hot region in trajectory databases, Journal of Software 24(8) (2013), 1816–1835.

12.

Yin

F.J.

Yao

C.L.

et al., Mining frequent spatio-temporal items in trajectory data, International Journal of Database Theory & Application 8(4) (2015), 149–156.

13.

Zhang

Lee

and Lee

, Periodic Pattern Mining for Spatio-Temporal Trajectories: A Survey, in: Intelligent Systems and Knowledge Engineering (ISKE), TaiPei, 2015, pp. 306–313.

14.

Mazzarella

Vespe

Alessandrini

et al., A novel anomaly detection approach to identify intentional AIS on-off switching, Expert Systems with Application 78(JUL.) (2017), 110–123.

15.

Miyake

Itoh

Nishizaki

et al., Safety assessment for establishing ships’ routing: Recommended route off the western coast of Izu O Shima Island, in: 2017 Fourth Asian Conference on Defence Technology(ACDT), Tokyo, 2017, pp. 1–6.

16.

Velarde-Alvarado

Martínez-Herrera

and Iriarte-Solís

, Traffic pattern detection using the Hough transformation for anomaly detection to improve maritime domain awareness, in: International Conference on Information Fusion, Salamanca, 2014, pp. 1–6.

17.

Brian

and Lokukaluge

P.P.

, A dual linear autoencoder approach for vessel trajectory prediction using historical AIS data, Ocean Engineering 209 (2020), 1–13.

18.

Zhao

Z.J.

and Ji

G.L.

, Research progress of spatial-temporal trajectory classification, Journal of Geo-information Science 19(003) (2017), 289–297.

19.

Cui

Y.Y.

, Bin

et al., Temporal association rules discovery algorithm based on improved index tree, Applied Mathematics and Nonlinear Sciences (2021), 00001024782021100016.

20.

Biljecki

Ledoux

and Van Oosterom

, Transportation mode-base segmentation and classification of movement trajectories, International Journal of Geographical In-formation Science, 27(2) (2013), 385–407.

21.

Zhu

Zheng

Zhang

et al., Inferring taxi status using GPS trajectories, Computer Science 5 (2012), 1–13.

22.

Calinon

Guenter

and Billard

, On learning, representing, and generalizing a task in a humanoid robot, IEEE Transactions on Systems Man & Cybernetics Part B 37(2) (2007), 286–298.

23.

Gonzalez

P.A.

Weinstein

J.S.

Barbeau

S.J.

et al., Automating mode detection using neural networks and assisted GPS data collected using GPS-enabled mobile phones, in: 15th World Congress on Intelligent Transport Sys-tems and ITS America’s 2008 Annual Meeting, 2008, pp. 30267–30279.

24.

Sun

S.L.

Zhao

and Gao

Q.B.

, Modeling and recognizing human trajectories with beta process hidden markov models, Pattern Recognition 48(8) (2015), 2407–2417.

25.

Matthew

David

Pan

Z.X.

et al., Recognizing human motions through mixture modeling of inertial data, Pattern Recognition 48(8) (2015), 2394–2406.

26.

Luís

Khoshhal

and Dias

, Trajectory-based human action segmentation, Pattern Recognition 48(2) (2015), 568–579.

27.

Chen

Xue

et al., Classification of vessel motion pattern in inland waterways based on automatic identification system, Ocean Engineering 161(aug.1) (2018), 69–76.

28.

Wen

Y.T.

Lai

C.H.

Lei

P.R.

et al., RouteMiner: Mining Ship Routes from a Massive Maritime Trajectories, in: IEEE International Conference on Mobile Data Management, 2014, pp. 353–356.

29.

Sun

Zhou

Guan

et al., Mining spatial-temporal motion pattern for vessel recognition, International Journal of Distributed Sensor Networks 14(5) (2018), 1–11.

30.

Feng

Q.S.

, Research on Residents’ Trip Hot Routes and Attractive Areas Based on Taxi Trajectory Data, Ph.D. Dissertation, Chongqing University, 2016.

31.

Zhang

R.J.

, Optimization Research on Urban Bus Line Network Based on Shared Bicycle Track, Ph.D. Dissertation, Xi’an University of Technology, 2019.

32.

H.Y.

, Temporal and Spatial Characteristics of Urban Traffic Based on Taxi Trajectories, Ph.D. Dissertation, Nanjing University, 2019.

33.

Kishore

, Character segmentation from multi-oriented video words using discrete wavelet transform and k-means clustering, IJSEAT 2(12) (2015), 1033–1039.

34.

Zhou

and Lu

H.L.

, Research progress of clustering algorithm in data mining, Computer Engineering and Applications 48(12) (2012), 100–111 (in Chinese).

35.

Wang

Zheng

X.F.

and Pu

, Pattern recognition of approach landing trajectories in terminal air space based on wavelet clustering, Computer Applications and Software 33(011) (2016), 112–116.

36.

Wang

L.Z.

T.R.

and Li

, Trajectory analysis algorithm based on least-squares cubic spline curves approximation feature and collaborative representation, Journal of University of Jinan (Science and Technology) 31(003) (2017), 202–207.

Classification method of marine target motion pattern based on spatial-temporal trajectories

Abstract

Keywords

1. Introduction

2. Problem modeling

3.1 Wavelet clustering based sea area channel extraction

(1) Remove wrong data

(2) Detect and remove mooring

3.1.2 Meshing processing

3.2 Secondary segmentation based least square cubic spline curve trajectory description

4.1 Experimental environment

Table 1 Comparison of LCSCA accuracy between primary and secondary segmentation

4.3 Performance analysis

References

Table 1
Comparison of LCSCA accuracy between primary and secondary segmentation