Back to search

Cornell University

GRAPH CUTS, SUM-OF-SUBMODULAR FLOW, AND LINEAR PROGRAMMING: EFFECTIVE INFERENCE IN HIGHER-ORDER MARKOV RANDOM FIELDS

Abstract

dc:description.abstract

Optimization algorithms have a long history of success in computer vision, providing effective algorithms for tasks as varied as segmentation, stereo estimation, image denoising and scene understanding. A notable example of this is Graph Cuts, in which the minimum-cut problem is used to solve a class of vision problems known as first-order Markov Random Fields. Despite this success, first-order MRFs have their limitations. They cannot encode correlations between groups of pixels larger than two or easily express higher-order statistics of images. In this thesis, we generalize graph cuts to higher-order MRFs, while still maintaining the properties that make graph cuts successful. In particular, we will examine three different mathematical techniques which have combined to make previously intractable higher-order inference problems become practical within the last few years. First, order-reducing reductions, which transform higher-order problems into familiar first-order MRFs. Second, a generalization of the min-cut problem to hypergraphs, called Sum-of-Submodular optimization. And finally linear programming relaxations based on the Local Marginal Polytope, which together with Sum-of-Submodular flow results in the highly effective primal-dual algorithm SoSPD. This thesis presents all mathematical background for these algorithms, as well as an implementation and experimental comparison with state-of-the-art.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Computer Science
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Fix, Alexander Jobe
Chair dc:contributor.chair
  • Zabih, Ramin D
Committee members dc:contributor.committeemember
  • Shmoys, David B
  • Williamson, David P

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
9948815
Dc Identifier Other
ProQuest Submission ID: 10199
ProQuest Publication ID: 10256102

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Fix, Alexander Jobe. GRAPH CUTS, SUM-OF-SUBMODULAR FLOW, AND LINEAR PROGRAMMING: EFFECTIVE INFERENCE IN HIGHER-ORDER MARKOV RANDOM FIELDS. Doctor of Philosophy thesis, Cornell University, 2017. https://hdl.handle.net/1813/51592