15. 电影中成千上万的群众演员是怎么来的？
15. 电影中成千上万的群众演员是怎么来的？
前段时间我看了一部剧热血的电影《波西米亚狂想曲》，简直是当年经典音乐会的神还原，你们看看剧照：
《波西米亚狂想曲》剧照
我当时就在想，这得找多少群众演员啊，剧组真有钱?
当然，这完全也可以通过影视特效来完成——如果有一种技术能够用少量的素材创造出宏大的人群场景，那就可以满足需求，但前提是要非常逼真，天衣无缝。
今天给大家介绍的就是这样一种技术，这里的参考文献依然很”古老“，是16年前SIGGRAPH 2003的文章[1]：
Vivek Kwatra and Arno Schodl and Irfan Essa and Greg Turk and Aaron Bobick, Graphcut Textures: Image and Video Synthesis Using Graph Cuts, ACM Transactions on Graphics, SIGGRAPH 2003
它要解决的问题是”如何通过缝隙拼接图像“，而且拼接效果要做到天衣无缝。我的上一篇专栏文章14. 如何通过缝隙切割图像-Intelligent Scissors里，我给大家介绍了如何通过缝隙切割图像，图像像素间的缝隙是通过将要解决的问题转化为寻找最小代价路线问题而得到的。而今天介绍的技术，则是通过”图割“来寻找图像像素间的合理拼接缝隙。让我们来看看它具体要解决的问题。
一、问题说明
这篇文章要解决的问题是如何将一个或者多个原始小图像，天衣无缝的拼合成一个空间尺寸上更大的图像。例如：
用小Patch生成大图像
事实上，在这篇文章之前就已经有很多人对这个问题做了研究，但总有这样那样的问题，而文章的作者们则用一种相对直观的方法得到了较好的结果。话不多说，接下来我们就来欣赏下作者的成果。
二、算法效果
- 纹理拼接
算法的第一个典型应用是将一小块纹理图像拼合成一幅更大的纹理图像，这样很容易做一张巨大的壁纸出来。实际上在一些虚拟场景构建，例如游戏场景构建的应用中，这个技术非常有效：
输入：
输出：
输入：
输出：
作者还展示了拼合多张不同的图像为一张大图像的效果：
输入：
输出：
2. 自然图像拼合
除了拼合纹理之外，这个技术还能够用于拼合自然图像：
再看看我前面提到的拼合人群。。。以及羊群的例子：
3. 视频拼合
除了能够拼合图像之外，还可以拼合视频帧，从而将一段短的视频帧天意无缝的变成一个时间更长的视频。可以看看下面这个视频：
看到这里，想必你肯定会感到好奇了，这是怎么做到的呢？那么让我们继续深入探索该算法的原理奥秘。
三、原理介绍
3.1 基本Graph Cut原理
正如前面所述，我们需要将一张或多张输入的小图(原料）拼合成一张大图：
那么作者的想法就是选择原始小图中的部分局部通过旋转、缩放、平移等变换放置到输出图像上，并尽量通过拼接掩盖局部像素之间的间隙。大家可以看到下图中绿圈部分其实都是原图中的局部信息。
这个过程其实分为了两步，
第一步：挑选原始图像中的局部图像，并放置到输出图像上
第二步：通过图割(Graph Cut)，寻找局部图像块和原输出图像中已有像素之间的像素缝隙，并确定输出图像中哪些真正变为该局部图像块中的像素，哪些保持不变。
我们看看原论文中一幅插图，可以更深入的理解
由于第二步非常关键，所以我们先来看看图割这一步，这一步是需要将一个新的图像局部块放置到已经有的输出图像上，并且尽量没有明显的间隙，所以要解决的问题可以形象的表示为：
上图中，我们把两个Patch拼合到一起，它们首先被放置为有一定重合区域。为了让两者之间的缝隙尽可能的不明显，我们需要知道一个分割线（cut)，在这个分割线的左边，图像像素由A贡献，相反在其右边，图像像素则由B贡献。
这里我们将输出的图像看做是由”图(Graph)“所表示，并且给这个Graph两个端点，一个是A，一个是B：
上图中，标有数字的节点实际上是重合区域的像素，节点之间的连接都是有代价的。我们需要拿起剪刀从某个连接上剪掉某些连接，并且要使得被剪掉的连接的代价之和最小化，这就是最典型的图算法中的最小割问题（min cut），它也对应着所谓的最大流问题(max flow)
那么，如何定义连接之间的代价呢？这里假设在重合区域两个相邻的输出像素分别是s和t。我们知道输出的像素既可能来自于A，也可能来自于B，于是我们用A(s)，B(s)来表示s点在A图和B图的颜色, 用A(t)，B(t)来表示t点在A图和B图的颜色。
于是，s点和t点的连接的代价被定义为：
我们要做的就是寻找一个切割缝，最小化
, 当找到这条缝之后，左边的像素从A中拷贝而来，而右边的像素则从B中拷贝而来即可。
3.2 不断拼合更多的Patch
有了上面的基本原理后，就可以不断的拼合更多的Patch，目标是用越来越多次的覆盖输出图片中的缝隙，使得输出越来越”天衣无缝“，直到代价值收敛，我们可以看看下面这个短视频：
我们也许会认为这个过程就是先拼合两个Patch成为一张新图片，然后再将此新图片和新的Patch拼合，第二步和第一步完全无关，就像这样：
但这样只会得到糟糕的结果，因为第二步没有考虑到第一步的信息。
作者认为，当要将新的patch加入到上一轮已经生成的部分输出图片时，需要保存上一轮接缝的分割代价，并将新计算的分割代价加入到老的分割代价中，形成总体代价，并以这个代价来决定新的分割位置。
当然，这个过程比上图还要复杂一些，原论文中有一幅插图和一段文字来解释这个过程：
首先，首先在上面右图中的绿色分割线上加入所谓的"缝节点(Seam Node)"，即S1,S2,S3,S4。
然后将缝节点与新Patch B相连，并且为与之相连的连接都分配相应的代价。我以节点1和4之间的缝节点为例列表如下：
那么作者进一步提到如何计算新的总代价，以及如何去根据新的总代价进行新Patch B与原Patch A的拼合：
- 规则1：如果M（1，4，A1，B）经过图割运算后依然属于min-cut，即依然是缝合线，那么说明原有的缝合线是合理的，缝合线两边至少有一个像素被替换为新Patch的像素。例如上图中像素连接5--8.
- 规则2：如果M（1，4，A1，B）经过图割运算后依然不属于min-cut，说明原始接缝会消失。所以该缝合线两边的像素都会被替换为新像素，或维持老像素，例如上图中像素连接6--9
- 规则3：如果与某个缝节点及其相邻像素间的连接被切割，那么需要将切割代价与原有代价相加，形成新的切割代价。
当我们不断按照这个规则加入新Patch时，就会使得生成的图片的缝隙越来越不明显，直到代价收敛：
3.2 Patch的选择和匹配
你可能会问，如何从原始的素材里面找到合适的Patch，并将此Patch放置到输出图像和合适的地方呢？
作者提到了三种方法：Random Placement（随机放置）, Entire Patch Matching （整体匹配），Sub-Patch Matching (子区块匹配）
1） Random Placement，简单说就是将整个输入图像（B）经过随机的平移放置到输出图像(A）上，再从中用Graph-Cuts原理进行输入图像和输出图像之间的拼合。
2）Entire Patch Matching，这个方法需要遍历所有可能的平移量，并从中找出与已有输出图像最匹配的一个位置。”匹配度“是通过计算A与B之间的重合区域的sum-of-squared-differences (SSD) 来完成的
3）Sub-Patch Matching，这个方法先从输出图像中找到一个子区域，并在输入图像中寻找与这个子区域最匹配的Patch。
作者还讲了很多优化搜寻Patch的方法，以及如何让接缝更加不显眼的方法。大家可以仔细去阅读原论文。
3.3 视频处理
这个算法最神奇的一点是还可以用于视频的合成，甚至制作出无限循环播放的视频。其基本思想是在视频中找到合适的帧范围，在这个范围中进行图割，然后进行像素的填充和替换：
对于有周期变化的视频，作者提到可以在视频中找两个相邻的匹配度很高的帧，然后在这帧之间进行图割和像素填充。这样就可以将帧间的变化缝隙抹掉。这样当我们无限循环播放此视频时，看起来就似乎视频没有终止一样。
例如下面这个视频：
关于视频的拼接合成，作者论文里面还有一些精彩的例子，大家感兴趣可以自行阅读原论文。
四、总结
这篇文章给大家介绍了第一个”图割(Graphcut)“的应用，它可以用一小片图像生成一幅很大的图像，也可以用一小段视频生成一个很长的视频，而且从视觉上让人看不出来生成过程中的拼接痕迹。我觉得它给我带来的最关键的启示就是另外一种在图像中寻找缝隙的方法，这里的缝隙使得当图像被切开并将部分像素进行替换后，可以让人从视觉上感觉不明显。
由于作者的论文中还有很多细节被我忽略了，所以我推荐感兴趣的你仔细阅读原始论文，并欢迎和我交流。如果你喜欢这篇文章，请给我点赞，谢谢！
五、参考资料
这次我参考的文章主要有：
[1]Vivek Kwatra and Arno Schodl and Irfan Essa and Greg Turk and Aaron Bobick, Graphcut Textures: Image and Video Synthesis Using Graph Cuts, ACM Transactions on Graphics, SIGGRAPH 2003
[2]Graphcut Textures Image and Video Synthesis Using Graph Cuts, Presentation by Benjamin Sigg
开篇的电影剧照来自：
[3]电影波西米亚狂想曲剧照