Spectral Matting论文解读

一、论文简介

文章使用谱分割的方法对图像进行软分割，分割过程既可以自动进行，也可以通过人工交互完成。之前的方法对Matting的定义为：$I_i = \alpha_iF_i+(1-\alpha_i)B_i$Ii​=αi​Fi​+(1−αi​)Bi​, 本文进行了扩展，将Matting问题定义为如下的形式：

$I_i =\sum^K_{k=1}\alpha^k_iF^k_i, for \forall i\sum^K_{k=1}\alpha^k_i=1$Ii​=k=1∑K​αik​Fik​,for∀ik=1∑K​αik​=1

我们看看下面这张示意图：
图中(d)就是指的整个图像分为了8个layer：$F^1,F^2,F^3,F^4,F^5,F^6,F^7,F^8$F1,F2,F3,F4,F5,F6,F7,F8, 每个layer的size跟原图像相同。
图中(e)就是8个$\alpha$α：$\alpha^1,\alpha^2,\alpha^3,\alpha^4,\alpha^5,\alpha^6,\alpha^7,\alpha^8$α1,α2,α3,α4,α5,α6,α7,α8. 同时，每个$\alpha$α的size跟原图像相同。

论文Spectral Matting的核心工作就是：通过 $F$F 得到 $\alpha$α

对于第1个像素的$I_1$I1​：$I_1=\alpha^1_1F^1_1+\alpha^2_1F^2_1+\alpha^3_1F^3_1+\alpha^4_1F^4_1+\alpha^5_1F^5_1+\alpha^6_1F^6_1+\alpha^7_1F^7_1+\alpha^8_1F^8_1$I1​=α11​F11​+α12​F12​+α13​F13​+α14​F14​+α15​F15​+α16​F16​+α17​F17​+α18​F18​

对于第1个像素的$\alpha$α：$\alpha^1_1+\alpha^2_1+\alpha^3_1+\alpha^4_1+\alpha^5_1+\alpha^6_1+\alpha^7_1+\alpha^8_1 =1$α11​+α12​+α13​+α14​+α15​+α16​+α17​+α18​=1

$$(1)Spectral Matting示意图$$

Matting的主要应用是图像合成。有了$\alpha$α，接下来就可以提取前景跟背景，这里我们将上图(d)中的三块红色框起来的部分组合一下即可：$\alpha_F=\alpha^3+\alpha^5+\alpha^7$αF​=α3+α5+α7。我们发现$\alpha_F$αF​其实就是上图（c）的内容，白色部分：纯白色为1，边缘部分半透明介于0-1之间，其余黑色部分就是背景为0。

总结起来，有三个主要问题：
1、Laplace矩阵的谱分割，如何通过谱分割得到(d)图
2、Spectral Matting，如何通过硬分割得到软分割
3、如何提取前景部分

二、图像的谱分割

谱分割是一种图分割的方法，详细可以参考知乎上这篇文章：谱聚类方法推导和对拉普拉斯矩阵的理解。
谱分割得先构建一个对称半正定的Laplacian矩阵，实际上就是相似度矩阵，具体定义为：
$L_{i,j} = \begin{cases} \sum_{q|(i,j)\in w_q}-\frac{1}{|w_q|}(1+(I_i-\mu_q)^T(\Sigma_q+\frac{\epsilon}{|w_q|}I_3)^{-1}(I_j-\mu_q))& i\not=j\\ \sum^n_{j=1}-L_{i,j}& i=j \end{cases}.$Li,j​={∑q∣(i,j)∈wq​​−∣wq​∣1​(1+(Ii​−μq​)T(Σq​+∣wq​∣ϵ​I3​)−1(Ij​−μq​))∑j=1n​−Li,j​​i​=ji=j​.
注意L的每一行之和为0，那么为什么$L$L的特征向量就可以实现硬分割呢？答案都在上面的那边知乎文章中，这里仅仅验证一下。

$(2)图像谱分割示意图$(2)图像谱分割示意图

图（2）(1)中图像由4种颜色显著的分为4块区域，假设不同块之间的相似度为0，可以得到如(2)所示的Laplace矩阵，应该是16*16，这里只画8行。右图为下边Laplace矩阵4个特征值为0的特征向量。 每一列是一个特征向量。可以验证，$Le_1 = Le_2=Le_3=Le_4=0$Le1​=Le2​=Le3​=Le4​=0。

我们发现，0特征值对应的特征向量$e_1,e_2,e_3,e_4$e1​,e2​,e3​,e4​恰好对应4块分割区域。但是实际处理过程中，$L$L矩阵不可能这么完美的在各区域间完美分割，0特征对应的特征向量可能不存在或很少，因此实际过程中我们只需要取出$k$k个最小特征值对应的特征向量即可。

这里有一个概念叫过分割，如果当$k$k取得稍微大一点，就会分割出很多块，甚至语义上属于同一类都会分成很多块，如图（1)(b)中的衣服分为了左边的分红和右边的绿色。接下来就是根据这一步得到的$k$k个layer获取matting component $\alpha$α。

三、Spectral Matting

一个重要的claim如下所示：

意思就是如果满足以上3个性质，那么，$\alpha^1,\alpha^2...\alpha^k$α1,α2...αk位于Laplace矩阵$L$L的零空间。也就是说，$\alpha^1,\alpha^2...\alpha^k$α1,α2...αk可以使用$L$L矩阵0特征值对应的特征向量$e^1,e^2...e^k$e1,e2...ek线性组合得到。当然，这里放宽了限制，不一定是0特征值对应的特征向量，实际用到的是若干个最小特征值对应的特征向量。

接下来的事情，就是最优化如下的能量函数即可
$\sum_{i,k}|\alpha^k_i|^\gamma+|1-\alpha^k_i|^\gamma, where·\alpha^k=Ey^k，subject ·to·\sum_k\alpha^k_i=1$i,k∑​∣αik​∣γ+∣1−αik​∣γ,where⋅αk=Eyk，subject⋅to⋅k∑​αik​=1

四、前景提取

本文提供了两种抽取：1、自动提取前景，2、交互式的提取前景

1.自动提取前景

对于有$k$k个matting component的$\alpha$α，那么它所有可以组合的方式有$2^k$2k种，最暴力的办法就是依次遍历每一种可能的组合，如果$k$k不大的话，依然很快。

那么问题是如何衡量到底哪一种组合好呢？文中提到了两种方法：

(1) 如果只在意低级颜色信息，那么可以使用论文：A closed form solution to natural image matting中提到的方法，使用如下的表达式计算分值，

$J(\alpha) =\alpha^TL\alpha$J(α)=αTLα ，其中，$\alpha=\alpha^{k1}+\alpha^{k2}+...+\alpha^{kn}$α=αk1+αk2+...+αkn，表示前景区域。这里的$\alpha$α可能有$2^k$2k种组合。

(2)为了防止不合理的分割，考虑使用平衡的分割，使得前景和背景约束在一个百分比之内。

2.交互提取前景

没有详细阅读，大致是通过交互制定前景和背景，然后使用最大流最小割的方法快速分割得到前景和背景。

参考文献：

[1] Levin A, Rav-Acha A, Lischinski D. Spectral Matting[J]. 2008, 30(10):1699-1712.
[2] Levin A . A closed form solution to natural image matting[C]// IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2006. IEEE Computer Society, 2006.
[3] 知乎专栏：谱聚类方法推导和对拉普拉斯矩阵的理解
[4] spectral matting的python实现