35

1 INTRODUCTION

Since2003,Chinahasbeguntodeployedshore‐based

AIS stations, which gradually covers all key coastal

waters as well as the important ports along China

coastline.Now,theAISreportscollectedbytheseAIS

stationsarewidelyusedinmarinetrafficsupervising,

marine traffic statistics and marine accident

invest

igations, and so on, by maritime safety

authoritiesorportauthorities.

According to the performance standards of ship

borne Automatic Identification System, ship static

information is broadcast every 6 minutes or when

asked, and the minimum interval of broadcasting

dynamic information reports is 2 seconds and the

maximumis3minutes[1].Accordingtostatisticsin

Shanghai[2],dynamicinformat

ionofabout15%ships

isnotupdatedin3minutes,dynamicinformationof

about 10% ships is not updated in 5 minutes, and

dynamic information of about 5% ships is not

updated in 15 minutes. There are two reasons

contributedtothi

sdelay.Oneisthatthedeployment

ofbasestationsisnotsensible,andanotheristhatthe

crowdedmarine  trafficlikeinport of Shanghaimay

result in AIS information transmission blocking. In

consequence, it is necessary to develop a algorithm

forinterpolatingshipAISmotionvectorstoestimate

the lost ship AIS reports when replaying ma

rine

traffic accidents oranalysing themarine trafficwith

AISreportscollectedbyshorebasedAISstations.

In recent years, the research on smoothing and

recoveringthetrajectoryofmoving‐objectshasmade

abundant achievements. An Extended Kalman Filter

(EKF)wasproposedfortheesti

mationofvesselstates

and further used for the prediction of vessel

trajectories[3].AdatamodelofHCFMOST(History‐

Current‐FutureMovingObjectsSpatio‐Temporal)was

presented and the trajectories of moving objectives

An Algorithm for Interpolating Ship Motion Vectors

Q.Hu,F.Cai,C.Yang&C.Shi

erchantMarineCollege,ShanghaiMaritimeUniversity,Shanghai,China

ABSTRACT:InterpolationofshipmotionvectorsisabletobeusedforestimatingthelostshipAISdynamic

information, which is important for replaying marine accidents and for analysing marine traffic data. The

previous methods can only interpolate ship’s position, while not including shipʹs course and speed. In thi

s

paper,vectorfunctionisusedtoexpresstherelationshipbetweentheship’stimeandspacecoordinates,and

the tangent of the vector function and its change rate are able to express physical characteristics of ship’s

course,speedandacceleration.ThegivenAISdynamicinformat

ioncanbeappliedtocalculatetheparameters

ofshipʹsvectorfunctionandthentheinterpolationmodelforshipmotionvectorsisdevelopedtoestimatethe

lost ship dynamic information at any given moment. Experiment results show that the ship motion vector

functionisabletodepictthecharacteristicsofshipmotionsaccuratelyandthemodelcanesti

matenotonlythe

ship’spositionbutalsoship’scourseandspeedatanygivenmomentwithlimiteddifferences.

http://www.transnav.eu

the International Journal

on Marine Navigation

and Safety of Sea Transportation

Volume 8

Number 1

March 2014

DOI:10.12716/1001.08.01.04

36

werestimulatedbyusingcubicHermiteinterpolation

[4]. These methods, however, could not restore or

predictshipmotionatanygiventime.

Thecurve‐basedmodelwaspresentedtoprovide

much more accurate trajectory [5]. A generalized

trajectory interpolation model using parametric

trajectory representations was proposed in [6].

Smooth trajectory

 tracking interpolation on a  robot

simulatorandinterpolationofmobilerobottrajectory

tracking control were presented in [7] and [8].

Piecewise cubic spline interpolation was used for

restoringvesseltrackbasedonAISInformationin[9].

The 5th‐order Runge‐Kutta‐Nystrom method was

presented to interpolate ship positions for

on‐board

navigationsystems[10].Aspatiotemporaluncertainty

modelwasproposedforinterpolationofcontinuously

changingdataobjects[11‐12].Thesemethodsareable

tobeusedforsmoothingtrajectory,however,notfor

moving‐objects’velocityanddirection.

In order to depict the physical relationship

between the time and space parameters

 of a ship,

vectorfunctionisintroducedinthispaper,thenship

motion vector function is constructed and

interpolationmodelissetup.WithgivenAISreport

information, the parameters of ship motion vector

interpolationmodelcanbedetermined,andthenthe

modelcanbeusedtoestimateshipʹs

position,course

andspeedatanygiventime.

This paper is organized as follows: Section 2 presents

ship motion vector function. Section 3 introduces the

model for interpolating ship motion vectors and the

model’sparametersisoptimized.  Section4describes

themethodcalculateshipmovingaccelerationwhich

is not reported by AIS. Section 5 demonstrates an

experiment and related error  analysis. Finally,



conclusionsaregiveninsection6.

2 SHIPMOTIONVECTORFUNCTION

Shipsnavigateinatwo‐dimensionalEuclideanspace.

Let vector function r(t) be ship’s motion vector

function, then given time t

0, radial vector

r(t

0)={x(t0),y(t0)} can express ship’s position. Tangent

vectorr’(t

0)={x’(t0),y’(t0)}candenoteship’sspeedand

ship’scourse.Vectorr(t

0) andvectorr’(t0)candepict

ship’smotionstate,asshowninFig1.

)}('),('{)('

000

r tytxt 

)}(),({)( 000r tytxt 

))(),(()( tytxt rr 



Figure1.Vectorfunctionofshipmovements

3 MODELFORINTERPOLATINGSHIPMOTION

VECTORS

Given vector function which indicates ship’s

movement, interpolation model for ship motion

vectors is set up. Then the physical characteristics

betweenshipandship’sspeed,headingareanalysed.

3.1 Modelforinterpolatingmoving‐object’strajectory

In order to make sure that the model expresses



moving‐objects’ motion vectors as accurate as

possible,firstly,vectorfunctionmustsatisfythegiven

motion vectors of the moving‐object. Secondly, the

model for interpolating moving‐object’s motion

vectorsissetup.Themodelforinterpolatingmoving‐

objects’motionvectorsisdefinedasfollows.

Foranygivenadjacenttime

and

)(



 and

their interval

[, ]

,coordinate vector and high

order coordinate vector of

 and

are

() () ()

() { (), ()}

nnn

iii

txtytr



and

() () ()

() { (), ()}

nnn

jjj

txtytr

,

,...)2,1,0( n



respectively,andvectorfunctionofthemovingobject

at time t (

[, ]

ttt



) can be expressed by Equation

(1).

21 21

() { (), ()} { , }

txtyt at bt







r  (1)

where

,

)12,...,2,1,0( 



 should meet

Equation(2)and(3).

() ()

()

ttrr (2)

() ()

()

ttrr (3)

3.2 Parametersofthemodelforinterpolatingship’s

motionvectors

Inordertodevelopthe model forinterpolatingship

motion vectors, the parameters a

k, bk of the

interpolation model is to be determined in this

section.

According to Equation (1), the order of vector

functionatanytimetisdependedonthevalue ofk

whichisfurtherdependedonthevalueofn.ifn=1,

thenk = 3,andif

n=2,thenk=5.Assumingattimeti

and tj, ship dynamic information includes position,

courseCandspeedv.Whenn=1,theneachorderof

ship radial vector functions are expressed by

Equation(4),(5),(6)and(7).

{(), ()}

iii

tyt



r  (4)

{( ), ( )}

jjj

tyt



 (5)

' {cos( ) ,sin( ) }

ii ii

itttt

Cv Cv



 (6)

37

'{cos( ) ,sin( )}

jj jj

tt tt

Cv Cvr

(7)

Amongthem,r

iand rj show the radialvectorsof

shipattimet

iandtjrespectively,r’iandr’jshowthe

velocityvectorsofshipattimet

iandtjrespectively.

AccordingtoEquation(2),theparametervector a

k

canbeachievedbyEquation(8).

1000

0010

()'

33 21

221 1

()'

jii



















































 (8)

Similarly, if n = 2, suppose r

i’’and rj’’ showthe

acceleration vectors of ship at time t

i and tj

respectively,theparametervectorakcanbeachieved

byEquation(9)



012345

100000

0010 0 0

()'

00000.50

()'

10 10 6 4 1.5 0.5

15 15 8 7 1.5 1

()''

66 330.50.5

()''

aaaaaa





































(9)

the parameter vector b

k can also be achieved in the

similarway.

FromEquation(8)and(9),itisobviouslythatthe

valuesofthemodel’sparametersaredirectlyrelated

to the distance of the given two motion nodes. In

ordertoacquireidealparametersandaccuratemodel,

the condition as Equation (10) shows should be

satisfiedbeforeint

erpolating[13].



max ' , ' 3 ( ) ( )

ij i j

ttrr r r (10)

3.3 Connectionconditionsofthemodelforinterpolating

shipmotionvectors

Insection3.1and3.2,thispaperdevelopsthemodel

for interpolating ship motion vectors between two

given adjacent ship motion vectors. The trajectory

nearthejointoftwo segments whichare formed by

the given ship motion vectors and int

erpolated

motionvectors,however,isnotcertaintobesmooth.

Inorderto constructatrajectorysatisfying withC



[14] standard, two adjacent interpolated trajectories

should be connected in C

 at the connection point.

Therefore, it is necessary to discuss the connection

conditions of two adjacent interpolated trajectories.

SuBuqinghas presented itsnecessaryandsufficient

conditionsin[14].

Given two intervals

[,]



and

[, ]



,

interpolated trajectories of ship are

()t



and

()t

thesufficientandnecessaryconditionsformeetingC

2

standard at the connection point

is expressed by

Equation(11).

() ()

'( ) '( )

''( ) ''( ) '( )

jjj

t α t

t α t β t



















122

rrr

(11)

where

and

 are constants, and usually,

and

have two kinds of values. One case is

1α



and

0β



, which is suitable for equal time

interval motion vectors, otherwise interpolated

trajectory will be shaking. Another case

( ) () () ( )

jjjj

α tttt



 

1122

rrrr

 and

0β



,

which is suitable for parametric interpolation. The

latterkindofvaluesisusedinthispaper.

4 CALCULATIONOFSHIP’SACCELERATION

Todevelopamoreaccuratemodelforinterpolateship

motionvectors,itisnecessarytointroducehighorder

parameters, i.e. acceleration of ship motion, into the

modelasEquation(9)shows.However,AISdoesnot

reportship’saccelerationrightnow,soit’snecessary

todevelopamethodtoesti

mateitwithneighbouring

shipmotionvectors.

Obviously, the closer between the estimated

acceleration and actual acceleration, the more

accurate the interpolation model is. Greater time

difference between two adjacent motion nodes will

lead to greater error. Therefore, more time‐adjacent

motion nodes will be selected to calculate the

accelerationatagivennode.

For example, given three ship motion nodes at

me t

i‐1, ti, and ti+1 as shown in Fig. 2, difference of

timeΔt

i‐1=ti‐ti‐1,Δti=ti+1‐tianddifferenceofspeedΔ vi‐

1=vi‐vi‐1,Δvi=vi+1‐vi., if Δti>Δti‐1, then











and if

Δt

i<Δti‐1 ， then









, where ai denotes ship

movingaccelerationattime

ti.

11 111

(, , ,,)

ii iii

yCtv





(, , ,,)

ii i ii

yC tv



(, , ,,)

ji jj

yC tv



Figure2.Distributionofship’sadjacentnodes

38

5 EXPERIMENT

AIS dynamic reports are used to verify the

effectiveness of the model introduced in this paper.

For better demonstration, this paper uses the AIS

dynamic reports, totally 1400 reports or motion

vectors in this paper, of a ship with MMSI of

412049010from1426to2159localtimeonJanuary31,

2013,whenshenavigatednearthemouthofYa

ngzte

Riverwherethetrafficisverycrowdedandshipneed

change course or speed frequently. Fig 3 shows the

trajectory constructed with the given AIS dynamic

reports.

Theexperimentalstepsareasfollows.

1 Extracted Sampling nodes from ship’s AIS

dynamicinformat

ionastheinterpolationnodes,as

showninFig4.

2 Set up the model for interpolating ship’s motion

vectors with determined sampling points. The

stepstointerpolateshipmotionvectorsareshown

intable1.

Interpolated trajectory is shown in Fig 5 while

interpolated courses and speeds are shown in

Fig6.Inordertoanalyzethedifferencesbetween

the esti

mated motion vectors and the observed

motion vectors, the experiment estimates the

motionvectorsforthemomentscorrespondingto

eachobservedmotionvectors.

3 Calculating differences of ship’s position, speed

andcoursebetweentheestimatedmotion vectors

andthecorrespondingobservedvectorsasshown

inFig.8,10,12.

Table1.Stepsforinterpolatingshipmotionvectors

_______________________________________________

step actions 

_______________________________________________

1 Construct ship motion vector sequence in time ascending

order with ship AIS dynamic information records, and let

counter i= 0.

2 the ith (if any), (i+1)

, (i+2)

, and (i+3)

(if any) motion

vectors are selected.

3 The model for interpolation of vectors between the (i+1)

and (i+2)

motion vectors, is set up with given four motion

vectors.

4 Interpolate all ship motion vectors between the (i+1)

and

(i+2)

motion vectors with designated interval or strategy.

5 Update speed and acceleration of the (i+2)

motion vector,

let i=i+1, if i = n-2, then quit, otherwise back to step 2,

where n is the number of all given vectors.

_______________________________________________

Figure3.Motionnodesfromship’sAISdata

Figure4Samplingnodesfromship’sAISdata

Figure5.Observedtrajectoryandestimatedtrajectory

39



Figure6.Interpolatedvelocityvectors



Figure7. Average position differences under different

samplingratios

Figure8.Positiondifferencesofsamplingratio107/1400



Figure9. Average course differences under different

samplingratios

Figure10.Coursedifferencesofsamplingratio107/1400



Figure11. Average speed differences under different

samplingratios

40

Figure12.Speeddifferencesofsamplingratio107/1400

From the above charts, it’s obvious that this

algorithmisfeasibleandwithincreasingofsampling

nodes, the differences between interpolated motion

vectors and the observed motion vectors decreased

significantlyasshowninfigure7,9,11.

6 CONCLUSIONS

Inthispaper,vectorfunctionisintroducedtoexpress

shipmotionvectors,andbased

onit,the model and

the algorithm for interpolating ship motion vectors

aredevelopedtoestimate the lostshipAISdynamic

reports which often arise in crowded waters.

Experiment results show that the estimated ship

motion vectors are very close to the observed

position, course and speed if the given

observed

motion vectors satisfied the introduced condition.

Moreover, the more AIS dynamic reports are given,

theclosertheestimatedva lueandobservedvalueare.

Thealgorithmintroducedinthispapercanplaya

significantrolewhenreplayingthe marineaccidents

oranalysingthemarinetrafficrelatingtothewaters

whereAIS

reportlostoftenoccurs.

REFERENCES

[1]RecommendationITU‐RM.1371‐4, Technical

characteristics for an automatic identification system

using time‐divisionmultiple access in the VHF

maritimemobileband，2010.4

[2]ShanghaiMaritimeTrafficSafetyIndexReal‐timeStudy

Important Waters. Reports, Shanghai Maritime

University，2012，10，15.

[3]Perera L P，Oliveira P，Guedes Soares

 C. Maritime

TrafficMonitoringBasedonVesselDetection,Tracking,

State Estimation, and Trajectory Prediction. Intelligent

TransportationSystems,IEEETransactionson,2012(13):

1188‐1200.

[4]LU Yan‐sheng ， CHAZhi‐yong ， Pan Peng.An

improvequeedspatio‐temporaldatamodelformoving

objects.JournalofHuaZhongUniversityofScienceand

Technology:NaturalScience，2006(8):32‐35.

[5]YU B ， KIM S H ， BAILEY T ， etal .Curve‐Based

Representation of Moving Object Trajectories. IEEE

International Database Engineering and Applications

Symposium，2004：419‐425.

[6]YU B，KIM S H. Interpolating and Using Most Likely

TrajectoriesinMoving‐ObjectsDatabases.Databaseand



Expert Systems Applications. Springer Berlin

Heidelberg，2006：718~727.

[7]PACHECO RR，HOUNSELL M S，ROSSO R S U，et

al.SmoothTrajectoryTrackingInterpolationonARobot

Simulator.RoboticsSymposiumandIntelligentRobotic

Meeting (LARS)，2010 Latin American. IEEE，2010：

13~18.

[8]LIU Z， ZHAO J， ZHANG L， et

al. Realization of

Mobile Robot Trajectory Tracking Control Based on

Interpolation.IndustrialElectronics,2009.ISIE2009.IEEE

InternationalSymposiumon.IEEE， 2009： 648~651.

[9]Ling‐zhiS,Xin‐pingY,ZheM,etal.RestoringMethodof

Vessel Track Based on AIS Information. Distributed

ComputingandApplicationstoBusiness,Engineering&

Science

 (DCABES), 2012 11th International  Symposium

on.IEEE,2012:336‐340.

[10]MONTENBRUCK O, GILL E. State Interpolation for

On‐Board Navigation Systems. Aerospace Science and

Technology，2001(5)：209‐220.

[11]YU B.A Spatiotemporal  Uncertainty Model of Degree

1.5 for Continuously Changing Data Objects.

Proceedings of the 2006 ACM Symposium on

Applied

Computing.ACM，2006： 1150‐1155.

[12]YUB， KIMSH， ALKOBAISIS，etal.TheTornado

Model: Uncertainty Model for Continuously Changing

Data. Advances in Databases: Concepts, Systems and

Applications. Springer Berlin Heidelberg，2007：624‐

636.

[13]Pratt M J,FAUX I D.Computational Geometry for

designandmanufacture.

EllisHorwoodLtd,1979.

[14]SU Bu‐qing ， ZHOU Ding‐yuan. Computation

Geometry.Shanghai：ShanghaiScienceandTechnology

Press.1981.

