Gegeben ist eine fortwährend einlaufende Datenmenge von Y und X Werten
ungenau gemessener Positionen, die interpoliert werden wollen.
Wie geht das am einfachsten?
Die Werte X und Y sind nicht durch R und PHI darstellbar, bzw. sie
verhalten sich nicht so. Die Zeiten sind nicht im gleichen Abstand, es
kommen also z.B. 5 - 10 Werte die Sekunde, es gibt Lücken.
Geradeninterpolation zwischen den letzten bekannten Werten ist
vollkommen nutzlos. Splines wären rechentechnisch möglich, zeichnen aber
die Wege zu genau nach. Ich benötige eine einfache Methode, um sagen wir
10 Werte um den aktuellen Punkt (+/- 1 Meter) zu glätten, Messfehler zu
verwerfen und dann die Position mit Punkten zu interpolieren.
Hier ist das veranschaulicht: Es kommen mal wenige und mal viele Werte
pro Zeiteinheit. Herauskommen soll eine feiner aufgelöste Wertemenge
X'Y' mit wählbarem zeitlichen Abstand. Im ersten Schritt reicht eine
Interpolation auf feste zeitliche Werte.
Im Eindimensionalen hätte ich einfach die Y, die zur Verfügung stehen
(variierende Anzahl) je nach Abstand zum Betrachtungszeitpunkt gewichtet
und das in eine Dezimation geworfen, mit gfs einem
CIC-Aufwärts-Interpolator.
Im 2D fehlt dazu aber ersteinmal der Bezug, da X und t nicht equidistant
sind.
Du schreibst im ersten Beitrag von zu interpolierenden
Punkten, später aber in der Zeichnung deutest du per
grüner Linie und Punkten eine Approximation an.
Da die Interpolation der roten Punkte deiner Zeichnung
kaum Sinn machen würde, nehme ich mal an, du willst
approximieren (=> grüne Linie), und zwar so, dass
die Beschreibung eine zeitäquidistante Darstellung
über den gesamten Bereich erlaubt.
Das habe ich fast so schon gemacht, siehe Skizze.
Dazu habe ich jeweils z.B. 10 fortlaufende Punkte
zusammengefasst und per Bestapproximation z.B.
durch eine kubische Bezier-Linie approximiert.
Wenn man zwei dieser Kurven über den Punkten
p(k)..p(k+9) bzw. p(k+1)..p(k+10) in den überlagernden
Bereichen (überlagernd bzgl. der Zeiten) ineinander
übergehen lässt (genauso wie bei Bezierkurven nach
Beziersplines), dann erhält man eine gute Approximation.
(in der Skizze sind die roten Punkte die gemessenen,
die dunkelgrauen die berechneten Punkte, man erkennt
gut die zeitliche Äquidistanz)
Richtig, es ist faktisch eine Approximation, weil die Messwerte unsicher
sind. Die Interpolation bezieht sich auf die virtuellen (sozusagen
entrauschten) Punkte. Die Approximation erledigt damit das Entrauschen.
Sigi schrieb:> Dazu habe ich jeweils z.B. 10 fortlaufende Punkte> zusammengefasst
Das wird in meinem Fall schwierig, weil die 10 Punkte manchmal eine
große und manchmal eine sehr geringe Distanz umfassen. Ich brauche also
eine Vorschrift für die Distanz mit unterschiedlichen Mengen von
Punkten.
Also z.B. so:
000000000011111111112222222222
123456789012345678901234567890
*..........*.**..*....*.**....
von 1 bis 16 wären 4 Punkte drin
von 5 bis 20 wären 7 Punkte drin
Ich bräuche also gleitende Übergänge zwischen gleitenden
Interpolationskurven. Das sehe ich nicht, wie das mit Beziersplines
gehen soll / kann.
Signalverarbeiter schrieb:> Im 2D fehlt dazu aber erst einmal der Bezug, da X und t nicht> equidistant sind.
Im ersten Ansatz lasen sich die beiden Achsen getrennt interpolieren.
Alles weitere erfordert Annahmen über das System, dessen Trägheit,
Reaktion auf Oberwellen. Mechanische Objekte lassen sich gut modellieren
und als Filter für die hüpfenden Werte hernehmen. Mit etwas Geschick und
Nachdenken auch entlang der Bewegungsachse. Dazu muss das jeweilige
Wegdifferential gebildet werden und die Krümmung abgeleitet werden.
> Das wird in meinem Fall schwierig, weil die 10 Punkte manchmal eine> große und manchmal eine sehr geringe Distanz umfassen.
Der Zeitpunkt muss natürlich als Parameter in die Interpolation /
Schwerpunkberechnung / Annäherung mit hinein. Es ergibt sich ein
dx/dt(n) und ein dy/dt(n). Das Wegelement ist das Integral über beide,
vereinfacht die Summe über die Samples.
Signalverarbeiter schrieb:> Richtig, es ist faktisch eine Approximation, weil die Messwerte unsicher> sind. Die Interpolation bezieht sich auf die virtuellen (sozusagen> entrauschten) Punkte. Die Approximation erledigt damit das Entrauschen.
Gut, wir nennen es nur anders, meinen aber dasselbe.
Und das mit dem Entrauschen und deinem nachfolgenden
Bemerkungen ist extrem wichtig: ich habe Oben z.B.
10 Punkte für eine Approximation gewählt, du aber
willst nur die Punkte aus einem bestimmten Bereich.
Nehmen wir mal dazu einen Zeitbereich um einen
Zeitpunkt t (beliebig wählbar!), z.B.
Range=[t-dt/2,t+dt/2] (dt>0,aber nicht zu klein) und
bestimmen dazu alle zu approximierenden Punkte.
Das ist ein wesentlich besserer Ansatz als mein
10-Punkte-Ansatz, denn er filtert über einen Zeitbereich
und nicht über einem Indexbereich (ich hoffe mal, dir
ist das klar), und du wirst so sicherlich ein besseres
Ergebnis bekommen.
Damit hast du dann folgenden Algorithmus (zuerst nur grob):
0. Annahme: alle Zeiten deiner Messungen sind in [0..1]
(Vereinfachung für die Berechnungen, das ganze funktioniert
mit entsprechenden Änderungen auch auf offenen Zeitbereichen)
1. wähle einen Zeitpunkt t, zu dem du einen Punkt berechneen
willst. Dazu noch ein geeignetes dt für das
Zeit-Intervall.
2. Bestimme alle Punkte pi und Zeitpunkte ti, so dass
ti in [t-dt/2,t+dt/2] gilt
3. Berechne eine Polynom-Approximation über den Punkten
pi des Zeit-Intervalls
4. Berechne aus dem berechneten Polynom einen Punkt p.
Die Menge aller berechneten p ergibt dann deine gewünschte Kurve.
Zur Approximation: da kann eine sog. Bestapproximation
gewählt werden, typischerweise nach dem Gauss-Ansatz
(hier mal eine quadratische Approximation):
M sei eine Matrix[1..3,1..k], k: Anzahl Punkte des Intervalls
M[1,*] = 1
M[2,*] = [ht1,..,htk] die Zeitpunkte des Intervalls
M[3,*] = [ht1^2,..,htk^2] deren Quadrate
MT = transpose(M)
MI = invert(MT*M)*MT *: Matrix-Multiplikation
vx = [p1.x,..,pk.x] x-Koordinate
vy = [p1.y,..,pk.y] y-Koordinate
mit:
ht1 = (t1-t1)/(tk-t1) Zeitbereichsnormierung
..
htk = (tk-t1)/(tk-t1)
damit: (cx,cy: Polynome der Form c[1]*1 + c[2]*x + c[3]*x^2)
cx = MI*vx *: Matrix-Vector-Produkt
cy = MI*vy
px = cx[1]+0.5*cx[1]+0.25*cx[2] wähle Punkt in ht=0.5
py = cy[1]+0.5*cy[1]+0.25*cy[2]
p = [px,py] ist dann der zu berechnende Punkt.
(grosses Problem, wenn die Anzahl Punkte im Bereich
kleiner 2 ist, dann kann aber der Durchschnitt der
Punkte Als Approximation gewählt werden)
Ich habe hier das Approximationspolynom in ht=0.5 berechnet,
weil er ja in der Mitte des Zeitintervalls liegt.
In den Angehängten Skizzen wird es hoffentlich klar.
Skizze1: Approximation zu einem Zeitpunkt
Skizze2: Approximation zu allen (äquidist.) Zeitpunkten
Skizze3: DT=0.1
Skizze4: DT=0.2
Skizze5: DT=0.3
Skizze6: DT=0.4
(hier sieht man gut, dass mit wachsendem dt die
Approximationskurve "glatter" wird, aber auch die
Form der Punkte aus dem Auge zu verlieren scheint)
Viel Spass..
Signalverarbeiter schrieb:> Wie geht das am einfachsten?
In dem man schreibt was man will:
Aus GPS Punktwolke den vermutlich zurückgelegten Track berechnen.
Kalman schrieb:> Ein Kalman-Filter als Schätzer?
Funktioniert nur für äquidistante Messzeitpunkte
und bei linearer verrauschter Bewegung. Hier
trifft wohl beides nicht zu.
Signalverarbeiter schrieb:> mit gfs einem CIC-Aufwärts-Interpolator.
Grundsätzlich ja, aber nicht bei verrauschten Daten. Hier läuft es auf
einen Schätzer hinaus. Entscheidend ist, wie weit der in die
Vergangenheit und Zukunft schauen soll / darf. Bei ausreichend Punkten
ist das kein Problem.
> Im 2D fehlt dazu aber ersteinmal der Bezug, da X und t nicht> equidistant sind.
konstante Abstände und 2D sind zwei Paar Schuhe. Das Problem der
ungleichmäßigen Punkte gibt es auch im Eindimensionalen.
Die Lösung muss daran orientiert werden, wie schnell sich die Kurve
ändern kann. Diese Krümmung wirkt direkt auf das Differential. Die
Trägheit mit der die Kurve verläuft, z.B. bei einem massebelasteten
System wäre eine Information für die zweite Ableitung.
Mit diesen Randbedingungen kann man schon einmal 3 Gleichungen
aufstellen, in den Zeitbereich überführen und so umformen und mit
Punkten füttern, dass eine überbestimmte Gleichung entsteht, die man
optimieren kann.
