Fast explicit methods for PDE-based image analysis

Abstract

This thesis introduces a novel fast explicit diffusion (FED) scheme that uses varying time step sizes to efficiently solve parabolic problems. For the efficient solution of elliptic problems, we embed FED as well as an FED-based solver for linear systems of equations, the Fast-Jacobi method, in a cascadic coarse-to-fine approach. Both FED and Fast-Jacobi are very well-suited for simple, parallel implementations. FED is motivated from a decomposition of box filters, which is a well-known signal processing tool, in terms of explicit schemes for one-dimensional linear diffusion problems. The corresponding time step sizes violate the stability restrictions of usual explicit schemes in up to 50 percent of all cases. Unlike the known Super Time Stepping (STS) approach, it does not require an additional damping parameter due to the derivation based on signal processing. To improve the numerical stability, we present an FED Runge-Kutta scheme and a semi-iterative version of the Fast-Jacobi method. Regarding nonlinear problems, these approaches allow update strategies that can further improve both the accuracy and efficiency. Finally, we show that FED can be combined with extrapolation methods. This yields stable, higher order explicit schemes for the solution of parabolic problems.

Diese Arbeit stellt ein neues schnelles explizites Diffusionsschema (FED) vor, das wechselnde Zeitschrittweiten nutzt, um parabolische Probleme effizient zu lösen. Für die effiziente Lösung von elliptischen Problemen bauen wir FED und auch einen auf FED basierenden Löser für lineare Gleichungssysteme, das schnelle Jacobi-Verfahren, in ein kaskadiertes Mehrgitterverfahren ein. Sowohl FED als auch das schnelle Jacobi-Verfahren sind sehr gut für einfache parallele Implementierungen geeignet. FED wird durch eine Zerlegung von aus der Signalverarbeitung bekannten Mittelwertfiltern im Sinne von expliziten Schemata für eindimensionale lineare Diffusionsprobleme motiviert. Die entsprechenden Zeitschrittweiten verletzen die Stabilitätsbedingungen gewöhnlicher expliziter Schemata in bis zu 50 Prozent der Fälle. Anders als das bekannte Superzeitschrittverfahren (STS) benötigt es dank der auf der Signalverarbeitung basierenden Herleitung keinen zusätzlichen Dämpfungsparameter. Zur Verbesserung der numerischen Stabilität präsentieren wir ein FED Runge-Kutta Schema und eine semi-iterative Version des schnellen Jacobi-Verfahrens. Im Bezug auf nichtlineare Probleme erlauben diese Verfahren Updatestrategien, die sowohl die Genauigkeit als auch die Effizienz weiter verbessern können. Schließlich zeigen wir, dass FED mit Extrapolationsverfahren kombiniert werden kann. Dies liefert stabile explizite Schemata höherer Ordnung zur Lösung parabolischer Probleme.