conference paper published yes Paul Swoboda author 446560C6-F248-11E8-B48F-1D18A9856A87 Carsten Rother author Carsten Abu Alhaija author Dagmar Kainmueller author Bogdan Savchynskyy author VlKo department CVPR: Computer Vision and Pattern Recognition Discrete Optimization in Computer Vision: Theory and Practice project We study the quadratic assignment problem, in computer vision also known as graph matching. Two leading solvers for this problem optimize the Lagrange decomposition duals with sub-gradient and dual ascent (also known as message passing) updates. We explore this direction further and propose several additional Lagrangean relaxations of the graph matching problem along with corresponding algorithms, which are all based on a common dual ascent framework. Our extensive empirical evaluation gives several theoretical insights and suggests a new state-of-the-art anytime solver for the considered problem. Our improvement over state-of-the-art is particularly visible on a new dataset with large-scale sparse problem instances containing more than 500 graph nodes each. https://research-explorer.ista.ac.at/download/916/5848/2017_CVPR_Swoboda2.pdf application/pdfno IEEE2017Honolulu, HA, United States eng 978-153860457-1 00041837140701810.1109/CVPR.2017.747 20177062-7071 Swoboda P, Rother C, Abu Alhaija C, Kainmueller D, Savchynskyy B. 2017. A study of lagrangean decompositions and dual ascent solvers for graph matching. CVPR: Computer Vision and Pattern Recognition vol. 2017, 7062–7071. P. Swoboda, C. Rother, C. Abu Alhaija, D. Kainmueller, and B. Savchynskyy, “A study of lagrangean decompositions and dual ascent solvers for graph matching,” presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States, 2017, vol. 2017, pp. 7062–7071. Swoboda, Paul, et al. <i>A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching</i>. Vol. 2017, IEEE, 2017, pp. 7062–71, doi:<a href="https://doi.org/10.1109/CVPR.2017.747">10.1109/CVPR.2017.747</a>. Swoboda, Paul, Carsten Rother, Carsten Abu Alhaija, Dagmar Kainmueller, and Bogdan Savchynskyy. “A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching,” 2017:7062–71. IEEE, 2017. <a href="https://doi.org/10.1109/CVPR.2017.747">https://doi.org/10.1109/CVPR.2017.747</a>. Swoboda P, Rother C, Abu Alhaija C, Kainmueller D, Savchynskyy B. A study of lagrangean decompositions and dual ascent solvers for graph matching. In: Vol 2017. IEEE; 2017:7062-7071. doi:<a href="https://doi.org/10.1109/CVPR.2017.747">10.1109/CVPR.2017.747</a> Swoboda, P., Rother, C., Abu Alhaija, C., Kainmueller, D., &#38; Savchynskyy, B. (2017). A study of lagrangean decompositions and dual ascent solvers for graph matching (Vol. 2017, pp. 7062–7071). Presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States: IEEE. <a href="https://doi.org/10.1109/CVPR.2017.747">https://doi.org/10.1109/CVPR.2017.747</a> P. Swoboda, C. Rother, C. Abu Alhaija, D. Kainmueller, B. Savchynskyy, in:, IEEE, 2017, pp. 7062–7071. 9162018-12-11T11:49:11Z2024-11-04T13:52:34Z