Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Minimizing nonsubmodular functions with graph cuts - a review.

Vladimir Kolmogorov1, Carsten Rother

  • 1University College London, Martlesham Heath, UK. vnk@adastral.ucl.ac.uk

IEEE Transactions on Pattern Analysis and Machine Intelligence
|May 15, 2007
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Discovering Digital Tumor Signatures-Using Latent Code Representations to Manipulate and Classify Liver Lesions.

Cancers·2021
Same author

Visual Camera Re-Localization From RGB and RGB-D Images Using DSAC.

IEEE transactions on pattern analysis and machine intelligence·2021
Same author

Can Virtual Contrast Enhancement in Brain MRI Replace Gadolinium?: A Feasibility Study.

Investigative radiology·2019
Same author

Uncertainty-aware performance assessment of optical imaging modalities with invertible neural networks.

International journal of computer assisted radiology and surgery·2019
Same author

Cascades of Regression Tree Fields for Image Restoration.

IEEE transactions on pattern analysis and machine intelligence·2016
Same author

A New Look at Reweighted Message Passing.

IEEE transactions on pattern analysis and machine intelligence·2015
Same journal

HardFlow: Hard-Constrained Sampling for Flow-Matching Models Via Trajectory Optimization.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

Industrial Brain: Self-Evolving Neuro-Symbolic Autonomy with Causal Resilience for Cyber-Physical Systems.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

Adaptive Hardness-Driven Dictionary Distillation for Incomplete Streaming View Clustering.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

Mixture of Global and Local Experts with Diffusion Transformer for Controllable Face Generation.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

Task-KV: Task-aware KV Cache Optimization via Semantic Differentiation of Attention Heads.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

Achieving Text-based Person Retrieval with Any Granularity.

IEEE transactions on pattern analysis and machine intelligence·2026
See all related articles

Graph cut optimization, widely used in computer vision for Markov Random Fields (MRFs), can optimize more than just submodular functions. This survey explores applying graph cuts to nonsubmodular functions for broader vision applications like texture restoration.

Area of Science:

  • Computer Vision
  • Optimization Techniques
  • Image Processing

Background:

  • Graph cut optimization is a standard tool for minimizing energy functions in computer vision, typically applied to pairwise Markov Random Fields (MRFs).
  • The prevailing view in computer vision is that graph cuts are limited to optimizing submodular functions.
  • Existing optimization literature contains results applicable to a wider range of energy functions, including nonsubmodular ones.

Purpose of the Study:

  • To survey and highlight optimization results demonstrating the applicability of graph cuts to nonsubmodular energy functions.
  • To bridge the gap between optimization theory and computer vision practice regarding graph cut capabilities.
  • To showcase the potential of these broader graph cut applications in computer vision tasks.

Main Methods:

Related Experiment Videos

  • Reviewing and synthesizing existing mathematical results on graph cut optimization for general energy functions.
  • Applying these generalized graph cut techniques to a specific computer vision problem.
  • Demonstrating the optimization of nonsubmodular energy functions using graph cuts.

Main Results:

  • Graph cuts can effectively optimize a broader class of energy functions beyond submodular functions.
  • The application of these techniques to binary texture restoration yields relevant improvements.
  • This work demonstrates the practical utility of previously underutilized optimization results in computer vision.

Conclusions:

  • The capabilities of graph cut optimization in computer vision are significantly underestimated.
  • Nonsubmodular energy functions can be optimized using graph cuts, expanding their applicability.
  • This research encourages the adoption of advanced graph cut techniques for enhanced performance in vision applications.