Connected-Component-Labeling (CCL) für 2D-Bilddaten ist ein bekanntes Problem im Bereich der Bildverarbeitung. Ziel ist es, zusammenhängende Pixelgruppen mit gleichen Eigenschaften zu erkennen und mit einem eindeutigen Label zu versehen. Zur Lösung von CCL-Problemen für 2D-Bilddaten werden sowohl sequentielle als auch parallele Algorithmen untersucht. Unter den bekannten Algorithmen gibt es solche, die asymptotisch optimale Eigenschaften besitzen. Speziell für den Bereich der Bildverarbeitung interessant sind außerdem auf Konturierung basierende Algorithmen. Die zusätzlich extrahierten Konturen können z.B. für die Buchstabenerkennung genutzt werden. Seit der jüngeren Vergangenheit werden Grafikprozessoren (GPUs) mit großem Erfolg für allgemeines Computing eingesetzt. So existieren auch mehrere Implementationen von Connected-Component-Labeling-Algorithmen für GPUs, welche im Vergleich mit Varianten für CPUs oft deutlich schneller sind. Diese GPU-basierten Ansätze verarbeiten typischerweise das Pixelgitter direkt. Im Rahmen der vorliegenden Arbeit werden mehrere neue parallele CCL-Algorithmen vorgeschlagen, welche auf Konturen basieren und sowohl für GPUs als auch für Multicore-CPUs geeignet sind. Diese werden experimentell mit Implementationen aus der Literatur unter Verwendung aktueller GPUs und CPUs verglichen. Dabei erreichen in vielen Fällen die vorgeschlagenen Techniken ein besseres Laufzeitverhalten. Das ist auf GPUs insbesondere dann besonders deutlich, wenn sich die evaluierten Datensätze durch einen geringen Anteil von Konturen im Vergleich zur Fläche der Connected-Components auszeichnen.

Random sampling is an appealing approach to build synopses of large data streams because random samples can be used for a broad spectrum of analytical tasks. Users are often interested in analyzing only the most recent fraction of the data stream in order to avoid outdated results. In this paper, we focus on sampling schemes that sample from a sliding window over a recent time interval; such windows are a popular and highly comprehensible method to model recency. In this setting, the main challenge is to guarantee an upper bound on the space consumption of the sample while using the allotted space efficiently at the same time. The difficulty arises from the fact that the number of items in the window is unknown in advance and may vary significantly over time, so that the sampling fraction has to be adjusted dynamically. We consider uniform sampling schemes, which produce each sample of the same size with equal probability, and stratified sampling schemes, in which the window is divided into smaller strata and a uniform sample is maintained per stratum. For uniform sampling, we prove that it is impossible to guarantee a minimum sample size in bounded space. We then introduce a novel sampling scheme called bounded priority sampling (BPS), which requires only bounded space. We derive a lower bound on the expected sample size and show that BPS quickly adapts to changing data rates. For stratified sampling, we propose a merge-based stratification scheme (MBS), which maintains strata of approximately equal size. Compared to naive stratification, MBS has the advantage that the sample is evenly distributed across the window, so that no part of the window is over- or underrepresented. We conclude the paper with a feasibility study of our algorithms on large real-world datasets.

Der steigende Trend zur Urbanisierung stellt sowohl auf lokaler als auch auf globaler Ebene eine beträchtliche Herausforderung dar. Bis zum Jahr 2050 werden beinahe 7 von 10 Menschen in städtischen Gebieten leben, was einer Verdopplung der städtischen Bevölkerung gleichkommt. Die Schwierigkeit liegt darin, dass städtische Regionen momentan im Durchschnitt doppelt so schnell expandieren wie ihre Bevölkerung wächst. Man erwartet, dass das Anwachsen der städtischen Bevölkerung zusammen mit der wirtschaftlichen Entwicklung in den nächsten drei Jahrzehnten weltweit zu einer zusätzlichen bebauten Fläche von etwa 1,2 Millionen km2 führen wird. Neben negativen Auswirkungen wie dem Verlust von fruchtbaren Böden und Biodiversität durch Versiegelung und Fragmentierung, bieten Urbanisierungsprozesse auch Chancen für eine nachhaltigere Entwicklung. Daher ist es wichtig, diesen Prozess zu steuern, um die negativen Auswirkungen zu minimieren. Die Steuerung der Siedlungsentwicklung erfordert verlässliche Datengrundlagen. Die derzeitige Datenlage in Deutschland beruht jedoch eher auf Annahmen und Schätzungen denn empirischen Erhebungen. Ursache hierfür ist die Erfassung von Nutzungsänderungen aggregiert auf administrative Einheiten und deren Zusammenfassung in einer Nutzungsklasse, der Siedlungs- und Verkehrsfläche. Damit können weder kleinräumige Flächenänderungen noch die Qualität der Änderungen hinreichend bestimmt werden. In Wissenschaft, Stadt- und Regionalplanung besteht daher gleichermaßen Bedarf an aktuellen, homogenen, aussagekräftigen und ökonomisch generierten Informationen zur Siedlungsentwicklung. Im Rahmen dieser Arbeit wurde ein Abgrenzungsverfahren zur Erstellung detaillierter Siedlungsabgrenzungen, insbesondere des Innenbereichs im baurechtlichen Sinne, entwickelt. Um eine möglichst breite Anwendbarkeit zu gewährleisten, wurden als Eingangsdaten ausschließlich Gebäudegrundrisse und allgemein verfügbare topographische Daten verwendet. Nach einer Partitionierung des Datensatzes erfolgte eine semantische Filterung und Aggregation über einen dichtegesteuerten Clusteralgorithmus. Eine besondere Herausforderung stellte dabei die Berücksichtigung planerischer und rechtlicher Aspekte in Deutschland dar. Die Anwendung der Methode erfolgte in Untersuchungsgebieten in Frankfurt am Main, in der Region Hannover und im ländlichen Raum Brandenburgs. Die Abgrenzungsergebnisse wurden mit Hilfe von GIS-Analysen und Expertenbefragungen evaluiert. Die Ergebnisse zeigen, dass die Methode in der Lage ist, sowohl ländliche Gebiete als auch Großstädte und Ballungsräume mit einer Genauigkeit von 75 bis 94 % im Vergleich zu Expertenabgrenzungen abzubilden. Insbesondere Gebiete mit Wohn- und Mischbebauung liefern sehr gute Ergebnisse. Optimierungspotenzial bieten dagegen Flächen mit Sondernutzungen oder stark heterogene Siedlungsbereiche. Das Verfahren stellt somit ein wertvolles Instrument zur Generierung von Grundlagendaten für zukünftige Studien oder Fachanwendungen dar. Die automatisiert generierten Abgrenzungen können Planungsaufgaben auf verschiedenen räumlichen Ebenen unterstützen, sie bilden die Grundlage für die Bestimmung von Innenentwicklungspotenzialen bzw. -indikatoren und eignen sich außerdem für Untersuchungen zur Zersiedelung.:Übereinstimmungserklärung Danksagung Zusammenfassung Abstract Abkürzungsverzeichnis Abbildungsverzeichnis Tabellenverzeichnis 1. Einleitung 1 1.1. Reduzierung der Flächeninanspruchnahme als politisches Ziel 1.2. Funktion des Siedlungsflächenmonitoring 1.3. Problemstellung 1.4. Zielstellung und Forschungsfragen 1.5. Aufbau der Arbeit 2. Forschungsansätze für automatisierte Siedlungsabgrenzungen 2.1. Datenquellen 2.2. Methoden 2.3. Bewertung bisheriger Ansätze 3. Begriffliche und konzeptionelle Grundlagen 3.1. Im Zusammenhang bebauter Ortsteil 3.1.1. Vorhaben 3.1.2. Bebauungszusammenhang 3.1.3. Ortsteil 3.2. Baulücke 3.3. Außenbereich im Innenbereich 3.4. Innenbereichssatzungen 3.4.1. Klarstellungssatzung 3.4.2. Entwicklungssatzung 3.4.3. Einbeziehungs- oder Ergänzungssatzung 3.5. Außenbereich 4. Verfahrensentwicklung 4.1. Allgemeiner methodischer Ansatz 4.2. Eingangsdaten 4.3. Anforderungen 4.4. Methodik 4.4.1. Partitionierung 4.4.2. Erstellung von Baublockgeometrien 4.4.3. Ermittlung Überbauungsgrad 4.4.4. Filterung 4.4.5. Identifizierung dicht bebauter Blöcke 4.4.6. Aggregation mittels minimalen Spannbaum 4.4.7. Nachbearbeitung 4.5. Parametrisierung des Verfahrens 4.5.1. Eingangsdaten für Innenbereichsabgrenzung 4.5.2. Objektauswahl für die Filterung 4.5.3. Schwellwert für dicht bebaute Blöcke 4.5.4. Größe von Baulücken und Freiflächen 4.5.5. Größe von Außenbereichsflächen im Innenbereich 4.5.6. Mindestanzahl von Gebäuden und Mindestgröße eines Ortsteils 4.5.7. Abgrenzung der Innenbereichsflächen vom Außenbereich 4.6. Programmtechnische Umsetzung 5. Evaluationsmethodik 5.1. Vorüberlegungen 5.1.1. Ziel der Bewertung 5.1.2. Definition von Qualität 5.1.3. Kontext der Bewertung 5.1.4. Qualitative und quantitative Methoden zur Bewertung von Geometrien 5.2. Empirische Bestimmung der Abgrenzungsqualität 5.3. Bestimmung der Abgrenzungsqualität mittels Expertenbefragung 5.3.1. Umsetzung der Datenerhebung mittels Fragebogen 5.3.2. Datenerhebungstechnik 5.3.3. Erfassen und Auswerten von Daten 5.3.4. Stichprobenbildung für Experteninterviews 5.3.5. Bewertung der Innenbereichsgeometrien 5.3.6. Mögliche Fehlerquellen von Umfragen 5.3.7. Gütekriterien 6. Ergebnisse 6.1. Vergleich der Abgrenzungsergebnisse mittels Referenzdaten 6.1.1. Untersuchungsgebiete und verwendete Daten 6.1.2. Auswertung GIS-Analyse 6.2. Auswertung der Befragung und Experteneinschätzung 6.2.1. Vorerfahrungen der Teilnehmenden 6.2.2. Allgemeine Fragen zum Thema Innenbereich 6.2.3. Beurteilung der Karten 6.2.4. Auswertung der Bewertungen der Karten nach Flächennutzung 6.2.5. Bewertung aller Abgrenzungen im Untersuchungsgebiet 6.2.6. Urteile zu Einsatzmöglichkeiten des Verfahrens 7. Diskussion 7.1. Stärken und Schwächen des Verfahrens 7.2. Beurteilung der quantitativen Bewertungsmethode 7.2.1. Einfluss der Siedlungsstruktur auf das Abgrenzungsergebnis 7.2.2. Umgang mit unvollständigen Referenzabgrenzungen 7.3. Bewertung der Expertenbefragung 7.4. Herausforderungen der Innenbereichsabgrenzung 7.4.1. Wohnbebauung 7.4.2. Kleingartensiedlungen 7.4.3. Wochenendhaussiedlungen 7.4.4. Industrie- und Gewerbegebiete 7.4.5. Tagebau 7.4.6. Landwirtschaftliche Betriebe 7.4.7. Streusiedlungen und Einzelgehöfte 7.4.8. Großflächige Photovoltaikanlagen 7.4.9. Kasernen 7.5. Fehlerbetrachtung 7.6. Vergleich mit anderen Studien 7.7. Anwendung und Übertragbarkeit 8. Fazit und Ausblick 8.1. Kriterien für die Innenbereichsabgrenzung und Aspekte bei der Abgrenzung durch Experten 8.2. Ansatz, Voraussetzungen und Vorgehen beim automatisierten Abgrenzen von Innenbereichen 8.3. Einfluss Struktur der Siedlungen auf die Abgrenzungsqualität 8.4. Anwendungsfelder einer Innenbereichsabgrenzung 8.5. Forschungsbedarf A. Anhang A.1. Befragungsergebnisse A.1.1. Einführungstext zur Befragung A.1.2. Hintergrund der Teilnehmenden A.1.3. Grundlagen Innenbereich A.1.4. Bewertung der Karten A.1.5. Bewertung der Abgrenzung in der Gesamtheit A.2. Detailauswertung nach Flächennutzungen A.3. Quellcode A.3.1. Skripte IB-Tool A.3.2. Skript qualitative Bewertung A.3.3. Skript Auswertung Befragung A.3.4. Zufallsfunktion für Flächenauswahl A.4. Geodaten Literaturverzeichnis

Die vorliegende Arbeit befasst sich mit der Erfassung von Oberflächen mittels Streifenprojektionsverfahren. Dabei wird ein Berechnungsmodell erarbeitet, welches den durch eine Aufnahme erfassten Bereich der Objektoberfläche berechnet und bewertet. Mithilfe einer optimalen Positionierung von Einzelaufnahmen ist es möglich, ein Objekt bei festgelegten Randbedingungen zeitsparend zu erfassen.

No description available.

Answer Set Programming (ASP) is an emerging paradigm for declarative programming, in which a computational problem is specified by a logic program such that particular models, called answer sets, match solutions. ASP faces a growing range of applications, demanding for high-performance tools able to solve complex problems. ASP integrates ideas from a variety of neighboring fields. In particular, automated techniques to search for answer sets are inspired by Boolean Satisfiability (SAT) solving approaches. While the latter have firm proof-theoretic foundations, ASP lacks formal frameworks for characterizing and comparing solving methods. Furthermore, sophisticated search patterns of modern SAT solvers, successfully applied in areas like, e.g., model checking and verification, are not yet established in ASP solving. We address these deficiencies by, for one, providing proof-theoretic frameworks that allow for characterizing, comparing, and analyzing approaches to answer set computation. For another, we devise modern ASP solving algorithms that integrate and extend state-of-the-art techniques for Boolean constraint solving. We thus contribute to the understanding of existing ASP solving approaches and their interconnections as well as to their enhancement by incorporating sophisticated search patterns. The central idea of our approach is to identify atomic as well as composite constituents of a propositional logic program with Boolean variables. This enables us to describe fundamental inference steps, and to selectively combine them in proof-theoretic characterizations of various ASP solving methods. In particular, we show that different concepts of case analyses applied by existing ASP solvers implicate mutual exponential separations regarding their best-case complexities. We also develop a generic proof-theoretic framework amenable to language extensions, and we point out that exponential separations can likewise be obtained due to case analyses on them. We further exploit fundamental inference steps to derive Boolean constraints characterizing answer sets. They enable the conception of ASP solving algorithms including search patterns of modern SAT solvers, while also allowing for direct technology transfers between the areas of ASP and SAT solving. Beyond the search for one answer set of a logic program, we address the enumeration of answer sets and their projections to a subvocabulary, respectively. The algorithms we develop enable repetition-free enumeration in polynomial space without being intrusive, i.e., they do not necessitate any modifications of computations before an answer set is found. Our approach to ASP solving is implemented in clasp, a state-of-the-art Boolean constraint solver that has successfully participated in recent solver competitions. Although we do here not address the implementation techniques of clasp or all of its features, we present the principles of its success in the context of ASP solving. / Antwortmengenprogrammierung (engl. Answer Set Programming; ASP) ist ein Paradigma zum deklarativen Problemlösen, wobei Problemstellungen durch logische Programme beschrieben werden, sodass bestimmte Modelle, Antwortmengen genannt, zu Lösungen korrespondieren. Die zunehmenden praktischen Anwendungen von ASP verlangen nach performanten Werkzeugen zum Lösen komplexer Problemstellungen. ASP integriert diverse Konzepte aus verwandten Bereichen. Insbesondere sind automatisierte Techniken für die Suche nach Antwortmengen durch Verfahren zum Lösen des aussagenlogischen Erfüllbarkeitsproblems (engl. Boolean Satisfiability; SAT) inspiriert. Letztere beruhen auf soliden beweistheoretischen Grundlagen, wohingegen es für ASP kaum formale Systeme gibt, um Lösungsmethoden einheitlich zu beschreiben und miteinander zu vergleichen. Weiterhin basiert der Erfolg moderner Verfahren zum Lösen von SAT entscheidend auf fortgeschrittenen Suchtechniken, die in gängigen Methoden zur Antwortmengenberechnung nicht etabliert sind. Diese Arbeit entwickelt beweistheoretische Grundlagen und fortgeschrittene Suchtechniken im Kontext der Antwortmengenberechnung. Unsere formalen Beweissysteme ermöglichen die Charakterisierung, den Vergleich und die Analyse vorhandener Lösungsmethoden für ASP. Außerdem entwerfen wir moderne Verfahren zum Lösen von ASP, die fortgeschrittene Suchtechniken aus dem SAT-Bereich integrieren und erweitern. Damit trägt diese Arbeit sowohl zum tieferen Verständnis von Lösungsmethoden für ASP und ihrer Beziehungen untereinander als auch zu ihrer Verbesserung durch die Erschließung fortgeschrittener Suchtechniken bei. Die zentrale Idee unseres Ansatzes besteht darin, Atome und komposite Konstrukte innerhalb von logischen Programmen gleichermaßen mit aussagenlogischen Variablen zu assoziieren. Dies ermöglicht die Isolierung fundamentaler Inferenzschritte, die wir in formalen Charakterisierungen von Lösungsmethoden für ASP selektiv miteinander kombinieren können. Darauf aufbauend zeigen wir, dass unterschiedliche Einschränkungen von Fallunterscheidungen zwangsläufig zu exponentiellen Effizienzunterschieden zwischen den charakterisierten Methoden führen. Wir generalisieren unseren beweistheoretischen Ansatz auf logische Programme mit erweiterten Sprachkonstrukten und weisen analytisch nach, dass das Treffen bzw. Unterlassen von Fallunterscheidungen auf solchen Konstrukten ebenfalls exponentielle Effizienzunterschiede bedingen kann. Die zuvor beschriebenen fundamentalen Inferenzschritte nutzen wir zur Extraktion inhärenter Bedingungen, denen Antwortmengen genügen müssen. Damit schaffen wir eine Grundlage für den Entwurf moderner Lösungsmethoden für ASP, die fortgeschrittene, ursprünglich für SAT konzipierte, Suchtechniken mit einschließen und darüber hinaus einen transparenten Technologietransfer zwischen Verfahren zum Lösen von ASP und SAT erlauben. Neben der Suche nach einer Antwortmenge behandeln wir ihre Aufzählung, sowohl für gesamte Antwortmengen als auch für Projektionen auf ein Subvokabular. Hierfür entwickeln wir neuartige Methoden, die wiederholungsfreies Aufzählen in polynomiellem Platz ermöglichen, ohne die Suche zu beeinflussen und ggf. zu behindern, bevor Antwortmengen berechnet wurden.

Convex cycles play a role e.g. in the context of product graphs. We introduce convex cycle bases and describe a polynomial-time algorithm that recognizes whether a given graph has a convex cycle basis and provides an explicit construction in the positive case. Relations between convex cycles bases and other types of cycles bases are discussed. In particular we show that if G has a unique minimal cycle bases, this basis is convex. Furthermore, we characterize a class of graphs with convex cycles bases that includes partial cubes and hence median graphs. (authors' abstract) / Series: Research Report Series / Department of Statistics and Mathematics

We study algorithms for efficient compression and decompression of a sequence of integers on modern hardware. Our focus is on universal codes in which the codeword length is a monotonically non-decreasing function of the uncompressed integer value; such codes are widely used for compressing 'small integers'. In contrast to traditional integer compression, our algorithms make use of the SIMD capabilities of modern processors by encoding multiple integer values at once. More specifically, we provide SIMD versions of both null suppression and Elias gamma encoding. Our experiments show that these versions provide a speedup from 1.5x up to 6.7x for decompression, while maintaining a similar compression performance.

Es gibt viele praktische Probleme im GIS, die derzeit nicht automatisch gelöst werden können, nicht weil unsere Algorithmen zu langsam sind, sondern weil wir überhaupt keinen zufriedenstellenden Algorithmus haben. Dies kann vorkommen, wenn es um Semantik geht, z. B. beim Extrahieren von Informationen oder beim Entwerfen von Visualisierungen. Von einem Computer kann derzeit nicht erwartet werden, dass er solche Probleme völlig unbeaufsichtigt löst. Darum betrachten wir den menschlichen Einsatz explizit als Ressource. Ein Algorithmus soll so viel Arbeit wie möglich in hoher Qualität leisten – aber entscheidend ist auch, dass er intelligent genug ist, um zu sehen, wo er Hilfe braucht, was er den Benutzer fragen sollte und wie er dessen Antworten berücksichtigt. Dieses Konzept bezieht sich auf neue Bereiche der Informatik wie aktives Lernen, aber wir legen den Fokus auf das richtige Design und die Analyse von Algorithmen und den daraus resultierenden Dialog zwischen Algorithmus und Mensch, den wir algorithmisch geführte Benutzerinteraktion nennen. Dieser Ansatz soll auf die Informationsextraktion aus historischen Karten angewandt werden.

Im Rahmen des 180jährigen Jubiläums der technischen Universität Chemnitz fand am 28. April 2016 das zweite Studierendensymposium der Fakultät Informatik statt. Das Studierendensymposium Informatik richtete sich inhaltlich an alle Themen rund um die Informatik und ihre Anwendungen: Ob Hardware oder Software, ob technische Lösungen oder Anwenderstudien, ob Programmierung oder Verwendung, ob Hardcore-Technik oder gesellschaftliche Fragestellungen – alles, was mit informatischen Lösungen zu tun hat, war willkommen. Das Studierendensymposium Informatik war dabei weder auf die Fakultät Informatik noch auf die TU Chemnitz begrenzt. Es wurden explizit Einreichungen aus thematisch angrenzenden Fächern beworben und Hochschulen der Region in die Planung und Organisation eingebunden. Der Tagungsband enthält die 21 Beitrage, die auf dem Symposium vorgestellt wurden. / In the course of the 180 year anniversary of the Technische Universität Chemnitz the Department of Computer Science held the second Students Symposium on April 18, 2016. The symposium addressed topics related to computer science and its applications: Whether hardware or software, whether technical solutions or user studies, whether programming or use, whether hardcore technology or social issues - everything concerned with computational solutions was welcomed. The Students Symposium included explicitly submissions from thematically adjacent departments and involved universities in the region in planning and organization. The proceedings contain the 21 papers (full and short), which were presented at the symposium.