1

1. 算法原理

1.1. 基本原理

  • 输入:$n$对控制点对$(\pmb p_i,\pmb q_i)$,$i=1,2,\cdots,n$,其中$\pmb p_i\in\mathbb R^2$为控制起始点,$\pmb q_i\in\mathbb{R}^2$为控制目标点
  • 目标:找到一个映射$f:\mathbb R^2\rightarrow \mathbb{R}^2$,满足$f(\pmb p_i)=\pmb q_i$,$i=1,2,\cdots,n$

1.2. Inverse distance-weighted interpolation methods(IDW)[1]

IDW 算法基本原理是根据给定的控制点对和控制点对的位移矢量,计算控制点对周围像素的反距离加权权重影响,实现图像每一个像素点的位移。

选择$n$对控制点对$(\pmb p_i,\pmb q_i)$,$i=1,2,\cdots,n$,目标映射$f:\mathbb R^2\rightarrow \mathbb{R}^2$可表示成

以下形式:
$$
f(\pmb p)=\sum_{i=1}^n\omega_i(\pmb p)f_i(\pmb p)
$$
其中,权重$\omega_i(\pmb p)$满足:
$$
w_i(\pmb p)=\frac{\sigma_i(\pmb p)}{\sum_{j=1}^n\sigma_j(\pmb p)}
$$
$\sigma_i(\pmb p)$反映第$i$对控制点对像素$\pmb p$得反距离加权权重影响程度,可以直接取:
$$
\sigma_i(\pmb p)=\frac{1}{|\pmb p-\pmb p_i|^\mu}
$$
其中$\mu>1$,也可以取locally bounded weight:
$$
\sigma_i(\pmb p)=\left[\frac{R_i-d(\pmb p,\pmb p_i)}{R_id(\pmb p,\pmb p_i)}\right]^\mu
$$
$f_i$为线性函数,满足:
$$
f_i(\pmb p)=\pmb q_i+\pmb T_i(\pmb p-\pmb p_i)
$$
其中$\pmb T_i$为二阶矩阵:
$$
\pmb T_i=\begin{bmatrix}
t_{11}^{(i)}&t_{12}^{(i)}\\
t_{21}^{(i)}&t_{22}^{(i)}
\end{bmatrix}
$$
矩阵$\pmb T$得确定,可以通过求解如下最优化问题:
$$
\arg\min_{\pmb T_i} E(\pmb T_i)=\sum_{j=1,j\neq i}^n\sigma_i(\pmb p_j)|\pmb q_j-f_i(\pmb p_j)|^2
$$
上式对$\pmb T_i$求导,令方程为0得:
$$
\pmb T_i\sum_{j=1,j\neq i}\sigma_i(\pmb p_j)\pmb p\pmb p^T=\sum_{j=1,j\neq i}\sigma_i(\pmb p_j)\pmb q\pmb p^T
$$
其中$\pmb p=\pmb p_j-\pmb p_i$,$\pmb q=\pmb q_j-\pmb q_i$

又$\sigma_i(\pmb p_j)\pmb p\pmb p^T$非奇异,因此可以直接解出$\pmb T_i$的值:
$$
\pmb T_i=\left(\sum_{j=1,j\neq i}\sigma_i(\pmb p_j)\pmb q\pmb p^T\right)\left(\sum_{j=1,j\neq i}\sigma_i(\pmb p_j)\pmb p\pmb p^T\right)^{-1}
$$
求出$\pmb T_i(i=1,\cdots,n)$后,映射$f$也就相应确定

1.3. Radial basis functions interpolation method(RBF)[2]

选择$n$对控制点对$(\pmb p_i,\pmb q_i)$,$i=1,2,\cdots,n$,目标映射$f:\mathbb R^2\rightarrow \mathbb{R}^2$可表示为以下形式:
$$
f(\pmb p)=\sum_{i=1}^n\alpha_ig_i(|\pmb p-\pmb p_i|)+\pmb{Ap}+\pmb B
$$
其中,$g_i$为径向基函数,通常可以取Hardy multiquadrics:$g(t)=(t^2+c^2)^{\pm \frac{1}{2}}$或高斯函数$g_\sigma(t)=e^{-t^2/\sigma^2}$,

为了计算方便,这里取Hardy multiquadrics:
$$
\begin{aligned}
g_i(d)&=(d+r_i)^{\pm\frac{1}{2}}\
r_i&=\min_{j\neq i}d(\pmb p_i,\pmb p_j)
\end{aligned}
$$
对于线性部分分量$\pmb {Ap}+\pmb B$,本例简单地取$\pmb A=\pmb I$和$\pmb B=\pmb 0$

2. 实验结果

2.1. 标准图像测试

如下图所示,固定四角,蓝色为控制起始点,绿色为控制终止。

tag

2.2. IDW算法

$\mu$取值 修复前 修复后
$\mu=-1$ IDW_mu=-1_nofix IDW_mu=-1_fix
$\mu=-2$ IDW_mu=-2_nofix IDW_mu=-2_fix

2.3. RBF算法

$\mu$取值 修复前 修复后
$\mu=-0.5$ RBF_mu=-0_5_nofix RBF_mu=-0_5_fix
$\mu=0.5$ RBF_mu=0_5_nofix RBF_mu=0_5_fix

2.4. 相关应用

2.4.1. 柴犬表情包

原图像:

dog

开心:

dog1

Emmm……:

dog2

2.4.2. 藏狐的笑容

原图像:

zanhu

处理后:

result

参考文献

[1] D. Ruprecht and H. Muller. Image warping with scattered data interpolation. IEEE Computer Graphics and Applications, 15(2):37–43, 1995. 10

[2] N. Arad and D. Reisfeld. Image warping using few anchor points and radial functions. In Computer graphics forum, volume 14, pages 35–46. Wiley Online Library, 1995.