|
Image Partitioning based on Semidefinite Programming
Keuchel, Jens
![[img]](https://madoc.bib.uni-mannheim.de/style/images/fileicons/application_pdf.png)  Vorschau |
|
PDF
keuchel_diss.pdf
- Veröffentlichte Version
Download (9MB)
|
|
URL:
|
http://ub-madoc.bib.uni-mannheim.de/759
|
|
URN:
|
urn:nbn:de:bsz:180-madoc-7594
|
|
Dokumenttyp:
|
Dissertation
|
|
Erscheinungsjahr:
|
2004
|
|
Titel einer Zeitschrift oder einer Reihe:
|
None
|
|
Verlag:
|
Universität Mannheim
|
|
Gutachter:
|
Schnörr, Christoph
|
|
Datum der mündl. Prüfung:
|
13 September 2004
|
|
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:
|
CCS:
I.5.3 I.4.6 G.1.6 ,
|
|
Normierte Schlagwörter (SWD):
|
Bildverarbeitung , Bildsegmentierung , Partitionierung , Semidefinite Optimierung , Kombinatorische Optimierung , Relaxationsmethode
|
|
Freie Schlagwörter (Englisch):
|
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.
|
|
Übersetzter Titel:
|
Bildpartitionierung mittels Semidefiniter Programmierung
(Deutsch)
|
|
Übersetzung des Abstracts:
|
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.
(Deutsch)
|
|
Zusätzliche Informationen:
|
|
 | Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt. |
 Suche Autoren in
Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail
Actions (login required)
 |
Eintrag anzeigen |
|
