这是计算机视觉的课程作业

Introduction

Background

图像滤波在图像处理领域十分重要。数十年来，有许多的滤波算法/滤波器被提出，他们被广泛用于图像去模糊、图像锐化、边缘检测和特征提取。

有许多应用用到了滤波器的一个重要特性——边缘保留（edge-preserving）。边缘保留希望图像中的边缘在经过滤波器处理后能尽可能得被保留下来，不至于显得过于模糊。这一类滤波器通常可以被分为两类，

  1. 一类是全局优化性算法（global optimization based algorithms），比如total variation算法，iterative shrinkage approach算法，relative total variation算法，weighted least squares算法；
  2. 另一类是局部优化性算法（local optimization based algorithms），例如双边滤波算法（Bilateral Filters），导向滤波算法，mutual structure joint算法，curvature算法。

下面我们讨论局部优化性的滤波算法。这类算法通常是输入一个中心像素以及它的一些邻近像素，然后输出一个处理后的结果像素。这其中的处理过程，有线性的处理方式，例如均值滤波、高斯滤波，也有非线性的处理方式，例如中值滤波、双边滤波。下面我们考虑线性的局部优化滤波器。

线性的局部优化滤波器通常有以下两个假设

  1. 图像是分段局部（piecewice）线性的

  2. 算法的输出是原像素在一个局部窗口中的邻近像素的加权和。如果用式子表示即：
    $$
    I_i’ = \sum_{j \in \Omega_i} \omega_{ij} q_j
    $$
    其中 $i$ 是原像素在原图像中的坐标，$I_i’$是输出像素，$\omega_i$ 是局部窗口， $j$ 是邻近像素 $q$ 在局部窗口 $\omega$ 中的坐标， $q_j$ 是邻近像素， $\omega_{ij}$ 是邻近像素 $q_{ij}$ 在窗口中被赋予的权值。

而滤波器输出的结果与原图像之间的差异通常用以下用二范数表示的损失函数（lost function）来描述：

$$
E_i = {|| I_i - I_i’ ||}_2^2
$$

具体到线性的局部优化滤波器的情况，这个式子为

$$
E_i = {(I_i - \sum_{j \in \Omega_i} \omega_{ij} q_j)}^ 2
$$

Problem and Motivation

对于线性局部优化滤波器，我们考虑如下图所示的三种“边缘”：阶梯形边缘（step edge），坡形边缘（ramp edge），屋顶形边缘（roof edge）。

edges
edges

图中每一个格点代表一个像素，格点在三维空间中的高低代表像素值（可能是灰度值，某一通道的像素值）的大小。可以看到图中的像素值变化剧烈，这即是图像中的边缘。而且可以注意到由于边缘的存在，这些图像是连续但不可微的。图中的矩形则表示局部优化滤波器在运算时所用的局部窗口（对应前文中的 $\omega$）。由于通常的局部优化滤波器是取以当前像素为中心的正方形作为窗口 $\omega$， 因此对于阶梯形边缘的情况，像素 $a$ 对应的窗口就是图中红蓝两个矩形的拼接。

下面[1]我们用 $g(x,y)$ 来代表在图像 $(x,y)$ 坐标处的原像素的值，易知在图中所示的边缘点附近，有
$$
g(x+\epsilon, y) \neq g(x-\epsilon, y)
$$
或是
$$
g’(x+\epsilon, y) \neq g’(x-\epsilon, y)
$$
如果在 $(x+\epsilon, y)$ 和 $(x-\epsilon, y)$ 处进行 Taylor 展开[2]，并分别代入 $x-2\epsilon, x+2\epsilon$ 易得
$$
g(x−2\epsilon, y) \approx g(x−\epsilon, y) + \frac{\partial}{\partial x} g(x−\epsilon, y) \cdot (−\epsilon)
$$
和
$$
g(x+2\epsilon, y) \approx g(x+\epsilon, y) + \frac{\partial}{\partial x} g(x+\epsilon, y) \cdot \epsilon
$$

以阶梯状边缘为例，结合上两式可以看到，点 $a$ 左侧点的像素值应该仅与 $a$ 左侧的点相关，$b$ 右侧的点的像素值也仅与 $b$ 右侧的点相关。再结合上文，由于一般的滤波器以当前像素为中心的正方形区域作为窗口，而在图像的边缘附近，这种方法不可避免地将不相关的一大部分像素点包括到计算之中，这样往往会造成边缘的像素发生扩散，显得非常模糊。

事实上我们可以调整窗口的大小，使其不再是一个完整的正方形，而是缩减为与当前像素点相关性更高的区域，例如在阶梯状边缘中，我们针对 $a$ 点就将窗口区域缩减为蓝色矩形，针对 $b$ 点就缩减为是红色矩形。这就是我们的侧边窗口滤波的思想。

Algorithm

Core

这一章我们介绍核心算法。

传统的线性局部优化滤波器的窗口是一当前像素为中心的一个正方形，而在侧边窗口滤波算法中，窗口有八种选择（事实上不仅限于这八种，这个算法是容易被拓展的）。如下图所示，

1
2
3
4
5
┏━━━┯━━━┓
┃ A │ B ┃
┠───┼───┨
┃ D │ C ┃
┗━━━┷━━━┛

我们将原先的正方形四等分为 $A, B, C, D$ 四个正方形，那么窗口的八种选择即 ${A, B, C, D, AB, BC , CD, DA }$ 。

算法将遍历八个窗口，最终选出一个窗口使得以下值最小
$$
E_i = \frac{1}{N_A} (I_i - \sum_{j \in \Omega_i} \omega_{ij} q_j) ^ 2
$$
其中 $N_A = \sum_{j \in {\Omega_i}} \omega_{ij}$ （这里 $\frac{1}{N_A}$ 的作用是归一化）。

Analysis

由于我们的新算法只涉及对窗口的选取，所以很容易被附加到现有的一般算法上。

首先我们在盒子滤波（均值滤波 Box filter）上应用了我们的算法，然后在一些典型的样例上进行了测试。如下图所示，每三个横向的图片为一组测试。对于每一组中的三个图片，左起第一个为原灰度图像，中间为经过算法变换后的沿着过中心的横线的灰度变化图，右起第一个则为中间图像在红色方框处的放大后的图像。容易看到经过改进的盒子滤波更接近原图像的像素值，能更好的保留边缘（edge-preserving）。

analysis
analysis

Evaluation

我们将侧边滤波算法部署到了现有的滤波算法上，并在不同的应用方面进行了实际测试。由于涉及方面过多，时间有限无法深入调研，下面仅进行简要描述并附上实验结果。

对于图中常用的算法缩写，解释如下：

  • BOX 盒子滤波 均值滤波
  • GAU 高斯滤波
  • MED 中值滤波
  • BIL 双边滤波
  • GUI 导向滤波 guided filter

图像平滑

图像平滑用于减少图片的噪声或是产生锯齿较少的图片。大部分平滑化方法基于低通滤波器。

Smoothing is often used to reduce noise within an image or to produce a less pixelated image. Most smoothing methods are based on low pass filters.[3]

image smoothing
image smoothing

图像去噪

image denoising
image denoising

图像增强

图像增强的主要目的是处理给定的图像，以使结果比原始图像更适合特定的应用。它可以突出或锐化图像特征（例如边缘，边界或对比度），从而使图形显示更有助于展示和分析。增强功能不会增加数据的固有信息内容，但是会增加所选功能的动态范围，使得他们可以轻松被检测到。

The principal objective of image enhancement is to process a given image so that the result is more suitable than the original image for a specific application.

It accentuates or sharpens image features such as edges, boundaries, or contrast to make a graphic display more helpful for display and analysis.

The enhancement doesn’t increase the inherent information content of the data, but it increases the dynamic range of the chosen features so that they can be detected easily. [4]

image enhancement
image enhancement

HDR 色调映射

HDR 色彩映射指的是是将高动态范围成像（HDR）的图像映射到有限的范围（例如打印结果，LCD 显示器，投影仪）内。

hdr
hdr

在自然图像上保留结构和去除纹理

matual structure
matual structure

相互结构提取 [5]

structure preserving
structure preserving

Colorization

图像上色是一种借助计算机给单色图像或电影添加颜色的过程。这个过程通常会将图像分割为多个区域并且在多个图像序列中追踪这些区域。

Colonization is a computer-assisted process of adding color to a monochrome image or movie. The process typically involves segmenting images into regions and tracking these regions across image sequences. [6]

colorization
colorization

Complexity Anylysis

显然，在应用侧边窗口算法后，时间复杂度的次数是不变的。但由于多遍历了几个子窗口，时间复杂度应当是原先的常数倍。具体地，我们对不同算法的时间复杂度进行了测试。实验环境为

  • 包含有 1 Mega 像素的灰度图
  • 3.5GHz Intel core Xeon® CPU

结果为

Method BOX GAU MED BIL GUI
Original 0.052 0.023 1.16 8.69 0.131
SWF version 0.215 0.23 3.67 26.2 0.431

可以看到耗时为原先的2到10倍不等。

Conclusion

  • 传统的图像处理算法将以像素为中心的正方形作为处理窗口，而我们指出这一取法并不是最优的，我们可以将窗口缩小为原先正方形的一个半边或是角落，从而提出侧边窗口滤波（SWF）。
  • 许多流行的线性、非线性的滤波算法都可以很轻松地在侧边窗口滤波的基础上进行扩展，而且扩展后的算法能更好地保留边缘，提升性能，避免如颜色泄漏的伪像问题。
  • 基于窗口的操作近些年来在计算机视觉、包括卷积神经网络在内的机器学习领域内被广泛使用。而 SWF 的一些原则，例如将操作窗口的边缘或是角落对齐到待操作像素，虽然看起来微不足道，但实际上扎根于许多算法的基本假设。我们的理论分析和在最新应用领域的实验都证明了其有效性。我们相信 SWF 原则会使更多的应用受益。

  1. 事实上，我认为原文中这一部分的说明不严谨，不够令人信服 ↩︎

  2. 函数 $f$ 在 $a$ 点进行泰勒展开：$f(x) = \sum_{n=0}^{\infty} \frac{f^{(n)}(a)}{n!} (x - a)^n$ ↩︎

  3. https://caligari.dartmouth.edu/doc/idl/html_6.2/Smoothing_an_Image.html ↩︎

  4. http://www.eie.polyu.edu.hk/~enyhchan/imagee.pdf ↩︎

  5. http://www.cse.cuhk.edu.hk/leojia/projects/mutualstructure/index.html ↩︎

  6. https://www.researchgate.net/publication/2896183_Colorization_using_Optimization ↩︎