datenreduktion eines xy-signals

mael15

hallo zusammen,
mein programm zeichnet xy-Werte auf und stellt sie auf dem bildschirm in einem koordinatensystem dar (siehe http://gemini-sites.de/signal.gif). ich habe eine einstellbare samplerate, z.b. 2000 smpl/s. nun möchte ich zum reduzieren der zu speichernden daten relativ unwichtige punkte löschen, z.b. den mittleren auf einer geraden mit drei punkten.
meine idee ist, die für meine zwecke wichtigen extremwerte unverändert zu lassen und irgendwie die restlichen punkte zu reduzieren. gibt es dafür ein geeignetes verfahren?
danke!

knivil

gibt es dafür ein geeignetes verfahren

Hunderte ... z.B. stueckweise Approximation mit einer Geraden, Glaettung, Ableitung/Kruemmung betrachten ... Du kannst wahrscheinlich x und y unabhaengig betrachten ...

Das kommt darauf an, welche Eigenschaften du erhalten möchtest. Wenn es dir nur auf Extremwerte ankommt, schmeisse doch alles bis auf (lokale) Extremwerte weg. Das Signal sieht danach ganz "eckig" aus, aber vielleicht reicht dir das ja?

Stichwort "Smoothing Spline"?

mael15

danke für eure antworten!

JFB schrieb:

Stichwort "Smoothing Spline"?

klingt gut, hab ich mal zu gegooglt, aber leider nichts umsetzbares gefunden. kann es sein, dass es sich dabei eher um eine technik handelt, mit der man weiche kurven aus wenigen punkten erzeugen kann? als zweiter schritt wäre das gut, aber ich müsste vorher punkte "sinnvoll" reduzieren.

Mups schrieb:

Das kommt darauf an, welche Eigenschaften du erhalten möchtest. Wenn es dir nur auf Extremwerte ankommt, schmeisse doch alles bis auf (lokale) Extremwerte weg. Das Signal sieht danach ganz "eckig" aus, aber vielleicht reicht dir das ja?

das resultat sollte schon recht nach dran am ausgangssignal, also nicht extrem eckig sein.

ich hatte vermutet, dass eine solche datenreduktion häufig gebraucht werden würde und es deshalb schon fertige bibliotheken dafür gibt. kennt jemand eine?

alternativ hatte ich überlegt, punkte umso häufiger zu löschen je weiter sie von wichtigen punkten entfernt sind. vielleicht gibt es dafür schon einen guten algorithmus? wichtig wären neben extremwerten noch die schnittpunkte des signals mit dem roten kreis.

Wenn dir tatsächlich soetwas einfaches reicht, dann ist selber machen vermutlich 100x schneller als Bibliothek installieren, komplilieren, Doku-lesen etc.

Ganz naiv reicht dir vielleicht jeder 100ste Punkt (damit es hübsch aussieht), und die interessanten Punkte nahe des Kreises und die Extrempunkte:

Für lokale Extrema:
\mbox{Falls } |x_{n-1}| <= |x_{n}| \mbox{ und } |x_{n+1}| <= |x_{n}|: \mbox{ Speichere } x_n

Der Schnitt mit dem Kreis liegt zwischen zwei Punkten:
\mbox{Falls } |x_{n-1}| <= R <= |x_{n}|: \mbox{ Speichere } x\_n \mbox{ und } x\_{n-1}

Irgendeine komische Bedingung für zusätzliche Punkte:
\mbox{Falls } n \mbox{ mod } 100=0: \mbox{ Speichere } x_n

Falls du irgendetwas ausdenken möchtest, um "nah bei wichtigen Punkten" viel zu speichern, und weit weg möglichst wenig, wird die Formulierung umständlicher. Wie wäre es mit soetwas hier:
Falls $x_n$ ein "wichtiger" Punkt ist, speichere die Punkte mit den Indices $n\pm2^0, n\pm2^1, n\pm2^2 ...$

Du kannst dir aber auch beliebig viel klügere Dinge ausdenken. Wenn du einfach Plattenplatz sparen willst, empfehle ich möglicherweise auch WinZip

Mups schrieb:

Der Schnitt mit dem Kreis liegt zwischen zwei Punkten:
\mbox{Falls } |x_{n-1}| <= R <= |x_{n}|: \mbox{ Speichere } x\_n \mbox{ und } x\_{n-1}

Besser:

Der Schnitt mit dem Kreis liegt zwischen zwei Punkten:
\mbox{Falls } |x_{n-1}| <= R <= |x_{n}| \mbox{ oder } |x_{n}| <= R <= |x_{n-1}|: \mbox{ Speichere } x\_n \mbox{ und } x\_{n-1}

mael15

Mups schrieb:

Wenn dir tatsächlich soetwas einfaches reicht, dann ist selber machen vermutlich 100x schneller als Bibliothek installieren, komplilieren, Doku-lesen etc.

ok, dann denke ich mir selber etwas aus. das hat mich neulich bei einem anderen problem 5 tage gekostet und konnte im nachhinein schneller mit einer library gelöst werden. deswegen wollte ich in diesem fall lieber erstmal nach einer library fragen.

Mups schrieb:

Wenn du einfach Plattenplatz sparen willst, empfehle ich möglicherweise auch WinZip

winrar habe ich schon versucht, hat im besten fall leider nur 14% gebracht. bisher speichere ich die daten (16 bit mit vorzeichen) binär in eine textdatei.

danke!

Ah, meine Antwort war auf den Post darüber bezogen Gegen Eckigkeit hilft das nämlich ganz gut, wie der Name schon nahelegt.

PS: Unter dem Stichwort "Knotenentfernen" ließe sich aber vielleicht doch etwas basteln. Wenn man nämlich zuerst einen Smoothing Spline mit passendem Glättungsparameter (bzw. Datentreueparameter, den zu finden eher eine Gefühlssache ist, bzw. wenn du wirklich Interpolation brauchst, kannst du ihn eh weglassen) über die Datenpunkte legt und dann mit einem Krümmungsschätzer nur die Knoten behält, bei denen die Krümmung hoch ist (hat ja knivil schon angedeutet) und dann ebendort den Spline auswerten. Das könnte mit MATLAB evtl. schon mit annehmbarem Aufwand implementiert werden.
Wenn dir ein Quasi-Interpolant reicht könntest du auch einfach den Schoenberg-Operator auf deine Punkte loslassen.
Aber das hängt natürlich von der erforderlichen Datentreue ab.
Vielleicht sind Splines aber auch ein viel zu komplizierter Ansatz für dein Problem. Kommt halt darauf an, was du erreichen willst.
Eine angenehme (weil nicht formal-mathematische) Einführung in das Thema gibt's hier: http://www.uni-giessen.de/tomas.sauer/Skripten/Splines.pdf bzw. in neuerer Version hier: http://www.fim.uni-passau.de/fileadmin/files/lehrstuhl/sauer/geyer/SplinesV3.pdf

knivil

mael15 schrieb:

bisher speichere ich die daten (16 bit mit vorzeichen) binär in eine textdatei.

1.) Wie ist das den zu verstehen?
2.) Ueber wieviel GByte reden wir hier?

mael15

knivil schrieb:

mael15 schrieb:

bisher speichere ich die daten (16 bit mit vorzeichen) binär in eine textdatei.

1.) Wie ist das den zu verstehen?
2.) Ueber wieviel GByte reden wir hier?

ich speichere maximal 4 kanäle je x+y mit maximaler samplerate 10000 s/sek per wxDataOutputStream::Write16 (http://docs.wxwidgets.org/2.9.1/classwx_data_output_stream.html). die normale aufnahmedauer beträgt 10 sekunden, ergibt dateien der größe 1,5 MB. das können aber an einem arbeitstag schonmal 800 dateien werden, ein normales projekt dauert 1-2 wochen.

JFB schrieb:

PS: Unter dem Stichwort "Knotenentfernen" ließe sich aber vielleicht doch etwas basteln. [...] Das könnte mit MATLAB evtl. schon mit annehmbarem Aufwand implementiert werden.
Wenn dir ein Quasi-Interpolant reicht könntest du auch einfach den Schoenberg-Operator auf deine Punkte loslassen. [...] Eine angenehme (weil nicht formal-mathematische) Einführung in das Thema gibt's hier: http://www.uni-giessen.de/tomas.sauer/Skripten/Splines.pdf bzw. in neuerer Version hier: http://www.fim.uni-passau.de/fileadmin/files/lehrstuhl/sauer/geyer/SplinesV3.pdf

danke, das klingt alles sehr gut und die pdfs scheinen auch genau das richtige zu sein, für mich als nicht-mathematiker wird es aber zu viel aufwand. mit matlab habe ich auch nur sehr wenig erfahrung, leider.
ich habe gedacht, vielleicht gibt es einen (auch für mich einfach zu berechnenden) wert, der den übereinstimmungsgrad zweier signale angibt? dann könnte ich die punkte nach meiner eigenen logik soweit reduzieren, bis ein bestimmter übereinstimmungsgrad erreicht ist.

knivil

Vielleicht suchst du sowas, ist nett: http://www.motiondraw.com/md/as_samples/t/LineGeneralization/demo.html

mael15

ou, das sieht super aus, danke!
ich bin gerade mit einem anderen teil meines programmes beschäftigt, werde mir das aber definitv noch genauer anschauen.