Transcript
Universität Bremen - Fachbereich 3 - Informatik SS 2009 Diplomarbeit Bestimmung von Landmarken aus räumlichen Daten Dustin Boris Wagner 27. Juli 2009 Betreuer / Erster Gutachter: Zweiter Gutachter: Kai-Florian Richter Prof. Dr. Bernd Krieg-Brückner Diese Diplomarbeit beschäftigt sich mit der Bestimmung von Landmarken an einer Route. Landmarken dienen in Wegbeschreibungen als Referenzpunkte für die entscheidenden Stellen der Route und können die Wegndung dadurch bedeutend erleichtern. Was dabei als Landmarke geeignet ist und was nicht, hängt in der Regel von der Umgebung und der Lage zur Route ab. Die automatische Bestimmung ist entsprechend schwer und Kartendaten, die bereits explizite Informationen über Landmarken enthalten sind kaum verfügbar. Diese Arbeit zeigt einen Ansatz zur Extraktion hervorstechender Objekte aus räumlichen Daten des Landes Bremen. Der Ansatz berücksichtigt dabei strukturelle und funktionale Aspekte. Zur Auswertung wurde der Ansatz in einem eigens dafür entwickelten Geoinformationssystem umgesetzt. Das Ergebnis ist eine Software, mit der Routen berechnet werden können und automatisch Landmarken in deren Umgebung bestimmt werden können. Der Vergleich mit den real an der Route vorkommenden Objekten zeigt, dass der Ansatz durchaus brauchbare Ergebnisse liefert. Die Qualität der Landmarken hängt dabei jedoch stark von der Granularität der Daten ab. 4 Inhaltsverzeichnis 1. Einleitung Aufgabenstellung Überblick Existierende Arbeiten Landmarken Aktueller Stand der Technik Ansätze zur automatischen Extraktion von Landmarken Ein Ansatz zur Einbindung von Landmarken in Wegbeschreibungen Ein Ansatz zur Klassikation von Landmarken Spatial Chunking Bestimmung von Landmarken aus räumlichen Daten Die ATKIS Daten Repräsentation der Objekte Tatsächlich vorhandene Objektarten Kriterien zur Auswahl geeigneter Objekte Distanz Sichtbarkeit Objektart Räumliche Lage Einzigartigkeit Bewertung der Objektarten Extraktion der Objekte (algorithmisch) Berechnung der Distanz Berechnung der Sichtbarkeit Bestimmung der räumlichen Lage Bestimmung der Objektart Bestimmung der Einzigartigkeit Implementation Genereller Aufbau Genereller Ablauf Probleme Evaluation Vorgehensweise Durchführung Berechnung und Beschreibung der Route Wahl der Parameter Auswertung der Landmarkenbestimmung Qualität der Daten Rückschlüsse Ergebnis Zukünftige Arbeiten Änderungen am Verfahren Verwendung anderer Datensätze A. Inhalt der CD-ROM 71 Literaturverzeichnis 74 Abbildungsverzeichnis 75 Tabellenverzeichnis 77 6 Erklärung Bisher habe ich keine Informatik-Diplomarbeit in dem gleichen oder einem fachlich entsprechenden Studiengang an einer wissenschaftlichen Hochschule in der Bundesrepublik Deutschland endgültig bestanden oder nicht bestanden oder bende mich in einem entsprechendem Prüfungsverfahren. Auÿerdem habe ich nicht den Prüfungsanspruch durch endgültiges Nichtbestehen einer Prüfung verloren. Bremen, Unterschrift des Antragstellers 8 1. Einleitung Wegndung ist keine einfache Aufgabe. Schon gar nicht, wenn während der Wegndung ein Teil der Aufmerksamkeit einer anderen Tätigkeit gewidmet werden muss, wie etwa dem Autofahren. Deshalb wird häug auf Hilfsmittel wie zum Beispiel Wegbeschreibungen aus dem Internet, Navigationsassitenzsysteme oder spezielle Software für mobile Geräte (insbesondere Smartphones) zurückgegrien. Diese Wegbeschreibungen werden automatisch erzeugt und enthalten Informationen, die zum Folgen des Routenverlaufs erforderlich sind. Besonders wichtig sind die Informationen über die sogenannten Entscheidungspunkte der Route. Die Entscheidungspunkte sind die Stellen, an denen eine Entscheidung von dem Navigierenden erforderlich ist. In der Regel sind dies Kreuzungen, an denen die richtige (zur Route gehörende) Abzweigung gewählt werden muss. Die Lokalisation dieser Punkte während des Navigierens kann durch eine entsprechende Kommunikation der Entscheidungspunkte erleichtert werden. Hier kommen die sogenannten Landmarken ins Spiel. Landmarken sind Objekte der Umgebung, die besonders hervorstechen und dadurch besonders gut als Referenzen für Entscheidungspunkte genutzt werden können. Dass die gezielte Verwendung von Landmarken in den Routeninstruktionen die Qualität von Routeninstruktionen verbessern kann, wurde bereits gezeigt [Lovelace et al. 1999]. Des Weiteren ähnelt dieses Vorgehen der Verhaltensweise von Menschen, die in ihren Wegbeschreibungen ebenfalls auällige Objekte benutzen, um den Ort einer durchzuführenden Aktion zu kennzeichnen: an der Telefonzelle rechts. Diese Verhalten begründet sich dabei auf die Art und Weise, wie Menschen Navigationsaufgaben planen und vor allem wie dabei die mentale Repräsentation der Route aufgebaut ist. Diese basiert verallgemeinert auf zueinander in Verbindung gesetzten Objekten [McNamara 1992], wobei es sich im Falle einer Navigationaufgabe vornehmlich um Landmarken handelt. Die Angabe von Landmarken kann auch abseits von Entscheidungspunkten hilfreich sein. Bendet sich zwischen den Entscheidungspunkten der Route ein längerer Abschnitt, so können Objekte referenziert werden, die auf diesem Abschnitt passiert werden. Durch Informationen dieser Art erhält der Nutzer eine Bestätigung, dass er sich bei einer längerwährenden Aktion noch auf der Route bendet [Michon und Denis 2001]. Die automatische Bestimmung von Landmarken zur Verwendung in von Computern erzeugten Wegbeschreibungen ist ein schwieriges Problem. Ob ein Objekt hervorsticht und sich somit als Landmarke eignet, geht nicht ausschlieÿlich aus den Eigenschaften des Objekts hervor. Vielmehr ist es entscheidend, ob das Objekt von der Route aus als hervorstechend wahrgenommen wird. Das wird unter anderem durch die Lage und die Ausrichtung des Objekts zur Route beeinusst: Ist das Objekt von der Route aus gut sichtbar, ist es über einen längeren Abschnitt von der Route aus sichtbar oder bendet es sich an einer markanten Stelle? Auch von Bedeutung ist die Umgebung 9 des Objekts: Bildet das Objekt einen visuellen Kontrast zu seiner Umgebung oder geht es in einer Menge ähnlicher Objekte unter? Ein weiteres Problem besteht darin ausreichend Landmarken entlang der Route auszusuchen, aber nicht zu viele. Denn zu viele oder schlechte Landmarken tragen eher zu der Verwirrung des Nutzers bei [Burnett 2000]. Das heiÿt, dass Landmarken in Konikt zu einander stehen können. Zum Beispiel kann es zu dicht aufeinanderfolgende Landmarken geben. Solche Kon- ikte müssen durch Auswahl der am besten geeigneten Landmarke behoben werden. Die Mehrzahl der aktuell in Navigationssystemen oder Internetroutenplanern verwendeten Datensätze bieten aufgrund dieser Schwierigkeit der automatischen Landmarkenbestimmung keine expliziten Informationen über Landmarkenobjekte. Das Ziel dieser Arbeit ist es deshalb einen Ansatz zu liefern, der dennoch versucht aus vorhandenen räumlichen Daten Landmarken zu bestimmen. Benutzt wird dabei ein konkreter Datensatz, dieser basiert auf dem aktuellen (2008) ATKIS (Amtliches Topographisch- Kartographisches Informationssystem) Datenbestand des Landes Bremen. Die ATKIS- Daten entsprechen den digitalisierten Kartendaten, die vom Landesvermessungsamt herausgegeben werden. Neben sämtlichen öentlichen Straÿen Bremens wurden auch eine Vielzahl an topograschen Objekten (Objekte der Erdoberäche) erfasst, die sich zum Teil als Landmarken eignen können. Aus der Wahl beziehungsweise Vorgabe dieses Datensatzes resultiert eine Einschränkung auf städtische Gebiete, der Ansatz wird also nicht auf Funktion in Verbindung mit ländlicheren Regionen untersucht. Des Weiteren beschränkt sich der Ansatz bei der Routenwahl auf Routen, die auf dem Straÿennetz basieren, dass heiÿt Strecken, die in erster Linie mit dem Auto befahren werden. Dadurch ergibt sich eine relativ klare Absteckung der Anforderungen an das zu entwickelnde Verfahren. Das angestrebte Ziel dieser Arbeit ist es Kriterien zur Bestimmung von Landmarken zu formulieren und diese in Algorithmen umzusetzen, so dass eine Grundlage für weiterführende landmarkenbasierte Verfahren zur Generierung von Routeninstruktionen entsteht. Es ist dabei nicht oensichtlich, dass dieser Ansatz der Landmarkenbestimmung zum Erfolg führen muss. Die Daten könnten sich beispielsweise als ungeeignete beziehungsweise ungenügende Quelle für sinnvolle Referenzobjekte herausstellen Aufgabenstellung Die wesentliche Aufgabe dieser Arbeit besteht, wie der Titel schon besagt, in der Extraktion von Landmarken aus räumlichen Daten. Das damit verbundene Hauptproblem liegt in der Beschaenheit der zugrunde liegenden Daten: diese stellen keine expliziten Informationen über Landmarken bereit. Im Fall dieser Arbeit wird auf einem räumlichen Datensatz des Landes Bremen gearbeitet. Neben dem Straÿennetz sind in diesem auch Vorkommen vieler verschiedener Arten von Objekten kodiert. Genau diese sogenannten Objektarten gilt es auf die Eignung als Landmarken hin zu untersuchen. Aufgrund der Einteilung in Objektarten kann die Bestimmung, was sich als Landmarke eignet, nicht oder nur begrenzt auf individuellen Objekten durchgeführt wer- 10 den. Vorrangig müssen allgemein gültige Annahmen zur Eignung der Objektarten getroen werden, anhand derer die Extraktion von Landmarken erfolgen kann. Ein groÿer Teil der theoretischen Vorarbeit besteht also darin, die vorhandenen Objektarten, unter Berücksichtung struktureller und funktionaler Aspekte zu ordnen. Der praktische Teil umfasst die Implementation eines eigenständigen Programmes, welches diese Ordnung benutzt, um automatisiert Landmarken aus dem Datenbestand zu extrahieren. Die Auswahl der zu extrahierenden Landmarken beschränkt sich dabei auf die für die Wegbeschreibung einer vorgegebenen Route relevanten Landmarken. Die Berechnung der Route, sowie die Erzeugung der Wegbeschreibung stehen dabei eher im Hintergrund. Hier kann auf bereits existierende Algorithmen zurückgegriffen werden. Zu den Problemen, die von der Software gelöst werden sollen, gehört zum Einen das Auslesen von möglichen Landmarkenkandidaten aus dem Kartenmaterial. Dabei kann es sich um punkt-, linien- und ächenförmige Objekte handeln, deren Lage zu der Route ermittelt werden muss. Des Weiteren muss geprüft werden, wie es um die Sichtbarkeit der einzelnen Kandidaten bestellt ist. Es kann durchaus der Fall sein, dass sich verdeckende Objekte zwischen Route und Kandidat benden. Auch falls mehrere Kandidaten gleicher Art zur Wahl stehen, muss das Programm eine Lösung nden. Dazu kann zum Beispiel analysiert werden, welches der Objekte sich am meisten von seiner Umgebung abhebt oder ob sich eines der Objekte für eine bevorzugte funktionale Rolle bezüglich der Route einsetzen lässt, zum Beispiel als Orientierungspunkt an einer Kreuzung. Zum anderen muss die Software die extrahierten Landmarken auch in einer geeigneten Form ausgeben. Die Landmarken sollten in grascher Form zusammen mit der dazugehörigen Route ausgegeben werden können, was gleichzeitig auch die Evaluation erleichtert. Eine Evaluation mit Versuchspersonen ist in dieser Arbeit nicht vorgesehen. Stattdessen soll die Funktion wahlweise mittels synthetischer Eingaben oder Eingaben in Form von existierenden Routen in dem räumlichen Datenbestand kontrolliert werden. Je nach Ausgang der Evaluation müssen eventuell die Auswahlkriterien für die Landmarken oder die Verfahren zur Extraktion überarbeitet werden. Den Abschluÿ der Arbeit stellt die ausführliche Dokumentation des Endergebnisses dar. Dabei soll insbesondere auch auf weitere mögliche Optimierungen und Erweiterungen eingegangen werden Überblick Im folgenden Kapitel werden einige existierende Arbeiten zu dem Thema Landmarken vorgestellt. Den Anfang bilden dabei Arbeiten, die sich mit der Denition von Landmarken beschäftigen. Weiterführend kommen dann Ansätze, die sich mit der Extraktion von Landmarken und der Einbindung von Landmarken in Wegbeschreinungen befassen. Neben den Forschungsbeiträgen wird in diesem Kapitel auch der aktuelle Stand der Technik dargestellt. Dazu werden Internetroutenplaner auf die Verwendung von Landmarken hin untersucht. Das dritte Kapitel stellt den Hauptteil dieser Arbeit dar. Der erste Abschnitt ist den 11 zugrunde liegenden Daten gewidmet. Dabei wird insbesondere auf die Struktur und den Umfang der Daten eingegangen. In dem zweiten Abschnitt werden die Kriterien zur Auswahl als Landmarken geeigneter Objekte erläutert. Eines der Kriterien ist die Bewertung der Objektart. Diese Bewertung ndet im darauolgenden Abschnitt für alle in den Daten vorkommenden Objektarten statt. Der vierte Abschnitt befasst sich mit der algorithmischen Extraktion der Objekte anhand den zuvor genannten Kriterien. Der letzte Abschnitt des dritten Kapitels gibt einen Überblick über die daraus entstandene Implementation. Im vierten Kapitel wird das implementierte Verfahren ausgewertet und Rückschlüsse auf die verwendeten Kriterien und Algorithmen gezogen. Das fünfte und letzte Kapitel gibt eine Zusammenfassung darüber, was bei der geleisteten Arbeit erreicht wurde und wie dies durch zukünftige Arbeiten verbessert werden kann. 12 2. Existierende Arbeiten In dem nachfolgenden Abschnitt wird zunächst einmal der Begri der Landmarke erklärt. Darauf folgend wird ein Überblick über den aktuellen Stand der Technik, sowie den aktuellen Stand der Wissenschaft gegeben. Für ersteres werden exemplarisch drei verschiedene Internet-Routenplaner untersucht. Den Überblick über den aktuellen Stand der Wissenschaft bilden einige Zusammenfassungen wissenschaftlicher Arbeiten. Dabei handelt es sich einmal um zwei Ansätze zur automatischen Bestimmung von Landmarken, einen Ansatz zur Einbindung von Landmarken in Routeninstruktionen, sowie eine Vorgehensweise zur Klassikation von Landmarken. Darüber hinaus wird ein Abschnitt am Ende dieses Kapitels dem Spatial-Chunking gewidmet Landmarken Im Folgenden wird der Begri der Landmarke genauer erklärt. Dazu werden zuerst ein paar existierende und geläuge Denitionen betrachtet und deren Brauchbarkeit im Kontext dieser Arbeit abgewogen. Danach wird auf mögliche Unterkategorien von Landmarken eingegangen. Presson und Montello haben sich bereits mit der Bedeutung des Begris Landmarke auseinandergesetzt. Vom Autor frei übersetzt lautet ihre minimale Denition: Alle Elemente oder Merkmale der Umgebung, die als Referenzpunkt dienen könnten. In diesem Sinne, ist eine Landmarke ein unterscheidbares Objekt oder Merkmal, das auällt und an das man sich erinnern kann. Sie machen aber zugleich klar, dass der Kontext eine wichtige Rolle spielt: Eine Campus-Bibliothek kann (möglicherweise) als Referenzpunkt für andere Gebäude auf dem Campus dienen, aber nicht für die gröÿere Stadt, in der sich der Campus bendet. [Presson und Montello 1988] Gemäÿ der Denition von Sorrows und Hirtle machen bestimmte Eigenschaften eine Landmarke aus. Einzigartigkeit (Singularity) führt dazu, dass ein Objekt einen Kontrast zu seiner Umgebung bildet. Ein Objekt kann aber auch durch seine besondere Lage hervorragen (Prominence), zum Beispiel im Stadtzentrum oder auf einer Anhöhe. Objekte, die einem speziellen Nutzen dienen, eine besondere Bedeutung (Content) oder kulturellen Stellenwert haben, können ebenfalls als Landmarke gewählt werden. Auch typische Vertreter einer bestimmten Kategorie von Objekten (Prototypicality) eignen sich als Landmarke. Bei Objekten mit den genannten Eigenschaften liegt die Wahrscheinlichkeit vergleichsweise höher, dass sie Leuten bekannt sind oder andernfalls leicht ausndig gemacht werden können. [Sorrows und Hirtle 1999] Bei einer automatischen Bestimmung von Landmarken ist es jedoch nur schwer möglich, anhand der räumlichen Daten zu entscheiden, ob ein Objekt auällig ist 13 und ob man sich daran erinnern kann. Auch Eigenschaften wie der kulturelle Stellenwert lassen sich kaum aus den Daten ableiten, es sei denn sie sind explizit in den Daten kodiert. Der in dieser Arbeit verwendete Datensatz stellt neben der Art der Objekte kaum weitere nützliche Informationen bereit. Daher ist es notwendig allgemein gültige Aussagen über diese Objektarten zu treen, mit dessen Hilfe Landmarken extrahiert werden können, die im Kontext der Route angemessen erscheinen. Um diese Problematik strukturiert angehen zu können, ist es wichtig die möglichen Kategorien von Landmarken und ihre Eigenheiten zu berücksichtigen. Für Presson und Montello gibt es einerseits Landmarken, mit denen sich die Position anderer Objekte identizieren lässt. Für die Verwendung in Wegbeschreibungen eignet sich eine solche Landmarke besonders, um den Ort einer Richtungsänderung zu kennzeichnen, also als eine Landmarke an einem Entscheidungspunkt. Andererseits gibt es Landmarken, die weniger mit einem bestimmten Punkt in der Umgebung in Verbindung gebracht werden können, sich aber dafür für Bestätigungszwecke eignen. In Wegbeschreibungen können solche Landmarken an langen Abschnitten zwischen Richtungsänderungen eingesetzt werden. Diese werden im Folgenden mit Landmarken an Zwischenabschnitten oder Landmarken entlang der Route bezeichnet. Im Gegensatz zu diesen Landmarkentyp, den sogenannten lokalen Landmarken, die sich immer in unmittelbarer Nähe zu der Route benden, gibt es auch den Typ der entfernten Landmarke. Dabei handelt es sich um Objekte, die über eine entsprechend hohe Sichtbarkeit verfügen, so dass sie über weite Teile der Route hinweg zu erkennen sind. Entfernte Landmarken eignen sich als generelle Orientierungshilfe. Sie können zum Beispiel einem Navigierenden an dem Startpunkt der Route helfen, die richtige Richtung zu nden. Darüber hinaus kann es auch Landmarken geben, die einen Symbolcharakter haben. So wie der Eielturm für die Stadt Paris. Weitere Kategorien liefern Sorrows und Hirtle mit der Unterteilung in visuelle, kognitive und strukturelle Landmarken. Die Unterteilung basiert hauptsächlich auf den unterschiedlichen Wegen, auf denen Objekte den Navigierenden beeinussen können. Visuelle Landmarken stechen aus ihrer Umgebung durch ihr Äuÿeres hervor. Das heiÿt die Gröÿe, Form und / oder Farbe der Landmarke bilden einen Kontrast zu der Umgebung, auf die die visuelle Wahrnehmung besonders anspricht. Bei kognitiven Landmarken spielt beispielsweise die kulturelle oder historische Bedeutung des Objekts eine Rolle. Denkmäler und andere Sehenswürdigkeiten haben einen gewissen Symbolcharakter, sie stehen mit bestimmten Ereignissen, Aktivitäten oder Personen in Verbindung und besitzen dadurch einen hohen Bekanntheitsgrad. Dabei kann es sich aber auch um banalere Dinge wie zum Beispiel der Leuchtreklame einer groÿen Supermarktkette oder ähnliches handeln. Strukturelle Landmarken werden durch besondere Verbindungs- oder Knotenpunkte dargestellt, zum Beispiel durch einen Bahnhof, der Schienen- und Straÿenverkehrsnetz miteinander verbindet oder einem Marktplatz, der das Zentrum einer Stadt markiert. Abgesehen von den bisherigen Kategorien lassen sich Landmarken aber auch durch die Form ihrer Repräsentation in dem verwendeten Kartenmaterial unterscheiden. Üblicherweise wird ein Objekt in den Daten entweder durch einen Punkt (punktförmig), durch eine Sequenz von Punkten (linienförmig) oder durch ein Polygon bezie- 14 hungsweise eine Fläche oder mehrere zusammenhängender Flächen (ächenförmig) beschrieben. Je nach Form eignet sich eine Landmarke auch für bestimmte Zwecke in einer Routenbeschreibung besser oder schlechter als Landmarken einer anderen Form. An Kreuzungen sind beispielsweise punktförmige Landmarken besser geeignet als andersförmige, da sie sich eben nur an diesem Punkt an der Kreuzung benden, während linien- oder ächenförmige Landmarken mit einem viel gröÿerem Bereich in Verbindung gebracht werden können. Linienförmige Landmarken scheinen dagegen wie prädestiniert für den Einsatz an Zwischenabschnitten einer Route, falls sie parallel zu diesem verlaufen sollten Aktueller Stand der Technik Wie anfangs schon erwähnt, machen heutige Routenplaner kaum von Landmarken Gebrauch. Dies wurde 2005 bereits von Klippel et al. anhand einiger Internet-Routen
