原文链接：http://www-sop.inria.fr/reves/Basilic/2013/CDSD13/
Introduction
基本的自动3D重建方法能够很好地对建筑和规则物体进行重建，却常常无法对日常城市场景中的植物，汽车和其他复杂几何图形取得很好的重建效果。深度信息的丢失也使得对上述场景进行基于图象的渲染（IBR）极为困难。这篇论文的目的是为此类场景的数据集提供近乎可靠的自由视角导航。为了达到这一目的，论文提出了一种新的IBR算法。它对丢失和不稳定的几何图形具有很好的鲁棒性，能够在距离输入相机很远的区域创建新的视角并生成该视角下的图像。该算法主要有两部分：(1)对无法进行充分重建，深度不明确的区域提供深度采样点（depth sample）的深度合成（depth synthesis）算法; (2)局部保持形状的变换（local shape-preserving warp）和三步（three-pass）渲染算法。以上两部分建立在对输入图像进行过分割（oversegmentation）的基础上。
Overview
- 使用Bundler提取相机参数矩阵和multiview stereo重建场景的3D点云。
- 将3D点投影到输入图像中，得到每张图像深度采样点的集合。
- 过分割所有输入图像，创建超像素（superpixel）。
- 在进行3D重建后，仍存在部分区域没有明确的深度信息，使用深度合成在图像上寻找和该区域超像素具有相似性的超像素。以找到的所有候选超像素为节点建立图结构（graph structure），遍历图找到颜色和空间最匹配的3个超像素，并对深度信息不明确的超像素进行深度插值。
- 与论文Silhouette-Aware Warping for Image-Based Rendering和Content-Preserving Warps for 3D Video Stabilization做法相反，对每个超像素而非图像整体进行局部保持形状的变换。
- 三步渲染算法：首先选出距离新视角最近的四个输入相机，通过局部保持形状的变换将其图像投影到新视角的相机投影面上，再根据权重混合（blend）这四张变换后的图像，最后使用泊松融合（Poisson blending）填补孔洞（hole）。
Depth synthesis algorithm
3D重建后，采用论文SLIC superpixels compared to state-of-the-art superpixel methods提出的算法对每张输入图像进行过分割，该算法将图像分割成大小近似且具有规则形状的超像素（左图）。用(S={S_i}_{iin{0,1,2...n-1}})表示每张图像中所有超像素的集合，将重建得到的3D点云投影到图像上（右图），像素(x)的深度表示为(D[x])。若(D[x]>0),则(x)为图像上的一个深度采样点，并用集合(D[S_i]={xin{S_i}|D[x]>0})表示每个超像素里所有的深度采样点。其中，只包含极少量（少于该超像素内像素总数量的0.5%）采样点的超像素，被称为目标超像素（target superpixel），即没有明确深度信息，需要进行深度合成的超像素。为了对目标超像素进行深度合成，需要从其余超像素里选出一组（一般为3个）和目标超像素内容相似，空间接近的超像素作为源超像素（source superpixel），求出源超像素内深度分布的概率密度函数（PDF），在目标超像素内插值。
Computing similar superpixels
类似论文Efficient Hierarchical Graph-Based Video Segmentation提出的方法，使用(chi^2)距离来度量超像素之间的内容相似性。
- 将图像变换到(L_{AB})空间。
- 对每个超像素(S_i)，作出直方图，根据直方图计算60维的描述子(H_{Lab}[S_i])。
- 对每个目标超像素(S_i^T)，使用描述子间的(chi^2)距离找出和目标超像素内容最相似的40个超像素，定义其集合为(N[S_i^T])。
Shortest walk algorithm
采用图遍历算法找出(N[S_i])中和目标超像素空间最接近的3个超像素，即源超像素。
- (Gamma[S_i^T ightarrow S_j])表示从目标超像素(S_i^T)到(S_jin N[S_i^T])的所有可能路径。
- 路径(gammainGamma[S_i^T ightarrow S_j])，令(gamma(0)=S_i^T)，(gamma(|gamma|)=S_j)。
- (C(S_i^Tstackrel{gamma}{
ightarrow}S_j))表示通过路径(gamma)花费的成本，若用(chi^2)距离度量在超像素(S_m)和(S_n)之间移动的成本，则路径成本：
(C(S_i^Tstackrel{gamma}{ ightarrow}S_j)=sum_{t=0}^{|gamma|-1}d(H_{Lab}[gamma(t)],H_{Lab}[gamma(t+1)])) - 采用Dijkstra最短路径算法求解( ilde{C}(S_i^T ightarrow S_j)=minlimits_{gamma} C(S_i^Tstackrel{gamma}{ ightarrow}S_j))，找出路径成本最小的3个解，定义其集合为( ilde{N}[S_i^T])。
- 对( ilde{N}[S_i^T])作出深度直方图，考虑两种情况：
- 直方图中出现一个峰值或两个连续的峰值（左图），表示目标超像素和源超像素很可能属于图像上的同一个物体，深度合成的结果是近似可靠的。
- 直方图中出现两个以上或分离的峰值（右图），表示目标超像素和源超像素大概率属于图像上不同的物体，丢弃该目标超像素，并将其标记为孔洞。
Interpolating depth samples
以源超像素集( ilde{N}[S_i^T])的深度概率密度函数为权重，在目标超像素内进行插值。
- 在(S_i^T)内随机选出10-15个像素(x)。
- 作出( ilde{N}[S_i^T])的深度直方图，对直方图归一化，得到深度的概率密度函数(P(D))。
- 对( ilde{N}[S_i^T])内(P(D[y]))越大的深度采样点(y)赋予越高的权重。
- 对( ilde{N}[S_i^T])内距离(x)越近的深度采样点(y)赋予越高的权重。
- 对深度的倒数进行插值（我觉得直接对深度插值也是可以的，区别不大）：
(frac{1}{D[x]}=frac{sum_{S_kin ilde{N}[S_i^T]}(sum_{yin D[S_k]}P(D[y])|x-y|^{-2}D^{-1}[y])}{sum_{S_kin ilde{N}[S_i^T]}(sum_{yin D[S_k]}P(D[y])|x-y|^{-2})})
Local warpping of superpixels with depth samples
一些深度采样点，尤其是物体轮廓附近的深度采样点，会被视为噪声。另一方面，经过深度合成得到的深度值只是近似可靠，并非精确。因此，使用这些深度采样点，直接将超像素重投影（reprojection）到新视角的相机平面（image plane）上会造成图像失真。为了解决失真问题，对每个超像素进行局部变换（local warp，warp本义是“扭曲，变形”，我把它理解为“变换”，因为我觉得其本质上是将超像素变换到不同的相机坐标系），并正则化（regularize）深度采样点。
Shape-preserving warp
- 如下图所示，对每个超像素建立一个轴对齐的边界框（axis-aligned bounding box），被三角化的变形网格所覆盖（warp mesh）。经过局部变换后的网格顶点坐标是未知量，用( ilde{v})表示。
- 定义两个ernergy term（不知道该怎么翻译了，其实就是最小二乘的误差项）：
- Reprojection energy（RPE）：网格的每个三角形(T)，都包含0个或若干个深度为(D[x])的深度采样点(x)。用((v_{j1},v_{j2},v_{j3}))表示三角形(T)的顶点位置，则(x)的质心坐标（barycentric coordinates）可表示为((alpha_j,eta_j,gamma_j))。用RPE度量经过重投影后，在新视角的像素坐标系中，(x)所在位置和经过局部变换后的位置之间的距离，即(E_{rpe}[x]=|alpha_j ilde{v}_{j1}+eta_j ilde{v}_{j2}+gamma_j ilde{v}_{j3}-C_N(C_{Ii}^{-1}(D[x]))|^2)。其中，(M=C_N C_{Ii}^{-1})为将(x)从输入相机像素坐标系投影到新视角像素坐标系的变换矩阵。
- Shape-preserving energy（SPE）：对于顶点为((v_{m1},v_{m2},v_{m3}))的变形网格三角形，SPE度量了三角形经过局部变换后的变形（distortion）程度。理想情况下，其值为0。对SPE的推导参考论文Silhouette-Aware Warping for Image-Based Rendering和Content-Preserving Warps for 3D Video Stabilization。
(a=(v_{m3}-v_{m1})^T(v_{m2}-v_{m1})/|v_{m2}-v_{m1}|)
(b=(v_{m3}-v_{m1})^TR_{90}(v_{m2}-v_{m1})/|v_{m2}-v_{m1}|)，(R_{90}表示90^omicron旋转矩阵)
(E_{spe}[T]=| ilde{v}_{m3}-( ilde{v}_{m2}+a( ilde{v}_{m1}- ilde{v}_{m2})+bR_{90}( ilde{v}_{m1}- ilde{v}_{m2}))|^2)
- 建立稀疏线性系统（sparse linear system），采用CHOLMOD算法，求解最小化(E_w[S_k]=sum_{xin D[S_k]}E_{rpe}[x]+sum_T E_s[T])。
Rendering
渲染分为三步。首先，选择距离新视角最近的4个输入相机，将输入相机的图像变换到新视角的像素坐标系中。融合变换后的4张图像生成新视角下的图像。最后填补图像上的孔洞。
Camera selection and warping
- 根据相机方向，选择距离新视角相机所在位置最近的4个输入相机。
- 经过之前所述操作后，分别将输入图像变换到新视角上。
- 启用浮点渲染（floating point render target），使能深度测试（depth test），使用超像素内所有深度采样点的中值进行深度测试。
- 由超像素的轮廓构建阿法遮罩（alpha matte），并渲染变形网格。
- 若相邻超像素的深度和当前超像素几乎相同，则采用“软阿尔遮罩”（soft alpha matte），即超像素边界向外扩展4个像素后，构建阿法遮罩，再渲染变形网格。这种方法能够填补超像素之间的小裂缝。
- 渲染后得到4张新视角下的图像，效果如下图所示。可以看到，经过变换后，背景超像素会沉降到前景超像素下方，并产生孔洞。
Blending
- 对新视角下图像的每个像素进行着色，需要对4个候选像素赋予不同的权重。计算角度惩罚因子（angle penalty），剔除权重最低的两个候选像素以避免过度融合。
- 以来自不同图像的两个超像素为节点，若这两个超像素对应着相同的3D点，则进行链接。遍历超像素，建立图像间超像素的对应图（correspondence graph，又不知道该怎么翻译了，直译好别扭）。
- 若待融合的两个候选像素间存在链接，则使用角度惩罚因子对候选像素赋予权重。若不存在，且其中一个超像素的深度是通过multiview stereo重建得到的“真实值”，另一个超像素的深度由深度合成得到，则增加前者的权重（2倍）。其余情况下，对拥有更大深度值的像素，提高权重（2倍）。融合的效果如下图所示。
Hole filling
当新视角位置距离输入相机很远时，一些区域无法被输入相机拍摄到，从而在融合后产生很大的孔洞。针对这种情况，求解泊松方程对图像进行处理。
Liminations
这篇论文提出的方法存在以下不足：
- 若和目标超像素相对应的物体未在图像其它地方出现，则深度合成之后，该目标超像素会被分配不正确的深度值。下图中，前景中树的深度被分配给了背景中的树，导致融合后无法区分前景和背景。
- 深度合成无法处理场景中的动态对象，比如人。
- 效果好坏受到过分割算法的限制。
- 填补孔洞的方法过于简单。
论文最后也给出了一些改进方法和参考论文：
Region Filling and Object Removal by Exemplar-Based Image Inpainting
PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing
Piecewise Planar and Non-Planar Stereo for Urban Scene Reconstruction
Image-Based Rendering for Scenes with Reflections