Gegeben sei eine Punktewolke, die durch Streuung zufälliger Punkte einer
Kurve (parametrisiert durch (x,y)(t)=r(t,a1...an) mit Parameter a1...an
und unabhängiger Variable t) entsteht. Wie rekonstruiere ich a1...an?
Konkret geht es darum, aus aufgezeichneten GPS-Punkten entlang eines
Weges (nehmen wir der Einfachheit halber mal als
(x,y)(t)=(at^2+bt+c,dt^2+et+f) an) die Parameter a...f zu bestimmen.
Gibt es einen einfacheren Ansatz, als zu jedem Punkt den minimalen
Abstand zur Kurve auszurechen, und die Summe dieser Abstände zu
minimieren?
Das Problem ist, dass nur die Punkte (x1,y1)...(xm,ym) bekannt sind,
aber nicht die Variable t in jedem Punkt. Wäre ti bekannt, wäre es ein
leichtes, den Abstand ||(xi,yi)-r(ti,a1...an)|| zu berechnen. So aber
muss ich erst das passende ti finden (Suche des absoluten Minimums der
Abstandsfunktion), was sehr rechenzeitaufwendig ist.
Das beste wäre ein Link zu einer Lösung dieses Problems. Für den Fall,
dass die Kurve r(t) eine Gerade ist, können die Geradenparameter direkt
bestimmt werden (Stichwort Ausgleichsgerade). Es bringt also nicht,
diesen Spezialfall als Vereinfachung zu diskutieren, da es sich nicht
auf gekrümmte Kurven verallgemeinern läßt.
Handlet es sich nicht um die übliche Suche nach einer Näherungsfunktion
? Für beliebige Kurven nimmt man soweit ich weiß Splines oder
Bezierkurven, die zwar keine geschlossene Funktion bilden, aber
wenigstens stetig.
Noch eine Ergänzung: es geht nicht darum, durch einen einzigen
aufgezeichneten Track eine glatte Kurve zu legen (dafür sind
Bezierkurven genau richtig), sondern aus den Punkten von hunderten
Tracks (die allerdings nur als Punktewolke, also ohne Reihenfolge und
Zeitangaben vorliegen) die gemittelte Kurve zu bestimmen.
Sind nur die xy-Wertepaare in beliebiger Folge bekannt, oder wenigstens
deren zeitliche Aufeinanderfolge ?
Der exakte Zeitpunkt jeder Messung ist jedenfalls unbekannt. Das würde
ja nur verhindern, die Geschwindigkeit zu bestimmen, mit der die Kurve
durchlaufen wurde.
- Warum speicherst du nicht alles doppelt in ein Array. Es gibt bei
Zufallsvariablen doch ohnehin kein System.
Also f(x) und gleichzeitig die Umkehrfunktion.
- In Numerical Recipes (http://www.nr.com/) findest du bestimmt auch
etwas.
- mit Ausgleichsgeraden (auch kurvilinear) bin ich satt. Die
Ausgleichsrechnung liefert eine Art Kurvenschlange - mehr nicht.
Vorraussetzung für brauchbare Ergebnisse ist eine hohe Korrelation.
Beispielsweise die Situation, wenn die Punktewolke durch zwei Geraden im
45 Grad Winkel genau beschrieben wird, dann lässt sich die ursprüngliche
Situation über Partialrechnung gar nicht mehr rekonstruieren (Varimax).
Wir haben zunächst lokale Punktanhäufungen, die irgendwie
auseinanderdividiert werden müßten, deren Zentrum wären dann die Städte,
die der Handlungsreisende wahscheinlich auf dem kürzesten Weg
durchquert hat, genau sagen kann man das nicht mehr.
Hier sind eindeutig zuviele Frickler unterwegs. Ich hatte nicht gefragt,
was euch zu meiner Frage durch den Kopf geht, sondern nach einer Lösung.
Wenn ihr schon die Frage nicht versteht, fragt nach und interpretiert
sie nicht um.
Ja, und jetzt kommt ... Undankbarkeit ... dbluq war schon hier bevor
gast laufen konnte ... wir sind alle ganz toll außer gast ... laber blah
fasel sülz BLUBBB!
Einen Zusammenhang mit dem Problem des Handlungsreisenden kann ich zwar
beim besten Willen nicht erkennen, aber dein Gelaber kannst du dir
schenken, Gast!
> (x,y)(t)=(at^2+bt+c,dt^2+et+f) an) die Parameter a...f zu bestimmen.
Warum eine Modelfunktion abhängig von t, wenn dies die Probleme macht
und eigentlich auch gar kein sinnvoller Parameter ist?
> Gibt es einen einfacheren Ansatz, als zu jedem Punkt den minimalen> Abstand zur Kurve auszurechen, und die Summe dieser Abstände zu> minimieren?
Ja, die Methode der kleinsten Quadrate.
> (Stichwort Ausgleichsgerade).
Ist nur ein Spezialfall oben genannter Methode, welche prima auch für
nicht-lineare Modellfunktionen anwendbar ist.
So ein Jammer. Eine fertige Lösung wäre natürlich schön, aber eine
genauere Formulierung des Problems in Zusammenarbeit mit uns Fricklern
kann ja vielleicht doch irgendwie weiterhelfen.
>Einen Zusammenhang mit dem Problem des Handlungsreisenden kann ich zwar>beim besten Willen nicht erkennen, aber dein Gelaber kannst du dir>schenken, Gast!
dbluqs krampfhafte Versuche überall was beizutragen nerven einfach.
sorry
>> (x,y)(t)=(at^2+bt+c,dt^2+et+f) an) die Parameter a...f zu bestimmen.>>Warum eine Modelfunktion abhängig von t, wenn dies die Probleme macht>und eigentlich auch gar kein sinnvoller Parameter ist?
Was wäre denn ein sinnvoller Parameter? x oder y kommen nicht in Frage,
weil die Kurve keine eindeutige Funktion y(x) oder x(y) sein muss. t ist
übrigens nicht die Zeit sondern halt eine beliebige unabhängige
Variable, über die die Kurve läuft. Man könnte t als Weglänge festlegen.
>> Gibt es einen einfacheren Ansatz, als zu jedem Punkt den minimalen>> Abstand zur Kurve auszurechen, und die Summe dieser Abstände zu>> minimieren?>>Ja, die Methode der kleinsten Quadrate.
Und was sind dann die Quadrate? Die Quadrate der genannten Abstände. Und
was ist dann die Methode der kleinsten Quadrate? Die Minimierung der
Summe dieser Abstände. Das meinte ich, habe vergessen, das Quadrieren
dazuzuschreiben.
>> (Stichwort Ausgleichsgerade).>>Ist nur ein Spezialfall oben genannter Methode, welche prima auch für>nicht-lineare Modellfunktionen anwendbar ist.
Ja? Wie genau verallgemeinerst du die Methode, um den Abstand eines
Punkte (xi,yi) von einer unendl. oft diffbaren Kurve zu berechnen, von
der nichts bekannt ist ausser ihrer Parametrisierung?
Ich habe so allmählich die Aufgabe verstanden:
Wir haben eine Ebene, die in kartesischen x- und y-Koordinaten vermessen
wird, und darauf schlängelt sich eine Straße, auf der viele Fahrzeuge
entlangfahren, jedes liefert zu unbekannten Zeitpunkten XY-Wertepaare
eines GPS-Empfängers ab. Leider wird auch die Reihenfolge nicht
aufgezeichnet. Am Ende hat man in der Umgebung der Straße viele
Koordinatenpunkte und soll daraus den wahrscheinlichsten Verlauf der
Straße als Funktion der Zeit t ausgeben, in der man sie entlangfährt.
Konstante Geschwindigkeit wäre dann vorausgesetzt, sonst wird es noch
komplizierter.
Ist das so korrekt?
9 von 10 Punkten!!
> und soll daraus den wahrscheinlichsten Verlauf der Straße als Funktion der >
Zeit t ausgeben,
nein: richtig wäre
...und soll daraus den wahrscheinlichsten Verlauf der Straße als
Funktion der Weglänge t ausgeben,
wobei du Weglänge und Zeit als äquivalent betrachten darfst, wenn du mit
konstanter Geschwindigkeit fährst.
Sorry, aber deine Verallgemeinerung der Methode der kleinsten Quadrate
hört sich schwer nach einer Schleifenkonstruktion an.
Im NR steht was von einer "Downhill Simplex Method". Ist sicher eine
stupide Rechnerei aber vielleicht genau das was du hier brauchst. Sowas
kann nicht befriedigend funktionieren. Aber dafür gibts ja schließlich
Computer.
Andernfalls müsstest Du jetzt genauer spezifizieren was du willst...
>Andernfalls müsstest Du jetzt genauer spezifizieren was du willst...
Dieser Satz ist hier im Forum gleichbedeutend mit "Ich habe keine
Ahnung, bin mir aber zu fein, es zuzugeben."
Was ist hieran ungenau, wenn ich hinzufüge, dass r(t,a1...an) unednl.
oft diffbar ist:
>Gegeben sei eine Punktewolke, die durch Streuung zufälliger Punkte einer>Kurve (parametrisiert durch (x,y)(t)=r(t,a1...an) mit Parameter a1...an>und unabhängiger Variable t) entsteht. Wie rekonstruiere ich a1...an?>Im NR steht was von einer "Downhill Simplex Method".
Da habe ich schon effizientere Algorithmen. Es geht aber um einen
intelligenteren Ansatz, der die verschachtelte Schleife (1. Minimierung
der Quadrate, 2. Suche nach kleinstem Abstand) umgeht, nicht um eine
schnelle Implementierung dieser beiden Schleifen.
Da du ja n-mal klüger bist als wir alle zusammen, lös' dein Problem doch
einfach selbst und lass uns Deppen hier zufrieden, statt ständig deinen
überlegenen Intellekt zur Schau zu stellen.
Die parametrische Darstellung der Straße ist zum Beispiel nötig, wenn
sie ein Autobahnkleeblatt enthält, wo das Durchfahren der Schleife zu
zwei Zeit- oder Wegpunkten dieselben XY-Koordinaten ergibt. ( "nicht
eindeutig" wie oben schon gesagt).
Ist die Fitfunktion vorgegeben? Die genannten quadratischen Gleichungen
waren doch nur ein Beispiel, fitten mit der Methode der kleinsten
Quadrate setzt zunächst mal diese Vorgabe voraus oder sehe ich das
falsch?
Interessantes Problem. Ich habe wirklich auch keine Ahnung.
Ich glaube ich habe es jetzt auch langsam begriffen. Leider muss ich bei
meiner ursprünglichen Aussage bleiben:
Brauchbare Ergebnisse gibt es nur bei einer hohen Korrelation.
Also wenn die Strasse Kurven hat und nur wenige Punkte vorliegen kann
man gar nichts mit anfangen.
Wenn man viele Punkte hat kann man sie in x,y Richtung anordnen
(sortieren) und bekommt eine Vorstellung vom Verlauf der Strasse. Dann
ist auch alles kein Problem mehr. Zunächst über Clusterbildung der
Punkte und dann iterativ durch Verfeinerung der Granulation. Solange bis
die Korrelation nicht mehr wesentlich besser wird.
Und dazwischen liegt nun die Realität für die du eine Lösung suchst. Die
soll natürlich dank Kollege Computer besser sein als der Augenschein.
Also ich kenne das als Clusteranalyse. Vielleicht bringt dir das etwas.
Es handelt sich um ein multivariates Verfahren für Probleme dieser Art.
Gruss
> Ist die Fitfunktion vorgegeben?
Das fällt unter meinen Kommentar zu:
> Andernfalls müsstest Du jetzt genauer spezifizieren was du willst...
Wenn du weißt wie es fürs Beispiel der quadratischen Funktionen geht,
dann heraus damit. Wenn nicht, wird es auch nicht weiterhelfen, wenn ich
dir sage, dass ich stückweise kubische Polynome stetig differenzierbar
verkette, oder doch?
>Und dazwischen liegt nun die Realität für die du eine Lösung suchst. Die>soll natürlich dank Kollege Computer besser sein als der Augenschein.
Nein, überhaupt nicht. Eine Kurve, die ich per Augenmaß zeichnen würde,
wäre die perfekte Lösung. Dir scheint nicht bewußt zu sein, dass
Computer sich mit Augenmaß sehr schwer tun.
>Also ich kenne das als Clusteranalyse. Vielleicht bringt dir das etwas.>Es handelt sich um ein multivariates Verfahren für Probleme dieser Art.
Ich kenne Clusteranalyse als etwas anderes. multivariates ist auch ein
schönes Wort.
Und das ist keine Spline-Funktion? Es hört sich in der Wikipedia
zumindest genauso an: aus Stücken zusammmengesetzt und stetig
differenzierbar
"Ein Spline n-ten Grades ist eine Funktion, die stückweise aus Polynomen
mit maximalem Grad n zusammengesetzt ist. Dabei werden an den Stellen,
an denen zwei Polynomstücke zusammenstoßen (man spricht auch von Knoten)
bestimmte Bedingungen gestellt, etwa dass der Spline (n-1) mal stetig
differenzierbar ist."
Das Stichwort "Clusteranalyse" klingt wirklich vielversprechend:
http://de.wikipedia.org/wiki/Clusteranalyse
>Clusteranalyse
Trotzdem. So funktioniert es und nicht anders. Wenn du weniger
Dimensionen hast umso besser...
Also Clustern und dann die Granulation verkleinern.
Ist aber alles PI mal Daumen versteht sich.
Das Problem mit dem man am Schluss konfrontiert wird nennt sich
Schwellenwertverfahren und die sind mit natürlicher Intelligenz leicht
zu verarbeiten, wie du eben auch richtig angemerkt hast.
Natürlich ist das eine Splinefunktion, wenn du es so betrachtest. Aber
die Methode der Berechnung des Splines aus Stützstellen ist hier völlig
unbrauchbar, wenn du mal drüber nachdenkst.
>Das Stichwort "Clusteranalyse" klingt wirklich vielversprechend:
ja, das Stichwort "Mathematik" klingt auch vielversprechend
Leute, es war nett mit euch. Ihr müsst euch nun leider alleine weiter
mit dem Problem vergnügen, weil ich eine Lösung brauche und keine Zeit
mehr habe darauf hinzuweisen, warum der eine oder andere (oder jeder)
Geistesblitz zu nichts führt.
hier wendet sich der Gast mit Grausen, so kann ich hier nicht ferner
hausen...
Ich sehe das ganze wie eine Fotobearbeitung am Computer, Kontrast
anheben, Schärfen oder weichzeichnen, Auflösung verringern usw. Am
Schluß soll eine saubere Linie rauskommen.
"Clustern und dann die Granulation verkleinern" wäre so ein Rezept.
Meine Formulierung "lokale Punktanhäufungen irgendwie
auseinanderdividieren (und anschließend eine kürzeste Verbindungslinie
ermitteln)" geht in die gleiche Betrachtungsweise. Die Autobahnschleife
wäre ein Test für die Güte des Vorgehens, die darf nicht rausgemittelt
werden.
Man sollte schon mit quadratischen B-Splines arbeiten (Bsp. TrueType)
aus vielen Segmenten zusammengesetzt alles andere ist doch noch mehr
Kaffesatz.
Damit gibt es keine Unstetigkeiten. Also es reicht aus und noch mehr
Parameter lassen sich nicht rechtfertigen. Der Algorithmus soll ja nur
in eine Richtung konvergieren.
Hallo Gast,
Das Grausen ist berechtigt.
Was hast du denn erwartet. Man erwartet vom Computer, dass er
intelligenter ist als der Mensch und verrechnen darf er sich nicht.
Wenn der Mensch nach Augenmass eine Linie einzeichnet, was ist davon zu
halten. Über solche Linien sind doch schon unzählige Köpfe gerollt.
Du bist dem Problem KI-Forschung nähergerückt - einer Utopie.
Jorge, ich glaube du solltest Politiker werden, wenn du es nicht schon
bist. Deine Fähigkeit, Zusammenhänge aus der Luft zu greifen, wo keine
sind, und dir in einem Satz gleichzeitig selbst zu widersprechen und
diesen Widerspruch scheinbar in eine frühere Aussage eines anderen zu
platzieren, ist phänomenal.
"Jorge, ich glaube du solltest Politiker werden, wenn du es nicht schon
bist. Deine Fähigkeit, Zusammenhänge aus der Luft zu greifen, wo keine
sind, und dir in einem Satz gleichzeitig selbst zu widersprechen und
diesen Widerspruch scheinbar in eine frühere Aussage eines anderen zu
platzieren, ist phänomenal."
Das ist ja genial...
>Soll angeblich ein effizienter Algorithmus für das Orthogonal Distance>Fitting (ODF) von Kurven und Flächen sein
Dank dir Holger, ODF reicht völlig als Stichwort, damit komme ich
weiter.
ODF ist tatsächlich das Schlagwort für die hilflosen Versuche sowas in
den Griff zu bekommen.
http://www.innovations-report.de/html/berichte/informationstechnologie/bericht-26319.html
Jetzt wünsche ich Gast weiterhin viel Vergnügen mit der Lösung seines
speziellen Problems.
Ich persönlich bin weiterhin skeptisch. Damit habe ich aber schon
verraten, dass ich in der Opposition bin :-))...
>ODF ist tatsächlich das Schlagwort für die hilflosen Versuche sowas in>den Griff zu bekommen.>>http://www.innovations-report.de/html/berichte/inf...
Schön, dass du das nochmal wiederholt hast, Jorge.
Holger, leider musste ich feststellen, dass ODF nichts anderes ist als
die von mir umrissene Idee. Die Projektion jedes Punktes auf die Kurve
wird mittels Newtonverfahren o.ä. gemacht, wodurch wieder das Problem
der verschachtelten Schleifen vorliegt (das Newtonverfahren an sich ist
nicht das Problem, sondern die Anzahl der zu testenden Startwerte um
nicht bloss ein lokales Minimum zu finden).
Was bisher vergessen wurde, ist dass das Problem eine Groessenskala
besitzt. Dh es ist nicht variabel in der Groesse, noch kann
Selbstaehnlichkeit vorkommen. Irgendwo kommt die Breite der Strasse und
deren minimaler Kruemmungsradius rein. Sonst ist das Problem
unterbstimmt.
RT
> Was bisher vergessen wurde, ist dass das Problem eine Groessenskala> besitzt.
Und du könntest Jorge in seiner Politikerkarriere, vor allem in der
Opposition, beraten. Immer schön alle Probleme verkomplizieren, auch
wenn noch nicht mal eine Lösung für den einfachen Fall existiert.
Nicht ganz. Wenn die Strasse unendlich duenn ist und ein Kurvenradius
gegen Null zulaessig ist, dann kriegt man durch jede Punktwolke eine
sich beliebig windende Gebirgsstrasse. Nein ?
RT
Das Problem ist, dass nur die Punkte (x1,y1)...(xm,ym) bekannt sind,
aber nicht die Variable t in jedem Punkt. Wäre ti bekannt, wäre es ein
leichtes, den Abstand ||(xi,yi)-r(ti,a1...an)|| zu berechnen. So aber
muss ich erst das passende ti finden (Suche des absoluten Minimums der
Abstandsfunktion), was sehr rechenzeitaufwendig ist.
Das must nicht so eng sehen.
Schau mal was da schon gemacht ist um Polis zu tracen.
Datenparalleler Software-Ray-Tracer
Die bisher vorhandenen COVISE-Module zur Grafikausgabe basieren alle auf
der Programmierschnittstelle OpenGL für Hardware-beschleunigte
3D-Grafik. Am Rechenzentrum steht jedoch ein großes Cluster (128 Knoten)
aus Shared Memory-System (je 2 CPUs) mit einem schnellen
Verbindungsnetzwerk (Infiniband, fast 1 Gigabyte/s bei einer Latenz von
5 Mikrosekunden) zur Verfügung, das nicht über die dafür notwendigen
Grafikkarten verfügt. Damit die in Simulationen auf diesem Cluster
gewonnenen enormen Datenmengen effizient - insbesondere ohne sie über
langsame Verbindungen umzukopieren - visualisiert werden können, soll
ein datenparalleler Software-Ray-Tracer (d.h. es wird mittels
Strahl-Rückverfolgung ermittelt, welche Farbe einem Bildpunkt zugeordnet
wird) implementiert werden, der die schon vorhandene verteilte Struktur
der Daten respektiert. Insbesondere sollen Polygone zusammen mit
volumetrischen Daten auf unstrukturierten Gittern dargestellt werden
können.
