What energy functions can be minimized via graph cuts?

IEEE Transactions on Pattern Analysis and Machine Intelligence
Vladimir Kolmogorov, Ramin Zabih

Abstract

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 give a characterization of the energy functions that can be minimized by graph cuts. Our results are restricted to functions of 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 give a precise characterization of what energy functions can be minimized using graph cuts, among the energy functions that can be written as a sum of terms containing three or fewer binary variables. We also provide a general-purpose construction to minimize such an energy function. Finally, we give a necessary condition for any energy function of binary variables to be minimized by graph cuts. Researchers who are considering the use of graph cuts to optimiz...Continue Reading

References

Sep 2, 1985·Nature·T PoggioC Koch
Feb 5, 2008·IEEE Transactions on Image Processing : a Publication of the IEEE Signal Processing Society·José M B Dias, José M N Leitao
Jun 1, 1984·IEEE Transactions on Pattern Analysis and Machine Intelligence·S Geman, D Geman

❮ Previous
Next ❯

Citations

Jan 16, 2013·Journal of Digital Imaging·Yao WuWufan Chen
Jan 25, 2012·International Journal of Computer Assisted Radiology and Surgery·Daniel F MalanEdward R Valstar
Mar 1, 2012·International Journal of Computer Assisted Radiology and Surgery·M FreimanJ Sosna
Jun 4, 2013·Computerized Medical Imaging and Graphics : the Official Journal of the Computerized Medical Imaging Society·Manivannan SundarapandianVijay Daniel Manason
Nov 4, 2011·Microscopy and Microanalysis : the Official Journal of Microscopy Society of America, Microbeam Analysis Society, Microscopical Society of Canada·Jan MichálekLucie Kubínová
Aug 14, 2009·Medical Physics·Yuanjie ZhengDinggang Shen
May 17, 2011·Annual Review of Biomedical Engineering·Ben GlockerNikos Paragios
Mar 29, 2007·Investigative Ophthalmology & Visual Science·Michael D AbràmoffYoung H Kwon
Oct 25, 2013·PloS One·Koichi OgawaraYaokai Feng
Jan 28, 2014·PloS One·Chunhui ZhangJimin Liang
Dec 4, 2012·Sensors·Antonio Hernández-VelaSergio Escalera
Jul 19, 2013·International Journal of Computer Assisted Radiology and Surgery·Wei WuJason J Corso
Jan 1, 2013·Computational and Mathematical Methods in Medicine·Brian Liu, Ashish Raj
Feb 15, 2014·TheScientificWorldJournal·Rui MinJean-Luc Dugelay
Apr 29, 2014·Computer Methods and Programs in Biomedicine·Oscar EstebanMeritxell Bach-Cuadra
Apr 1, 2014·Computers in Biology and Medicine·Ioannis MarrasIoannis Pitas
Dec 8, 2009·Optical Engineering : the Journal of the Society of Photo-optical Instrumentation Engineers·Bugao XuJeanne H Freeland-Graves
Nov 26, 2015·Eye and Vision·Dominic WilliamsAhmed Elsheikh
Jul 18, 2015·International Journal for Numerical Methods in Biomedical Engineering·Feng Zhao, Xianghua Xie
Jun 1, 2013·Optics Letters·Shibo GaoYongqiang Zhao
Apr 16, 2013·Computer Vision and Image Understanding : CVIU·Xinjian ChenDrew A Torigian
Sep 11, 2012·Computerized Medical Imaging and Graphics : the Official Journal of the Computerized Medical Imaging Society·Laura IgualPetia Radeva
Oct 23, 2012·Medical Image Analysis·Marc Niethammer, Christopher Zach
Jan 14, 2016·Scientific Reports·Guoqi LiLuping Shi
Dec 6, 2011·Applied Radiation and Isotopes : Including Data, Instrumentation and Methods for Use in Agriculture, Industry and Medicine·Anderson A M MenesesRegina C Barroso
Feb 3, 2009·Journal of the Optical Society of America. A, Optics, Image Science, and Vision·Xiang Zhang, Jie Yang
Sep 2, 2009·Journal of the Optical Society of America. A, Optics, Image Science, and Vision·Gonçalo Valadão, José Bioucas-Dias
May 8, 2010·Journal of the Optical Society of America. A, Optics, Image Science, and Vision·Rajiv R Sahay, A N Rajagopalan
Aug 2, 2011·Neural Networks : the Official Journal of the International Neural Network Society·Chien-Chung ChangYuh-Jye Lee
May 3, 2011·Computerized Medical Imaging and Graphics : the Official Journal of the Computerized Medical Imaging Society·Alper AyvaciJochen Kruecker
Nov 3, 2010·Medical Image Analysis·Philipp FürnstahlMatthias Harders
Jul 15, 2009·Computerized Medical Imaging and Graphics : the Official Journal of the Computerized Medical Imaging Society·Junhua ZhangXinling Shi
Jul 27, 2015·Medical Image Analysis·Mustafa Gokhan UzunbasDimitris Metaxas
Dec 9, 2008·Artificial Intelligence in Medicine·Paola CampadelliAndrea Esposito
May 9, 2015·IEEE Transactions on Image Processing : a Publication of the IEEE Signal Processing Society·Jin-Hwan KimChang-Su Kim

❮ Previous
Next ❯

Related Concepts

Trending Feeds

COVID-19

Coronaviruses encompass a large family of viruses that cause the common cold as well as more serious diseases, such as the ongoing outbreak of coronavirus disease 2019 (COVID-19; formally known as 2019-nCoV). Coronaviruses can spread from animals to humans; symptoms include fever, cough, shortness of breath, and breathing difficulties; in more severe cases, infection can lead to death. This feed covers recent research on COVID-19.

Blastomycosis

Blastomycosis fungal infections spread through inhaling Blastomyces dermatitidis spores. Discover the latest research on blastomycosis fungal infections here.

Nuclear Pore Complex in ALS/FTD

Alterations in nucleocytoplasmic transport, controlled by the nuclear pore complex, may be involved in the pathomechanism underlying multiple neurodegenerative diseases including Amyotrophic Lateral Sclerosis and Frontotemporal Dementia. Here is the latest research on the nuclear pore complex in ALS and FTD.

Applications of Molecular Barcoding

The concept of molecular barcoding is that each original DNA or RNA molecule is attached to a unique sequence barcode. Sequence reads having different barcodes represent different original molecules, while sequence reads having the same barcode are results of PCR duplication from one original molecule. Discover the latest research on molecular barcoding here.

Chronic Fatigue Syndrome

Chronic fatigue syndrome is a disease characterized by unexplained disabling fatigue; the pathology of which is incompletely understood. Discover the latest research on chronic fatigue syndrome here.

Evolution of Pluripotency

Pluripotency refers to the ability of a cell to develop into three primary germ cell layers of the embryo. This feed focuses on the mechanisms that underlie the evolution of pluripotency. Here is the latest research.

Position Effect Variegation

Position Effect Variagation occurs when a gene is inactivated due to its positioning near heterochromatic regions within a chromosome. Discover the latest research on Position Effect Variagation here.

STING Receptor Agonists

Stimulator of IFN genes (STING) are a group of transmembrane proteins that are involved in the induction of type I interferon that is important in the innate immune response. The stimulation of STING has been an active area of research in the treatment of cancer and infectious diseases. Here is the latest research on STING receptor agonists.

Microbicide

Microbicides are products that can be applied to vaginal or rectal mucosal surfaces with the goal of preventing, or at least significantly reducing, the transmission of sexually transmitted infections. Here is the latest research on microbicides.

Related Papers

IEEE Transactions on Pattern Analysis and Machine Intelligence
Yuri Boykov, Vladimir Kolmogorov
IEEE Transactions on Pattern Analysis and Machine Intelligence
Richard SzeliskiCarsten Rother
IEEE Transactions on Image Processing : a Publication of the IEEE Signal Processing Society
T F Chan, L A Vese
IEEE Transactions on Pattern Analysis and Machine Intelligence
Nikos Komodakis, Georgios Tziritas
IEEE Transactions on Pattern Analysis and Machine Intelligence
Pushmeet Kohli, Philip H S Torr
© 2021 Meta ULC. All rights reserved