---
_id: '2927'
abstract:
- lang: eng
  text: 'In the last few years, several new algorithms based on graph cuts have been
    developed to solve energy minimization problems in computer vision. Each of these
    techniques constructs a graph such that the minimum cut on the graph also minimizes
    the energy. Yet because these graph constructions are complex and highly specific
    to a particular energy function, graph cuts have seen limited application to date.
    In this paper we characterize the energy functions that can be minimized by graph
    cuts. Our results are restricted to energy functions with binary variables. However,
    our work generalizes many previous constructions, and is easily applicable to
    vision problems that involve large numbers of labels, such as stereo, motion,
    image restoration and scene reconstruction. We present three main results: a necessary
    condition for any energy function that can be minimized by graph cuts; a sufficient
    condition for energy functions that can be written as a sum of functions of up
    to three variables at a time; and a general-purpose construction to minimize such
    an energy function. Researchers who are considering the use of graph cuts to optimize
    a particular energy function can use our results to determine if this is possible,
    and then follow our construction to create the appropriate graph.'
acknowledgement: We thank Olga Veksler and Yuri Boykov for their careful reading of
  this paper, and for valuable comments which greatly improved itsreadibility. We
  also thank Ian Jermyn for helping us clarify the paper’s motivation. This research
  was supported by NSF grants IIS-9900115 and CCR-0113371, and by a grant from Microsoft
  Research.
article_processing_charge: No
author:
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
- first_name: Ramin
  full_name: Zabih, Ramin
  last_name: Zabih
citation:
  ama: 'Kolmogorov V, Zabih R. Multi-camera scene reconstruction via graph cuts. In:
    <i>Proceedings of the 7th European Conference on Computer Vision</i>. Springer;
    2002:65-81. doi:<a href="https://doi.org/10.1007/3-540-47977-5_5">10.1007/3-540-47977-5_5</a>'
  apa: 'Kolmogorov, V., &#38; Zabih, R. (2002). Multi-camera scene reconstruction
    via graph cuts. In <i>Proceedings of the 7th European Conference on Computer Vision</i>
    (pp. 65–81). Copenhagen, Denmark: Springer. <a href="https://doi.org/10.1007/3-540-47977-5_5">https://doi.org/10.1007/3-540-47977-5_5</a>'
  chicago: Kolmogorov, Vladimir, and Ramin Zabih. “Multi-Camera Scene Reconstruction
    via Graph Cuts.” In <i>Proceedings of the 7th European Conference on Computer
    Vision</i>, 65–81. Springer, 2002. <a href="https://doi.org/10.1007/3-540-47977-5_5">https://doi.org/10.1007/3-540-47977-5_5</a>.
  ieee: V. Kolmogorov and R. Zabih, “Multi-camera scene reconstruction via graph cuts,”
    in <i>Proceedings of the 7th European Conference on Computer Vision</i>, Copenhagen,
    Denmark, 2002, pp. 65–81.
  ista: 'Kolmogorov V, Zabih R. 2002. Multi-camera scene reconstruction via graph
    cuts. Proceedings of the 7th European Conference on Computer Vision. ECCV: European
    Conference on Computer Vision, 65–81.'
  mla: Kolmogorov, Vladimir, and Ramin Zabih. “Multi-Camera Scene Reconstruction via
    Graph Cuts.” <i>Proceedings of the 7th European Conference on Computer Vision</i>,
    Springer, 2002, pp. 65–81, doi:<a href="https://doi.org/10.1007/3-540-47977-5_5">10.1007/3-540-47977-5_5</a>.
  short: V. Kolmogorov, R. Zabih, in:, Proceedings of the 7th European Conference
    on Computer Vision, Springer, 2002, pp. 65–81.
conference:
  end_date: 2002-05-31
  location: Copenhagen, Denmark
  name: 'ECCV: European Conference on Computer Vision'
  start_date: 2002-05-28
date_created: 2018-12-11T12:00:23Z
date_published: 2002-01-01T00:00:00Z
date_updated: 2023-07-18T08:20:02Z
day: '01'
doi: 10.1007/3-540-47977-5_5
extern: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 65 - 81
publication: Proceedings of the 7th European Conference on Computer Vision
publication_identifier:
  isbn:
  - '9783540437468'
publication_status: published
publisher: Springer
publist_id: '3810'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Multi-camera scene reconstruction via graph cuts
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '2002'
...