文档介绍：pletionwithStructurePropagation[1]——《计算机应用数学》读书报告10421038董子龙浙江大学CAD&CG实验室浙江大学计算机系摘要:报告总结了[1]的算法流程,设计动态编程,信任传播,泊松方程;同时补充说明Texture-by-numbers纹理合成方法[2][3][4]。pletion也称为ImageInpainting,主要功能是利用已知的图像信息,填充未知的区域像素。已有的方法涉及偏微分方程,采样,梯度光滑等技术,已经能够较好的恢复未知区域的颜色,保持在纹理上的一致性,但是不能很好的保持显著的结构,如栅栏、楼梯、窗户等。这篇文章在一定范围内解决了这个问题。 基本思路研究者基于以下两个结果:自然图像中的特征通常能够用曲线勾勒出来;在填充其它区域之前,这些特征的内容应该首先确定。提出了图像填充的步骤:用户勾勒出特征曲线,图1(b);结构扩散,根据曲线确定特征,图1(c);纹理扩散,填充其它区域,图1(d)。图1全局优化模型研究者建立了一个全局优化的模型,以最小化合成面片的重叠区域的颜色差异。以最简单的一条曲线为例,如图2:图2已知和未知区域分别用I和Ω表示,C是用户画的特征曲线,在Ω中对C稀疏采样得到L个锚点,作为合成面片的中心。这些点相邻之间两两相连,构成一个单链图G={V,ε},V就是L个锚点的集合,ε是连接相邻节点的边集合。在Ω外,沿着C的一条窄条对已知区域采样得到样本面片集合P={P(1),P(2),……,P(N)},如果结构样本不足够,可以通过旋转获得新的样本。于是问题就转化为,为L个合成面片选择相应的样本源面片,即求取路径,使其中最小。ES,EI,E2分别代表结构,完整,耦合约束;ks,ki是调节权值。ES是源面片与合成面片结构上的差异,即所包含的特征曲线之间的差异。d函数计算第一个曲线参数上的每一个点到第二个曲线参数上的距离之和,如图3(a)。图3EI约束与I存在交集的合成面片的源面片在交集上必须一致,即在图3(b)绿色框中的橙黄色部分。EI等于交集上的归一化平方差(SSD)的和。E2指明了相邻的两个合成面片之间的重叠区域的差异,即在图3(b)红色框中的橙黄色部分。同样是计算归一化平方差(SSD)的和。动态编程——单曲线的结构扩散对于只有一条曲线的情况,可以看作单链图求解一个最小值路径的动态编程问题。定义为从1到i所有可能的xi的积累最小值,动态编程遍历2到L,递归计算所有路径的:其中。L的对应的xi即是,在计算的过程中维护一张记录路径的表,就可以回溯得到所有的源面片。信任传播——多曲线的结构扩散对于更加复杂的情况,单链图不足以表示,如图4(a)。为了构造符合要求的图G,首先在所有的曲线交点上设置锚点,然后对剩下的曲线采样,如图4(b)。对于这样的图,动态编程的代价非常高,所以研究者采用了信任传播。图4信任传播是两两相连的无向图上的局部消息传递算法,旨在使定义的Gibbs能量最小。其基本思想:图中的每一个节点从它的邻居接收消息,根据自身状态更新消息,然后把消息返还各个邻居。如下:是从i节点传给j节点的消息,包含N个元素的列向量,N是样本源面片的个数,表示j节点对应的可能性,在算法实现过程中,只保存最大可能值。公式(5)就是消息传递的循环过程,研究者利用带负号的log函数把概率转换成和的最小值,事实上