Information Flow Matting
来除草了，最近都在做一些杂事，就记一篇最近复现论文的工作和一些思考吧。其实是实验报告……最近没太多时间用于记录，需要学习的内容实在太多了，等有一定积累的时候再来吧！不然记录的东西都是错误的也没什么价值。
实验目的
复现 Aksoy 等人在论文《Designing Effective Inter-Pixel Information Flow for Natural Image Matting》中提出的基于传播的抠图算法。
实验原理
基于传播的抠图方法依据像素之间颜色和空间的相近性，将透明度从已知区域传播到未知区域。基于传播的抠图方法有局部和非局部两种。局部方法为每个未知点设置一个以它为中心的窗口，信息只通过该点对应的窗口中的点传播。非局部方法则通过未知点的颜色和空间信息寻 找几个邻近点，信息通过这几个邻近点传播，不限于局部窗口内。
该论文使用线性表达式将局部方法与非局部方法结合起来，其中局部方法使用了 Close-Form Matting 的算法，非局部方法则由作者设计，由三部分组成:颜色混合信息流、已知区域到未 知区域信息流、未知区域内部信息流。算法流程图如下图所示。其中各个信息流之间主要的差异在于邻近点的搜索空间不同，颜色混合信息流从全图中搜索，已知区域到未知区域信息流只从已知区域中搜索，未知区域内部信息流只从未知区域中搜索。
大致计算流程如下，首先在每个信息流中使用 K 邻近法(KNN)搜索邻近点，其中搜索使用的特征向量如表 1 所示。然后使用局部线形嵌入方法(LLE)求解公式(1)得到权重。最后将每个信息流线性组合成公式(2)，并使用预条件共轭梯度法(PCG)求出透明度。
公式(1)中为点的 RGB 颜色向量，为点通过 KNN 获取的邻近点集合，该公式的作用为计算出点邻近点的权重，这些权重可以使得邻近点加权组合成的颜色与点的颜色相近，从而使用这些权重与邻近点的透明度计算出点的透明度。公式(2)为每个信息流的线性组合，其 中、、、为参数，其取值下表所示，是为了保持三分图中的前景和背景信息不 被影响而附加的公式，如公式(3)所示，其余公式大同小异，不再赘述。
公式(3)中为未知区域的点集，该公式通过邻近点的权重和透明度计算未知点的透明度，之所以计算差值是因为论文中不止使用一种评估透明度的方法，如公式(2)所示，将这些评估的差值线性组合起来，使得总差值最小，从而计算最终的透明度。
| 参数名 | 参数值 |
|---|---|
| 颜色混合信息流的搜索特征 | [𝑟, 𝑔, 𝑏, 𝑥, 𝑦] |
| 已知到未知信息流的搜索特征 | [𝑟, 𝑔, 𝑏, 𝑥 × 10, 𝑦 × 10] |
| 未知内部信息流的搜索特征 | [𝑟, 𝑔, 𝑏, 𝑥/20, y/20] |
| 颜色混合信息流的邻近点个数 | 20 |
| 已知到未知信息流的邻近点个数 | 7 |
| 未知内部信息流的邻近点个数 | 5 |
| 已知到未知信息流的混合系数 | 0.05 |
| 未知内部信息流的混合系数 | 0.01 |
| 局部信息流的混合系数 | 1 |
| 保持三分图已知信息的混合系数 | 100 |
实验步骤
1、寻找算法库 由于该论文使用了很多已有的算法，且并没做详细说明，故在复现的开始先寻找提供了这些算法的第三方库。其中 KNN 算法使用了 SKLERAN 库中的 neighbors 模块，LLE 算法使用了 NUMPY 库中的 Linear Algebra Tools 模块，PCG 使用了 SCIPY 库中的 sparse 模块，局部信息流使用了一个开源的 Close-Form Matting 中的方法。
2、实现非局部方法中的邻近点搜索功能 由于 KNN 算法使用的是第三方库，所以该功能实现起来很简单。输入搜索区域和被搜索区域，用 KNN 算法搜索出邻近点即可。这里要注意的是 KNN 搜索的时候如果搜索区域和被搜索区域有重叠，那么最近的点一定是自身，需要将自身的点排除。
3、实现计算权重的方法 直接使用第三方的 LLE 算法计算公式(1)即可。
4、实现各个信息流 整个算法由四个信息流和最终的求解组成，其中三个非局部信息流的实现过程相似。首先读取图片和三分图的信息、加载算法需要的参数，然后通过三分图计算出背景区域、前景区域和未知区域，将这些区域和对应的参数交给邻近点搜索算法计算出临近点，最后通过计算权重的算法计算出每个信息流的权重即可。其中未知区域内部信息流的权重不是通过公式(1)计算 的，而是论文中的另一个简单公式，不需要使用 LLE 算法。其中局部信息流直接使用了开源的 Close-Form Matting 算法。
5、实现透明度的求解 将所有信息流求得的权重按照公式(2)组合起来，使用第三方库的 PCG 算法进行求解。
实验结果与分析
1、分步结果
分步结果的示意图如下图所示，其中(a)为执行颜色混合信息流的结果，(b)为接着执行已知区域到未知区域信息流的结果，(c)为接着执行未知点内部信息流的结果，(d)为接着执行局部信息流的结果。其中蓝色框和黄色框的区域分别为结果局部放大的图像。
通过该结果可以看出，颜色混合信息流可以基本获取到未知点的透明度，该结果可以保留大量的孔洞特征，图(a)的黄色框中叶子缝隙保留完整。但是距离背景近的未知点可能整块都被错误判断为背景，图(a)的蓝色框中许多叶子全都被判断为背景，这是由于这些叶子内 部颜色相近，颜色混合信息流的邻近点可能全取自未知点，导致这些叶子判断错误。
已知区域到未知区域信息流的结果弥补了颜色混合信息流的缺陷，由于邻近点都是从已知区域中选取的，所以图(b)的蓝色框中的叶子被正确判断为前景。但由于该信息流的空间约束很大，造成前景内部的孔洞特征消失，从图(b)的黄色框中可以看出，原本叶子间的缝隙 完全消失了。
未知区域内部信息流由于空间约束条件小，可以从很远的地方寻找颜色相近的邻近点，从而弥 补已知区域到未知区域信息流照成孔洞特征消失的缺陷，从图 2(c)的黄色框中可以看出，叶子间的缝隙被复原了一些。但是边缘的噪声也随之增加了，图 2(c)的蓝色框中叶子边缘 的噪声更多了。所以未知区域内部信息流并不一定可以使结果变得更好，要做取舍。
局部信息流由于是在局部窗口中传播，所以可以使得最终结果变得更加平滑。
2、运行时间
运行时间如下图所示，其中 Python 为本实验复现的结果，MATLAB 为作者提供源码的结果。
从图中可以看出复现结果与作者提供的结果相差无几。除了 net 的测试集以外均可在 50s 左右得出 结果，与论文中描述一致。
3、与作者提供源码结果的差异
由于论文中没有三分图预处理的具体方法，故只将未作预处理的结果进行比较。两种之间没有肉眼可见的区别，但是还是有部分像素差，主要原因是因为 PCG 算法的差异导致的，目前没有 找到计算结果和 MATLAB 完全一致的 Python 替代算法。但是其结果在 alphamatting.com 上测试并没有明显差别，其中 MSE 的差别如下图所示。
在对比实验时也将每一步算出来的权重进行了比较，没有差异，故本实验已经将论文中所提到 的算法流程进行了复现。
4、与原文结果的差异
作者提供的源码与论文中的结果存在一定差距，但作者强调该源码为论文的复现版本，不提供论文的原始代码，可以依照该复现版本进行对比实验和改进。故将两者进行了简单的比较，如下图所示，其中(a)为实验结果、(b)为论文结果、(c)修改参数的结果。通过对比实验结果与论文结果可以发现，论文结果保留了更多孔洞的信息，如图黄色框。在实验分步运行阶段可知，保留孔洞信息主要通过颜色混合信息流和未知区域内部信息流完成。故将对应过程 的系数增加，得到图(c)的结果。从结果可以发现，黄框部分的孔洞细节更接近论文结 果，但是蓝色框部分的噪声也随之增加，这部分在上文也论述过原因。
并非所有情况都可以通过增加未知区域信息流的权重使结果变好，如下图展示的是其中一个测试样本，图中黑色部分表示实验结果和原文结果的差异部分，图(a)为实验结果，(b)为修改参数的结果。
由于该样本的前景为一个菠萝，没有孔洞信息，这样未知区域信息流的操作使得周围噪声变多的坏处要远大于解决孔洞问题所带来的好处。故尝试降低未知区域信息流的权重，得到图(b)的结果，从结果可以发现，周围的噪声明显变少了。
所以我认为论文中的结果可能根据样本的不同调节了参数，选择了每个样本最好的结果放到测 试集上进行测试。或者是作者隐藏了可以判断是否存在大量孔洞或其他情况的方法，可以自动调节参数。
