Automating Image Morphing Using Structural Similarity on a Halfway Domain

Introduction

Steps of Morphing

• Determine corresponding feature points in the images
• Define the motion paths followed by these features
• Interpolate a mapping in the space between the features
• Warp the images into alignment
• Blend the warped images to produce an animation

Method

The halfway Parameterization

Problem: Disoccluded region

As to define a map $\phi$ from $I_0$ to $I_1$, one challenge is that each image may contain Disoccluted regions that are not visible in the other image. Within disoccluted regions of $I_0$, map $\phi$ is typically undefined, and aross disocculted regions of $I_1$, it must be discontinuous.

Although one can inroduce a second map from $I_1​$ back to $I_0​$, it is really inefficient and expensive.

Halfway Domain $\Omega$

This paper define a single 2D vector field v over a domain $\Omega$ halfway between the two images and use this field to create two maps:
$$
\phi_0(p)=p-v(p) \quad and \quad \phi_1(p)=p+v(p)
$$
The inter-image map $\phi = \phi_1 \circ \phi_2$

Correspondence Optimization

Energy Function

The paper optimize the gird of vector values $v(p)$ minimizes the following energy function to find the best pixel neighbourhood correspondence.
$$
E = \sum_{p\in \Omega}E(p), \quad with \
E(p) = E_{SIM}(p) + \lambda E_{TPS}(p) + \gamma E_{UI}(p)
$$

$E_{SIM}$: Similarity energy, measure edge structure similarity between corresponding neighborhoods

$E_{TPS}$: Smoothness energy, thin-plate spline(TPS) energy

$E_{UI}$: UI energy

$\lambda=0.001$ and $\gamma=100$ are fixed weights

Similarity energy

For each halfway point $p$,
$$
\begin{gather}
E_{SIM}(p) = -\frac{1}{wh}SIM(N_0, N_1), \quad with\
N_0 = I_0(\phi_0(N(p)) \quad and \quad N_1=I_1(\phi_1(N(p))\
SIM(N_0, N_1) = c(N_0, N_1)\cdot s(N_0, N_1), \quad with \
c(N_0, N_1) = \frac{2\sigma_{N_0}\sigma_{N_1}+C_2}{\sigma_{N_0}^2+\sigma_{N_1}^2+C_2}, \quad and \
s(N_0, N_1) = \frac{|\sigma_{N_0N_1}|+C_3}{\sigma_{N_0N_1}+C_3}
\end{gather}
$$

$wh$: normailization

$\phi_0(N(p)), \phi_1(N(p))$: mappings of a $5\times5$ neighborhood $N(p)$ of $p$.

$C_2=58.5, C_3 = 29.3$ are fixed constants

Smoothness energy

$$
\begin{gather}
E_{TPS}(p)=TPS(v_x(p))+TPS(v_y(p)), \quad where \
TPS(v_x(p))=(\frac{\partial^2v_x(p)}{\partial p_x^2})^2+2(\frac{\partial^2v_x(p)}{\partial p_xp_y})^2+(\frac{\partial^2v_x(p)^2}{\partial p_y^2})
\end{gather}
$$

UI energy

$$
\begin{gather}
E_{UI}(p)=\frac{1}{wh}\sum_{i,j|p_{ij}=p}b(p_{ij},\overline{u_i})|v(p_{ij})-v_{u_i}|^2, \quad where \
\overline{u_i}=(u_i^0+u_i^1)/2 \
v_{u_i}=(u_i^1-u_i^0)/2
\end{gather}
$$

$u_i^0$, $u_i^1$: user-specified pairs of corresponding points in image $I_0$ and $I_1$

Quadratic motion paths

Linear motion paths

For each post p,
$$
q_\alpha = p + (2\alpha-1)v(p), where \ \alpha\in[0,1]
$$

Quadratic motion paths

For each point p
$$
\begin{split}
q_\alpha &= (1-\alpha)((1-\alpha)q_0+\alpha b_{1/2})+\alpha((1-\alpha)b_{1/2}+\alpha q_1) \
&=p+(2\alpha-1)v(p)+4\alpha(1-\alpha)w(p)
\end{split}
$$

$b_{1/2}=p+2w(p)$

Selection of $w(p)$

We select $w(p)$ by minimizing the energy:
$$
E(w)=E_D(w)+\beta E_R(w)
$$

$E_D(w)$: match the halfway rotation and scale between two images

$E_R(w)$: encourage points that are at rest($v(p)=0$) to remain at rest

$\beta=1$ is fixed

For a pair of neighbors(either horizontal or vertical) in the halfway domain $\Omega​$ , define the vectors connecting them in images $I_0​$ and $I_1​$:
$$
\begin{split}
d_0(p_i,p_j)&=\phi_0(p_j)-\phi_0(p_i)\
&=p_j-p_i-(v(p_j)-v(p_i))\
d_1(p_i,p_j)&=p_j-p_i+(v(p_j)-v(p_i))
\end{split}
$$

$$
\begin{gather}
\tilde{d}_{1/2}(p_1,p_j)=\sqrt{|d_o(p_i,p_j)||d_1(p_i,p_j)|}\hat{d}-X(p_i,p_j), \quad with \
d_s(p_i， p_j)=\hat{d}_1(p_i,p_j)+\hat{d}_2(p_i,p_j) \quad and \quad \hat{u}=u/|u|
\end{gather}
$$

$$
d_{1/2}(p_i,p_j)=p_j-p_i+(w(p_j)-w(p_i))
$$

Deformation energy $E_D(w)$
$$
E_D(w)=\sum_{p_i,p_j}|d_{1/2}(p_i,p_j)-\tilde{d}{1/2}(p_i,p_j)|^2
$$
Resting energy $E_R(w)$
$$
E_R(w)=\sum{p_i\text{s.t.}|v(p_i)|<1}(1-|v(p_i)|)|w(p_i)|^2
$$

Direct pixel evaluation for rendering

Each pixel in an intermediate image is indenpendently evaludated without rasterization.

For each morph image $I_\alpha$,

1. Render a single quadrilateral over the whole image domain

2. For pixel $q_\alpha$ in the pixel shader, an iterative search is performed to find the corresponding point p

   For linear motion paths,
   $$
   \begin{gather}
   p^{(0)}=q_\alpha \
   v^{(0)}=v(p^{(0)}) \
   p^{(i+1)}=q_\alpha-(2\alpha-1)v(p^{(i)}) \
   v^{(i+1)}=(\eta)v(p^{(i+1)})+(1-\eta)v^{(i)}
   \end{gather}
   $$
   For quadratic motion paths,
   $$
   \begin{gather}
   p^{(0)}=q_\alpha \
   v^{(0)}=v(p^{(0)}) \
   p^{(i+1)}=q_\alpha-(2\alpha-1)v(p^{(i)})-4\alpha(1-\alpha)w(p^{(i)}) \
   v^{(i+1)}=(\eta)v(p^{(i+1)})+(1-\eta)v^{(i)}
   \end{gather}
   $$
   $\eta=0.8$ is fixed

3. Sample $I_0$ at $\phi_0(p)$ and $I_1$ at $\phi_1(p)$ using bicubic filtering

4. Blend $I_\alpha(p)=(1-\alpha)I_0(\phi_0(p))+(\alpha)I_1(\phi_1(p))$

Poission-extened image boundaries

Pixel transport

Construct for image $I_0$ an extended version $\overline{I}_0$ (for instance, with 10% extra pixels in each direction).

For each pixel $q_0\in \overline{\Omega}_0$, we seek its domain point p such that $\phi_0(p)=q_0$ to find its corresponding point $q_1=\phi_1(p)\in \Omega_1$

Completion using gradient-domain optimization

Optimize the pixel colors in the extened region of $\overline{I}_0$ and extend image $I_1$ to $\overline{I}_1$ using colors transported from $I_0$

User interface

User-specified correspondence points are used to align important features and do coarse-to-finr optimization.

$$
E = 1- \prod_{c_i\in C}(1-v_{c_i})
$$