445
1 INTRODUCTION
Ashorelineisaboundarybetweenthelandandwater
surfaces [1]. It is characterised by instability and
functional diversity which vary depending on the
region[2].Thisboundaryisofparticularimportance
fromtheperspectiveofeconomicandenvironmental
policiesofthecoastalstates.Thisstemsfrom
thefact
thattheshorelineisrichinnaturalresources,whichis
why approx. 50% of theworld’s populationinhabits
theareas locatedwithin 100 km of the shoreline [1].
Therefore, it is essential to monitor the state of the
seashore,whichchangesrapidlyandisdeterminedby
numerous anthropogenic
and natural factors. These
include: biological activity, coastal flooding [3],
earthquakes [4], marine erosion, ocean acidification
[5],oceancurrents,riverregulation,sealevelrise[6],
seawater intrusion [7], temperature increase, tides,
transportation of the rock debris [8] or wave action.
Research into the impact of the above‐mentioned
factors on the
shoreline course is conducted in a
variety of waterbodies such as bays [9], river deltas
Shoreline Extraction Based on LiDAR Data Obtained
Using an USV
A.Halicki
1,2
,M.Specht
1,3
,A.Stateczny
4
,C.Specht
3
&O.Lewicka
3
1
MarineTechnologyLtd.,Gdynia,Poland
2
UniversityofPorto,Porto,Portugal
3
GdyniaMaritimeUniversity,Gdynia,Poland
4
GdańskUniversityofTechnology,Gdańsk,Poland
ABSTRACT: This articleexplores the use of Light Detection And Ranging (LiDAR) derived point clouds to
extracttheshorelineoftheLakeKłodno(Poland),basedontheirgeometryproperties.Thedatacollectionwas
performed using the Velodyne VLP‐16 laser scanner,
which was mounted on the HydroDron Unmanned
Surface Vehicle (USV). A modified version of the shoreline extraction method proposed by Xu et al. was
employed, comprising of the following steps: (1) classifying the point cloud using the Euclidean cluster
extraction with a tolerance parameter of 1 m and min. cluster size
of 10,000 points, (2) further filtration of
boundarypointsbyremovingthosewithheightabove1mfromthemeasuredelevationofwatersurface,(3)
manualdeterminationofacurveconsistingof5pointslocatedalongtheentireshorelineextractionregionata
relativelyconstantdistantfromthecoast,(4)
removalofpointsthatarefurtherfromthecurvethantheaverage
distance,repeatedtwice.ThemethodwastestedonthescannedsectionofthelakeshorelineforwhichGround
ControlPoints(GCP)weremeasuredusingaGlobalNavigationSatelliteSystem(GNSS)RealTimeKinematic
(RTK)receiver.Then,theresultswere
comparedtothegroundtruthdata,obtaininganaveragepositionerror
of2.12mwithastandarddeviationof1.11m.Themaxerrorwas5.54m,whilethemin.errorwas0.41m,all
calculated on 281 extracted shoreline points. Despite the limitations of this parametric, semi‐supervised
approach,
thosepreliminaryresultsdemonstratethepotentialforaccurateshorelineextractionbasedonLiDAR
data obtained using an USV. Further testing and optimisation of this method for larger scale and better
generalisation for different waterbodies are necessary to fully assess its effectiveness and feasibility. In this
context, it is essential to develop
computationally efficient methods for approximating shorelines that can
accuratelydeterminetheircoursebasedonasetofpoints.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 17
Number 2
June 2023
DOI:10.12716/1001.17.02.22
446
and estuaries [10,11], wetlands [12], as well as other
geographicformationssituatedalongthecoast[13,14].
Due to complex shoreline dynamics, different
indicators[e.g. High Water Line (HWL), MeanHigh
WaterLine(MHWL)]areusedtodefineanddescribe
shoreline [1]. Moreover, different authors often use
divergentdefinitionsforthe
sameshorelineindicators
[1].
Similarly,manydifferentmethodsfordetermining
the shoreline course are applied throughout the
literature.These include: geodeticsurveys[15,16], in
particular,thoseusingtheGlobalPositioningSystem
(GPS) and remote sensing measurements [17]
performed using unmanned and manned airborne
systems[18],aswellassatellites[19].
Inrecentyears,
LightDetectionAndRanging(LiDAR)hasbecomea
popular method for shoreline determination. LiDAR
measurementsaretypicallyperformedusingairborne
systems[13],andallowforalargeareatobecovered
inarelativelyshorttime[20,21].Themethodinvolves
emittingabeamoflightataspecific
wavelengthand
recordingthereturnsignal if thebeamencounters a
reflector(i.e.,alightreflectingobject).By measuring
the time, it takes for the beam to return and taking
intoaccountthedeviceʹsorientationinspaceandthe
angleatwhichthebeamwasemitted,itispossible
to
calculate the position of the reflector. LiDAR has
severaladvantagesoverothershorelinedetermination
methods, including its ability to capture detailed
topographic information, its high accuracy and
precision,aswellasitsabilitytoprovidedatainreal‐
time [22]. However, the use of LiDAR also has its
limitations,including
relativelyhighcost,theneedfor
extensivedatapre‐processing,aswellasdependence
onenvironmentalandweatherconditions,whichcan
makeLiDARlesspracticalforsomeapplications.
Farris et al. [22] compared three shoreline
extraction methods used by the United States
Geological Survey (USGS) as part of the Marine
Geology Program. The first of them is a modified
profile method as described by [21]. It uses a 20 m‐
wide window determined along the transverse
profiles.Thesecondoneisthegridmethodbasedon
theinterpolationofheightsontoagridofsquares.The
thirdoneisa contour
methodthatallowsacontourof
theMeanHighWater(MHW)leveltobeobtainedby
usingthecontourgenerationfunction in the ArcGIS
software.Aspartofthevalidationtests,avisualand
quantitative assessment of the shoreline extraction
accuracywasconductedbasedontheAirborneLaser
Scanning (ALS)
data recorded using the ATM‐II
system. The measurements were performed on Fire
Island (USA) by the National Oceanic and
AtmosphericAdministration(NOAA) and the USGS
intheyears2000and2012.Theauthorshadnodata
on the actual position of the shoreline, which
prevented the comparison of the errors
in the
determination of its course. For this reason, they
decided to compare the differences in the extraction
resultsbetweentheindividualmethods.Theauthors
quantitatively demonstrated that the shoreline
courses obtained using the contour, grid and profile
methods are very similar to each other, with shifts
betweenthemof
lessthan1m.
Fernández Luque et al. [23] developed the
Elevation Gradient Trend Propagation (EGTP)
method for shoreline extraction, which uses the
iterative method based on a grid of squares. The
EGTP method involves the use of the elevation
gradient trend (its size and direction) calculated for
eachgridcell
ofaknownelevationtowardscellsofan
unknownelevation.Thisprocessisrepeateduntilthe
newpointofthegridreachesalevelsimilarto(lower
than) the selected vertical reference system. In this
way,itiseasytodeterminetheshorelinecoursefrom
the extrapolated terrain model. As
part of the
validationtests,avisualandquantitativeassessment
of the shoreline extraction accuracy was conducted
based on the ALS data recorded using the Leica
Geosystems ALS60 system. The measurements were
performed along the Mediterranean coast in the
Almeria province (Spain) in 2009. The shoreline
extraction errors were referred to
62 control points
that were determined using a Differential Global
PositioningSystem(DGPS)receiver.Asdemonstrated
by statistical analyses,themean uncertaintyand the
medianuncertaintyfortheEGTPmethodwere2.08m
and 1.51 m, respectively. The study results obtained
usingthe elevationgradient trend propagationwere
compared with
the results obtained using the
referencemethodsasproposedby[21,22].TheEGTP
methodhasbeenproventohaveahigheraccuracyof
the shoreline course determination than that of the
referencemethods.
Hua et al. [24] developeda method for detecting
shoresofananthropogenicnature. At the beginning
of
thepaper,attentionwasdrawntothelargevolume
of data derived from LiDAR measurements.
Therefore, the authors proposed simple criteria to
limitthesizeoftheLiDARpointcloud,thusreducing
thecomputationalcomplexityatthelaterstagesofthe
anthropogenic method. External software was used
forthevisualisation
andanalysisoftheLiDARpoints.
This enabled the determination of the coordinate
range of the area under study, the coordinate range
within which the shoreline is found, the scanning
directionwhen using aircraft and the side on which
the shoreline was located on the scan. The program
also enabled the
performance of preliminary
segmentation(classification)oftheareaunderstudy.
Subsequently,thepointsthatmayhavebeenreflected
from the water surface were removed. Only then
couldtheshorelinecoursebedeterminedbasedonthe
informationon thedirectionof flight.As part ofthe
validation tests, a visual assessment
of the shoreline
extractionaccuracywasconductedbasedontheALS
data. The measurements were conducted in the
coastal zone of Longkou (China). The authors
compared the method they had proposed with the
contour method only visually. Unfortunately, they
failedtodescribethereferencemethod.
Liu et al. [25] proposed two
shoreline extraction
methods,bothofthemusingLiDARdataandremote
sensing imagery. It is noteworthy that the authors
created and made available a plugin for the ArcGIS
software named “ShorelineExtractor”, which enables
the determination of the shoreline course using the
contour and object‐oriented methods. The contour
method subtracts
the elevation of the local tidal
system from the elevation in the Digital Terrain
Model (DTM). In this way, a contour (a shoreline)
with an elevation of 0 m is obtained. On the other
hand,intheobject‐orientedmethod,aclusterofland
or water pixels is regarded as an
object, while the
447
shorelinesarecreatedasboundariesbetweenclusters
of different classes. The “ShorelineExtractor”
extension also enables the generalisation and
smoothingoftheshorelineobtainedusingoneofthe
two methods proposed by the authors. The first of
them is the shoreline simplification by the Douglas‐
Peucker method, which preserves points that
are
relevantintermsofmaintainingthebasicshapeofthe
curve.Thesecondmethodinvolvesananalysisofthe
shoreline shape and the elimination of bends with
highcurvature.Aspartofthevalidationtests,avisual
assessment of the shoreline extraction accuracy was
conductedbasedontheALS
datarecordedusingthe
ATM system. The measurements were conducted in
thecoastalzoneofGalvestonBay(USA)in1999.The
studydemonstratedthattheaccuracyoftheshoreline
coursedeterminationwas4.5m(p=0.95).Itshouldbe
pointed out that the use of a constant tidal datum
value for a
large region could lead to an error in
shorelinepositiondetermination.
Xu et al. [26] proposed a parametric method of
shoreline extraction based on the cloud of points
surveyed by LiDAR. The first part of the algorithm
involves the detection and rejection of the points
belongingtothewatersurface
byusingplanefitting
by the RANdom SAmple Consensus (RANSAC)
method [29], as well as density and distance
characteristics of individual points [30]. The second
part of the algorithm involves classification of the
land returns using the Euclidean cluster extraction
[27,28]. The indication of potential boundary points
and the optimisation of
the boundary formed from
them based on the cost function optimisation model
[26,31]. As part of the validation tests, a visual and
quantitative assessment of the shoreline extraction
accuracywasconductedbasedontheALSdata.The
measurements were carried out on five waterbodies
withdifferentgeometricalandopticalcharacteristics:
Bowman Lake, Canyon Stream, Oregon Estuary,
SusquehannaRiverandWaxLake,intheyears2005–
2014. Shoreline extraction accuracy metrics, such as
correctness and completeness, were calculated as
90.7% and 92.5%, respectively. Moreover, it was
demonstrated that the accuracy of the shoreline
course determination by the parametric method on
fivedifferent
waterbodieswas1m[26].Theobtained
results were compared with the results presented in
fourdifferentpapersaddressingsimilarissues.Ithas
been proven that their accuracy level was 1.5–31 m,
i.e.lowerthanthatoftheparametricmethod[26,32–
35].Itshouldbenotedthattheextractionresultswere
obtained on various data sets (aerial images and
LiDARpoints)withdifferentspatialresolutions.The
authors also addressed the issues related to the
parametricityofthemethodproposed.Theoperation
of the algorithm was tested for different parameter
values. In their article, they provided suggested
valuesofindividualparametersforwhich
satisfactory
resultsoftheshorelineextractiononfivewaterbodies
wereobtained.
Yousef et al. [36,37] developed a morphological
shoreline extraction method, which uses a DTM
created based on the ALS data and the local tidal
system.Themorphologicalalgorithmcompriseseight
main stages. The first stage is the process of
converting the point cloud from LiDAR
measurementsintotheformofadigitalterrainmodel.
In the second stage, thesegmentation (classification)
ofeachcelloftheDTMtooneofthetwoclasses:land
or water, is performed. In the third stage, the
anomalies that are interpreted as outliers and
measurementerrorsaredetectedandremovedusing
the neighbourhood test. In the fourth stage,
constrainedmorphologicalopenandcloseoperations
are carried out in order to remove the remaining
artifacts,suchasgapsbetweentheneighbouringland
areasorbrokenpartsofwaterareas.Inthefifthstage,
smallisolated
landandwaterbodiesareremoved.In
thesixthstage,theHoughtransform[38]isappliedto
removestructuresofananthropogenicnature,suchas
bridges, docks or fishingpiers. In the seventh stage,
the shoreline is determined and subsequently
smoothed. To this end, the authors performed the
Gaussian kernel. In
the eighth stage, the shoreline
obtained was superimposed on an aerial image in
ordertovisuallyassesstheextractionresults.Aspart
of the validation tests, a visual and quantitative
assessment of the shoreline extraction accuracy was
conductedbasedontheALSdatarecordedusingthe
LMS‐Q680i system. The
measurements were
performed along the coast of the USA, passing
through three states: New Jersey, Rhode Island and
Virginia,intheyears2008–2012.Inordertoassessthe
shoreline extraction accuracy, the shoreline
determined manually based on an aerial image was
used. Moreover, a Monte Carlo simulation was
performed in the
article in order to estimate the
shoreline extraction errors using the morphological
method. Statistical analyses showed that the mean
errorandthestandarddeviationwere1.21mand1.97
m,respectively.Thestudyresultsobtainedusingthe
morphological method were compared with the
results obtained using the reference methods
proposed
by [25,39]. The morphological method has
been proven to have a higher accuracy of shoreline
position determination than that of the reference
methods.
As part of the INNOBAT project [40], it was
decidedtoimplementtheparametricmethod[26]for
shoreline extraction. An important advantage of the
methodis theuse
of onlythegeometricalproperties
of the LiDAR point cloud. The method proposed
enablesthe fullautomationof the extractionprocess
and offers the possibility for conducting further
research to attempt to develop specific parameter
valuesforaparticularmeasurement(waterbodytype,
the nature of the shoreline and measurement
conditions)
[31]. Moreover, according to the results
presented by the original authors, the parametric
method enables the fulfilment of the accuracy
requirements provided for the most rigorous
International Hydrographic Organization (IHO)
order,i.e.theExclusiveOrder(horizontalaccuracyof
5m(p=0.95))[41],whichrefertotheworksrelatedto
the shoreline
course determination. In view of the
above, the aim of this article is to validate the
parametric method of shoreline extraction based on
theLiDARdatarecordedusinganUnmannedSurface
Vehicle(USV).
448
2 MATERIALSANDMETHODS
2.1 Datacollection
The shoreline extraction was performed on data
collected with the Velodyne VLP‐16 laser scanner
mounted on the HydroDron USV. Obtained results
were validated against the ground‐truth data
determinedwithaGlobalNavigationSatelliteSystem
(GNSS) Real Time Kinematic (RTK) receiver. The
studyareawasashorelinesectionoftheLakeKłodno
(Poland).Boththelakeandthemeasurementareaare
presentedonFigure1.
Figure1.SatelliteimageoftheLakeKłodnowiththeareain
which the hydrographic surveys were conducted marked
witharedrectangle.
The data was collected and georeferenced to the
PL‐UniversalTransverseMercator(UTM)(zone34N)
and PL‐EVRF2007‐NH systems using the HYPACK
software. To compensate for the movements of the
vessel and obtain accurate positions, the HYPACK
program was integrated with the Ekinox2‐U Inertial
NavigationSystem(INS)anda
GNSSRTKreceiver.
2.2 Shorelineextractionmethod
Theshorelineextractionmethodusedinthisworkis
basedonthemethodproposedbyXuetal.[26].The
modifications involve additional filtration steps and
skipping of the shoreline approximation using the
cost model proposed by the authors of the original
method.
This was due to the problems with the
implementationoftheoriginalapproach,describedin
furthersectionsofthearticle.Theshorelineextraction
method used in this work comprises of five main
stages:
1. ClassificationofpointsintheLiDARderivedpoint
cloud into clusters using Euclidean clustering,
describedindetail
byRusu[28];
2. Indication of potential boundary points using the
authors’originaltestalgorithm[26];
3. Filtration of potential boundary points using the
elevationthreshold;
4. Manual indication of curve points in the water
along the entire shoreline section at a relatively
constantdistancefromtheshore;
5. Calculation
of the average distance between the
points and the formed curve, rejection of points
foundfurtherthantheaveragedistance.
2.3 Extractionerrorcalculation
In order to quantitatively measure the error of the
extraction method, the Euclidean distance was
computed between coordinates of each extracted
point and the coordinates of the
closest Ground
Control Point (GCP). The Mean Error (ME) was
calculated using the Euclidean distance, and its
formulaisgivenbyEquation1:
1
1
min ,
N
ij
j
i
M
EdPGCP
N
, (1)
where:
N–numberofextractedshorelinepoints(–);
i–numberingrepresentingshorelinepoints(–);
j–numberingrepresentingGCPs(–);
P
i–i‐thshorelinepoint(–);
GCP
j–j‐thGCP(–);
d(P
i,GCPj)–Euclideandistancebetweeni‐thshoreline
pointandj‐thGCP(m).
The Euclidean distance for a pair of shoreline
pointsp,qisgivenbyEquation2:
222
,
pq pq pq
dpq x x y y z z , (2)
where:
d(p,q) – Euclidean distance between points p, q in
three‐ dimensionalCartesiancoordinatespace(m);
p, q – numbering representing a pair of shoreline
points(–);
x–longitudeoftheshorelinepoint(m);
y–latitudeoftheshorelinepoint(m);
z–heightoftheshorelinepoint(m).
Min.andmaxvaluesoftheshorelinepositionerror
were calculated in similar manner, as well as the
standarddeviationofthemean.Obtainedvalues
are
presentedattheendoftheResultssection.
3
RESULTS
The shoreline extraction method applied was
developedbased onthe extraction methodproposed
byXuetal.[26].Severalissuesthatweredescribedin
detail in this article prevented the authors of this
study from implementing the method described in
[26] in its original form. Additional filtering steps
were required
in order to remove the excess points.
Moreover, the method for shoreline approximation
givenasetofboundarypointswasnotperformeddue
to problems with its implementation. Instead, the
manualconnectionofextractedpointswasperformed
for ease of visual analysis. Additionally, the mean
shoreline position error and deviation
were
calculated.Itshouldbealsonotedthatthepointcloud
datausedinthisstudywasobtainedusingadifferent
technique [Terrestrial Laser Scanning (TLS) from a
movingUSVratherthanALS].Belowaretheresults
oftheextractionroutineperformedinthispaper.The
following steps assume that the
cloud does not
contain many water returns. Otherwise, prior
filtration of water returns should be performed, e.g.
usingthedensityanddistancethresholdsmentioned
449
by [26,30]. In the case of the measurements on the
LakeKłodno,therewerehardlyanywaterreflections,
thus,theadditionalfiltrationstepwasnotperformed
(Figure2).
Figure2. Point cloud derived from LiDAR measurements
conductedalongthesectionoftheLakeKłodnoshoreline.
3.1 ClusterisationofLiDARreturns
OneofthefirststepsofthealgorithmistheEuclidean
extraction, which clusters points in the point cloud
based on the distance to others. This algorithm
requires that three parameters are provided [28].
Thesearethemin.numberofpointsinthecluster,the
max number
of points in the cluster and the cluster
tolerance. In their study, the authors [26] only
providedthevalueusedforthemin.numberofpoints
inthecluster.Themaxnumberofpointsinthecluster
can be omitted, by setting its value as the number
equal to or
higher than the number of points in the
cloud. This was done in this study, as a result the
constraint on the max cluster size was removed.
However, the cluster tolerance parameter is crucial,
affectingtheresultsdramatically,yetitalsoremains
left out in the study by Xu et al.
[26]. The
clusterisationstepcouldbedescribedasthedatapre‐
processingstageandhasahugeimpactontheresults
oftherestofthealgorithmicroutine.Itwasnecessary
todeterminetheparametersoftheclusteringprocess
for the study area. To this end, the Euclidean
clustering[28]
wasperformedforallthecombinations
of parameter values from Table 1. Results of the
classification obtained for each parameter
combination were evaluated through visual
inspection.
Table1.ParametergridusedfortheEuclideanclustering
evaluation.
________________________________________________
Parameter Value
________________________________________________
Tolerance(m) 0.1,0.25,0.5,0.75,1,1.5,2,3,4
Min.points(–) 200, 10000
Maxpoints(–) 10
8
(representsnorestrictions)
________________________________________________
Selectedresults from theEuclidean clusteringare
presentedonFigures3and4.
Figure3. Influence of the tolerance parameter on the
clusterisationresults.Theleftimage(a)showstheresultsof
theEuclideanclusteringwithatoleranceof0.25mandmin.
clustersizesetto200points.Therightimage(b)showsthe
resultsof theEuclideanclusteringwith a tolerance of3 m
andmin.clustersizesetto200points.
Figure4. Influence of the min. number of points in the
clusterontheclusterisationresults.Theleftimage(a)shows
theresultsoftheEuclideanclusteringwithatoleranceof0.5
mandmin.clustersizesetto200points.Therightimage(b)
shows the results of the Euclidean
clustering with a
toleranceof0.5mandmin.clustersizesetto10,000points.
3.2 Identificationofpotentialboundarypoints
In[26],analgorithmcalledthetestingalgorithmwas
proposed by the authors to identify potential
boundarypointsusinganiterativeconvexhullfitting
approach. The algorithm required a custom
implementationasthesourcecodewasnotprovided
intheoriginalpaper.Therefore,thealgorithmwas
re‐
implemented, according to the description provided
in[26].Toensurecorrectnessoftheimplementation,a
simplevalidationwasperformedonanartificialsetof
100points(Figure5).
Figure5.Testingalgorithm[26]appliedtoanartificialsetof
100points.Theleftimage(a)showstheinitialstageofthe
algorithmwhenallpointsaretreatedasunlabeledpotential
candidates.Inthe middle plot(b),the firstiteration ofthe
algorithmisshown.Forthefirsttestedpoint,
markedwitha
blue cross, 10nearest neighboursare selectedand marked
withorangecrosses.Aconvexhulliscreatedforthesetof
points containing the tested point and its neighbours,
markedbytheblackcontour.Thepointsinsidetheconvex
hullarelabeledasnon‐boundarypointsand
colouredred.
Theprocessisthenrepeateduntilnomorepointsarefound
thatcouldbelabeledasnon‐boundary.Therightimage(c)
shows the final results, where non‐boundary points are
colouredinredandpotentialboundarypointsarecoloured
inblue.
450
Theresultsdemonstratethatthetestingalgorithm
wascorrectlyimplemented.Then,thealgorithmwas
applied to the clustered point cloud to identify
candidate boundary points for the Lake Kłodno
dataset. Results of the boundary point identification
usingthetestingalgorithm[26]onrealworldLiDAR
data are presented on
Figure 6. They were obtained
usingtheoriginalpointcloudwithnodownsampling,
after performing the Euclidean clustering with a
toleranceof0.5mandmin. clustersizesetto10,000
points.Inorder toincreaseefficiencyoftheiterative
convex hull fitting, a three‐dimensional k‐d tree [28]
was used for space partitioning. Such approach is
very efficient and may significantly speed up the
process of searchingnearest neighboursinthepoint
cloud.
Figure6.Resultsofthetestingalgorithm[26]appliedtothe
LakeKłodnodataset.
3.3 Filtrationofpotentialboundarypoints
Themainproblematthisstageofthealgorithmisto
eliminate the points that do not constitute the
shoreline(e.g.thetreecover).Includingthosepoints
in the shoreline would greatly impact the accuracy.
Therefore, a filtration method is necessary. To this
end, the authors
of the original method used an
elevationthreshold[26].Inthispaper,theapproachis
followed, and the results of applying an elevation
thresholdof1mheightrelativetothemeasuredwater
surfaceelevationarepresentedonFigure7.
Figure7. Results offiltrationof the candidatepoint clouds
using elevation threshold of 1 m height relative to the
measuredwatersurfaceelevation.
Theaboveresultsaresatisfactory,yetmanypoints
thatarenotdirectcomponentsoftheshorelineremain
inthepointcloud.Visualinspectionofthepointcloud
atthisstagerevealedthatsomepointsinthecloudare
up to 15–20 m inland. Therefore, another filtration
wasnecessary.Thefiltrationapproach
wasbasedon
thedistancetothewaterbody.Tothisend,themanual
indication of a curve consisting of 5 points was
performed. The curve was assumed to be placed on
the waterbody and roughly following the shoreline.
The elevation of the curve is constant and was
determined by fitting
a plane to all of the points
remaininginthecloud.ThemeanEuclideandistance
was calculated for all of the remaining potential
boundary points. Then, the curve was used to filter
outpointsthatwerefurtherthanmeandistancefrom
the curve. This was repeated twice, in order to
strengthen
the removal effect. The results of this
supervised filtration approach are presented on
Figure8.
Figure8. Results offiltrationof the candidatepoint clouds
usingthemeandistancefrompolylinethreshold.Redpoints
are removed from the candidate boundary points. Green
points are the remaining points which will be used for
boundaryapproximation. Twoconsecutivefiltrations were
performed using the same curve and shrinking set
of
candidateboundarypoints.
The elevation and waterbody distance filtration
steps allowed to filter out the points that were
deemed unnecessary, without losing the underlying
shoreline geometry information. It should be noted
thattheshorelineistraditionallydefinedby a curve
ratherthanasetofpoints.Sofarthealgorithmresults
in a set
of points. Therefore, it is necessary to
determine an order in which the points should be
connected.Theapproximationofshorelinefromaset
ofpointsisa non‐trivialtask, whichisdescribedin‐
depthinthefollowingsection.
3.4
Approximationofshorelinefromasetofpoints
Authorsoftheoriginalarticle[26]proposetofindthe
optimalshorelinefromthesetofboundarypointsby
evaluating edges constructed by all possible 3‐point
permutations of said points. The paper proposes a
costoptimisationmodel,whichconsistsofnodesthat
representthepermutations.Singlenodeinthemodel
representstheselectionofthreepointsfromthecloud
andlinkingthemastheleftmost,themiddleandthe
rightmost one. The model evaluates each such
451
permutation using a novel cost function, which
calculates the cost of each node according to the
Equation3[26]:
,,
cos , , cos
22
klm
dkl dlm
tklm
, (3)
where:
cost(k,l,m)–costofthesinglenode(–);
k,l,m–numberingrepresentingthek‐th,l‐thandm‐th
point from the point cloud (3‐point permutation
with no repetitions), assigned respectively as the
leftmost,themiddleandtherightmostpointsinthe
shorelinesection(–);
d(k,l) – Euclidean distance between the leftmost and
themiddlepointinthenode(m);
d(l,m) – Euclidean distance between the middle and
therightmostpointinthenode(m);
λ–weightcoefficient(–);
θ
klm–anglebetweenedges(k,l)and(l,m)(rad).
This is an NP‐hard combinatorial optimisation
problem. Solving such problems typically requires a
specific approach that takes into account the
problemʹsuniquecharacteristicsandstructure.Dueto
the complexity of NP‐hard problems, finding exact
solutions may be
infeasible or even impossible in
some cases. Therefore, heuristic and approximation
algorithms are often used to find near‐optimal
solutionsefficiently.Theauthors[26]proposedtouse
adynamicprogrammingapproachandbacktrackthe
solutionfrom thesink node tothesource.However,
the problem of defining source and sink nodes
was
not clearly addressed in their paper. The
representationoftheproblem proposed by Xu et al.
[26]isalsocomputationallyexpensive.Inagraphin
which eachnode representsthe3‐point permutation
of points created from n‐element point cloud, the
numberofpermutationsisdescribedbyEquation
4:
1!
,3
23
n
Pn
n
, (4)
where:
P(n,3) – set of all 3‐element permutations with no
repetitionsfromn‐elementpointcloud(–);
n–numberofpointsinthepointcloud(–).
Multiplication by ½ in the above formula results
from ignoring reverse permutations. Point clouds
derived from laser scanning are considerably
large,
and the number of points at the end of algorithmic
routine may vary depending on the parameters an
individualtraitsof thescannedarea.For thedataset
usedinthisstudy,aftertheelevationthresholdthere
was still over 1000 points left, which results in over
840millionpermutationswith
norepetitionsand no
reversed permutations included, according to the
Equation 4. Due to the above‐mentioned issues, the
shorelineapproximationbasedonthesetofobtained
boundary points was not performed in this study.
Instead, a point‐wise qualitative and quantitative
error of shoreline extraction was performed. The
extracted
shoreline points (black colour)
superimposed on the GCPs (green colour) are
presentedonFigure9.
Figure9. Extracted boundary points (black colour)
superimposedontheGCPs(greencolour).
In order to verify the performed extraction in a
quantitativeway,thepositionerrorsoftheindividual
pointsmakingupthecurve(shoreline)obtainedwere
calculated. For each of the 281 shoreline points, the
nearestGCPwasselected.Thecalculatedstatisticsare
providedinTable2.
Table2.Summaryoferrorsofthe281pointscomprisingthe
extractedshorelineobtainedinrelationtothereferenceline
determinedusingaGNSSRTKreceiver.
________________________________________________
Mean Standard Max Min.
error(m) deviation(m) error(m) error(m)
________________________________________________
2.12 1.115.54 0.41
________________________________________________
A one‐tailedt‐test was additionally performed to
verify, if the extraction results fulfil the accuracy
requirements provided for the Exclusive Order (i.e.
horizontal accuracy of 5 m (p=0.95)). In the test, the
null hypothesis (H
0) was specified as the (error)
populationmeanbeinglargerorequalto5m,while
the alternative hypothesis (H
A) was specified as the
(error) population mean being less than 5 m. The
calculatedt‐statisticof–43.36andaverysmallp‐value
of1.4∙10
‐126
mallowtorejectthenullhypothesiscanbe
rejected with high confidence. Therefore, results
presented in this work show that the method used
fulfils the accuracy requirements provided for the
moststringentIHOorder.
4
DISCUSSION
Most of the state‐of‐the‐art in the area of shoreline
extraction puts focus on using methods based on
DTMs using cross‐shore profiles or contours of the
vertical datums. This article explores the topic of
shorelineextractionbasedonthegeometryofLiDAR
derivedpointclouds.Methodswhich
arebasedsolely
ongeometryarequitescarceintheliterature.Inthis
paper,theresultsofreimplementationofthemethod
proposedbyXuetal.[26]aredescribed.Specifically,
theprocessofclustering the point cloud,identifying
the candidate boundary points and filtering the
candidatesisvalidatedona
real‐worlddataset.
The direct interpretation of the clusterisation
results in the case of a problem with shoreline
452
identificationishinderedduetotheheterogeneityof
theenvironmentandtheobjectsfoundthere.Inother
words,this is not apuretest caseofthe desk object
type [28], where the interpretation of the results is
relatively easy. However,it is quite evident that the
resultsarevery
parameterdependent.Hightolerance
values lead to grouping points into bigger clusters,
whilelowvaluescanseparatetoomanyclusters.Best
results on the dataset from the Lake Kłodno were
obtainedforatoleranceof0.5mandmin.clustersize
of 10,000 points. These settings allowed for most
of
the point cloud to be discarded, while keeping the
largest clusters adjacent to the waterbody. It is
important to note that the results may differ if the
point cloud was derived from ALS. Moreover,
additionalprocessingisneededtofacilitatethetaskof
shorelineidentificationwiththeresultingpointcloud.
The iterative convex hull fitting approach is
effectiveinidentifyingedgesinanunorganisedpoint
cloud.However,althoughthisapproachsignificantly
reduces the number of remaining points, further
filtrationisstillrequired.Itappearsthatthisapproach
will inevitably result in a large number of points
remaining at the far‐
off ends of the clusters, which
needtobeeliminated.Toachievethis,theauthors[26]
employ an elevation threshold, which may pose
challenges in areas with waterbodies that have
varying elevations. Nevertheless, the original article
demonstrates promising results in such cases.
However, this approach may also prove challenging
in areas
with low terrain slopes surrounding the
waterbody.
Inthispaper,amulti‐stepfiltrationapproachwas
employed to identify shoreline points in a LiDAR
derivedpointcloud.Thefirststepinvolvedusingthe
elevationthresholdasproposedbyXuetal.[26].This
approachissimpleandeffective,particularlyin
cases
whereonlyonewaterbodyispresentinthesceneand
theadjacentterrainhasanoticeableslope.However,
in the case of the Lake Kłodno point cloud, this
approach alone was not sufficient, and additional
filtrationwasrequiredduetothelowterrainslopein
the region. To address
this issue, a supervised
filtration step was proposed, which involved
manually determining a 5‐point curve that
approximatelyfollowedtheshoreline.Then,themean
distance from the curve was calculated for all
remainingpointsandusedasathresholdtoeliminate
far‐off points that did not constitute the shoreline.
This operation was repeated twice but could be
repeated more times, though with increasing loss in
the underlying shoreline geometry. This approach
effectively removed unwanted points while
preserving the essential shoreline points for further
analysis.
Thetaskofshorelineapproximationis acomplex
one, as previously discussed. While the approach
introduced
by Xu etal.[26] of finding the min. cost
pathbetweenpermutationsofallpoints inthepoint
cloud is intriguing, its computational expense is a
notabledrawback.Moreover,theoriginalmanuscript
lacked certain implementation details, which made
reimplementation challenging. This emphasises the
necessityofdevelopingpreciseandefficient
methods
forapproximatingshorelinesfrompointclouds.
5
CONCLUSIONS
The applied method successfully extracted the
shoreline with an average accuracy of 2.12 m and a
standard deviation of 1.11 m. However, to evaluate
the methodʹs reliability, it is essential to test it on
largerdatasetsderivedfromdiversewaterbodiesand
scanningtechniques,suchasALS.Notably,Xu
etal.
[26] proposed their method for larger scale scenes
surveyed using airborne LiDAR. This study
demonstrates that key concepts utilised in the
algorithmic routine, such as clusterisation, convex
hull fitting, as well as elevation and distance
thresholds, can effectively obtain a high accuracy
shorelinerepresentationthatmeetsIHOstandards.
To
utilise point cloud‐based methods effectively, it is
crucial to enhance filtration techniques and develop
efficient algorithms for shoreline approximation. As
theeffectivenessoftheinvestigatedmethodsdepends
heavily on parameter settings, developing
customisable plugins with user‐friendly interfaces
andinteractivevisualisationstoassistindetermining
feasibleparameterscouldbe
highlybeneficial.
FUNDING
This research was funded by the National Centre for
Research and Development in Poland, grant number
LIDER/10/0030/L‐11/19/NCBR/2020.Moreover,thisresearch
wasfundedfromthestatutoryactivitiesofGdyniaMaritime
University, grant numbers WN/PI/2023/03 and
WN/2023/PZ/05.
REFERENCES
1.Li, Z.; Zhai, J.; Wu, F. Shape Similarity Assessment
MethodforCoastlineGeneralization.ISPRSInt.J.Geo‐
Inf.2018,7,283.
2.Sui, L.; Wang, J.; Yang, X.; Wang, Z. Spatial‐temporal
Characteristics of Coastline Changesin Indonesiafrom
1990to2018.Sustainability2020,12,3242.
3.Kanwal,S.;Ding,
X.;Sajjad,M.;Abbas,S.ThreeDecades
of Coastal Changes in Sindh, Pakistan (1989–2018): A
GeospatialAssessment.RemoteSens.2020,12,8.
4.Nikolakopoulos,K.;Kyriou,A.;Koukouvelas,I.;Zygouri,
V.;Apostolopoulos,D.CombinationofAerial,Satellite,
andUAVPhotogrammetryforMappingtheDiachronic
CoastlineEvolution:TheCaseofLefkada
Island.ISPRS
Int.J.Geo‐Inf.2019,8,489.
5.Zhang, Y.; Hou, X. Characteristics of Coastline Changes
on Southeast Asia Islands from 2000 to 2015. Remote
Sens.2020,12,519.
6.Mury, A.; Jeanson, M.; Collin, A.; James, D.; Etienne, S.
HighResolutionShoreline andShellyRidgeMonitoring
over Stormy
Winter Events: A Case Study in the
MegatidalBayofMont‐Saint‐Michel(France).J.Mar.Sci.
Eng.2019,7,97.
7.Fu, Y.; Guo, Q.; Wu, X.; Fang, H.; Pan, Y. Analysis and
Prediction of Changes in Coastline Morphology in the
BohaiSea,China,UsingRemoteSensing.Sustainability
2017,
9,900.
8.Mahamud,U.; Takewaka,S.Shoreline Changearounda
RiverDelta onthe Cox’sBazar Coast of Bangladesh. J.
Mar.Sci.Eng.2018,6,80.
9.Martínez,C.; Quezada, M.;Rubio,P.HistoricalChanges
in the Shoreline and Littoral Processes on a Headland
Bay Beachin Central Chile.Geomorphology
2011, 135,
80–96.
453
10.Chu, Z.X.; Yang, X.H.; Feng, X.L.; Fan, D.J.; Li, Y.K.;
Shen, X.; Miao, A.Y. Temporal and Spatial Changes in
CoastlineMovementoftheYangtzeDeltaduring1974–
2010.J.AsianEarthSci.2013,66,166–174.
11.Cowart, L.; Corbett,D.R.; Walsh,J.P. ShorelineChange
along Sheltered Coastlines: Insights from the
Neuse
River Estuary, NC, USA. Remote Sens. 2011, 3, 1516–
1534.
12.Kuleli, T.; Guneroglu, A.; Karsli, F.; Dihkan, M.
Automatic Detection of Shoreline Change on Coastal
RamsarWetlandsofTurkey.OceanEng.2011,38,1141–
1149.
13.Specht, M.; Specht, C.; Lewicka, O.; Makar, A.;
Burdziakowski,P.;Dąbrowski,P.Study
ontheCoastline
Evolution in Sopot (2008–2018) Based on Landsat
SatelliteImagery.J.Mar.Sci.Eng.2020,8,464.
14.Zhang,X.;Pan,D.;Chen,J.;Zhao,J.;Zhu,Q.;Huang,H.
Evaluation of Coastline Changes under Human
Intervention Using Multi‐temporal High‐resolution
Images: A Case Study ofthe
ZhoushanIslands, China.
RemoteSens.2014,6,9930–9950.
15.Specht, C.; Weintrit, A.; Specht, M.; Dąbrowski, P.
Determination of the Territorial Sea Baseline—
MeasurementAspect.IOPConf.Ser.EarthEnviron.Sci.
2017,95,1–10.
16.Specht, M.; Specht, C.; Wąż, M.; Dąbrowski, P.; Skóra,
M.; Marchel,Ł. Determining
the Variability of the
Territorial Sea Baseline on the Example of Waterbody
Adjacent to the Municipal Beach in Gdynia. Appl. Sci.
2019,9,3867.
17.Basterretxea,G.;Orfila,A.;Jordi,A.;Fornós,J.;Tintoré,J.
Evaluation of a Small Volume Renourishment Strategy
on a Narrow Mediterranean Beach. Geomorphology
2007,88,139–151.
18.Specht,M.; Specht,C.;Mindykowski,J.; Dąbrowski, P.;
Maśnicki, R.; Makar, A. Geospatial Modeling of the
Tombolo Phenomenon in Sopot Using Integrated
Geodetic and Hydrographic Measurement Methods.
RemoteSens.2020,12,737.
19.Viaña‐Borja, S.P.; Ortega‐Sánchez, M. Automatic
Methodology to Detect the Coastline from Landsat
Images with a New Water Index Assessed on Three
Different Spanish Mediterranean Deltas. Remote Sens.
2019,11,2186.
20.Boak, E.H.; Turner, I.L. Shoreline Definition and
Detection:AReview.J.Coast.Res.2005,214,688–703.
21.Stockdonf, H.F.; Sallenger Jr.; A.H.; List, J.H.; Holman,
R.A.EstimationofShorelinePositionandChange
Using
AirborneTopographicLidarData.J.Coast.Res.2002,18,
502–513.
22.Farris, A.S.; Weber, K.M.; Doran, K.S.; List, J.H.
ComparingMethodsUsedbytheU.S.GeologicalSurvey
Coastal and Marine Geology Program for Deriving
Shoreline Position from Lidar Data. Available online:
https://pubs.usgs.gov/of/2018/1121/ofr20181121.pdf
(accessedon26April2023).
23.Fernández
Luque,I.;AguilarTorres,F.J.;AguilarTorres,
M.A.; Pérez García, J.L.; López Arenas, A. A New,
Robust, and Accurate Method to Extract Tide‐
coordinatedShorelinesfromCoastalElevationModels.J.
Coast.Res.2012,28,683–699.
24.Hua, L.W.; Bi, Y.L.; Hao, L. The Research of Artificial
ShorelineExtractionBasedonAirborne
LIDARData. J.
Phys.:Conf.Ser.2021,2006,012048.
25.Liu, H.; Wang, L.; Sherman, D.J.; Wu, Q.; Su, H.
Algorithmic Foundation and Software Tools for
Extracting Shoreline Features from Remote Sensing
ImageryandLiDARData.J.Geogr.Inf.Syst.2011,3,99–
119.
26.Xu, S.; Ye, N.; Xu, S.
A New Method for Shoreline
ExtractionfromAirborneLiDARPointClouds.Remote
Sens.Lett.2019,10,496–505.
27.Rusu, R.B. Semantic 3d Object Maps for Everyday
Manipulation in Human Living Environments. KI‐
KünstlicheIntelligenz2010,24,345–348.
28.Rusu, R.B. Semantic 3d Object Maps for Everyday
Manipulation in Human Living
Environments. PhD
Thesis, Technische Universität München, München,
Germany,2009.
29.Xu,S.;Xu,S.AMinimum‐costPathModeltotheBridge
ExtractionfromAirborneLiDARPointClouds.J.Indian
Soc.RemoteSens.2018,46,1423–1431.
30.Smeeckaert,J.;Mallet,C.;David,N.;Chehata,N.;Ferraz,
A. Large‐scale Classification of
Water Areas Using
Airborne Topographic LiDAR Data. Remote Sens.
Environ.2013,138,134–148.
31.Lewicka, O.; Specht, M.; Stateczny, A.; Specht, C.;
Dardanelli, G.; Brčić, D.; Szostak, B.; Halicki, A.;
Stateczny,M.;Widźgowski,S.IntegrationDataModelof
the Bathymetric Monitoring System for Shallow
Waterbodies Using UAV
and USV Platforms. Remote
Sens.2022,14,4075.
32.Di, K.; Wang, J.; Ma, R.; Li, R. Automatic Shoreline
Extraction from High‐resolution IKONOS Satellite
Imagery. In Proceedings of the American Society for
Photogrammetry and Remote Sensing Annual
Conference2003(ASPRS2003),Anchorage,AK,USA,5–
9May2003.
33.Lee,
I.‐C.; Cheng, L.; Li, R. Optimal Parameter
Determination for Mean‐shift Segmentation‐based
Shoreline Extraction Using Lidar Data, Aerial
Orthophotos, and Satellite Imagery. In Proceedings of
the American SocietyforPhotogrammetry andRemote
Sensing Annual Conference 2010 (ASPRS 2010), San
Diego,CA,USA,26–30April2010.
34.Liu, H.; Sherman,
D.; Gu, S. Automated Extraction of
Shorelines from AirborneLightDetection andRanging
Data and Accuracy Assessment Based on Monte Carlo
Simulation.J.Coast.Res.2007,236,1359–1369.
35.Niedermeier, A.; Romaneeßen, E.; Lehner, S. Detection
of Coastlines in SAR Images Using Wavelet Methods.
IEEETrans.Geosci.RemoteSens.2000,
38,2270–2281.
36.Yousef, A.H.; Iftekharuddin, K.; Karim, M. A New
Morphology Algorithm for Shoreline Extraction from
DEMData.InProceedingsoftheSPIEDefense,Security,
and Sensing 2013, Baltimore, MA, USA, 29–30 April
2013.
37.Yousef, A.H.; Iftekharuddin, K.M.; Karim, M.A.
ShorelineExtractionfromLightDetectionand Ranging
Digital Elevation
Model Data and Aerial Images. Opt.
Eng.2013,53,011006.
38.Trucco, E.; Verri, A. Introductory Techniques for 3‐D
Computer Vision; Prentice Hall: Hoboken, NJ, USA,
1998.
39.Lee, I.‐C.; Wu, B.; Li, R. Shoreline Extraction from the
Integration of LiDAR Point Cloud Data and Aerial
Orthophotos Using
Mean Shift Segmentation. In
Proceedings of the American Society for
Photogrammetry and Remote Sensing Annual
Conference2009(ASPRS2009),Baltimore,MD,USA,9–
13March2009.
40.Specht, M.; Stateczny, A.; Specht, C.; Widźgowski, S.;
Lewicka,O.; Wiśniewska,M.Conceptof an Innovative
Autonomous Unmanned System for Bathymetric
Monitoring
of Shallow Waterbodies (INNOBAT
System).Energies2021,14,5370.
41.IHO.IHOStandardsforHydrographicSurveys,6thed.;
SpecialPublicationNo.44;IHO:Monaco,Monaco,2020.
