In this paper we address the problem of finding the most probable state of a discrete Markov random field (MRF), also known as the MRF energy minimization problem. The task is known to be NP-hard in general and its practical importance motivates numerous approximate algorithms. We propose a submodular relaxation approach (SMR) based on a Lagrangian relaxation of the initial problem. Unlike the dual decomposition approach of Komodakis et al. [29] SMR does not decompose the graph structure of the initial problem but constructs a submodular energy that is minimized within the Lagrangian relaxation. Our approach is applicable to both pairwise and high-order MRFs and allows to take into account global potentials of certain types. We study theoretical properties of the proposed approach and evaluate it experimentally.
Download full-text PDF |
Source |
|---|---|
| http://dx.doi.org/10.1109/TPAMI.2014.2369046 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
Shooting Utility Maximization in UAV-Assisted Wireless Camera Sensor Networks.
Sensors (Basel)
May 2022
College of Computer Science and Technology, Nanjing University, Nanjing 210023, China.
Recently, wireless camera sensor networks (WCSNs) have entered an era of rapid development, and WCSNs assisted by unmanned aerial vehicles (UAVs) are capable of providing enhanced flexibility, robustness and efficiency when executing missions such as shooting targets. Existing research has mainly focused on back-end image processing to improve the quality of captured images, but it has neglected the question of attaining quality images on the front-end, which is significantly influenced by the location and hovering time of the UAV. Therefore, in this paper, we conceive a novel shooting utility model to quantify shooting quality, which is maximized by simultaneously considering the UAV's trajectory planning, hovering time and shooting point selection.
View Article and Find Full Text PDFAn optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint.
Math Program
October 2020
ETH Zurich, Zurich, Switzerland.
Relaxation and rounding approaches became a standard and extremely versatile tool for constrained submodular function maximization. One of the most common rounding techniques in this context are contention resolution schemes. Such schemes round a fractional point by first rounding each coordinate independently, and then dropping some elements to reach a feasible set.
View Article and Find Full Text PDFA network information theoretic framework to characterise muscle synergies in space and time.
J Neural Eng
February 2022
Faculty of Biological sciences, School of Biomedical sciences, University of Leeds, Leeds, United Kingdom.
. Current approaches to muscle synergy extraction rely on linear dimensionality reduction algorithms that make specific assumptions on the underlying signals. However, to capture nonlinear time varying, large-scale but also muscle-specific interactions, a more generalised approach is required.
View Article and Find Full Text PDFSubmodular Maximization via Gradient Ascent: The Case of Deep Submodular Functions.
Adv Neural Inf Process Syst
December 2018
Depts. of Electrical & Computer Engineering, Seattle, WA 98195.
We study the problem of maximizing deep submodular functions (DSFs) [13, 3] subject to a matroid constraint. DSFs are an expressive class of submodular functions that include, as strict subfamilies, the facility location, weighted coverage, and sums of concave composed with modular functions. We use a strategy similar to the continuous greedy approach [6], but we show that the multilinear extension of any DSF has a natural and computationally attainable concave relaxation that we can optimize using gradient ascent.
View Article and Find Full Text PDFLocal Submodularization for Binary Pairwise Energies.
IEEE Trans Pattern Anal Mach Intell
October 2017
Many computer vision problems require optimization of binary non-submodular energies. We propose a general optimization framework based on local submodular approximations (LSA). Unlike standard LP relaxation methods that linearize the whole energy globally, our approach iteratively approximates the energy locally.
View Article and Find Full Text PDFWant AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!