Category: Master Thesis

… ist vollbracht: Mein Entwurf für das “Indoor Landmark Navigation Model” (ILNM) ist nun fertig gestellt und wird diese Woche an meinem Betreuer gesendet. Kurz gesagt ging es darum, das von Duckham et. al. (2010) für den Outdoor-Bereich entwickelte “Landmark Navigation Model” für die Anwendung innerhalb von Gebäuden anzupassen. Dabei waren für die unterschiedlichen Phasen der Routenbeschreibungsgenerierungsprozesses (was für ein Wort!) verschiedene, indoor-spezifische Aspekte zu beachten: Welche Indoor-Objekte eignen sich als Landmarks? Welche spezifischen Aspekte muss man bei der Auswahl von Landmarks für Routen innerhalb von Gebäuden beachten? Wie müssen Indoor-Routenbeschreibungen aufgebaut sein und wie sollen Landmarks darin inkludiert sein?

Mein Model stellt dabei einen ersten Entwurf dar und kann, abhängig von der Ergebnissen der Anwendung auf das Campus-GIS der WU, noch iteativ verbessert werden. Die spannende Aufgabe des Testens des Modells anhand realer Daten stellt den nächsten Schritt dar.

Da ich derzeit an meinem letzten Modul (“Geostatistik”) arbeite, kann sich das jedoch noch etwas hinziehen.

 

Literatur
Duckham, Matt, Stephan Winter, and Michelle Robinson (2010). “Including landmarks
in routing instructions”. In: Journal of Location Based Services 4.1, pp. 28-52.

Im letzten Post habe ich über den kritischen Punkt der Datenqualität geschrieben. Dieser hat mich nun im letzten Monat etwas länger beschäftigt als erwartet. Bevor man nämlich konkret Objekte auswählen kann, welche für die Bewertung hinsichtlich deren Eignung als Landmark-Kandidaten herangezogen werden können, müssen die Daten vorverarbeitet und vorselektiert werden. Wie bereits beschrieben, stehen im Campus-GIS unterschiedliche Datenquellen mit unterschiedlicher Qualität zur Verfügung. Folgende Schritte wurde daher im Zuge der Vorbereitung der Daten durchgeführt:

1. Klassifizierung: Wenn Objekte nicht bereits einer Kategorie angehören, wurden sie klassifiziert, sofern entsprechende Attribute zur Verfügung standen. Z.B. konnten alle Räume, die das Wort “Gang” im Raumnamen enthalten, der entsprechenden Kategorie zugeordnet werden.
2. Generalisierung: Wenn mehrfache Kategorien für ähnliche Objekttypen existieren, wurden diese zusammengefasst. Beispielsweise wurden die Kategorien “Treppe” und “Stiege” in eine Kategorie “Stiege” zusammengefasst.
3. Vorauswahl: Um die Anzahl der Objektkategorien überschaubar zu halten, welche als Landmark-Kandidaten bewertet werden sollen, wurde eine grobe Vorauswahl durchgeführt. Nur jene Objektkategorien wurden ausgewählt, welche folgende Eigenschaften erfüllen:
   • Leicht erkennbar: aufgrund der Form, Kennzeichnung, Tür o.ä.
   • Einmalig: Gewisse Information sind teilweise redundant in mehreren Datenquellen gespeichert. Beispielsweise sind Toiletten sowohl über die Raumtypen als auch als POIs verfügbar. In diesem Fall wird die jeweils genauere Datenquelle verwendet.
   • Allgemein verfügbar: Objekte, die nur an wenigen Stellen des Campus vorkommen (z.B. die Selbstbedienungs-Terminals an zwei Orten) werden nicht ausgewählt.
   • Klassifizierbar: Nur Objekte, die eindeutig einer Kategorie zugeordnet werden können, werden ausgewählt.
   • Relevant für Indoor-Routing: Einige POI-Kategorien (z.B. Fahrradgarage) beziehen sich auf Outdoor-Objekte. Auch wenn diese grundsätzlich für die Navigation zwischen Gebäuden relevant sein könnten, werden sie im Rahmen dieser Masterarbeit nicht behandelt.

Nach Anwendung dieser Schritte wurden etwa 40 Objektkategorien ausgewählt, welche nun für deren Eignung als Indoor-Landmarks bewertet werden können. Mehr dazu (hoffentlich bald) im nächsten Post.

 

 

Rechtzeitig vor dem Jahreswechsel habe ich die Kapitel zu den grundlegenden Theorien meiner Master Thesis fertiggestellt. In Kapitel 2 wurden die grundlegende Konzepte zu “Landmarks in Routenbeschreibungen” erläutert. Der Ausgangspunkt dabei war die Beschreibung von Theorien zur menschlichen Wegefindung und Navigation. Eine weit verbreitete Definition von Wegefindung ist jene von Montello (2005): “Navigation is the coordinated and goal-directed movement through the environment by organisms or intelligent machines.” Navigation wird dabei in die Komponenten “Locomotion” und “Wayfinding” unterteilt. Golledge (1999) definiert Wegefindung wie folgt: “Wayfinding is the process of determining and following a path or
route between an origin and destination.”

Um Wissen über Navigation weiterzugeben, gibt es verschiedene Formen, wobei Karten und Routenbeschreibungen am häufigsten verwendet werden. Untersuchungen zeigen, dass Menschen aus der Umgebung herausragenden Objekte – so genannte Landmarks – zur Orientierung und auch für die Angabe von Richtungsänderungen in Routenbeschreibungen verwenden (Siegel and White (1975), Tom and Denis (2003), Ross et al. (2004)).

Landmarks sind bekannte, kennzeichnete Objekte in einer Umgebung, die einfach erkannt und gemerkt werden können. Landmarks können nach verschiedenen Kriterien unterschieden werden, wobei jene von Sorrows und Hirtle (1999) in visuelle, kognitive und strukturelle Landmarks die am häufigsten verwendete ist. Verschieden Studien zeigen auf, dass Landmarks für die Qualität von Routenbeschreibungen eine wichtige und kritische Rolle spielen (z.B. Lovelace et al. (1999), Tom und Denis (2003), Rehrl, Leitinger, et al. (2009)).

Gerade für die Navigation innerhalb von Gebäuden sind Landmarks eine wichtige Unterstützung, da man hier leichter die Orientierung verliert und Richtungsänderungen häufiger stattfinden. Deshalb wäre hier auch eine höhere Dichte von Landmarks notwendig. Allerdings gibt es in Gebäuden grundsätzlich eine kleinere Auswahl an Landmark-Kategorien und diese sind oft auch weniger herausstechend als außerhalb von Gebäuden (Gartner (2007), Radoczky (2007)). Auch existieren bis jetzt kaum reale Indoor-Navigationssysteme, die eine Navigation mit Landmarks anbieten. Huang und Gartner (2010) zeigen auf, dass die Bereitstellung von Landmark-basierten Routenbeschreibungen eine der zentralen Herausforderungen von Indoor-Navigationssystemen ist, welche noch Bedarf für weitere Forschung und Entwicklung aufweist.

Kapitel 3 wird sich nun der Entwicklung des “Indoor Landmark Navigation Model” widmen. Dazu wurde im ersten Subkapitel eine Recherche der bestehenden Ansätze zur automatischen Generierung von Routenbeschreibungen mit Landmarks durchgeführt. Bis auf eine Ausnahme beziehen sich dabei alle Ansätze auf Routengenierungen für den Outdoor-Bereich.

Nachdem damit die theoretischen Konzepte meiner Arbeit erläutert wurden, darf ich mich nun als nächstes (endlich) der Entwicklung des ILNM widmen. Der erste Schritt dazu wird die “Landmark identification” sein. Das heißt es wird eine Klassifizierung erstellt, welche Objekte sich grundlegend als Indoor-Landmarks eignen, unabhängig von einer konkreten Route. Diese Klassifizierung wird exemplarisch für die Daten des Campus-GIS der WU durchgeführt.

Nachdem ich bis Ende des Jahres mit dem UNIGIS-Modul “OpenGIS und verteilte Geoinformationsverarbeitungen” widmen werde, wird mit der Entwicklung eines Ansatzes für die Landmark-Identifikation Anfang nächsten Jahres begonnen. Ich freue mich schon auf diesen spannenden Teil meiner Masterarbeit!

 

Literatur

Gartner, Georg (2007). “Semantic Wayfinding with Ubiquitous Cartography”. In: Proc. of the XXIII International Cartographic Conference, pp. 4-10.

Golledge, Reginald G (1999). “Human wayfinding and cognitive maps”. In: Wayfinding behavior: Cognitive mapping and other spatial processes, pp. 5-45.

Huang, Haosheng and Georg Gartner (2010). “A Survey of Mobile Indoor Navigation Systems”. In: Cartography in Central and Eastern Europe. Ed. by Georg Gartner and Felix Ortag. Lecture Notes in Geoinformation and Cartography. Springer Berlin Heidelberg, pp. 305-319.

Lovelace, Kristin L., Mary Hegarty, and Daniel R. Montello (1999). “Elements of good route directions in familiar and unfamiliar environments”. In: Spatial information theory. Cognitive and computational foundations of geographic information science. Springer, pp. 65-82.

Montello, Daniel R. (2005). “Navigation”. In: The Cambridge Handbook of visuospatial thinking. Ed. by P. Sha and A. Miyake. New York: Cambridge University Press,pp. 257-294.

Radoczky, Verena (2007). “How to design a pedestrian navigation system for indoor and outdoor environments”. In: Location Based Services and TeleCartography. Berlin: Springer.

Rehrl, Karl, Sven Leitinger, Georg Gartner, and Felix Ortag (2009). “An Analysis of Direction and Motion Concepts in Verbal Descriptions of Route Choices”. In: Spatial Information Theory. Ed. by KathleenStewart Hornsby, Christophe Claramunt, Michel Denis, and Gerard Ligozat. Vol. 5756. Lecture Notes in Computer Science. Springer Berlin Heidelberg, pp. 471-488.

Ross, Tracy, Andrew May, and Simon Thompson (2004). “The Use of Landmarks in Pedestrian Navigation Instructions and the Effects of Context”. In: Mobile Human-Computer Interaction – MobileHCI 2004. Ed. by Stephen Brewster and Mark Dunlop.Vol. 3160. Lecture Notes in Computer Science. Springer Berlin Heidelberg, pp. 300-304.

Siegel, Alexander W. and Sheldon H. White (1975). “The Development of Spatial Representations of Large-Scale Environments”. In: ed. by Hayne W. Reese. Vol. 10. Advances in Child Development and Behavior. JAI, pp. 9-55.

Sorrows, Molly E. and Stephen C. Hirtle (1999). “The nature of landmarks for real and electronic spaces”. In: Spatial information theory. Cognitive and computational foundations of geographic information science. Springer, pp. 37-50.

Tom, Ariane and Michel Denis (2003). “Referring to landmark or street information in route directions: What difference does it make?” In: Spatial information theory. Foundations of geographic information science. Springer, pp. 362-374.

 

Nachdem die grundsätzliche Fragestellung, d.h. “Wie können Indoor-Routenbeschreibungen mit Landmarks automatisiert erzeugten werden?”, gefunden war, ging es darum, das genaue Ziel und die Teilfragen der Master Thesis genauer zu spezifizieren.

Der erste Schritt war eine umfassende Literatur-Recherche. Schnell stellte sich dabei heraus, dass bis jetzt kein Ansatz über die automatische Erzeugung von Indoor-Routenbeschreibungen mit Landmarks in der Literatur existiert und auch generell Studien über Indoor-Landmarks sehr rar sind. Für Routenbeschreibungen mit Landmarks außerhalb von Gebäuden wurden einige Ansätze entwickelt. Der Großteil dieser Ansätze basiert jedoch auf der Extraktion von Landmarks aufgrund der visuellen beziehungsweise geometrischen Eigenschaften der potentiellen Landmarks (z.B.: Raubal und Winter (2002), Elias (2003)). Während im Outdoor-Bereich Landmarks über die visuellen Eigenschaften (z.B. Gebaudegröße) selektiert werden können, stehen diese Informationen für Landmarks innerhalb von Gebäuden grundsätzlich nicht zur Verfügung. Einen alternativen Ansatz dazu bildet das von Duckham u. a. (2010) entwickelte “Landmark Navigation Model” (LNM), welches nicht auf den visuellen oder geometrischen Eigenschaften der individuellen Landmark-Kanditaten sondern auf Informationen auf der Ebene der Kategorien der Landmarks beruht.

Da grundsätzlich für Indoor-Landmarks keine Informationen über die individuellen Eigenschaften der einzelnen Landmark-Objekte vorliegen, wurde das LNM von Duckham
u. a. (2010) als geeigneter Ausgangspunkt für meine Arbeit festgelegt. Es wurde jedoch fur den Einsatz außerhalb von Gebäuden entwickelt und die integrierten Landmarks sind ausschlielich POIs. Als Ziel der Arbeit wurde daher im nächsten Schritt festgelegt, das LNM fur den Einsatz innerhalb von Gebäuden und fur die Auswahl von Landmarks aus unterschiedlichen, bestehenden Objekten einer räumlichen Datenbank als so genanntes “Indoor Landmark Navigation Model” (ILNM) weiterzuentwickeln. Um den entwickelten Ansatz zu evaluieren, soll dieser in das Campus-GIS der WU implementiert und durch Feldstudien getestet werden.

In einem weiteren Schritt wurden nun die Teilfragen der Arbeit festgelegt. Nach Duckham u. a. (2010) erfordert die automatische Integration von Landarks in Routenbeschreibungen zwei intelligende Mechanismen: Zuerst müssen jene Objekte identifiziert werden, die aus einer Umgebung hervorstechen und als Landmark-Kandidaten dienen können (“Landmark-Identifikation”) und i zweiten Schritt müssen aus diesen identifizierten Objekten jene für eine individuelle Route ausgewählt werden (“Landmark-Selektion”). Ich füge diesen Prozessen noch den Mechanismus der Integration der Landmarks in die Routenbeschreibungen hinzu (“Landmark-Integration”) und erhalte somit untenstehende Forschungsfragen meiner Arbeit.

Die zentrale Forschungsfrage dieser Arbeit lautet:
Wie können Routenbeschreibungen mit Landmarks für die Navigation innerhalb von Gebäuden aus einer bestehenden räumlichen Datenbank automatisiert erzeugt werden?

Aus dieser zentralen Frage ergeben sich folgende Teil-Fragestellungen:

• Welche Objekttypen eignen sich grundsätzlich fur den Einsatz als Landmarks für Indoor-Routenbeschreibungen (“Landmark-Identikation”)?
• Wie können Landmarks fur konkrete Routen ausgewählt werden (“Landmark-Selektion”)?
• Wie können die extrahierten Landmarks in die Wegbeschreibung integriert werden (“Landmark-Integration”)?
• Wie gut eignet sich der entwickelte Algorithmus fur die Beschreibung von konkreten Routen innerhalb von Gebauden (“Evaluierung”)?

Die letzte Teilfrage bezieht sich dabei auf die geplante Implementierung des entwickelten Ansatzes in das Campus-GIS der WU und der Durchführung von Feldstudien mit den erzeugten Routenbeschreibungen.

Das Festlegen des genauen Ziels sowie der Forschungsfragen der Arbeit war ein iterativer Prozess, welcher durch den Austausch mit Prof. Josef Strobl, mit meinem Betreuer Prof. Georg Gartner sowie Dr. Haosheng Huang von der TU Wien unterstützt wurde. Vielen Dank an dieser Stelle an diese Personen für das wertvolle Feedback zu meinen Ideen!

Literatur
Duckham, Matt, Stephan Winter, and Michelle Robinson (2010). “Including landmarks in routing instructions”. In: Journal of Location Based Services 4.1, pp. 28-52.

Elias, Birgit (2003). “Extracting landmarks with data mining methods”. In: Spatial Information Theory. Foundations of Geographic Information Science. Springer, pp. 375-389.

Raubal, Martin and Stephan Winter (2002). “Enriching Wayfinding Instructions with Local Landmarks”. In: Geographic Information Science. Ed. by Max J. Egenhofer and David M. Mark. Vol. 2478. Lecture Notes in Computer Science. Springer Berlin Heidelberg, pp. 243-259.

Große und komplexe, öffentliche Gebäude bringen oft auch Probleme der menschlichen Orientierung mit sich. Indoor-Navigationssysteme, die auch Routenanweisungen bereitstellen, wären daher eine Unterstützung für die Wegsuche innerhalb von Gebäuden. Routenanweisungen für Fußgänger und vor allem innerhalb von Gebäuden sind jedoch nur sinnvoll, wenn sie als Referenzpunkte für Entscheidungspunkte oder zur Beschreibung von Routensegmenten so genannte Landmarks verwenden. Landmarks sind herausragende Objekte aus der Umgebung, welche leicht erkannt und gemerkt werden können.

Außerhalb von Gebäuden stehen vor allem im städtischen Bereich eine große Anzahl von Landmarks zur Verfügung: Kirchen, bekannte Geschäfte, Häuser mit außergewöhnlichen Fassaden usw. Für den Indoor-Bereich gibt es grundsätzlich jedoch weniger und weniger herausragende Objekte, welche als Landmarks verwendet werden können. Ob und wie diese automatisch aus einer räumlichen Datenbank extrahiert und in Routenbeschreibungen eingesetzt werden können, ist die zentrale Frage meiner Master Thesis, welche in diesem Blog dokumentiert wird.