笔记-A-Close-Form-Solution-to-Natural-Image-Matting

A Closed Form Solution to Natural Image Matting – 笔记

2020-7-17

# 完整计算流程

对于灰度图，每个像素的值满足:

I_i=\alpha_iF_i+(1-\alpha_i)B_i

转换一下可以得到：

\alpha_i=\frac{1}{F_i-B_i}I_i+\left(-\frac{B_i}{F_i-B_i}\right)

$F$ $B$ $\alpha_i \approx aI_i+b,\quad \forall i\in w$ $i$ $w$ $3\times3$ ）。

所以有能量函数：

J(\alpha,a,b)=\sum_{j\in I}\left(\sum_{i\in w_j}(\alpha_i-a_jI_i-b_j)^2+\epsilon a_j^2\right)

它可以写成矩阵的形式：

J(\alpha,a,b)=\sum_{j\in I} \left \| \left[\begin{matrix} I_i^j & 1\\ I_2^j & 1\\ \vdots & \vdots\\ I_w^j & 1\\ \sqrt{\epsilon} & 0\\ \end{matrix}\right] \left[\begin{matrix} a_j\\\\ b_j \end{matrix}\right] - \left[\begin{matrix} \alpha_1^j\\ \alpha_2^j\\ \vdots\\ \alpha_w^j\\ 0\\ \end{matrix}\right] \right \|^2 \text{（其中$j$代表第$j$个像素，$w$为第$j$个像素所属窗口内的像素个数）}

$G_k=\begin{bmatrix} I_i^k & 1\\ I_2^k & 1\\ \vdots & \vdots\\ I_w^k & 1\\ \sqrt{\epsilon} & 0 \end{bmatrix}$ $\bar{\alpha_k}=\begin{bmatrix} \alpha_1^k\\ \alpha_2^k\\ \vdots\\ \alpha_w^k\\ 0 \end{bmatrix}$ ，则上式写成：

J(\alpha,a,b)=\sum_{k} \left \| G_k \left[\begin{matrix} a_j\\ b_j \end{matrix}\right] - \bar{\alpha_k} \right \|^2 \text{（其中$k$即为上式中的$j$）}

$\alpha$ $\begin{bmatrix} a_k^*\\ b_k^* \end{bmatrix}={\rm argmin} \left \| G_k \begin{bmatrix} a_k\\ b_k \end{bmatrix} - \bar{\alpha_k} \right \|^2$ $A=G_k$ $B=\bar{\alpha_k}$ $X=\begin{bmatrix} a_k\\b_k \end{bmatrix}$ $X^*={\rm argmin}\left \| AX-B \right \|^2$ 。

其中：

\begin{aligned} \left \| AX-B \right \|^2 & =(AX-B)^T(AX-B)\\ & =(X^T A^T - B^T)(AX-B)\\ &=X^TA^TAX-B^TAX-X^TA^B+B^TB\\ & =X^TA^TAX-2X^TA^TB+B^TB\\ \end{aligned}

$\left \| AX-B \right \|^2$ 的梯度，令其梯度为0得最优解：

\begin{aligned}<br> & \nabla \left \| AX-B \right \|^2 =2A^TAX-2A^TB=0\\<br> & \Rightarrow A^TAX =A^TB\\<br> & \Rightarrow X =(A^TA)^{-1}A^TB\\<br> \end{aligned}

$\begin{bmatrix} a_k^*\\ b_k^*\\ \end{bmatrix}=(G_k^TG_k)^{-1}G_k^T\bar{\alpha_k}$ $J(\alpha,a,b)$ 中得到:

\begin{aligned} J(\alpha) & =\sum_k \left \| G_k(G_k^TG_k)^{-1}G_k^T\bar{\alpha}_k-\bar{\alpha}_k \right \|^2\\ & = \sum_k \left \| (I-G_k(G_k^TG_k)^{-1}G_k^T) \bar{\alpha_k} \right \|^2 \end{aligned}

$\bar{G_k}=I-G_k(G_k^TG_k)^{-1}G_k^T$ $I$ 代表单位矩阵），则：

\begin{aligned} J(\alpha) & =\sum_k \left \| \bar{G_k}\bar{\alpha_k} \right \|^2\\ & =\sum_k (\bar{G_k}\bar{\alpha_k})^T\bar{G_k}\bar{\alpha_k}\\ & =\sum_k(\bar{\alpha_k^T}\bar{G_k^T}\bar{G_k}\bar{\alpha_k}) \end{aligned}

$J(\alpha)$ 写成：

J(\alpha)=\alpha^TL\alpha

$\bar{G_k^T}\bar{G_k}$ $L$ $i,j$ $L$ ）

$\alpha$ $J(\alpha)$ 的值最小：

\begin{aligned} & \nabla{\alpha^TL\alpha}=2L\alpha=0\\ & \Rightarrow L\alpha=0\\ \end{aligned}

$\alpha$ 有很多，所以需要给它加上额外的约束：scribbles：

\begin{aligned} & \min_\alpha J(\alpha)=\alpha^TL\alpha\\ s.t. \quad & (\alpha-S)^TD_c(\alpha-S)=0 \end{aligned}

$S$ $N\times1$ $D_c$ $N\times N$ $N$ 个值，属于scribbles的位置为1，矩阵其余位置都为0。）

$\lambda$ ，最终求解的能量函数为：

\begin{aligned} J(\alpha) & = \alpha^TL\alpha+\lambda (\alpha^T-S^T)D_c(\alpha-S)\\ & =\alpha^TL\alpha+\lambda(\alpha^TD_c\alpha-S^TD_c\alpha-\alpha^TD_cS+S^TD_cS)\\ \end{aligned}

求该能量函数的梯度：

\begin{aligned} \nabla J(\alpha) & = 2L\alpha+\lambda(2D_c\alpha-2D_cS+S^TD_cS)\\ & = (L+\lambda D_c)2\alpha-2\lambda D_cS \end{aligned}

$\alpha$

\begin{aligned} & \nabla J(\alpha)=0\\ & \Rightarrow (L+\lambda D_c)2\alpha-2\lambda D_cS=0\\ & \Rightarrow (L+\lambda D_c)\alpha-\lambda D_cS=0\\ & \Rightarrow (L+\lambda D_c)\alpha=\lambda D_cS\\ & \Rightarrow \alpha=(L+\lambda D_c)^{-1}\lambda D_cS \end{aligned}

$\alpha$ $\alpha^*=(L+\lambda D_c)^{-1}\lambda D_cS$

$(L+\lambda D_c)\alpha=\lambda D_cS$ $\alpha$ 的解

$L$ $i,j$ 项

$\bar{G_k^T}\bar{G_k}$ $i,j$ $\bar{G_k}=I-G_k(G_k^TG_k)^{-1}G_k^T$ $k$ $k$ $I$ $\alpha$ $k$ 个窗口。

G_k=\begin{bmatrix} I_1 & 1\\ I_2 & 1\\ \vdots & \vdots\\ I_w & 1\\ \sqrt{\epsilon} & 0 \end{bmatrix} \quad G_k^T=\begin{bmatrix} I_1 & I_2 & \cdots & I_w & \sqrt{\epsilon}\\ 1 & 1 & \cdots & 1 & 0 \end{bmatrix}

\begin{aligned} G_k^TG_k & =\begin{bmatrix} I_1 & I_2 & \cdots & I_w & \sqrt{\epsilon}\\ 1 & 1 & \cdots & 1 & 0 \end{bmatrix} \begin{bmatrix} I_1 & 1\\ I_2 & 1\\ \vdots & \vdots\\ I_w & 1\\ \sqrt{\epsilon} & 0 \end{bmatrix}\\ & = \begin{bmatrix} \sum\limits_{i=0}^w I^2+\epsilon & \sum\limits_{i=0}^w I_i\\ \sum\limits_{i=0}^w I_i & w \end{bmatrix} \end{aligned}

已知：

\begin{aligned} \left \{ \begin{aligned} \mu & =\frac{1}{w}\sum\limits_{i=0}^wI_i\\ \sigma^2 & =\frac{1}{w}\sum\limits_{i=0}^w(I_i-\mu)^2 \end{aligned}\right. \quad \Rightarrow \left \{ \begin{aligned} \sum\limits_{i=0}^wI_i & =\mu w\\ \sum\limits_{i=0}^wI_i^2 & =w\sigma^2+w\mu^2 \end{aligned}\right. \end{aligned}

$G_k^TG_k$ 可写成：

G_k^TG_k=\begin{bmatrix} w\sigma^2+w\mu^2+\epsilon & \mu w\\ \mu w & w \end{bmatrix}

$G_k^TG_k$ 的逆：

\begin{aligned} (G_k^TG_k)^{-1} &=\frac{1}{w(w\sigma^2+w\mu^2+\epsilon)-\mu^2w^2} \begin{bmatrix} w & -\mu w\\ -\mu w & w\sigma^2+w\mu^2+\epsilon \end{bmatrix}\\ &=\frac{1}{w^2\sigma^2+w\epsilon} \begin{bmatrix} w & -\mu w\\ -\mu w & w\sigma^2+w\mu^2+\epsilon \end{bmatrix}\\ &=\frac{1}{w\sigma^2+\epsilon} \begin{bmatrix} 1 & -\mu\\ -\mu & \sigma^2+\mu^2+\frac{\epsilon}{w} \end{bmatrix} \end{aligned}

$\frac{1}{w\sigma^2+\epsilon}$ $k_1$ $\sigma^2+\mu^2+\frac{\epsilon}{w}$ $k_2$ $(G_k^TG_k)^{-1}=k_1\begin{bmatrix} 1 & -\mu\\ -\mu & k_2\\ \end{bmatrix}$ $G_k(G_k^TG_k)^{-1}$ ：

\begin{aligned} G_k(G_k^TG_k)^{-1} &=k_1\begin{bmatrix} I_1 & 1\\ I_2 & 1\\ \vdots & \vdots\\ I_w & 1\\ \sqrt{\epsilon} & 0 \end{bmatrix} \begin{bmatrix} 1 & -\mu\\ -\mu & k_2 \end{bmatrix}\\ &=k_1\begin{bmatrix} I_1-\mu & -I_1\mu+k_2\\ I_2-\mu & -I_2\mu+k_2\\ \vdots & \vdots\\ I_w-\mu & -I_w\mu+k_2\\ \sqrt{\epsilon} & -\mu\sqrt{\epsilon} \end{bmatrix} \end{aligned}

$G_k(G_k^TG_k)^{-1}G_k^T$ ：

\begin{aligned} G_k(G_k^TG_k)^{-1}G_k^T &=k_1\begin{bmatrix} I_1-\mu & -I_1\mu+k_2\\ I_2-\mu & -I_2\mu+k_2\\ \vdots & \vdots\\ I_w-\mu & -I_w\mu+k_2\\ \sqrt{\epsilon} & -\mu\sqrt{\epsilon} \end{bmatrix} \begin{bmatrix} I_1 & I_2 & \cdots & I_w & \sqrt{\epsilon}\\ 1 & 1& \cdots & 1 & 0 \end{bmatrix}\\ &=k_1\begin{bmatrix} I_1I_1-\mu I_1-\mu I_1+k_2 & I_1I_2-\mu I_2-\mu I_1+k_2 & \cdots & I_1I_w-\mu I_w-\mu I_1+k_2 & \sqrt{\epsilon}I_1-\mu \sqrt{\epsilon}\\ I_2I_1-\mu I_1-\mu I_2+k_2 & I_2I_2-\mu I_2-\mu I_2+k_2 & \cdots & I_2I_w-\mu I_w-\mu I_2+k_2 & \sqrt{\epsilon}I_2-\mu \sqrt{\epsilon}\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ \sqrt{\epsilon}I_1-\mu \sqrt{\epsilon} & \sqrt{\epsilon}I_2-\mu \sqrt{\epsilon} & \cdots & \sqrt{\epsilon}I_w-\mu \sqrt{\epsilon} & \epsilon \end{bmatrix} \end{aligned}

$\bar{G_k}$ $I$ 为单位矩阵）：

\bar{G_k}=I-G_k(G_k^TG_k)^{-1}G_k^T

$\bar{G_k}$ $i,j$ 项为：

\begin{aligned} \bar{G}\_{(i,j)|(i,j)\in k} &= \delta_{ij}-k_1\left(I_iI_j-\mu I_i-\mu I_j+k_2\right)\\ &=\delta_{ij}-\left(I_iI_j-\mu I_i-\mu I_j+\sigma^2+\mu^2+\frac{\epsilon}{w}\right)\frac{1}{w\sigma^2+\epsilon}\\ &=\delta_{ij}-\left(\left(I_i-\mu\right)\left(I_j-\mu\right)+\sigma^2+\frac{\epsilon}{w}\right)\frac{1}{w\sigma^2+\epsilon}\\ &=\delta_{ij}-\left(\left(I_i-\mu\right)\left(I_j-\mu\right)+\frac{w\sigma^2+\epsilon}{w}\right)\frac{1}{w\sigma^2+\epsilon}\\ &=\delta_{ij}-\left(\frac{1}{w\sigma^2+\epsilon}\left(I_i-\mu\right)\left(I_j-\mu\right)+\frac{1}{w}\right)\\ &=\delta_{ij}-\frac{1}{w}\left( 1+\frac{1}{\sigma^2+\frac{\epsilon}{w}}\left(I_i-\mu\right)\left(I_j-\mu\right) \right) \end{aligned}

由23式可得：

\begin{aligned} \bar{G}_k^T\bar{G}_k & =\left(I-G_k(G_k^TG_k)^{-1}G_k^T\right)^T\left(I-G_k(G_k^TG_k)^{-1}G_k^T\right)\\ & =\left(I-G_k\left((G_k^TG_k)^{-1}\right)^TG_k^T\right)\left(I-G_k(G_k^TG_k)^{-1}G_k^T\right)\\ & =I+G_k\left((G_k^TG_k)^{-1}\right)^TG_k^TG_k(G_k^TG_k)^{-1}G_k^T-G_k\left((G_k^TG_k)^{-1}\right)^TG_k^T-G_k(G_k^TG_k)^{-1}G_k^T\\ & =I+G_k\left( (G_k^TG_k)^{-1} \right)^TG_k^T -G_k\left((G_k^TG_k)^{-1}\right)^TG_k^T -G_k(G_k^TG_k)^{-1}G_k^T\\ & =I-G_k(G_k^TG_k)^{-1}G_k^T\\ & =\bar{G}_k \end{aligned}

$\bar{G}_k$ $i,j$ $\bar{G}_k^T\bar{G}_k$ $i,j$ 项}

$i,j$ $i,j\in [0,N]$ $i$ $j$ $k$ $\bar{G}_k^T\bar{G}_k$ $i,j$ $L$ $i,j$ 项。

A Closed Form Solution to Natural Image Matting – 笔记

A Closed Form Solution to Natural Image Matting – 笔记

# 完整计算流程

$L$ $i,j$ 项

# 参考了：

1条评论

留下评论取消回复

A Closed Form Solution to Natural Image Matting – 笔记

# 完整计算流程

# 推导L的第i,j项

# 参考了：

1条评论

留下评论 取消回复

$L$ $i,j$ 项

留下评论取消回复