由于各种各样的原因，上上周花了差不多一个星期复现一篇关于图形学的传统算法的论文，现在稍微闲下来了，想着还是要写一下笔记，毕竟也学习到了一些东西。
复现的这篇文章如下：
Background
- 在大多数情况下，全景图在最原始的情况下是不规则的，可能是因为用相机拍照的时候手抖了，或者是用算法拼接的时候，结果本来就很难直接拼成矩形，所以全景图大部分都是非规则的。
- 在Instagram或者Flickr上的受欢迎的全景图中，大部分都是矩形化的，可以发现矩形化的全景图更受欢迎。
- 综上所述，将非规则的图片矩形规则化是一个很重要的课题。
Conventional Method
- Crop: 最直接的办法就是直接从非规则的原图中尽可能的裁剪出最大的矩形，这种方法虽然简单，但是缺点也很明显：会遗失大量的信息。
- Inpainting: 这是在Crop之后出现的算法，通过图像修复预测空白区域的图像本来应该是什么，在某些程度上能有很好的效果，但是有时候会出现Artifact的地方：如下图中右下角的半身所示：
- Warping: 然后就是本文所提出的这个方法，用变形的办法将非规则原图“拉”成矩形，这种办法的优点，其一，与其它办法相比来说，轻微的变形对于人眼来说不太明显，与对比度的显眼特征不同，其二，全景图本身就是有变形的效果，那么同用变形的办法在一定程度上会有好处，但是这种方法也会有难点，于是本文也提出了优化的地方。
Challenge
- 第一点就是输入图片的边界不规则，那怎么把不同的规则规整为适合长宽比尺寸的矩形就是第一个难题。
- 第二点就是即使图片变成矩形了，怎么保证其中的内容也能保持一定的形状呢？
Method
本文主要用两个步骤来执行这个算法：
Local Warp
该算法主要采用了[Avidan and Shamir 2007]论文中的Seam Carving (以下称为SC) 算法，主要算法如下所示：
首先根据图像的形状，画出要生成的图片的框(最高的像素的那一行就是图像的上边框，其它边框也是一样)，然后在所有的边上找到最长的一条空白边长，然后根据这个边长从原图中截取出子图，然后从子图中执行SC算法，即，根据能量图:
其实就是梯度图(边缘检测：Sobel)，生成一条最小能量线(Seam)，然后朝着最长边长的那边将所有像素复制并移动一格，然后继续找最长边，就这样不停的迭代直到所有的像素都被填满了，就可以得到矩阵化的图片：
可以看到，形状都畸变了，且有相当多的锯齿，效果很不好，不过不用担心，这肯定不是最后的结果，本文首先，根据该图和原图，生成每个像素的移动矩阵，然后在该图上防止一个标准的Grid网格，这个时候，将Grid根据移动矩阵Warp回去，网格的顶点也是要移动回去，就能得到一个在原图上的Grid网格：
这个网格就是第一步所需要的结果。
Global Warp
由于这个网格一定程度上能将图像矩形化，所以这个网格有很大的作用，那么在这个网格的基础上，优化原图像，就是第二个算法的主要途径、
那第二个方法主要是通过赋予图像，其实是网格，一个能量值，通过最小化这个能量值，就能驱使原图像渐渐生成优化后的矩形图。
能量值设计的思路如下：
第一个便是Boundary Constraints，由于这个算法主要的还是矩形化图像，所以最重要的底线就是保持边界一定是矩形的，所以首先给予网格如下限制：出于左侧的所有网格顶点的纵坐标必须保持一致，上面的所有网格顶点的横坐标也必须保持一致，其他边也是。具体的方程如下所示：
第二个便是Shape Preservation，这个能量值的定义是从[Zhang et al. 2009]这篇论文里面得来的，其目的就是保持所有矩形块在优化前后不要有太大的变化，但是不同的是原算法中还要关注变形图的显著性物体的形状，所以会给予这些块一定的权重，但是对于全景图来说，没有所谓的显著性物体，所以没有特意设置权重。
其中$N$是块的数量，$q$是块的系数，$I$是单位矩阵，$A_{q}$和${V}_{q}$如下所示：
第三个能量值是Line Preservation，主要是从[Chang and Chuang 2012]论文中得来的算法，主要的目的就是让平行的线保持平行，让直线继续保持直直的(与原算法不一样的是不用保持倾斜角度不变)，而实现的途径，首先用LSD(LineSegmentDetection)算法检测出图片中的所有线，再用网格分割所有的线到各自的格子里面，再根据每个线的倾斜角度，将线分到预先设置的盒子里面(将180度均分50份)，通过在优化过程中，约束每个格子里的所有线保持一致的倾斜角度，就能一定程度上保证图像的线不变形了。
Optimization
优化过程如下，第一、二个矩阵不用实时更新，都可以直接计算，但是第三个不同，所以本文首先固定每个线的倾斜角度，计算优化之后的网格是怎样的，再根据优化之后的网格计算每个线的新的倾斜角度，然后再更新那50个装线的盒子中，每个盒子的平均倾斜角度(每个线的倾斜角度和其顶点满足一定的双线性插值关系)，再计算新的倾斜条件下，优化后的网格状况，不断迭代，就能得到更好的结果了。
Results
本算法在Release版本下基本上普通的一张图只需要1000ms以内的时间就可以完成。
但是不是越优化，结果就越好，如下面两个图的比较：
上面那个是20次迭代，下面那个是100次迭代，可以发现20次迭代的效果还行，但是100次就完全不能看了。
Failure
每个算法都有它的Limitation，本算法也不例外，本算法在处理相机直出图像的时候，效果还好，但是在以下条件下会效果不太好：
- 当然在场景没有被完全拍完的情况下，比如在一组要拼接的图片组中缺失了几张时，效果会不会。
- 本文在非常凹的边界会变形的比较厉害，当然，算法使然：
本文说可以将一部分白色没有照片的地方当场有照片的地方(强行变凸)，变形完后，再用图像修补(Image Completion)算法填补缺失的地方。
- 当一个块里面有过多的线的时候，本算法会有些力不从心，不能保持所有线的形状。
Comparison in Resizing
说到本文，最需要思考的就是，本文是第一个将变形(Warping)的思想用到矩形化(Rectangling)里面的，且本文引用的算法中SC算法和Shape Preservation算法的原论文都是做图像Resize的，它们分别从去除像素和变形的角度解决问题，那这两个思想在Resize这个问题下分别有哪些优点和缺点呢？(这真的是一个相当值得思考的问题)：
Seam Carving
优点
- 首先就是这个算法是通过去除像素来实现的，那么首先最大的优点就是像本文里面用到的这样，能灵活的，将图像变形(正方形变圆形？)。
- 其次就是本文是一个离散的一步一步根据当前的状态的形式，这就与一次性的优化的算法不同，一次性的优化就难免会造成特定区域过度优化，而其他区域欠优化。
- 在处理整齐的图像或高度纹理化的图像的时候，SC算法比较有效
- 由于SC算法在像素上允许算法有高度的灵活性，所以基于这个算法，还能基于这个算法有很多其它的用途，比如目标消除(Object Removal)。
缺点：
- 首先这个算法相比Warping来说，它执行比较慢。
- 其实，该算法的离散的性质在一定程度上也算是缺点，会导致结果的边缘有明显的锯齿状，会去掉边缘的一部分。
- 当然，在图像存在很多线型形状的时候，效果就完全不行了。
- 当一张图片的显著性物体的宽比目标图像的宽长的时候，本算法不能很好的应对，效果很差，锯齿很明显(当然了，要去除很多的边缘像素)。
Warping
优点：
- 在处理目标物体有很明显的结构的时候相对于SC算法很有效
- 执行速度快。
- 执行结果能很好的保持边缘信息，能应对线型物体较多的情况。
缺点：
- 相对于SC算法，该算法的应用可能没有那么多。
- 因为本算法的限制大都是软限制，所以可能不能很好地保持线的形状，
References
- AVIDAN, S., AND SHAMIR, A. 2007. Seam carving for content- aware image resizing. In SIGGRAPH 2007.
- ZHANG, G., CHENG, M., HU, S., AND MARTIN, R. 2009. A shape- preserving approach to image resizing. In Computer Graphics Forum, Wiley Online Library, 1897–1906.
- CHANG, C.-H., AND CHUANG, Y.-Y. 2012. A line-structure- preserving approach to image resizing. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 1075 –1082.