ML Anthology

Efficient Planar Graph Cuts with Applications in Computer Vision

Frank R. Schmidt, Eno Töppe, Daniel Cremers
CVPR 2009 pp. 351-356
doi:10.1109/CVPR.2009.5206863 /cvpr/2009/schmidt2009cvpr-efficient/

Abstract

We present a fast graph cut algorithm for planar graphs. It is based on the graph theoretical work and leads to an efficient method that we apply on shape matching and image segmentation. In contrast to currently used methods in computer vision, the presented approach provides an upper bound for its runtime behavior that is almost linear. In particular, we are able to match two different planar shapes of N points in O(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> log N) and segment a given image of N pixels in O(N log N). We present two experimental benchmark studies which demonstrate that the presented method is also in practice faster than previously proposed graph cut methods: On planar shape matching and image segmentation we observe a speed-up of an order of magnitude, depending on resolution.

CVPR Semantic Scholar

Cite

Text

Schmidt et al. "Efficient Planar Graph Cuts with Applications in Computer Vision." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2009. doi:10.1109/CVPR.2009.5206863

Markdown

[Schmidt et al. "Efficient Planar Graph Cuts with Applications in Computer Vision." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2009.](https://mlanthology.org/cvpr/2009/schmidt2009cvpr-efficient/) doi:10.1109/CVPR.2009.5206863

BibTeX

@inproceedings{schmidt2009cvpr-efficient,
  title     = {{Efficient Planar Graph Cuts with Applications in Computer Vision}},
  author    = {Schmidt, Frank R. and Töppe, Eno and Cremers, Daniel},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year      = {2009},
  pages     = {351-356},
  doi       = {10.1109/CVPR.2009.5206863},
  url       = {https://mlanthology.org/cvpr/2009/schmidt2009cvpr-efficient/}
}