sin oder -sin in einer verrauschten Kurve finden

[ogni42]

Hmm, zuerst würde ich die Daten über einen (moderaten) Tiefpass filtern.

Eine Zeitreihe der Lenkwinkelauslenkungen korrespondiert ja mit einer entsprechenden Zeitreihe für die Geschwindigkeit.

Jetzt nimmst Du zum Vergleich möglichst Vektoren (=Zeitreihen) gleicher Länge, ansonsten wird die Klassifikation etwas schwieriger. Also z.B. 101 Elemente für Lenkwinkel und Geschwindigkeit. Aus der kontinuierlich aufgenommenen Datenreihen kannst Du Dir dann die Punkte heraussuchen, bei denen der Lenkwinkel einen Extremwert hat (dafür braucht es dann den entsprechenden Tiefpass auf den Eingangsdaten, sonst bekommst Du zuviele Kandidaten). Das wäre dann der Mittelpunkt für einen solchen Vektor (mit dann jeweils 50 Elementen davor und dahinter).

Zur Klassifikation kannst Du dann die Vektoren für Winkel und Geschwindigkeit einfach hintereinander hängen. Du hast also jeweils einen langen (z.B. 202 Elemente langen) Merkmalsvektor.

Sofern Du genügend Beispiele hast (Positive = Spurwechsel und Negative = Kein Spurwechsel) kannst Du damit einen Klassifikator bauen. Als einfachstes käme ein k-Nearest Neighbour in Frage, bessere Ergebnisse wirst Du aber wahrscheinlich mit einem LVQ oder RBF Netz erzielen können (Aus meiner Erfahrung liefern RBF Netze mit LVQ als erster Schicht tendenziell die besseren Ergebnisse).

Bei allen drei Verfahren ist es sinnvoll, nicht nur zwei Klassen (Spurwechsel ja/nein) zu wählen, sondern z.B. jeweils vier, damit die Aufteilung des Merkmalsraumes feiner stattfindet. Hintergrund ist, dass mit einem solchen Klassifikator ein n-dimensionaler Merkmalsraum in n-Klassen aufgeteilt wird. Beispiel für 2-Dimensionen: Wenn Du nur zwei Klassen hast, kannst Du den 2-D Raum nur in 2 Halbebenen teilen. Nimmst Du mehr Klassen, gehen auch komplexere Polygone ( http://de.wikipedia.org/wiki/Voronoi ).

Der Umkehrschluss: "Dann nehme ich eben jeweils 100 Klassen" ist auch nicht so sinnvoll, da der Klassifikator dann:
a) sehr lange zum Training braucht
b) oftmals nicht mehr so gut generalisiert

[BiGF00T]

Wow, das was viel Input auf einmal...

Hmm, zuerst würde ich die Daten über einen (moderaten) Tiefpass filtern.

Also den Tiefpass brauche ich wohl nur, um die Daten ein wenig zu glätten, oder? Also reicht es vermutlich aus, einfach einen Mittelwert der jeweils letzten X Werte zu bilden oder so.

Eine Zeitreihe der Lenkwinkelauslenkungen korrespondiert ja mit einer entsprechenden Zeitreihe für die Geschwindigkeit.

Ja, das sollte so sein.

Jetzt nimmst Du zum Vergleich möglichst Vektoren (=Zeitreihen) gleicher Länge, ansonsten wird die Klassifikation etwas schwieriger. Also z.B. 101 Elemente für Lenkwinkel und Geschwindigkeit. Aus der kontinuierlich aufgenommenen Datenreihen kannst Du Dir dann die Punkte heraussuchen, bei denen der Lenkwinkel einen Extremwert hat (dafür braucht es dann den entsprechenden Tiefpass auf den Eingangsdaten, sonst bekommst Du zuviele Kandidaten). Das wäre dann der Mittelpunkt für einen solchen Vektor (mit dann jeweils 50 Elementen davor und dahinter).

Ok, das mit dem Vektor habe ich jetzt nicht genau verstanden... Ich speichere mir 101 Werte (Elemente) meines Lenkwinkels ab und Suche einen Extremwert. Hier mal nen Hochpunkt. Dieser stellt dann den Mittelpunkt meines Vektors dar.
Sowas?
Bild hier  

Oder eher sowas?
Bild hier  

Oder ganz anders?

Zur Klassifikation kannst Du dann die Vektoren für Winkel und Geschwindigkeit einfach hintereinander hängen. Du hast also jeweils einen langen (z.B. 202 Elemente langen) Merkmalsvektor.

Sofern Du genügend Beispiele hast (Positive = Spurwechsel und Negative = Kein Spurwechsel) kannst Du damit einen Klassifikator bauen. Als einfachstes käme ein k-Nearest Neighbour in Frage, bessere Ergebnisse wirst Du aber wahrscheinlich mit einem LVQ oder RBF Netz erzielen können (Aus meiner Erfahrung liefern RBF Netze mit LVQ als erster Schicht tendenziell die besseren Ergebnisse).

Bei allen drei Verfahren ist es sinnvoll, nicht nur zwei Klassen (Spurwechsel ja/nein) zu wählen, sondern z.B. jeweils vier, damit die Aufteilung des Merkmalsraumes feiner stattfindet. Hintergrund ist, dass mit einem solchen Klassifikator ein n-dimensionaler Merkmalsraum in n-Klassen aufgeteilt wird. Beispiel für 2-Dimensionen: Wenn Du nur zwei Klassen hast, kannst Du den 2-D Raum nur in 2 Halbebenen teilen. Nimmst Du mehr Klassen, gehen auch komplexere Polygone ( http://de.wikipedia.org/wiki/Voronoi ).

Der Umkehrschluss: "Dann nehme ich eben jeweils 100 Klassen" ist auch nicht so sinnvoll, da der Klassifikator dann:
a) sehr lange zum Training braucht
b) oftmals nicht mehr so gut generalisiert

Ok, das mit vielen Beispielen muss ich erst noch sehen... Ich habe einiges an Daten, aber leider sind in diesen so gut wie keine bis gar keine Spurwechsel vorhanden aber das muss ich noch sehen.
Danke schonmal für die Hilfe. Auch wenn ich noch nicht alles verstanden habe und vieles möglicherweise auch nicht richtig...

[SprinterSB]

Eigentlich müsste ich ja nur das über und unter der Nulllinie zusammenzählen und ca 0 rausbekommen, oder?

Ja, wenn in dem Intervall keine netto-Änderung der Richtung bzw. Transversalgeschwindigkeit passiert. Aber es kann auch eine netto-Änderung sein, stwa ein Spurwechsel in einer langgezogenen Kurve.

Prinzipiell kannst du aus den daten nur bestimme Bewegungen der Fahrzeugs lesen. Ab eine Bewegung ein Spurwechsel ist, steht aber auf nem ganz anderen Blatt. Genausogut könnte die Straße nen leichten Versatz haben, wie es bei Baustellen oft der Fall ist...

Deine Version scheint aber wesentlich mehr zu können als nur zusammenzählen...
Ich habe leider gerade nur eine uralt-Version von Mozilla zur Verfügung, wo die untere f(x) Zeile komplett abgeschnitten wird. Ich kann gerade noch den oberen Rand des Eingabefelds sehen

Mit den Layoutmanagern stehe ich seit je her auf Kriegsfuß. Ich hab das Applet einfach mal größer gemacht, vielleicht hilft das schon, damit das Feld nicht mehr umgebrochen wird? Ansonsten einfach ein f(x) eintippen und "Reload".

Also wenn ich das mit diesem farbigen Bild richtig deute, meintest du, dass nach oben hin das Fenster größer wird und nach unten hin kleiner, richtig?

Jepp.

[...] und wahrscheinlich nicht mal extrem rechenintensiv. Wenn ich das richtig sehe, ist ein Integral ja nichts weiter als die Fläche unter der Kurve, also reicht es bei einem normalen Zeitintervall die einzelnen "Rechteckchen" zusammenzuzählen. f(x) + f (x+1) + ... + (f+n)

Ich hatte von -n bis n integriert. Das Integral über ein Fenster zu berechnen ist recht einfach (Ich nehme nur die Simpson-Regel).

Da die Daten Lenkpositionen sind, ist das F(x,y) ein Maß für die Quergeschwindigkeit, die im Zeitintervall y um den Zeitpunkt x erzielt wird.

Der ganze ich erstaunlich unempfindlich gegen Rauschen, in den Bildern ist es kaum zu erkennen. Allerdings müsste man die Daten noch weiter verarbeiten.

Es sieht auch nicht so aus, als ob man einen Tiefpass bräuchte, bzw den Tiefpass bekommt man implizit, indem man die Fensterbreite passend (nicht zu klein) wählt. Ein Tiefpass macht in Endeffekt auch nichts anderes, als f(x) zu ersetzen durch
\int_{x-a}^{x+a} f(t)*q(t-x)*dt / \int_{-a}^a q(t)*dt

Und das Integral haben wir eh

Im Ende wirst du aber an einer Auswertung, wie Ogni sie genannt hat, nicht vorbeikommen... Evtl auch mit Verfahren, wie die in der Bildverarbeitung benutzt werden, um Linien etc zu finden?

Evtl ist es auch sinnvoll, den Datensatz auf die über dem maximal betrachteten Fenster geschehene Richtungsänderung zu normieren (in dem F-Bild mitte oben), so daß an der Stelle immer eine 0 steht. Den Offset nimmt man als Geschwindigkeitsänaderung und sucht in dem "bereinigten" F nach Wechseln

[BiGF00T]

*Ogni42 & SprinterSB hit BiGF00T with Magical Mathematics Lvl 666 -> HIT, inflicting 10000 pts brain damage*
*BiGF00T backs off to charge his mighty Elementary School Math Lvl 0 -> MISS*
*BiGF00T dies of Math overdose*
*Ogni42 & SprinterSB loot 1xElemetary Math book, 100x Gold, 100x useless electronic device*
...
Da mein Intervall ja relativ groß ist (20 ms) und ein normaler Spurwechsel wohl nicht mehr als 5s (oder doch?) braucht, müsste ich dann theoretisch 250 Werte speichern und integrieren. Wenn ich dann mein Fenster theoretisch 100 Werte breit mache, bekomme ich dann ein vernünftiges Ergebnis oder muss es immer mindestens so breit sein wie die Kurve selbst (also > 250)? Wenn ich das Fenster dann breiter mache, würde sich das negativ darauf auswirken, dass ich noch ruckartige Spurwechsel (nach 2s vorbei) finden würde?
Ok, also das mit dem Eingabefeld habe ich jetzt irgendwie gefixt (paarmal reload und irgendwann hat es, ohne erkennbaren Grund, funktioniert )
Muss ich das Fenster für jede Analyse so wie in dem Applet von klein nach groß variieren oder reicht mir eine geschickt gewählte Fenstergröße aus?
Wenn ich dann theoretisch eine solche Analyse durchgeführt habe, bekomme ich eine Linie mit (hier im Bild) grünen und roten Bereichen, die über die Zeit verteilt sind. Sollten jetzt grün und rot genau gleich groß sein, wäre somit ein Spurwechsel gefunden. (?)
Nochmal zum Verständnis der Diagramme des Applets:
Das Fenster geht einfach entlang der t-Achse und wenn die Fläche positiv ist, erscheint das rot, wenn die Fläche unverändert ist blau und bei negativer Fläche grün. Blau ist es dann, wenn sich beide gegeneinander aufheben, oder wenn es gar keine Fläche gibt?

EDIT:
Wie groß muss ich mir eigentlich das Fenster in diesen Applet-Screenshots vorstellen? Unten im Bild ein paar Werte groß und oben dann eine halbe Diagrammlänge? Lässt sich so etwas herausfinden?

EDIT2:
Was ich auch nicht genau verstehe ist, wie ich eure beiden Methoden kombinieren sollte... Vielleicht auch, weil ich Ogni42s noch nicht genau verstehe... Wenn ich jetzt mal ein Fenster nehmen und darin deine Methode anwenden würde und als Ergebnis erhalten würde, dass ich einen roten und einen grünen Bereich habe, sagt mir das dann, dass ich einen potentiellen Kandidaten für einen Spurwechsel habe und ich muss dann die Daten des Bereichs mit Ogni42s Methode mit meinen (noch nicht vorhandenen) Referenzdaten vergleichen?

[ogni42]

*Ogni42 & SprinterSB hit BiGF00T with Magical Mathematics Lvl 666 -> HIT, inflicting 10000 pts brain damage*
*BiGF00T backs off to charge his mighty Elementary School Math Lvl 0 -> MISS*
*BiGF00T dies of Math overdose*
*Ogni42 & SprinterSB loot 1xElemetary Math book, 100x Gold, 100x useless electronic device*

Ja, hm, dann nehmen Sie zwei Aspirin und kommen morgen wieder

Auf den Extremwert bin ich folgendermaßen gekommen:
Beim Spurwechsel schlägt man das Lenkrad erst langsam, dann stärker nach (o.B.d.A.) rechts ein und reduziert danach den Lenkwinkel wieder bis auf 0.

Dementsprechend sollte der Verlauf der Lenkwinkelfunktion sowas wie ein Sinus oder eine Parabel, oder .... sein (Daher ja der Name des Threads )

Die Tiefpassfilterung ist deswegen nötig, da ein Mensch normalerweise immer ein kleines bisschen nach Links und Rechts lenkt (ohne die Spur zu wechseln). Um jetzt die Kandidaten für einen Spurwechsel zu finden ist es einfacher, über eine tiefpassgefilterte Funktion zu laufen, da dann weniger Kandidaten auftauchen. Die Breite des Filters kann so gewählt werden, dass Du ein gewisses Zeitintervall abdeckst (z.B. 1s).

Die Filterung kann durch Faltung im Originalraum oder Multiplikation im Fourierraum erfolgen. Willst Du Vektoren aus dem Fourierraum zur Klassifikation heran ziehen, bietet sich die Filterung dort an, da das wesentlich Rechenzeit spart. Wie Sprinter geschrieben hat, kannst Du auch ein Frequenzfenster setzen (entspricht Rechtecktiefpass). Gaussfilter hat aber den Vorteil, dass weit entfernte Datenpunkte einen geringeren Beitrag liefern als - in Deinem Fall - zeitlich nahe Punkte.

Als Filter in der Zeitreihe empfiehlt sich ein Gauss, bzw. dessen Ableitung, da Du dann bei der Faltung schon die Ableitung des Signals heraus bekommst und dann nur noch nach Nullstellen (bzw. numerisch nahe Null) (1. Ableitung) im gefilterten Signal suchen musst. Dann kommst Du ohne FFT aus, was, wenn Du auch den korrespondierenden Geschwindigkeitsvektor auswerten willst, m.E. auch Sinn macht.

Um den Klassifikator kümmern wir uns dann später. Implementierungen (so Du das denn auf dem PC testen willst) findest Du in der LTILib (C++) ( www.techinfo.rwth-aachen.de, gibt's auch bei sourceforge).

[BiGF00T]

Ok, also soweit sieht es jetzt dann aus, dass ich wohl ein wenig falten werde. Ich habe gestern noch ein wenig die Faltung rekapituliert und gesehen, dass die garnicht so schlimm ist. Ich weiß nicht, woher meine Ängste davor kamen. Irgendwie hatte ich daran noch schlechte Erinnerungen von früher... Leider habe ich ein wenig zu lange über alten Unterlagen gesessen, weshalb heute auch Aspirin nicht mehr stark zur Besserung meines Denkvermögens beitragen können.
Fürs Erste werde ich mich mal ein wenig verkriechen, um herauszufinden, ob ich ein paar Beispiele für Spurwechsel in meinen Testdaten finden kann. Vielleicht kann ich daran dann schon ein wenig sehen, wie gut diese Sinus-Theorie wirklich war.
Sinus kam daher, dass ja ein Fahrer, wie du ja schon bemerkt hast, zuerst in eine Richtung einschlägt, dann wieder gerade wird - das Fahrzeug steht jetzt in einem bestimmten Winkel zur Spur - und dann diesen Winkel durch Lenken in die entgegengesetzte Richtung wieder ausgleichen muss. Dies erfolgt leider wie auch schon erwähnt leider in den seltensten Fällen gleichschnell/-stark. Ob das jetzt dann wirklich noch als Sinus zu bezeichnen ist, weiß ich nicht. Als ich den Thread startete, war ich noch der Meinung es wäre so... Langsam bin ich mir nichts mehr sicher, das nicht mindestens mathematisch bewiesen ist.

[ogni42]

Da fällt mir ein, dass ein Spurwechsel ja einen Nulldurchgang beim Lenkwinkel hat. Damit reicht Dir der Wendepunkt der Funktion ( f''(x) = 0 ), der leichter zu finden ist. Mit 2. Ableitung Gauss filtern (da f*g'' = f''*g) und dann nur nach Vorzeichenwechel suchen.

Ob das dann ein Sinus ist, oder irgend etwas anders geartetes ist eigentlich egal (sofern Du das nicht über fitting lösen willst).

[SprinterSB]

IMHO ist es egal, ob es genau ein Sinus ist oder nicht. Ob da Dellen drin sind oder ein Halb"welle" länger dauert als die andere kann ja durchaus sein und wirs in der Praxis auch so sein. Sinus, Fourier-Trafo u.ä. wie (F)FT, STFT, (F)WT, GT etc kann man gestrost vergessen (ausser evtl für'n Tiefpass, aber das geht einfacher, wie Ogni schon gesagt hat).

Bei der Verwendung von f' muss man sehr vorsichtig sein. Wie will man das berechen?? Angezeigt, um f' zu bekommen, ist ein numerischer Ausgleich (etwa Splines über ein geglättetes und entrauschtes differenzieren). Das ist sehr aufwändig zu berechnen. f' über Differenzenquotienten zu erhalten führt warscheinlich zur Bauchlandung, weil der Diff'quot-Operator stark aufrauht. Für f'' ist's nochmal extremer.

Das INtegral zu berechnen ist sehr einfach. Da die Daten eh verrauscht sind braucht man keine feinziselierten Algorithmen höherer Ordnung. Er reicht einfach Summation. Hast du in einem Feld
F[i] = \sum_0^i f_i
dann ist
F(i,y) = F[i+y]-F[i-y]

An F zu kommen ist also kein Problem -- weder algorithmisch noch von der Laufzeit her.

Wie groß muss ich mir eigentlich das Fenster in diesen Applet-Screenshots vorstellen? Unten im Bild ein paar Werte groß und oben dann eine halbe Diagrammlänge? Lässt sich so etwas herausfinden?

Wenn du mit der Maus über den Graphen fährst erscheinen im StatusBar des Brausers die Koordinaten (evtl erst nach "aktualisieren im Brauser). Mit zoom=1 läuft x von ca -30 bis 30. Zeile 1 (unten) des F-Fensters schaut von x-1 bis x+1. Zeile 2 von x-2 bis x+2, etc. Ausserhalb des sichtbaren bereiches wird f zu 0 angenommen.

[ogni42]

Bei der Bestimmung der Ableitung von f hilft ja gerade die Faltung:

f' muss man nicht kennen, da bei der Tiefpassfilterung f*g'' = f''*g gilt. Es kommt also in jedem Fall die zweite Ableitung des tiefpassgefilterten Signals raus.

Sofern man g'' als zweite Ableitung der Gaussfunktion nimmt, muss man die Breite des Faltungskerns aber groß genug wählen (IIRC reicht 8+1+8 Elemente auf jeden Fall, muss ich aber ggfs. mal nachschauen).

Da die Ableitung auf dem Tiefpassgefilterten Bild erfolgt ist das Rauschen auch schon reduziert.