pletionwithStructurePropagation1——计算机应用.docx

Image Completion with Structure Propagation [1]
――《计算机应用数学》读书报告
10421038董子龙
浙江大学CAD&CG实验室
浙江大学计算机系
摘要：报告总结了 [1]的算法流程，设计动态编程，信任传播，泊松方程；同时补充说明Texture- by-numbers 纹理合成方法[2][3][4]。
简介
Image Completion也称为Image Inpainting，主要功能是利用已知的图像信息，填充未知 的区域像素。已有的方法涉及偏微分方程，采样， 梯度光滑等技术，已经能够较好的恢复未
知区域的颜色，保持在纹理上的一致性，但是不能很好的保持显著的结构，如栅栏、楼梯、 窗户等。这篇文章在一定范围内解决了这个问题。
基本思路
研究者基于以下两个结果：
自然图像中的特征通常能够用曲线勾勒出来；
在填充其它区域之前，这些特征的内容应该首先确定。 提出了图像填充的步骤：
用户勾勒出特征曲线，图 1(b);
结构扩散，根据曲线确定特征，图 1(c);
纹理扩散，填充其它区域，图 1(d)。
全局优化模型
研究者建立了一个全局优化的模型，以最小化合成面片的重叠区域的颜色差异。以最简 单的一条曲线为例，如图 2 :
已知和未知区域分别用 I和Q表示，C是用户画的特征曲线，在 Q中对C稀疏采样得到
L个锚点{ pi} Lj，作为合成面片的中心。 这些点相邻之间两两相连， 构成一个单链图 G={V,
£ }，V就是L个锚点的集合，£是连接相邻节点的边集合。在 Q外，沿着C的一条窄条对
已知区域采样得到样本面片集合 P ={P(1), P(2),……,P(N)},如果结构样本不足够，可
以通过旋转获得新的样本。于是问题就转化为，为L个合成面片选择相应的样本源面片， 即
求取路径X二{X儿，使
E(X) = £百1(心)+ 乂 甌(斗宀h ⑴
其中
如仕訂』心* £曲"+札・旳(如. (2)
最小。Es, Ei, E2分别代表结构，完整，耦合约束； ks, ki是调节权值。
Es是源面片与合成面片结构上的差异，即所包含的特征曲线之间的差异。
(叭)=+d(4i,q), (鼻)
d函数计算第一个曲线参数上的每一个点到第二个曲线参数上的距离之和，如图 3(a)。
何 (b)
图3
即在图3(b)绿色框中的橙
Ei约束与I存在交集的合成面片的源面片在交集上必须一致, 黄色部分。Ei等于交集上的归一化平方差 (SSD)的和。
即在图3(b)红色框中的橙黄色部
E2指明了相邻的两个合成面片之间的重叠区域的差异, 分。同样是计算归一化平方差 (SSD)的和。
动态编程一一单曲线的结构扩散
对于只有一条曲线的情况，可以看作单链图求解一个最小值路径的动态编程问题。定义
Mj(xJ为从1到i所有可能的Xi的积累最小值，动态编程遍历 2到L,递归计算所有路径
的 M4):
= Ei(矶)十 ^<)十胚一〕］-, (4)
其中M^xJ = E^xJ。L的对应的xi即是Xl =argmi n%ML(XL)，在计算M/x」的过
程中维护一张记录路径的表，就可以回溯得到所有的源面片。
信任传播一一多曲线的结构扩散
对