A dual decomposition approach to feature correspondence

article A dual decomposition approach to feature correspondence published yes Lorenzo Torresani author Vladimir Kolmogorov author 3D50B0BA-F248-11E8-B48F-1D18A9856A87 Carsten Rother author VlKo department Microsoft Research Faculty Fellowship project 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. IEEE2012 eng IEEE Transactions on Pattern Analysis and Machine Intelligence 00031256060000210.1109/TPAMI.2012.105 352259 - 271 Torresani, Lorenzo, Vladimir Kolmogorov, and Carsten Rother. “A Dual Decomposition Approach to Feature Correspondence.” IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE, 2012. <a href="https://doi.org/10.1109/TPAMI.2012.105">https://doi.org/10.1109/TPAMI.2012.105</a>. 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. L. Torresani, V. Kolmogorov, C. Rother, IEEE Transactions on Pattern Analysis and Machine Intelligence 35 (2012) 259–271. 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. 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:<a href="https://doi.org/10.1109/TPAMI.2012.105">10.1109/TPAMI.2012.105</a> 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:<a href="https://doi.org/10.1109/TPAMI.2012.105">10.1109/TPAMI.2012.105</a>. Torresani, L., Kolmogorov, V., & Rother, C. (2012). A dual decomposition approach to feature correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE. <a href="https://doi.org/10.1109/TPAMI.2012.105">https://doi.org/10.1109/TPAMI.2012.105</a> 29312018-12-11T12:00:24Z2025-09-30T08:15:06Z