论文阅读：Guided Linear Upsampling
今天介绍一篇有趣的文章，Guided Linear Upsampling，基于引导的线性上采样，这是发表在 ACM transaction on Graphic 的一篇工作。
Abstract
引导上采样是加速高分辨率图像处理的一种有效方法。在本文中，文章作者提出了一种简单而有效的引导上采样方法。高分辨率图像中的每个像素表示为两个低分辨率像素的线性插值，其索引和权重经过优化以最小化上采样误差。下采样可以联合优化，以防止遗漏小的孤立区域。该方法可以从颜色线模型和局部颜色变换推导得出。与以前的方法相比，该方法可以更好地保留细节效果，同时抑制诸如渗色和模糊等伪影。它高效、易于实现且没有需要仔细微调的参数。我们使用广泛的图像运算符评估所提出的方法，并通过定量和定性分析展示其优势。我们展示了我们的方法在交互式图像编辑和实时高分辨率视频处理方面的优势。特别是对于交互式编辑，联合优化可以预先计算，因此无需硬件加速即可实现即时反馈。
Method
给定一个图像运算符 f f f 和具有 RGB 颜色的高分辨率输入图像 I I I，我们的目标是获得原始输出 𝑇 = 𝑓 ( 𝐼 ) 𝑇 = 𝑓(𝐼) T=f(I) 的近似值 T ^ \hat{T} T^。使用引导上采样方法，我们首先将 f f f 应用于下采样图像 𝐼↓，然后在 I I I 的引导下将结果 𝑇↓上采样到高分辨率输出 T ^ \hat{T} T^。我们需要优化下采样和上采样过程，以最小化 T ^ \hat{T} T^ 和 T T T 之间的差异。
Guided Linear Upsampling
我们首先假设下采样后的输入图像 𝐼↓ 是给定的，或者默认情况下使用规则网格下采样生成。如图 2 所示，为了优化上采样，我们的基本假设是高分辨率目标图像 T T T 的每个像素 p p p 可以通过一对低分辨率像素 ( a , b ) (a,b) (a,b) 的线性插值很好地近似，如下所示：
T ^ p = w a b T a ↓ + ( 1 − w a b ) T b ↓ s . t . a , b ∈ Ω p ↓ (1) \hat{T}_p = w_{ab} T_{a}^{↓} + (1 - w_{ab}) T_{b}^{↓} \quad s.t. \quad a,b \in \Omega_{p↓} \tag{1} T^p=wabTa↓+(1−wab)Tb↓s.t.a,b∈Ωp↓(1)
其中， w a b w_{ab} wab 是加权函数，p↓ 是 p p p 的下采样坐标， Ω p \Omega_{p} Ωp 是 p↓ 的一个小邻域。 T ^ p \hat{T}_p T^p 是原始输出 T p T_p Tp 的估计值。公式（1）包含三个参数 w a b , a , b w_{ab}, a, b wab,a,b，为了最小化上采样误差，需要对这些参数进行优化。用 Θ p = { a , b , w a b } \Theta_{p} = \{a, b, w_{ab} \} Θp={a,b,wab} 表示像素 p p p 的参数，那么 Θ \Theta Θ 是一个 3 × H × W 3 \times H \times W 3×H×W 的张量，包含 T T T 的所有像素的参数。给定 Θ \Theta Θ ，相应的高分辨率输出 T ^ ( Θ ) \hat{T}(\Theta) T^(Θ) 可以很容易地用公式（1）计算出来。
与之前的局部颜色变换方法 [Chen et al. 2016; He et al. 2012; Levin et al. 2007] 一样，文章也假设目标图像可以局部表示为源图像的仿射变换。正如在后面将要解释的那样，在这种情况下，源图像和目标图像可以用同一组参数进行最佳上采样。换句话说，如果对于源图像是最优的，那么它对于目标图像也应该是最优的。因此，为了最小化其上采样误差，可以仅针对源图像求解最优参数。
Θ = arg min Θ ∥ I ^ ( Θ ) − I ∥ (2) \Theta = \argmin_{\Theta} \left \| \hat{I}(\Theta) - I \right \| \tag{2} Θ=Θargmin I^(Θ)−I (2)
其中， I ^ ( Θ ) \hat{I}(\Theta) I^(Θ) 表示源图的上采样结果，假设 Θ p \Theta_{p} Θp 是相互独立的，那么每个像素的参数可以独立优化：
Θ p = arg min Θ p ∥ w a b I a ↓ + ( 1 − w a b ) I b ↓ − I p ∥ (3) \Theta_{p} = \argmin_{\Theta_p} \left \| w_{ab} I_{a}^{↓} + (1 - w_{ab}) I_{b}^{↓} - I_{p} \right \| \tag{3} Θp=Θpargmin wabIa↓+(1−wab)Ib↓−Ip (3)
这是一个组合优化问题，通常很难解决。幸运的是，在文章中， Ω p ↓ \Omega_{p↓} Ωp↓ 是一个小邻域（在我们的实验中是一个 3×3 的窗口），所以很容易枚举所有可能的像素对。对于每个选定的像素对 ( a , b ) (a,b) (a,b)，权重参数可以表示为：
w a b = ( I p − I b ↓ ) ( I a ↓ − I b ↓ ) ∥ I a ↓ − I b ↓ ∥ 2 + ϵ (4) w_{ab} = \frac{(I_{p} - I_{b}^{↓})(I_{a}^{↓} - I_{b}^{↓})}{\left\| I_{a}^{↓} - I_{b}^{↓} \right\|^{2} + \epsilon} \tag{4} wab= Ia↓−Ib↓ 2+ϵ(Ip−Ib↓)(Ia↓−Ib↓)(4)
- 图 3
图 3 展示了一个从下采样图像上采样回原图像的示例。上述简单方法取得了惊人的好结果。即使对于像 32 倍这样的大比例，原始图像的细节也几乎可以完美地重建。相比之下，即使对于较小的比例，JBU（联合双边上采样）的结果也明显模糊。
Efficient Computation
上述优化算法的复杂度和局部邻域的像素数量成平方关系，对于一个 3 × 3 3 \times 3 3×3 的局部邻域，需要检查的像素对有 36 对，对于一个高分辨率的图像来说，这个算法的复杂度依然很高，为了进一步提升运算效率，文章发现没有必要枚举所有的像素对 ( a , b ) (a, b) (a,b)。相反，我们可以首先将 a a a 固定为与 I p I_p Ip 颜色最相似的像素，然后仅针对公式（3）优化 b , w a b b, w_{ab} b,wab。这样，复杂度可以降低到与 ∣ Ω p ↓ ∣ |\Omega_{p↓}| ∣Ωp↓∣ 成线性关系。由于 a a a 在颜色空间中与 I p I_{p} Ip 接近，所以对于在颜色线上的投影，近似误差应该很小。很容易看出，如果 I p I_p Ip 在由 I a ↓ I_{a↓} Ia↓ 和 I b ↓ I_{b↓} Ib↓ 确定的颜色线上，那么公式（4）中的插值权重就简化为：
w a b = ∥ I p − I b ↓ ∥ ∥ I p − I a ↓ ∥ + ∥ I p − I b ↓ ∥ + ϵ (5) w_{ab} = \frac{ \left \| I_{p} - I_{b}^{↓} \right \|} { \left \| I_{p} - I_{a}^{↓} \right \| + \left \| I_{p} - I_{b}^{↓} \right \| + \epsilon} \tag{5} wab= Ip−Ia↓ + Ip−Ib↓ +ϵ Ip−Ib↓ (5)
这可以更有效地计算，并且结果保证在 [0,1] 范围内。由于不经过的颜色线被选中的可能性较小，所以上述近似对我们方法的质量影响很小。如图 3 所示，与我们的原始方法相比，上述加速方法不会引入明显的差异，但复杂度要低得多。因此，在下面的内容中，我们将默认使用加速后的方法。
最终的上采样方法如算法 1 所述。它非常简单且高效。 Ω p ↓ \Omega_{p↓} Ωp↓ 通常选择为一个 3×3 的窗口，所以对于每个像素，只需要检查 9 个像素对。如果我们固定 w a b w_{ab} wab 为 1，那么第 3 行的优化就不必要了，并且 T ^ p \hat{T}_p T^p 将等于 T a ↓ T_{a}^{↓} Ta↓ 。我们将这种特殊情况的方法称为引导最近邻上采样（Guided Nearest Upsampling，GNU）。如图 4 所示，GNU 缺乏恢复自然图像的斜坡边缘和平滑变化的能力，从而产生块状效果和错误轮廓，而使用 GLU（我们的方法）可以有效地消除这些问题。
- 算法 1
- 图 4
Downsample Optimization
- 图 5
对于大的下采样比例，由于规则网格下采样，孤立的细结构和小区域可能会完全丢失。在这种情况下，上采样过程将不可能恢复原始内容。图 5 展示了这样一种情况。给定 GLU 上采样器 Ψ ( I ↓ , Θ ) \Psi(I^{↓},\Theta) Ψ(I↓,Θ)，我们可以将下采样过程表述为一个优化问题，旨在最小化源图像的自上采样误差。实际上，由于是未知的，下采样和上采样需要联合优化。
I ↓ , Θ = arg min I ↓ , Θ ∥ I − Ψ ( I ↓ , Θ ) ∥ (6) I^{↓},\Theta = \argmin_{I^{↓},\Theta} \left \| I - \Psi( I^{↓},\Theta ) \right \| \tag{6} I↓,Θ=I↓,Θargmin I−Ψ(I↓,Θ) (6)
公式 (6) 使得下采样图像 I ↓ I^{↓} I↓ 的每一个像素，都来自原始图像 I I I，在以前的方法中， I ↓ I^{↓} I↓ 的每个像素通常是从 I I I 的多个像素中滤波得到的，以减少混叠伪影。对于我们的方法，下采样中的滤波可能会使上采样后的图像明显模糊，因为它会收缩颜色线的端点，这对图像细节是不利的。
公式（6）可以通过迭代优化 I ↓ I^{↓} I↓ 和 Θ \Theta Θ 来求解。给定 I ↓ I^{↓} I↓，上采样参数 Θ \Theta Θ 可以按照算法 1 求解。为了优化下采样，我们首先计算像素级误差图 E E E, $E_{p} = \left | I_{p} - \hat{I}_{p} \right | $。显然，误差大的像素一定是那些不能被 I ↓ I^{↓} I↓ 很好地表示的像素，因此需要通过替换一些现有的像素将它们添加到 I ↓ I^{↓} I↓ 中。由于 I ↓ I^{↓} I↓ 中的每个像素可能用于插值 I I I 的多个像素，上述操作可能不会减少总误差。因此，我们采用试错法，如果替换 I ↓ I^{↓} I↓ 中的一些像素不能减少总误差，被替换的像素将被回滚。
- 图 6
图 6 说明了我们方法的过程，更多细节在算法 2 中描述。试错过程针对具有大误差 ε \varepsilon ε 的像素的每个连通区域 C i C_{i} Ci 执行。具有大误差的像素尝试被添加到下采样图像中，如果该操作可以减少总误差，则该操作将被接受，否则将被回滚。对于映射到相同低分辨率像素位置$q \in I^{↓} $的多个高分辨率像素，选择具有最大误差的像素来替换 q q q 的原始颜色。
如图 5 所示，上述方法可以有效地防止细结构和小区域的丢失。在大多数情况下，它只需要 1 或 2 次迭代就可以收敛，并且在初始化后，只有具有大误差的像素才会被进一步处理，所以只需要稍微多一点的计算量。
- 算法 2
Theoretical Derivation
颜色线模型告诉我们，小区域内像素的颜色在颜色空间中应该大致在同一条线上。因此，该区域中每个像素的颜色必须通过颜色线的两个端点 [ a , b ] [a, b] [a,b] 的线性插值来很好地近似。下采样后，由于高分辨率图像中的信息冗余，可以预期 [ a , b ] [a, b] [a,b] 仍然可以由下采样后的区域中的两个像素很好地表示。结果，原始区域中的每个像素颜色也可以由下采样后的区域中的两个像素进行线性插值，如公式 (1) 所示。
局部颜色变换方法假设输出图像可以局部表示为输入图像的仿射变换，即 T p = A p I p T_{p} = A_{p}I_{p} Tp=ApIp，其中 A p A_{p} Ap 是在图像空间中平滑变化的仿射变换。此外，我们要求运算符近似具有尺度不变性： T p ↓ = A p I p ↓ T_{p}↓ = A_{p}I_{p}↓ Tp↓=ApIp↓。因此，如果使用可以线性插值表示原始图像：
I p = w a b I a ↓ + ( 1 − w a b ) I b ↓ (7) I_{p} = w_{ab} I_{a}^{↓} + (1 - w_{ab}) I_{b}^{↓} \tag{7} Ip=wabIa↓+(1−wab)Ib↓(7)
那么变换后的图像也可以满足：
T p = w a b A p I a ↓ + ( 1 − w a b ) A p I b ↓ = w a b T a ↓ + ( 1 − w a b ) T b ↓ (8) {T}_p = w_{ab}A_p I_{a}^{↓} + (1 - w_{ab}) A_{p} I_{b}^{↓} = w_{ab} T_{a}^{↓} + (1 - w_{ab}) T_{b}^{↓} \tag{8} Tp=wabApIa↓+(1−wab)ApIb↓=wabTa↓+(1−wab)Tb↓(8)
Edge Recovery
典型的图像边缘可以分为三种类型：阶跃边缘、斜坡边缘和屋脊边缘 [Koschan 和 Abidi 2005；Yin 等人 2019]。对于自然图像，大多数边缘应该是连接两个区域的斜坡边缘。显然，斜坡边缘的过渡效果可以通过两个区域颜色的线性插值很好地表示。因此，通过仅插值两个像素，GLU 可以很好地恢复原始图像的边缘。相比之下，使用 GNU 只能恢复阶跃边缘，因此会引入明显的伪影，如图 4 所示。
一个自然的问题是，通过插值更多的像素是否可以实现进一步的效果提升。实际上，公式（1）可以更一般地表示为
T ^ p = ∑ q ∈ Ω p ↓ w q T q ↓ (9) \hat{T}_p = \sum_{q \in \Omega_{p}^{↓}} w_{q} T_{q}^{↓} \tag{9} T^p=q∈Ωp↓∑wqTq↓(9)
其中 w q w_{q} wq 是归一化的权重。有趣的是，这正是 JBU（联合双边上采样）的形式。虽然没有进行测试，但我们认为没有必要采用更多的像素进行插值。涉及更多的像素不仅会使优化更加困难，还可能导致过拟合和外推，这两者都会降低结果质量。
Detail Preservation
我们的方法隐含地利用了局部颜色变换来传递上采样参数。然而，需要注意的是，与之前的方法如引导滤波 [He 等人，2012] 和 BGU 不同，我们的方法不要求变换在图像空间或双边空间中是平滑的。因此，它可以更好地保留目标图像的细节效果，同时避免过度平滑导致的渗色伪影。
我们方法的一个潜在问题是缺乏明确的平滑性约束。虽然保持平滑对于大多数图像处理操作符很重要，但我们发现我们的方法在大多数情况下独立地对每个像素进行操作也能很好地工作。这主要是因为线性插值模型可以很好地近似原始源图像的外观，它作为一个平滑的引导图，如果目标图像与源图像具有相似的局部亲和力，可以抑制不光滑的伪影。然而，如果源图像和目标图像的像素亲和力有显著差异（例如，当在目标图像中引入新的边缘时），可能会产生不光滑的伪影。实际上，这是我们方法的主要局限性。
Limitations
与 JBU 和 BGU 一样，我们方法的一个基本假设是源图像和目标图像具有几乎相同的局部亲和力，即源图像中颜色更相似的像素在目标输出中应该具有更相似的颜色。因此，我们的方法不适用于可能在目标图像中引入新边缘的应用。图 14 展示了这样一个例子。新边缘的亲和力与源图像有很大不同，因此不在联合优化的范围内。在更一般的情况下，由于不同的局部亲和力，我们的方法可能会产生不光滑的边缘。如图 15 所示，由于物体与背景颜色相似，我们的方法无法准确地恢复清晰的遮罩边缘。
与添加新边缘不同，去除边缘通常不会给我们的方法带来问题，因为得到的像素仍然可以由相邻像素插值，所以像抠图和平滑这样的应用可以得到很好的支持。相比之下，BGU 可能会坚持保留源图像的边缘和局部结构，所以对于去除边缘的应用，它可能会产生伪影，如图 8 所示。
由于在处理新边缘方面的限制，我们的方法不适用于可能极大地改变局部图像结构的应用，例如最近基于学习的风格迁移方法 [Park 等人，2020；Zhu 等人，2017]。这是包括 JBU 和 BGU 在内的通用引导上采样方法的一个共同局限性。图 16 展示了一些例子。如图所示，对于像马变斑马这样的情况，BGU 可能完全忽略新边缘，而我们的方法会导致不光滑的伪影。实际上，由于对于新边缘，源图像中没有引导信息，如果没有任何特定领域的先验知识，就无法得到好的结果，所以在这种情况下使用基于学习的方法应该更好。
对于实际应用，一个实际问题是找到一个适合低分辨率处理的图像运算符。如图 10 所示，输入图像的尺度可能对一些图像处理方法的输出有很大影响。例如，我们发现 BackgroundMattingV2 在应用于 8 倍下采样的输入时会产生明显更多的错误，因为它最初是为高分辨率视频设计的。另一个例子是光流估计 [Teed 和 Deng，2020]，其准确性受图像分辨率的极大影响，并且在上采样后需要特殊处理。如何调整这些方法以更好地进行低分辨率图像处理是一个遗留问题。