English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Generalizations of the Multicut Problem for Computer Vision

Levinkov, E. (2019). Generalizations of the Multicut Problem for Computer Vision. PhD Thesis, Universität des Saarlandes, Saarbrücken. doi:10.22028/D291-27909.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/21.11116/0000-0003-9B27-3 Version Permalink: http://hdl.handle.net/21.11116/0000-0003-F506-2
Genre: Thesis

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Levinkov, Evgeny1, Author              
Andres, Bjoern2, Advisor              
Lempitsky, Victor3, Referee
Rother, Carsten3, Referee
Affiliations:
1International Max Planck Research School, MPI for Informatics, Max Planck Society, ou_1116551              
2Computer Vision and Machine Learning, MPI for Informatics, Max Planck Society, ou_1116547              
3External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 Abstract: Graph decomposition has always been a very important concept in machine learning and computer vision. Many tasks like image and mesh segmentation, community detection in social networks, as well as object tracking and human pose estimation can be formulated as a graph decomposition problem. The multicut problem in particular is a popular model to optimize for a decomposition of a given graph. Its main advantage is that no prior knowledge about the number of components or their sizes is required. However, it has several limitations, which we address in this thesis: Firstly, the multicut problem allows to specify only cost or reward for putting two direct neighbours into distinct components. This limits the expressibility of the cost function. We introduce special edges into the graph that allow to define cost or reward for putting any two vertices into distinct components, while preserving the original set of feasible solutions. We show that this considerably improves the quality of image and mesh segmentations. Second, multicut is notorious to be NP-hard for general graphs, that limits its applications to small super-pixel graphs. We define and implement two primal feasible heuristics to solve the problem. They do not provide any guarantees on the runtime or quality of solutions, but in practice show good convergence behaviour. We perform an extensive comparison on multiple graphs of different sizes and properties. Third, we extend the multicut framework by introducing node labels, so that we can jointly optimize for graph decomposition and nodes classification by means of exactly the same optimization algorithm, thus eliminating the need to hand-tune optimizers for a particular task. To prove its universality we applied it to diverse computer vision tasks, including human pose estimation, multiple object tracking, and instance-aware semantic segmentation. We show that we can improve the results over the prior art using exactly the same data as in the original works. Finally, we use employ multicuts in two applications: 1) a client-server tool for interactive video segmentation: After the pre-processing of the video a user draws strokes on several frames and a time-coherent segmentation of the entire video is performed on-the-fly. 2) we formulate a method for simultaneous segmentation and tracking of living cells in microscopy data. This task is challenging as cells split and our algorithm accounts for this, creating parental hierarchies. We also present results on multiple model fitting. We find models in data heavily corrupted by noise by finding components defining these models using higher order multicuts. We introduce an interesting extension that allows our optimization to pick better hyperparameters for each discovered model. In summary, this thesis extends the multicut problem in different directions, proposes algorithms for optimization, and applies it to novel data and settings.

Details

show
hide
Language(s): eng - English
 Dates: 2019-04-0820192019
 Publication Status: Published in print
 Pages: 151 p.
 Publishing info: Saarbrücken : Universität des Saarlandes
 Table of Contents: -
 Rev. Method: -
 Identifiers: BibTex Citekey: Levinkovphd2013
DOI: 10.22028/D291-27909
 Degree: PhD

Event

show

Legal Case

show

Project information

show

Source

show