---
OA_type: closed access
_id: '3183'
abstract:
- lang: eng
  text: This paper describes two algorithms capable of real-time segmentation of foreground
    from background layers in stereo video sequences. Automatic separation of layers
    from colour/contrast or from stereo alone is known to be error-prone. Here, colour,
    contrast and stereo matching information are fused to infer layers accurately
    and efficiently. The first algorithm, Layered Dynamic Programming (LDP), solves
    stereo in an extended 6-state space that represents both foreground/background
    layers and occluded regions. The stereo-match likelihood is then fused with a
    contrast-sensitive colour model that is learned on the fly, and stereo disparities
    are obtained by dynamic programming. The second algorithm, Layered Graph Cut (LGC),
    does not directly solve stereo. Instead the stereo match likelihood is marginalised
    over foreground and background hypotheses, and fused with a contrast-sensitive
    colour model like the one used in LDP. Segmentation is solved efficiently by ternary
    graph cut. Both algorithms are evaluated with respect to ground truth data and
    found to have similar perfomance, substantially better than stereo or colour/contrast
    alone. However, their characteristics with respect to computational efficiency
    are rather different. The algorithms are demonstrated in the application of background
    substitution and shown to give good quality composite video output.
article_processing_charge: No
author:
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
- first_name: Antonio
  full_name: Criminisi, Antonio
  last_name: Criminisi
- first_name: Andrew
  full_name: Blake, Andrew
  last_name: Blake
- first_name: Geoffrey
  full_name: Cross, Geoffrey
  last_name: Cross
- first_name: Carsten
  full_name: Rother, Carsten
  last_name: Rother
citation:
  ama: 'Kolmogorov V, Criminisi A, Blake A, Cross G, Rother C. Bi-layer segmentation
    of binocular stereo video. In: <i>Proceedings of the 2005 IEEE Computer Society
    Conference on Computer Vision and Pattern Recognition Volume 2 </i>. Vol 2. IEEE;
    2005:407-414. doi:<a href="https://doi.org/10.1109/CVPR.2005.91">10.1109/CVPR.2005.91</a>'
  apa: 'Kolmogorov, V., Criminisi, A., Blake, A., Cross, G., &#38; Rother, C. (2005).
    Bi-layer segmentation of binocular stereo video. In <i>Proceedings of the 2005
    IEEE Computer Society Conference on Computer Vision and Pattern Recognition Volume
    2 </i> (Vol. 2, pp. 407–414). San Diego, CA, United States: IEEE. <a href="https://doi.org/10.1109/CVPR.2005.91">https://doi.org/10.1109/CVPR.2005.91</a>'
  chicago: Kolmogorov, Vladimir, Antonio Criminisi, Andrew Blake, Geoffrey Cross,
    and Carsten Rother. “Bi-Layer Segmentation of Binocular Stereo Video.” In <i>Proceedings
    of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition
    Volume 2 </i>, 2:407–14. IEEE, 2005. <a href="https://doi.org/10.1109/CVPR.2005.91">https://doi.org/10.1109/CVPR.2005.91</a>.
  ieee: V. Kolmogorov, A. Criminisi, A. Blake, G. Cross, and C. Rother, “Bi-layer
    segmentation of binocular stereo video,” in <i>Proceedings of the 2005 IEEE Computer
    Society Conference on Computer Vision and Pattern Recognition Volume 2 </i>, San
    Diego, CA, United States, 2005, vol. 2, pp. 407–414.
  ista: 'Kolmogorov V, Criminisi A, Blake A, Cross G, Rother C. 2005. Bi-layer segmentation
    of binocular stereo video. Proceedings of the 2005 IEEE Computer Society Conference
    on Computer Vision and Pattern Recognition Volume 2 . CVPR: Computer Vision and
    Pattern Recognition vol. 2, 407–414.'
  mla: Kolmogorov, Vladimir, et al. “Bi-Layer Segmentation of Binocular Stereo Video.”
    <i>Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision
    and Pattern Recognition Volume 2 </i>, vol. 2, IEEE, 2005, pp. 407–14, doi:<a
    href="https://doi.org/10.1109/CVPR.2005.91">10.1109/CVPR.2005.91</a>.
  short: V. Kolmogorov, A. Criminisi, A. Blake, G. Cross, C. Rother, in:, Proceedings
    of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition
    Volume 2 , IEEE, 2005, pp. 407–414.
conference:
  end_date: 2005-06-25
  location: San Diego, CA, United States
  name: 'CVPR: Computer Vision and Pattern Recognition'
  start_date: 2005-06-20
das_tickbox: '1'
date_created: 2018-12-11T12:01:52Z
date_published: 2005-07-25T00:00:00Z
date_updated: 2026-07-02T09:00:36Z
day: '25'
doi: 10.1109/CVPR.2005.91
extern: '1'
intvolume: '         2'
language:
- iso: eng
main_file_link:
- url: http://research.microsoft.com/pubs/67281/criminisi_cvpr2005.pdf
month: '07'
oa_version: None
page: 407 - 414
publication: 'Proceedings of the 2005 IEEE Computer Society Conference on Computer
  Vision and Pattern Recognition Volume 2 '
publication_identifier:
  isbn:
  - '0769523722'
  issn:
  - 1063-6919
publication_status: published
publisher: IEEE
publist_id: '3502'
status: public
title: Bi-layer segmentation of binocular stereo video
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 2
year: '2005'
...
---
OA_type: closed access
_id: '3175'
abstract:
- lang: eng
  text: This paper addresses the novel problem of automatically synthesizing an output
    image from a large collection of different input images. The synthesized image,
    called a digital tapestry, can be viewed as a visual summary or a virtual 'thumbnail'
    of all the images in the input collection. The problem of creating the tapestry
    is cast as a multi-class labeling problem such that each region in the tapestry
    is constructed from input image blocks that are salient and such that neighboring
    blocks satisfy spatial compatibility. This is formulated using a Markov Random
    Field and optimized via the graph cut based expansion move algorithm. The standard
    expansion move algorithm can only handle energies with metric terms, while our
    energy contains non-metric (soft and hard) constraints. Therefore we propose two
    novel contributions. First, we extend the expansion move algorithm for energy
    functions with non-metric hard constraints. Secondly, we modify it for functions
    with &quot;almost&quot; metric soft terms, and show that it gives good results
    in practice. The proposed framework was tested on several consumer photograph
    collections, and the results are presented.
article_processing_charge: No
author:
- first_name: Carsten
  full_name: Rother, Carsten
  last_name: Rother
- first_name: Sanjiv
  full_name: Kumar, Sanjiv
  last_name: Kumar
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
- first_name: Andrew
  full_name: Blake, Andrew
  last_name: Blake
citation:
  ama: 'Rother C, Kumar S, Kolmogorov V, Blake A. Digital tapestry. In: <i>Proceedings
    of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition
    Volume 1</i>. Vol 1. IEEE; 2005:589-596. doi:<a href="https://doi.org/10.1109/CVPR.2005.130">10.1109/CVPR.2005.130</a>'
  apa: 'Rother, C., Kumar, S., Kolmogorov, V., &#38; Blake, A. (2005). Digital tapestry.
    In <i>Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision
    and Pattern Recognition Volume 1</i> (Vol. 1, pp. 589–596). San Diego, CA, United
    States: IEEE. <a href="https://doi.org/10.1109/CVPR.2005.130">https://doi.org/10.1109/CVPR.2005.130</a>'
  chicago: Rother, Carsten, Sanjiv Kumar, Vladimir Kolmogorov, and Andrew Blake. “Digital
    Tapestry.” In <i>Proceedings of the 2005 IEEE Computer Society Conference on Computer
    Vision and Pattern Recognition Volume 1</i>, 1:589–96. IEEE, 2005. <a href="https://doi.org/10.1109/CVPR.2005.130">https://doi.org/10.1109/CVPR.2005.130</a>.
  ieee: C. Rother, S. Kumar, V. Kolmogorov, and A. Blake, “Digital tapestry,” in <i>Proceedings
    of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition
    Volume 1</i>, San Diego, CA, United States, 2005, vol. 1, pp. 589–596.
  ista: 'Rother C, Kumar S, Kolmogorov V, Blake A. 2005. Digital tapestry. Proceedings
    of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition
    Volume 1. CVPR: Computer Vision and Pattern Recognition vol. 1, 589–596.'
  mla: Rother, Carsten, et al. “Digital Tapestry.” <i>Proceedings of the 2005 IEEE
    Computer Society Conference on Computer Vision and Pattern Recognition Volume
    1</i>, vol. 1, IEEE, 2005, pp. 589–96, doi:<a href="https://doi.org/10.1109/CVPR.2005.130">10.1109/CVPR.2005.130</a>.
  short: C. Rother, S. Kumar, V. Kolmogorov, A. Blake, in:, Proceedings of the 2005
    IEEE Computer Society Conference on Computer Vision and Pattern Recognition Volume
    1, IEEE, 2005, pp. 589–596.
conference:
  end_date: 2005-06-25
  location: San Diego, CA, United States
  name: 'CVPR: Computer Vision and Pattern Recognition'
  start_date: 2005-06-20
das_tickbox: '1'
date_created: 2018-12-11T12:01:50Z
date_published: 2005-07-25T00:00:00Z
date_updated: 2026-07-02T09:06:43Z
day: '25'
doi: 10.1109/CVPR.2005.130
extern: '1'
intvolume: '         1'
language:
- iso: eng
main_file_link:
- url: http://research.microsoft.com/en-us/um/people/ablake/papers/ablake/rother_cvpr05.pdf
month: '07'
oa_version: None
page: 589 - 596
publication: Proceedings of the 2005 IEEE Computer Society Conference on Computer
  Vision and Pattern Recognition Volume 1
publication_identifier:
  isbn:
  - '0769523722'
  issn:
  - 1063-6919
publication_status: published
publisher: IEEE
publist_id: '3503'
status: public
title: Digital tapestry
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 1
year: '2005'
...
---
OA_place: repository
OA_type: green
_id: '3176'
abstract:
- lang: eng
  text: "This paper demonstrates the high quality, real-time segmentation techniques.
    We achieve real-time segmentation of foreground from background layers in stereo
    video sequences. Automatic separation of layers from colour/contrast or from stereo
    alone is known to be error-prone. Here, colour, contrast and stereo matching information
    are fused to infer layers accurately and efficiently. The first algorithm, layered
    dynamic programming (LDP), solves stereo in an extended 6-state space that represents
    both foreground/background layers and occluded regions. The stereo-match likelihood
    is then fused with a contrast-sensitive colour model that is learned on the fly,
    and stereo disparities are obtained by dynamic programming. The second algorithm,
    layered graph cut (LGC), does not directly solve stereo. Instead the stereo match
    likelihood is marginalised over foreground and background hypotheses, and fused
    with a contrast-sensitive colour model like the one used in LDP. Segmentation
    is solved efficiently by ternary graph cut. Both algorithms are evaluated with
    respect to ground truth data and found to have similar performance, substantially
    better than stereo or colour/contrast alone. However, their characteristics with
    respect to computational efficiency are rather different. The algorithms are demonstrated
    in the application of background substitution and shown to give good quality composite
    video output.\r\n"
article_processing_charge: No
author:
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
- first_name: Antonio
  full_name: Criminisi, Antonio
  last_name: Criminisi
- first_name: Andrew
  full_name: Blake, Andrew
  last_name: Blake
- first_name: Geoffrey
  full_name: Cross, Geoffrey
  last_name: Cross
- first_name: Carsten
  full_name: Rother, Carsten
  last_name: Rother
citation:
  ama: 'Kolmogorov V, Criminisi A, Blake A, Cross G, Rother C. Bi-layer segmentation
    of binocular stereo video. In: <i>Proceedings of the 2005 IEEE Computer Society
    Conference on Computer Vision and Pattern Recognition</i>. IEEE; 2005:1186-1186.
    doi:<a href="https://doi.org/10.1109/CVPR.2005.90">10.1109/CVPR.2005.90</a>'
  apa: 'Kolmogorov, V., Criminisi, A., Blake, A., Cross, G., &#38; Rother, C. (2005).
    Bi-layer segmentation of binocular stereo video. In <i>Proceedings of the 2005
    IEEE Computer Society Conference on Computer Vision and Pattern Recognition</i>
    (pp. 1186–1186). San Diego, CA, United States: IEEE. <a href="https://doi.org/10.1109/CVPR.2005.90">https://doi.org/10.1109/CVPR.2005.90</a>'
  chicago: Kolmogorov, Vladimir, Antonio Criminisi, Andrew Blake, Geoffrey Cross,
    and Carsten Rother. “Bi-Layer Segmentation of Binocular Stereo Video.” In <i>Proceedings
    of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition</i>,
    1186–1186. IEEE, 2005. <a href="https://doi.org/10.1109/CVPR.2005.90">https://doi.org/10.1109/CVPR.2005.90</a>.
  ieee: V. Kolmogorov, A. Criminisi, A. Blake, G. Cross, and C. Rother, “Bi-layer
    segmentation of binocular stereo video,” in <i>Proceedings of the 2005 IEEE Computer
    Society Conference on Computer Vision and Pattern Recognition</i>, San Diego,
    CA, United States, 2005, pp. 1186–1186.
  ista: 'Kolmogorov V, Criminisi A, Blake A, Cross G, Rother C. 2005. Bi-layer segmentation
    of binocular stereo video. Proceedings of the 2005 IEEE Computer Society Conference
    on Computer Vision and Pattern Recognition. CVPR: Computer Vision and Pattern
    Recognition, 1186–1186.'
  mla: Kolmogorov, Vladimir, et al. “Bi-Layer Segmentation of Binocular Stereo Video.”
    <i>Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision
    and Pattern Recognition</i>, IEEE, 2005, pp. 1186–1186, doi:<a href="https://doi.org/10.1109/CVPR.2005.90">10.1109/CVPR.2005.90</a>.
  short: V. Kolmogorov, A. Criminisi, A. Blake, G. Cross, C. Rother, in:, Proceedings
    of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition,
    IEEE, 2005, pp. 1186–1186.
conference:
  end_date: 2005-06-25
  location: San Diego, CA, United States
  name: 'CVPR: Computer Vision and Pattern Recognition'
  start_date: 2005-06-20
das_tickbox: '1'
date_created: 2018-12-11T12:01:50Z
date_published: 2005-06-20T00:00:00Z
date_updated: 2026-07-15T12:24:09Z
day: '20'
doi: 10.1109/CVPR.2005.90
extern: '1'
language:
- iso: eng
month: '06'
oa_version: None
page: 1186 - 1186
publication: Proceedings of the 2005 IEEE Computer Society Conference on Computer
  Vision and Pattern Recognition
publication_identifier:
  isbn:
  - '0769523722'
  issn:
  - 1063-6919
publication_status: published
publisher: IEEE
publist_id: '3504'
status: public
title: Bi-layer segmentation of binocular stereo video
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2005'
...