{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:52:32Z","timestamp":1787323952495,"version":"build-2736575974"},"reference-count":37,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Imaging Sci."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>Dense conditional random fields (CRFs) have become a popular framework for modeling several problems in computer vision such as stereo correspondence and multiclass semantic segmentation. By modeling long-range interactions, dense CRFs provide a labeling that captures finer detail than their sparse counterparts. Currently, the state-of-the-art algorithm performs mean-field inference using a filter-based method but fails to provide a strong theoretical guarantee on the quality of the solution. A question naturally arises as to whether it is possible to obtain a maximum a posteriori (MAP) estimate of a dense CRF using a principled method. Within this paper, we show that this is indeed possible. Specifically, we will show that, by using a filter-based method, continuous relaxations of the MAP problem can be optimized efficiently using state-of-the-art algorithms. Specifically, we will solve a quadratic programming relaxation using the Frank--Wolfe algorithm and a linear programming relaxation by developing a proximal minimization framework. By exploiting labeling consistency in the higher-order potentials and utilizing the filter-based method, we are able to formulate the above algorithms such that each iteration has a complexity linear in the number of classes and random variables. The presented algorithms can be applied to any labeling problem using a dense CRF with sparse higher-order potentials. In this paper, we use semantic segmentation as an example application as it demonstrates the ability of the algorithm to scale to dense CRFs with large dimensions. We perform experiments on the Pascal dataset to indicate that the presented algorithms are able to attain lower energies than the mean-field inference method.<\/jats:p>","DOI":"10.1137\/18m1178104","type":"journal-article","created":{"date-parts":[[2019,1,30]],"date-time":"2019-01-30T15:33:37Z","timestamp":1548862417000},"page":"287-318","source":"Crossref","is-referenced-by-count":7,"title":["Efficient Relaxations for Dense CRFs with Sparse Higher-Order Potentials"],"prefix":"10.1137","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2707-6526","authenticated-orcid":true,"given":"Thomas","family":"Joy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alban","family":"Desmaison","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thalaiyasingam","family":"Ajanthan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rudy","family":"Bunel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mathieu","family":"Salzmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pushmeet","family":"Kohli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Philip H. S.","family":"Torr","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. Pawan","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,1,30]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"A. Adams, J. Baek, and M. Abraham,\n                      Fast high-dimensional filtering using the permutohedral lattice\n                      , in Proceedings of Eurographics, 2010.","DOI":"10.1111\/j.1467-8659.2009.01645.x"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"T. Ajanthan, A. Desmaison, R. Bunel, M. Salzmann, P. H. S. Torr, and M. P. Kumar,\n                      Efficient linear programming for dense CRFs\n                      , in Proceedings of CVPR, 2017.","DOI":"10.1109\/CVPR.2017.313"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/130941961"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"P. Baqu\u00e9, T. Bagautdinov, F. Fleuret, and P. Fua,\n                      Principled parallel mean-field inference for discrete random fields\n                      , in Proceedings of CVPR, 2016.","DOI":"10.1109\/CVPR.2016.630"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"S. Chandra, N. Usunier, and I. Kokkinos,\n                      Dense and low-rank gaussian crfs using deep embeddings\n                      , in Proceedings of International Conference on Computer Vision, Vol. 2, 2017.","DOI":"10.1109\/ICCV.2017.546"},{"key":"atypb6","unstructured":"C. Chekuri, S. Khanna, J. Naor, and L. Zosin,\n                      Approximation algorithms for the metric labeling problem via a new linear programming formulation\n                      , in Proceedings of SODA, 2001."},{"key":"atypb7","unstructured":"L. Chen, G. Papandreou, I. Kokkinos, K. Murphy, and A. L. Yuille,\n                      Semantic image segmentation with deep convolutional nets and fully connected CRFs\n                      , in Proceedings of ICLR, 2015."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2017.2699184"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1109\/34.1000236"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"A. Desmaison, R. Bunel, P. Kohli, P. H. S. Torr, and M. P. Kumar,\n                      Efficient continuous relaxations for dense CRF\n                      , in Proceedings of ECCV, 2016.","DOI":"10.1007\/978-3-319-46475-6_50"},{"key":"atypb11","unstructured":"M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman,\n                      The PASCAL Visual Object Classes Challenge $2010$ (VOC$2010$) Results\n                      ,http:\/\/www.pascal-network.org\/challenges\/VOC\/voc2010\/workshop\/index.html."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030109"},{"key":"atypb13","unstructured":"J. L. Kelley,\n                      General Topology\n                      , Grad. Texts in Math. 27, Springer, New York, 1975."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585268"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"P. Kohli, P. Kumar, and P. Torr,\n                      P$3$ & beyond: Solving energies with higher order cliques\n                      , in Proceedings of CVPR, 2007.","DOI":"10.1109\/CVPR.2007.383204"},{"key":"atypb16","unstructured":"P. Kohli, T. Minka, and J. Winn,\n                      MSRC Dataset\n                      ,https:\/\/www.microsoft.com\/en-us\/research\/project\/image-understanding(2017)."},{"key":"atypb17","unstructured":"D. Koller and N. Friedman,\n                      Probabilistic Graphical Models: Principles and Techniques\n                      , MIT Press, Cambridge, UK, 2009."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.1262177"},{"key":"atypb19","unstructured":"P. Kr\u00e4henb\u00fchl and V. Koltun,\n                      Efficient inference in fully connected CRFs with gaussian edge potentials\n                      , in Proceedings of NIPS, 2011."},{"key":"atypb20","unstructured":"P. Kr\u00e4henb\u00fchl and V. Koltun,\n                      Parameter learning and convergent inference for dense random fields\n                      , in Proceedings of ICML, 2013."},{"key":"atypb21","first-page":"71","volume":"10","author":"Kumar M. P.","year":"2008","journal-title":"J. Mach. Learn. Res."},{"key":"atypb22","unstructured":"S. Lacoste-Julien,\n                      Convergence Rate of Frank-Wolfe for Non-Convex Objectives\n                      ,arXiv:1607.00345, 2016."},{"key":"atypb23","unstructured":"S. Lacoste-Julien, M. Jaggi, M. Schmidt, and P. Pletscher,\n                      Block-coordinate Frank-Wolfe optimization for structural SVMs\n                      , in Proceedings of ICML, 2012."},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"L. Ladicky, C. Russell, P. Kohli, and P. Torr,\n                      Graph cut based inference with co-occurrence statistics\n                      , in Proceedings of ECCV, 2010.","DOI":"10.1007\/978-3-642-15555-0_18"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"L. Ladicky, C. Russell, P. Kohli, and P. H. S. Torr,\n                      Associative hierarchical CRFs for object class image segmentation\n                      , in Proceedings of IEEE 12th Conference on Computer Vision, 2009, pp. 739-746.","DOI":"10.1109\/ICCV.2009.5459248"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"J. Long, E. Shelhamer, and T. Darrell,\n                      Fully convolutional networks for semantic segmentation\n                      , in Proceedings of CVPR, 2015.","DOI":"10.1109\/CVPR.2015.7298965"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1561\/2400000003"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"P. Ravikumar and J. Lafferty,\n                      Quadratic programming relaxations for metric labeling and Markov random field map estimation\n                      , in Proceedings of ICML, 2006.","DOI":"10.1145\/1143844.1143937"},{"key":"atypb29","unstructured":"A. Schwing and R. Urtasun,\n                      Fully Connected Deep Structured Networks\n                      ,arXiv:1503.0235, 2015."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-007-0109-1"},{"key":"atypb31","unstructured":"J. Snoek, H. Larochelle, and R. Adams,\n                      Practical bayesian optimization of machine learning algorithms\n                      , in Proceedings of NIPS, 2012."},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"M. Tappen, C. Liu, E. Adelson, and W. Freeman,\n                      Learning gaussian conditional random fields for low-level vision\n                      , in Proceedings of CVPR, 2007.","DOI":"10.1109\/CVPR.2007.382979"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1055"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"V. Vineet, J. Warrell, and P. H. S. Torr,\n                      Filter-based mean-field inference for random fields with higher-order terms and product label-spaces\n                      , in Computer Vision: ECCV 2012, Lecture Notes in Comput. Sci. 7576, Springer, New York, pp. 31-44.","DOI":"10.1007\/978-3-642-33715-4_3"},{"key":"atypb35","unstructured":"P. Wang, C. Shen, and A. van den Hengel,\n                      Efficient SDP inference for fully-connected CRFs based on low-rank decomposition\n                      , in Proceedings of CVPR, 2015."},{"key":"atypb37","unstructured":"Y. Zhang and T. Chen,\n                      Efficient inference for fully-connected CRFs with stationarity\n                      , in Proceedings of CVPR, 2012."},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"S. Zheng, S. Jayasumana, B. Romera-Paredes, V. Vineet, Z. Su, D. Du, C. Huang, and P. Torr,\n                      Conditional random fields as recurrent neural networks\n                      , in Proceedings of ICCV, 2015.","DOI":"10.1109\/ICCV.2015.179"}],"container-title":["SIAM Journal on Imaging Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1178104","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:16:23Z","timestamp":1787321783000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1178104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/18M1178104"],"URL":"https:\/\/doi.org\/10.1137\/18m1178104","relation":{},"ISSN":["1936-4954"],"issn-type":[{"value":"1936-4954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}