Von Pixeln zu Regionen: Partielle Differentialgleichungen in der Bildanalyse

This work deals with applications of partial differential equations in image analysis. The focus is thereby on applications that can be used for image segmentation. This includes, among other topics, nonlinear diffusion, motion analysis, and image segmentation itself. From each chapter to the next, the methods are directed more and more to image segmentation. While Chapter 2 presents general denoising and simplification techniques, Chapter 4 already addresses the somewhat more special task to extract texture and motion from images. This is in order to employ the resulting features to the partitioning of images finally in Chapter 5. Thus, in this work, one can clearly make out the thread from the raw image data, the pixels, to the more abstract descriptions of images by means of regions. The fact that image processing techniques can also be useful in research areas besides conventional images is shown in Chapter 3. They are used here in order to improve numerical methods for conservation laws in physics. The work conceptually focuses on using as many different features as possible for segmentation. This includes besides image-driven features like texture and motion the knowledge-based information of a three-dimensional object model. The basic idea of this concept is to provide a preferably wide basis of information for separating object regions and thus increasing the number of situations in which the method yields satisfactory segmentation results. A further basic concept pursued in this thesis is to employ coarse-to-fine strategies. They are used both for motion estimation in Chapter 4 and for segmentation in Chapter 5. In both cases one has to deal with optimization problems that contain many local optima. Conventional local optimization therefore usually leads to results the quality of which heavily depends on the initialization. This situation can often be eased, if the optimization problem is first significantly simplified. One then tries to solve the original problem by continuously increasing the problem complexity. Apart from this, the work contains several essential technical novelties. In Chapter 2, nonlinear diffusion with unbounded diffusivities is considered. This also includes total variation flow(TV flow). A thorough analysis of TV flow thereby leads to an analytic solution that allows to show that TV flow is in the space-discrete, one-dimensional setting exactly identical to the corresponding variational approach called TV regularization. Moreover, various different numerical methods are investigated in order to determine their suitability for diffusion filters with unbounded diffusivities. TV flow can be regarded as an alternative to Gaussian smoothing, though there is the significant difference of TV flow being discontinuity preserving. By replacing Gaussian smoothing by TV flow, one can develop new discontinuity preserving versions of well-known operators such as the structure tensor. TV flow is also employed in Chapter 3 where the goal is to improve numerical schemes for the approximation of hyperbolic conservation laws by means of image processing techniques. The role of TV flow in this scope is to remove oscillations of a second order method. In an alternative approach, the approximation performance of a first order method is improved by a nonlinear inverse diffusion filter. The underlying concept is to remove exactly the amount of numerical diffusion that actually stabilizes the scheme. By means of an appropriate stabilization of the inverse diffusion process it is possible to preserve the positive stability properties of the original method. III IV Abstract Chapter 4 is separated into two parts. The first part deals with the extraction of texture features, whereas the second part focuses on motion estimation. Goal of the texture extraction method is to derive a feature space that is as low-dimensional as possible but still provides very good discrimination properties. The basic framework of this feature space is the structure tensor based on TV flow presented earlier in Chapter 2. It contains the orientation, magnitude, and homogeneity of a texture and therefore provides already very important features for texture discrimination. Additionally, a region based local scale measure is developed that supplements the size of texture elements to the feature space. This feature space is used later in Chapter 5 for texture segmentation. Two motion estimation methods are introduced in Chapter 4. One of them is based on the structure tensor from Section 2 and improves existing local methods. The other technique is based on a global variational approach. It differs from usual variational approaches by the use of a gradient constancy assumption. This assumption provides the method with the capability to yield good estimation results even in the presence of small local or global variations of illumination. Besides this novelty, the combination of non-linearized constancy assumptions and a coarse-to-fine strategy yields a numerical scheme that provides for the first time a well founded theory for the very successful warping methods. The described technique leads to results that are generally more accurate than all results presented in literature so far. As already mentioned, goal of the image segmentation approach in Chapter 5 is mainly to integrate the features derived in Chapter 4 and to utilize a coarse-to-fine strategy. This is done in the framework of region based, implicit active contour models which are set up on the concept of level sets. The involved region models are extended by nonparametric as well as local region statistics. A further novelty is the extension of the level set concept to multiple regions. The optimum number of regions is thereby estimated by a hierarchical approach. This is a considerable extension of conventional active contour models, which are usually restricted to two regions. Moreover, the idea to use three-dimensional object knowledge for segmentation is presented. The proposed method uses the extracted contour for estimating the pose of the object, while in return the projected object model supports the segmentation. The implementation of this idea as described in this thesis is only at an early stage. Plenty of interesting aspects can be derived from this concept that are to be investigated in the future.Die vorliegenden Arbeit beschäftigt sich mit Anwendungen partieller Differentialgleichungen in der Bildanalyse. Dabei stehen Anwendungen im Vordergrund, die sich zur Bildsegmentierung verwenden lassen. Dies schließt unter anderem nichtlineare Diffusion, Bewegungsschätzung und die Bildsegmentierung selbst ein. Von Kapitel zu Kapitel werden die verwendeten Methoden dabei mehr und mehr auf die Bildsegmentierung ausgerichtet. Werden in Kapitel 2 noch allgemeine Entrauschungs- und Bildvereinfachungsoperationen vorgestellt, behandelt Kapitel 4 die schon etwas speziellere Aufgabe, Textur und Bewegung aus Bildern zu extrahieren, um entsprechende Merkmale schließlich in Kapitel 5 zur Segmentierung von Bildern verwenden zu können. Dabei zieht sich der Weg von den rohen Bilddaten, den Pixeln, hin zur abstrakteren Beschreibung von Bildern mit Hilfe von Regionen als roter Faden durch die gesamte Arbeit. Dass sich Bildverarbeitungstechniken auch in Forschungsgebieten fern herkömmlicher Bilder als nützlich erweisen können, zeigt Kapitel 3. Hier werden Bildverarbeitungstechniken zur Verbesserung numerischer Verfahren für Erhaltungsgleichungen der Physik verwendet. Konzeptionell legt diese Arbeit Wert darauf, möglichst viele verschiedene Merkmale zur Segmentierung zu verwenden. Darunter fallen neben den bildgestützten Merkmalen wie Textur und Bewegung auch die wissensbasierte Information eines dreidimensionalen Oberflächenmodells. Die prinzipielle Idee hinter diesem Konzept ist, die Entscheidungsgrundlage zur Trennung von Objektregionen auf eine möglichst breite Informationsbasis zu stellen und somit die Anzahl der Situationen, in denen das Verfahren zufriedenstellende Segmentierungsergebnisse liefert, zu erhöhen. Ein weiteres Grundkonzept, das in dieser Arbeit verfolgt wird, ist die Verwendung von Coarse- To-Fine-Strategien. Sie kommen sowohl bei der Bewegungsschätzung in Kapitel 4 als auch in der Segmentierung in Kapitel 5 zum Einsatz. In beiden Fällen hat man es mit Optimierungsproblemen zu tun, die viele lokale Optima aufweisen. Herkömmliche lokale Optimierung führt daher meist zu Ergebnissen, deren Qualität stark von der Initialisierung abhängt. Diese Situation lässt sich häufig entschärfen, wenn man das entsprechende Optimierungsproblem zunächst deutlich vereinfacht und erst nach und nach das ursprüngliche Problem zu lösen versucht. Daneben enthält diese Arbeit viele wesentliche technische Neuerungen. In Kapitel 2 wird nichtlineare Diffusion mit unbeschränkten Diffusivitäten betrachtet, was auch Total-Variation- Flow (TV-Flow) mit einschließt. Eine genaue Analyse von TV-Flow führt dabei zu einer analytischen Lösung, mit Hilfe derer man zeigen kann, dass TV-Flow im diskreten, eindimensionalen Fall exakt identisch mit dem ensprechenden Variationsansatz der TV-Regularisierung ist. Desweiteren werden verschiedene numerische Verfahren in Bezug auf ihre Eignung für Diffusionsfilter mit unbeschränkten Diffusivitäten untersucht. Man kann TV-Flow als eine Alternative zur Gaußglättung ansehen, mit dem entscheidenden Unterschied, dass TV-Flow kantenerhaltend ist. Durch Ersetzen von Gaußglättung durch TV-Flow lassen sich so diskontinuitätserhaltende Varianten bekannter Operatoren wie etwa des Strukturtensors entwickeln. Auch in Kapitel 3 kommt TV-Flow zum Einsatz, wenn es darum geht, numerische Verfahren zur Approximation hyperbolischer Erhaltungsgleichungen durch Bildverarbeitungsmethoden zu verbessern. TV-Flow fällt dabei die Rolle zu, Oszillationen eines Verfahrens zweiter Ordnung zu beseitigen. In einem alternativen Ansatz werden die Approximationseigenschaften eines Verfahrens erster Ordnung durch einen nichtlinearen Rückwärtsdiffusionsfilter verbessert, indem die numerische Diffusion, die das Verfahren eigentlich stabilisiert, gezielt wieder entfernt wird. Dabei gelingt es durch eine geeignete Stabilisierung der Rückwärtsdiffusion, die positiven Stabilitätseigenschaften des Originalverfahrens zu erhalten. Kapitel 4 spaltet sich in zwei Teile auf, wobei der erste Teil von der Extrahierung von Texturmerkmalen handelt, während sich der zweite Teil auf Bewegungsschätzung konzentriert. Bei den Texturmerkmalen besteht dabei das Ziel, einen möglichst niederdimensionalen Merkmalsraum zu kreieren, der dennoch sehr gute Diskriminierungseigenschaften besitzt. Das Grundgerüst dieses Merkmalsraums stellt dabei der in Kapitel 2 vorgestellte, auf TV-Flow basierende Strukturtensor dar. Er beschreibt mit der Orientierung, Stärke und Homogenität der Texturierung bereits sehr wichtige Merkmale einer Textur. Daneben wird ein regionenbasiertes, lokales Skalenmaß entwickelt, das zusätzlich die Größe von Texturelementen als Merkmal einbringt. Diese Texturmerkmale werden später in Kapitel 5 zur Textursegmentierung verwendet. Zur Bewegungsschätzung werden zwei Verfahren vorgestellt. Das eine basiert auf dem in Kapitel 2 eingeführten Strukturtensor und stellt eine Verbesserung vorhandener lokaler Methoden dar. Das andere Verfahren basiert auf einem globalen Variationsansatz und unterscheidet sich von üblichen Variationsansätzen durch die Verwendung einer Gradientenkonstanzannahme. Diese stattet das Verfahren mit der Fähigkeit aus, auch beim Vorhandensein kleinerer lokaler oder globaler Helligkeitsschwankungen gute Schätzergebnisse zu liefern. Daneben ergibt sich aus der Kombination von nicht-linearisierten Konstanzannahmen und einer Coarse-To-Fine-Strategie ein numerisches Schema, das erstmals eine fundierte Theorie zu den sehr erfolgreichen Warping-Verfahren zur Verfügung stellt. Mit der beschriebenen Technik werden Ergebnisse erzielt, die grundsätzlich präziser sind als alles was bisher in der Literatur vorgestellt wurde. Bei der eigentlichen Bildsegmentierung in Kapitel 5 geht es schließlich, wie bereits erwähnt, hauptsächlich um die Einbringung der in Kapitel 4 entwickelten zusätzlichen Merkmale und um die Verwendung einer Coarse-To-Fine-Strategie. Dies geschieht im Rahmen von regionenbasierten, impliziten Aktiv-Kontur-Modellen, die auf dem Konzept der Level-Sets aufbauen. Dabei werden die Regionenmodelle um nichtparametrische und lokale Beschreibungen der Regionenstatistik erweitert. Eine weitere Neuerung ist die Erweiterung des Level-Set-Konzepts auf mehrere Regionen. In einem teils hierarchischen Ansatz wird dabei auch die optimale Anzahl der Regionen geschätzt, was eine erhebliche Erweiterung im Vergleich zu herkömmlichen Aktiv-Kontur- Modellen darstellt. Außerdem wird die Idee vorgestellt, dreidimensionales Objektwissen in der Segmentierung zu verwenden, indem anhand der Segmentierung die Lage des Objekts geschätzt wird und umgekehrt wiederum das projizierte Objektmodell die Segmentierung unterstützt. Die Umsetzung dieser Idee, wie sie in dieser Arbeit beschrieben wird, steht dabei erst am Anfang. Für die Zukunft ergeben sich hieraus noch viele interessanter Aspekte, die es zu untersuchen gilt