Noise aus Datensätzen möglichst gut filtern?

Huhu Community,



ich versuche aktuell verrauschte Datensätze möglichst qualitativ zu bereinigen. Der genaue Anwendungszweck tut glaube ich nicht so ewig viel zur Sache, deshalb stelle ich das mal nur verkürzt dar: Eine Kamera mit stetig Bilder auf und aus den Bilddaten werden Lokalisationsmodelle erstellt, Objekte im Bild erkannt, Entfernung und andere Dinge zu Objekte berechnet.


Der Input besteht also aus 2- und 3-dimensionalen Ortsvektoren sowie direkten Entfernungs- und Gradschätzungen zu den einzelnen, erkannten Objekten im Bild.

Bis jetzt habe ich nur einen recht einfachen Algorithmus dafür geschrieben: Für jedes Objekt existiert zur Laufzeit, solange es auf mehreren Frames gesehen wird, ein Puffer. Von diesen gepufferten Datensätzen berechne ich Varianz und Mittelwert und bewerte anhand der Varianz, welcher Datensatz wahrscheinlich ein Ausreißer ist. Ausreißerdatensätze werden gelöscht, die verbleibenden Datensätze bekommen anhand verschiedener Faktoren (wie sicher ist der Datensatz, ist das Bild verschwommen, usw. usf.) ein Rating und mit den Ratings wird dann ein gewichteter Mittelwert gebaut.

Das Verfahren funktioniert ganz gut, selbst kleinere Gegenstände haben so auf 2-4m Entfernung tatsächlich recht stabile Daten was Ortsvektoren, Entfernung, Gradzahl usw. angeht. Allerdings ist das ganze durchaus ausbaufähig.

Damit kommen wir zu meinem Problem: Mathematik an sich ist selbstverständlich kein Problem, allerdings habe ich mich weder im Abitur noch im Studium noch sonst irgendwann mit Statistik oder Stochastik befasst.
D.h. auf meiner bisherigen Suche habe ich größtenteils wissenschaftliche Papers gefunden oder Fachbücher, die für einen Anfänger auf dem Gebiet der Datenfilterung recht schwer zu verstehen waren.
Außerdem kenne ich bis jetzt keine der eleganteren Verfahren für solche Zwecke, was es für mich sehr schwer macht, ein geeignetes Verfahren zu suchen, da die Auswahl offensichtlich sehr groß ist.

Ich habe beispielsweise versucht, per LDA (linear discriminant analysis) die Daten in den Puffern zu clustern, nach guten Datensätzen und Ausreißern, das hat bis jetzt aber leider nicht vernünftig funktioniert. Sicherlich liegt das an meinem aktuell auf dem Gebiet recht beschränktem Verständnis, aber es gibt ja bestimmt ohnehin noch klügere Herangehensweisen, also z.B. besser geeignete Verfahren?

Was ich benötige: Wäre zum einen eine grobe Übersicht (am besten mit Erklärung), was geeignete Standardverfahren für mein Vorhaben sind und zum anderen eventuell noch kleine "Erfahrungsberichte", worauf man bei den einzelnen Verfahren z.B. besonders achten sollten.

Literatur: Ich wäre sehr dankbar, wenn man mir (vorzugsweise einsteigerfreundliche) Fachliteratur empfehlen könnte. Tutorials, Fachbücher...bisher hab ich leider noch nicht das richtige entdeckt, um mich auf Kurs zu bringen und mir fehlt auch vollkommen der Überblick, was geeignet wäre (da ich auf dem Gebiet, wie gesagt, bis jetzt noch nicht unterwegs war).

Eventuell sind noch folgende Eckdaten für die Literaturempfehlungen interessant:
-> deutsch oder englisch
-> aktuell implementiere ich in C++ oder Python, Java wäre auch kein Problem (falls es Literatur mit entsprechenden Codesnippets gibt), Pseudocode wäre natürlich ebenso absolut in Ordnung



Vielen Dank für jeden Beitrag & eure Hilfe

ascer

Hi,
ich kann dir leider nicht direkt weiterhelfen, aber dein Ansatz hoert sich schon ganz gut an. Was jetzt genau dein Problem ist habe ich nicht ganz verstanden, also ob du jetzt ein schnelleres oder ein genaueres Verfahren suchst.
Was ich eigentlich vorschlagen wollte ist dass du die Frage mal auf
http://www.matheplanet.com
stellst, da gibt es auch ein separates Informatik Forum. Da dort hauptsaechlich Mathematiker unterwegs sind wirst du dort eher eine zufriendenstellende Antwort finden.

Komplexität ist nicht unbedingt das Problem. Wenn der Algorithmus schnell läuft, ist das zwar schön, aber das Hauptziel ist, dass er möglichst qualitativ filtert.

Die Problematik ist eben, dass der aktuelle Ansatz zwar ganz gut läuft, dass aber tendenziell noch besser gehen sollte.

Und da kommt mein Problem eben ins Spiel, dass ich nicht weiß, ob ich mir nun zuerst weiter LDA anschaue, oder doch zu PCA, Partikelfiltern, Kalman-Filtern oder oder wechsel. Abgesehen von einer Übersicht über das Gesamtthema fehlt mir auch noch "Einsteigerliteratur" zu eben diesen Themen..

Du brauchst meiner Meinung nach (nach kurzem Überfliegen) ein dichtebasiertes Clustering. Als Algorithmus werfe ich da mal DBSCAN in die Runde.

Ok danke, werd ich mir mal anschauen

Ich kenn mich halbwegs aus mit Kameras, Sensoren und Objekt-Tracking aber ich verstehe ehrlich gesagt noch nicht genau was du willst.
Geht es dir um Object-Tracking im Bild? Sind die Objekte Statisch? Die Kamera-Position? Kennst du die Kamera-Bewegung über irgendeine Art von Odometrie?
Wenn sich alles unabhängig voneinander bewegt und du nur 2D Bilddaten (1 Kamera) hast ist das ein verdammt schweres (für Anfänger unmögliches) Thema.
Sofern zumindest die Kamera statisch ist werden Verfahren eingesetzt die unter Object Tracking laufen wie Kalman- oder Partikelfilter.
Sofern es dir nicht um absolute Welt-Koordinaten der Objekte sondern nur um Koordinaten relativ zur Kamera geht, ist es auch egal wenn die Kamera sich bewegt.

Huhu kuddlmuddl,

danke für die Antwort (:

Es sind 2D-Bilddaten, die Kamera ist auf einem Roboter montiert, es ist also alles dynamisch. Für das Preprocessing sind aktuell schon ein/zwei Sachen am werkeln, die Gyroskopdaten, Kamerawinkel und sowas erfassen und Softwaremodule, die statische und dynamische Objekte im Bild erkennen.

Aktuell ist mein Projekt aber Prepocessing, d.h. ich bekomme auf Softwareseite kontinuierlich Daten, wie z.B. "Ball", 1.2m Entfernung, 20° und dazugehörige Ortsvektoren für die Shapes des Objektes.

Der Witz dabei ist jetzt, das z.B. ein bewegter Ball ja nicht hin und her springt, sondern relativ gleichmäßige Bewegungen über längere Zeit macht. Stillstehende Objekte machen tendenziell eher keine Bewegungen usw. Das Preprocessing soll auf jeden Fall auch noch verbessert werden, aber hier geht es jetzt wirklich nur darum, im Postprocessing über die Datensätze zu iterieren. Schlechte aussortieren und den Rest halbwegs sinnvoll filtern.

Das hier ist z.B. ein Plot von der raw-data und der filtered-data:



Szenario war das tracken eines Balles (Roboter stand still) bei langsamer Ballbewegung. Rot ist gefiltert, blau ungefiltert. Zuerst war der Ball in Ruheposition, deshalb die vielen roten konzentrierten Datenpunkte (jeder Datenpunkt symbolisiert einen aus dem Bild extrahierten 2D-Ortsvektor, der möglichst den Mittelpunkt des Objektes finden soll) und danach wurde er etwas schneller bewegt.

Da funktioniert der von mir implementierte Filter auch ganz gut. Wenn der Robo sich aber bewegt oder der Ball schneller bewegt wird, springen die Daten deutlich stärker. Da wäre etwas noch besseres zum filtern eben ganz schön..

( Das heißt natürlich nicht, dass das Preprocessing untouched bleibt, da werde ich schon auch noch dran arbeiten, aber erst später. Abgesehen davon: wenn der Filter im Postprocessing gut läuft, werden die Daten ja automatisch noch besser, wenn das Preprocessing die Daten überhaupt besser aus den einzelnen Frames extrahiert )

EDIT: ja, es geht erstmal nur Daten relativ zur Kamera. Rest kommt später^^

Ich hab gerad zu wenig Zeit für eine ausführlichere Antwort aber sobald die Kamera sich bewegt läuft es auf das SLAM Problem hinaus. Der aktuell bekannteste Algorithmus ist FastSLAM, den ich damals auch während meiner Diplomarbeit implementiert habe. Es gibt Jede Menge open source Quellcode dazu und auch eine sehr kompakte Implementation in MATLAB.
Alle SLAM Algorithmen lösen das Problem zunächst für eine statische Welt (kein einziges Objekt, was für die Orientierung verwendet wird darf sich bewegen) - können aber dahingehend erweitert werden. Das hört sich ziemlich traurig/wenig an, aber das SLAM Problem ist leider so komplex, dass es zunächst so angegangen werden muss. Wenn man lange genug sucht findet man die PhD von Thrun und Montemerlo als Pdf - ansonsten muss man das Buch kaufen :X FastSLAM 123€. Damals hab ich nur 80€ bezahlt^^
Der Algorithmus ist so gut, weil er der einzige(erste) ist, der keine O(n²) sondern nur O(n) bzw durch Optimierung O(log N) Komplexität hat mit N als Anzahl der Orientierungspunkte.
Der Thrun wurde daraufhin von Larry Page (Google CEO) angeheuert um die Projektgruppe für autonome PKWs zu leiten... und hatte damit auch Erfolg wie man sieht.

Dem ganzen Kram verdanken wir Google Streetview und auch sowas wie die 3D Ansicht von Städten wie Apple es für seine Maps App aktuell einpflegt.