本学期选修了媒体计算课程，由于过于懒惰（沉迷做宝可梦）所以迟迟没有开始写大作业……希望能通过写博客督促一下自己XD。（或许一定会写成论文翻译一样的东西
Upd: 虽然按时交了作业，但博客拖到毕业了……真正的拖延症选手XD
第一个大作业和图像补全相关，由于需要补全的图像中框架结构部分往往可以用曲线来近似，所以可以考虑优先先补全框架部分，再补全其他区域的方法。附上 paper 的链接：
Image Completion with Structure Propagation
根据上述思路，补全可以被分为三个阶段：
- 用户标记出图片中需要补全的结构部分的曲线
- Structure propagation（也是本篇论文的核心）补全显著的结构部分
- Texture propagation 补全剩余部分
Structure Propagation
首先在用户标定的曲线 C 的未知区域取 L 个锚点 \(\{p_i\}^L_{i=1}\), 每个 patch 都以这个锚点为中心分布，构成一个一维的图 \(G = \{V, \varepsilon\}\) , 两个点之间的间距往往取patch 的一半。在已知区域中以极小的间隔（往往为1-5个 pixels）在曲线 C 上选取一组 patches 记为 \(P = \{P(1), P(2), …, P(N)\}\) 。问题转换为对每一个锚点 \(p_i\), 在 N 个已知的 patches 中找到合适的 \(P(x_i)\) 补全到锚点的位置。
判断是否合适的能量函数定义为$$E(X) = \sum_{i{\in}V}{E_1(X_i)}+\sum_{(i, j)\in\varepsilon}{E_2(x_i, x_j)}$$ 其中 $$E_1(x_i) = k_s{\cdot}E_S(x_i)+k_i{\cdot}E_I(x_i)$$ \(E_S(x_i), E_I(x_i), E_2(x_i, x_j)\)分别衡量了结构相似性，边界相似性和相邻两个patch之间的相似性，\(k_s\)和\(k_i\)为权重系数。我们通过最小化\(E(X)\)来获得一系列选取的patches的label \(X={x_i}^L_{i=1}\)。
\(E_S (x_i)\) 用来衡量patch和目标未知区域在结构上的相似程度。定义 \(c\)为区域内结构的曲线，则 \(E_S (x_i) \)可定义为$$E_S(x_i)=d(c_i, c_{x_i})+d(c_{x_i}, c_i)$$其中\(d(c_i, c_{x_i})=\sum_{s}||dist(c_i(s),c_{x_i})||^2\)，为\(c_i\)中的每个点到曲线\(c_{x_i}\)之间的最短距离平方之和，如图Figure 3(a)所示，s为 曲线\(c_i\)上点的index 。最终 \(E_S (x_i) \) 需要进一步用 \(c_i\) 中点的数目来归一化 （个人认为是在计算\(d(c_i, c_{x_i})\)的时候归一化，即使用 \(c_i\) 和 \(c_{x_i}\) 分别对 \(E_S (x_i) \) 中的两项进行归一化，因为如果只用 \(c_i\) 中点的数目进行归一化 ， 第二项中曲线\(c_{x_i}\) 包含的点的数目会明显会影响最后的结果，而我个人认为点的数目和两条曲线在形状上的相似程度关系不大） 。
\(E_I(x_i)\)用来衡量patch和未知区域边界部分的已知区域的相似程度（图 Figure 3(b) 绿框部分）。用patch和边界区域已知部分（图中橙色）的sum of normalized squared differences(SSD)来计算，即令区域内点的颜色值为v，有 $$ E_I(x_i)=\frac{\sum_{r,c}(v_i[r,c]-v_{x_i}[r,c])^2}{ \sum_{r,c}(v_i[r,c])^2 \sum_{r,c}(v_{x_i}[r,c])^2 }$$（这里normalized可以用分子的单独一项或者两项都用（参考），具体怎么做还是看需求，理论上应该让几个能量函数得到的值在一个量级量级，我由于懒惰直接使用了两项的版本，感觉效果还行就也没再尝试）。在非边界区域这项为0。
\(E_2(x_i, x_j)\)用来衡量两个相邻patch之间的相似程度 （图 Figure 3(b) 红框部分） 。用两个patch重叠部分的归一化SSD来计算，不再过多赘述。
对于由一条曲线构成的图，很容易就想到用动态规划的思路来使能量最小。对于有相交点的图，首先交点应当被包含在锚点的集合中，其次可以通过Belief Propagation (BP)法来使得能量最小，复杂度为\(O(2LN^2)\)。详见Algorithm 1和Figure 4。
Texture propagation
可能由于论文的重点在对结构的处理上，这部分内容就很常规。有一些更新、更高效的方法应该也可以用来完成纹理补全，应该能收获更好的效果。
Texture Propagation
首先需要补全的部分会被用户指定的结构自然分割成几块，所以每块中的未知区域可以使用该块所在的子区域内的已知区域来补全（图Figure 5(a)），一方面可以提高效率，另一方面也一定程度上避免用到完全无关的纹理信息。
具体的补全方法论文中提到了两篇其他论文：
Image Repairing: Robust Image Synthesis by Adaptive ND Tensor Voting
对于补全顺序的确定，同样提到两篇论文：
Fragment-based image completion
Object removal by exemplar-based inpainting
Photometric Correction
感觉就是解泊松方程那一套 （图Figure 5(b, c)） ，这里放上论文链接：
Sample transformation
通过上述方法sample到的patches可能并不能很好的满足补全的需要，所以论文提出了两种方法来扩充这个集合：
- 对源patch进行固定角度（例如90°）的旋转或是水平/竖直方向的翻转
- 对patch进行任意角度的旋转，使得patch的结构曲线更贴近目标区域的曲线，定义旋转变化\(R(c_{x_i};\theta)\)使得：
$$\theta^*=argmin_\theta\{d(R(c_{x_i};\theta), c_i)+d(c_i, R(c_{x_i};\theta)\}$$
（但做到这里整个程序已经完全跑不动了，所以这一步就被省略了
实现过程中遇到的问题和一些吐槽
我觉得整篇文章的思路还是很好的，针对计算机不能很好的意识到图像中存在一定的结构的问题，通过引入与人的交互来为其提供更多的信息，从而解决这一问题。但某种程度上来说这样的方式也显得这种方法不够“智能”。在查找资料的过程中发现最新的很多论文使用了神经网络来搞这个问题，不需要人的参与，同时效果也很好，不得不感叹传统方法确实还是有很多局限性的:(
由于论文涉及人的参与，就逃不开交互的设计，这个问题既不是论文的核心，又不得不做，并且很影响效果，十分让人头大。我首先想到的是让用户用鼠标来标记结构，但实在是太难控制了手实在是太抖了，根本不能画出很好的直线，更别说曲线了，故弃之。随后我搞了几张类似mask一样图片来标记结构，一条线画了一张图，这种方法的问题是如果逐行逐列扫描的话（例如：从上到下，从左到右），对于一些曲线会导致扫描到的点不连续，然后为了回避这个问题我就没搞曲线的图片XD，实际上应该用深搜什么的连续的把点记录下来，感觉这样对于多条线也不用准备很多张图片了。
然后就是交点的问题，由于曲线在弯的地方可能会不是一个单像素的线了（形容的过于抽象不过反正也没人看XD），所以如果此时与另一条线相交，会导致交点不只一个，虽然可能并不影响什么计算，但最后构成的锚点的图就有些奇怪强迫症，所以最后我挑了几张结构都是直线的图来跑（逃（话说PS里就不能画一条1像素的线就永远是1像素吗？！虽然这个要求好像有点过分）
把锚点、patches这些东西存下来也挺麻烦的，虽然我用了图并且给锚点单独搞了一个类来存乱七八糟的东西，但确实不是很优美。算能量的时候做了很多重复的运算。到最后也没找到一种优美的解决方案。
由于结构的patch是一块一块用泊松融合补全上去的，所以还有一个问题就是填补的顺序。可以优先填补锚点所在区域中已知面积最大的部分，但对于直线状的结构，问题在于当把边界填充完成后，剩下部分的已知区域是一样大的，最后会变成从一边开始补全，导致整体颜色趋近于某一边的颜色。如Figure 6所示，因为除了边界外补全顺序为由上到下，由左到右（和我构建图的顺序有关），可以明显看出色调的差异，而且不知道为什么颜色还越偏越厉害，让人感觉泊松写错了XD。（能够想到对于曲线结构通过旋转应该能改善这个问题，对于直线感觉可以将锚点之间的间距搞成随机数，但这样也有点麻烦，不知道论文里咋搞的，Figure 1看起来挺好的，也许是我漏了什么东西？）
之后的纹理补全我就用了最简单的方法，L形区域一个点一个点补，难的是如何根据用户画的不知道是直线还是曲线的结构——也可能不与图像边界相交——来把整个图像分成几部分。我看到有人在标记的结构的尾端作射线，或者拿直线拟合，然后算点在直线的哪一侧，感觉确实靠谱。但由于这种方法运算量太大了懒惰，最后我用了让用户手动圈一块区域来补全的方法XD
最后这个计算量实在是太大了，我还用了python，稍微复杂一点的结构，简直一跑一晚上还没什么结果，就很难受:(
最后放上几组效果图把，都选择了比较简单的结构，比单纯的纹理补全好了不少，但由于论文本身的原因和我的各种原因，导致效果并没有想象的好。顺序为原图、结构补全结果，最终补全结果，直接纹理补全结果。
Test 1
Test 2
Test 3
