Image Partitioning based on Semidefinite Programming


Keuchel, Jens


[img]
Preview
PDF
keuchel_diss.pdf - Published

Download (9MB)

URL: http://ub-madoc.bib.uni-mannheim.de/759
URN: urn:nbn:de:bsz:180-madoc-7594
Document Type: Doctoral dissertation
Year of publication: 2004
Publishing house: Universität Mannheim
Evaluator: Schnörr, Christoph
Date of oral examination: 13 September 2004
Publication language: English
Institution: School of Business Informatics and Mathematics > Bildverarbeitung, Mustererkennung u. Computergrafik (Schnörr)
Subject: 004 Computer science, internet
Classification: CCS: I.5.3 I.4.6 G.1.6 ,
Subject headings (SWD): Bildverarbeitung , Bildsegmentierung , Partitionierung , Semidefinite Optimierung , Kombinatorische Optimierung , Relaxationsmethode
Keywords (English): Computer Vision , Image Partitioning , Segmentation , Semidefinite Programming , Convex Relaxation
Abstract: Many tasks in computer vision lead to combinatorial optimization problems. Automatic image partitioning is one of the most important examples in this context: whether based on some prior knowledge or completely unsupervised, we wish to find coherent parts of the image. However, the inherent combinatorial complexity of such problems often prevents to find the global optimum in polynomial time. For this reason, various approaches have been proposed to find good approximative solutions for image partitioning problems. As an important example, we will first consider different spectral relaxation techniques: based on straightforward eigenvector calculations, these methods compute suboptimal solutions in short time. However, the main contribution of this thesis is to introduce a novel optimization technique for discrete image partitioning problems which is based on a semidefinite programming relaxation. In contrast to approximation methods employing annealing algorithms, this approach involves solving a convex optimization problem, which does not suffer from possible local minima. Using interior point techniques, the solution of the relaxation can be found in polynomial time, and without elaborate parameter tuning. High quality solutions to the original combinatorial problem are then obtained with a randomized rounding technique. The only potential drawback of the semidefinite relaxation approach is that the number of variables of the optimization problem is squared. Nevertheless, it can still be applied to problems with up to a few thousand variables, as is demonstrated for various computer vision tasks including unsupervised segmentation, perceptual grouping and image restoration. Concerning problems of higher dimensionality, we study two different approaches to effectively reduce the number of variables. The first one is based on probabilistic sampling: by considering only a small random fraction of the pixels in the image, our semidefinite relaxation method can be applied in an efficient way while maintaining a reliable quality of the resulting segmentations. The second approach reduces the problem size by computing an over-segmentation of the image in a preprocessing step. After that, the image is partitioned based on the resulting "superpixels" instead of the original pixels. Since the real world does not consist of pixels, it can even be argued that this is the more natural image representation. Initially, our semidefinite relaxation method is defined only for binary partitioning problems. To derive image segmentations into multiple parts, one possibility is to apply the binary approach in a hierarchical way. Besides this natural extension, we also discuss how multiclass partitioning problems can be solved in a direct way based on semidefinite relaxation techniques.
Translation of the title: Bildpartitionierung mittels Semidefiniter Programmierung (German)
Translation of the abstract: Viele Bildverarbeitungsaufgaben lassen sich auf kombinatorische Optimierungsprobleme zurückführen. Eines der wichtigsten Beispiele in diesem Kontext ist die automatische Zerlegung von Bildern in kohärente Bestandteile, sei es unter Zuhilfenahme von Vorwissen oder völlig unüberwacht. Allerdings erlaubt es die hohe Komplexität derartiger Probleme häufig nicht, optimale Lösungen in polynomieller Zeit zu berechnen. Aus diesem Grund wurden verschiedenartige Verfahren entwickelt, um gute Näherungslösungen für Bildpartitionierungsprobleme zu bestimmen. Als wichtiges Beispiel vergleichen wir zunächst mehrere spektrale Relaxations-Methoden, welche solche Approximationen mit Hilfe von speziellen Eigenvektor-Berechnungen ermitteln. Der wesentliche Beitrag dieser Arbeit besteht jedoch darin, ein neuartiges Optimierungsverfahren zur diskreten Bildpartitionierung vorzustellen. Wir verwenden dazu einen Relaxationsansatz, der letztlich ein spezielles konvexes Optimierungsproblem liefert, welches mittels semidefiniter Programmierung gelöst werden kann. Im Gegensatz zu anderen Näherungsverfahren, die beispielsweise auf Annealing-Algorithmen beruhen, besteht somit keine Gefahr, in einem lokalen Minimum zu landen. Außerdem kann die Lösung eines semidefiniten Programms ohne aufwändige Parameteroptimierung mit Interior-Point-Methoden in polynomieller Zeit bestimmt werden. Qualitativ hochwerige diskrete Lösungen des Originalproblems lassen sich anschließend mit Hilfe einer probabilistischen Rundungstechnik ermitteln. Der einzige potenzielle Nachteil der semidefiniten Relaxation besteht darin, dass eine Quadrierung der Variablenanzahl notwendig ist. Nichtsdestotrotz lassen sich Probleme mit bis zu einigen tausend Variablen zufriedenstellend bearbeiten, wie wir anhand unterschiedlicher Bildverarbeitungsaufgaben aus der unüberwachten Segmentierung, perzeptuellen Gruppierung oder Bildrekonstruktion demonstrieren werden. Für Problemstellungen höherer Dimension untersuchen wir zwei verschiedene Verfahren, welche die Variablenanzahl effektiv reduzieren. Zum einen handelt es sich dabei um einen Ansatz, der auf probabilistischem Sampling beruht: Durch zufällige Auswahl eines kleinen Prozentsatzes der Bildpixel erhalten wir ein Optimierungsproblem, auf das unser semidefinites Relaxationsverfahren effizient angewandt werden kann, und zwar unter Beibehaltung einer zufriedenstellenden Qualität der endgültigen Segmentierung. Das zweite Verfahren reduziert die Problemgröße, indem zunächst in einem Vorverarbeitungsschritt eine Übersegmentierung des Bildes berechnet wird. Anschließend werden anstelle der Pixel die resultierenden "Superpixel" als Grundlage zur Zerlegung des Bildes verwendet. Da die reale Welt nicht aus Pixeln besteht, erscheint dies sogar die natürlichere Bild-Repräsentation zu sein. Unser semidefinites Relaxationsverfahren ist ursprünglich nur für binäre Problemstellungen definiert. Eine naheliegende Möglichkeit, um mehrteilige Zerlegungen zu erhalten, besteht in der hierarchischen Anwendung der binären Methode. Neben dieser Erweiterung untersuchen wir zudem, inwiefern Bildsegmentierungen in mehrere Teile auf direkte Weise mittels semidefiniter Relaxation bestimmt werden können. (German)
Additional information:

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




+ Citation Example and Export

Keuchel, Jens (2004) Image Partitioning based on Semidefinite Programming. Open Access [Doctoral dissertation]
[img]
Preview


+ Search Authors in

BASE: Keuchel, Jens

Google Scholar: Keuchel, Jens

+ Download Statistics

Downloads per month over past year

View more statistics



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item