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.
http://de.wikipedia.org/wiki/Spline http://de.wikipedia.org/wiki/B%C3%A9zierkurve Die Splines würden jeden Punkt der Wolke exakt durchlaufen, Bezier macht eine Annäherung, wenn ich das recht sehe.
Nein. Für Splines und Bezierkurven muss die Reihenfolge der Punkte vorgegben sein. Das ist ein völlig anderes Problem.
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.
Also eher sowas wie das Problem des Handlungsreisenden. Das ist je bekanntlich nicht exakt lösbar.
- 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).
hab ich gerade vor ein paar Tagen gelesen: http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden
Wenn du eine kurilineare Ausgleichsrechnung suchst, dann empfehle ich wegen der linearen Unabhängigkeit die "Legendre Polynome". Quelle s.o.
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?
> lös' dein Problem doch einfach selbst und lass uns Deppen hier zufrieden,
Schon recht, Christoph.
Ich antworte nur den Deppen, die danach fragen.
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.
Ich würde eine quadratische B-Spline Funktion ansetzen, die nicht so stark oszilliert.
Immer wenn ich "Zeit ist Geld" höre, weiss ich das ist eine Ausrede.
>Ich würde eine quadratische B-Spline Funktion ansetzen, die nicht so >stark oszilliert. Ich denke nicht, dass man von vornherein Annahmen über die Anzahl von Wendepunkten machen sollte. Kennst du die "Most curvy street of the world"? http://maps.google.com/maps?f=q&hl=en&q=lombard+st,+san+francisco&ie=UTF8&z=17&ll=37.802112,-122.417779&spn=0.007019,0.016952&t=h&om=1&iwloc=addr Die würde dann als schöne Gerade interpoliert. Wohl nicht ganz im Sinne des Erfinders.
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...
Wirf mal einen Blick in dieses Paper: http://www.springerlink.com/content/c434qb8l038qeu1b/ Soll angeblich ein effizienter Algorithmus für das Orthogonal Distance Fitting (ODF) von Kurven und Flächen sein. Basiert allerdings auch auf der Kleinste-Quadrate Methode. Hab gerade gemerkt, daß da nicht jeder drauf zugreifen kann ohne entsprechend zu zahlen. Hier ist noch ne Pressemeldung von 2004 über das Verfahren: http://www.innovations-report.de/html/berichte/informationstechnologie/bericht-26319.html Der Autor des Verfahrens hat auch ein Buch darüber veröffentlicht, daß man bei Amazon erstehen kann: http://www.amazon.de/Squares-Orthogonal-Distance-Surfaces-Computer/dp/3540239669 Ansonsten vielleicht einfach mal in ner Universitätsbibliothek in der Nähe danach suchen. Meistens steht da auch irgendwo nen Kopierer rum, wenn man keine Lust hat extra nen Ausweis zu beantragen.
Sehr sinnig einen Link auf ein Dokument im Nutzerbeschränkten Bereich anzugeben.
>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
Holger-Hhhh, ich weiß ja nicht von wo du schreibst, aber in Deutschland ist dein Zeug bestimmt nicht legal.
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.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.