GRAPH CUTS, SUM-OF-SUBMODULAR FLOW, AND LINEAR PROGRAMMING: EFFECTIVE INFERENCE IN HIGHER-ORDER MARKOV RANDOM FIELDS
| dc.contributor.author | Fix, Alexander Jobe | |
| dc.contributor.chair | Zabih, Ramin D | |
| dc.contributor.committeeMember | Shmoys, David B | |
| dc.contributor.committeeMember | Williamson, David P | |
| dc.date.accessioned | 2017-07-07T12:48:35Z | |
| dc.date.available | 2017-07-07T12:48:35Z | |
| dc.date.issued | 2017-05-30 | |
| 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. | |
| dc.identifier.doi | https://doi.org/10.7298/X40Z71DC | |
| dc.identifier.other | Fix_cornellgrad_0058F_10199 | |
| dc.identifier.other | http://dissertations.umi.com/cornellgrad:10199 | |
| dc.identifier.other | bibid: 9948815 | |
| dc.identifier.uri | https://hdl.handle.net/1813/51592 | |
| dc.language.iso | en_US | |
| dc.subject | Graphical Models | |
| dc.subject | Markov Random Fields | |
| dc.subject | Optimization | |
| dc.subject | Computer science | |
| dc.title | GRAPH CUTS, SUM-OF-SUBMODULAR FLOW, AND LINEAR PROGRAMMING: EFFECTIVE INFERENCE IN HIGHER-ORDER MARKOV RANDOM FIELDS | |
| dc.type | dissertation or thesis | |
| dcterms.license | https://hdl.handle.net/1813/59810 | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.grantor | Cornell University | |
| thesis.degree.level | Doctor of Philosophy | |
| thesis.degree.name | Ph. D., Computer Science |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Fix_cornellgrad_0058F_10199.pdf
- Size:
- 4.74 MB
- Format:
- Adobe Portable Document Format