论文阅读： AppProp: All-Pairs Appearance-Space Edit Propagation 核心内容翻译

我们提出了一种直观而有效的方法来编辑复杂的空间变化数据集的外观。在我们的框架中，用户通过执行将相似的编辑应用于外观相似的空间紧密区域的策略，来指定粗略的调整，这些调整可以交互式地进行细化。我们的方法不是提出特定的用户界面，而是允许艺术家使用他们最喜欢的任何方法或工作流快速，不精确地指定初始编辑。通过对数据集中所有点对实施编辑策略，可以使用能量优化公式将初始的粗调调整传播到最终的细化调整。我们表明，该公式等效于求解由稠密矩阵定义的大型线性系统。我们利用矩阵的固有结构，推导了一种近似算法来交互式地计算这种解决方案。我们通过编辑图像，HDR辐射图和测量的材料来展示我们的方法。最后，我们证明了我们的框架对现有方法进行了概括，同时在通用性，鲁棒性和效率方面都进行了重大改进。

概述

无论是低动态范围还是高动态范围的图像，以及被测量的材质，都可以看作是外观样本，编码颜色或材质参数的大型空间变化的集合。尽管这些数量差异很大，但通常会产生编辑需求，以传达对原件的艺术诠释。由于两个主要原因，对这些空间变化的数据集的外观进行甚至简单的调整都是具有挑战性的。首先，这些数据集中的大量外观样本不允许单独手动更改每个样本。其次，要保持复杂的模式，必须对分布在复杂，通常不相交的空间模式中的区域均匀地进行编辑。

我们的目标是提供一种直观，易于控制的交互式方法来编辑空间变化数据集的外观。我们通过一个编辑框架来实现这一目标，在该框架中，用户可以对这些数据集的不同区域指定“粗略”调整，而我们的算法则通过执行将相似的编辑应用于外观相似的空间紧密区域的策略，来交互式地优化这些编辑。此策略是由观察得出的，该观察表明具有此属性的已编辑数据集保持了原始数据集的复杂模式。我们的框架自然支持不同的编辑工作流程，从而允许艺术家选择他们喜欢的方法来指定粗略编辑。换句话说，我们不专注于定义特定的工作流程和相关的用户界面，而是在执行直观有效的策略的同时允许艺术家选择任何工具来执行初始操作。

图一中展示了在我们框架支持下的两个粗略编辑的例子。在上面的一行，用户使用在不同外观区域绘制的几个笔触来编辑图像；我们的算法会自动将这些编辑内容传播到图像中的所有其他点，即使这些点在不连续的区域中也是如此。为了获得更多控制，美术人员可能需要快速指定整个图像的编辑，而无需精确地遵循外观图案。我们的算法将优化这些编辑，以确保它们尊重基本的外观特征，如底部图片所示。在指定这些初始粗略调整时，美术师可以使用他们觉得最舒适的任何用户界面，包括Adobe Photoshop等商业软件包。

在我们的框架中，使用能量优化公式将初始的粗略编辑传播到最终的精细编辑。在这种表述中，用户编辑是软约束，而将相似编辑应用于相似外观的邻近区域的策略表示为对数据集中所有样本对计算的相似外观点之间最终编辑中的梯度进行惩罚的术语（项）。我们证明，这等效于求解由数千亿个元素的密集矩阵定义的线性系统。为了实现交互性，我们提出了一种近似算法，该算法可以利用矩阵的固有结构派生出的交互速率高的线性系统，且精度很高。

我们的工作灵感来自图像和材料编辑的最新成果，这些成果使用稀疏优化公式来提供有效的基于笔划的编辑工作流程。我们表明，这些方法可以解释为我们公式的特殊情况，它们在支持用户输入方面不太普遍，而同时却证明使用它们时的鲁棒性和计算速度较慢。此外，我们表明，我们的方法也可以解释为联合双边过滤的一种稳健的概括，可应用于编辑传播。

在本文的其余部分，我们将介绍我们的框架，主要显示图像编辑结果，因为图像更容易获得。读者应该知道，尽管我们的框架也适用于材料，但实际上我们发现进行调整的难度较小。本文做出以下研究贡献：

我们提出了一种精炼“粗糙”编辑的通用公式，该公式可确保将相似的编辑应用于外观相似的空间接近区域，并自然支持不同的艺术工作流程和用户界面。
我们基于矩阵采样得出了精确的近似算法，以交互方式传播最终编辑，并通过仔细的分析来支持我们的主张。
我们证明了我们的编辑框架可以处理多种外观量，包括低动态范围图像和高动态范围图像以及使用各种解析和非参数表示形式的测量材料
我们表明，我们的框架概括了先人基于笔画的图像和材料配方的工作，以及从联合双边过滤中得出的方法，同时在鲁棒性和效率方面提供了显着改进。

编辑框架

我们提出了一个编辑框架，在该框架中，用户可以通过对图像或材料的不同区域执行“粗略”调整来指定编辑，这些图像或材料将传播到所有其他点，并实施将相似编辑应用于外观相似的邻近区域的策略。此策略可确保在应用编辑后，尊重原始数据集中发现的复杂模式，从而使艺术家免于繁琐的过程，因为他们不必仔细选择复杂的区域来执行局部调整。此外，我们发现所传播的编辑内容非常符合艺术家的直觉，因此提供了易于理解的控件。

我们框架的一个好处是，我们专注于执行编辑策略，而不是提出特定的用户界面。这使艺术家可以选择自己喜欢的工作流程和工具来指定初始编辑。我们在图2中通过演示对为演示清晰而选择的简单HDR图像执行的曝光调整来说明这一方面。艺术家可以选择用几个笔触快速在不同区域上绘制编辑，而无需调整其余图像。我们将这些编辑称为“稀疏编辑”。然后，我们的算法会将此类编辑内容传播到图片的所有其他区域；请注意，在这种情况下，天空和两栋不相连的建筑物如何进行适当的调整。为了控制传播，艺术家只需编辑更多区域，例如使图2中的左塔变暗。与在Photoshop中进行类似编辑（即使在这张简单图片中）所需的几分钟相比，执行这些调整要花费几秒钟。为了获得更多控制权，艺术家可以通过应用所需的任何编辑来快速调整整个图像。我们将这些编辑称为“密集编辑”。我们的编辑政策的一个好处是，它允许艺术家以非常不精确的输入来执行操作，而这些输入不遵守数据中发现的复杂图案和边缘。图2（右）显示了一个这样的编辑，其中艺术家对建筑物进行了均匀的曝光调整并在天空中绘制渐变。请注意这些编辑有多粗糙，尤其是它们如何不尊重图像边缘。我们的修改政策只会对这些修改进行完善，以尊重数据中的模式。我们的算法在外观非常复杂的图像上也能很好地工作，例如图1所示的花和雾场景，其中不连续的区域，柔和的边缘，雾渐变和复杂的图案使普通的编辑工具变得不切实际。

尽管我们没有进行任何正式的用户研究，但我们发现稀疏编辑足以满足对简单图像或材质的简单调整。先前的工作仅通过提出基于笔划的界面来将重点仅放在此工作流程上，该界面将支持的编辑限制为仅对每个笔划进行恒定的修改，并且要求输入内容与绘制的像素完全相同。在结构更复杂的数据集上，我们发现精确指定编辑变得太麻烦了，并且使用不精确的密集输入会明显更快，更自然。这也使我们能够自然地施加我们想要的任何编辑，不仅是每个笔划的不断修改，还包括渐变更改，艺术滤镜等。

编辑定义

在我们的框架下，在点 $i$ 位置编辑后的外观 $a_i^{‘}$ ，由原始的 $a_i$ 应用上编辑方程 $a_i^{‘} = f(a_i; e_i)$ 计算得到。该方程由该点的编辑参数 $e_i$ 控制。对于图像来说， $a_i$ 包括每个像素点的颜色值，对于空间变化的材料，它包含每个表面位置的基础BRDF模型的参数。艺术家在图像或材料的不同区域中指定其所需编辑 $g_i$ 的参数，其中 $w_i$ 表示用户偏好的强度，介于0和1之间。

追随前人的工作，我们的框架通过传播参数 $e$ 而不是最终外观值来支持任意编辑，从而使我们的编辑方式独立于所应用的特定编辑。因此我们的框架可以看做一个函数 $T: {g_i, w_i} \to {e_i}$ ，该函数通过执行我们的编辑政策，将用户编辑传播到最终编辑。图4显示了图2中执行的用户输入和曝光调整的最终值。在我们的原型中，我们测试了图像的曝光，对比度，饱和度和色温调整，以及材料参数的缩放和偏移。

外观距离

为了找到外观相似的区域，我们的方法需要计算两点之间的外观距离。我们把每个位置的特征向量之间的 $L^2$ 距离看做这个距离。

对于图像，特征向量由像素颜色以及像素周围固定大小的邻域中颜色的平均和标准偏差（对于我们的结果为3×3）组成，以解决纹理变化。按照先前的工作，在Lab颜色空间中为低动态范围的图像计算颜色特征，而为高动态范围的图像计算这些值的对数，以解决较大的外观变化。纹理度量用于确保颜色变化大但纹理相似的区域收到相同的编辑。尽管我们承认存在更精确的纹理度量，但我们发现这一简单的度量对于我们的应用程序非常有效，并且在将来的工作中将更精确的纹理集成在一起。

对于材料，我们遵循[Pellacini and Lawrence 2007]并将两个BRDF样本之间的距离定义为它们的值的余弦项加权的平均值平方差，并在传入和传出方向上进行积分。这项工作的作者展示了如何通过对特征向量的L2距离进行精确估计，该特征向量是通过对大量来回方向采样BRDF并通过使用PCA减少尺寸数而获得的。

编辑传播

我们将编辑传播形式化为优化问题，通过将传播参数e定义为最小化以下能量函数的参数，将用户编辑g解释为软约束。
$\sum_i \sum_j w_jz_{ij}(e_i-g_j)^2 + \lambda \sum_i \sum_j z_{ij}(e_i – e_j)^2$

$z_{ij} = e^{-\frac{|f_i-f_j|^2}{\sigma_a}} e^{-\frac{|x_i-x_j|^2}{\sigma_s}}$

上式在数据集中的所有点上计算总和， $z_{ij}$ 是样本i和样本j之间的亲和度，是两个高斯乘积，分别是点的空间位置 $x_i$ 与它们的外观向量 $f_i$ 之间的距离。这个能量方程可表示为两个项的加和，其相对贡献由 $\lambda$ 控制。（例如非编辑样本为0，编辑样本为更大的值）与其将这些约束严格地施加在已编辑点上，不如将它们施加在所有由相似性 $z_{ij}$ 捕获的，外观相似的附近点上。这是因为我们期望艺术家不精确地指定编辑，因此我们将这些编辑强加在附近地区。（反正指定的编辑是粗略的，那我们与其严格按照这个粗略的编辑精准定义这一项，还不如把附近区域一起考虑进来）。能量函数的第二项强制执行我们的编辑策略，通过将相似性样本的梯度限制为较小（如亲和力 $z_{ij}$ 所捕获的），确保最终编辑对于相似外观的邻近区域相似。在我们的实现中，我们将这一策略强加于数据中的所有样本对，以确保获得高质量的解决方案。

传播过程由 $\lambda, \sigma_a, \sigma_s$ 三个参数控制。在本篇论文的所有结果中，我们设置 $\lambda = \frac{\sum_i w_i}{n}$ ，确保能量函数的两个项之间的相对贡献大致相同。 $\sigma_a$ 主要取决于被编辑的数据集的类型。对于低动态范围图像，我们使用500；对于HDR辐射图，我们使用0.2；对于材质，我们使用0.2。这些值之间的差异不足为奇，因为针对不同类型的输入，计算得出的特征距离值会发生根本变化。 $\sigma_s$ 是我们在编辑的过程唯一更改的值，因为它取决于指定粗略编辑的用户意图。我们报告归一化为图片大小的 $\sigma_s$ 值。在两个极端情况下，我们将值0.05用于不精确的密集编辑以维持其基本结构，而将10用于非常稀疏的编辑尽可能传播。对于一个600×400的图像，这些大致相当于90个像素和整个图像。

尽管以前已经提出了用于外观编辑的用于编辑传播的优化公式，但是我们的方法在三种方式上根本不同。首先，我们在优化过程中明确考虑了用户错误，从而允许艺术家处理复杂自然图像中必要的不精确输入。其次，在先前的工作中描述的基于笔划的界面实质上等于解决了软选择问题，其中通过在与这种笔划相对应的区域中应用笔划调整来计算最终编辑。我们的方法更广泛地支持任何类型的调整，例如更改渐变或应用艺术滤镜，因此不等同于软选择。第三，我们对所有样本对实施我们的编辑策略，而不仅仅是挑选一些样本。我们将在第5节中证明，这使我们的框架在所有测试的数据集中都更加健壮。

算法

能量方程是二次函数，因此可以转换为求解以下线性系统：
$(\sum_j z_{ij}w_j +2\lambda\sum_jz_{ij})e_i – 2\lambda\sum_{j}z_{ij}e_j = \sum_jz_{ij}w_jg_j$
本质上就是对能量方程求导，由于后面一项中有两个与e有关的量，所以求出来导也是两份，所以有2 $\lambda$

转换成矩阵形式：
$(D-Z)e = \frac{1}{2\lambda}ZWg$
e和g是传播和初始化编辑的向量，Z是亲和度矩阵，元素就是 $z_{ij}$ ，W是对角矩阵， $W_{ii} = w_i$ ， $D$ 是对角矩阵 $D_{ii} = d_i = \sum_{j}(z_{ij}+z_{ij}w_j/2\lambda)$ .

（线性系统的意思就是一个方程组，每一个i对应一个方程，因此按照上述定义放进去，两边同时除 $2\lambda$ 前面一项就是De，这也是设置成对角矩阵的原因，每次都只有一项，就是与i对应的哪一项，Ze是后面一项，对于给定的i，计算要牵扯到所有的e，因此变成矩阵形式就是Ze；等式右边和第二项类似，每次都要牵扯所有的e来计算，因此写成ZWg。）

求解这个线性系统是存在问题的，取决于亲和力矩阵的大小，为 $n^2$ ，其中 $n$ 是数据集中的点数；使得整个线性系统的复杂度为 $O(n^3)$ 。例如，对于一百万像素的图像，Z的大小为 $10^{12}$ 个元素。尽管此类矩阵可能包含零个元素，但它稀疏到不足以有效地稀疏地进行有效处理（或存储）。

近似解

我们的方法的关键见解之一是，鉴于数据集中特征向量的自相似性数量，亲和矩阵具有相当大的结构并且接近于低秩。这种自相似性源自相似外观区域的存在。我们通过寻求计算和内存有效的低秩近似来利用亲和矩阵的结构。当在基于内核的学习中使用亲和矩阵时，Williams做出了类似的观察。他们介绍了一种用于计算低秩矩阵近似的随机算法，然后将其应用于加速二进制图像分割。在本文中，我们采用这种近似方法来得出有效的算法，并通过仔细的分析来验证其准确性和效率。

低阶随机逼近

在这里，我们采用与我们的后续用法更接近的方法，得出威廉姆斯论文中引入的近似过程。由于Z接近低秩，因此可以通过考虑m个线性独立的列来很好地近似它，并且有 $m \ll n$ 。设 $U$ 为由这m列组成的 $n\times m$ 的矩阵。采样U等效于计算少量位置对数据中所有其他点的亲和力。为了简化表示，让我们假设所选的m列在Z中排在第一位，其余列在第二位。由于Z是对称的，我们可以写：
$U = \left[\begin{matrix} A\\B\end{matrix}\right] \Rightarrow Z = \left[\begin{matrix} A&B^T\\B&C\end{matrix}\right]$
上式中，A是 $m\times m$ 的所选位置之间的亲和度矩阵，B是 $(n-m)\times m$ 的所选位置与其他所有点之间的亲和度矩阵，C是 $(n-m)\times (n-m)$ 的矩阵，是我们试图从U近似计算的残差矩阵。如果Z的秩为m，那么由于它是正定的，就必然存在一个 $n\times m$ 的矩阵V，使得 $Z = VV^T$ 。通过选择X和Y分别具有与A和B相同的大小，我们有：
$V = \left[\begin{matrix} X\\Y\end{matrix}\right] \Rightarrow Z = \left[\begin{matrix} X\\Y\end{matrix}\right] \left[\begin{matrix} X&X^T\end{matrix}\right] = \left[\begin{matrix} XX^T&XY^T\\YX^T &YY^T\end{matrix}\right]$
比较上述两式，我们可以由 $A = XX^T$ 和 $B = YX^T$ 推导出 $C=YY^T$ ，于是有下式：
$C = YY^T=(YX^T)((X^T)^{-1}X^{-1})(XY^T) = BA^{-1}B^T$
实际上，Z的秩不一定正好是m，但是由于其近似低秩，它可以由一组线性无关的列很好的近似。例如 $Z \approx VV^T ,m \ll n$ 。于是我们可以说， $C \approx BA^{-1}B^T$ 的近似质量可以由A在Z中的舒尔补的F范数测量，即 $|C-BA^{-1}B^T|_F$ 。然而确定如何挑选列，使其线性独立，需要了解整个矩阵。我们则是通过对图像进行分层采样来随机选择一组m列，以确保良好的覆盖率，我们希望该覆盖率比最佳值略大，但仍明显小于n。于是，我们有：
$Z \approx \widetilde{Z} = \left[\begin{matrix} A&B^T\\B &BA^{-1}B^T\end{matrix}\right] = \left[\begin{matrix} A\\B\end{matrix}\right] A^{-1}\left[\begin{matrix} A&B^T\end{matrix}\right] = UA^{-1}U^T$
因此，我们可以通过计算和存储更小的 $n\times m$ 的矩阵 $U$ 来近似 $n*n$ 的矩阵Z。请注意，即使是少量样本也能很好地捕获整个矩阵的结构。在第4.2节中，我们将证明逼近对于全尺寸图像是准确的。

近似编辑传播 从概念上讲，我们通过将亲和度矩阵Z替换为其近似值 $\widetilde{Z}$ 来近似解决我们原来的编辑传播问题，即：
$e \approx \frac{1}{2\lambda}(D-\widetilde{Z})^{-1}\widetilde{Z}Wg$
所有计算都需要在不从其因式表示扩展Z的情况下进行。我们首先从按 $UA^{-1}U^TWg$ 开始计算 $\widetilde{Z}Wg$ 开始，这个式子可以使用从对角矩阵W开始向U移动的小的矩阵向量乘法来计算。接下来，要确定D的对角元素，我们将其定义重写为矩阵符号：
$d = (\frac{1}{2\lambda}ZW + Z)1_n \approx (\frac{1}{2\lambda}UA^{-1}U^TW + UA^{-1}U^T)1_n$
上式中， $1_n$ 表示有n个1的向量。上式也可以作为一组小的矩阵矢量乘法来计算。

现在我们剩下的问题是计算 $(D-\widetilde{Z})^{-1}$ 。我们可以通过使用Woodbury公式避免计算大矩阵的逆，该公式给出了矩阵与矩阵乘积的和的逆的求法。应用到我们的问题有：
$(D-UA^{-1}U^T)^{-1} = D^{-1}-D^{-1}U(-A+U^TD^{-1}U)^{-1}U^TD^{-1}$
上述等式只需计算两个逆，由于 $D$ 是对角矩阵，因此 $D^{-1}$ 计算非常简单。而 $(-A+U^TD^{-1}U)^{-1}$ 只是一个 $m\times m$ 的矩阵，且 $m \ll n$ 。结合上述说明，我们可以得到：
$e \approx \frac{1}{2\lambda}(D^{-1} D^{-1}U(-A+U^TD^{-1}U)^{-1}U^TD^{-1}) (UA^{-1}U^T)Wg$

算法分析

计算复杂度 我们的最终算法执行了数次矩阵向量乘法，其中最大的花费 $O(nm)$ ，所有的求逆中花费最大的是 $O(m^3)$ ，所有的矩阵-矩阵乘法中，最大的一项是 $U^TD^{-1}U$ ，花费 $O(m^2n)$ 。由于 $m \ll n$ ，总的算法花费为 $O(m^2n)$ 。该算法与数据中的点数呈线性关系，与采样的列数呈平方关系。需要的空间大小由矩阵 $U$ 决定，为 $O(nm)$ 个元素，与数据中的点数和采样的列数均成线性关系。这说明我们的近似算法可以很好地与数据中的点数进行缩放，即使考虑 $n^2$ 对成对亲和力来传播编辑时也是如此。

数值精度 我们通过计算图6中64 * 64裁剪图像的全亲和度矩阵来分析该方法的准确性，这是我们可以在内存中容纳的最大亲和度矩阵，并将其与近似值进行比较。图7绘制的是舒尔补的范数，通过亲和力矩阵范数进行了归一化，从而可以更简单的比较 $\sigma_s$ 。请注意，随着我们增加样本数量m，范数如何快速收敛到较小的值。为了了解这如何影响全分辨率图像中传播的编辑的质量，我们计算传播的编辑和使用200个样本获得的参考之间的平均相对误差，作为m的函数。平均值是对高分辨率图像的二十次编辑计算得出的。我们选择200个样本作为参考，因为我们看不到通过添加更多样本而导致的误差改善，并且由于计算完整矩阵对于大型图像而言是不切实际的。受这些结果的激励，我们选择使用100个样本生成本文中的所有结果，这些样本在传播的编辑中始终提供小于1％的误差。此外，在算法的多次执行中计算出的相对误差的方差可忽略不计，这表明随机化对最终编辑的稳定性没有负面影响。

限制经过我们的分析，我们得到了算法的主要局限性，对于太小的空间核，逼近效果不佳。这很容易解释，因为在这种情况下，亲和度矩阵接近对角线，因此矩阵的秩较高，不能由低秩矩阵很好地近似。（过分强调了距离的比重，因此靠近对角线的更接近）但是在我们的框架内，这实际上不是问题，因为我们的目标是将编辑内容传播到较大的空间邻域。我们发现，对于所有大于 $\sigma_s = 0.05$ 的邻域，对应于64×64图像中的14个像素，我们的算法表现良好。换句话说，仅对于在我们的编辑框架内不感兴趣的情况，我们的近似是不准确的，这使得该算法非常适合我们的问题。