Laden...

Algorithmus um Kurve (eine Liste von Punkten) zu komprimieren

Erstellt von michlG vor 13 Jahren Letzter Beitrag vor 13 Jahren 6.163 Views
michlG Themenstarter:in
3.430 Beiträge seit 2007
vor 13 Jahren
Algorithmus um Kurve (eine Liste von Punkten) zu komprimieren

Hallo zusammen,

ich habe momentan ein ziemlich nerviges Problem.
Vor einiger Zeit habe ich ein kleines Benutzersteuerelement geschrieben dass verschiedene Funktionen bereitstellt um Daten in einem Chart darzustellen.

Klappt auch ganz gut, aber jetzt beklagten sich die Benutzer über eine angeblich schlechte Performance.
Der Grund dafür ist dass pro Linie bis zu 15.000 Punkte übergeben wurden.
Und bei 20 Linien kommt man damit auf 300.000 Punkte was natürlich das Charting-Control etwas überlastet 😉

Ich suche also einen Algorithmus der mir die 15.000 Punkte (immer DateTime mit double Paar) auf 1000 Punkte zusammenfasst.
Dabei sollte aber noch die grobe Grundstruktur der Linie erhalten bleiben.

Mittlerweile habe ich schon einiges versucht, aber der Mathematiker in mir will nicht wirklich aufkommen.
z.B: hab ich einfach immer X Punkte zu einem zusammengefasst indem ich den Mittelwert genommen habe.
Das war danach auch schön schnell aber die Linien wurden extrem verfälscht.
Zudem hab ich versucht den Min/Max-wert von den einzelnen Bereichen zu behalten und dann vom Rest den Mittelwert zu bilden -> resultat: gleich schlimm wie beim normalen Durchschnitt.

Kennt evtl. jemand einen Algorithmus mit dem die Linie nicht so extrem verfälscht werden würde?
Details sollen verschwinden aber die Grundstruktur sollte erkennbar bleiben 😃

Vielen Dank im Voraus

Gruss
Michael

Hier noch ein kleines Beispielbild. Oben die Unkomprimierte Version und unten die Komprimierte Version. Wie man sieht erkennt man fast nicht dass es sich um die selben Daten handelt. Es handelt sich um Werte einer Maschine und ab und an gibt es da größere Abweichungen welche man oben aufgrund der vielen Punkte nicht sieht. Unten jedoch sind die gut sichtbar.
Kurz gesagt soll es ähnlich ausschauen wie oben aber mit viel weniger Punkten 😃

6.911 Beiträge seit 2009
vor 13 Jahren

Hallo,

ev. wäre eine Medianfilterung (ein Rangordnungsfilter) passend. Über die Filterlänge kann eingestellt werden wie fein oder grob. Wenn eine lokale Störung von n Abtastwerten ausgefiltert werden soll muss der Filter 2n+1 lang sein.

Edit: Filtern alleine behält natürlich die Anzahl der Werte bei*. Daher auch ein Ersetzen der Werte im Fenster des Filters durch den Ausgabewert des Filters um eine Reduktion zu erreichen.

* In nachstehender Impl. wird dies erreicht indem die Anfangswerte gespiegelt werden.
Für den Medianfilter verwende ich folgende (nicht optimierte) Version:


using System;
using System.Collections.Generic;
using System.Linq;

namespace gfoidl.Signalprocessing.Filter.NonLinear
{
	/// <summary>
	/// Stellt einen Median-Filter dar.
	/// </summary>
	/// <remarks>
	/// Median-Filter sind eine gute Wahl zum Ausfiltern von Ausreißern (auch
	/// Spikes genannt).
	/// <para>
	/// Für das Ausfiltern einer Störung von n Abtastwerten der Stichprobe
	/// muss die Filterlänge 2n+1 sein.
	/// </para>
	/// </remarks>
	/// <seealso cref="MovingAverageFilter"/>
	public class MedianFilter : NonLinearFilter
	{
		/// <summary>
		/// Erstellt eine Instanz eines Median-Filters.
		/// </summary>
		/// <param name="filterLength">
		/// Die Filterlänge. Es muss eine ungerade Zahl übergeben werden.
		/// </param>
		/// <exception cref="ArgumentException">
		/// <paramref name="filterLength"/> ist keine ungerade Zahl oder 
		/// ist &lt; 3
		/// </exception>
		public MedianFilter(int filterLength) : base(filterLength) { }
		//---------------------------------------------------------------------
		/// <summary>
		/// Die Strategie mit der die Daten gefiltert werden sollen.
		/// </summary>
		/// <param name="sequence">
		/// Die Daten welche vom Filterfenster erfasst sind.
		/// </param>
		/// <returns>Den gefilterten Wert.</returns>
		protected override double FilterOperation(IEnumerable<double> sequence)
		{
			List<double> sort = sequence.ToList();
			sort.Sort();
			int n = sort.Count;

			if (n % 2 == 0)
				return (sort[n / 2 - 1] + sort[n / 2]) * 0.5;
			else
				return sort[(n - 1) / 2];
		}
	}
}


using System;
using System.Collections.Generic;
using System.Linq;

namespace gfoidl.Signalprocessing.Filter.NonLinear
{
	/// <summary>
	/// Stellt die Basisimplementierung eines nichtlinearen Filters
	/// bereit.
	/// </summary>
	/// <remarks>
	/// Nichtlineare Filter schließen die Gruppe der Rangordnungsfilter ein.
	/// </remarks>
	public abstract class NonLinearFilter : IFilter
	{
		/// <summary>
		/// Die Filterlänge.
		/// </summary>
		public int FilterLength { get; private set; }
		//---------------------------------------------------------------------
		/// <summary>
		/// Erstellt eine Instanz des nichtlinearen Filters.
		/// </summary>
		/// <param name="filterLength">
		/// Die Filterlänge. Es muss eine ungerade Zahl übergeben werden.
		/// </param>
		/// <exception cref="ArgumentException">
		/// <paramref name="filterLength"/> ist keine ungerade Zahl oder 
		/// ist &lt; 3
		/// </exception>
		protected NonLinearFilter(int filterLength)
		{
			if (filterLength % 2 == 0)
				throw ExceptionHelper.Argument(
					() => filterLength,
					"Der Wert muss eine ungerade Zahl sein.");

			if (filterLength < 3)
				throw ExceptionHelper.Argument(
					() => filterLength,
					"Der Wert muss größer als 3 sein.");
			//-----------------------------------------------------------------
			this.FilterLength = filterLength;
		}
		//---------------------------------------------------------------------
		/// <summary>
		/// Filtert die Werte.
		/// </summary>
		/// <param name="values">Die zu filternden Werte.</param>
		/// <returns>Gefilterte Werte.</returns>
		/// <exception cref="ArgumentNullException">
		/// <paramref name="values"/> ist <c>null</c>.
		/// </exception>
		/// <exception cref="ArgumentException">
		/// <paramref name="values"/> ist <c>null</c>, eine leere Menge oder
		/// die Anzahl der Elemente kleiner als die Filterlänge.
		/// </exception>
		/// <remarks>
		/// Der Filter spiegelt die Anfangs- und Endwerte so dass die Anzahl
		/// der Elemente in der Stichprobe erhalten bleibt. Üblicherweise würde
		/// bei Filtern die Anzahl N-(Filterlänge-1) betragen. Das ist hier
		/// aufgrund des ausgeklügelten Spiegelverfahrens nicht der Fall.
		/// </remarks>
		public IEnumerable<double> Filter(IEnumerable<double> values)
		{
			if (values == null)
				throw ExceptionHelper.ArgumentNull(() => values);

			int n = values.Count();

			if (n == 0)
				throw ExceptionHelper.NoElements(() => values);

			if (n < this.FilterLength)
				throw ExceptionHelper.Argument(
					() => values,
					"Die Anzahl der Elemente darf nicht kleiner als die " +
					"Filterlänge sein.");
			//-----------------------------------------------------------------
			// Offset aus der Filterlänge berechnen:
			int offset = (this.FilterLength - 1) / 2;

			// Tipp: Aufzeichnen um die Indextransformation besser zu 
			// verstehen.
			// +---+---+---+---+---+---+----
			// | 0 | 1 | 2 | 3 | 4 | 5 | ...
			// +---+---+---+---+---+---+----
			// Da der Filter symmetrisch zum betrachteten Abtastpunkt ist
			// müssen die ersten Werte der Stichprobe gesondert behandelt
			// werden. Hier werden so viele Folgewerte am Abtastpunkt 
			// gespiegelt so dass sich ein volles Fenster ergibt. Der Median
			// sortiert die Werte -> dies erleichtert die Auswahl der Elemente
			// denn es muss keine Rücksicht auf die Ordnung genommen werden.
			// Die Werte ungefiltert zurückgeben ist nicht sinnvoll denn
			// es könnte ja der erste Punkt bereits ein Spike sein.
			for (int i = 0; i < offset; i++)
			{
				// Sequenz mit aktuellem Element + Folgeelementen:
				var q1 = values.Skip(i).Take(offset + 1);

				// Werte vor dem aktuellen Element (sofern vorhanden):
				var q2 = values.Take(i);

				// Werte die gespiegelt werden:
				var q3 = values.Skip(i + 1).Take(offset - i);

				// Filterung:
				yield return FilterOperation(q1.Concat(q2).Concat(q3));
			}

			// Über alle Werte der Stichprobe iterieren. Die Daten welche
			// vom Filterfenster erfasst werden werden dann symmetrisch 
			// zum betrachteten Abtastpunkt ausgewählt. Daher muss bei der
			// oberen Schranke die Filterlänge berücksichtigt werden.
			// Der Median sortiert die Daten -> daher muss keine Rücksicht
			// auf die Ordnung der Elemente während der Auswahl getroffen
			// werden. Wichtig ist nur dass alle Elemente im Filterfenster
			// ausgewählt werden.
			for (int i = 0; i < n - this.FilterLength + 1; i++)
				yield return FilterOperation(values
					.Skip(i)
					.Take(this.FilterLength));

			// Wie die Startwerte müssen die letzten Werte gesondert behandelt
			// werden. Es werden alle möglichen Werte genommen und dann
			// wird das Fenster mit den gespiegelten Werten vor dem aktuellen
			// Abtastpunkt aufgefüllt.
			for (int i = values.Count() - offset; i < values.Count(); i++)
			{
				// Sequenz mit dem aktuellen Element + Vorherelemente:
				var q1 = values.Skip(i - offset).Take(offset + 1);

				// Werte nach dem aktuellen Element (sofern vorhanden):
				var q2 = values.Skip(i + 1).Take(values.Count() - i - 1);

				// Werte die gespiegelt werden:
				int remaining = this.FilterLength - q1.Count() - q2.Count();
				var q3 = values.Skip(i - remaining).Take(remaining);

				// Filterung:
				yield return FilterOperation(q1.Concat(q2).Concat(q3));
			}
		}
		//---------------------------------------------------------------------
		/// <summary>
		/// Die Strategie mit der die Daten gefiltert werden sollen.
		/// </summary>
		/// <param name="sequence">
		/// Die Daten welche vom Filterfenster erfasst sind.
		/// </param>
		/// <returns>Den gefilterten Wert.</returns>
		protected abstract double FilterOperation(IEnumerable<double> sequence);
	}
}

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

C
401 Beiträge seit 2007
vor 13 Jahren

Versuch doch einfach die Punkte genau dann zusammenzufassen, wenn viele Aufeinanderfolgende einen ähnlichen Wert haben, dann verhinderst du die grobe Verfälschung, sondern hast nur noch eine minimale Abweichung des urspünglichen Graphen.

3.170 Beiträge seit 2006
vor 13 Jahren

Hallo,

... pro Linie bis zu 15.000 Punkte übergeben wurden.

über welchen Zeitraum erstrecken sich denn die 15000 Werte?
Ich meine , stellt das Bild das komplette Control dar, oder erstreckt sich das noch (viel) weiter nach rechts?

Denn das Bild hat in er Breite ja mal gerade 786px, das heisst auf jeden Pixel würden etliche Punkte gezeichnet, die gehen ja schon allein durch die Auflösung flöten.

Es dürfte ja nicht allzu schwierig sein zu ermitteln, welche Punkte ohnehin auf den selben Pixel der Zeitachse fallen.
Vielleicht reicht es ja, diese Werte zu mitteln und dann wirklich nur für jeden tatsächlich vorhandenen Pixel auf der Zeitachse diesen Mittelwert darzustellen.

Gruß, MarsStein

Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca

1.373 Beiträge seit 2004
vor 13 Jahren

Hier noch ein kleines Beispielbild. Oben die Unkomprimierte Version und unten die Komprimierte Version. Wie man sieht erkennt man fast nicht dass es sich um die selben Daten handelt. Es handelt sich um Werte einer Maschine und ab und an gibt es da größere Abweichungen welche man oben aufgrund der vielen Punkte nicht sieht. Unten jedoch sind die gut sichtbar.
Kurz gesagt soll es ähnlich ausschauen wie oben aber mit viel weniger Punkten 😃

Ich bin etwas verwirrt. Für mich sieht das Bild oben komprimiert aus, das Bild unten unkomprimiert, weil es viel mehr Details enthält. Oder verstehe ich was falsch?

Vielleicht (bestimmt) overkill, aber trotzdem zur Information: um z.B. kleine Änderungen (= hohe Frequenzen) herauszufiltern könntest du eine Fourier-Transformation machen, aus dem Spektrum die hohen Frequenzen herausnehmen und dann wieder zurücktransformieren. Sowas macht auch z.B. ein MP3 Encoder.

Grüße,
Andre

T
327 Beiträge seit 2006
vor 13 Jahren

Hallo,

ich hatte mal ein ähnliches Problem, siehe Algorithmus zur Datenaufbereitung für Diagrammdarstellung

In der Zwischenzeit habe ich eine zugekaufte Charting-Komponente verwendet, die bis zu 1 Million Datenpunkte relativ problemlos anzeigen kann.

Inzwischen habe ich aber mit Hilfe eines Mathematikers etwas gefunden, das sich "Swinging Door Algorithmus" (einfach Googlen) nennt, der perfekt für genau diesen Zweck funktioniert (Ist eigentlich eine Methode zur Datenkompression)

--> Reduktion von ca. 50000 Datenpunkten auf 3000 ohne ein einziges Pixel Unterschied auf der Grafik. Mit den Parametern muss man je nach Art der Daten dann etwas spielen... Wahrscheinlich kann man noch etwas weiter runtergehen und dennoch einen sehr guten Verlauf erzielen...

michlG Themenstarter:in
3.430 Beiträge seit 2007
vor 13 Jahren

Hallo Leute,

erstmal vielen Dank für die zahlreichen Antworten.

@gfoidl: Danke für den Code, das werd ich ausprobieren

@corpsegrinder: Danke für den Tipp, das hab ich jetzt mal versucht und ein viel viel besseres Ergebnis erzielt. Mit ein paar Verfeinerungen wäre das schon mehr als ausreichend

@MarsStein: Theoretisch wäre das kein Problem wenn man die Kurven selbst zeichnet, aber ich verwende das Charting-Control von Syncfusion. Und dabei hau ich einfach die Daten rein und das Control zeigt sie an. Deshalb hab ich da keinen Eingriff

@VizOne: Das obere ist schon das unkomprimierte Bild, das ist sicher.
Ich habe auch nicht ganz verstanden wieso er mir bei der komprimierten Variante diese Spitzen darstellt. Durch das Berechnen des Durchschnittwertes müssten eigentlich die Spitzen wegfallen... Da war wohl irgendwo ein Bug in meinem Algorithmus versteckt..

Vielleicht (bestimmt) overkill, aber trotzdem zur Information: um z.B. kleine Änderungen (= hohe Frequenzen) herauszufiltern könntest du eine Fourier-Transformation machen, aus dem Spektrum die hohen Frequenzen herausnehmen und dann wieder zurücktransformieren. Sowas macht auch z.B. ein MP3 Encoder.

Ja ist wirklich etwas overkill 😃

@telnet: Thx für den Tipp, das werde ich mir mal angucken.
PS: Was hast du für eine Charting-Komponente gekauft? Weil das Syncfusion Ding braucht eine Minute um 100.000 Punkte darzustellen und benötigt dabei 1GB RAM!

Aber mittlerweile bin ich schon dabei das ganze Syncfusion Zeug aus meinen Programmen zu entfernen. Grund dafür sind unglaublich viele Bugs welche zwar nach genauer beschreibung schnell gefixt werden, aber beim nächsten größeren Update kommen die alten Bugs wieder ans Tageslicht und dazu noch X neue!

Vielen Dank euch allen

Gruss
Michael

//EDIT:
Ich habe es jetzt mit corpsegrinders vorschlag gemacht. Relativ einfach und das Ergebnis ist gut

T
327 Beiträge seit 2006
vor 13 Jahren

Wenn du die Daten transformierst, filterst und danach wieder zurücktransformierst bekommst du aber doch auch wieder die gleiche Anzahl Datenpunkte, nur das "Gezappel" des Graphen wird geringer, oder?

Ich persönlich habe bisher immer nur die Komponenten von DevExpress eingesetzt.. bin vor allem mit dem Support sehr zufrieden (wirkliche Bugs werden i.d.R. in weniger als einer Woche gefixt) und die Performance ist größtenteils auch wirklich gut.

michlG Themenstarter:in
3.430 Beiträge seit 2007
vor 13 Jahren

Hallo,

Wenn du die Daten transformierst, filterst und danach wieder zurücktransformierst bekommst du aber doch auch wieder die gleiche Anzahl Datenpunkte, nur das "Gezappel" des Graphen wird geringer, oder?

Nö, dadurch hab ich viel weniger Punkte.

Kurz gesagt hab ich folgenden Code:
Hier gibt es noch ein paar kleinere Anpassungen mit der ich es ein bisschen einstellen kann wie die Daten zusammengefügt werden.


int maxCombine = 0;
double initialValue = values[0];

for (int i = 1; i < values.Count; i++)
{
	var abweichung = (values[i] * 0.01) * Diagramm.KomprimierungMaxAbweichung;
	if (maxCombine < Diagramm.KomprimierungMaxNebeneinander && initialValue < values[i] + abweichung && initialValue > values[i] - abweichung)
	{
		if (maxCombine == 0)
		{
			initialValue = values[i];
		}

		values[i - 1] = (values[i - 1] + values[i])  * 0.5;
		values.RemoveAt(i);
		dateTimes.RemoveAt(i);
		i--;
		maxCombine++;
	}
	else
	{
		maxCombine = 0;
		initialValue = values[i];
	}
}

Er geht also die Punkte der Reihe nach durch und vergleicht den aktuellen wert mit dem vorherigen. Wenn diese beiden nicht mehr als 10% voneinander abweichen dann werden diese zusammengefügt.
Im nächsten Schritt beginnt das selbe spiel mit dem nächsten punkt.
Beendet wird das Ganze wenn man am Ende der Liste ist.

Gruss
Michael

T
327 Beiträge seit 2006
vor 13 Jahren

Ich hätte vielleicht dazuschreiben sollen, dass ich die Fourier-Transformation gemeint habe....

6.911 Beiträge seit 2009
vor 13 Jahren

Hallo Michael,

wenn bei deinem Ansatz noch Spikes (= Ausreißer = lokalisierte Störung) in Folge von Messfehlern, etc. ausgefiltert werden sollen dann wärs genau mein obiger Ansatz 😉

Da du viele Messwerte hast erstetz in deinem Code noch /100 durch *0.01 und /2 durch *0.5 -> ist schneller, denn der Compiler kapiert das nicht von selbst (und diese Optimierung ist auch nicht "premature" 😉

Hallo telnet,

Wenn du die Daten transformierst, filterst und danach wieder zurücktransformierst bekommst du aber doch auch wieder die gleiche Anzahl Datenpunkte, nur das "Gezappel" des Graphen wird geringer, oder?

So ist es. Daher wird beim erwähnten MP3 auch eine Art Wavelt-Kompression verwendet. D.h. vereinfacht ausgedrückt wird das Gesamtsignal in Teile zerlegt und von jedem Teil werden nicht mehr die Abtastwerte der Amplitude gespeichert sondern nur die Parameter der Wavelet-Funktion und der zeitliche Ort. Somit lässt sich durch Umkehrung das Signal fast wieder Original herstellen. Vor der Komprimierung werden jedoch mittels FFT-Filter die Teile ausgefilter die der Mensch eh nicht wahrnehmen kann (-> "Rohdatenreduktion" vor der Komprimierung).

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

michlG Themenstarter:in
3.430 Beiträge seit 2007
vor 13 Jahren

Hallo,

wenn bei deinem Ansatz noch Spikes (= Ausreißer = lokalisierte Störung) in Folge von Messfehlern, etc. ausgefiltert werden sollen dann wärs genau mein obiger Ansatz 😉

Nö, ich weiss auch nicht ob das wirklich Messfehler sind, oder ob diese Spitzen so gehören.
Mir wurden nur die Daten zum Testen gegeben, und falls es Messfehler sind dann sollen die Benutzer meines Controls selbst filtern 😃
Aber vielen Dank für den Tipp.

Da du viele Messwerte hast erstetz in deinem Code noch /100 durch *0.01 und /2 durch *0.5 -> ist schneller, denn der Compiler kapiert das nicht von selbst (und diese Optimierung ist auch nicht "premature" 😉

Hab gar nicht gewusst dass unser Compiler so doof ist 😃
Jedenfalls hab ich es jetzt angepasst. Thx

Gruss
Michael