Snakes für Aufgaben der digitalen Photogrammetrie und Topographie

Abstract

Snakes gelten in der Computer Vision als ein allgemein bekanntes Verfahren zum automatisierten (halbautomatischen) Extrahieren von Kanten und Linien in digitalen Bildern. Ausgehend von einer groben Naeherung der Form der gesuchten Kurve und ihrer Lage im Bild verbessert die Snake ihre Form und Lage durch Optimierung eines komplexen Energiefunktionals. Dabei soll sie die gesuchte Kurve detailgetreu nachbilden. Die Staerken von Snakes liegen in ihrer Robustheit gegenueber Rauschen im Bild und Luecken in der abgebildeten Kurve. Zahlreiche kritische Konstellationen wurden allerdings publiziert, die ihr Konvergenzverhalten und ihre Robustheit beeintraechtigen. Es soll beurteilt werden inwieweit sich Snakes auch angesichts ihrer Schwaechen für Aufgaben in der digitalen Photogrammetrie und Topographie eignen. Schwaechen der Methode waren für viele dem urspruenglichen Aufsatz folgende Publikationen Anlass zur Verbesserung der Methode. Ein Schwerpunkt dieser Arbeit ist eine umfassende Zusammenstellung und Beurteilung erweiterter und verbesserter Ansaetze. Weiters werden einige im Rahmen der Dissertation erarbeitete Bausteine zu einem für die jeweilige Anwendung optimalen Ansatz vorgestellt. Die Probleme der Snakes koennen auf drei verschiedene Arten geloest werden: Wahl des Optimierungsalgorithmus: Fuenf verschiedene Optimierungsmethoden werden präsentiert. Neben der urspruenglichen Lösung über Variationsrechnung werden die Loesungen mittels dynamischer Programmierung, mittels kleinster-Quadrate-Ausgleichung, mittels eines Level-Set-Ansatzes sowie mittels Simulated Annealing untersucht. Anpassung der Energiefunktion: Die Energiefunktion besteht aus mehreren Termen für unterschiedliche Zwecke. Die vielfaeltigen publizierten Formulierungen der Energieterme werden analysiert. Insbesondere die internen Energieterme, die für eine glatte Form der Snake verantwortlich sind, werden kritisch betrachtet. Neue Formulierungen werden vorgeschlagen, die das Schrumpfen der Kurve unterbinden sollen. Einsatz einer speziellen Anwendungsstrategie: Hierarchische Strategien, eine Strategie vom Groben ins Feine oder die Optimierung zwischen zwei Punkten wurden in der Literatur bereits vorgeschlagen. Im Rahmen dieser Arbeit wurden andere Strategien entwickelt: die Unterteilung in Segmente sowie die Verwendung zweier Snakes (Twin Snakes). Die Arbeit schließt mit einigen moeglichen Anwendungen von Snakes im Bereich der digitalen Photogrammetrie und der Topographie. Neben der Kanten- und Linienextraktion im dreidimensionalen Raum wird der Einsatz von Snakes für die Schnittliniensuche bei der Orthophotomosaikierung sowie für die Detektion von Kanten in Gelaendemodellen vorgeschlagen.

Snakes are well known in computer vision as an automated (semiautomatic) tool for extracting edges and lines in digital images. Starting from a rough approximation of the desired curve regarding both its shape and its location in the image, the snake improves its state by optimizing a complex energy functional. The aim is to reconstruct the desired curve in detail. The benefits of snakes lie in their robustness with respect to noise in the image and gaps in the image curve. However, numerous critical constellations were published, which impair their convergence behavior and their robustness. Having their weaknesses in mind we will evaluate whether snakes are suitable for applications in digital photogrammetry and topography. After the first publication of snakes many papers followed presenting improvements in order to overcome some weaknesses. As an emphasis of this thesis, a comprehensive comparison and evaluation of extended and improved snake models is given. Further, some components developed in the course of the thesis are presented which make the snake's energy function optimal for a specific application. The problems of snakes can be solved by three different approaches: Selecting an optimization algorithm: Five different optimization methods are presented. Beside the original solution using variational calculus, the solutions by means of dynamic programming, by least squares adjustment, by using a level set method as well as by using a simulated annealing method are considered. Adapting the energy function: The energy function consists of several terms for different purposes. Various published formulations of energy terms are analyzed. In particular, internal energy terms being responsible for a smooth shape of the snake are examined critically. Alternative formulations are suggested which prevent the snake from shrinking. Employing a special application strategy: Hierarchical strategies, strategies from coarse to fine, or optimizing the path between two points were already suggested in literature. In this thesis, further strategies are developed: partitioning the snake into segments as well as using two coupled snakes (twin snakes). The thesis closes with some possible applications of snakes in the context of digital photogrammetry and topography. Beside edge and line extraction in the three-dimensional space, we use snakes for detecting the optimal seam line in orthophoto mosaics as well as for extracting fold lines in terrain models.