#交互式数字蒙太奇

1. 交互式数字蒙太奇效果概述

交互式数字蒙太奇可以将多张照片以难以察觉的方式融合在一起，产生非常真实的图像融合效果。 当系统输入一系列的照片之后，用户通过画笔的方式将label刷到每张照片中。系统通过每个区域中用户指定的label，结合图中的颜色信息，得到最终的结果。比如下图中，左边的四张图片融合在一起，用户输入了如中图所示的人工交互，产生了右图的融合效果。

2. 算法原理

关于算法原理，已经在课程ppt中进行了详细的介绍，在推荐的论文中也做了非常详细的描述，同学们可以通过阅读ppt和论文，对关键的细节进行理解。这里仅仅给出大致的框架流程，以及对实验来说最重要的的公式。

2.1 总能量函数

本实验中需要优化的能量函数为：

比较重要的概念是data term 和 smooth term。

数据项

data term中文名为数据项，它的定义如下：

平滑项

对于smooth term，它的中文名为平滑项，它的定义如下：

2.2 使用graph cut optimization来优化上述总能量函数

已经知道了上述的能量函数之后，我们的目标是优化（即最小化）上述的函数，从而求出最佳的解（在本实验中解即是每个像素的label）。相信认真阅读过课程ppt以及论文的同学们都知道，这个能量函数本质上是一个MRF问题，这里我们使用graph cut optimization来进行优化求解。对于graph cut optimization，有兴趣的同学可以阅读[2]来了解更多。由于要实现graph cut optimization的难度非常大，这里我们用一个现成的实现。请同学们点击这里来下载gco-v3.0库。

下载完成后，请同学们先仔细阅读GCO_README.TXT，然后阅读example.cpp，大致了解这个库是怎么用的，怎样去求解MRF问题。正如上述提到的，这里最重要的概念是数据项和平滑项，而gco-v3.0正是需要同学们对数据项和平滑项进行定义。对此，同学们可以仔细阅读example.cpp里面的这几个函数：

void GridGraph_DfnSfn(int width,int height,int num_pixels,int num_labels);
int smoothFn(int p1, int p2, int l1, int l2);	//这个函数定义了平滑项
int dataFn(int p, int l, void *data);			//这个函数定义了数据项

了解了这个库是怎么用之后，同学们便可着手定义自己的smoothFn和dataFn，去优化2.1中所定义的总能量了。

2.3 Gradient-domain fusion

利用gco-v3.0进行求解之后，我们得到每个像素的label。但是由于光照不同等问题的存在，可能导致在图像的连接处依然存在明显的瑕疵。所以这里做的是减少这种瑕疵。正如论文[1]里面Section 4所描述的，这里我们根据2.2中得到的labeling，去计算融合图像中的每个像素的梯度，然后求解泊松方程来得到最终的融合图像每个像素的颜色。原理在这里不再描述，这里只给同学们点出最重要的公式：

求解泊松方程需要求解一个线性方程组。由于之前的实验中已经实现过一个求解现象方程组的程序了，这里要求同学们利用之前写的代码，求解泊松方程。

3. 实验要求

实验平台：VS2010+OpenCV 2.4.10

要求实现用给定的框架代码（界面工具），完成后台代码，实现图像蒙太奇的核心算法。

Bonus:

  1. 使用鼠标进行交互，实现简单的画刷式能（最多2分）
  2. 能够通过图像号码选择需要交互的图像。（最多2分）
  3. 实现单一图像笔刷功能。使用单个图像笔刷，用户希望只向当前合成中添加一个图像，并且该图像应该是既满足笔划下的目标又尽可能无缝地与现有合成匹配的最佳图像。为了向用户提供对最佳图像选择的控制，在绘制之后立即向用户显示第三个窗口，称为选择窗口。（最多3分）
  4. 实现多图像笔刷的功能。多图像笔刷主要针对一个图像不包含所有需要的效果情况下的情景。（最多3分）
    注：共10分，请根据文档质量及代码实现效果酌情给分。

4. 参考文献

[1] Aseem Agarwala, Mira Dontcheva, Maneesh Agrawala, Steven M. Drucker, Alex Colburn, Brian Curless, David Salesin, Michael F. Cohen:
Interactive digital photomontage. ACM Trans. Graph. 23(3): 294-302

[2] Vladimir Kolmogorov, Ramin Zabih:
What Energy Functions Can Be Minimized via Graph Cuts? IEEE Trans. Pattern Anal. Mach. Intell. 26(2): 147-159