mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik AVR: Interpolation? Splines?


Autor: Kalle (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ich habe vier Meßpunkte in der Ebene und möchte zwischen dem zweiten
und dritten einen weiteren Punkt möglichst gut interpolieren.

Hat zufällig jemand so etwas schon mal gemacht, mit etwas besserem
als nur linearer Interpolation.

Wenn ich mir die Formel in Wikipedia zu Splines, Langrane-Interpolation, 
etc. anschaue, verstehe ich nur noch Bahnhof.
Muß man da wirklich erstmal riesen Gleichungssysteme lösen.

Hat jemand so etwas schon mal mit einem AVR gemacht?

Grüsse
Kalle

Autor: Kalle (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ach ja, vergessen.
Die Messpunkte / Messwerte liegen als uint16_t vor.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kein Wunder, daß alles andere als lineare Interpolation aufwändiger
ist - du musst ja auch mehr als 2 Punkte verwursten.

Wenn du mehr als die zwei verwenden willst, musst du dir erst mal
klar werden, ob die Punkte (z.B. 4) exakt sind.
Falls ja, kannst du entsprechend interpolieren (dann halt nicht mit
einer Geraden wie bei lin. Int., sondern 3. O.).
Falls nein, geht es nicht um Interpolieren, sondern Approximieren;
ganz anderes Thema.

Autor: Zefix (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
mh, Ja.
Aber was ist daran bitte so schwer? Spline Interpolation gehört
zu den mathematischen Grundlagen eines technischen Studiums ...
In deinem Fall zwar nicht ganz angebracht, aber das solltest du
beim eifrigen Studium der Materie selber rausfinden.
Und die Methode der kleinsten Quadrate ist wohl auch kein Geheimnis.

Autor: Stefan Salewski (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Muß man da wirklich erstmal riesen Gleichungssysteme lösen.

Nein. Holzbrett, Nägel, biegsame Latte.
Daher kommt ja die Bezeichnung Spline-Interpolation.

Autor: Kalle (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

Kleinste Quadarate ist aber keine Interpolation.

Und es hat nicht jeder ein Mathe-Studium absolviert.

Hat jemand evt. Links, auf Seiten zu dem Thema,
wie die Gleichungssysteme effizient auf einem MC löst?
Oder evt. sogar ein Stück COde zum Abschauen?

Grüsse
Kalle

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

Bewertung
0 lesenswert
nicht lesenswert
Da drin versteckt findest du eine sehr verständliche Darstellung für 
Splines

Autor: Zefix (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Les n Mathebuch !
Und die Methode der kleinsten Quadrate hat sehrwohl was
mit Interpolation sowie dem Lösen nichtlinearer Gleichungssystem
zu tun ... pfosten ...

Autor: ?? (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Fuer solche Geschichten hat man vorteilhafter Weise ein Mathe oder 
aehnliches Studium absolviert. Zuerst sollte man sich im klaren werden, 
ob man nun etwas Approximierendes oder etwas Interpolierendes haben 
will. Falls das System ueberbestimmt ist, wird's etwas Approximierendes 
werden.

Autor: AVRNeuling (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du hast ja die Punkte

[0] [1] [2] [3]
     ^   ^
      [x]
       ^

Diese zwei Punkte willst du interpolieren, wenn ich dich richtig 
verstanden habe.

Dann nimm doch die erste Formel aus Wikipedia ;-) Spline Interpolation

s(x) = m * x + b

m = (y2 - y1) /  (x2 - x1)

b = y1 - m * x1

x - Also die Abtastachse ist hier das "Problem", denn dieser Werte 
liegen ja vermutlich in einem Puffer und der neue interpolierte Wert 
soll ja bei der "doppelten Abtastrate" liegen.

(x2 - x1) ist bei einer konstanten Abtastung immer 1.

Also x müsste man dann eine gebrochene Zahl verwenden.

Du kannst auch deinen Eingangspuffer vergroessern (also zwischen jeden 
Wert eine Null einfügen) dann benötigst du keine gebrochene Zahl zur 
Interpolation.

ciao

Autor: Nils (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo AVRNeuling,

was Du beschreibst ist doch genau die lineare Interpolation, die der 
Thread-Starter nicht wollte.

Wer mehr will, muss halt auch mehr rechnen...

Nils.

Autor: spess53 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi

Zefix (Gast) schrieb:

>Aber was ist daran bitte so schwer? Spline Interpolation gehört
>zu den mathematischen Grundlagen eines technischen Studiums ...

Dann kannst du das ja auch mal allgemein verständlich darlegen

MfG Spess

Autor: Marko B. (glagnar)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kennt eigentlich jemand ein gutes Verfahren um Splines zu retikulieren?

Autor: Dieter Engelhardt (netdieter) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die Frage ist eigentlich, was willst Du eigentlich darstellen?
Splines ist das apropate Mittel um schwingungsverläufe Abzubilden. Wenn 
Du aber ein linears System abbilden willst, dann ist eine lineare 
Regression ggf. das wo nach Du suchst: 
http://de.wikipedia.org/wiki/Regressionsanalyse

Autor: Christian H. (netzwanze) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Passt auch eventuell dazu (eigene Frage):

Ich habe eine (grobe) Tabelle, welche mir zu gegebenen ADC-Werten 
(AVR-ADC) eines NTC, Temperaturen ausgibt. Ich habe in der Tabelle aus 
Platzgründen nicht jeden möglichen Zwischenwert abgelegt. Nun möchte ich 
aus einem ADC-Wert, der zufällig nicht in der Tabelle liegt (jedoch zwei 
anschließende)
in einen Temperaturwert "umrechnen".

Wie mache ich das am geschicktesten. Linear oder mittels Spline? 
Ersteres ist sicherlich viel schneller machbar, birgt aber 
Ungenauigkeiten.

Sind Splines dazu geeignet und vor allen, auf einem AVR sinnvoll 
anzuwenden?

Ich hatte zwar mal Mathe studiert, habe aber noch vor den Splines das 
Fach gewechselt. Angestaubtes Grundwissen in irgendwelchen Fachbüchern 
ist nicht mehr erreichbar, da ich nach Ende meines IT-Studiums fast 
alles verschenkt hatte. Ich würde es mir aber gerne einfach machen und 
auf ein fertiges Konzept (gerne auch Programm in C) zurückgreifen, ohne 
weit zu fahren und Mathe Biblotheken zu besuchen.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das ist doch ein Kurve, bei der nichts spannendes passiert!
Da reicht lineare Int. allemal denke ich. Jeder Mehraufwand lohnt
frühestens, wenn die Kurve auch eine ordentliche Krümmung hat.
Mal doch mal die Punkte auf und schau dir die Abweichung an zwischen
den geraden Linien und einer glatt durchgezogenen Kurve.
Schon mit wenigen Stützpunkten wird die Abweichung akzeptabel sein.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
?? schrieb:
> Fuer solche Geschichten hat man vorteilhafter Weise ein Mathe oder
> aehnliches Studium absolviert.

Nicht wirklich

> Zuerst sollte man sich im klaren werden,
> ob man nun etwas Approximierendes oder etwas Interpolierendes haben
> will.

Das ist ok. Das sollte man.
Man sollte aber auch die Aufgabenstellung lesen.

Gegeben sind 4 Punkte, gesucht ist eine Gleichung (Gleichungssystem), so 
dass die 4 Punkte auf der Kurve liegen, die durch diese 4 Punkte 
beschrieben werden kann.

Nun gibt es natürlich viele Gleichungsfamilien, mit denen man so etwas 
lösen kann.

Also kann man zb. Polynome als Grundlage nehmen.
zb. eine Gleichung 3. Grades

  Y = a*X^3 + b*X^2 + c*X + d

Wo kriegt man die 4 Koeffizienten a, b, c, d her?

Ganz einfach, wir haben 4 Punkte P1, P2, P3, P4. Jeder mit einem X und 
dem zugehörigen Y Wert.

D.h. wir haben

   P1y = a*P1x^3 + b*P1x^2 + c*P1x + d
   P2y = a*P2x^3 + b*P2x^2 + c*P2x + d
   P3y = a*P3x^3 + b*P3x^2 + c*P3x + d
   P4y = a*P4x^3 + b*P4x^2 + c*P4x + d

... ein lineares Gleichungssystem aus 4 Gleichungen in 4 Unbekannten. 
Und das kann man lösen (zb. Gauss Verfahren).

Damit hat man dann die Koeffizienten und eine Gleichung in die ich einen 
beliebiegen X-Wert einsetzen kann und den zugehörigen Y Wert 
rausbekomme.


Spline ist das noch keiner. Da müsste man nach X und Y aufdröseln, 
jeweils für X und Y ein eigenständiges Gleichungssystem aus 4 
Gleichungen aufbauen und einen Parameter t von 0 bis 1 laufen lassen (0 
= der eine Endpunkt, 0.33 der erste Zwischenpunkt, 0.66 der nächste 
Zwischenpunkt und schliesslich t gleich 1 der andere Endpunkt)

    X = at^3 + bt^2 + ct + d
    y = et^3 + ft^2 + gt + h

d.h.

   P1x = a*0^3    + b*0^2    + c*0    + d
   P2x = a*0.33^3 + b*0.33^2 + c*0.33 + d
   P3x = a*0.66^3 + b*0.66^2 + c*0.66 + d
   P4x = a*1^3    + b*1^2    + c*1    + d

   P1y = e*0^3    + f*0^2    + g*0    + h
   P2y = e*0.33^3 + f*0.33^2 + g*0.33 + h
   P3y = e*0.66^3 + f*0.66^2 + g*0.66 + h
   P4y = e*1^3    + f*1^2    + g*1    + h


Beide linearen Gleichungssysteme lösen um die Koeffizienten a, b, c, d 
bzw. e, f, g, h zu bestimmen.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
So weit, so gut.
Es geht hier aber um 4 Meßpunkte laut OP.
Je nach (Un-) Genauigkeit kann ein Polynom dritten Grades da schon
ziemlich unruhig werden. Möglicherweise ist das dann nicht das
Grüne vom Ei.

Autor: Maxxie (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ob das linear ist oder nicht muss man daran sehen, welcher Natur die 
Meßwerte sind.

Wenn das Wort Meßwerte fällt und einen Verlauf anzunähern, ist eine 
Interpolation nicht das Richtige:
Meßwerte enthalten Fehler, Abweichungen zum Ideal. Wenn nun interpoliert 
wird, dann läuft diese exakt durch diese Fehler, was wohl nicht 
gewünscht ist. Statt dessen soll der Idealverlauf gefunden werden

Und hier hat schon jemand gesagt wie das funktioniert: Lineares 
Ausgleichsproblem mit dem Verfahren der minimalen Fehlerquadrate.

Du stellst eine Annahme auf, wie der Verlauf auszusehen hat. Vielleicht 
eine Gerade, eine Hyperbel, Polynom etc ...

Die Parameter dieser Form werden nun bestimmt, in dem du ein 
entsprechendes (überbestimmtes) Gleichungssystem A und den Meßwerten b 
aufbaust (|Ax-b| -> min), dieses mit der Transponierten multiplizierst 
(entspricht der ersten Ableitung der 2. euklidischen Norm der Matrix) 
und das löst. 0-Stelle -> Extremstelle (Minimum) des Fehlers des 
überbestimmten Gleichungssystems.

Nun kannst du die gewonnen Parameter in den angenommenen Verlauf 
einsetzen und hast das was du suchst: Eine Annäherung an den 
fehlerkorrigierten Werteverlauf.

Autor: Kalle (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

erstmal Danke an Karl heinz Buchegger für seine grundsätzlichen 
Ausführungen.

Ich bin mir schon im klaren, was die Unterschiede zwischen den
verschiedenen Imnterpolationsverfahren sind.
Und nein, ich "Kleinste Quadrate" ist keine Interpolation.
Das weiss ich auch ohne Mathe-Studium.

Vieleicht noch etwas zur Anwendung.
Ein Tastkopf fährt eine Bauteil ab. Die Position des Tastkopfs
wird an einen AR übermittelt, der einen Plotter ansteuert.
Alle 1 kommt eine Position des Tastkopfs. Der plotter benötigt aber
alle 500ms einen Position.
Da wären Splines IMHO angebarcht, da lt. Wiki, ja Unstetigkeiten
in Ableitungen gößer zwei nicht mehr wahr nimmt.

Hab#' das ganze mal mit Corel Draw probiert.
Die Meßpunkte eingezeichnet und dann einen Spline-Zug über die Punkte
gelegt.

Grüsse
Kalle

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kalle schrieb:

> Da wären Splines IMHO angebarcht, da lt. Wiki, ja Unstetigkeiten
> in Ableitungen gößer zwei nicht mehr wahr nimmt.

Den letzten Satzteil versteh ich zwar nicht, aber

Da könntest du genausogut die letzte gemessene Position 2-mal 
hintereinander ausgeben. Ist genauso gelogen, wie wenn du da jetzt einen 
Spline reinlegst. Nur weniger Arbeit :-)

Autor: Kalle (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich hätte besser schreiben sollen:

Splines sehen so schön glatt aus, da Unstetigkeiten erst ab der dritten
Ableitung auftreten können.

Und besser gelogen als jeden Wert zweimal zu nehmen, sind
Spline IMHO allemal, wenn - wie in meinem Fall - die abzutastenden
Linie von einem Kurvenlineal stammt. ;-)

Grüsse
Kalle

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kalle schrieb:
> Ich hätte besser schreiben sollen:
>
> Splines sehen so schön glatt aus, da Unstetigkeiten erst ab der dritten
> Ableitung auftreten können.

Das hast du nicht wirklich verstanden.
Bei der beschriebenen Problematik geht es darum, was passiert, wenn 2 
Splines zusammenstossen. Meistens geht man nämlich her und legt nicht 
einen Spline durch 20 Punkte, sondern man konstruiert in diese 20 Punkte 
zb 18 Splines rein, die an den gegebenen Punkt zusammenstossen.

Dabei gibt es jetzt aber Unterschiede
* haben die Splines an den Zusammenstosspunkten nur die Position
  gemeinsam, dann spricht man an diesem 'Schnittpunkt' von einer
  Kontunität (engl. Continuity) C(0).
  Der Splinezug aus den beiden einzelnen Splines kann an diesem
  Punkt durchaus einen scharfen 86,5° Knick haben.
  Wenn du in einem Wägelchen sitzt, dass diesen Verbindungspunkt als
  Schiene in einer Achterbahn durchfährst, dann knallst du gewaltig
  gegen die Seitenwand.
* ist an den gemeinsamen Punkten gewährleistet, dass die Richtung
  der Tangenten der beiden Splines (die erste Ableitung) übereinstimmt,
  dann hat man einen C(1) Übergang. Der Übergang ist zwar nicht mehr so
  abrupt, wie bei C(0), die Kurve läuft schön durch, aber dem Auge
  fällt immer noch auf, dass etwas nicht stimmt.
  In der Achterbahn wäre das: Die Kurve der Bahn ist zwar durchgehend.
  Aber an einem Punkt der Bahn nimmt die Fliehkraft urplötzlich
  sprunghaft zu
* eine C(2) Continuity erreicht man, wenn am Verbindungspunkt auch noch
  die 2-te Ableitung übereinstimmt. Geometrisch gesprochen: wenn der
  Kurvenradius identisch ist.
  In der Achterbahn bedeutet das, dass die Fliehkraft sich gleichmässig
  auf bzw. abbaut.

Das alles kommt aber nur dann zum Tragen, wenn der komplette Spline aus 
mehreren Teilstücken zusammengesetzt werden muss.

Du hast sowieso nur 4 Punkte, bei dir spielt das so gut wie keine Rolle. 
Einzige Ausnahme: wenn du in deine 4 Punkte 3 Parabeln 
hineinkonstruierst.

Mit 4 Punkten könntest du zb einen Bezier Spline erreichten oder aber 
den schon weiter oben angesprochenen kubischen Spline. (Wobei der 
Einwand natürlich berechtigt ist, dass ein polynomialer Spline unter 
gewissen Umständen heftig um die gewünschte Kurve pendelt. Bei kubischen 
Abschnitten ist die Gefahr noch nicht so gross, dazu hat eine Kurve 3. 
Grades einfach zuwenig Freiheitsgrade als zb eine Kurve 10-ten Grades. 
Aber möglich ist es, und die Überschwinger sind dann heftig)

> Und besser gelogen als jeden Wert zweimal zu nehmen, sind
> Spline IMHO allemal, wenn - wie in meinem Fall - die abzutastenden
> Linie von einem Kurvenlineal stammt. ;-)

Na dann.


Im Übrigen:
Wenn eine deiner beiden Koordinatenachsen monotan wachsend abgenommen 
wird (und bis jetzt hört sich alles danach an), dann wärst du besser 
beraten, eine Funktion y = f(x) zu bauen, als einen Spline. Spline sind 
zwar wunderschön anzuschauen, aber sie sind Krüppel wenn es darum geht 
zb equidistante Punkte auf dem Spline zu finden.

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.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

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