FMM影像修复方法

数学描述

$\hspace{1cm}$以上为FMM方法的示意图，图中$p$为待修复的点，$\delta\Omega$为待修复区域的边界$\Omega$为待修复的区域，对于一个待修复点$p$周围的的邻域小区域$B_\epsilon(p)$，区域大小为$\epsilon$，如Figure2图（a）所示，则未知点$p$的像素值应该由已知的区域$B_\epsilon(p)$得到，首先考虑灰度影像，彩色影像是灰度影像的扩展。如果区域$\epsilon$足够小的话，我们认为使用一个一阶导的近似可以进行修复，进行修复的公式为：
$$I_{q}(p)=I(q)+\Delta I(q)(p-q)\,.(1)$$
$\hspace{1cm}$上述公式表明在位置$p$的校正结果与$q$点位置和$q$点位置和$p$点位置距离差值的一阶近似，也就是$q$点的1阶近似（在区域比较小的时候比较适用）。接下来我们修复$p$点实用区域$B_\epsilon(p)$内所有像素进行处理，对每一个像素都有一个权值，则$p$的修复后的像素值为：
$$I(p)=\frac{\Sigma_{q\in{B_\epsilon(p)}}\omega(p,q)[I(q)+\Delta I()q(p-q)]}{\Sigma_{q\in{B_\epsilon(p)}}\omega(p,q)}\,.(2)$$
其中$\omega(p,q)$为权函数，权函数的设计既要考虑到$p$点信息的传递也要考虑到在$B_\epsilon(p)$区域影像的细节。

FMM影像修复

$\hspace{1cm}$上一章节描述了影像修复的基本原理和数学基础，则对整个区域的$\Omega$的修复方法为，对处于$\delta\Omega$边界上的点根据公式（2）进行修复，然后进行迭代，直到整个区域都修复完成，在这里有一个修复顺序的问题，在处理过程中使用待修复边界点与原始边界点的距离进行判断，距离原始边界越越近的点首先进行修复，这是因为距离边界越近的点修复的可靠性越大。对于上述操作可以采用FMM方法进行处理，简单的说FMM方法就是求解 $Eikonal$方程1

$$|\Delta T|=1\hspace{1cm}on \hspace{3pt}\Omega,\hspace{1cm}with\,T=0\,on\,\delta\Omega\,.(3)$$
其中方程（3）中对$T$的求解就是$\Omega$中像素距离初始边界$\delta\Omega$的距离，整个求解过程的伪代码为：

$\delta\Omega_i\,$=boundary of region to inpaint
$\delta\Omega\,$= $\,\delta\Omega_i$
while($\delta\Omega\,$not empty)
{
$p\,$=$\,$pixel of $\delta\Omega\,$closest to $\delta\Omega_i\,$
inpaint $\,p$ using Eqn (2)
advance $\delta\Omega\,$into $\Omega$
}

FMM方法的主要优势在于此方法明确平衡了区分已知和未知区域窄带，确定了下一个需要进行修复的像素，这里的像素窄带表示的就是我们的边界$\delta\Omega$，则对于每一个像素除了储存像素的灰度值之外还储存一个标志变量，这个标志变量包含三个值

• BAND：像素值属于窄带，其值经过更新。
• KNOWN：在边界$\delta\Omega$之外的点，也就是在已知区域的点，其T和灰度值I是已知的。
• INSIDE：在边界的像素值点，在边界区域中，T和I的值目前是未知的。

则FMM算法的初始值和传播相位如下：首先设置T在边界$\delta\Omega$上或边界外值为0，在待修复边界内设置极大值，对所有的影像都按上述条件设置初始值

while (NarrowBand not empty)
{
extract P(i,j) = head(NarrowBand); /* STEP 1 */
f(i,j) = KNOWN;
for (k,l) in (i1,j),(i,j1),(i+1,j),(i,j+1)
if (f(k,l)!=KNOWN)
{
if (f(k,l)==INSIDE)
{
f(k,l)=BAND; /* STEP 2 */
inpaint(k,l); /* STEP 3 */
}
T (k,l) = min(solve(k1,l,k,l1), /* STEP 4 */
solve(k+1,l,k,l1),
solve(k1,l,k,l+1),
solve(k+1,l,k,l+1));
insert(k,l) in NarrowBand; /* STEP 5 */
}
float solve(int i1,int j1,int i2,int j2)
{
float sol = 1.0e6;
if (f(i1,j1)==KNOWN)
if (f(i2,j2)==KNOWN)
{
float r = sqrt(2(T(i1,j1)T(i2,j2))*(T(i1,j1)T(i2,j2)));
float s = (T(i1,j1)+T(i2,j2)r)/2;
if (s>=T(i1,j1) && s>=T(i2,j2)) sol = s;
else
{ s += r; if (s>=T(i1,j1) && s>=T(i2,j2)) sol = s; }
}
else sol = 1+T(i1,j1));
else if (f(i2,j2)==KNOWN) sol = 1+T(i1,j2));
return sol;
}

对于单个像素的修复伪代码如下：

void inpaint(int i,int j)
{
for (all (k,l) in Bε(i,j) such that f(k,l)!=OUTSIDE)
{
r = vector from (i,j) to (k,l);
dir = r * gradT(i,j)/length(r);
dst = 1/(length(r)*length(r));
lev = 1/(1+fabs(T(k,l)T(i,j)));
w = dir*dst*lev;
if (f(k+1,l)!=OUTSIDE && f(k1,l)!=OUTSIDE &&
f(k,l+1)!=OUTSIDE && f(k,l1)!=OUTSIDE)
gradI = (I(k+1,l)I(k1,l),I(k,l+1)I(k,l1));
Ia += w * (I(k,l) + gradI * r);
s += w;
}
I(i,j) = Ia/s;
}

FMM算法细节

首先使用FMM方法计算初始待修复边界外的区域，获取待修复边界外部距离。由于我们只需要距离边界点小于$\epsilon$的点，因此只在边界外小于$\epsilon$的区域内计算T，这样我们就提高了计算速度，另外我们对边界内的点运行FMM进行处理，因此，整个影像上的T可以表现为：
$$\begin{equation} T(p)= \left\{ \begin{array}{lr} &T_{in}(p)\, & if \,p\in\Omega \\ -&T_{out(p)}\,&if\,p\not\in\Omega\, \end{array} \right. \,.(5) \end{equation}$$
然后通过$3\times 3$滤波算子进行滤波，然后计算$\Delta T$通过中心差分。

以上为文修复的效果，从上图可以看出，与BSCB方法相比，文章提出的方法在细节上表现并没有比BSCB方法好，但是文章的方法处理效率要远高于BSCB方法2。

局限性

对于以上采用微分校正的方法只能校正比较小的，或者线性的缺失区域，缺失范围较大的区域，校正方法会造成过度平滑，并不能很好进行处理，因此对于比较大的缺失需要进一步处理，但是采用微分校正的方法可疑获取校正趋势3。