---
OA_place: repository
OA_type: green
_id: '3170'
abstract:
- lang: eng
  text: Geodesic active contours and graph cuts are two standard image segmentation
    techniques. We introduce a new segmentation method combining some of their benefits.
    Our main intuition is that any cut on a graph embedded in some continuous space
    can be interpreted as a contour (in 2D) or a surface (in 3D). We show how to build
    a grid graph and set its edge weights so that the cost of cuts is arbitrarily
    close to the length (area) of the corresponding contours (surfaces) for any anisotropic
    Riemannian metric. There are two interesting consequences of this technical result.
    First, graph cut algorithms can be used to find globally minimum geodesic contours
    (minimal surfaces in 3D) under arbitrary Riemannian metric for a given set of
    boundary conditions. Second, we show how to minimize metrication artifacts in
    existing graph-cut based methods in vision. Theoretically speaking, our work provides
    an interesting link between several branches of mathematics -differential geometry,
    integral geometry, and combinatorial optimization. The main technical problem
    is solved using Cauchy-Crofton formula from integral geometry.
article_processing_charge: No
author:
- first_name: Yuri
  full_name: Boykov, Yuri
  last_name: Boykov
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
citation:
  ama: 'Boykov Y, Kolmogorov V. Computing geodesics and minimal surfaces via graph
    cuts. In: Vol 1. IEEE; 2008:26-33. doi:<a href="https://doi.org/10.1109/ICCV.2003.1238310">10.1109/ICCV.2003.1238310</a>'
  apa: 'Boykov, Y., &#38; Kolmogorov, V. (2008). Computing geodesics and minimal surfaces
    via graph cuts (Vol. 1, pp. 26–33). Presented at the ICCV: International Conference
    on Computer Vision, Nice, France: IEEE. <a href="https://doi.org/10.1109/ICCV.2003.1238310">https://doi.org/10.1109/ICCV.2003.1238310</a>'
  chicago: Boykov, Yuri, and Vladimir Kolmogorov. “Computing Geodesics and Minimal
    Surfaces via Graph Cuts,” 1:26–33. IEEE, 2008. <a href="https://doi.org/10.1109/ICCV.2003.1238310">https://doi.org/10.1109/ICCV.2003.1238310</a>.
  ieee: 'Y. Boykov and V. Kolmogorov, “Computing geodesics and minimal surfaces via
    graph cuts,” presented at the ICCV: International Conference on Computer Vision,
    Nice, France, 2008, vol. 1, pp. 26–33.'
  ista: 'Boykov Y, Kolmogorov V. 2008. Computing geodesics and minimal surfaces via
    graph cuts. ICCV: International Conference on Computer Vision vol. 1, 26–33.'
  mla: Boykov, Yuri, and Vladimir Kolmogorov. <i>Computing Geodesics and Minimal Surfaces
    via Graph Cuts</i>. Vol. 1, IEEE, 2008, pp. 26–33, doi:<a href="https://doi.org/10.1109/ICCV.2003.1238310">10.1109/ICCV.2003.1238310</a>.
  short: Y. Boykov, V. Kolmogorov, in:, IEEE, 2008, pp. 26–33.
conference:
  end_date: 2003-10-16
  location: Nice, France
  name: 'ICCV: International Conference on Computer Vision'
  start_date: 2003-10-13
date_created: 2018-12-11T12:01:48Z
date_published: 2008-04-03T00:00:00Z
date_updated: 2026-05-21T12:25:56Z
day: '03'
doi: 10.1109/ICCV.2003.1238310
extern: '1'
fulldoi: https://doi.org/10.1109/ICCV.2003.1238310
intvolume: '         1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.cs.cornell.edu/people/vnk/papers/BK-ICCV03.pdf
month: '04'
oa: 1
oa_version: Preprint
page: 26 - 33
publication_identifier:
  isbn:
  - '0769519504'
publication_status: published
publisher: IEEE
publist_id: '3511'
quality_controlled: '1'
status: public
title: Computing geodesics and minimal surfaces via graph cuts
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 1
year: '2008'
...
---
OA_place: repository
OA_type: green
_id: '3174'
abstract:
- lang: eng
  text: We address visual correspondence problems without assuming that scene points
    have similar intensities in different views. This situation is common, usually
    due to non-lambertian scenes or to differences between cameras. We use maximization
    of mutual information, a powerful technique for registering images that requires
    no a priori model of the relationship between scene intensities in different views.
    However, it has proven difficult to use mutual information to compute dense visual
    correspondence. Comparing fixed-size windows via mutual information suffers from
    the well-known problems of fixed windows, namely poor performance at discontinuities
    and in low-texture regions. In this paper, we show how to compute visual correspondence
    using mutual information without suffering from these problems. Using 'a simple
    approximation, mutual information can be incorporated into the standard energy
    minimization framework used in early vision. The energy can then be efficiently
    minimized using graph cuts, which preserve discontinuities and handle low-texture
    regions. The resulting algorithm combines the accurate disparity maps that come
    from graph cuts with the tolerance for intensity changes that comes from mutual
    information.
article_processing_charge: No
author:
- first_name: Junhwan
  full_name: Kim, Junhwan
  last_name: Kim
- 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: 'Kim J, Kolmogorov V, Zabih R. Visual correspondence using energy minimization
    and mutual information. In: <i>Proceedings Ninth International Conference on Computer
    Vision</i>. Vol 2. IEEE; 2008:1033-1040. doi:<a href="https://doi.org/10.1109/ICCV.2003.1238463">10.1109/ICCV.2003.1238463</a>'
  apa: 'Kim, J., Kolmogorov, V., &#38; Zabih, R. (2008). Visual correspondence using
    energy minimization and mutual information. In <i>Proceedings Ninth International
    Conference on Computer Vision</i> (Vol. 2, pp. 1033–1040). Nice, France: IEEE.
    <a href="https://doi.org/10.1109/ICCV.2003.1238463">https://doi.org/10.1109/ICCV.2003.1238463</a>'
  chicago: Kim, Junhwan, Vladimir Kolmogorov, and Ramin Zabih. “Visual Correspondence
    Using Energy Minimization and Mutual Information.” In <i>Proceedings Ninth International
    Conference on Computer Vision</i>, 2:1033–40. IEEE, 2008. <a href="https://doi.org/10.1109/ICCV.2003.1238463">https://doi.org/10.1109/ICCV.2003.1238463</a>.
  ieee: J. Kim, V. Kolmogorov, and R. Zabih, “Visual correspondence using energy minimization
    and mutual information,” in <i>Proceedings Ninth International Conference on Computer
    Vision</i>, Nice, France, 2008, vol. 2, pp. 1033–1040.
  ista: 'Kim J, Kolmogorov V, Zabih R. 2008. Visual correspondence using energy minimization
    and mutual information. Proceedings Ninth International Conference on Computer
    Vision. ICCV: International Conference on Computer Vision vol. 2, 1033–1040.'
  mla: Kim, Junhwan, et al. “Visual Correspondence Using Energy Minimization and Mutual
    Information.” <i>Proceedings Ninth International Conference on Computer Vision</i>,
    vol. 2, IEEE, 2008, pp. 1033–40, doi:<a href="https://doi.org/10.1109/ICCV.2003.1238463">10.1109/ICCV.2003.1238463</a>.
  short: J. Kim, V. Kolmogorov, R. Zabih, in:, Proceedings Ninth International Conference
    on Computer Vision, IEEE, 2008, pp. 1033–1040.
conference:
  end_date: 2003-10-16
  location: Nice, France
  name: 'ICCV: International Conference on Computer Vision'
  start_date: 2003-10-13
date_created: 2018-12-11T12:01:49Z
date_published: 2008-04-03T00:00:00Z
date_updated: 2026-05-21T12:22:19Z
day: '03'
doi: 10.1109/ICCV.2003.1238463
extern: '1'
fulldoi: https://doi.org/10.1109/ICCV.2003.1238463
intvolume: '         2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.cs.cornell.edu/people/vnk/papers/KKZ-ICCV03.pdf
month: '04'
oa: 1
oa_version: Preprint
page: 1033 - 1040
publication: Proceedings Ninth International Conference on Computer Vision
publication_identifier:
  isbn:
  - '0769519504'
publication_status: published
publisher: IEEE
publist_id: '3510'
quality_controlled: '1'
status: public
title: Visual correspondence using energy minimization and mutual information
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 2
year: '2008'
...