Efficient Linear Programming for Dense CRFs
Efficient Linear Programming for Dense CRFs
复制标题
DOI：
10.1109/cvpr.2017.313
复制
发表时间：
2016-11
期刊：
影响因子：
--
通讯作者：
Thalaiyasingam Ajanthan;Alban Desmaison;Rudy Bunel;M. Salzmann;Philip H. S. Torr;M. P. Kumar
中科院分区：
文献类型：
--
作者：
Thalaiyasingam Ajanthan;Alban Desmaison;Rudy Bunel;M. Salzmann;Philip H. S. Torr;M. P. Kumar
具有高斯对偶电位的全连通条件随机场（CRF）已被证明是一种广泛而有效的多类语义分割方法。虽然可以使用线性规划（LP）松弛精确地最小化密集CRF的能量，但最先进的算法速度太慢，无法在实践中使用。为了缓解这一缺陷，我们引入了一种高效的密集CRFs LP最小化算法。为此，我们开发了一个近端最小化框架，其中每个近端问题的对偶通过块坐标下降进行优化。我们证明了每个变量块都可以有效地优化。具体来说，对于一个块，问题分解为更小的子问题，每个子问题都在单个像素上定义。对于另一个块，通过条件梯度下降对问题进行优化。这有两个优点：1)条件梯度可以在像素和标签的数量上按时间线性计算，2)最优步长可以解析计算。我们在标准数据集上的实验提供了令人信服的证据，证明我们的方法优于所有现有的基线，包括先前基于LP的密集crf方法。
The fully connected conditional random field (CRF) with Gaussian pairwise potentials has proven popular and effective for multi-class semantic segmentation. While the energy of a dense CRF can be minimized accurately using a linear programming (LP) relaxation, the state-of-the-art algorithm is too slow to be useful in practice. To alleviate this deficiency, we introduce an efficient LP minimization algorithm for dense CRFs. To this end, we develop a proximal minimization framework, where the dual of each proximal problem is optimized via block coordinate descent. We show that each block of variables can be efficiently optimized. Specifically, for one block, the problem decomposes into significantly smaller subproblems, each of which is defined over a single pixel. For the other block, the problem is optimized via conditional gradient descent. This has two advantages: 1) the conditional gradient can be computed in a time linear in the number of pixels and labels, and 2) the optimal step size can be computed analytically. Our experiments on standard datasets provide compelling evidence that our approach outperforms all existing baselines including the previous LP based approach for dense CRFs.