Automatisierte Erzeugung personalisierter ad-hoc-Karten in einem Service-basierten GIS (Mapping on Demand)

Abstract

In den letzten Jahren wurden mehr und mehr raumbezogene Daten über das World Wide Web zur Verfügung gestellt. Karten und Luftbilder bekannter Anwendungen (z.B. Google Maps) lassen sich direkt nutzen oder mit Daten anderer Angebote verknüpfen und in ihrem Informationsgehalt erweitern. Ein Nutzer hat so die Möglichkeit, unabhängig von Ort und Zeit, zu einer aktuellen Fragestellung beliebige Daten zu integrieren und eigene Karten zu erstellen (Mapping on demand). Benötigte Daten werden zunehmend im Zusammenhang mit Diensten - Funktionen, die den Zugriff auf Daten und deren sachgerechte Verwendung unterstützen - zur Verfügung gestellt. Dies entspricht dem allgemeinen Trend des Internets hin zu einer Service-orientierten Architektur; deren Implementierung durch Web Services löst Daten aus dem Kontext spezifischer Anwendungen und macht sie über definierte Schnittstellen verfügbar.<br /> Herausforderung in einer Service-orientierten Architektur ist zunächst, dass die genutzten Daten weltweit verteilt sind, zu verschiedensten Zwecken erhoben wurden und in unterschiedlichen Formaten vorliegen. Diese Heterogenität wird durch den Einsatz standardisierter Dienste und Formate überwunden. In der vorliegenden Arbeit wird gezeigt, dass im World Wide Web Technologien verfügbar sind, die das notwendige Potential für ein Mapping on demand besitzen. Beim Auffinden geeigneter Dienste und der Nutzung verfügbarer Technologien wird ein Nutzer durch Webportale unterstützt. Diese bündeln Dienste, machen sie strukturiert zugänglich und ermöglichen die Erschließung durch geeignete Werkzeuge. Eine konkrete Umsetzung von Webportalen wird in dieser Arbeit anhand dreier Beispiele aus dem Bereich der Freizeitplanung gezeigt.<br /> Für das Mapping on demand ist von Bedeutung, dass Daten verfügbarer Dienste nicht nur als fertige Karten vorliegen, sondern auch als Kartenbausteine in Form raumbezogener Objekte oder thematischer Layer. Bei der Integration der graphischen Ausgaben dieser Dienste wird offensichtlich, dass die graphische Repräsentation, die jedes Angebot von sich aus mitbringt, isoliert von anderen Angeboten festgelegt ist. Die Kombination beliebiger Quellen führt damit häufig zu Darstellungen, die schon den Mindestanforderungen graphischer Gestaltungsregeln und erst recht den Erfordernissen der Prägnanz nicht genügen, so dass der Inhalt schwer erfassbar ist. Nur eine prägnante Darstellung gibt dem Nutzer die Möglichkeit, Objekte visuell zu differenzieren und effektiv Wesentliches von Unwesentlichem zu unterscheiden. Eine Voraussetzung hierfür ist der Einsatz visuell gut unterscheidbarer Farben.<br /> Kern dieser Arbeit ist der Nachweis, dass die Bestimmung gut unterscheidbarer Farben als Optimierungsproblem formuliert und mit mathematischen Methoden on demand gelöst werden kann. Dies erfordert eine objektivierte Beschreibung des subjektiven Vorgangs der Farbwahrnehmung in einem Bezugssystem (Farbraum), auf dem eine geeignete, der menschlichen Wahrnehmung entsprechende, Metrik definiert ist. Ein solches System steht bspw. mit dem CIELUV-Farbraum zur Verfügung: Wenn darin der Abstand zweier Farben ein gewisses Minimum überschreitet, ist die Verschiedenheit dieser Farben für einen (normalsichtigen) Menschen klar erkennbar. Das Optimierungsproblem besteht dann darin, die minimale Distanz in einem dreidimensionalen Raum zu maximieren. Es handelt sich dabei um ein nichtlineares Problem, das durch eine Vielzahl lokal optimaler Lösungen gekennzeichnet ist. Klassische gradientenbasierte Verfahren berechnen zwar eine lokale, in der Regel aber nicht die global optimale Lösung. Probleme der globalen Optimierung sind im Allgemeinen schwer lösbar (NP-vollständig). Effiziente Verfahren wurden für diskrete Problemstellungen entwickelt, sind aber wegen der spezifischen Randbedingungen auf das vorliegende Problem nicht übertragbar.<br /> In dieser Arbeit wird eine Methode entwickelt, die mehrere Standardverfahren und Lösungsparadigmen integriert. Ausgangspunkt ist ein randomisierter Algorithmus zur Bestimmung geeigneter Startpunkte. Dieser Algorithmus basiert auf der Beobachtung, dass sich Punkte auf dem Rand der konvexen Hülle des Farbraums in besonderer Weise als Startpunkte eignen. Die Lage dieser Punkte wird durch Anwendung eines Verfahrens der lokalen Optimierung verbessert. Ein dreidimensionales Voronoi-Diagramm wird genutzt, um eine suboptimale Nutzung des verfügbaren Farbraums zu identifizieren und Verbesserungsmöglichkeiten herzuleiten.<br /> Das skizzierte Szenario geht zunächst von einem Standardnutzer und Standardbedingungen aus. Die Methode kann aber ohne weiteres auch auf davon abweichende Randbedingungen, z.B. Farbsehschwächen eines Nutzers, Qualität der Farbwiedergabe eines Anzeigegeräts oder Umgebungsbedingungen (abgedunkelter Raum oder helles Sonnenlicht), angepasst werden. In ihrer Auswirkung führen diese Bedingungen zu einer Einschränkung des verfügbaren Farbraums.

<strong>Automated Creation of personalised ad-hoc-Maps in a Service-based GIS (Mapping on Demand)</strong><br /> Providing geospatial data over the World Wide Web has developed rapidly in recent years. Maps and aerial photographs offered by popular applications (e.g. Google Maps) can either be used directly or may be linked to data of other providers to broaden information content. Hence, a user who demands a map to answer a current question is enabled to create his own map by overlaying arbitrary data - regardless of location and time (Mapping on demand). Data is increasingly provided in connection with services - functions, which support access and appropriate use of data. Services correspond to a general trend of realising a service-oriented architecture in the internet. Web services, which implement this architecture, dissolve data from specific applications and provide them by defined interfaces.<br /> The challenge in using services consists in the worldwide distribution of data, different intentions of data collection and the large variety of available formats. This heterogeneity is overcome by applying standardised formats and services. This thesis demonstrates the potential of technologies which are available for a mapping on demand. In finding suitable services and using technologies, a user is supported by web portals. These portals make services accessible in a structured manner and support their exploration by suitable tools. This thesis presents three examples of real implementations of web portals from the domain of recreation planning.<br /> In the scope of mapping on demand it is important to note that data provided by services are not only available as complete maps but also as components (thematic layers or features). Integrating their graphical output shows that graphical representation of data from each source is defined independently and that graphical representations of different sources may conflict. Thus, the ad hoc combination of sources may lead to maps, which do not satisfy basic rules of graphical design or even requirements of a concise cartographic product. But only conciseness enables a user to identify features visually and to distinguish between essential and nonessential contents. This requires the choice of colours which are well distinguishable by human visual perception.<br /> The main contribution of this thesis is the proof that the determination of well distinguishable colours can be formulated as an optimization problem, which can be solved on demand by mathematical methods. This approach requires an objectified description of the subjective process of colour vision in a reference system (colour space), which provides an appropriate metric according to human perception. Particularly the CIELUV colour space satisfies the requirement: If the distance between two colours exceeds a certain minimum, a human with full colour vision is able to distinguish these colours clearly. Thus the optimization problem is to maximise the minimal distance in a three-dimensional space. This is a nonlinear problem, which is characterized by a large number of locally optimal solutions. Classical descend methods find a locally, but usually not the globally optimal solution. In general, global optimization problems are computationally hard to solve (NP-complete). Efficient methods have been developed for solving discrete problems. Due to specific constraints these methods are not applicable to the problem at hand.<br /> This thesis presents a method which integrates several standard methods and solution paradigms. It is based on a randomized algorithm to determine appropriate starting points. The essential observation is that points on the boundary of the convex hull of the colour space are well suited as starting points. Afterwards the location of these points is improved by a method of local optimization. A three-dimensional Voronoi-diagram is used to detect suboptimal solutions and to identify possible improvements.<br /> Initially the scenario outlined above acts on a standard user and standard conditions. The method is adaptable to incorporate further constraints, e.g. user's colour-defective vision, device-specific colour reproduction and ambient conditions (darkened room or sunlight). These constraints result in clipping the available colour space.