Image Completion With Structure Propagation

1. 算法概览

用户在空洞区域以及已知图像区域勾画结构线, 该算法在已知图像区域采样, 通过优化一个目标能量来决定如何将样本填充被结构线覆盖的空洞区域.如图1所示
图1

2. 知识点回顾

2.1 采样策略

首先对处于Ω\Omega区域的CC进行稀疏采样, 依次得到LL个锚点{pi}i=1L\{p_i\}_{i=1}^{L}如图2所示, 之后再Ω\Omega区域合成的块都是以这些锚点为中心的, 这些锚点形成一条链条或者可以认为是一个以为的图G={v,e}G=\{v, e\}. 抽样间隔通常是块大小的一半, 这样可以保证有足够的重叠区域使得修补后的图像结构变得更加平滑. 在Ω\Omega外, 沿着曲线CC进行采样, 一般采样间隔为1-5个像素, 得到的样本集块P={P(1),P(2),P(3),…,P(N)}P=\{P(1), P(2), P(3), \ldots, P(N)\}
图2

2.2. 目标能量

对于每一个锚点pip_i, 我们找到一个标签xi∈{1,2,…,N}x_i\in\{1,2,\ldots,N\}对应于其中的一个样本块, 将样本块P(xi)P(x_i)复制到pip_i的位置如图3所示.

图3
能量函数定义如下:
E(X)=∑i∈vE1(xi)+∑(i,j)∈eE2(xi,xj)E(X)=\sum_{i\in v}E_1(x_i)+\sum_{(i, j)\in e}E_2(x_i, x_j)
其中E1(xi)=ksEs(xi)+kiEI(xi)E_1(x_i)=k_sE_s(x_i)+k_iE_I(xi).Es(xi),EI(xi),E2(xi,xj)E_s(x_i), E_I(x_i), E_2(x_i, x_j)分别表示结构, 边界和一致性约束. 这几个约束的定义详见PPT.

2.3. 单结构线的求解

单结构线的求解问题可以动态规划(Dynamic Programming)进行求解. 递推公式如下:
Mi(xi)=E1(xi)+min⁡xi−1{E2(xi−1,xi)+Mi−1(xi−1)} M_i(x_i)=E_1(xi)+\min_{x_{i-1}}\{E_2(x_{i-1}, x_i)+M_{i-1}(x_{i-1})\}
其中Mi(xi)M_i(x_i)表示在第i个锚点位置放置xix_i个样本块的情况下, 从锚点1到ii之间最优的一个能量. 那么当i=Li=L的时候, 最优的样本标号xL∗=arg⁡min⁡xLML(xL)x_L^*=\arg\min_{x_L}M_L(x_L), 其他锚点位置摆放的样本标号容易用回溯法求得.

3. 实验要求

利用VisualStudio与OpenCV设计交互界面完成以下功能, 可以用OpenCV做一个简单的界面。
你可以参考此工程，也可以选择自己喜欢的IDE与工具集。

必做:

  1. 任意选择需要修补的区域, 可以用简单的传入一张mask来做
  2. 能够使用直线结构修补

Bonus:

  1. 用鼠标交互的方式框选出需要修补的区域（最多2分）
  2. 完成曲线结构修补功能（最多2分）
  3. 完成光测度一致性调整（最多3分）
  4. 多结构线的修补算法（最多3分）

4. 参考文献

[1] J. Sun, L. Yuan, J. Jia, and H.Y. Shum. Image completion with structure propagation. In ACM SIGGRAPH 2005 Papers, ACM, 2005. page 868