Horizontal accuracy assessment of a novel algorithm for approximate a surface to a DEM
Abstract
This study evaluates the horizontal positional accuracy of a new algorithm that defines a surface that approximates DEM data by means of a spline function. This algorithm allows evaluating the surface at any point in its definition domain and allows analytically estimating other parameters of interest, such as slopes, orientations, etc. To evaluate the accuracy achieved with the algorithm, we use a reference DEM 2 m × 2 m (DEMref) from which the derived DEMs are obtained at 4 m × 4 m, 8 m × 8 m and 16 m × 16 m (DEMder). For each DEMder its spline approximant is calculated, which is evaluated at the same points occupied by the DEMref cells, getting a resampled DEM 2x2m (DEMrem). The horizontal accuracy is obtained by computing the area amongs the homologous contour lines derived from DEMref and DEMrem, respectively. It has been observed that the planimetric errors of the proposed algorithm are very small, even in flat areas, where you could expect major differences. Therefore, this algorithm could be used when an evaluation of the horizontal positional accuracy of a DEM product at lower resolution (DEMpro) and a different producing source than the higher resolution DEMref is wanted.
Full text
Ho izon al accu acy assessmen o a no el algo i hm o
app oxima e a su ace o a DEM
Ba e a, D. a,b, Ibáñez, M.J. a, Edda gani, S. a, c, Rome o, R. d, A iza-López, F.J.e, Reinoso-Go do,
J.F. ,*
a Depa men o Applied Ma hema ics, Uni e si y o G anada, Spain – [email p o ec ed], [email p o ec ed],
[email p o ec ed]
b IMAG -- Ins i u e o Ma hema ics, G anada, Spain
c Uni e si y Hassan Fi s , MISI Labo a o y, Mo occo
d Depa men o Compu e Science and A i icial In elligence, Uni e si y o G anada, Spain – [email p o ec ed]
e Depa men o Ca og aphic, Geodesic and Pho og amme y Enginee ing – [email p o ec ed]
Depa men o A chi ec u al and Enginee ing G aphic Exp ession – [email p o ec ed]
* [email p o ec ed]
Abs ac :
This s udy e alua es he ho izon al posi ional accu acy o a new algo i hm ha de ines a su ace ha app oxima es DEM
da a by means o a spline unc ion. This algo i hm allows e alua ing he su ace a any poin in i s de ini ion domain and
allows analy ically es ima ing o he pa ame e s o in e es , such as slopes, o ien a ions, e c. To e alua e he accu acy
achie ed wi h he algo i hm, we use a e e ence DEM 2 m × 2 m (DEM e ) om which he de i ed DEMs a e ob ained a
4 m × 4 m, 8 m × 8 m and 16 m × 16 m (DEMde ). Fo each DEMde i s spline app oximan is calcula ed, which is e alua ed
a he same poin s occupied by he DEM e cells, ge ing a esampled DEM 2x2m (DEM em). The ho izon al accu acy is
ob ained by compu ing he a ea amongs he homologous con ou lines de i ed om DEM e and DEM em, espec i ely. I
has been obse ed ha he planime ic e o s o he p oposed algo i hm a e e y small, e en in la a eas, whe e you could
expec majo di e ences. The e o e, his algo i hm could be used when an e alua ion o he ho izon al posi ional accu acy
o a DEM p oduc a lowe esolu ion (DEMp o) and a di e en p oducing sou ce han he highe esolu ion DEM e is
wan ed.
Keywo ds: Spline, Be ns ein basis, con ol poin s, Bézie o dina es, enso p oduc , esample, ho izon al accu acy, DEM
1. In oduc ion
Ha ing a ma hema ical unc ion ha ep esen s he e ain
h oughou i s con inuous de ini ion domain has di e en
ad an ages, among o he s he ollowing: a) I is possible o
sample egula meshes o gene a e digi al ele a ion models
(DEM) o bo h highe and lowe esolu ion han he da a
om which he ma hema ical unc ion was ob ained; and
his is achie ed hanks o i s de ini ion domain is
con inuous, b) mo phological a iables o in e es can be
ob ained om he co esponding ma hema ical o mulas o
he su aces, such as slope, o ien a ion, cu a u e and
no mal di ec ion, c) You could in e sec wo su aces
co esponding o homologous DEMs om di e en da es
and calcula e he inc ease o dec ease in he e ain
olume. The p o ision o unc ions o his ype has
allowed esampling h ough bilinea (Maune, 2007) and
bicubic (Keys, 1981) in e pola ions ha ha e been used in
di e en applica ions bo h o ob ain DEMs o highe and
lowe esolu ion. In he i s case, ob aining highe
esolu ion has been used o, o example, imp o e u ban
lood zones in he absence o dense models (Shen and
Tan, 2020); in he second case, i s use has been equen
when i was in ended o compa e he al ime ic accu acy o
a lowe esolu ion p oduc model wi h ano he highe
esolu ion e e ence model (Gao, 1998, Mukhe jee e al.
2013, Wang e al. 2015), al hough, in mos cases, he e o
in oduced by he esampling om a highe esolu ion o a
lowe one was le unanalysed, as indica ed by Mesa and
A iza, 2020. O he s udies ha e add essed he in luence o
esampling echniques on p oduc s de i ed om DEMs
such as s eam lows. (Leong e al., 2015).
Al hough p ocedu es a e a ailable o ex ac in o ma ion
di ec ly om a DEM, we p opose a new algo i hm o build
a su ace wi h low compu a ional cos ha adjus s he
ele a ions in o de o ha e an explici exp ession
( unc ion) om which o ind he elemen s o in e es . As
he e ain has many i egula i ies, a su ace should no be
cons uc ed oo egula . C1 con inui y is su icien . The
egula s uc u e o he DEM allows o de ine a piecewise
su ace de ined on a quad angula pa i ion o he e ain.
Mo e p ecisely, we de ine a piecewise bicubic su ace by
p o iding simple ules ha gi e he Bézie o dina es (c .
Fa in 2001) o he su ace pa ches ela i e o he squa es
ha make up he pa i ion.
Mos s udies on DEM accu acy o DEM THT compa e a
p oduc wi h a e e ence ha e analyzed he al i ude
P oceedings o he In e na ional Ca og aphic Associa ion, 4, 2021.
30 h In e na ional Ca og aphic Con e ence (ICC 2021), 14–18 Decembe 2021, Flo ence, I aly. This con ibu ion unde wen
single-blind pee e iew based on submi ed abs ac s. h ps://doi.o g/10.5194/ica-p oc-4-11-2021 | © Au ho (s) 2021. CC BY 4.0 License.
2 o 5
componen , lea ing he ho izon al componen un ouched.
The eason o he lowe numbe o in es iga ions de o ed
o he ho izon al componen is due o he di icul y o
inding a sa is ac o y me hod. In his wo k we will s udy
he ho izon al accu acy achie ed by he new algo i hm ha
we ha e p oposed. We will use he au oma ic algo i hm
based on homologous con ou lines in oduced in Reinoso,
2010 and igo ously demons a ed in Reinoso, 2011 o
e alua ing he ho izon al accu acy.
2. Ma e ial and Me hodology
Ou s udy was ca ied ou on a 2x2 m esolu ion DEM e
p oduced by he Ins i u o Geog á ico Nacional o Spain o
he Na a a egion. The ollowing phases ha e been
ca ied ou :
1. S a ing om he 2x2 m esolu ion DEM e , a
esampling has been pe o med using he nea es
neighbo me hod a esolu ions o 16x16, 8x8 and
4x4 m (DEMde ) which we espec i ely deno e
DEM4x4, DEM8x8, DEM16x16. In his way, he
DEMde ha e he same alues as he DEM e a he
poin s in e pola ed by he nea es neighbo
me hod.
2. To e alua e he capaci y o ou app oxima ion
algo i hm (Aapx) o es ima e he DEM e alues,
he su ace o each DEM e se ha calculado la
supe icie de cada DEMde (Sde ) has been
calcula ed using Aapx. Sde is assessed o ob ain
DEMs wi h he same esolu ion as DEM e which
we call DEM emXxX (DEM em4x4, DEM em8x8,
DEM em16x16).
3. The ho izon al displacemen be ween DEM e and
each one o he DEM emXxX is calcula ed using he
Reinoso 2011 con ou me hod.
4. The esul s ob ained wi h Aapx a e compa ed wi h
he adi ional bicubic esampling algo i hm.
2.1 Ma e ial
The DEM e has a cell size o 2x2m and y occupies an a ea
o 4.8x4.8 Km. Figu e 1 shows he geog aphical
cha ac e is ics o he en i onmen , as well as he DEM e
ha con ains la a eas along wi h o he s eep slopes. The
coo dina es a e e e ed in he ETRS89 sys em 30N UTM
zone.
Figu e 1: DEM used as e e ence and i s geog aphical
en i onmen
2.2 The app oxima ion algo i hm
We p opose o cons uc a spline su ace by means o a
enso p oduc o 1D spline app oximan s, de ining he
su ace pa ches di ec ly in he Be ns ein basis. Suppose
ha o a eal unc ion 𝑓 he alues 𝑓(𝑣𝑖), 𝑖 ∈ℤ, a e known,
whe e 𝑣𝑖=𝑖 ℎ, wi h ℎ > 0 he size o he pa i ion 𝛥≔
{𝑣𝑖:𝑖 ∈ ℤ}. The 1D app oxima ing spline 𝐴𝑓 educes on
each in e al 𝐼𝑖≔[𝑣𝑖,𝑣𝑖+1] o a cubic polynomial, whose
con ol polygon is o med by ou con ol poin s wi h
Bézie abscissae {𝑣𝑖,𝑣𝑖+ℎ
3,𝑣𝑖+1 −ℎ
3,𝑣𝑖+1}. I 𝐷3 is he
union (wi hou epe i ions) o hese Bézie abscissae and
𝑢𝑖=𝑣𝑖−ℎ
3y 𝑤𝑖= 𝑣𝑖+ℎ
3, hen 𝐷3=⋃{𝑢𝑖,𝑣𝑖,𝑤𝑖}
𝑖∈ℤ .
Fo 𝑥 ∈𝐼𝑖, i holds
𝐴𝑓(𝑥)=𝑉𝑖𝐵0(𝑡)+𝑊𝑖𝐵1(𝑡)+𝑈𝑖+1𝐵2(𝑡)+𝑉𝑖+1𝐵3(𝑡),
wi h 𝑡 = 𝑥
ℎ−𝑖 and 𝐵𝑘(𝑡)=(3
𝑘)𝑡𝑘(1−𝑡)3−𝑘, 0≤𝑘 ≤3.
The Bézie o dina es 𝑉𝑖,𝑊𝑖,𝑈𝑖+1 and 𝑉𝑖+1 a e de ined as
linea combina ions o poin alues 𝑓(𝑣𝑖): 𝑉𝑖=𝑓(𝑣𝑖),
𝑈𝑖=∑𝛼𝑟𝑓(𝑣𝑖+𝑟)
1
𝑟=−1 , 𝑊𝑖=∑𝛽𝑟𝑓(𝑣𝑖+𝑟)
1
𝑟=−1 ,
whe e he masks 𝛼 =(𝛼−1,𝛼0,𝛼1)∈ℝ3 and 𝛽 =
(𝛽−1,𝛽0,𝛽1)∈ℝ3 a e de e mined o achie e 𝐶1
con inui y as well as he ep oduc ion o he quad a ic
polynomials.
P oceedings o he In e na ional Ca og aphic Associa ion, 4, 2021.
30 h In e na ional Ca og aphic Con e ence (ICC 2021), 14–18 Decembe 2021, Flo ence, I aly. This con ibu ion unde wen
single-blind pee e iew based on submi ed abs ac s. h ps://doi.o g/10.5194/ica-p oc-4-11-2021 | © Au ho (s) 2021. CC BY 4.0 License.
3 o 5
P oposi ion 1 The unique masks yielding 𝐶1 con inui y
and he ep oduc ion o quad a ic polynomials a e
𝛼=(1
6,1,−1
6) and 𝛽=(−1
6,1,1
6).
Fu he mo e, he uni o m no m o he co esponding
ope a o 𝐴 is equal o 4/3.
F om he exac ness o 𝐴, he ollowing esul ega ding
he app oxima ion e o holds.
P oposi ion 2 The e exis cons ans 𝐾𝑙,𝑙 = 0,1,
independen o 𝑓 and ℎ and 𝑖, such ha
‖(𝑓−𝐴𝑓)(𝑙)‖∞,𝐼𝑖≤𝐾𝑙ℎ3−𝑙‖𝑓(3)‖∞,𝛺,
whe e 𝛺 =[𝑣𝑖−1,𝑣𝑖+2].
Now, gi en a 2D unc ion 𝑓(𝑥,𝑦) a bi-cubic piecewise
su ace 𝑠 is de ined as a enso p oduc app oximan : he
ope a o 𝐴 is applied o 𝑓 as a unc ion depending on 𝑥
(o 𝑦), and hen 𝐴 is again applied o de esul ing
unc ion, i.e. 𝑠(𝑥,𝑦)= 𝐴𝑦𝐴𝑥𝑓(𝑥,𝑦).
On each squa e 𝐼𝑖×𝐼𝑗 his unc ion is a bi-cubic Bézie
su ace, so ha i can be ep esen ed in Be ns ein-Bézie
o m. I is a linea combina ion o unc ions
𝐵𝑚(𝑥
ℎ−𝑖)𝐵𝑛(𝑥
ℎ−𝑗),0 ≤𝑚,𝑛 ≤3,
whose coe icien s a e exp essed in e ms o alues
𝑓(𝑣𝑖+𝑘,𝑣𝑗+𝑙),−1≤𝑘,𝑙 ≤1.
Fo F anke unc ion (see F anke 1982) ( op), he esul s
p o ided by he me hod p oposed o ℎ =2−7 a e shown
in Fig. 2.
Figu e 2: Resul s p o ided by ou Aapx o h=2-7 acco ding o
he F anke uncion
Also o Nielson es unc ion (Nielson 1978) i p o ides
good esul s o he same s ep leng h, shown in Fig.3.
Figu e 3: Resul s om ou Aapx algo i hm acco ding o he
Nielson es unc ion
2.3 Con ou s-based algo i hm o measu e he
ho izon al displacemen
The he ho izon al displacemen compu a ion o he ases
wi h espec o he DEM e is ca ied ou in he ollowing
phases:
1. The con ou s o bo h DEMs a e calcula ed (Fig. 4
a and b espec i ely), and hei homologous
cu es a e au oma ically iden i ied, e.g. cu es
C4a and C4b in Fig. 4 a and b.
2. A e supe imposing he homologous con ou s
(Fig. 4 c), he a eas enclosed be ween hem a e
calcula ed (g ay a ea in Fig. 4 d). The ho izon al
displacemen (Hdi) compu ed by he i h pai o
homologous con ou s (Cia, Cib) is o mula ed as
he a ea enclosed by bo h cu es (Ai) di ided by
he mean leng h o hose con ou s (𝐿𝑚𝑖=
𝐿𝑖𝑎+𝐿𝑖𝑏
2)
𝐻𝑑𝑖=𝐴𝑖
𝐿𝑚𝑖
3. And he mean displacemen o he DEM emXxX
espec o DEM e (𝐻𝑑DEM emXxX) is compu ed as
he weigh ed a e age o he displacemen s o all
he homologous con ou s, he weigh ing ac o
being he a e age leng h o hose con ou s,
di ided by he o al leng h o he a e age con ou s
being he o al leng h 𝐿𝑇𝑜𝑡 =∑𝐿𝑚𝑖
𝑛
𝑖=1 :
𝐻𝑑DEM emXxX =1
𝐿𝑇𝑜𝑡 ∑𝐴𝑖∗
𝑛
𝑖=1 𝐿𝑚𝑖
P oceedings o he In e na ional Ca og aphic Associa ion, 4, 2021.
30 h In e na ional Ca og aphic Con e ence (ICC 2021), 14–18 Decembe 2021, Flo ence, I aly. This con ibu ion unde wen
single-blind pee e iew based on submi ed abs ac s. h ps://doi.o g/10.5194/ica-p oc-4-11-2021 | © Au ho (s) 2021. CC BY 4.0 License.
4 o 5
Figu e 4: Hologous con ou s and a ea be ween hem
3. Resul s and discussion
To calcula e he 𝐻𝑑DEM emXxX a 10 m in e al be ween
con ou lines has been used, ha in ou DEM p oduces a
o al o 22 le els, speci ically hei heigh s anging om
450 o 660 m. In Fig. 5 you can see he homologous
con ou d awn on a shadow map, as well as a de ail whe e
he a ea enclosed be ween hose homologous con ou s a e
highligh ed on g een colo .
Figu e 5: A ea be ween homologous con ou s co esponding o
he DEM e and he DEM em16x16
Table 1 shows he mean ho izon al displacemen s as well
as hei s anda d de ia ions calcula ed o 4x4, 8x8 and
16x16m esolu ions using ou new Aapx algo i hm and he
adi ional bicubic esampling me hod.
DEM emXxX
𝐻𝑑DEM emXxX
Aapx (m)
Bicubic
(m)
DEM em4x4
Mean
0.07
0.99
S d
0.03
0.06
DEM em8x8
Mean
0.28
1.05
S d
0.13
0.06
DEM em16x16
Mean
0.81
1.38
S d
0.38
0.27
Figu e 6: Ho izon al displacemen om he
𝐻𝑑𝐷𝐸𝑀𝑟𝑒𝑚𝑋𝑥𝑋 espec o he DEM e , compa ing ou algo i hm
and he adi ional bicubic.
Table 1 shows ha ou new algo i hm p oduces be e
esul s han he adi ional bicubic algo i hm ega dless o
he cell size used as DEMde . While ou algo i hm seems o
dec ease he e o due o ho izon al displacemen a a a e
o ¼ as he esolu ion inc eases a a a e o 2, in he bicubic
algo i hm he a e o dec ease is much lowe . Howe e , no
la ge di e ences a e obse ed in he alues o he s anda d
de ia ions i bo h algo i hms a e compa ed o each le el
P oceedings o he In e na ional Ca og aphic Associa ion, 4, 2021.
30 h In e na ional Ca og aphic Con e ence (ICC 2021), 14–18 Decembe 2021, Flo ence, I aly. This con ibu ion unde wen
single-blind pee e iew based on submi ed abs ac s. h ps://doi.o g/10.5194/ica-p oc-4-11-2021 | © Au ho (s) 2021. CC BY 4.0 License.
5 o 5
o esolu ion. Howe e , addi ional es s should be ca ied
ou wi h a g ea e numbe o DEMs, co e ing all ypes o
e ain ( la , undula ing and moun ainous), in o de o
s a is ically alida e he appa en ly be e esul s o ou
algo i hm espec he adi ional bicubic one.
Ano he ad an age o he new algo i hm wi h espec o
he adi ional bicubic one is ha i has a lowe
compu a ional cos , making i a candida e o be
implemen ed in ca og aphic p oduc ion so wa e
packages.
We belie e ha his new algo i hm can be used when you
wan o know he posi ional accu acy (ho izon al and
e ical) o a lowe esolu ion DEM coming om a sou ce
o he han he e e ence one o ha has been c ea ed wi h
a di e en me hod om he e e ence one.
On he o he hand, i would also be in e es ing o ha e an
algo i hm ha no only epo ed he ho izon al
displacemen wi h a scala alue, bu also included
in o ma ion abou di ec ion in each o he cells, which
would be possible by adap ing he con ou s me hod by
Reinoso 2011.
4. Conclusions
In his wo k a new algo i hm (Aapx) is p esen ed o
app oxima e a DEM by means o a piecewise de ined
su ace (Sde ). I p esen s some ad an ages linked o i s
de ini ion ype, such as being able o ob ain he al i ude o
a poin in he en i e de ini ion domain o ha su ace, as
well as mo phological a iables ha cha ac e ize he
e ain su ace: slope, o ien a ion, cu a u e o no mal
di ec ion in an analy ical way. An immedia e applica ion
would be he possibili y o esampling Sde o ob ain DEMs
(DEM emXxX) o highe o lowe esolu ion han hose used
o c ea e Sde . One consequence o Aapx esampling
capabili ies is being able o assess he accu acy o a
p oduc DEM (DEMp o) agains a highe accu acy
DEM e . This assessmen could be ca ied ou bo h in he
e ical componen and in he ho izon al componen ,
which is he one s udied in his wo k. DEMp o can come
om bo h a sou ce o a me hod o he han he sou ce o
me hod used o c ea e he DEM e .
Aapx has shown a lowe ho izon al displacemen han he
adi ional bicubic in e pola ion algo i hm, which can be
in e p e ed as a lowe e o when esampling DEMs o
lowe esolu ion o o he s o highe esolu ion; These
p ocesses a e necessa y when ying o compa e he
accu acies o a DEMp o agains a DEM e , and whene e
possible i will be necessa y o choose hose algo i hms
ha p oduce he leas e o (ho izon al displacemen ).
The Aapx compu a ional cos is lowe han o he
concep ually simila such as he adi ional bicubic one.
Finally, in he u u e an expe imen will ha e o be
designed wi h a su icien ly la ge numbe o DEMs on
which o es Aapx so ha he esul s ha appea in his i s
Aapx s udy can be e i ied.
5. Re e ences
Fa in, G. (2001). Cu es and Su aces o CAGD: A
p ac ical guide, 5 h Edi ion. Mo gan Kau mann, San
F ancisco, USA.
F anke, R. (1982) Sca e ed da a in e pola ion: es s o
some me hods, Ma h. Comp. 157, pp. 181-200.
Gao, J. (1998). Impac o sampling in e als on he
eliabili y o opog aphic a iables mapped om g id
DEMs a a mic o-scale. In . J. Geog . In . Sci., 12, 875–
890.
Keys, R. (1981). "Cubic con olu ion in e pola ion o
digi al image p ocessing". IEEE T ansac ions on
Acous ics, Speech, and Signal P ocessing. 29 (6): 1153–
1160
Leong Tan, M.; Ficklin, D.L.; Dixon, B.; Ib ahim, A.L.;
Yusop, Z.; Chaplo , V. (2015). Impac s o DEM
esolu ion, sou ce, and esampling echnique on SWAT-
simula ed s eam low. Appl. Geog ., 63, 357–368
Maune D (2007) Digi al ele a ion model echnologies and
applica ions: he DEM use ’s manual, 2nd edn.Be hesda,
USA
Mesa-Mingo ance, J.L.; A iza-López, F.J. (2020)
Accu acy Assessmen o Digi al Ele a ion Models
(DEMs): A C i ical Re iew o P ac ices o he Pas Th ee
Decades. Remo e Sens. , 12, 2630.
Mukhe jee, S.; Joshi, P.K.; Mukhe jee, S.; Ghosh, A.;
Ga g, R.D.; Mukhopadhyay, A (2013). IU accu acy o
open sou ce Digi al Ele a ion Model (DEM). In . J.
Appl. Ea h Obs. Geoin ., 21, 205–217.
Nielson G. M. (1978) A i s o de blending me hod o
iangles based upon cubic in e pola ion, In . J. Nume .
Me h. Eng g. 15, pp. 308-318.
Reinoso, J. F. (2010) A p io i ho izon al displacemen
(HD) es ima ion o hyd ological ea u es when e sioned
DEMs a e used, Jou nal o Hyd ology,384: 1–2, pp. 130-
141.
Reinoso, J. F. (2011). An algo i hm o au oma ically
compu ing he ho izon al shi be ween homologous
con ou s om DTMs, ISPRS Jou nal o Pho og amme y
and Remo e Sensing, 66: 3, pp. 272-286.
Shen, J., Tan, F. (2020). E ec s o DEM esolu ion and
esampling echnique on building ea men o u ban
inunda ion modeling: a case s udy o he 2016 looding
o he HUST campus in Wuhan. Na Haza ds 104, 927–
957.
Wang, B.; Shi, W.; Liu, E. (2015). Robus me hods o
assessing he accu acy o linea in e pola ed DEM. In . J.
Appl. Ea h Obs. Geoin ., 34, 198–206.
P oceedings o he In e na ional Ca og aphic Associa ion, 4, 2021.
30 h In e na ional Ca og aphic Con e ence (ICC 2021), 14–18 Decembe 2021, Flo ence, I aly. This con ibu ion unde wen
single-blind pee e iew based on submi ed abs ac s. h ps://doi.o g/10.5194/ica-p oc-4-11-2021 | © Au ho (s) 2021. CC BY 4.0 License.