Lehrstuhl für Computerlinguistik der Universität Heidelberg
Hauptseminar Maschinelle Sprachgenerierung im SS01 bei Prof. Peter Hellwig

Giskern mit
Datenbank-Komponente
(WP 2)

Hausarbeit von:
Titus v. d. Malsburg
malsburg@cl.uni-heidelberg.de


Version 1.0
13. November 2001


HTML: http://www.cl.uni-heidelberg.de/~malsburg/gener/gener.html
PDF: http://www.cl.uni-heidelberg.de/~malsburg/gener/gener.pdf
Postscript: http://www.cl.uni-heidelberg.de/~malsburg/gener/gener.ps

1 Übersicht

Das Workpackage 2 (WP2) "Giskern mit Datenbankkomponente" ist eines von acht, in denen Daten und Programme erstellt werden sollen, die Teile eines Sprachgenerierungssystems sind. Dieses System soll natürlichsprachliche Wegbeschreibungen auf natürlichsprachige Routenanfragen erzeugen. Ausserdem sollen topologische Beschreibungen erzeugt werden können. Das System soll sich in seiner ersten Version nur auf die Analyse und Erzeugung natürlicher Sprache und der dafür notwendigen Techniken beschränken (Routenplanungs-Probleme, etc bleiben ausgeschlossen). Das WP2 befasst sich mit der Beschaffung und Verwaltung von geographischen Daten, den Möglichkeiten des Zugriffs auf diese und deren geometrischer Analyse.

2 Inhalt

  1. Übersicht
  2. Inhalt
  3. Ziele
  4. Aufgaben
  5. Ergebnisse der Analyse und Recherche
  6. Implementierung
  7. Ergebnisse
  8. Bedeutung
  9. Weitere Entwicklung
  10. Literatur und Verweise

3 Ziele

Das Sprachgenerierungssystem soll Raumausdrücke mit Hilfe von geometrischen Definitionen klassifizieren. Diese Definitionen sind in einer XML-Sprache repräsentiert und verwenden Attribute wie Abstand, Enthaltenseins-Beziehung, Schnitt, etc., um zu entscheiden welche Raumausdrücke auf die Relation, in der die beteiligten Objekte stehen, anwendbar sind. Folglich muss der Zugriff auf die geometrischen Objekte, ihre Eigenschaften und auf Operationen und Funktionen zu Testen der Relationen zwischen ihnen bereitgestellt werden. Aufgrund des engen, im Rahmen dieses Projekts zur Verfügung stehenden Zeitrahmens soll, eine Lösung gefunden werden, die einen unkomplizierten und schnellen Einsatz ermöglicht.

Ziel ist es also, den Komponenten des Gesamtsystems Zugriff auf geographische Daten über die Heidelberger Innenstadt und Operationen auf diese zu geben. Dies beinhaltet folgende Punkte:

Daraus ergeben sich folgende

4 Aufgaben

5 Ergebnisse der Analyse und Recherche

5.1 Daten

5.1.1 Natur

Bei den geographischen Daten handelt es sich in unserer ersten Version des Sprachgenerierungssystem um einfache 2D-Geometrie. Die atomaren Objekte sind Punkte und Linien. Aus diesen werden komplexe Objekte konstruiert. Das sind: Path (Folge von Punkten; mit Linien verbunden), Polygon (Vieleck), Kreis (Punk als Mittelpunkt, Radius). Jedes geometrische Objekt, das eine Entität in unserer Datenbank repräsentiert, soll eine ID haben, über die es identifiziert und zugeordnet werden kann.

5.1.2 Quellen

Wir erhalten Daten über einen Ausschnitt der Heidelberger Innenstadt von Alexander Zipf (EML). Diese liegen im Format des kommerziellen GIS ArcView der Firma ESRI [ESRI] vor. Diese Daten beinhalten: Strassen, Gebäude, Brücken, Brunnen, Grünanlagen, Plätze, Wald. Bauten, Wald, Fluss und Strassen sind in getrennten Dateien gespeichert. Für die Objekte liegen teilweise auch die Namen vor. Andere Daten waren nicht zu bekommen, sodass man, falls man sie benötigt, mit dem EML verhandeln müsste. Eine andere Möglichkeit wäre, sie selbst zu digitalisieren, wozu man aber aufwendige Hardware (Digi-Brett), kommerzielle Software und sehr viel Zeit benötigt.
Möglichkeiten über das Geographische Institut der Univerität Heidelberg Daten zu bekommen wurden nicht geprüft.

5.1.3 Format

Günstig wäre ein Format, das man leicht lesen und schreiben kann und das man ausserdem mit freien Werkzeugen - zum Beispiel dem GIS GRASS [GRASS] - verarbeiten kann. Für das vorliegende Format trifft das beides nicht zu. Ausserdem war es nicht möglich, die Daten in ein anderes geeignetes Format zu konvertieren. Beim Konvertieren in das GRASS-Ascii-Format ist nur die Geometrie übertragen worden. Namen, IDs, etc. sind verloren gegeangen. Deshalb muss also das Shapefile-Format verwendet werden.
Das Shapefile-Format besteht in unserem Fall aus zwei Dateien:
Die "shp"-Datei
In dieser wird die Geometrie gespeichert. Das Format ist eine Erfindung von ESRI. Unter [SHP] findet man die Spezifikation.
Die "dbf"-Datei
Diese zweite Datei ist im DBase-III-Format (DBase ist eine alte relationale Datenbank aus MS-DOS-Zeiten) gespeichert. In ihr werden zusätzliche Informationen zu der Geometrie gespeichert. Für uns interessant ist der dort gespeicherte Name des Objekts.

5.2 GIS

Für das GIS gibt es folgende Vorgaben:
  1. Verfügbarkeit für Unix/Linux
  2. Fähigkeit, unsere Daten zu lesen
  3. Frei oder billig
  4. Überschaubarer Einarbeitungsaufwand
  5. Programmier-Schnittstelle
Es konnte kein GIS gefunden werden, dass alle Kriterien vollstandig erfüllt, sodass ich mich für die Implementierung eines eigenen kleinen GIS entschied. Da wir nur wenige Funktionen eines GIS benötigen, ist der Aufwand dafür kalkulierbar klein.

6 Implementierung

Da die zur Implementierung verfügare Zeit sehr beschränkt war, entschied ich mich dafür die benötigte Software in Python [PY] zu entwickeln, das aufgrund seiner Syntax und seiner umfangreichen Bibliotheken ein schnelles Erzeugen von Prototypen ermöglicht.

6.1 Daten

Für das Lesen von Shapefile-Daten wird das frei verfügbare Python-Modul PyShapeLib [SHPLIB2] verwendet. Es gab allerdings Probleme beim Einlesen der Daten. Es wurde aber noch nicht festgestellt, ob diese in dem PyShapeLib-Modul oder im Format der Shapefiles begründet sind.

6.2 GIS

Das GIS wurde nicht als Standalone-Applikation sondern als Bibliothek von Objekten und Funktionen entworfen, sodass es von den anderen Komponenten des Sprachgenerierungssystems einfach eingebunden und genutzt werden kann.
Das GIS besteht aus mehreren Python-Modulen, die im Folgendem beschrieben werden.
(Es werden nur dir wesentlichen Aspekte beschrieben. Eine vollständige beschreibung der Module findet man unter [EMDOC])

6.2.1 geometry

enthält Definitionen elementarer geometrischer Objekte, Operationen und Funktionen.
6.2.1.1 Objekte
Point
Ein Punkt. Im Moment mit nur zwei Koordinaten. Punkte kann man Addieren, Vergleichen.
norm() gibt die Norm des Vektors.
mult(i) multipliziert den Vektor mit dem Skalar i
Line
Die Linie repräsentiert sowohl die Gerade durch zwei Punkte, als auch das Segment zwischen zwei Punkten.
length() liefert die Länge.
scaleToLength(i) die Länge wird i.
translate(v) verschiebt die Linie um den Vektor v.
Path
length() liefert Gesamtlänge.
Polygon
(wie Path)
Box
Ist ein spezielles Polygon.
Circle
Besteht aus Punkt und Radius.
6.2.1.2 Funktionen
distance(obj1,obj2)
gibt das Minimum der Abstände zwischen den Punkten von obj1 und obj2.
intersects(obj1,obj2)
prüft, ob sich obj1 und obj2 schneiden.
angle(line1,line2)
gibt den Winkel zwischen line1 und line2.
angleClockwise(lin1,line2)
gibt den Winkel, der von line1 im Uhrzeigersinn zu line2 liegt.
between(line,v)
prüft, ob p zwischen den Endpunkten von line liegt. (Er muss nicht auf der line liegen.)
collinear(v1,v2,v3)
prüft, ob v1,v2,v3 collinear sind.
contains(obj1,obj2)
prüft, ob sich obj1 vollständig in obj2 befindet.
containsPartOf(obj1,obj2)
prüft, ob sich obj1 mindestens teilweise in obj2 befindet.
crossProdukt()
Mathematische Operation, wird von anderen Funktionen verwendet.
intPoint(line1,line2)
gibt den Schnittpunkt der Linien.
sameSide(v1,v2,line)
prüft, ob sich zwei Punkte auf der gleichen Seite einer Geraden befinden. Wenn einer der beiden sich auf der Geraden befindet gilt das auch.
skalarMult(i,v)
Skalare Multiplikation.
skalarProdukt(v1,v2)
Skalarprodukt.
turns(v1,v2,v3)
prüft, in welche Richtung die Kurve geht, die durch Verbinden der Punkte entsteht.

6.2.2 geodataresource

stellt Objekte und deren Methoden zum Zugriff auf Geodaten bereit. Momentan enthält dieses Modul Objekte zum Lesen von GRASS-Ascii-Daten und ESRI Shapesfiles.
geodataresource
Abstrakte Klasse, aus der die konkreten Klassen abgeleitet werden.
getLines() um sie zu zeichnen.
getObject(key)
getObjectIDs()
getObjects()
getObjectsInArea(polygon)
parseFile() hier kann auch die Herstellung einer SQL-Connection passieren.

6.2.3 geobuffer

erzeugt zu geometrischen Objekten neue Objekte, die deren Buffer repräsentieren. Ein Buffer buf zu einem Objekt obj ist die Menge der Punkte, die höchstens den Abstand d (mit d >= 0) von obj haben. Falls obj ein Polygon oder Kreis ist, sind auch die in obj enthalten Punkte in buf.
buffer(obj,abstand)
gibt ein neues Objekt, das den Buffer für obj darstellt.
getBoundingBox(obj)
gibt die kleinste Box, die obj enthält.

6.2.4 geovisibility

stellt Funktionen für Sichtbarkeitstests zur Verfügung.
isVisible(p,obj)
überprüft, ob das obj vom Punkt p aus sichtbar ist. Funktioniert im Moment nur für Objekte, die aus Linien bestehen.
Algorithmus:
1.
Sei c ein Kreis um p. (Bild: Der Punkt ist p, das grosse Polygon obj, der Kreis c, das kleine Polygon ein Objekt, das die Sicht behindert.)		 2.
Errechne das kleinste Segment segobj von c, das obj vollständig enthält.
3.
Für alle Ojekte xn, die in der bounding box um p und obj enthalten sind (ausser obj): Errechne das kleinste Segment segn von c, das xn vollständig enthält.		 4.
Ziehe von segobj alle segn ab.
5.
Bleibt ein nichtleeres Segment übrig, dann ist obj von p aus sichtbar,

7 Ergebnisse

7.1 Erfüllung der Ziele

Datenbank für Geographische Daten
Das GIS ist nicht von einem speziellem Datenformat abhängig. Neue Datenformate können genutzt werden, indem man eine Klasse, die den Zugriff auf dieses Format regelt; aus geodataresource ableitet. Dadurch stehen für alle Datenformate (Relationale DBS, objektorientierte DMS, XML, etc.) standartisierte Zugriffsmethoden zur Verfügung, sodass das Datenformat die Abläufe im GIS nicht beeinflusst.
Geographische Daten
Es stehen die Testdaten des EML zur Verfügung. Diese allerdings sind nicht ohne eine weitere Aufbereitung und Ergänzung sinnvoll nutzbar, da die Daten teilweise unvollständig sind und die Repräsentationen teilweise ungeeignet sind.
Implementierung des GIS
Die GIS-Bibliotheken bieten elementare geometrische Objekte, Operationen und Funktionen in 2D. Diese sind vermutlich für die Verarbeitung der Daten, wie sie im Moment vorliegen, ausreichend. Sollten jedoch 3D-Daten hinzu kommen müssten sie erweitert werden, was aber leicht möglich und vorgesehen ist. Die Performanz ist aufgrund der Tatsache, dass eine Interpretersprache genutzt wird, nicht optimal. Ob sie dennoch ausreichend ist, konnte nicht geprüft werden, da die Ausmasse der Anfragen der Semantik-Komponenten an das GIS nicht bekannt sind.
Routen
Test-Routen können in der Datenbank als Paths angelegt und mit entprechenden Labels versehen werden.

7.2 Abdeckung des Phänomenbereichs

Modellierbar ist das was man auf einem Stadtplan sehen kann. Somit sind keine 3D-Daten verarbeitbar. Auch liegen keine Informationen über Intrinsik, oder Attribute von Bauten (z.B: Position der Haustür) vor.

7.3 Vorteile

7.4 Nachteile

8 Bedeutung

Die GIS-Bibliotheken sind wahrscheinlich für weitere Anwendungen in Sprachverarbeitungsprojekten am LCL geeignet. Die Verwendung ist vorallem für Projekte mit engem Zeitrahmen geeignet, da die Einarbeitung und Anpassung an die eigenen Bedürfnisse schnell vonstatten gehen kann. Dies vorallem aus folgenden Gründen: Die Bibliotheken sind nicht für echte geographische Anwendungen gschrieben worden und deshalb dafür wahrscheinlich nicht zu gebrauchen. Unter Anderem wurde folgende Vereinfachung vorgenommen um den Aufwand zu verringern: Die Projektion der Daten wird nicht berücksichtigt. Es wird zu Abstandsberechnungen die euklidische Metrik verwendet, sodass die errechneten Abstände - je nach räumlichen Ausmassen der Daten - mehr oder weniger von den tatsächlichen Abständen abweichen. Ob die Mängel bei der geographischen Anwendung mit erträglichem Aufwand repariert werden können, kann ich nicht beurteilen.

9 Weitere Entwicklung

Ich werde in naher Zukunft die Bibliotheken überarbeiten und 3- und 4D-fähig machen. Sodass also zusätzliche Raum- und Zeit-Informationen einsetzbar sind.

10 Literatur und Verweise

[EMDOC] Embedded Documentation der GIS-Module
http://www.cl.uni-heidelberg.de/~malsburg/gener/emdoc/

[ESRI] ESRI GIS & Mapping Software
http://www.esri.com

[GRASS] Official Home of the GRASS GIS
http://www.baylor.edu/grass/

[PY] Python Programming Language
http:/www.python.org

[SHP] ESRI Shapefile Technical Description
http://arconline.esri.com/arconline/whitepapers/mo_/shapefile.pdf?PID=17

[SHPLIB1] Shapefile C Library V1.2
The Shapefile C Library provides the ability to write simple C programs for reading, writing and updating (to a limited extent) ESRI Shapefiles, and the associated attribute file (.dbf).
http://gdal.velocet.ca/projects/shapelib/shapelib.html

[SHPLIB2] PyShapelib
PyShapelib liest den Inhalt eines ESRI-Shapefiles aus, das geografische Daten in Form von Vektoren speichert, und gibt diese auf Aufforderung zurück.
http://www.derfrosch.de/weichewaren/pyshapelib.html

Titel | Inhalt