Fakultät für Informatik und Mathematik
Refine
Document Type
- Doctoral Thesis (7)
- Other (1)
- Preprint (1)
- Report (1)
Language
- German (10) (remove)
Has Fulltext
- yes (10)
Is part of the Bibliography
- no (10)
Keywords
- (lokale) Bildmerkmale (1)
- Abfragesprache (1)
- Alltagsdigitalisierung (1)
- Anfragerelaxation (1)
- B-Spline (1)
- Bildverarbeitung (1)
- CNC-Maschine (1)
- Computeralgebra (1)
- Datenbanksprache (1)
- Datenbanksystem (1)
Institute
In den vergangenen Jahrzehnten hat es unübersehbar zahlreiche Fortschritte im Bereich der IT-Sicherheitsforschung gegeben, etwa in den Bereichen Systemsicherheit und Kryptographie. Es ist jedoch genauso unübersehbar, dass IT-Sicherheitsprobleme im Alltag der Menschen fortbestehen. Mutmaßlich liegt dies an der Komplexität von Alltagssituationen, in denen Sicherheitsmechanismen und Gerätefunktionalität sowie deren Heterogenität in schwer antizipierbarer Weise mit menschlichem Verständnis und Alltagsgebrauch interagieren. Um die wissenschaftliche Forschung besser auf Menschen und deren IT-Sicherheitsbedürfnisse auszurichten, müssen wir daher den Alltag der Menschen besser verstehen. Das Verständnis von Alltag ist in der Informatik jedoch noch unterentwickelt. Dieser Beitrag möchte das Forschungsfeld “Sicherheit in der Digitalisierung des Alltags” definieren, um Forschenden die Gelegenheit zu geben, ihre Anstrengungen in diesem Bereich zu bündeln. Wir machen dabei Vorschläge einerseits zur inhaltlichen Eingrenzung der informatischen Forschung. Andererseits möchten wir durch die Einbeziehung von Forschungsmethoden aus der Ethnografie, die Erkenntnisse aus der durchaus subjektiven Beobachtung des “Alltags” vieler einzelner Individuen zieht, zur methodischen Weiterentwicklung interdisziplinärer Forschung in diesem Feld beitragen. Die IT- Sicherheitsforschung kann dann Bestehendes gezielt für eine richtige Alltagstauglichkeit optimieren und neue grundlegende Sicherheitsfunktionalitäten für die konkreten Herausforderungen im Alltag entwickeln.
Sichtbarkeitsprobleme, wie das Folgende, gehören zu den grundlegenden Problemen der algorithmischen Geometrie: Berechne zu einem einfachen Polygon, dem sogenannten Kanal, und zu einem darin enthaltenen Punkt die von diesem Punkt aus sichtbare Punktmenge. Dabei ist ein Punkt von einem anderen Punkt aus sichtbar, wenn deren Verbindungsstrecke den Kanal nicht verlässt. Wir wollen uns in dieser Arbeit mit zirkulärer Sichtbarkeit beschäftigen. Zur Verbindung zweier Punkte sind dann nicht nur Strecken, sondern auch Kreisbögen zulässig. Außerdem betrachten wir als Ausgangspunkt dieser sogenannten Sichtbarkeitskreisbögen und -strecken eine Kante des Kanals anstatt eines einzelnen Punkts. Konkret liefert diese Arbeit einen Beitrag zur numerisch robusten Bestimmung der zirkulären Sichtbarkeitsmenge ausgehend von einer Kante des Kanals.
Hierfür wird in dieser Arbeit ein Algorithmus vorgestellt, mit dem für einen gegebenen Punkt festgestellt werden kann, ob dieser von der Startkante aus sichtbar ist. Im Fall eines sichtbaren Punkts wird ein Sichtbarkeitskreisbogen berechnet, der zwei Kanalberührungen besitzt. Damit kann der Algorithmus bei geeigneter Wahl des zu untersuchenden Punkts – der als dritte Kanalberührung fungiert – direkt zur Berechnung von sogenannten Grenzkreisbögen der Sichtbarkeitsmenge benutzt werden. Diese definieren den Rand der zirkulären Sichtbarkeitsmenge und zeichnen sich dadurch aus, dass sie vom Kanal dreimal abwechselnd von links und von rechts berührt werden.
Der beschriebene Algorithmus basiert auf der Untersuchung derjenigen Kreisbögen, die zwar nicht notwendigerweise vollständig im Kanal liegen, aber die Startkante mit dem Punkt verbinden, dessen Sichtbarkeit bestimmt werden soll. Insbesondere werden dabei die Bereiche untersucht, in denen der jeweilige Kreisbogen den Kanal
verlässt, die sogenannten Verletzungen. Da die „Schwere“ einer solchen Verletzung quantifizierbar ist, wird ein iteratives Vorgehen ermöglicht. Dabei wird der Kreisbogen iterativ so verändert, dass dieser bei gleichem Endpunkt den Kanal immer „weniger verlässt“. Ist der Endpunkt und damit der zu untersuchende Punkt nicht sichtbar, wird im Laufe des Algorithmus festgestellt, dass keine derartige Verbesserung möglich ist. Der vorgestellte Algorithmus ist numerisch robust, einfach umzusetzen und besitzt eine in der Anzahl der Kanalecken lineare Laufzeit.
In dieser Arbeit wird eine neue Integraltransformation, die Roulettransformation, eingeführt. Diese arbeitet mit anisotropen Skalierungen und Rotationen. Es wird gezeigt, dass die Roulettransformation allgemeine gerichtete Singularitäten im Sinne von temperierten Distributionen auflöst. Die Abklingraten an Punkt- sowie Liniensingularitäten werden explizit angegeben.
Für Monumentalbauten als Teil unseres Kulturgutes im Speziellen als auch für Gebäude im Allgemeinen, wurden im Rahmen des MonArch- rojektes verschiedene Methoden zur digitalen Speicherung von Informationen über Monumentalbauten erforscht. Das daraus entstandene MonArch-System ist für die Dokumentation von Monumentalbauten verwendbar und speichert das digitale Modell des Bauwerks in einer relationalen Datenbank. Das digitale Modell des Bauwerks entsteht durch eine Segmentierung in Gebäudeteile, die dann in einer Strukturhierarchie zusammengefasst werden können. Als Strukturhierarchie versteht man in diesem Zusammenhang eine Hierarchie von Gebäudeteilen, die in einer Teil-von-Beziehung stehen. Die Strukturhierarchie erlaubt es Informationen z.B. Dokumente mit einem räumlichen Bezug auszuzeichnen. Zusätzlich wird eine Themenhierarchie unterstützt, die es erlaubt Informationen thematisch mit Begriffen zu beschreiben.
Betrachtet man räumliche und thematische Anfragen in vernetzten MonArch-Systemen, in denen sich mehrere Gebäudearchive zusammenschließen, ist diese starke Bindung der Information an die einzigartige Struktur jedes Gebäudes ein Hindernis für ein einfaches Verfahren zur räumlichen Suche. Da sich jedes Gebäude in seinem speziellen strukturellen und räumlichen Aufbau unterscheidet, liefert eine räumliche Anfrage, die speziell auf diese Eigenheiten eines Gebäudes ausgerichtet ist, für andere Gebäude keine Suchergebnisse. Für thematische Anfragen stellen nicht kompatible Themenhierarchien ein Hindernis dar, die eine übergreifende thematische Anfrage verhindern. Die größte Herausforderung ist es, Struktur- und Themenhierarchien aufeinander abzubilden.
Zur Lösung des geschilderten Problems wird in vernetzten Informationssystemen auf eine geeignete Transformation der ursprünglichen Anfrage zurückgegriffen, um den Anfragefokus zu erweitern (Relaxation) oder eine Anpassung an die Gegebenheiten des entfernten Informationssystems zu erreichen (Transformation). Das Anfragetransformations- und -relaxationsverfahren, das in dieser Arbeit vorgestellt wird, nutzt eine Generalisierungsbeziehung aus, um ausgehend von einer Anfrage an eine spezielle Struktur- und Themenhierarchie eine automatische Transformation der Anfrage durchzuführen. Bei Themenhierarchien sind gemeinsame Oberthemen ein Ansatzpunkt. Bei Strukturhierarchien können Typinformationen zu Gebäudeteilen die Generalisierungsbeziehung darstellen. Die transformierte und dadurch relaxierte Anfrage kann dann an ein Netzwerk von MonArch-Systemen gestellt werden, ohne dass eine manuelle Auswahl der Gebäudeteile in anderen Strukturhierarchien oder eine angepasste Themenauswahl erfolgen muss. Dazu muss die Strukturhierarchie der anderen Gebäude im Netzwerk von MonArch-Systemen nicht bekannt sein. Im Rahmen der vorliegenden Arbeit werden verschiedene Relaxationsverfahren, z.B. ein angepasstes Spreading-Activation-Verfahren, zur automatischen Anfragetransformation von räumlichen und thematischen Anfragen vorgestellt, mit dem Ziel eine vollständige Abbildung zwischen den Strukturhierarchien von Gebäuden und Themenhierarchien zu vermeiden. Erreicht wird das Ziel durch eine Erweiterung des MonArch-Datenmodells und eine Verallgemeinerung der MonArch-Anfragen, die eine Anfragetransformation zum Anfragezeitpunkt erlauben.
Splinekurven sind oft das erste Mittel der Wahl, wenn Daten interpoliert oder approximiert werden sollen. Sie spielen in vielen praktischen Anwendungsbereichen eine wichtige Rolle und sind in Bereichen des CAD/CAM nicht mehr weg zu denken. In der vorliegenden Arbeit werden in diesem Kontext Bahnpunkte zur Steuerung von Werkzeugmaschinen untersucht. Die Analyse wird mit Hilfe eines Multiresolution (MRA) Ansatzes für Splinekurven mit adaptiven Knotenfolgen realisiert. Dieser MRA Ansatz basiert auf einer Least-Squares-Projektion zum Knotenentfernen und unterscheidet sich somit zu bekannten Ansätzen, die auf orthogonalen Komplementen aufbauen. Des Weiteren wird ein Konzept zur Approximation von Orientierungsdaten mittels homogenen Quaternionensplines vorgestellt. Diese Splines leben auf der Sphäre und lassen sich mittels Knotenentfernen bzw. einfügen verfeinern. Somit lässt sich das vorgestellte MRA–Analyseverfahren ebenfalls auf diese Kurven anwenden. Weiter konnte für diese Kurven eine konvexe Hülle–Eigenschaft nachgewiesen werden.
Als sich in der ersten Hälfte des 19. Jahrhunderts zunehmend mehr bedeutende Mathematiker mit der Suche nach Invarianten beschäftigten, konnte natürlich noch niemand vorhersehen, dass die Invariantentheorie mit Beginn des Computerzeitalters in der Bildverarbeitung bzw. dem Rechnersehen ein äußerst fruchtbares Anwendungsgebiet finden wird. In dieser Arbeit wird eine neue Anwendungsmöglichkeit der Invariantentheorie in der Bildverarbeitung vorgestellt. Dazu werden lokale Bildmerkmale betrachtet. Dabei handelt es sich um die Koordinaten einer Polynomfunktion bzgl. einer geeigneten Orthonormalbasis von P_n(R^2,R), die die zeitintegrierte Sensorinputfunktion auf lokalen Pixelfenstern bestmöglich approximiert. Diese Bildmerkmale werden in vielen Anwendungen eingesetzt, um Objekte in Bildern zu erkennen und zu lokalisieren. Beispiele hierfür sind die Detektion von Werkstücken an einem Fließband oder die Verfolgung von Fahrbahnmarkierungen in Fahrerassistenzsystemen. Modellieren lässt sich die Suche nach einem Muster in einem Suchbild als Paar von Stereobildern, auf denen lokal die affin-lineare Gruppe AGL(R) operiert. Will man also feststellen, ob zwei lokale Pixelfenster in etwa Bilder eines bestimmten dreidimensionalen Oberflächenausschnitts sind, ist zu klären, ob die Bildausschnitte durch eine Operation der Gruppe AGL(R) näherungsweise ineinander übergeführt werden können. Je nach Anwendung genügt es bereits, passende Untergruppen G von AGL(R) zu betrachten. Dank der lokalen Approximation durch Polynomfunktionen induziert die Operation einer Untergruppe G eine Operation auf dem reellen Vektorraum P_n(R^2,R). Damit lässt sich das Korrespondenzproblem auf die Frage reduzieren, ob es eine Transformation T in G gibt so, dass p ungefähr mit der Komposition von q und T für die zugehörigen Approximationspolynome p,q in P_n(R^2,R) gilt. Mit anderen Worten, es ist zu klären, ob sich p und q näherungsweise in einer G-Bahn befinden, eine typische Fragestellung der Invariantentheorie. Da nur lokale Bildausschnitte betrachtet werden, genügt es weiter, Untergruppen G von GL_2(R) zu betrachten. Dann erhält man sofort auch die Antwort für das semidirekte Produkt von R^2 mit G. Besonders interessant für Anwendungen ist hierbei die spezielle orthogonale Gruppe G=SO_2(R) und damit insgesamt die eigentliche Euklidische Gruppe. Für diese Gruppe und spezielle Pixelfenster ist das Korrespondenzproblem bereits gelöst. In dieser Arbeit wird das Problem in eben dieser Konstellation ebenfalls gelöst, allerdings auf elegante Weise mit Methoden der Invariantentheorie. Der Ansatz, der hier vorgestellt wird, ist aber nicht auf diese Gruppe und spezielle Pixelfenster begrenzt, sondern leicht auf weitere Fälle erweiterbar. Dazu ist insbesondere zu klären, wie sich sogenannte fundamentale Invarianten von lokalen Bildmerkmalen, also letztendlich Invarianten von Polynomfunktionen, berechnen lassen, d.h. Erzeugendensysteme der entsprechenden Invariantenringe. Mit deren Hilfe lässt sich die Zugehörigkeit einer Polynomfunktion zur Bahn einer anderen Funktion auf einfache Weise untersuchen.
Neben der Vorstellung des Verfahrens zur Korrespondenzfindung und der dafür notwendigen Theorie werden in dieser Arbeit Erzeugendensysteme von Invariantenringen untersucht, die besonders "schöne" Eigenschaften besitzen. Diese schönen Erzeugendensysteme von Unteralgebren werden, analog zu Gröbner-Basen als Erzeugendensysteme von Idealen, SAGBI-Basen genannt ("Subalgebra Analogs to Gröbner Bases for Ideals"). SAGBI-Basen werden hier insbesondere aus algorithmischer Sicht behandelt, d.h. die Berechnung von SAGBI-Basen steht im Vordergrund. Dazu werden verschiedene Algorithmen erarbeitet, deren Korrektheit bewiesen und implementiert. Daraus resultiert ein Software-Paket zu SAGBI-Basen für das Computeralgebrasystem ApCoCoA, dessen Funktionalität in diesem Umfang in keinem Computeralgebrasystem zu finden sein wird. Im Zuge der Umsetzung der einzelnen Algorithmen konnte außerdem die Theorie der SAGBI-Basen an zahlreichen Stellen erweitert werden.
DoSeR - A Knowledge-Base-Agnostic Framework for Entity Disambiguation Using Semantic Embeddings
(2016)
Entity disambiguation is the task of mapping ambiguous terms in natural-language text to its entities in a knowledge base. It finds its application in the extraction of structured data in RDF (Resource Description Framework) from textual documents, but equally so in facilitating artificial intelligence applications, such as Semantic Search, Reasoning and Question & Answering. In this work, we propose DoSeR (Disambiguation of Semantic Resources), a (named) entity disambiguation framework that is knowledge-base-agnostic in terms of RDF (e.g. DBpedia) and entity-annotated document knowledge bases (e.g. Wikipedia). Initially, our framework automatically generates semantic entity embeddings given one or multiple knowledge bases. In the following, DoSeR accepts documents with a given set of surface forms as input and collectively links them to an entity in a knowledge base with a graph-based approach. We evaluate DoSeR on seven different data sets against publicly available, state-of-the-art (named) entity disambiguation frameworks. Our approach outperforms the state-of-the-art approaches that make use of RDF knowledge bases and/or entity-annotated document knowledge bases by up to 10% F1 measure.
Abstract zum Dissertationsfragment "Spotzuordnung und Wellenfront-Rekonstruktion für Shack-Hartmann-Sensoren" von Sascha Groening (20.04.1972 - 16.11.2001)
Sascha Groening war nach seinem Studium der Informatik an der Universität Passau von 01.Oktober 1998 bis 16. November 2001 wissenschaftlicher Mitarbeiter der Forschungsgruppe Entscheidungsunterstützende Systeme innerhalb des Forschungsverbundes Wissensbasierte Systeme, die 2005 in das Institut für Softwaresystem in technischen Anwendungen der Informatik an der Universität Passau überging.
Tragischerweise ist er am 16. November 2001 im Alter von nur 28 Jahren kurz vor der Fertigstellung seiner Dissertation völlig überraschend verstorben. In seiner Dissertation beschäftigte er sich mit Fragestellungen aus dem Teilprojekt „Entwicklung eines Messverfahrens mit hohem Dynamikbereich für die Qualitätssicherung von optischen Asphären für die in‐situ Messung von Wellenfronten (kurz Wellensensor)“ des Forschungsverbundes FORMIKROSYS II, der von der Bayerischen Forschungsstiftung gefördert wurde.
Auf den Sicherungen des Instituts konnten wir nur eine relativ unvollständige elektronische Version seiner Dissertation „Spotzuordnung und Wellenfrontrekonstruktion für Shack‐Hartmann‐Sensoren“ finden, da er seine Arbeit auf einem privaten PC anfertigte.
Monika Groening, seine Mutter, hat dagegen im Jahr 2013 privat unten stehenden Ausdruck seiner schriftlichen Arbeit gefunden, die einem Stand etwa zwei Wochen vor der geplanten Abgabe entspricht und die nun hiermit als Scan der Öffentlichkeit zur Verfügung gestellt wird.
Am Institut wurden nach Abschluss des Projektes Wellensensor die Forschungen auf diesem Gebiet nicht weiter verfolgt, da die Problemstellung des Projektes für die Partner, die die Lösung von Sascha Groening angewendet haben, zufriedenstellend gelöst war.
Im Rahmen des Projektes wurden die Leistungsgrenzen für ein Messgerät zur Vermessung von optischen Asphären (z.B. Gleitsicht‐Brillengläsern) und allgemeinen Wellenfronten (z.B. Strahlprofil eines Lasers, Wellenfront hinter einem optischen Subsystem) auf der Basis des Shack‐Hartmann‐Sensors erforscht. Das Prinzip beruht auf der geometrisch‐optischen Bestimmung lokaler Wellenfrontkrümmungen mit Hilfe eines Feldes von Mikrolinsen und einer CCD‐Kamera in der Fokalebene der Mikrolinsen. Sascha Groening entwickelte völlig neu konzipierte Auswertealgorithmen, die eine schnelle und zuverlässige Zuordnung von Fokuspunkten zu Mikrolinsen durchführen und damit eine hochgenaue Vermessung von
Ashären bei stark aberranten Wellenfronten möglich machen. Eine einfallende Wellenfront erzeugt in der Fokalebene der Mikrolinsen ein charakteristisches Spotmuster. Durch die Analyse der lokalen Ablenkungen der Spots von ihren Idealpositionen, also den Positionen, die bei Einfall einer ebenen Wellenfront entstehen würden, können Aussagen über das
lokale Steigungsverhalten der einfallenden Wellenfront getroffen werden. Je größer der Dynamikbereich des Messgerätes sein soll, desto schwieriger wird das Problem der Zuordnung von Spot zu Mikrolinse. Genau diese Herausforderung wurde von Sascha Gröning durch einen iterativen Spline‐Passungs‐Algorithmus schnell und elegant gelöst. Wenn dann
die Spotzuordnung erfolgt ist, kann die Wellenfront aus den lokalen Ablenkungen der Spots rekonstruiert werden.
Das Fragment der Dissertationsschrift ist vollständig bis auf Kapitel 1 Einleitung und Kapitel 7 Zusammenfassung. Außerdem fehlen in Kapitel 4 noch die Beschreibungen einiger untersuchter Verfahren zur Spotdetektion und in den Unterkapiteln von 5 und 6 fehlen die Verfahren zur Spotzuordnung und Wellenfrontrekonstruktion bei nicht stetig differenzierbaren bzw. unstetigen Wellenfronten. Ansonsten bietet die Arbeit aber einen guten Überblick über den Stand der Technik zur damaligen Zeit und erklärt die grundlegenden Verfahren, die von Sascha Groening erforscht und entwickelt wurden. In Kapitel 2 werden ausführlich das Funktionsprinzip des Shack‐Hartmann‐Sensors und die Wellenfrontvermessung erklärt, wobei speziell auf das Zuordnungsproblem von Spot zu Mikrolinse und auf die globale Wellenfrontrekonstruktion aus einem Feld partieller Ableitungen eingegangen wird.
Die mathematischen Grundlagen wie Tensorprodukt‐Splines oder die Lösungsverfahren für lineare Ausgleichsprobleme ohne und mit linearen Nebenbedingungen werden in Kapitel 3 gelegt. Einen ersten Schwerpunkt bildet Kapitel 4, das sich mit der Spotdetektion beschäftigt. Nach der Erläuterung der optischen Grundlagen wird die Spotentstehung mathematisch modelliert, um so geeignete Detektionsverfahren ableiten zu können.
Im zentralen Kapitel 5 der Dissertation geht es um die Spotzuordnung. Nach der Vorstellung bekannter Verfahren wird die neu entwickelte Spotzuordnung durch iterative Funktionspassung beschrieben. Nach einer initialen Zuordnung von einigen zentralen Spots, die unter Nutzung von Nebenwissen problemlos möglich ist, wird dann iterativ mit Hilfe von Splinepassungen vorgegangen. Bei einer vorhandenen Zuordnung wird durch Extrapolation der berechneten Splinepassung der Suchbereich für weitere, nicht zugeordnete Spots ausgedehnt, und diese werden dann wiederum korrekt zugeordnet. Diese Schritte werden iterativ wiederholt, bis alle Spots zugeordnet sind. Die Vorgehensweise, von bekanntem in unbekanntes Gebiet zu extrapolieren führt hier vortrefflich zum Ziel. Sascha Groening zeigt auch, dass der Erfolg vom gewählten Funktionsraum, hier Tensorprodukt‐Splines, abhängt. Schließlich runden die Verfahren zur Wellenfrontrekonstruktion, die ebenfalls auf Spline‐Passungen basieren, in Kapitel 6 die Arbeit ab.
Mit der Bereitstellung dieses Fragments seiner Dissertation wollen wir die geleistete Arbeit von Sascha Groening an der Universität Passau würdigen und hoffen, dass seine Ergebnisse ihren Platz in der wissenschaftlichen Gemeinschaft finden.
Im Mai 2015, Dr. Erich Fuchs
Eine Gruppe erfüllt die Tits-Alternative, wenn sie entweder eine nicht-abelsche freie Untergruppe vom Rang 2 enthält oder virtuell auflösbar ist, d. h. eine auflösbare Untergruppe von endlichem Index enthält. Diese Eigenschaft geht auf J. Tits zurück, der sie für endlich erzeugte lineare Gruppen nachwies. Es wird eine relevante Klasse endlich präsentierter Gruppen in Bezug auf die Tits-Alternative untersucht. Die betrachteten Gruppen stellen eine Verallgemeinerung von Pride-Gruppen und der von Vinberg betrachteten Gruppen erzeugt von periodisch gepaarten Relationen für drei Erzeugende dar. Zusätzlich treten diese Gruppen als Fundamentalgruppen hyperbolischer Orbifaltigkeiten auf. Es wird der Nachweis der Tits-Alternative unter bestimmten Voraussetzungen an die Präsentierungen der betrachteten Gruppen erbracht. Für diesen Nachweis werden verschiedene Methoden angewandt: Es werden zum einen homomorphe Bilder der Gruppen betrachtet. Zum anderen wird die Existenz wesentlicher Darstellungen in eine lineare Gruppe nachgewiesen. Basierend auf diesen Darstellungen kann in vielen Fällen der Nachweis der Existenz nicht-abelscher freier Untergruppen erbracht werden. Zusätzlich wird für den Nachweis der Endlichkeit und damit der Tits-Alternative einiger Gruppen eine Methode angewandt, die auf Berechnungen von Gröbner-Basen in nicht-kommutativen Polynomringen basiert. Es wird dabei die Dimension der Gruppenringe betrachtet als Vektorräume berechnet. Für die betrachtete Klasse von Gruppen wird für Relationen der Blocklänge 1 die Tits-Alternative vollständig nachgewiesen. Als Folgerung ergibt sich eine Klassifikation der endlichen unter diesen Gruppen.