Kurvenglättung / Interpolation / Extrapolation berechnen?

[moelski]

Moin !

Wir ham erst kürzlich TeeChart Pro grkauft. Soweit eine feine Sache. Aber ...
Wenn man eine neue Serie hinzufügt und als Data Source Function -> Smoothing nutzt, dann mag das bei weniger als 500 Punkten noch recht performant sein. Wenn wir aber mal in die Region von sagen wir mal 20000 und mehr gehen, dann ist das nur noch ein CPU Killer.

Der Support von Steema hat das wohl auch erkannt, aber wann es gefixt wird weiss keiner

Frage deshalb ...
Hat jemand eine Funktion, die man auf eine bestehende Kurve (bzw. dessen x/y Daten) loslassen kann und mit den gegebenen Werten eine neue geglättete Kurve berechnet (oder sagen wir mal die Werte dafür). Das ganze solte nur halbwegs performant sein und vielleicht über ein paar Parameter einstellbar (Stärke der Glättung z.B.).

[alzaimar]

Ahoi

Meine Meinung: Wer 20.000 Messwerte ungefiltert in so eine Komponente jagt, dem fehlen -ehrlich gesagt- grundlegende Kentnisse in der Aufbereitung und vor allen Dingen der Bedeutung der Messwerte. Erwartet von Steema keine Wunder, dafür gibt es andere Firmen.

Was sind denn das für 20.000 Punkte? Wie genau soll das Fitting sein? Erwartet ihr Peaks? Genügen die Messwerte theoretisch einer Funktion? Kann man also Regression ansetzen?

Ich habe z.B. mal ein Fitting mit Hilfe einer Spline-Funktion erstellt, bei der so lange Punkte entfernt wurden, bis die resultierende Spline die gelöschten Punkte nicht mehr approximiert hat. Damit lassen sich glatte Bereiche auf 2-3 Punkte reduzieren, Peaks bleiben jedoch erhalten. Das Verfahren war verblüffend simpel, erstaunlich schnell und sehr erfolgreich. Es lief vor 20 Jahren ( ) auf einem Motorola-Rechner, der mit 10MHz getaktet war in RM-Basic, einer Interpreter-Sprache. Es handelte sich zwar nicht um 20.000 Punkte, ich könnte mir aber vorstellen, das man zunächst Chunks à 100 Punkte erstellt, die einzeln glättet und dann das Verfahren abschließend auf alle Punkte anwendet. Richtig schnell ist das aber auch nicht.

Ich würde erstmal einen Filter vorschalten, denn offensichtlich benötigt ihr die 20.000 Punkte gar nicht. Ein Filter kann z.B. einen Punkt P[i] nur dann durchlassen, wenn sich sein Y-Wert signifikant von P[i-1] unterscheidet. Alternativ kannst Du auch über die letzten N Punkte eine polynomiale Regression laufen lassen und P[i] nur dann durchlassen, wenn eine Extrapolation dieses Punktes ihn nicht trifft. Oder Du nimmst einen 'Moving Average', was aufs Gleiche rauskommt.

Völlig unwissenschaftlich ist ein Ausgleichs-Spline, der die Punkteschar glättet, aber das machen die Steema-Leute bestimmt. Es läuft auf ein Gleichungssystem mit 20.000 Unbekannten hinaus, das -soweit ich weiss- bestenfalls in O(n*n) gelöst werden kann, ergo Dein CPU-Killer.

Ein Filter, wie von mir vorgeschlagen, dürfte jedoch in O(n) durchlaufen und recht brauchbare Ergebnisse liefern. Dazu sind aber Kenntnisse des physikalischen Hintergrundes der Messwerte nötig, um eine geeignete Filterfunktion zu entwickeln.

[marabu]

Hallo Dominik,

zuerst würde auch ich die Daten so komprimieren (alzaimar nennt es filtern), dass die Punktmenge einigermaßen mit der Auflösung deines Charts harmoniert. Ich würde das wahrscheinlich auf der Basis des perpendicular distance algorithm (Lang Simplification) machen - damit glätten die Kartographen ihre Linien. Dabei werden immer drei Folgepunkte betrachtet. Liegt der Abstand des mittleren Punktes von der Ideallinie (Verbindung zwischen dem Vorgänger und dem Nachfolger) innerhalb einer vorgegebenen Toleranzgrenze, dann wird der Punkt eliminiert.

Grüße vom marabu

[alzaimar]

Hallo Marabu,

Zitat von marabu:

...perpendicular distance algorithm (Lang Simplification)...

Lustig, wenn man zu selbstgebastelten kleinen Problemlösungen 20 Jahre später den entsprechenden Fachausdruck präsentiert bekommt (Hätte ich mehr lesen sollen? ). Dieses Verfahren verminderte in unseren Messreihen das Rauschen und bereitete die Daten für eine Regression oder profane Splines vor.

Vermutlich führt eine Verkettung von Filtern/Komprimieren zum Erfolg. Diese Blackboxes lassen sich ja ohne Probleme in den einkommenden Datenstrom integrieren, sodaß keine spürbare Verzögerung auftritt.

[moelski]

Moin Jungs,

Zitat:

Meine Meinung: Wer 20.000 Messwerte ungefiltert in so eine Komponente jagt, dem fehlen -ehrlich gesagt- grundlegende Kentnisse in der Aufbereitung und vor allen Dingen der Bedeutung der Messwerte.

Ich lass mich da gerne belehren

Zitat:

Erwartet von Steema keine Wunder, dafür gibt es andere Firmen.

Das geht schon. Man muss nur die FastLine Serie nutzen. Dann sind 20000 Punkte Peanuts ...

Aber prinzipiell gebe ich dir recht. Man könnte im Vorfeld eine Menge Daten wegfiltern. TeeChart bietet dafür sogar eigene Funktionen (DrawAll Option).

Vielleicht ein paar Worte was wir da überhaupt mit den Kurven treiben.
Also, wir werten von Ladegeräten die seriellen Daten aus. Und da können eben bei einer Liveaufzeichnung schon zig tausend Punkte anfallen.

Nuja, aber die Frage bleibt donnoch fast die gleiche ...
Hat jemand ein Stück Code für die ganzen tollen Fachbegriffe die hier heute schon gefallen sind?

[moelski]

Nachtrag:

Was mir gerade einfällt .. Einen Haken hat die Filterung aber. Wenn man in die Kurve reinzoomt kann man nicht mehr die Einzelheiten erkennen.

[marabu]

Hallo Dominik,

fertigen Code habe ich leider keinen für dich, aber er sollte nicht allzu schwer zu erstellen sein. Hier eine kleine Starthilfe:

Delphi-Quellcode:

function PDCompress(const Data: TIntegerDynArray; iDist: Integer): TIntegerDynArray;
var
  i, n: Integer;
begin
  SetLength(Result, Length(Data));
  Result[0] := Data[0];
  n := 1;
  for i := Succ(Low(Data)) to Pred(High(Data)) do
    if Distance(Data[i], Data[Pred(i)], Data[Succ(i)]) > iDist then
    begin
      Result[n] := Data[i];
      Inc(n);
    end;
  Result[n] := Data[High(Data)];
  SetLength(Result, Succ(n));
end;

Da ein solcher Filter die Originaldaten nicht verändert kannst du ihn bei verändertem Viewport einfach nochmal anwenden.

Freundliche Grüße

[alzaimar]

Zitat von moelski:

Zitat:

Erwartet von Steema keine Wunder, dafür gibt es andere Firmen.

Das geht schon. Man muss nur die FastLine Serie nutzen. Dann sind 20000 Punkte Peanuts ...

Du will ja glätten. Darum gehts. Fastline ist wirklich 'Fast'. Aber beim Glätten muss man zu anderen Mitteln greifen.

Zitat von moelski:

Also, wir werten von Ladegeräten die seriellen Daten aus. Und da können eben bei einer Liveaufzeichnung schon zig tausend Punkte anfallen.

Ah... Lange Zeit langweilige Daten (schön glatt) und dann unerwartete Peaks (I.)?
Oder nur zitternde, aber im Wesentlichen 'artige' Messwerte (die also irgendwie einer Kurve folgen) (II)?

I: Nimm den Vorschlag von Marabu, oder eine polynomiale oder exponentielle/logarithmische Regression über die letzten 10 Punkte, damit bekommt man die Peak-Flanken ordendlich hin und das Bild wird kaum verfälscht.

II: Bilde den Mittelwert aus jeweils X (z.B. X=100) Punkten.

Zitat von moelski:

Was mir gerade einfällt .. Einen Haken hat die Filterung aber. Wenn man in die Kurve reinzoomt kann man nicht mehr die Einzelheiten erkennen.

Welche Einzelheiten? Die Kunst der Filterung besteht darin, die langweiligen Bereiche rauszuschmeissen und nur die interessanten Teile zu behalten. Wozu eine Gerade mit 1000000 Punkten beschreiben, wo doch auch 2 reichen? Oder willst Du unbedingt das Rauschen aufzeichnen?

marabus Code reicht als Starthilfe allemal aus.

[generic]

Macht es überhaupt Sinn 20000 Punkte in einen Chart zu tun, wenn der nur 1280 Punkte (Breite) zur Anzeige auf dem Bildschirm hat?

[moelski]

Moin !

Zitat:

Macht es überhaupt Sinn 20000 Punkte in einen Chart zu tun, wenn der nur 1280 Punkte (Breite) zur Anzeige auf dem Bildschirm hat?

Nein sicherlich nicht. Allerdings wenn man live Daten im halb Sekundetakt reinbekommt und das über Stunden hinweg, dann müsste man ja entweder die Daten immer neu filtern, oder einen so inteligenten Filter haben, der eben nur das hinterste Ende der Daten gebutachtet.

Im Moment haben wir aber keinen solchen Filter. Und darum werden im Moment noch alle Punkte eingetragen. Was wir im Moment nur haben ist eine Reduktion. Dabei wird z.B. nur jeder 10te Punkt gezeichnet. Das bringt auch schon deutliche Entspannung. Ist aber sicherlich nur ein Behelf.