--- _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' ...