GPS-Tracks glätten mit einem Faktorgraphen
Wie walker GPS-Tracks auf dem Handy bereinigt: ein selbst geschriebener Faktorgraph mit Schritten, Barometer und Satellitenrohdaten, und was er gebracht hat.
· Malik · 23 Min. Lesezeit
Mit den Rohdaten der Satelliten bereinigt, kam eine Radtour von 1 h 16 min auf 6,98 km. Ohne diese Rohdaten bereinigt waren es 6,19 km. Der rohe Track, so wie er aus dem Chip kam, hatte 6,39 km. Die Bereinigung sollte Rauschen herausnehmen und hatte den Track länger gemacht als den rohen.
Bereinigt hat diese Tour walker, die App für Spaziergänge, Wanderungen und Radtouren, die ich für Android entwickle. Sie behält alles, was sie weiß, auf dem Handy und muss deshalb auch jede Zahl, die sie anzeigt, dort ausrechnen. Alles, was sie zählt, kommt aus dem bereinigten Track: Verlauf, Statistik, Ziele und Abzeichen. Die Bereinigung muss also stimmen, hübsch aussehen reicht nicht. Die Distanz, die du siehst, soll zur Strecke passen, und das Rauschen des GPS soll keine Höhenmeter erzeugen. Angefangen hat sie als Kalman-Glätter (ein Glätter, englisch smoother, schätzt jeden Punkt aus den Messungen davor und danach). Daraus wurde ein kleiner Faktorgraph mit einem Solver, den ich selbst geschrieben habe, und die Radtour war sein erster echter Test. In diesem Beitrag steht die Mathematik hinter dem Graphen. Die genaue Abstimmung bleibt walkers Sache.
Warum ein roher Track lügt
Die GPS-Punkte eines Handys rauschen, und die Fehler summieren sich. Zittern macht aus einer geraden Linie einen längeren Zickzackkurs. Ausreißer setzen einzelne GPS-Punkte Dutzende Meter daneben. Die GPS-Höhe weicht um 5–15 m ab, und weil die Höhenmeter jedes Stück bergauf aufaddieren, zählt auch das Rauschen als Anstieg. GPS-Strecke zu lang? Warum der Track mehr misst zeigt, was das für die Zahlen bedeutet, die du siehst. Auch diese Radtour kommt dort vor.
Der schlimmste Fall, der mir begegnet ist, heißt Static Hold. Manche Chips frieren die Position ein und melden 0 m/s, während du weitergehst. Mein Testhandy, ein OnePlus 7 Pro, hat das auf einem Spaziergang gemacht. Der GPS-Punkt blieb stehen und sprang dann nach vorn, um aufzuholen. Eine naive Bereinigung sieht darin einen Stopp und danach einen Teleport.
Erster Versuch: ein Kalman-Glätter mit Doppler
Vor dem Graphen bestand die Bereinigung aus einem Kalman-Filter mit konstanter Geschwindigkeit, der vorwärts lief, und einem Rauch-Tung-Striebel-Durchlauf rückwärts. Ost und Nord waren dabei zwei getrennte Achsen. Neben der Position verarbeitete der Filter die Doppler-Geschwindigkeit des Chips, berechnet aus Tempo und Richtung jedes GPS-Punkts. Die Höhe hatte einen eigenen Glätter.
Dazu kamen Regeln für Ausreißer, unmögliche Sprünge und Stopps. Am Static Hold scheiterte das Ganze gleich doppelt. Der eingefrorene GPS-Punkt wurde zu einem sehr sicheren „Geschwindigkeit ist null“, und die Stopp-Regel nagelte ihn fest. Der bereinigte Track zeigte einen Stopp und einen Sprung, wo ich gleichmäßig gegangen war. Der Schrittzähler wusste es besser, aber der Filter hatte keine Möglichkeit, auf ihn zu hören.
Warum ein Graph
Für ein lineares Modell mit gaußschem Rauschen liefern ein Faktorgraph und ein Kalman-Filter mit RTS-Durchlauf dasselbe Ergebnis. Beide lösen ein Kleinste-Quadrate-Problem über den ganzen Abschnitt. Der Vorteil liegt in dem, was sich mit einem Kalman-Filter nur schwer ausdrücken lässt. Mit einer robusten Verlustfunktion gewichtet der Schätzer einen Ausreißer selbst herunter, und niemand muss vorher einen Schwellwert festlegen. Ein nichtlinearer Faktor kann am Betrag der Geschwindigkeit ansetzen, und genau den misst das Tempo aus den Schritten. Mit einem linearen Faktor geht das nicht. Unbekannte, die für einen ganzen Abschnitt gelten, etwa die Schrittlänge oder Offset und Drift des Barometers, lassen sich zusammen mit dem Track bestimmen. Und wo eine Messung falsch ist, lässt sie sich abschalten: Ein gehaltener GPS-Punkt bekommt dann einfach keine.
Eine gute Einführung ist Factor Graphs for Robot Perception von Dellaert und Kaess. Den Solver habe ich selbst geschrieben. Das lohnte sich nur, weil dieser Graph eine ganz besondere Form hat.
Was im Graphen steckt
walker baut den Graphen für jeden Abschnitt zwischen zwei Pausen, damit nichts über eine Pause hinweg geglättet wird.
Die Zustände und die Kosten
Jeder behaltene GPS-Punkt bekommt einen horizontalen Zustand in lokalen Metern, : Ost und Nord, gezählt ab dem ersten GPS-Punkt des Abschnitts, und die Geschwindigkeit in beiden Richtungen. Höhe und Steigrate jedes GPS-Punkts stehen in einer eigenen, vertikalen Kette. Die beiden Ketten haben keinen gemeinsamen Faktor und werden deshalb getrennt gelöst. Neben den Zuständen stehen die globalen Unbekannten, ein Satz pro Abschnitt: in der Ebene die Schrittlänge, für die Höhe Offset und Drift des Barometers.
Jede Messung wird zu einem Faktor, also einem Term, der angibt, wie weit die Zustände von der Messung abweichen. Der Solver sucht die Zustände und globalen Unbekannten, bei denen die Summe aller Faktoren am kleinsten ist:
steht für alle Zustände der Kette und für die globalen Unbekannten. Jeder Faktor hat ein Residuum , die Differenz zwischen seiner Messung und dem, was die Zustände vorhersagen. Dazu hat er eine Kovarianz , die angibt, wie weit er danebenliegen darf. ist die Länge des Residuums, gemessen in Einheiten seines Rauschens. heißt also eine Standardabweichung, ganz gleich, was der Faktor misst. ist die Verlustfunktion des Faktors. Für die meisten Faktoren gelten einfache kleinste Quadrate, . Faktoren, die Ausreißer abbekommen, haben eine robuste Verlustfunktion, zu der ich weiter unten komme. Für den Track heißt das: Kein GPS-Punkt wird beim Wort genommen. Jeder zieht so stark an der Lösung, wie er sich sicher war, und alle anderen Messungen ziehen dagegen.
Bewegung zwischen Nachbarn
Zusammengehalten wird die Kette vom Bewegungsfaktor zwischen benachbarten Zuständen. Er nimmt an, dass du dich von einem GPS-Punkt zum nächsten mit konstanter Geschwindigkeit bewegt hast, und bestraft jede Änderung:
schreibt Zustand mit konstanter Geschwindigkeit um fort, die Zeit von GPS-Punkt bis GPS-Punkt . ist die 2×2-Einheitsmatrix, und wiederholt den Block für Ost und Nord, die unabhängig sind und demselben Modell folgen. ist die Kovarianz des Faktors, also das von oben, nach dem Lehrbuchmodell, das die Beschleunigung als kontinuierliches weißes Rauschen ansetzt. ist die spektrale Leistungsdichte der Beschleunigung: In der Zeit wächst die Varianz der Geschwindigkeit um , den Diagonaleintrag der Geschwindigkeit in . walker wählt danach, wie schnell sich das Tempo zu Fuß oder auf dem Rad ändern kann. Je größer , desto stärker darf sich der Track zwischen zwei GPS-Punkten krümmen.
Der alte Filter setzte dieses Rauschen als konstante Beschleunigung je Intervall an, mit der Varianz : . Diese Matrix ist das dyadische Produkt eines einzigen Vektors und hat deshalb Rang 1. Einen Kalman-Filter stört das nicht, er addiert sie nur. Ein Graph braucht aber ihre Inverse. Der Block des Modells mit weißem Rauschen hat die Determinante . Sie ist nie null, der Block ist also invertierbar.
Die Messungen
Fünf Arten von Messungen ziehen an den Zuständen.
Die GPS-Position ist ein robuster Faktor. Ihr Gewicht kommt aus der Genauigkeit, die der GPS-Punkt meldet, und walker legt diese Angabe vorsichtig aus.
Die Doppler-Geschwindigkeit ist ebenfalls ein robuster Faktor. Ihr Fehler zerfällt in einen Anteil längs und einen quer zur Bewegungsrichtung. Längs gilt die Geschwindigkeitsgenauigkeit, die der Chip meldet, quer die Genauigkeit der Richtung, und dieser Querfehler wächst mit dem Tempo. So entsteht eine volle 2×2-Kovarianz. Der alte Glätter mit seinen zwei getrennten Achsen konnte davon nur die Diagonale verwenden, der Graph verwendet die ganze Matrix.
Das Tempo aus den Schritten gilt für GPS-Punkte, an denen du gehst. Es ist Schrittlänge mal Schrittfrequenz, mit einer gewissen Toleranz. Der Faktor ist nichtlinear, weil er am Betrag der Geschwindigkeit ansetzt. Die Schrittlänge ist eine globale Unbekannte mit einem schwachen Prior, deshalb lernt der Graph sie dort, wo die Doppler-Messung gut ist.
Die Nullgeschwindigkeit gilt nur bei einem echten Stopp, also bei einigen langsamen GPS-Punkten in Folge, während die Schritte zeigen, dass du nicht gehst. Außerdem gilt sie nur ohne Satelliten, denn die Satelliten messen die Geschwindigkeit selbst.
Die Höhe kommt als robuster Faktor vom GPS und, wenn das Handy eines hat, vom Barometer. Über die internationale Standardatmosphäre wird aus dem Luftdruck eine Höhe. Ein Wetterwechsel verschiebt sie aber um einige Meter, deshalb traut walker nur ihren Änderungen. Offset und Drift des Barometers sind globale Unbekannte, verankert an der GPS-Höhe.
Eine Unbekannte des Abschnitts, die keine Messung berührt, ändert am Ergebnis nichts. So reicht eine Form des Graphen für jeden Track, ob mit oder ohne Schritte und Luftdruck.
Der gehaltene GPS-Punkt
Mit diesen Faktoren ist der Static Hold leicht zu behandeln. Meldet ein GPS-Punkt Stillstand, während der Schrittzähler Gehen meldet, gilt er als gehalten. Er bekommt weder einen Positions- noch einen Doppler-Faktor, wie der vierte Zustand in Abbildung 1. Die Bewegungsfaktoren tragen den Track über diese Stelle und verteilen den Aufholsprung auf die Zeit, in der der Punkt stand. Auf der Karte bleibt ein gleichmäßiger Spaziergang eine gleichmäßige Linie, ohne Sprung und ohne einen Stopp, den du nie gemacht hast.
Huber statt Ausreißerregeln
Die Ausreißerregeln habe ich gestrichen. Stattdessen haben Position, Doppler und GPS-Höhe eine Huber-Verlustfunktion. Sie zählt ein Residuum voll, solange es klein ist, und nur noch linear, sobald es eine Schwelle überschreitet. In walkers Skalierung lautet sie für eine Schwelle
ist das normierte Residuum des Faktors von oben. Bis zu Standardabweichungen zählt ein Faktor voll. Darüber zieht er nur noch so stark wie ein Residuum von , egal wie weit er danebenliegt. Das ist das Doppelte der üblichen Huber-Funktion. Am Ort des Minimums ändert das nichts. ist das Gewicht, mit dem der Solver rechnet, denn selbst wertet er nie aus. Für den Track heißt das: Ein Ausreißer braucht keine eigene Regel mehr. Er zieht so stark wie ein Residuum an der Schwelle, und wo der Track verläuft, entscheiden die anderen Messungen.
Für Positionen gibt es eine zusätzliche Regel: Liegt eine Position weit jenseits jedes ehrlichen Fehlers, bleibt sie ganz draußen. Dank dieser Grenze kann walkers GPS-Diagnose einen GPS-Punkt weiterhin als ausgelassen ausweisen, und die alten Tests für Ausreißer und zu hohes Tempo laufen unverändert durch. Ich hatte damit gerechnet, eine Cauchy-Funktion zu brauchen. Die Tests haben nie danach verlangt.
Der Solver: Levenberg-Marquardt auf einer Pfeilmatrix
Jeder Zustand hängt nur an seinen Nachbarn und an ein paar globalen Unbekannten. Weil das System so dünn besetzt ist, ist der Solver billig. Für einen Abschnitt aus Zuständen sieht das System für einen Schritt so aus:
ist der Block von Zustand mit sich selbst, für einen Zustand aus Zahlen. verbindet Zustand mit Zustand , und nur Faktoren zwischen Nachbarn tragen dazu bei. verbindet Zustand mit den globalen Unbekannten, und ist deren -Block. ist der Schritt für Zustand , der Schritt für die globalen Unbekannten, und die sind die rechte Seite. Alles andere ist null, und das ist der ganze Trick: Die Matrix ist blocktridiagonal mit einem Rand, eine Pfeilmatrix.
Der Solver eliminiert die Zustände einen nach dem anderen. Übrig bleibt ein kleines System, das nur noch die globalen Unbekannten enthält: ihr Schur-Komplement. Der Solver löst es und rechnet danach die Zustände rückwärts aus. Pro Zustand löst er ein paar kleine Systeme mit Cholesky. Nirgends entsteht eine dichte Matrix, und walker braucht kein Crate für lineare Algebra. Der Solver ist von Hand in Rust geschrieben, wie fast alles in walker. Ein Abschnitt kostet , linear in . Eine dichte Lösung für eine Stunde mit einem GPS-Punkt pro Sekunde läge bei , bei 14.400 Unbekannten etwa 10¹² Operationen.
Weil nicht alle Faktoren linear sind, läuft das Ganze in einer Levenberg-Marquardt-Schleife. Jede Iteration linearisiert alle Faktoren am aktuellen Stand der Zustände und macht einen gedämpften Schritt. Erhöht der Schritt die Kosten nicht, wird er übernommen, und die Dämpfung sinkt. Erhöht er sie, wird er verworfen und mit stärkerer Dämpfung wiederholt. Numerical Optimization von Nocedal und Wright beschreibt die Trust-Region-Variante. Sie vergleicht, wie stark die Kosten tatsächlich sinken, mit dem Rückgang, den das lineare Modell vorhergesagt hat. walker fragt nur, ob die Kosten gesunken sind. Das ist die einfachste Regel, die funktioniert.
Mit robusten Gewichten hängt die Summe von ihrer eigenen Lösung ab. Deshalb steckt das Ganze in einer iterativ neu gewichteten Kleinste-Quadrate-Schätzung. In jeder Runde wird jedes robuste Gewicht aus seinem Residuum berechnet, dann löst der Solver mit festen Gewichten. Das wiederholt sich, bis sich die Gewichte nicht mehr ändern. Auch ein ausgelassener Faktor wird in der nächsten Runde wieder geprüft. So kann ein früh verworfener GPS-Punkt zurückkommen, sobald sich der Track auf ihn zubewegt hat.
Robuste Verlustfunktionen machen das Problem nichtkonvex, also kommt es auf den Startwert an. Den liefert seitdem der alte Kalman-Glätter. Sein Ergebnis ist eine Kleinste-Quadrate-Lösung, und die erste Runde muss nur noch die Ausreißer herausnehmen.
Was die Tests zeigten
Zuerst die Gegenprobe: Mit einfachen gaußschen Verlustfunktionen trifft der Graph die Positionen und Höhen des alten Glätters auf einen Millimeter genau. Danach kamen synthetische Tests:
- Einen Static Hold im Gehtempo überbrückt der Track auf 5 m genau, und die Distanz stimmt auf 5 %. Ohne Schritte bleibt es ein Stopp.
- Bei einem Anstieg von 100 m mit verrauschter und systematisch verschobener GPS-Höhe weichen die gezählten Höhenmeter höchstens 10 % vom Wert aus den wahren Höhen ab. Sie liegen mindestens doppelt so nah daran wie ohne Barometer.
Abbildung 3 zeigt die Idee des ersten Tests in einer Dimension.
Das sind Tests mit erfundenen Tracks, keine Messungen im Gelände. Mein Handy hat kein Barometer, also habe ich diesen Teil nur mit synthetischen Hügeln und einem simulierten Barometer geprüft.
Die Radtour, die länger wurde
Später kamen die rohen GNSS-Messungen des Handys in den Graphen. Ihnen ist ein eigener Beitrag gewidmet. Der Zustand bekam Uhrenfehler und Uhrendrift des Empfängers dazu, der Bias jedes Signals gegenüber GPS L1 wurde zur globalen Unbekannten, und die Pfeilform blieb erhalten. Auf meinem OnePlus liegt BeiDou bei −459 m, GLONASS bei +1.141 m und GPS L5 bei −2.350 m. Exakt gerechnet wird jede Position bei jeder Auswertung aus lokalen Metern in erdzentrierte Koordinaten umgerechnet. So dauerte die Bereinigung einer Stunde mit Satelliten 13-mal so lange. walker linearisiert die Umrechnung deshalb einmal pro Epoche. Das ist unbedenklich: Ein Knoten verschiebt sich beim Lösen um einige Meter, und auf 100 m macht die Erdkrümmung weniger als einen Millimeter aus.
Dann kam die Radtour vom Anfang, der erste echte Test: 1 h 16 min aufgezeichnete GPS-Punkte aus einer längeren Fahrt mit einem Stopp von über zwei Stunden. Mit Satelliten bereinigt 6,98 km. Ohne sie 6,19 km. Roh 6,39 km.
Ein Diagnosewerkzeug schlüsselte die zusätzlichen 793 m auf. Nur 62 m davon entstanden, während der Empfänger stand. An den Stopps lag es also nicht. Schuld waren die Gewichte. Jede Pseudoentfernung trug das σ, das der Chip selbst angab, ein paar Meter, und galt Sekunde für Sekunde als unabhängig. Mehrwegefehler halten aber Sekunden bis Minuten an. So zerrte ein Dutzend Pseudoentfernungen pro Epoche jeden Knoten hin und her. Ich habe zwei Dinge geändert:
- eine Untergrenze für das σ jeder Pseudoentfernung, die steigt, wenn das Signal schwächer wird;
- eine Aufweitung, mit der eine Folge von Epochen pro Korrelationszeit (einige zehn Sekunden) nur als eine unabhängige Pseudoentfernung zählt.
| Gewicht der Pseudoentfernungen | Bereinigte Distanz | GPS-Punkte um mehr als 10 m verschoben |
|---|---|---|
| σ des Chips, feste Untergrenze | 6.978 m | 621 |
| nur Untergrenze nach Signalstärke | 6.954 m | 642 |
| nur Korrelationszeit | 6.389 m | 168 |
| beides, dazu die Stopps des Chips gehalten | 6.223 m | 50 |
In der letzten Zeile hält walker außerdem einen Stopp fest, den der Chip meldet, wenn auch die gelöste Geschwindigkeit dort einen Stopp zeigt. Ohne Satelliten: 6.185 m und 78 verschobene GPS-Punkte. Aus 6,98 km wurden so 6,22 km. Der Track ist damit wieder kürzer als der rohe, wie es sich für einen bereinigten Track gehört.
Als ich alle Satellitensysteme und Frequenzbänder dazunahm, die das Handy misst, etwa 25–30 Signale pro Epoche, kam die Falle in neuer Gestalt zurück. Die Umgebung lenkt alle Signale einer Epoche zugleich ab. Die Position, die sie ergeben, liegt dann um Meter daneben, ganz gleich, wie viele Satelliten übereinstimmen. Seitdem zählen die Pseudoentfernungen einer Epoche zusammen nur wie einige wenige unabhängige, und ihre Änderungsraten ebenso.
Beide Aufweitungen beruhen auf derselben Tatsache: Information, also eins durch die Varianz, addiert sich. Wird jede Pseudoentfernung einer Epoche um deren Anzahl aufgeweitet, bleibt ihre gemeinsame Information die von wenigen unabhängigen, egal wie viele Satelliten am Himmel stehen. Dasselbe gilt für die Aufweitung über die Zeit: Die Pseudoentfernungen eines Satelliten innerhalb einer Korrelationszeit zählen zusammen als eine. Ein vollständigerer Schätzer würde die Korrelation modellieren, mit einem Gauß-Markov-Zustand pro Satellit oder einer vollen Kovarianz pro Epoche. walker weitet nur jeden Faktor auf. So bleibt jeder Faktor skalar, und die Matrix behält ihre Pfeilform.
Bewerten ohne Referenzweg
Außerdem stimme ich nicht mehr auf die Länge ab. Zwei Gütemaße kommen ohne Referenz aus. Das erste misst, wie weit die bereinigten GPS-Punkte von den kartierten Wegen in den Kartenregionen auf dem Handy entfernt liegen, als Median und 90. Perzentil. Das zweite bereinigt den Track mehrmals und lässt dabei jedes Mal eine Gruppe von Satelliten weg. Dann vergleicht es deren Pseudoentfernungen mit den Orten, an die der Track die GPS-Punkte gelegt hat, und bildet ein robustes σ der Restfehler. Die Karte erkennt Fehler quer zum Weg, die zurückgehaltenen Satelliten Fehler längs des Wegs.
Auf der Radtour lagen die GPS-Punkte ohne Satelliten 2,37 m (Median) und 5,98 m (p90) von den Wegen entfernt, mit allen Signalen 2,24 m und 5,34 m. Das robuste σ der zurückgehaltenen Pseudoentfernungen ging von 7,61 m auf 7,51 m zurück. Heute kommt die Tour nach der Bereinigung auf 6,25 km, das über die Zeit aufsummierte Tempo des Chips auf 6,13 km.
Der Gewinn ist bescheiden. Die Satelliten stutzen vor allem die schlechten Ausläufer der Verteilung, also die Stellen, an denen ein Track am weitesten vom Weg abkommt. Wo der Chip gut ist, liegt sein GPS-Punkt ohnehin etwa so nah am Weg. Auf einer von drei kürzeren Aufzeichnungen wurde der Median etwas schlechter (von 2,63 m auf 2,87 m), während sich das p90 verbesserte. Auch die Siegerlösung der Google Smartphone Decimeter Challenge 2021 nutzte einen Faktorgraphen und kam auf 1,62 m, allerdings mit Trägerphase und mit Pseudoentfernungen, die mit Daten von Referenzstationen korrigiert waren. Mein Handy liefert keine gültige Trägerphase, und walker nutzt keinen Korrekturdienst.
Ein UKF für die zugeordneten Wege
walker ordnet Tracks auf dem Handy außerdem Wegen aus OpenStreetMap zu. Dafür nutzt die App ein Hidden-Markov-Modell und den Viterbi-Algorithmus, der die wahrscheinlichste Folge von Wegen findet. Die Projektion der Messpunkte auf die gewählten Wege zittert, und an einer Ecke kann sie rückwärts springen. Deshalb läuft auf jedem zugeordneten Teilstück ein Unscented-Kalman-Filter (UKF) entlang der zugeordneten Linie. Sein Zustand besteht aus der Strecke entlang der Linie, dem Tempo entlang der Linie und einem Versatz quer dazu. Der Versatz fängt einen Track ab, der sich an eine Seite eines breiten Wegs hält, oder einen GPS-Bias. Mit der Zeit klingt er wieder auf null ab.
Ein Unscented-Filter ist es, weil die Messfunktion an jeder Ecke abknickt. Sie gibt an, wo der Zustand einen Messpunkt auf die Linie setzt. Der Filter schickt eine Handvoll Stichproben-Zustände durch diese Funktion, die Sigma-Punkte. Liegen Punkte auf beiden Seiten einer Ecke, landen sie auf beiden Schenkeln und erfassen den Knick. Eine Linearisierung sähe nur einen Schenkel. Aus demselben Grund läuft die Linie über ihre Enden hinaus gerade weiter. Als ich sie stattdessen an den Enden begrenzt habe, landete jeder Sigma-Punkt jenseits eines Endes genau auf diesem Ende, und ein gerades, rauschfreies Teilstück lag 6 m daneben. Abbildung 4 zeigt beides. Danach wird das Teilstück rückwärts geglättet, und ein letzter Schritt stellt sicher, dass die Strecke nur zunimmt. An einer synthetischen Ecke ergibt das 1,5 m RMS, gegenüber 3,3 m bei der bloßen Projektion. Die zugeordnete Linie fließt nie in den bereinigten Track zurück, sonst würde sich deine Verlauf ändern, sobald du eine Kartenregion herunterlädst.
Was es auf dem Handy kostet
Auf meinem Desktop brauchte der Graph im Release-Build 4,4 s, um 300 synthetische Spaziergänge von je einer Stunde zu bereinigen, der alte Glätter 318 ms. Eine Stunde mit Rohdaten der Satelliten dauerte etwa 200 ms, ohne sie 20 ms.
Das Problem zeigte sich erst auf dem Handy. Auf dem OnePlus dauerte es 37 s, zwei Spaziergänge von 1,8 und 6,2 km mit rohen GNSS-Daten zu bereinigen, und das bei jedem Start, weil walker jede Aktivität von Grund auf neu bereinigte. Das war ein Debug-Build, und die kleinen Matrixfunktionen des Solvers, die ihre Argumente als Wert übernehmen, brauchen Inlining. Der Debug-Build überzeichnet also die Kosten. Einen Release-Build habe ich auf dem Handy aber noch nicht gemessen.
Im nächsten Meilenstein blieb der konstante Faktor, wie er war. Geändert habe ich das Muster: walker bereinigt jetzt jede Aktivität einmal und behält das Ergebnis, damit ein Start nicht wieder alle Aktivitäten neu bereinigt. Was noch fehlt, bereinigt die App auf bis zu vier Threads abseits des Speicher-Threads, damit der Rest der App nicht darauf wartet. Weil ich vorher gemessen habe, fand ich zwei Beschleunigungen, die das Ergebnis bitgenau gleich lassen. Auf meinem Desktop sank die Zeit für die Radtour im Release-Build von 2,6 s auf 1,2 s. Das ist gebaut, aber noch in keinem Release, und auf dem Handy habe ich es noch immer nicht gemessen.
Eine GPU spielt dabei keine Rolle. Pseudoentfernungen von etwa 2·10⁷ m brauchen Millimetergenauigkeit, also f64, und der Vulkan-Treiber des Handys hat keine f64-Shader.
Finge ich noch einmal an, würde ich zwei Dinge früher tun. Ich würde die Bereinigung an etwas prüfen, das sie nie zu sehen bekommt, statt an der Distanz, die sie anzeigt. Und ich würde früh auf dem Handy messen: Der Desktop sagte ein paar hundert Millisekunden pro Stunde, das Handy 37 Sekunden.