GNavigia - Höhen glätten

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 franzö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ährend 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ättung der Da­ten. Wenn man nämlich die Höhen­li­ni­en der SRTM Da­ten und die OSM Kar­ten­da­ten zu­sam­men pro­ji­ziert, erhält man in kou­pier­tem Gelände ei­ne um die Höhen­li­nie me­an­drie­ren­de Tras­senführung, die ein ständi­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 Gelände ist die Höhen­dif­fe­renz übri­gens fast zu ver­nachlässi­gen, ei­ne Glättung na­he­zu über­flüssig. Das gilt auch, wenn man die Abstände 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 geglätt­tet wer­den müssen, und zwar so, dass die Stütz­punk­te für die La­ge nicht ver­lo­ren ge­hen, Die Höhen müssen ge­eig­net in­ter­po­liert wer­den. Al­les, was ich hier erzähle, gilt für Höhen, die in ge­rin­gen Abständen 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-Empfänger mit SIRF-StarIII/IV oder MTK-3318 Hard­wa­re er­mit­telt, ist un­gleich zu­verlässi­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öllig un­ge­eig­net ist, wo der Empfänger 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­lität «Höhen glätten»

Die Funk­tio­na­lität «Höhen glätten» er­reicht man, so­fern ge­nau ein Track se­lek­tiert ist, aus dem Menü via Be­ar­bei­ten/Track/Höhen glätten. 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ättung 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ückgängig 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 geglätte­ten Höhen.

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

Ab Ver­si­on  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ättung 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önnen Sie die Glättung mehr­fach auf­ru­fen, oh­ne die zu­vor durch­geführ­te rückgängig ma­chen zu müssen oder auf be­reits be­rech­ne­ten Wer­ten auf­zu­set­zen. Außer­dem können 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ättung 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 ändern, müssen Sie aber nicht von Hand in die GTD-Da­tei ein­grei­fen. Viel­mehr können Sie über den Menüpunkt Be­ar­bei­ten/Track­punk­t/Kor­ri­gie­re ur­sprüng­li­che Höhe Ände­run­gen vor­neh­men. Sinn­gemäß 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 älte­ren Ver­sio­nen Höhen in­ter­po­liert oder von Hand geändert ha­ben, wer­den die­se Höhen beim Ein­le­sen in der neu­en Ver­si­on als ur­sprüng­li­che Höhen ge­spei­chert. Die Mess­wer­te vor die­ser Ände­rung bringt Ih­nen nie­mand wie­der zurück.

Metho­den der Glättung

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ättung von Höhen auch nur sehr un­be­frie­di­gen­de Mo­del­le. An­de­rer­seits ist die Fra­ge natürlich er­laubt, was man mit der Glättung 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 dafür, dass die Glättung 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ättung von Höhen ist ja auch im­mer die, wie­viel man am En­de ver­schwin­den las­sen möchte.
*
GNavigia be­nutzt zur Glättung 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 erläutert, dass die Metho­de aus 4 Schrit­ten be­steht:
  • Lo­cal Smoo­thing (lo­ka­le Glättung) 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 verlä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ättend zu­gleich.
  • Berück­sich­ti­gung der Nach­bar­schafts­verhä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 Punkte des Col d'Ornon werden auch auf älteren Rechnern trotz der vielen Rechenschritte sehr schnell berechnet. Mit dem Verfahren nach Rokul-Léger, hier mit den Standardparametern angewendet, werden auch neuralgische Abschnitte (Serpentinen) gemeistert und sauber geglättet. Der Wert TotalUphill zeigt 907 Meter, was mit den aus der Karte ermittelten Daten schon recht gut übereinstimmt.

Die Methode nach Douglas-Peuker mit einem Grenzwert von 50 m. Die Glättung wirkt unnatürlich stark, kleinere Grenzwerte führen aber u. U. zu Gegenanstiegen, die auf zu große Ausreißer in den Höhendaten hindeuten. Extremwerte bleiben erhalten, ganz gleich ob richtig oder falsch.


Die Glättung durch Polynominterpolation ist ebenso aufwändig zu programmieren wie leicht falsch zu gebrauchen. Wer diese Form der Glättung wählt, sollte wissen, was er tut. Mathematisch wird ein Modell nach der Methode der kleinsten Quadrate verwendet, das wie folgt aufgestellt wird:

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

darin ist xi die Strecke vom Anfang des Tracks (respektive vom Anfang des Teilabschnitts) und yi die Höhe in diesem Punkt. Der größte Exponent (n) bestimmt den Grad des Polynoms. Aufgrund der extrem schnell steigenden Zahlenwerte ist das Polynom auf Grad 11 begrenzt.
*
Wegen der großen Anzahl der Höhen­werte und der geringen Anzahl an Unbe­kann­ten (Grad des Polynoms + 1) handelt es sich zwar formal um ein Aus­glei­chungs­pro­blem mit sehr vielen Über­bestim­mungen, die «Beobach­tungen», also die Höhen, sind aller­dings nicht normal­verteilt. Obgleich hier der Cholesky-Algo­rithmus zur Anwen­dung kommt, der auch schwierige Normal­gleichungs­systeme ohne Pivot-Suche nume­risch stabil invertieren kann, ufern die Potenzen zum Teil gewaltig aus. Es ist daher nicht ratsam, diese Berechnungen für lange Distanzen durchzuführen, ohne zuvor eine Siche­rungs­kopie der Daten zu machen! Hier kann selbst das Undo versagen.
*
Die Polynominterpolation sollte niemals auf den gesamten Track angewendet werden, sondern immer nur auf einen Teil davon. Sie können zwar astronomische Werte unter Länge des Polygonabschnitts eingeben, aber Sie sollten es hier bei maximal 10 km belassen. Ist der angegebene Wert größer als die Tracklänge, wird der ganze Track berechnet. Standard ist 5 km. Ein ungerader Polynomgrad hat sich als sinnvoll erwiesen, da er Steigungswechsel besser beschreibt. Der Überlappungsbereich kann höher gesetzt werden, es werden aber nicht die geglätteten Werte der Berechnung zuvor genommen, sondern die Rohdaten. Dennoch wirkt das Ergebnis auf den ersten Blick stetig; dass die erste Ableitung nicht mehr stetig ist, erkennt man spätestens am Höhendifferenzprofil. Restbereiche werden verteilt. Die Länge des Polygonabschnitts ist also meist etwas größer als angegeben, im Beispiel sind es tatsächlich 10700 m. Zu den Bereichen 2-4 kommt noch der Überlappungsbereich hinzu, sodass diese de facto 11 km lang sind. Für die 22 Kilometer der Nürburgring-Nordschleife würde man etwas kleinere Abschnitte wählen.


Die Polynominterpolation liefert deutlich gefälligere Werte als die Glättung nach Douglas-Peuker. Mir persönlich gefällt das Ergebnis für 9-10000-1000 noch besser als das hier dargestellte, aber für jedes Gelände ergibt sich eine bestmögliche Kombination von Werten.
*
Weitere Methoden sind angedacht, aber nicht in Vorbereitung.