GNavigia - Hö­hen glät­ten

Ge­dan­ken um ein schwie­ri­ges The­ma

Ich schrei­be prak­tisch nichts über nichts was ich nicht selbst ge­brau­chen könn­te. Vor über zwan­zig Jah­ren hat­te ich zu­sam­men mit mei­ner da­ma­li­gen Frau ei­ne aus­ge­spro­chen span­nen­de Rad­tour durch die fran­zö­si­schen Al­pen un­ter­nom­men. Beglei­tet von den Auf­zeich­nun­gen im Ta­ge­buch und mei­ner treu­en Olym­pus OM-2 konn­te ich vie­le Jah­re spä­ter ei­ne Ge­schich­te dar­über schrei­ben und wei­te­re 10 Jah­re spä­ter die Rad­tour auf der Grund­la­ge von OSM Da­ten mit­tels GNavigia di­gi­ta­li­sie­ren und da­bei Hö­hen aus SRTM-Daten aus ei­ner lo­ka­len Post­greSQL-Daten­bank in­ter­po­lie­ren. Groß­ar­tig. Aber: Die Hö­hen wa­ren ir­gend­wie selt­sam. Und wäh­rend der ers­te Tag über den Col d'Or­non und den un­gleich auf­re­gen­de­ren Col de la Croix der Fer (Ei­sen­kreuz­pass) von la Mure nach St. Jean de Mau­ri­enne hin­sicht­lich der Ta­ge­s­ki­lo­me­ter auf 1% ge­nau stimm­te, hat­te ich für den Col d'Or­non 800 Hö­hen­me­ter Stei­gung aus den groß­ar­ti­gen Kar­ten der Mi­che­lin 1:200000 Se­rie ab­ge­grif­fen - und über 1650 aus den di­gi­ta­li­sier­ten Da­ten be­rech­net.
*
Nach­dem ich zahl­rei­che Ski­ge­bie­te mit­tels GPS bis in die letz­te Ecke hin­ein ver­mes­sen ha­be, ist mir klar, dass nicht die äu­ßerst pri­mi­ti­ve In­ter­po­la­ti­on, be­schrie­ben auf ei­ner ei­ge­nen Sei­te, Schuld ist an den Dif­fe­ren­zen, son­dern die man­geln­de Glät­tung der Da­ten. Wenn man näm­lich die Hö­hen­li­ni­en der SRTM Da­ten und die OSM Kar­ten­da­ten zu­sam­men pro­ji­ziert, er­hält man in kou­pier­tem Ge­län­de ei­ne um die Hö­hen­li­nie me­an­drie­ren­de Tras­sen­füh­rung, die ein stän­di­ges Auf und Ab mit sich bringt. Die­ses wie­der­um sorgt für die gro­ße Dis­kre­panz zwi­schen Wunsch und Wirk­lich­keit. In ebe­nem Ge­län­de ist die Hö­hen­dif­fe­renz üb­ri­gens fast zu ver­nach­läs­si­gen, ei­ne Glät­tung na­he­zu über­flüs­sig. Das gilt auch, wenn man die Ab­stän­de zwi­schen zwei di­gi­ta­li­sier­ten Punk­ten groß hält, was den Cha­rak­ter ei­ner Pass­stra­ße aber eher igno­riert. Ei­ne ähn­li­chen Ef­fekt hat­te ich mit den Mess­da­ten der 4 Run­den Rad am Ring 2010.
*
Da­mit ist klar, dass die Hö­hen ge­glätt­tet wer­den müs­sen, und zwar so, dass die Stütz­punk­te für die La­ge nicht ver­lo­ren ge­hen, Die Hö­hen müs­sen ge­eig­net in­ter­po­liert wer­den. Al­les, was ich hier er­zäh­le, gilt für Hö­hen, die in ge­rin­gen Ab­stän­den di­gi­ta­li­siert oder auf­ge­zeich­net wur­den. In der letz­ten Zeit hat sich, ver­mut­lich durch das Mar­ke­ting sei­tens Gar­min und an­de­rer An­bie­ter, ei­ne un­se­li­ge Ge­mein­de von Ver­fech­tern der Theo­rie her­aus­ge­bil­det, dass die ba­ro­me­tri­sche Hö­hen­mes­sung ei­ne groß­ar­ti­ge Sa­che sei. Sie ist es nicht! Die Hö­he, die ein GPS-Emp­fän­ger mit SIRF-StarIII/IV oder MTK-3318 Hard­wa­re er­mit­telt, ist un­gleich zu­ver­läs­si­ger als ei­ne ba­ro­me­tri­sche Hö­hen­mes­sung. Der Luft­druck (und nichts an­de­res wird da ge­mes­sen), ist nicht ge­nau­er zu be­stim­men als auf 10 Me­ter. Zu­dem kann er bin­nen we­ni­ger Stun­den um bis zu 100 Me­ter schwan­ken. Ich ha­be, das ha­be ich schon auf an­de­ren Sei­ten be­kannt, mei­nen Gar­min Vis­ta HCx wie­der ver­kauft, weil die ba­ro­me­tri­sche Hö­hen­mes­sung für all je­ne Zwe­cke völ­lig un­ge­eig­net ist, wo der Emp­fän­ger freie Sicht auf Sa­tel­li­ten hat, ins­be­son­de­re in baum­lo­sen Ski­ge­bie­ten. Wenn sie dar­über hin­aus nicht ab­schalt­bar ist und sich das Gerät nur beim Ein­schal­ten selbst syn­chro­ni­siert, kommt das Gerät weg!

Funk­tio­na­li­tät «Hö­hen glät­ten»

Die Funk­tio­na­li­tät «Hö­hen glät­ten» er­reicht man, so­fern ge­nau ein Track se­lek­tiert ist, aus dem Me­nü via Be­ar­bei­ten/Track/Hö­hen glät­ten. Es exis­tiert ein Short­cut für die­se Ak­ti­on. Vor dem Start er­scheint ein Dia­log, der Art und Pa­ra­me­ter der Glät­tung ab­fragt. Die Hö­hen des Tracks sind am En­de der Be­rech­nung mit den neu­en Wer­ten über­schrie­ben. Vor der An­wen­dung ei­ner an­de­ren Funk­ti­on muss da­her die Ak­ti­on rück­gän­gig ge­macht wer­den (Con­trol+Z oder Strg+Z). Sonst ar­bei­tet die nächs­te Funk­ti­on auf den be­reits ge­glät­te­ten Hö­hen.

Funk­tio­na­li­tät «Ur­sprüng­li­che Hö­hen»

Ab Ver­sion  2.12.12.92 spei­chert GNavigia die ori­gi­na­len, ur­sprüng­li­chen Hö­hen («genu­i­ne heights»); dar­un­ter ver­steht das Pro­gramm die al­ler­ers­te Hö­he, die für ei­nen Track­punkt ge­setzt wird. Wenn Sie bei der Glät­tung der Hö­hen an­ge­ben, dass die ur­sprüng­li­chen Hö­hen be­nutzt wer­den sol­len, wird auf die­sen ge­ar­bei­tet. Da­durch kön­nen Sie die Glät­tung mehr­fach auf­ru­fen, oh­ne die zu­vor durch­ge­führ­te rück­gän­gig ma­chen zu müs­sen oder auf be­reits be­rech­ne­ten Wer­ten auf­zu­set­zen. Au­ßer­dem kön­nen Sie nun in al­ler Ru­he dar­auf war­ten, dass Ih­nen GNavigia ei­nes Ta­ges ei­ne bes­se­re Metho­de zur Glät­tung an­bie­tet. Die ori­gi­na­len Da­ten blei­ben prin­zi­pi­ell auf im­mer er­hal­ten. Um die­se Wer­te, die ja grob falsch sein könn­ten, zu än­dern, müs­sen Sie aber nicht von Hand in die GTD-Da­tei ein­grei­fen. Viel­mehr kön­nen Sie über den Menü­punkt Be­ar­bei­ten/Track­punkt/Kor­ri­gie­re ur­sprüng­li­che Hö­he Än­de­run­gen vor­neh­men. Sinn­ge­mäß gilt das auch für Weg­punk­te.
Über den Menü­punkt Be­ar­bei­ten/Track/Ur­sprüng­li­che Hö­hen wie­der­her­stel­len wird ein Track oder ei­ne Lis­te von Tracks hin­sicht­lich der Hö­hen wie­der in den Aus­gangs­zu­stand ver­setzt. Sind meh­re­re Tracks se­lek­tiert, er­folgt zu­vor ei­ne Si­cher­heits­ab­fra­ge.
Al­ler­dings soll­ten Sie be­ach­ten: Wenn Sie in äl­te­ren Ver­sio­nen Hö­hen in­ter­po­liert oder von Hand ge­än­dert ha­ben, wer­den die­se Hö­hen beim Ein­le­sen in der neu­en Ver­sion als ur­sprüng­li­che Hö­hen ge­spei­chert. Die Mess­wer­te vor die­ser Än­de­rung bringt Ih­nen nie­mand wie­der zu­rück.

Metho­den der Glät­tung

So­wohl be­ob­ach­te­te als auch auf­ge­zeich­ne­te Hö­hen sind mit sys­te­ma­ti­schen Feh­lern be­haf­tet und stel­len kei­ne nor­mal­ver­teil­ten Beo­b­ach­tun­gen im Sin­ne der Sta­tis­tik dar. Da­her gibt es für die Glät­tung von Hö­hen auch nur sehr un­be­frie­di­gen­de Mo­del­le. An­de­rer­seits ist die Fra­ge na­tür­lich er­laubt, was man mit der Glät­tung er­rei­chen will. Und das ent­schei­det man doch am Bes­ten im «An­ge­sicht der Rei­se­rou­te». Dies ist ein Grund da­für, dass die Glät­tung der Hö­hen erst so spät Ein­zug in die­ses Pro­gramm ge­hal­ten hat. Denn da­zu konn­te man sich im­mer schon der Stei­gungs­bil­der be­die­nen, Punk­te gro­ßer Gra­di­en­ten ankli­cken und die man­gel­haf­te Hö­he in­ter­po­lie­ren las­sen. Die Fra­ge der Glät­tung von Hö­hen ist ja auch im­mer die, wie­viel man am En­de ver­schwin­den las­sen möch­te.
*
GNavigia be­nutzt zur Glät­tung der Hö­hen be­vor­zugt die von  Ro­kul und Lé­ger an­ge­ge­be­ne, stu­fen­wei­se und ite­ra­tiv vor­ge­hen­de Metho­de. An­ders als die Metho­de nach Dou­glas-Peu­ker blei­ben die Ex­trem­wer­te da­bei nicht er­hal­ten. Sie ist da­zu ge­eig­net, gro­be Feh­ler zu eli­mi­nie­ren. Oh­ne all­zu in­ten­siv auf die ma­the­ma­ti­schen  Grund­la­gen ein­zu­ge­hen, sei kurz er­läu­tert, dass die Metho­de aus 4 Schrit­ten be­steht:
  • Lo­cal Smoo­thing (lo­ka­le Glät­tung) zur Be­gren­zung des Gra­di­en­ten auf ei­nen fes­ten Ma­xi­mal­wert. Im Pa­ra­me­ter­dia­log wird die­ser in den Fel­dern Grenz­wert Gra­di­ent und Ite­ra­tio­nen ab­ge­legt.
  • Mit­te­lung der ver­bes­ser­ten Gra­di­en­ten. Die­se er­fasst nicht nur die im Feld Zu mit­teln­de Gra­di­en­ten an­ge­ge­be­ne An­zahl an Gra­di­en­ten, son­dern nutzt für die zwei­te und al­le nach­fol­gen­den Be­rech­nun­gen die Hälf­te der zu­vor ge­mit­tel­ten Gra­di­en­ten, so­dass der Über­gang zwi­schen den Ab­schnit­ten eher sanft ver­läuft.
  • Lo­ka­le li­nea­re In­ter­po­la­ti­on, die­ser Durch­gang in­ter­po­liert ite­ra­tiv ver­blei­ben­de Gra­di­en­ten, die den Grenz­wert über­stei­gen. Au­ßer­dem wer­den al­le Punk­te er­fasst, die ei­nen al­ter­nie­ren­den Gra­di­en­ten auf­wei­sen. Die­ser Schritt ist in be­son­de­rem Ma­ße wert­er­hal­tend und glät­tend zu­gleich.
  • Berück­sich­ti­gung der Nach­bar­schafts­ver­hält­nis­se. Die in an­ge­ge­be­ner Nä­he lie­gen­den Punk­te wer­den in der Hö­he ge­mit­telt.
Die 590 Punk­te des Col d'Or­non wer­den auch auf äl­te­ren Rech­nern trotz der vie­len Re­chen­schrit­te sehr schnell be­rech­net. Mit dem Ver­fah­ren nach Ro­kul-Léger, hier mit den Stan­dard­pa­ra­me­tern an­ge­wen­det, wer­den auch neur­al­gi­sche Ab­schnit­te (Ser­pen­ti­nen) ge­meis­tert und sau­ber ge­glät­tet. Der Wert To­talU­phill zeigt 907 Me­ter, was mit den aus der Kar­te er­mit­tel­ten Da­ten schon recht gut über­ein­stimmt.

Die Metho­de nach Dou­glas-Peu­ker mit ei­nem Grenz­wert von 50 m. Die Glät­tung wirkt un­na­tür­lich stark, klei­ne­re Grenz­wer­te füh­ren aber u. U. zu Ge­gen­an­stie­gen, die auf zu gro­ße Aus­rei­ßer in den Hö­hen­da­ten hin­deu­ten. Ex­trem­wer­te blei­ben er­hal­ten, ganz gleich ob rich­tig oder falsch.


Die Glät­tung durch Po­ly­no­min­ter­po­la­ti­on ist eben­so auf­wän­dig zu pro­gram­mie­ren wie leicht falsch zu ge­brau­chen. Wer die­se Form der Glät­tung wählt, soll­te wis­sen, was er tut. Ma­the­ma­tisch wird ein Mo­dell nach der Metho­de der kleins­ten Qua­dra­te ver­wen­det, das wie folgt auf­ge­stellt wird:

  yi = a0 + a1xi1 + a2xi2 + a3xi3 + ... + anxin ,

dar­in ist xi die Stre­cke vom An­fang des Tracks (re­spek­ti­ve vom An­fang des Teil­ab­schnitts) und yi die Hö­he in die­sem Punkt. Der größ­te Ex­po­nent (n) be­stimmt den Grad des Po­ly­noms. Auf­grund der ex­trem schnell stei­gen­den Zah­len­wer­te ist das Po­ly­nom auf Grad 11 be­grenzt.
*
We­gen der gro­ßen An­zahl der Hö­hen­wer­te und der ge­rin­gen An­zahl an Un­be­kann­ten (Grad des Po­ly­noms + 1) han­delt es sich zwar for­mal um ein Aus­glei­chungs­pro­blem mit sehr vie­len Über­be­stim­mun­gen, die «Beo­b­ach­tun­gen», al­so die Hö­hen, sind al­ler­dings nicht nor­mal­ver­teilt. Ob­gleich hier der Cho­lesky-Algo­rith­mus zur An­wen­dung kommt, der auch schwie­ri­ge Nor­mal­glei­chungs­sys­te­me oh­ne Pi­vot-Suche nu­me­risch sta­bil in­ver­tie­ren kann, ufern die Po­ten­zen zum Teil ge­wal­tig aus. Es ist da­her nicht rat­sam, die­se Be­rech­nun­gen für lan­ge Di­stan­zen durch­zu­füh­ren, oh­ne zu­vor ei­ne Si­che­rungs­ko­pie der Da­ten zu ma­chen! Hier kann selbst das Un­do ver­sa­gen.
*
Die Po­ly­no­min­ter­po­la­ti­on soll­te nie­mals auf den ge­sam­ten Track an­ge­wen­det wer­den, son­dern im­mer nur auf ei­nen Teil da­von. Sie kön­nen zwar astro­no­mi­sche Wer­te un­ter Län­ge des Po­ly­go­n­ab­schnitts ein­ge­ben, aber Sie soll­ten es hier bei ma­xi­mal 10 km be­las­sen. Ist der an­ge­ge­be­ne Wert grö­ßer als die Track­län­ge, wird der gan­ze Track be­rech­net. Stan­dard ist 5 km. Ein un­ge­ra­der Po­ly­nom­grad hat sich als sinn­voll er­wie­sen, da er Stei­gungs­wech­sel bes­ser be­schreibt. Der Über­lap­pungs­be­reich kann hö­her ge­setzt wer­den, es wer­den aber nicht die ge­glät­te­ten Wer­te der Be­rech­nung zu­vor ge­nom­men, son­dern die Roh­da­ten. Den­noch wirkt das Er­geb­nis auf den ers­ten Blick ste­tig; dass die ers­te Ablei­tung nicht mehr ste­tig ist, er­kennt man spä­tes­tens am Hö­hen­dif­fe­renz­pro­fil. Rest­be­rei­che wer­den ver­teilt. Die Län­ge des Po­ly­go­n­ab­schnitts ist al­so meist et­was grö­ßer als an­ge­ge­ben, im Bei­spiel sind es tat­säch­lich 10700 m. Zu den Be­rei­chen 2-4 kommt noch der Über­lap­pungs­be­reich hin­zu, so­dass die­se de fac­to 11 km lang sind. Für die 22 Ki­lo­me­ter der Nür­burg­ring-Nord­schlei­fe wür­de man et­was klei­ne­re Ab­schnit­te wäh­len.


Die Po­ly­no­min­ter­po­la­ti­on lie­fert deut­lich ge­fäl­li­ge­re Wer­te als die Glät­tung nach Dou­glas-Peu­ker. Mir per­sön­lich ge­fällt das Er­geb­nis für 9-10000-1000 noch bes­ser als das hier dar­ge­stell­te, aber für je­des Ge­län­de er­gibt sich ei­ne best­mög­li­che Kom­bi­na­ti­on von Wer­ten.
*
Wei­te­re Metho­den sind an­ge­dacht, aber nicht in Vor­be­rei­tung.