mikrocontroller.net

Forum: Digitale Signalverarbeitung / DSP intelligente und einfache 2-Koordinaten-Interpolation


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
Autor: Signalverarbeiter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: A. F. (artur-f) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kannst so z.B. interpoliert werden:
NeuerWert = ((NeuerWert - AlterWert) >> 3) + AlterWert;


Schieben um eine Stelle entspricht Wert / 2.

Autor: Signalverarbeiter (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Sigi (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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)

Autor: Signalverarbeiter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: J. S. (engineer) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Sigi (Gast)
Datum:
Angehängte Dateien:

Bewertung
1 lesenswert
nicht lesenswert
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..

Autor: Signalverarbeiter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wuhui! das lese ich mir am Wochenende durch.

Danke!

Autor: MaWin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Signalverarbeiter schrieb:
> Wie geht das am einfachsten?

In dem man schreibt was man will:

Aus GPS Punktwolke den vermutlich zurückgelegten Track berechnen.

Autor: Kalman (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ein Kalman-Filter als Schätzer?

Autor: Sigi (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
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.

Autor: J. S. (engineer) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.