Variational Domain Decomposition For Parallel Image Processing

Kohlberger, Timo

Vorschau

PDF
Dissertation_Timo_Kohlberger.pdf - Veröffentlichte Version
Download (7MB)

URL:	http://ub-madoc.bib.uni-mannheim.de/1427
URN:	urn:nbn:de:bsz:180-madoc-14276
Dokumenttyp:	Dissertation
Erscheinungsjahr:	2007
Titel einer Zeitschrift oder einer Reihe:	None
Verlag:	Universität Mannheim
Gutachter:	Schnörr, Christoph
Datum der mündl. Prüfung:	11 Juni 2007
Sprache der Veröffentlichung:	Englisch
Einrichtung:	Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Bildverarbeitung, Mustererkennung u. Computergrafik (Schnörr 1999-2008)
Fachgebiet:	004 Informatik
Fachklassifikation:	MSC: G.4 G.1.8 G.1.6 ,
Normierte Schlagwörter (SWD):	Bildverarbeitung , Numerische Mathematik
Freie Schlagwörter (Deutsch):	Gebietszerlegung , Variationionelle Methode , Partielle Differentialgleichungen
Freie Schlagwörter (Englisch):	Parallel Computing , Domain Decomposition , Variational Methods , PDE Parallelization
Abstract:	Many important techniques in image processing rely on partial differential equation (PDE) problems, which exhibit spatial couplings between the unknowns throughout the whole image plane. Therefore, a straightforward spatial splitting into independent subproblems and subsequent parallel solving aimed at diminishing the total computation time does not lead to the solution of the original problem. Typically, significant errors at the local boundaries between the subproblems occur. For that reason, most of the PDE-based image processing algorithms are not directly amenable to coarse-grained parallel computing, but only to fine-grained parallelism, e.g. on the level of the particular arithmetic operations involved with the specific solving procedure. In contrast, Domain Decomposition (DD) methods provide several different approaches to decompose PDE problems spatially so that the merged local solutions converge to the original, global one. Thus, such methods distinguish between the two main classes of overlapping and non-overlapping methods, referring to the overlap between the adjacent subdomains on which the local problems are defined. Furthermore, the classical DD methods --- studied intensively in the past thirty years --- are primarily applied to linear PDE problems, whereas some of the current important image processing approaches involve solving of nonlinear problems, e.g. Total Variation (TV)-based approaches. Among the linear DD methods, non-overlapping methods are favored, since in general they require significanty fewer data exchanges between the particular processing nodes during the parallel computation and therefore reach a higher scalability. For that reason, the theoretical and empirical focus of this work lies primarily on non-overlapping methods, whereas for the overlapping methods we mainly stay with presenting the most important algorithms. With the linear non-overlapping DD methods, we first concentrate on the theoretical foundation, which serves as basis for gradually deriving the different algorithms thereafter. Although we make a connection between the very early methods on two subdomains and the current two-level methods on arbitrary numbers of subdomains, the experimental studies focus on two prototypical methods being applied to the model problem of estimating the optic flow, at which point different numerical aspects, such as the influence of the number of subdomains on the convergence rate, are explored. In particular, we present results of experiments conducted on a PC-cluster (a distributed memory parallel computer based on low-cost PC hardware for up to 144 processing nodes) which show a very good scalability of non-overlapping DD methods. With respect to nonlinear non-overlapping DD methods, we pursue two distinct approaches, both applied to nonlinear, PDE-based image denoising. The first approach draws upon the theory of optimal control, and has been successfully employed for the domain decomposition of Navier-Stokes equations. The second nonlinear DD approach, on the other hand, relies on convex programming and relies on the decomposition of the corresponding minimization problems. Besides the main subject of parallelization by DD methods, we also investigate the linear model problem of motion estimation itself, namely by proposing and empirically studying a new variational approach for the estimation of turbulent flows in the area of fluid mechanics.
Übersetzter Titel:	Variationelle Gebietszerlegung zur parallelen Bildverarbeitung (Deutsch)
Übersetzung des Abstracts:	Viele Bildverarbeitungsverfahren basieren auf linearen und nicht-linearen partiellen Differenzialgleichungen (PDG), welche räumliche Abhängigkeiten zwischen den Unbekannten über den gesamten Bereich der Bildebene aufweisen. Eine direkte räumliche Zerlegung in seperate Teilprobleme und daran anschließende parallele Berechnung führt nicht zur Lösung des ursprünglichen Problems. Typischerweise treten starke Fehler an den lokalen Grenzen zwischen den Teilgebieten auf. Folglich ermöglichen die meisten PDG-basierten Bildverarbeitungsalgorithmen keine direkten grob-körnigen Parallelisierungen, sondern nur solche für fein-körnige, z.B. auf der Ebene der einzelnen Rechenoperationen des jeweiligen Lösungsverfahrens. Im Gegensatz dazu stellen Gebietszerlegungsmethoden (GZ) verschiedene Ansätze zur räumlichen Zerlegung von PDG-Problemen zur Verfügung, so daß die vereinigte Lösung der lokalen Teilprobleme zur ursprünglichen Lösung konvergiert. Hierbei wird zwischen den beiden Klassen der überlappenden und nicht-überlappenden Methoden -- in Bezug auf die Überdeckung von benachbarten Teilgebieten -- unterschieden. Zudem werden klassische Gebietszerlegungsmethoden -- selbst Gegenstand intensiver Forschung in den vergangenen dreißig Jahren -- primär auf lineare PDG-Probleme angewandt, wohingegen viele der heutigen Bildverarbeitungsverfahren, wie z.B. solche basierend auf der total Ableitung (TA), nicht-lineare Probleme mit sich bringen. Unter den linearen GZ-Methoden sind die Nicht-\"Uberlappenden generell von Vorteil, da sie im allgemeinen einen wesentlich geringen Datenaustausch zwischen den einzelnen Rechenknoten während der parallelen Berechnung erfordern und hierdurch eine höhere Skalierbarkeit erreichen. Daher liegt der theoretische und empirische Schwerpunkt dieser Arbeit hauptsächlich auf nicht-überlappenden Methoden, wohingegen wir in bezug auf die überlappenden Methoden im Großen und Ganzen bei der Erklärung der verschiedenen Berechnungsverfahren verbleiben. Bei den linearen nicht-überlappenden GZ-Methoden konzentrieren wir uns zu Beginn auf die theoretischen Grundlagen, welche hernach als Basis für die Herleitung der verschiedenen Algorithmen dient. Obwohl wir einen großen Bogen von den relativen simplen Methoden auf zwei Teilgebieten bis zu den heutigen Zwei-Gitter-Methoden auf einer beliebigen Anzahl von Teilgebieten spannen, beschränken sich die experimentellen Studien auf zwei prototypische Verfahren, anhand deren, in Anwendung auf das lineare Modellproblem der Bewegungschätzung, verschiedene numerische Aspekte, wie z.B. der Einfluß der Anzahl der Teilgebiete auf die Konvergenzgeschwindigkeit, untersucht werden. Im besonderen präsentieren wir experimentelle Ergebnisse, die auf einem PC-Cluster (einem auf kostengünstiger PC-Hardware basierenden Parallelcomputer mit verteiltem Speicher) mit bis zu 144 Prozeßknoten durchgeführt erzielt, die ihrerseits die sehr guten Skalierungseigenschaften von nicht-überlappenden GZ-Methoden aufzeigen. Im Hinblick auf nicht-lineare nicht-überlappende GZ-Methoden verfolgen wir zwei unterschiedliche Ansätze, beide jedoch in Anwendung auf nicht-lineare, PDG-basierte Bildentrauschung. Die erste Methode basiert auf einem kontroll\-theoretischen Ansatz, welcher bereits erfolgreich zur Parallelisierung von Navier-Stokes-Gleichungen eingesetzt wurde. Der zweite nicht-lineare Gebietszerlegungsansatz hingegen fußt auf konvexer Programmierung und basiert auf einer Zerlegung der korrespondierenden Minimierungsprobleme. Neben des Hauptthemas der Parallelisierung durch GZ-Methoden untersuchen wir auch das lineare Modellproblem der Bewegungsschätzung selbst. Hierbei stellen wir einen neuen variationellen Ansatz zur Schätzung von turbulenten Flußfeldern auf dem Gebiet der Flußmechanik vor und untersuchen ihn experimentell. (Deutsch)
Zusätzliche Informationen:

Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.

Suche Autoren in

BASE: Kohlberger, Timo

Google Scholar: Kohlberger, Timo

Download-Statistik

Downloads im letzten Jahr

Detaillierte Angaben

Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail

Actions (login required)

Eintrag anzeigen