DILinAV（4）：基于最小割的推理

本文内容主要来自M. Nikos Paragons和M. Pawan Kumar的课程《Discrete Inference & Learning in Artificial Vision》的第4节“Minimum cut based inference”。

Dinits算法

当弧的权值很大时，若选择了不恰当的s-t路径，Ford-Fulkerson算法效率非常低，可能导致“无限迭代”，如上图右所示。如何在余图中选择合适s-t路径，使得算法高效？

Dinits算法与Ford-Fulkerson算法的不同之处仅仅在于：每次从余图中找出最短s-t路径（弧的数目最少的路径），如上图所示。除了这两个算法，还有如下这些最大流算法：

$m$表示弧数，$n$表示顶点数，$U$表示最大弧长。有的算法对多项式时间复杂度或者伪多项式时间复杂度。时间复杂度依赖于所要解决的问题。

计算机视觉是一类特殊的问题，通常是连通度很低的稀疏图，比如网格，弧的数目和顶点数据相近。这类特殊的问题可以用Yuri Boykov和Vladimir Kolmogorov提出的算法[1]解决。

双标签能量函数

利用最小割（最大流）算法，可以求解能量最小化问题。首先从双标签问题入手，随机变量的取值为0或1。

上图的分割任务是从图中分割出白色的牛。蓝色笔刷选取前景，其RGB直方图记为$FG$；红色笔刷选取背景，其RGB直方图记为$BG$。

图像分割问题可以通过CRF解决。每个随机变量对应图中的一个像素。随机变量取值为0或1，标签1表示前景🐂，标签0表示背景。若图有$n$个像素，则共有$2^n$种候选标签组合，分割的任务就是从中找出最佳的标签组合。

在能量函数中，若白色像素视为前景，其对应的一元势（惩罚力度）应当很低，若白色像素视为背景，其对应的一元势应当很高，这种一元势可表示为（$d_a$表示色彩值）：

\begin{equation} \theta_p(0) \propto -\log(BG(d_a)), \quad \theta_p(1) \propto -\log(FG(d_a))。 \end{equation}

两个颜色相近像素的标签应当相同。若相邻两像素色彩差异很大，分配不同的标签惩罚力度小。二元势可表示为：

\begin{equation} \theta_{pq}(i,k) \left\{ \begin{aligned} &\propto \exp(-(d_a-d_b)^2) &&\text{if }i\neq k\\ &= 0 &&\text{if }i = k \end{aligned} \right.。 \end{equation}

基于最小割的能量最小化图像分割算法的思路：

1. 将能量最小化问题转换为最大流问题。能量函数$E$的每个随机变量对应一个顶点（像素），再加上s和t顶点，得到图$D$。
2. 计算图$D$的最小割，得到两个顶点子集$U$和$V\backslash U$，$U$包含顶点s，$V\backslash U$包含顶点t。
3. 两个顶点子集分别对应前景和背景。

次模能量函数（submodular energy function）

如何构造弧及其容量，使得最小割能最小化能量函数？

上图的例子只有唯一变量，改变量取值为0或1，因此存在两个一元势。$A$和$B$分别表示$x_p$的标签为0和1时的一元势。寻找能量最小化的解可转化为求解有向图的最小割。

首先需要增加s和t顶点，如上图右两图所示，问题转化为如何构建弧及其容量，使得求解最小割等价于能量最小化。最小割又可通过最大流求解。任意弧的流量必不小于0，且不大于其容量。因此，弧的容量（长度）必不小于0，这是构造有向图的约束条件。假设$A\geq B$，如上图左所示，将上表分解为下面两个表，其中第二表是常数，无论$x_p$取何值它都对能量最小化无影响。上图中表示$v_p\in V\backslash U$，$v_p$的标签为1；上图右表示$v_p\in U$，$v_p$的标签为0。容易看出，上图中$v_p$的标签为1时，最小割对应着能量最小化，上图右非最小割。上图左表与上图右两图表所表达的一致。

上图表示$A<B$时，最小割等价于能量最小化。

二元势的计算稍复杂。上图中包含两个随机变量$x_p$和$x_q$，它们互为邻居，存在4个二元势（左上表所示）。同样为这4个势构造有向图，先将左上表分解为4个表将简化构造有向图（$B<A$和$D<B$时也有类似做法），然后将表映射到有向图中，第二个表只和$x_q$有关，第三个表只和$x_p$有关，只有第四个表才表示二元势。

$C+B-D-A\geq 0$的假定，表示为相邻像素分配不同标签的势之和不小于分配相同标签的势之和，这称为次模式（submodular）二元势或次模式能量函数。若$C+B-D-A < 0$，需要进行另外的分解吗？事实上，不存在有向图对应于非次模式能量函数¹。因此，用最小割求解能量最小化问题时，通常假定能量函数是次模式的，也就是一元势可以是任意的，但是二元势必须有约束条件（不同标签的势之和不小于相同标签的势之和）。

应用实例

对一元势，已知如何构建有向图，使割对应于能量。对二元势，假设它是次模态的，已知如何构建有向图，使割对应于能量。若能量函数由一元和二元势的和表示，则需要构件一组有向图对应于这些一元和二元势，并将这些图合并起来，得到一个大图，然后再求最大流。利用该算法，可进行图像分割[2]和合成[3]。

上图中，需要分割出上图左中的人，白色的画笔相当于对前景采样，尽量覆盖皮肤、衣服等多种颜色，黑色画笔是对背景采样，得到的结果如山图右所示。

上图展示了两幅图像合成一幅图像，效果自然逼真。对每个像素，标签0或1表示采用图0或1的色彩值，红色线条表示产生割的地方。

多标签能量函数

两图图像分别来自左右两个相机。立体匹配（stereo correspondence），找出两图的像素对应关系。左图像素$(i_p,j_p)$对应与右图像素$(i_p+d_p,j_p)$。，立体匹配中的disparity map。CRF,每个随机变量表示左图的一个像素，标签$L$标示disparity。匹配好的，一元势很小，大。可定义$\theta_p(i)$正比于RGB值的差异。$\theta_{pq}(i,k)=w_{pq}d(i,k),w_{pq}\geq 0$，$d$表示距离函数。$w_{pq}$调节相似度，越相似值越大。

求解这样的问题通常是NP难的，但我们能找到近似解。

Move-Making算法

Expansion算法[4]，

参考资料

1. [1]Y. Boykov and V. Kolmogorov, “An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 26, no. 9, pp. 1124–1137, 2004.
2. [2]Y. Y. Boykov and M.-P. Jolly, “Interactive graph cuts for optimal boundary & region segmentation of objects in ND images,” in Computer Vision, 2001. ICCV 2001. Proceedings. Eighth IEEE International Conference on, 2001, vol. 1, pp. 105–112.
3. [3]V. Kwatra, A. Schödl, I. Essa, G. Turk, and A. Bobick, “Graphcut textures: image and video synthesis using graph cuts,” in ACM Transactions on Graphics (ToG), 2003, vol. 22, no. 3, pp. 277–286.
4. [4]Y. Boykov, O. Veksler, and R. Zabih, “Fast approximate energy minimization via graph cuts,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 23, no. 11, pp. 1222–1239, 2001.