Ich suche einen Algorithmus, der mir Bild-Daten - z.B. Google Maps Kacheln - vektorisiert. Das Ausgangsmaterial ist wenig verrauscht und im Prinzip soll nur die Straßenführung erkannt werden.

Kennt jemand Web-Seiten, die das Thema erklären? Habe bereits eine Vorstellung, wie das gehen könnte, würde aber vorher gerne wissen, was die 'Theorie' sagt.

Niemand? Na wäre auch zu schön gewesen, wenn ich aus den G'Maps für meinen PDA ein Navigationssystem hätte bauen können - noch an diesem Wochenende

Habe ich noch nie gemacht, würde ein paar Faltungsmatrizen draufwerfen (Entrauschen, Kantenextraktion) und dann mit dem was übrig bleibt Vektoren basteln.

Vielleicht ist da was hilfreiches dabei:

http://www.penguin.cz/~fojtik/vectoris/vektoris.htm

http://www.cs.ust.hk/~taicl/papers/line-net.pdf

http://www.research.ibm.com/journal/rd/266/ibmrd2606J.pdf

http://www.eg.org/EG/CGF/Volume13/Issue3/v13i3pp349-359.pdf

http://www.profc.udec.cl/~gabriel/tutoriales/giswb/vol1/cp3/cp3-7.htm

Thx!

Sollte eigentlich noch so kompliziert sein, da G'Maps sehr sauer aussehen und bestimmte Informationen - die ich vektorisieren möchte - immer durch gleiche Farben codiert sind.

Übrigens würde ich gerne Straßen in einfache simple Liniensegmente codieren, da der Großteil der G'Map Daten aus einzelnen Linienabschnitten besteht.

Oh, geirrt. Ist wohl doch etwas schwierig

Die langen Linienseqment entstehen bei der Vektoroptimierung aus den kurzen, wenn man mit einer gewissen Toleranz die zu größeren zusammenfaßt.

Das mit der Vektoroptimierung ist mir jetzt nur mal eingefallen, weil ich mal was ähnliches gemacht habe: Wegsuche mit dem Lee-Algorithmus. Aber das ist was anderes als Vektorisierung von Bitmaps.

OK, thx!

Meine algorithmische Idee geht so:

- Wähle einen beliebigen Punkt, von dem bekannt ist, dass er innerhalb einer Staße liegt.
- Für alle Winkel A von 0-360 Grad und eine Entfernung D
-- Lege eine Linie vom Startpunkt und bestimmt den Endpunkt in Richtung A mit Abstand D
-- Prüfe, ob der lineare Weg vom Startpunkt bis A vollständig auf der Linie liegt
-- Falls ja, erneut mit entfernterem Punkt
-- Falls nein, suche den nächsten Winkel.

Das erste D sollte dabei weiter entfernt sein als die typische Breite einer Straße.

Naja, mal sehn...

Rantanplan<br>
Trotzdem, vielen Dank! Da die G'Map PNGs wenig verrauscht sind, sind die allgemeinen Algorithmen mit Entrauschung oder Kantenschärfung vermutlich gar nicht erforderlich.

Dies Ausgangsbasis sieht übrigens - stark vergrößert - so aus. Ziemlich hochwertig, oder?

Da könnte fast anhand der Grauwerte der Kanten die Richtung zum nächsten Punkt bestimmt werden...

Ich hätte es vielleicht etwas anders angepackt:

- erstmal ein s/w-Bitmap (mit Threshold) erzeugt, so daß nur noch die Wege übrigbleiben

- dann mit einer Faltungsmatrix die Wege auf die Mittellinie reduzieren. Wenn die Faltungsmatrix größer als die Wegebreite ist, müßte man eine rasiermesserscharfe Mittellinie hinbekommen

- dann den "nur noch" den Mittellinien folgen und Vektoren erzeugen

- dann die Vektoren mit sinnvoller Toleranz zu größeren zusammenfassen

Zumindest eine spannende Aufgabenstellung

Hm, ja, das Ausgangsmaterial ist schon hochwertig. Aber meine Idee funktioniert da nicht, da sind auch Straßennamenn drin und die Straßen besitzen nicht alle eine eindeutige Farbe. Mit den Randlinien sollte man aber was anfangen können.

OK, auch eine interessante Idee.

Ist übrigens just for fun, da ich zufällig rausgefunden habe, dass die Kacheln von G'Map bzgl. der URL extrem einfach codiert sind und der fragliche Server die Kacheln auch in großer Zahl und kurzer Zeit ausspuckt.

Habe 100x100 Kacheln höchster Auflösung in 1,5 Stunden runtergeladen und mit x/y Koordinate in PNGs gepackt. Liefert eine Datenmenge von ca 100 MByte.

Ah, mir fällt gerade ein, dass ich noch ein Buch zum Thema 'Computer Graphics' rumliegen habe. Werde mal reinschauen.

Nacht!

Erste Approximation, nach ner Stunde Spielerei...

Und hier das nächste Ergebnis. Das sieht doch schon ganz nett aus...

Weiterer Fortschritt Jetzt werden aus Punkten Vetoren...

Nicht schlecht, sieht ja schon richtig brauchbar aus

Kiel!

Yes!

Rantanplan<br>
Algorithmus? Nimm zwei Vektore A und B, bestimme deren Winkel und ersetze sie durch deren Vektoraddition, wenn sie sich um weniger als A% unterscheiden?

Problem: Bei kurzen - 2 Pixel langen Vektoren - erzeugt die Verschiebung des Entpunktes um 1 Pixel nach link oder rechts eine Winkeländerung von 30-45 %, schätze ich mal.

Hast Du eine Idee, wie man dies ausgleichen könnte? Das Verfahren darf nicht so hart sein, dass es Kurvenzüge nicht in viele kleine Vektoren zerlegt.

Hm, wie wäre es mit |b-a|/(|a|+|b|) < n? Also der Fehlervektor normiert auf die Summe der Längen der Ausgangsvektoren muß in Länge kleiner als ein Schwellwert sein?

Ja, das schein sinnvoll. Trotzdem sehe ich das Problem mit Kurven. Denke ich morgen mal drüber nach .

CU

Und weil es so viel Spass macht, hier mal der Tracer als Film: http://www.turingart.com/downloads/gmap.mov

Und das ist sogar noch Rosetta Code

Süß

Ja, genau die richtige Beschreibung

Und hier noch eine etwas optimierte Version - auch süß

Hier natürlich: http://www.turingart.com/downloads/gmap.mov

E-Mail Benachrichtigung...

Ich soll den Thread sterben lassen? OK!

Hm? lol
Ich habe die E-Mail Benachrichtigung für mich angeschaltet, weil ich es höchst interessant finde.

Ok. Ich dachte, Deine Nachricht sollte 'Lass mal stecken und schick diese Infos doch einfach per EMail weiter'.

hehe, ne, sorry, falls es so klang. Aber aufgrund der funktionalen Beschränkung hier auf der Seite, muss man ja immer einen Beitrag schreiben und die Benachrichtigung einzuschalten.

Also weiter machen!

Hmm,

schicke Sache, aber wäre es nicht prinzipiell einfacher bereits vektorisiertes Kartenmaterial zu benutzen?

Nichts anderes macht Google doch auch, irgendwo müssen sie sich ja die Karteninfos aus den Finger saugen

PS:

Das erinnert mich aus irgendeinen Grund an Tron ^^

resistance<br>
Ja, richtig, aber nicht so einfach. Es gibt auf der Welt 2-3 Hersteller, die Vektordaten produzieren und liefern können. Einer der Hersteller ist Teleatlas. TeleAtlas hat in Deutschland diverse Digitizer Autos rumfahren, die ständig neue Daten liefern. Typischerweise wird 2x pro Jahr aktualisiert. Das Material ist nicht frei verfügbar - jedenfalls nicht soweit mir bekannt ist.

Da ich die fragliche Anwendung ja nicht verkaufen will, ist die Nutzung der G'Map Daten für private Zwecke laut Liz'Bestimmung ok.

Andererseits bringst Du mich auf eine Idee: Ich könnte ja irgendein anderes kommerziellen Vektorformat kaufen, die Windows Mobile Anwendung schreiben und das fertige Programm dann vertreiben. Andere Nutzer müssten sich dann natürlich das gleiche Kartenmaterial kaufen. Insofern wäre das ganz optisch wesentlich hochwertiger und zudem auch noch legal verkaufbar.


Ah, ja, richtig!

Ah, vergessen: Ich bastel an der Vektorisierersoftware auch deswegen, weil ich noch nie mit so etwas zu tun hatte.

Ist also just for fun, und um etwas zu lernen. Zudem entstehen lustige Bildchen.

Auf Google Video gibt es einen Beitrag direkt aus dem Google R&D Center, welches sogenannte Time-Series transformationen betrachtet. Das funktioniert so: Nimm Dir eine 2-D Figur, such Dir den Schwerpunkt/Mittelpunkt der Fläche und bestimmte für alle Richtungen R den Abstand zur Umrandung der Figur. Es entsteht eine Kurve, die in der X-Achse die Winkel darstellt und in der Y-Achse den Abstand repräsentiert die time-series.

Wenn Du die Kurve auf den höchsten Y-Wert skaliert - der dann 1 ist - dann hat sie sehr schöne Eigenschaften:
- Eine Rotation der 2-D Figur führt zu einer X-Achsen Transformation der time-series.
- Eine Vergrößerung der 2-D Figur um den Faktor 2 führt zu einer zu einer identischen time-series.
- Die time-series kann wohl mit weniger Speicher repräsentiert werden, als die 2-D Figur.

etc.

Habe leider nicht mehr den Link zu Google Video. Aber die Jungs von Google scheinen an einem System zu arbeiten, welches Ähnlichkeiten von Bilder berechnen kann.

Witzig.