# A Novel Adaptive Visual Analytics Framework for Multiship Encounter Identification

Authors: Rong Zhen; Ziqiang Shi
Journal: Journal of Advanced Transportation
 (2021)

---

## Abstract

The automatic identification of multiship encounter is a vital criterion for ship collision avoidance and intelligent maritime safety surveillance. However, the parameters of ship encounter identification in the existing studies are fixed, and the methods are weak to give an automatic and visual performance in the multiship encounter identification. In order to fix the existed gap, this paper proposed a novel adaptive visual analytics framework for automatic multiship encounter identification based on density-based spatial clustering of applications with noise (DBSCAN) and visual analytics by adjusting the parameters of ship encounter adaptively. The DBSCAN clustering method was applied to detect the clusters of encounter ships and filter out the nonencounter ship, and the distribution and density of the encounter ship had been visualized on the nautical chart to give a better perception of ships’ behavior with a potentially high navigational risk. The framework had been designed and developed using DBSCAN and visual analytics, and the effectiveness was evaluated and validated by adjusting different parameters of multiship encounter within the Southwest waters of Zhoushan Island, China. The results showed that the proposed framework had a good performance in the visual identification of multiship encounter within confined waters, which could assist the ship collision avoidance and intelligent maritime surveillance system.


---

## Body

## 1. Introduction

Maritime transport constitutes the arteries of global trade; more than 90% of the world trade volume is transported by sea [1]. The maritime transportation plays a significant role in the development of international society; it is urgent to ensure the maritime safety and environment protection [2–5]. The huge volume of ships challenges the safety and security within the confined and coastal waters [6]. There are still ship-ship collisions or grounding accidents occurring inevitably every year, and the collision accidents bring loss of life, property, and pollution to the marine environment [7]. In order to decrease the probability of accidents, optimize the traffic flow, and coordinate ships’ berthing sequence and protect the environment, some maritime traffic aids and surveillance systems have been installed. The surveillance systems are usually composed of radar, automatic identification system (AIS), port security system (PSS), vessel traffic service system (VTS), and video surveillance [8, 9].The situation of ship encounter is a prerequisite for ship collision accident, so the multiship encounter identification is a vital criterion to assess the maritime safety level and give suggestions about taking proactive collision avoidance actions to mitigate the possibility of collision accidents [10, 11]. However, exploring, analyzing, detecting, and ranking the potential ships in collision risk within the surveillance screen is a complex and challenging task for the operators in the surveillance systems. Facing the huge volumes of ships sailing within the surveillance waters (confined or harbor waters) during the rush hours, the cognitive working load of limited operators would be overwhelmed and compromised [12, 13], which will affect the performance and effectiveness of surveillance system to some extent. The intelligent maritime surveillance system with visual analytics functions would give the operator concrete encountering ships and reduce operators’ cognitive load when monitoring maritime traffic, allowing preventive actions before an emergency or collision accident occurs.The multiship encounter identification is a key problem that faces great difficulty and challenge; the main innovative contribution of this paper is that a novel adaptive visual analytics framework of the multiship encounter identification has been proposed, and the newly developed framework can contribute to the intelligent maritime traffic surveillance under number of ships sailing within a port in the visual and automatic way. Different from the previous work, this paper designed a novel framework that can adjust the ship encounter radius and the minimum number of sailing ships by introducing visual analytics and get flexible identification results of multiship encounter. The proposed framework is composed of AIS data processing and encounter ship detection by DBSCAN and adaptive visual analytics model for clusters of encounter ships under different specifications, which could make full use of the excellent performance of information processing by computer and adaptive visualization and perception from operators by adjusting the encounter radius and minimum number of ships in an adaptive way. The framework developed had been evaluated through a case study within the confined waters (Southwest Zhoushan, China). The results suggested that the proposed framework can cluster the whole ships into different clusters of encounter ships and give a visual identification of encounter ships.This paper is organized as follows. Section2 presents the necessary backgrounds and related research work regarding AIS data processing and application, ship encounter and adaptive visual analytics, and its performance and superiority in the maritime domain. Section 3 states the process of detecting ship encounter and visual analytics framework for encounter ships. The practical experimental case study using AIS data set from Zhoushan of China is described in Section 4. The results are discussed in Section 5, and finally, conclusions and future work are given in Section 6.


## 2. Related Work

### 2.1. Ship Encounter Identification

Aiming at improving the efficiency of maritime traffic surveillance, many studies and techniques are carried out to support intelligent vessel traffic service systems using computer-aided methods. The research of ship encounter or near-miss situation has been conducted in many kinds of literature studies [14, 15]. Taking into account the type of research objectives and methods, the studies published can be categorized into two groups broadly:(1)
Ship encounter detection(2)
Ship near-miss situationFor the lack of sufficient maritime accident data, the ship encounter is one of the most common criteria to identify and assess the maritime traffic safety level in the specific sea area [16]. The ship encounter is defined as a situation between ships where two or above sailing ships are close enough at a certain distance.As shown in Figure1, there are 6 ships sailing within in certain sea area. If the encounter radius is R, the ship A and ship B will be detected as a couple of encounter ships. However, the distance of the ship encounter varies by the situation between the ships, manipulating ability of the ship, state of the sea area, metrological conditions, officer’s navigational experience, and so on [17]. Iperen defined the encounter as the tracks of two ships which are expected to pass each other within 3 nautical miles within 20 minutes, based on their speed and course [15]. Zhang et al. [18] set the encounter radius as 1500 m (0.8 nautical miles) for the multiship encounter and collision avoidance support. Moreover, the ship encounter radius is defined as 700 m when the ship sailed within the sea area of the bay in [19]. Ship encounters were assessed by the way of the predicted point of collision in [20]. Zhen et al. [21] proposed a framework of real-time multivessel collision assessment based on DBSCAN, but the ship encounter radius and number of ships are fixed in the framework. Actually, the encounter radius is different for the whole waters. The detection of near-miss situations is proposed by considering the ship domain, course difference, and relative speed and using neuro-fuzzy classification in [17]. Chen et al. [22] proposed an ensemble framework via the ensemble empirical mode decomposition (EEMD) and artificial neural network (ANN) to predict the traffic flow under different time intervals ahead. Liu [23] conducted a topological analysis model of the ship encounter space using a geographic information system (GIS) spatial analysis technology. By combining the requirements for the light range in COLREGS and support vector classification to supervise and learn the actual meeting data, a map of the ship encounter azimuth division was constructed in [24]. An analytical model incorporating a Bayesian network is proposed to estimate the occurrence likelihood of a ship being grounded and collided in the fluctuating backwater zone in [25]. Ma et al. [26] proposed a deep learning model for predicting the sailing intent in the intersection waterway because ship-ship collisions in such areas mainly occur by incorrectly interpreting the intents of other vessels.Figure 1
Diagram of the ship encounter.On concluding the existing literature on ship encounter detection, we know that there is no specific distance defined for ship encounter, but it is closer when the ship sails in confined waters, while further in open or coastal waters suggested by navigational experience.A near miss is an unplanned event that has the potential to cause but does not actually result in human injury, environmental or equipment damage, or an interruption to normal operations, or a near miss is an unintentional incident that could have caused damage, injury, or death but was narrowly avoided [27]. The term “near miss” is a special event to be modelled and detected that can be applied to assess and identify safety operations in many industries and organizations, such as law enforcement and public safety, fire-rescue services, healthcare, aviation, railway, and maritime transportation [28]. Compared to other domains, the application of near-miss situation detection in maritime transportation research is a relatively new research topic, with a pioneering work by Berglund and Huttunen [29]. In the maritime transportation application, a near-miss situation between ships can be treated as a subset situation of ship encounter where the encounter ships would be in a more urgent unsafe situation. The near-miss situation is defined by the overlap of the ship domain by Fujii and Tanaka [30], and in a work by Kim and Jeong [31], as it shown in Figure 2, if one ship’s domain has been invaded by another’s, a near miss could be formed. A fuzzy logic method is proposed to add vessel collision avoidance capability to VTS in [32]. Zhang et al. [33] proposed a method to detect possible near-miss ship-ship collisions from AIS data.Figure 2
Concepts of the near-miss event using an elliptical domain.Generally speaking, ship encounter and near-miss situation are nonaccidental traffic situations that should be identified for further investigation to take proactive and evasive actions and reduce the risk from the maritime surveillance.


### 2.2. Adaptive Visual Analytics for Maritime Surveillance

The maritime surveillance system always integrates a huge amount of data; exploring and analyzing the vast volumes of data is becoming increasingly difficult. However, information visualization, visual data mining, and visual analysis can help to deal with the flood of information. Visual analysis is a set of techniques for combining the computational power of computers with the perceptive and cognitive capabilities of humans, in order to extract knowledge from large and complex datasets. The techniques rely heavily on user interaction and the human visual system and exist in the intersection between visual analytics and big data [34]. The visual analytics has been applied well to the maritime domain. An adaptive, visual knowledge discovery tool for supporting the detection and identification of anomalous behavior in maritime traffic data (VISAD) is proposed by Riveiro [35], which are a series of pioneering research studies integrating the preparation of the system, establishment of the normal picture, and the actual detection of maritime anomaly events. Chen et al. identify and visualize the cumulative activity patterns for ship groups derived from mass ship trajectories contained in AIS data and provide a clearer interpretation of shifting space-use patterns within strait corridors [36]. A normal model of vessel behavior is quantified and visualized by the Gaussian mixture model (GMM), and the model is applied in the maritime anomaly detection application in [37]. The maritime traffic route and density map is visualized by using AIS data along the Atlantic coast of the US for offshore wind energy areas planning by Breithaupt et al. [38]. Jin et al. [39] explored the characteristics of vessel behavior by means of integrating data mining with visual analytics, a human-computer interaction controlling model, which combines human insight with enormous storage and processing capacities of computers to gain insight into vessel behavior. The studies above are mostly about visualization of ship behavior expressed by AIS data; the process is not interactive and adaptive, so the visual analytics should be introduced in the following research.The existing studies about ship encounter detection mainly focus on models of the encounter between two ships, and the ship encounter radius and minimum number of ships are fixed. The previous work cannot meet the requirements of multiship encounter detection when there are a large number of ships sailing in confined waters. Visual analytics and its application in maritime have carried out research mainly on maritime anomaly detection and visualization of the density map. This paper proposes an adaptive visual analytics framework that incorporates multiship encounter detection by DBSCAN and clusters of encounter ships visualized and displayed adaptively on the nautical chart under the flexible parameter combination of encounter radius, minimal number of encounter ships, and diameter of cluster given by the operator in the surveillance center. The newly proposed framework can make full use of machine learning and visual analytics, which can contribute to the intelligent maritime surveillance system.


## 2.1. Ship Encounter Identification

Aiming at improving the efficiency of maritime traffic surveillance, many studies and techniques are carried out to support intelligent vessel traffic service systems using computer-aided methods. The research of ship encounter or near-miss situation has been conducted in many kinds of literature studies [14, 15]. Taking into account the type of research objectives and methods, the studies published can be categorized into two groups broadly:(1)
Ship encounter detection(2)
Ship near-miss situationFor the lack of sufficient maritime accident data, the ship encounter is one of the most common criteria to identify and assess the maritime traffic safety level in the specific sea area [16]. The ship encounter is defined as a situation between ships where two or above sailing ships are close enough at a certain distance.As shown in Figure1, there are 6 ships sailing within in certain sea area. If the encounter radius is R, the ship A and ship B will be detected as a couple of encounter ships. However, the distance of the ship encounter varies by the situation between the ships, manipulating ability of the ship, state of the sea area, metrological conditions, officer’s navigational experience, and so on [17]. Iperen defined the encounter as the tracks of two ships which are expected to pass each other within 3 nautical miles within 20 minutes, based on their speed and course [15]. Zhang et al. [18] set the encounter radius as 1500 m (0.8 nautical miles) for the multiship encounter and collision avoidance support. Moreover, the ship encounter radius is defined as 700 m when the ship sailed within the sea area of the bay in [19]. Ship encounters were assessed by the way of the predicted point of collision in [20]. Zhen et al. [21] proposed a framework of real-time multivessel collision assessment based on DBSCAN, but the ship encounter radius and number of ships are fixed in the framework. Actually, the encounter radius is different for the whole waters. The detection of near-miss situations is proposed by considering the ship domain, course difference, and relative speed and using neuro-fuzzy classification in [17]. Chen et al. [22] proposed an ensemble framework via the ensemble empirical mode decomposition (EEMD) and artificial neural network (ANN) to predict the traffic flow under different time intervals ahead. Liu [23] conducted a topological analysis model of the ship encounter space using a geographic information system (GIS) spatial analysis technology. By combining the requirements for the light range in COLREGS and support vector classification to supervise and learn the actual meeting data, a map of the ship encounter azimuth division was constructed in [24]. An analytical model incorporating a Bayesian network is proposed to estimate the occurrence likelihood of a ship being grounded and collided in the fluctuating backwater zone in [25]. Ma et al. [26] proposed a deep learning model for predicting the sailing intent in the intersection waterway because ship-ship collisions in such areas mainly occur by incorrectly interpreting the intents of other vessels.Figure 1
Diagram of the ship encounter.On concluding the existing literature on ship encounter detection, we know that there is no specific distance defined for ship encounter, but it is closer when the ship sails in confined waters, while further in open or coastal waters suggested by navigational experience.A near miss is an unplanned event that has the potential to cause but does not actually result in human injury, environmental or equipment damage, or an interruption to normal operations, or a near miss is an unintentional incident that could have caused damage, injury, or death but was narrowly avoided [27]. The term “near miss” is a special event to be modelled and detected that can be applied to assess and identify safety operations in many industries and organizations, such as law enforcement and public safety, fire-rescue services, healthcare, aviation, railway, and maritime transportation [28]. Compared to other domains, the application of near-miss situation detection in maritime transportation research is a relatively new research topic, with a pioneering work by Berglund and Huttunen [29]. In the maritime transportation application, a near-miss situation between ships can be treated as a subset situation of ship encounter where the encounter ships would be in a more urgent unsafe situation. The near-miss situation is defined by the overlap of the ship domain by Fujii and Tanaka [30], and in a work by Kim and Jeong [31], as it shown in Figure 2, if one ship’s domain has been invaded by another’s, a near miss could be formed. A fuzzy logic method is proposed to add vessel collision avoidance capability to VTS in [32]. Zhang et al. [33] proposed a method to detect possible near-miss ship-ship collisions from AIS data.Figure 2
Concepts of the near-miss event using an elliptical domain.Generally speaking, ship encounter and near-miss situation are nonaccidental traffic situations that should be identified for further investigation to take proactive and evasive actions and reduce the risk from the maritime surveillance.


## 2.2. Adaptive Visual Analytics for Maritime Surveillance

The maritime surveillance system always integrates a huge amount of data; exploring and analyzing the vast volumes of data is becoming increasingly difficult. However, information visualization, visual data mining, and visual analysis can help to deal with the flood of information. Visual analysis is a set of techniques for combining the computational power of computers with the perceptive and cognitive capabilities of humans, in order to extract knowledge from large and complex datasets. The techniques rely heavily on user interaction and the human visual system and exist in the intersection between visual analytics and big data [34]. The visual analytics has been applied well to the maritime domain. An adaptive, visual knowledge discovery tool for supporting the detection and identification of anomalous behavior in maritime traffic data (VISAD) is proposed by Riveiro [35], which are a series of pioneering research studies integrating the preparation of the system, establishment of the normal picture, and the actual detection of maritime anomaly events. Chen et al. identify and visualize the cumulative activity patterns for ship groups derived from mass ship trajectories contained in AIS data and provide a clearer interpretation of shifting space-use patterns within strait corridors [36]. A normal model of vessel behavior is quantified and visualized by the Gaussian mixture model (GMM), and the model is applied in the maritime anomaly detection application in [37]. The maritime traffic route and density map is visualized by using AIS data along the Atlantic coast of the US for offshore wind energy areas planning by Breithaupt et al. [38]. Jin et al. [39] explored the characteristics of vessel behavior by means of integrating data mining with visual analytics, a human-computer interaction controlling model, which combines human insight with enormous storage and processing capacities of computers to gain insight into vessel behavior. The studies above are mostly about visualization of ship behavior expressed by AIS data; the process is not interactive and adaptive, so the visual analytics should be introduced in the following research.The existing studies about ship encounter detection mainly focus on models of the encounter between two ships, and the ship encounter radius and minimum number of ships are fixed. The previous work cannot meet the requirements of multiship encounter detection when there are a large number of ships sailing in confined waters. Visual analytics and its application in maritime have carried out research mainly on maritime anomaly detection and visualization of the density map. This paper proposes an adaptive visual analytics framework that incorporates multiship encounter detection by DBSCAN and clusters of encounter ships visualized and displayed adaptively on the nautical chart under the flexible parameter combination of encounter radius, minimal number of encounter ships, and diameter of cluster given by the operator in the surveillance center. The newly proposed framework can make full use of machine learning and visual analytics, which can contribute to the intelligent maritime surveillance system.


## 3. Adaptive Visual Analytics Model for Multiship Encounter

### 3.1. DBSCAN for Multiship Encounter

The DBSCAN requires two parameters:ε (eps) and the minimum number of points required to form a dense region (minPts). It starts with an arbitrary starting point that has not been visited. This point’s ε-neighbourhood is retrieved, and if it contains sufficiently many points, a cluster is started. Otherwise, the point is treated as noise. Note that this point might later be found in a sufficiently sized ε-environment of a different point and hence be made part of a cluster. If a point is found to be a dense part of a cluster, its ε-neighbourhood is also part of that cluster. Hence, all points that are found within the ε-neighbourhood are added, as is their own ε-neighbourhood when they are also dense. This process continues until the density-connected cluster is completely found. Then, a new unvisited point is retrieved and processed, leading to the discovery of a further cluster or noise. The DBSCAN can be used with any distance function (as well as similarity functions or other predicates). The algorithm of DBSCAN (Algorithm 1) can be expressed in pseudocode as follows [40].Algorithm 1: DBSCAN (DB, distFunc, eps, minPts).
{C: = 0for each pointP in database DB {if label (P) ≠ undefined then continueNeighborsN: = RangeQuery (DB, distFunc, P, eps)if |N| < minPts then {label (P): = Noisecontinue}C: = C + 1label (P): = CSeedSetS: = N \ {P}for each pointQ in S {if label (Q) = Noise then label (Q): = Cif label (Q) ≠ undefined then continuelabel (Q): = CNeighborsN: = RangeQuery (DB, distFunc, Q, eps)if |N| ≥ minPts then {S: = S ∪ N}RangeQuery can be implemented using a database index for better performance, or using a slow linear scan (Algorithm2) [40].Algorithm 2: RangeQuery (DB, distFunc, Q, eps).
{NeighborsN: = empty listfor each pointP in database DB {if distFunc (Q, P) ≤ epsthen {N: = N ∪ {P}}}returnN}As the ship encounter is defined as a situation between ships where two or more sailing ships are close enough at certain distance in Figure1, so the detection of encounter ships can be taken as a spatial clustering process for ships’ position data shown in Figure 3.Figure 3
Multiship encounter detection based on DBSCAN.As shown in Figure3, the encounter ships are concentrated in the dense spatial sea area where the nonencounter ships do not have any ship around them within the encounter radius. Hence, the algorithm of DBSCAN in data mining is a quite suitable method to cluster ships’ position data from the semantical meaning of ship encounter, and the result of DBSCAN is the different clusters of the encounter ships and the noise data of clustering result is nonencounter ships.There are quite important criteria in the clustering process in the distance calculation between ships. In the nautical domain, the distance between the ships is calculated from the AIS data using the Mercator method which is more accurate and suitable than the Euclidean distance. The unit of distance is a nautical mile. Assume that there are two vessels:Vo (Longo, Lato, Sogo, Cogo) and Vt (Longt, Latt, Sogt, Cogt). The distance and bearing calculated from Vo to Vt are computed using the following equations:(1)Dif_Long=Longt−Longo,(2)Dif_Lat=Latt−Lato,(3)MP=7915.70447logtanπ4+Lat21−esinLat1+esinLate/2,(4)DMP=MPt−MPo,(5)bearing=arctanDif_LongDMP,(6)distance=Dif_Latcosbearing,where Dif_Long and Dif_Lat are the differences of longitude and latitude and MP is the meridional parts at the specific latitude calculated by equation (3). DMP is the differences of MP of Vo and Vt in equation (4); then the bearing and distance are calculated using equations (5)∼(6).Before the process of multiship encounter detection using DBSCAN, two parameters should be specified, and the principle of parameter specification is discussed as follows.


#### 3.1.1. Encounter Radius

It is always affected by the type of waters and weather condition (larger value when it is a relatively open waters under poor visibility, otherwise smaller value within confined water under good visibility, vice versa).


#### 3.1.2. Minimum Number of Ships Involving Multiship Encounter

Aiming at the detection of multiship encounter, the number of ships involving the multiship encounter should be above two or more. The encounter radius corresponds to the parameter eps and the number of ships involving multiship encounter corresponds to the parameter minPts in the DBSCAN algorithm. The two parameters for the multiship encounter detection discussed above can be specified in an adaptive way based on the operator’s cognitive perception and the computation process in the following framework.


### 3.2. Adaptive Visualization of Encounter Ships Using Visual Analytics

After each spatial clustering for ships, there would be several clusters of encounter ships generated. In order to distinguish the different clusters clearly, we introduce a circle with the center of each cluster and certain diameter to cover the clusters of encounter ships, which could benefit the focus on each cluster of encounter ships. Consider that the results of clustering are determined by the specification of minPts and eps before the implementation of DBSCAN, and assume thatm clusters will be generated and there are n ships in the mth cluster. Hence, the center position of the mth cluster can be calculated as follows:(7)LonCm,n=1n∑1nLonmi,(8)LatCm,n=1n∑1nLatmi.The diameter can be set after the results of the multiship encounter detection by DBSCAN. The diameter value should be specified according to the size of encountering ship clusters, so as to ensure that the clusters can be covered by circle clearly and assist the operators to distinguish the clusters of encounter ships.


### 3.3. Visual Analytics Process for Multiship Encounter Identification

Visual analysis (VA) is a set of techniques for combining the computational power of computers with the perceptive and cognitive capabilities of humans, in order to extract knowledge from large and complex datasets. An abstract and general overview of the diﬀerent stages and their transitions in the visual analytics process is shown in Figure3, which is adapted from the study of Keim et al. [41]. The first step is often to preprocess and transform the data and derive different representations for further exploration. Other typical preprocess tasks include data cleaning, normalization, grouping, or integration of heterogeneous data sources. After the transformation, the analyst may choose between applying visual or automatic analysis methods. If an automated analysis is used first, data mining methods are applied to generate models of the original data. Once a model is created, the analyst has to evaluate and refine the model, which can best be done by interacting with the data. Visualizations allow the analysts to interact with automatic methods by modifying parameters or selecting other analysis algorithms. Model visualization can then be used to evaluate the findings of the generated models. Alternating between visual and automatic methods is characteristic for the visual analytics process and leads to continuous refinement and verification of preliminary results. By using the visual analytics visual findings process, knowledge can be gained from visualization, automatic analysis, as well as the preceding interactions between visualizations, models, and the human analysts [42], and the overview of visual analytics is shown in Figure 4.Figure 4
Overview of visual analytics.According to the general process of visual analytics discussed above and the algorithm of multiship encounter detection designed based on DBSCAN, we design the following framework of adaptive visual analytics model for the multiship encounter identification, as shown in Figure5.Figure 5
Visual analytics process for the multiship encounter identification.The modules of adaptive visual analytics framework of multiship encounter detection are designed and shown in Figure6, considering the requirement of multiship encounter detection. There are four main modules designed to fulfil the functions in the visual analytics framework.Figure 6
Module design of adaptive visual analytics framework for the multiship encounter detection.


#### 3.3.1. Specification of Parameters for the Multiship Encounter

The parameters include the encounter radius (ER), the minimum number of encounter ships (MS) specified before the clustering process, and the diameter of a circle that covers clusters of encountering ships after the clustering process and before the identification of encountering ships’ distribution. All the specified parameters would be assigned to the DBSCAN algorithm, and clusters of encounter ships would be plotted on the nautical chart adaptively.


#### 3.3.2. Clustering Action for Encounter Detection

After the two parameters specified, the clustering process can be performed on ships’ position contained by AIS data, and the outputs are identifiers of ships: identifiers of encounter ships or nonencounter ships.


#### 3.3.3. Visual Display of Encounter Ships

The live AIS data can be loaded, updated, and displayed on maps. Then the clusters of encounter ships and nearest distance of ships between each encounter cluster can be visually displayed in this module. At the same time, the visual results should be assessed and the cognitive feedback of clustering detection of multiship encounter should be given to respecify the parameters of clustering process and identification of encounter ships and gain better performance between computation in computer and perceptive and cognitive capabilities of humans.


#### 3.3.4. Multiship Encounter Monitor

This module displays the number of encounter ship clusters, encounter ships’ percentage of the whole ships, and MMSI list of encounter ships. The adaptive framework of multiship encounter detection is shown in Figure5; here, we develop the components in a graphical user interface (GUI) to form a user-friendly and practical framework to validate its effectiveness.


## 3.1. DBSCAN for Multiship Encounter

The DBSCAN requires two parameters:ε (eps) and the minimum number of points required to form a dense region (minPts). It starts with an arbitrary starting point that has not been visited. This point’s ε-neighbourhood is retrieved, and if it contains sufficiently many points, a cluster is started. Otherwise, the point is treated as noise. Note that this point might later be found in a sufficiently sized ε-environment of a different point and hence be made part of a cluster. If a point is found to be a dense part of a cluster, its ε-neighbourhood is also part of that cluster. Hence, all points that are found within the ε-neighbourhood are added, as is their own ε-neighbourhood when they are also dense. This process continues until the density-connected cluster is completely found. Then, a new unvisited point is retrieved and processed, leading to the discovery of a further cluster or noise. The DBSCAN can be used with any distance function (as well as similarity functions or other predicates). The algorithm of DBSCAN (Algorithm 1) can be expressed in pseudocode as follows [40].Algorithm 1: DBSCAN (DB, distFunc, eps, minPts).
{C: = 0for each pointP in database DB {if label (P) ≠ undefined then continueNeighborsN: = RangeQuery (DB, distFunc, P, eps)if |N| < minPts then {label (P): = Noisecontinue}C: = C + 1label (P): = CSeedSetS: = N \ {P}for each pointQ in S {if label (Q) = Noise then label (Q): = Cif label (Q) ≠ undefined then continuelabel (Q): = CNeighborsN: = RangeQuery (DB, distFunc, Q, eps)if |N| ≥ minPts then {S: = S ∪ N}RangeQuery can be implemented using a database index for better performance, or using a slow linear scan (Algorithm2) [40].Algorithm 2: RangeQuery (DB, distFunc, Q, eps).
{NeighborsN: = empty listfor each pointP in database DB {if distFunc (Q, P) ≤ epsthen {N: = N ∪ {P}}}returnN}As the ship encounter is defined as a situation between ships where two or more sailing ships are close enough at certain distance in Figure1, so the detection of encounter ships can be taken as a spatial clustering process for ships’ position data shown in Figure 3.Figure 3
Multiship encounter detection based on DBSCAN.As shown in Figure3, the encounter ships are concentrated in the dense spatial sea area where the nonencounter ships do not have any ship around them within the encounter radius. Hence, the algorithm of DBSCAN in data mining is a quite suitable method to cluster ships’ position data from the semantical meaning of ship encounter, and the result of DBSCAN is the different clusters of the encounter ships and the noise data of clustering result is nonencounter ships.There are quite important criteria in the clustering process in the distance calculation between ships. In the nautical domain, the distance between the ships is calculated from the AIS data using the Mercator method which is more accurate and suitable than the Euclidean distance. The unit of distance is a nautical mile. Assume that there are two vessels:Vo (Longo, Lato, Sogo, Cogo) and Vt (Longt, Latt, Sogt, Cogt). The distance and bearing calculated from Vo to Vt are computed using the following equations:(1)Dif_Long=Longt−Longo,(2)Dif_Lat=Latt−Lato,(3)MP=7915.70447logtanπ4+Lat21−esinLat1+esinLate/2,(4)DMP=MPt−MPo,(5)bearing=arctanDif_LongDMP,(6)distance=Dif_Latcosbearing,where Dif_Long and Dif_Lat are the differences of longitude and latitude and MP is the meridional parts at the specific latitude calculated by equation (3). DMP is the differences of MP of Vo and Vt in equation (4); then the bearing and distance are calculated using equations (5)∼(6).Before the process of multiship encounter detection using DBSCAN, two parameters should be specified, and the principle of parameter specification is discussed as follows.


### 3.1.1. Encounter Radius

It is always affected by the type of waters and weather condition (larger value when it is a relatively open waters under poor visibility, otherwise smaller value within confined water under good visibility, vice versa).


### 3.1.2. Minimum Number of Ships Involving Multiship Encounter

Aiming at the detection of multiship encounter, the number of ships involving the multiship encounter should be above two or more. The encounter radius corresponds to the parameter eps and the number of ships involving multiship encounter corresponds to the parameter minPts in the DBSCAN algorithm. The two parameters for the multiship encounter detection discussed above can be specified in an adaptive way based on the operator’s cognitive perception and the computation process in the following framework.


## 3.1.1. Encounter Radius

It is always affected by the type of waters and weather condition (larger value when it is a relatively open waters under poor visibility, otherwise smaller value within confined water under good visibility, vice versa).


## 3.1.2. Minimum Number of Ships Involving Multiship Encounter

Aiming at the detection of multiship encounter, the number of ships involving the multiship encounter should be above two or more. The encounter radius corresponds to the parameter eps and the number of ships involving multiship encounter corresponds to the parameter minPts in the DBSCAN algorithm. The two parameters for the multiship encounter detection discussed above can be specified in an adaptive way based on the operator’s cognitive perception and the computation process in the following framework.


## 3.2. Adaptive Visualization of Encounter Ships Using Visual Analytics

After each spatial clustering for ships, there would be several clusters of encounter ships generated. In order to distinguish the different clusters clearly, we introduce a circle with the center of each cluster and certain diameter to cover the clusters of encounter ships, which could benefit the focus on each cluster of encounter ships. Consider that the results of clustering are determined by the specification of minPts and eps before the implementation of DBSCAN, and assume thatm clusters will be generated and there are n ships in the mth cluster. Hence, the center position of the mth cluster can be calculated as follows:(7)LonCm,n=1n∑1nLonmi,(8)LatCm,n=1n∑1nLatmi.The diameter can be set after the results of the multiship encounter detection by DBSCAN. The diameter value should be specified according to the size of encountering ship clusters, so as to ensure that the clusters can be covered by circle clearly and assist the operators to distinguish the clusters of encounter ships.


## 3.3. Visual Analytics Process for Multiship Encounter Identification

Visual analysis (VA) is a set of techniques for combining the computational power of computers with the perceptive and cognitive capabilities of humans, in order to extract knowledge from large and complex datasets. An abstract and general overview of the diﬀerent stages and their transitions in the visual analytics process is shown in Figure3, which is adapted from the study of Keim et al. [41]. The first step is often to preprocess and transform the data and derive different representations for further exploration. Other typical preprocess tasks include data cleaning, normalization, grouping, or integration of heterogeneous data sources. After the transformation, the analyst may choose between applying visual or automatic analysis methods. If an automated analysis is used first, data mining methods are applied to generate models of the original data. Once a model is created, the analyst has to evaluate and refine the model, which can best be done by interacting with the data. Visualizations allow the analysts to interact with automatic methods by modifying parameters or selecting other analysis algorithms. Model visualization can then be used to evaluate the findings of the generated models. Alternating between visual and automatic methods is characteristic for the visual analytics process and leads to continuous refinement and verification of preliminary results. By using the visual analytics visual findings process, knowledge can be gained from visualization, automatic analysis, as well as the preceding interactions between visualizations, models, and the human analysts [42], and the overview of visual analytics is shown in Figure 4.Figure 4
Overview of visual analytics.According to the general process of visual analytics discussed above and the algorithm of multiship encounter detection designed based on DBSCAN, we design the following framework of adaptive visual analytics model for the multiship encounter identification, as shown in Figure5.Figure 5
Visual analytics process for the multiship encounter identification.The modules of adaptive visual analytics framework of multiship encounter detection are designed and shown in Figure6, considering the requirement of multiship encounter detection. There are four main modules designed to fulfil the functions in the visual analytics framework.Figure 6
Module design of adaptive visual analytics framework for the multiship encounter detection.


### 3.3.1. Specification of Parameters for the Multiship Encounter

The parameters include the encounter radius (ER), the minimum number of encounter ships (MS) specified before the clustering process, and the diameter of a circle that covers clusters of encountering ships after the clustering process and before the identification of encountering ships’ distribution. All the specified parameters would be assigned to the DBSCAN algorithm, and clusters of encounter ships would be plotted on the nautical chart adaptively.


### 3.3.2. Clustering Action for Encounter Detection

After the two parameters specified, the clustering process can be performed on ships’ position contained by AIS data, and the outputs are identifiers of ships: identifiers of encounter ships or nonencounter ships.


### 3.3.3. Visual Display of Encounter Ships

The live AIS data can be loaded, updated, and displayed on maps. Then the clusters of encounter ships and nearest distance of ships between each encounter cluster can be visually displayed in this module. At the same time, the visual results should be assessed and the cognitive feedback of clustering detection of multiship encounter should be given to respecify the parameters of clustering process and identification of encounter ships and gain better performance between computation in computer and perceptive and cognitive capabilities of humans.


### 3.3.4. Multiship Encounter Monitor

This module displays the number of encounter ship clusters, encounter ships’ percentage of the whole ships, and MMSI list of encounter ships. The adaptive framework of multiship encounter detection is shown in Figure5; here, we develop the components in a graphical user interface (GUI) to form a user-friendly and practical framework to validate its effectiveness.


## 3.3.1. Specification of Parameters for the Multiship Encounter

The parameters include the encounter radius (ER), the minimum number of encounter ships (MS) specified before the clustering process, and the diameter of a circle that covers clusters of encountering ships after the clustering process and before the identification of encountering ships’ distribution. All the specified parameters would be assigned to the DBSCAN algorithm, and clusters of encounter ships would be plotted on the nautical chart adaptively.


## 3.3.2. Clustering Action for Encounter Detection

After the two parameters specified, the clustering process can be performed on ships’ position contained by AIS data, and the outputs are identifiers of ships: identifiers of encounter ships or nonencounter ships.


## 3.3.3. Visual Display of Encounter Ships

The live AIS data can be loaded, updated, and displayed on maps. Then the clusters of encounter ships and nearest distance of ships between each encounter cluster can be visually displayed in this module. At the same time, the visual results should be assessed and the cognitive feedback of clustering detection of multiship encounter should be given to respecify the parameters of clustering process and identification of encounter ships and gain better performance between computation in computer and perceptive and cognitive capabilities of humans.


## 3.3.4. Multiship Encounter Monitor

This module displays the number of encounter ship clusters, encounter ships’ percentage of the whole ships, and MMSI list of encounter ships. The adaptive framework of multiship encounter detection is shown in Figure5; here, we develop the components in a graphical user interface (GUI) to form a user-friendly and practical framework to validate its effectiveness.


## 4. Experimental Case Study

In order to evaluate the proposed adaptive visual analytics framework designed in Section3, we develop a visual analytics framework to validate its practical effectiveness in the identification and visualization of multiship encounter for maritime surveillance application. The framework loads ship AIS data within a relatively confined harbor waters (Southwest waters of Zhoushan Island, China), where there always be a high density of vessel traffic flow, and the live AIS data are displayed in first graph of the framework in Figure 7.Figure 7
Function design of adaptive visual analytics framework for multiship encounter detection.


### 4.1. Function Description for Visual Analytics Framework

To fulfil the functional requirement of adaptive visual analytics for multiship encounter detection, the framework is composed of four main modules shown specifically in Figure7.In order to ensure a better performance of multiship encounter in the high-dense sea area, the framework supports different levels of interactions between operators’ cognition and computation capability. The specific functions of each module are presented as follows.


#### 4.1.1. Encounter Parameter Set Module

Three parameters can be set in this module. The operators can specify the MS, whose value is more than 2, because the encounter must be formed by at least two ships in pairwise encounter, or multiship encounter compose of 3 or more ships. The encounter radius (ER) defines the distance between encounter ships. In order to get a good performance, the value of ER should be adjusted according to the navigational environment, and the ER should be set at a larger value when ships sail within open waters, whereas it should be set at a smaller value when ships sail within confined or complex waters. The third parameter is the radius that is applied to generate a circle to cover each cluster of encounter ships; the centers of circle are calculated by using equations (7) and (8).


#### 4.1.2. Calculation Action Module

This module includes actions for loading and displaying AIS data, clustering to generate clusters of encounter ships and nonencounter ships, identification of encounter ships covered by circle, respectively, and the density of each cluster expressed by the average distance between ships in each cluster and extraction of MMSI for encounter ships.


#### 4.1.3. Clustering Results Monitor Module

After the clustering process, the total number of encounters, the percentage of encounter ships, and MMSI list of encounter ships can be shown in this module.


#### 4.1.4. Geographical Display Module

The results of each action would be visually displayed on the map in this module. There are main four axes that are utilized to display live AIS data, clustering results, clusters of encounter ships, and visual display of the density of each encounter cluster.


### 4.2. Experiment Evaluation

We carry out several tests on the adaptive visual analytics framework to validate its practical application in multiship encounter detection. Here two representative cases are presented as follows.As shown in Figure7, when the MS is 3 and ER is 2 n mile, there are 5 clusters of encounter ships and 52% (29/56) of encounter ships out of whole sailing ships displayed in clustering results monitor module. And the clusters of encounter ships covered by a circle, the nearest couple of ships in each cluster, and the density of each cluster are displayed on the geographical display module interactively.As shown in Figure8, when the MS is 2 and ER is 1 n mile, there are 7 clusters of encounter ships and 32% (18/56) of encounter ships out of whole sailing ships displayed in clustering results monitor module. Other results are displayed in the geographical display module. The visual analytics provide a more interactive and adaptive way to detect the encounter ship, in which, the operators can adjust the parameters according to last detection results.Figure 8
Experimental test of adaptive visual analytics framework for multiship encounter detection.In addition to the cases described above, we have carried out several tests with the different specifications of the encounter radius and minPts, and the number of clusters is shown in Figure9 and Table 1. As we can see from Figure 9 and Table 1, with the increase of the radius and minPts, the number of clusters becomes smaller, so the parameters should be adjusted according to the navigational environment and characteristics.Figure 9
Number of clusters with the change of minPts and radius.Table 1
Specific parameters of ship encounter detection
Radius (n mile)MinPtsNumber of clusters127235344452561During the period of research, we made a survey from the captains and operators who work in the maritime surveillance of Maritime Safety Authority in Zhoushan, and they suggested that the encounter radius of 1n mile is a better choice in the present traffic situation and 7 clusters of encounter ships are appropriate to detect the potential navigational risk in the present situation. However, the encounter parameters should be adjusted according the distribution and change of ship traffic, and our work offer a flexible framework to adjust the parameters.The encounter radius and the minimum number of ships are two important parameters in the multiship encounter identification, the cases in the experiment are just for validating the effectiveness of proposed framework, and the operators should adjust the value in different situations and get a suitable performance. Through the experimental cases presented above, it is demonstrated that the adaptive visual analytics framework can identify the potential high risky clusters of encounter ships out of the whole sailing ships within the surveillance sea area, based on the adaptive visual specification of multiship encounter parameters. The proposed framework could provide a visual method to identify encounter ships with high potential collision risk, which decrease the cognitive working load and increase the working efficiency of operators in maritime surveillance.


## 4.1. Function Description for Visual Analytics Framework

To fulfil the functional requirement of adaptive visual analytics for multiship encounter detection, the framework is composed of four main modules shown specifically in Figure7.In order to ensure a better performance of multiship encounter in the high-dense sea area, the framework supports different levels of interactions between operators’ cognition and computation capability. The specific functions of each module are presented as follows.


### 4.1.1. Encounter Parameter Set Module

Three parameters can be set in this module. The operators can specify the MS, whose value is more than 2, because the encounter must be formed by at least two ships in pairwise encounter, or multiship encounter compose of 3 or more ships. The encounter radius (ER) defines the distance between encounter ships. In order to get a good performance, the value of ER should be adjusted according to the navigational environment, and the ER should be set at a larger value when ships sail within open waters, whereas it should be set at a smaller value when ships sail within confined or complex waters. The third parameter is the radius that is applied to generate a circle to cover each cluster of encounter ships; the centers of circle are calculated by using equations (7) and (8).


### 4.1.2. Calculation Action Module

This module includes actions for loading and displaying AIS data, clustering to generate clusters of encounter ships and nonencounter ships, identification of encounter ships covered by circle, respectively, and the density of each cluster expressed by the average distance between ships in each cluster and extraction of MMSI for encounter ships.


### 4.1.3. Clustering Results Monitor Module

After the clustering process, the total number of encounters, the percentage of encounter ships, and MMSI list of encounter ships can be shown in this module.


### 4.1.4. Geographical Display Module

The results of each action would be visually displayed on the map in this module. There are main four axes that are utilized to display live AIS data, clustering results, clusters of encounter ships, and visual display of the density of each encounter cluster.


## 4.1.1. Encounter Parameter Set Module

Three parameters can be set in this module. The operators can specify the MS, whose value is more than 2, because the encounter must be formed by at least two ships in pairwise encounter, or multiship encounter compose of 3 or more ships. The encounter radius (ER) defines the distance between encounter ships. In order to get a good performance, the value of ER should be adjusted according to the navigational environment, and the ER should be set at a larger value when ships sail within open waters, whereas it should be set at a smaller value when ships sail within confined or complex waters. The third parameter is the radius that is applied to generate a circle to cover each cluster of encounter ships; the centers of circle are calculated by using equations (7) and (8).


## 4.1.2. Calculation Action Module

This module includes actions for loading and displaying AIS data, clustering to generate clusters of encounter ships and nonencounter ships, identification of encounter ships covered by circle, respectively, and the density of each cluster expressed by the average distance between ships in each cluster and extraction of MMSI for encounter ships.


## 4.1.3. Clustering Results Monitor Module

After the clustering process, the total number of encounters, the percentage of encounter ships, and MMSI list of encounter ships can be shown in this module.


## 4.1.4. Geographical Display Module

The results of each action would be visually displayed on the map in this module. There are main four axes that are utilized to display live AIS data, clustering results, clusters of encounter ships, and visual display of the density of each encounter cluster.


## 4.2. Experiment Evaluation

We carry out several tests on the adaptive visual analytics framework to validate its practical application in multiship encounter detection. Here two representative cases are presented as follows.As shown in Figure7, when the MS is 3 and ER is 2 n mile, there are 5 clusters of encounter ships and 52% (29/56) of encounter ships out of whole sailing ships displayed in clustering results monitor module. And the clusters of encounter ships covered by a circle, the nearest couple of ships in each cluster, and the density of each cluster are displayed on the geographical display module interactively.As shown in Figure8, when the MS is 2 and ER is 1 n mile, there are 7 clusters of encounter ships and 32% (18/56) of encounter ships out of whole sailing ships displayed in clustering results monitor module. Other results are displayed in the geographical display module. The visual analytics provide a more interactive and adaptive way to detect the encounter ship, in which, the operators can adjust the parameters according to last detection results.Figure 8
Experimental test of adaptive visual analytics framework for multiship encounter detection.In addition to the cases described above, we have carried out several tests with the different specifications of the encounter radius and minPts, and the number of clusters is shown in Figure9 and Table 1. As we can see from Figure 9 and Table 1, with the increase of the radius and minPts, the number of clusters becomes smaller, so the parameters should be adjusted according to the navigational environment and characteristics.Figure 9
Number of clusters with the change of minPts and radius.Table 1
Specific parameters of ship encounter detection
Radius (n mile)MinPtsNumber of clusters127235344452561During the period of research, we made a survey from the captains and operators who work in the maritime surveillance of Maritime Safety Authority in Zhoushan, and they suggested that the encounter radius of 1n mile is a better choice in the present traffic situation and 7 clusters of encounter ships are appropriate to detect the potential navigational risk in the present situation. However, the encounter parameters should be adjusted according the distribution and change of ship traffic, and our work offer a flexible framework to adjust the parameters.The encounter radius and the minimum number of ships are two important parameters in the multiship encounter identification, the cases in the experiment are just for validating the effectiveness of proposed framework, and the operators should adjust the value in different situations and get a suitable performance. Through the experimental cases presented above, it is demonstrated that the adaptive visual analytics framework can identify the potential high risky clusters of encounter ships out of the whole sailing ships within the surveillance sea area, based on the adaptive visual specification of multiship encounter parameters. The proposed framework could provide a visual method to identify encounter ships with high potential collision risk, which decrease the cognitive working load and increase the working efficiency of operators in maritime surveillance.


## 5. Discussion

The specifications of the encounter radius and the minimum number of ships are very important to obtain a good performance of detecting clusters of encounter ships. In the real application of the maritime surveillance scenario within a different type of sea area, the operators can set and assess different specifications of the encounter radius and minimum number of ships in the encounter parameter set module according to some impact factors, such as the distribution of sailing ship, the type of surveillance sea area, weather condition, judgement, and experience from maritime experts, to gain a better performance of obtaining clusters encounter ships and filter out the safe ships.The DBSCAN clustering method is quite suitable to process the ship position data expressed by AIS, and the parameters of the multiship encounter are just appropriate for corresponding to the input of DBSCAN; other methods ofK-means or hierarchical clustering need the users to give the number of clusters, but we just care about the encounter ships that are in very close distance within the surveillance waters, and the DBSCAN is the most suitable method to detect encounter ships. Compared to the work [21], this paper provides a more flexible framework by combining DBSCAN and visual analytics, and the framework has a better performance by introducing visual analytics.Actually, the AIS data are discontinuous, the ships’ position and density are changing all the time, and therefore, the whole process of DBSCAN for clustering encounter ships should be implemented at a periodical time to get better performance in the real maritime surveillance application.


## 6. Conclusions

The maritime surveillance system always integrates a huge amount of data, so exploring and analyzing the vast volumes of data is becoming increasingly difficult; however, visual analysis can help to deal with the flood of maritime traffic information. We propose an adaptive visual analytics framework for multiship encounter identification-based DBSCAN and visual analytics. The incorporation of visual analytics and DBSCAN can contribute to adjust the encounter parameters for efficient detection of multiship encounters. The framework has been developed, and there are four main modules which are composed of the encounter parameter set module, clustering results monitor module, visual display of encounter ships, and geographical display module in the framework. The developed framework has been evaluated by experiments on AIS data within Southwest waters of Zhoushan Island, China. The results show that the proposed framework is effective and efficient to detect the clusters of encounter ships by a combination of the operator’s adaptive specification of the multiship encounter, spatial data clustering method, and visual display of distribution of ship encounter clusters. At the same time, we have conducted a comparative analysis about different specifications of ship encounter parameters and have showed the quantitative impact of parameter specification on the final results. The proposed framework provides a new method to identify encounter ships with high potential collision risk based on adaptive data visualization and clustering analysis. The proposed method has valuable contribution to maritime surveillance. We will carry out the multiship encounter identification based on visual analytics; the quantized collision risk for multiship will be considered in the future work.



---

*Source: 3063957-2021-07-13.xml*