---
_id: '2931'
abstract:
- lang: eng
text: "In this paper, we present a new approach for establishing correspondences
between sparse image features related by an unknown nonrigid mapping and corrupted
by clutter and occlusion, such as points extracted from images of different instances
of the same object category. We formulate this matching task as an energy minimization
problem by defining an elaborate objective function of the appearance and the
spatial arrangement of the features. Optimization of this energy is an instance
of graph matching, which is in general an NP-hard problem. We describe a novel
graph matching optimization technique, which we refer to as dual decomposition
(DD), and demonstrate on a variety of examples that this method outperforms existing
graph matching algorithms. In the majority of our examples, DD is able to find
the global minimum within a minute. The ability to globally optimize the objective
allows us to accurately learn the parameters of our matching model from training
examples. We show on several matching tasks that our learned model yields results
superior to those of state-of-the-art methods.\r\n"
acknowledgement: This research was funded in part by Microsoft Research.
author:
- first_name: Lorenzo
full_name: Torresani, Lorenzo
last_name: Torresani
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Carsten
full_name: Rother, Carsten
last_name: Rother
citation:
ama: Torresani L, Kolmogorov V, Rother C. A dual decomposition approach to feature
correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence.
2012;35(2):259-271. doi:10.1109/TPAMI.2012.105
apa: Torresani, L., Kolmogorov, V., & Rother, C. (2012). A dual decomposition
approach to feature correspondence. IEEE Transactions on Pattern Analysis and
Machine Intelligence. IEEE. https://doi.org/10.1109/TPAMI.2012.105
chicago: Torresani, Lorenzo, Vladimir Kolmogorov, and Carsten Rother. “A Dual Decomposition
Approach to Feature Correspondence.” IEEE Transactions on Pattern Analysis
and Machine Intelligence. IEEE, 2012. https://doi.org/10.1109/TPAMI.2012.105.
ieee: L. Torresani, V. Kolmogorov, and C. Rother, “A dual decomposition approach
to feature correspondence,” IEEE Transactions on Pattern Analysis and Machine
Intelligence, vol. 35, no. 2. IEEE, pp. 259–271, 2012.
ista: Torresani L, Kolmogorov V, Rother C. 2012. A dual decomposition approach to
feature correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence.
35(2), 259–271.
mla: Torresani, Lorenzo, et al. “A Dual Decomposition Approach to Feature Correspondence.”
IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35,
no. 2, IEEE, 2012, pp. 259–71, doi:10.1109/TPAMI.2012.105.
short: L. Torresani, V. Kolmogorov, C. Rother, IEEE Transactions on Pattern Analysis
and Machine Intelligence 35 (2012) 259–271.
date_created: 2018-12-11T12:00:24Z
date_published: 2012-05-08T00:00:00Z
date_updated: 2021-01-12T07:00:46Z
day: '08'
department:
- _id: VlKo
doi: 10.1109/TPAMI.2012.105
intvolume: ' 35'
issue: '2'
language:
- iso: eng
month: '05'
oa_version: None
page: 259 - 271
project:
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: IEEE Transactions on Pattern Analysis and Machine Intelligence
publication_status: published
publisher: IEEE
publist_id: '3805'
quality_controlled: '1'
scopus_import: 1
status: public
title: A dual decomposition approach to feature correspondence
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 35
year: '2012'
...
---
_id: '3117'
abstract:
- lang: eng
text: We consider the problem of minimizing a function represented as a sum of submodular
terms. We assume each term allows an efficient computation of exchange capacities.
This holds, for example, for terms depending on a small number of variables, or
for certain cardinality-dependent terms. A naive application of submodular minimization
algorithms would not exploit the existence of specialized exchange capacity subroutines
for individual terms. To overcome this, we cast the problem as a submodular flow
(SF) problem in an auxiliary graph in such a way that applying most existing SF
algorithms would rely only on these subroutines. We then explore in more detail
Iwata's capacity scaling approach for submodular flows (Iwata 1997 [19]). In particular,
we show how to improve its complexity in the case when the function contains cardinality-dependent
terms.
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: Kolmogorov V. Minimizing a sum of submodular functions. Discrete Applied
Mathematics. 2012;160(15):2246-2258. doi:10.1016/j.dam.2012.05.025
apa: Kolmogorov, V. (2012). Minimizing a sum of submodular functions. Discrete
Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2012.05.025
chicago: Kolmogorov, Vladimir. “Minimizing a Sum of Submodular Functions.” Discrete
Applied Mathematics. Elsevier, 2012. https://doi.org/10.1016/j.dam.2012.05.025.
ieee: V. Kolmogorov, “Minimizing a sum of submodular functions,” Discrete Applied
Mathematics, vol. 160, no. 15. Elsevier, pp. 2246–2258, 2012.
ista: Kolmogorov V. 2012. Minimizing a sum of submodular functions. Discrete Applied
Mathematics. 160(15), 2246–2258.
mla: Kolmogorov, Vladimir. “Minimizing a Sum of Submodular Functions.” Discrete
Applied Mathematics, vol. 160, no. 15, Elsevier, 2012, pp. 2246–58, doi:10.1016/j.dam.2012.05.025.
short: V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 2246–2258.
date_created: 2018-12-11T12:01:29Z
date_published: 2012-10-01T00:00:00Z
date_updated: 2021-01-12T07:41:11Z
day: '01'
department:
- _id: VlKo
doi: 10.1016/j.dam.2012.05.025
intvolume: ' 160'
issue: '15'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1006.1990
month: '10'
oa: 1
oa_version: Preprint
page: 2246 - 2258
publication: Discrete Applied Mathematics
publication_status: published
publisher: Elsevier
publist_id: '3582'
quality_controlled: '1'
scopus_import: 1
status: public
title: Minimizing a sum of submodular functions
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 160
year: '2012'
...
---
_id: '3257'
abstract:
- lang: eng
text: Consider a convex relaxation f̂ of a pseudo-Boolean function f. We say that
the relaxation is totally half-integral if f̂(x) is a polyhedral function with
half-integral extreme points x, and this property is preserved after adding an
arbitrary combination of constraints of the form x i=x j, x i=1-x j, and x i=γ
where γ∈{0,1,1/2} is a constant. A well-known example is the roof duality relaxation
for quadratic pseudo-Boolean functions f. We argue that total half-integrality
is a natural requirement for generalizations of roof duality to arbitrary pseudo-Boolean
functions. Our contributions are as follows. First, we provide a complete characterization
of totally half-integral relaxations f̂ by establishing a one-to-one correspondence
with bisubmodular functions. Second, we give a new characterization of bisubmodular
functions. Finally, we show some relationships between general totally half-integral
relaxations and relaxations based on the roof duality. On the conceptual level,
our results show that bisubmodular functions provide a natural generalization
of the roof duality approach to higher-order terms. This can be viewed as a non-submodular
analogue of the fact that submodular functions generalize the s-t minimum cut
problem with non-negative weights to higher-order terms.
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: Kolmogorov V. Generalized roof duality and bisubmodular functions. Discrete
Applied Mathematics. 2012;160(4-5):416-426. doi:10.1016/j.dam.2011.10.026
apa: Kolmogorov, V. (2012). Generalized roof duality and bisubmodular functions.
Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2011.10.026
chicago: Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.”
Discrete Applied Mathematics. Elsevier, 2012. https://doi.org/10.1016/j.dam.2011.10.026.
ieee: V. Kolmogorov, “Generalized roof duality and bisubmodular functions,” Discrete
Applied Mathematics, vol. 160, no. 4–5. Elsevier, pp. 416–426, 2012.
ista: Kolmogorov V. 2012. Generalized roof duality and bisubmodular functions. Discrete
Applied Mathematics. 160(4–5), 416–426.
mla: Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.”
Discrete Applied Mathematics, vol. 160, no. 4–5, Elsevier, 2012, pp. 416–26,
doi:10.1016/j.dam.2011.10.026.
short: V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 416–426.
date_created: 2018-12-11T12:02:18Z
date_published: 2012-03-01T00:00:00Z
date_updated: 2023-02-23T11:04:49Z
day: '01'
department:
- _id: VlKo
doi: 10.1016/j.dam.2011.10.026
external_id:
arxiv:
- '1005.2305'
intvolume: ' 160'
issue: 4-5
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1005.2305
month: '03'
oa: 1
oa_version: Preprint
page: 416 - 426
publication: Discrete Applied Mathematics
publication_status: published
publisher: Elsevier
publist_id: '3397'
quality_controlled: '1'
related_material:
record:
- id: '2934'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Generalized roof duality and bisubmodular functions
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 160
year: '2012'
...
---
_id: '3124'
abstract:
- lang: eng
text: "We consider the problem of inference in a graphical model with binary variables.
While in theory it is arguably preferable to compute marginal probabilities, in
practice researchers often use MAP inference due to the availability of efficient
discrete optimization algorithms. We bridge the gap between the two approaches
by introducing the Discrete Marginals technique in which approximate marginals
are obtained by minimizing an objective function with unary and pairwise terms
over a discretized domain. This allows the use of techniques originally developed
for MAP-MRF inference and learning. We explore two ways to set up the objective
function - by discretizing the Bethe free energy and by learning it from training
data. Experimental results show that for certain types of graphs a learned function
can outperform the Bethe approximation. We also establish a link between the Bethe
free energy and submodular functions.\r\n"
alternative_title:
- Inferning 2012
author:
- first_name: Filip
full_name: Korc, Filip
id: 476A2FD6-F248-11E8-B48F-1D18A9856A87
last_name: Korc
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: 'Korc F, Kolmogorov V, Lampert C. Approximating marginals using discrete energy
minimization. In: ICML; 2012.'
apa: 'Korc, F., Kolmogorov, V., & Lampert, C. (2012). Approximating marginals
using discrete energy minimization. Presented at the ICML: International Conference
on Machine Learning, Edinburgh, Scotland: ICML.'
chicago: Korc, Filip, Vladimir Kolmogorov, and Christoph Lampert. “Approximating
Marginals Using Discrete Energy Minimization.” ICML, 2012.
ieee: 'F. Korc, V. Kolmogorov, and C. Lampert, “Approximating marginals using discrete
energy minimization,” presented at the ICML: International Conference on Machine
Learning, Edinburgh, Scotland, 2012.'
ista: 'Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete
energy minimization. ICML: International Conference on Machine Learning, Inferning
2012, .'
mla: Korc, Filip, et al. Approximating Marginals Using Discrete Energy Minimization.
ICML, 2012.
short: F. Korc, V. Kolmogorov, C. Lampert, in:, ICML, 2012.
conference:
end_date: 2012-07-01
location: Edinburgh, Scotland
name: 'ICML: International Conference on Machine Learning'
start_date: 2012-06-26
date_created: 2018-12-11T12:01:31Z
date_published: 2012-06-30T00:00:00Z
date_updated: 2023-02-23T12:24:24Z
day: '30'
ddc:
- '000'
department:
- _id: ChLa
- _id: VlKo
file:
- access_level: open_access
checksum: 3d0d4246548c736857302aadb2ff5d15
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:34Z
date_updated: 2020-07-14T12:46:00Z
file_id: '4889'
file_name: IST-2016-565-v1+1_DM-inferning2012.pdf
file_size: 305836
relation: main_file
file_date_updated: 2020-07-14T12:46:00Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
publication_status: published
publisher: ICML
publist_id: '3575'
pubrep_id: '565'
quality_controlled: '1'
related_material:
record:
- id: '5396'
relation: later_version
status: public
status: public
title: Approximating marginals using discrete energy minimization
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '5396'
abstract:
- lang: eng
text: We consider the problem of inference in agraphical model with binary variables.
While in theory it is arguably preferable to compute marginal probabilities, in
practice researchers often use MAP inference due to the availability of efficient
discrete optimization algorithms. We bridge the gap between the two approaches
by introducing the Discrete Marginals technique in which approximate marginals
are obtained by minimizing an objective function with unary and pair-wise terms
over a discretized domain. This allows the use of techniques originally devel-oped
for MAP-MRF inference and learning. We explore two ways to set up the objective
function - by discretizing the Bethe free energy and by learning it from training
data. Experimental results show that for certain types of graphs a learned function
can out-perform the Bethe approximation. We also establish a link between the
Bethe free energy and submodular functions.
alternative_title:
- IST Austria Technical Report
author:
- first_name: Filip
full_name: Korc, Filip
id: 476A2FD6-F248-11E8-B48F-1D18A9856A87
last_name: Korc
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: Korc F, Kolmogorov V, Lampert C. Approximating Marginals Using Discrete
Energy Minimization. IST Austria; 2012. doi:10.15479/AT:IST-2012-0003
apa: Korc, F., Kolmogorov, V., & Lampert, C. (2012). Approximating marginals
using discrete energy minimization. IST Austria. https://doi.org/10.15479/AT:IST-2012-0003
chicago: Korc, Filip, Vladimir Kolmogorov, and Christoph Lampert. Approximating
Marginals Using Discrete Energy Minimization. IST Austria, 2012. https://doi.org/10.15479/AT:IST-2012-0003.
ieee: F. Korc, V. Kolmogorov, and C. Lampert, Approximating marginals using discrete
energy minimization. IST Austria, 2012.
ista: Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete
energy minimization, IST Austria, 13p.
mla: Korc, Filip, et al. Approximating Marginals Using Discrete Energy Minimization.
IST Austria, 2012, doi:10.15479/AT:IST-2012-0003.
short: F. Korc, V. Kolmogorov, C. Lampert, Approximating Marginals Using Discrete
Energy Minimization, IST Austria, 2012.
date_created: 2018-12-12T11:39:06Z
date_published: 2012-07-23T00:00:00Z
date_updated: 2023-02-23T11:13:22Z
day: '23'
ddc:
- '000'
department:
- _id: VlKo
- _id: ChLa
doi: 10.15479/AT:IST-2012-0003
file:
- access_level: open_access
checksum: 7e0ba85ad123b13223aaf6cdde2d288c
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:29Z
date_updated: 2020-07-14T12:46:44Z
file_id: '5490'
file_name: IST-2012-0003_IST-2012-0003.pdf
file_size: 618744
relation: main_file
file_date_updated: 2020-07-14T12:46:44Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '13'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '36'
related_material:
record:
- id: '3124'
relation: earlier_version
status: public
status: public
title: Approximating marginals using discrete energy minimization
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...