Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Partial Enumeration and Curvature Regularization

Olsson, Carl LU ; Ulén, Johannes LU ; Boykov, Yuri and Kolmogorov, Vladimir (2013) IEEE International Conference on Computer Vision (ICCV), 2013 p.2936-2943
Abstract
Energies with high-order non-submodular interactions have been shown to be very useful in vision due to their high modeling power. Optimization of such energies, however, is generally NP-hard. A naive approach that works for small problem instances is exhaustive search, that is, enumera- tion of all possible labelings of the underlying graph. We propose a general minimization approach for large graphs based on enumeration of labelings of certain small patches. This partial enumeration technique reduces complex high- order energy formulations to pairwise Constraint Satisfac- tion Problems with unary costs (uCSP), which can be ef- ficiently solved using standard methods like TRW-S. Our approach outperforms a number of existing... (More)
Energies with high-order non-submodular interactions have been shown to be very useful in vision due to their high modeling power. Optimization of such energies, however, is generally NP-hard. A naive approach that works for small problem instances is exhaustive search, that is, enumera- tion of all possible labelings of the underlying graph. We propose a general minimization approach for large graphs based on enumeration of labelings of certain small patches. This partial enumeration technique reduces complex high- order energy formulations to pairwise Constraint Satisfac- tion Problems with unary costs (uCSP), which can be ef- ficiently solved using standard methods like TRW-S. Our approach outperforms a number of existing state-of-the-art algorithms on well known difficult problems (e.g. curvature regularization, stereo, deconvolution); it gives near global minimum and better speed. Our main application of interest is curvature regular- ization. In the context of segmentation, our partial enu- meration technique allows to evaluate curvature directly on small patches using a novel integral geometry approach. (Less)
Please use this url to cite or link to this publication:
author
; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Computer Vision (ICCV), 2013 IEEE International Conference on
pages
8 pages
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
conference name
IEEE International Conference on Computer Vision (ICCV), 2013
conference location
Sydney, Australia
conference dates
2013-12-01 - 2013-12-08
external identifiers
  • scopus:84898805535
  • wos:000351830500367
ISSN
1550-5499
DOI
10.1109/ICCV.2013.365
language
English
LU publication?
yes
id
dbaacf02-02a1-49a8-8497-5174f7279c5e (old id 4433646)
date added to LUP
2016-04-01 14:39:33
date last changed
2022-04-30 02:57:25
@inproceedings{dbaacf02-02a1-49a8-8497-5174f7279c5e,
  abstract     = {{Energies with high-order non-submodular interactions have been shown to be very useful in vision due to their high modeling power. Optimization of such energies, however, is generally NP-hard. A naive approach that works for small problem instances is exhaustive search, that is, enumera- tion of all possible labelings of the underlying graph. We propose a general minimization approach for large graphs based on enumeration of labelings of certain small patches. This partial enumeration technique reduces complex high- order energy formulations to pairwise Constraint Satisfac- tion Problems with unary costs (uCSP), which can be ef- ficiently solved using standard methods like TRW-S. Our approach outperforms a number of existing state-of-the-art algorithms on well known difficult problems (e.g. curvature regularization, stereo, deconvolution); it gives near global minimum and better speed. Our main application of interest is curvature regular- ization. In the context of segmentation, our partial enu- meration technique allows to evaluate curvature directly on small patches using a novel integral geometry approach.}},
  author       = {{Olsson, Carl and Ulén, Johannes and Boykov, Yuri and Kolmogorov, Vladimir}},
  booktitle    = {{Computer Vision (ICCV), 2013 IEEE International Conference on}},
  issn         = {{1550-5499}},
  language     = {{eng}},
  pages        = {{2936--2943}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  title        = {{Partial Enumeration and Curvature Regularization}},
  url          = {{https://lup.lub.lu.se/search/files/4093276/4433651.pdf}},
  doi          = {{10.1109/ICCV.2013.365}},
  year         = {{2013}},
}