计算机视觉基础: Filtering (滤波)

Introduction

在数字图像处理中,滤波是一个基本且关键的操作。滤波不仅用于增强图像质量,还在诸如去噪、边缘检测和图像分割等高级任务中扮演着重要角色。本文将简单的探讨线性与非线性滤波的基本概念、实现方法及其在计算机视觉中的应用。

现实图像在数字世界的表示

我们知道,图片实际上就是一个颜色的强度在一个点阵上的值,比如灰度图可以说成是一个点阵上每个点上的光线强度。彩色图,通常就是一个点阵里每个点上红光绿光蓝光(RGB)的光线强度。而这个强度值在计算机中通常用uint8,也就是0-255表示。

比如我们拿灰度图做例子,即只有一个通道,大小为M x N的图片,就可以很自然的表示为 I(X, Y),其中 (X, Y) ∈ ([1, M], [1, N])

图像的处理

获得图像的数学表示后,我们可以通过数学运算对图像进行各种处理。根据操作是针对函数的定义域(domain)还是值域(range),图像处理操作大致可以分为以下两类:

Warping (变形)

变形操作涉及对图像的空间结构进行修改,如旋转、缩放和扭曲。这类操作改变了函数的定义域,使得图像在几何上发生变换。例如,图像校正就是一种变形操作,它用于消除镜头畸变,确保图像中的直线在变换后仍然保持直线。

Filtering (滤波)

滤波操作则是对图像的像素值进行修改,改变函数的值域。这类操作包括图像增强(如锐化、对比度调整)以及特定问题的解决(如模式识别、对象检测)。

Point Operation (点运算)

点运算是最基本的滤波操作,它对图像中的每个像素独立应用一个函数:

I(X,Y)=g(I(X,Y))I'(X, Y) = g(I(X, Y))

Credit: Ioannis (Yannis) Gkioulekas (CMU)

其中 g(x)g(x) 是应用于每个像素值的操作。例如:

  • g(x)=xcg(x) = x - c 可以使图像变暗;
  • g(x)=xcg(x) = \frac{x}{c} for (c>1)( c > 1 )可以降低对比度;
  • g(x)=xcg(x) = \frac{x}{c} for (c<1)( c < 1 )可以增加对比度。


Neighborhood operation (邻域运算)

邻域运算则考虑像素周围的邻域信息,对输出像素进行计算:

I(X,Y)=g(I(Xk:X+k,Yk:Y+k))I'(X, Y) = g(I(X - k : X + k, Y - k : Y + k))

Credit: Ioannis (Yannis) Gkioulekas (CMU)

这里,k=(M1)/2k = (M - 1)/2 M×MM \times M 是邻域的大小,且一般来说假设M为奇数,假设 M 为奇数的主要可以让滤波更加的简单直观。例如,无论从左到右还是从右到左,应用奇数尺寸滤波器的结果都是一样的。

同时邻域运算比点运算更强大,因为它考虑了局部区域的信息。

Linear Filter (线性滤波)

但不管是点运算还是邻域运算,这些操作都可被分为线性(linear)和非线性(non-linear)。

其中线性滤波是滤波操作中最常见的一类,它通过一个线性滤波器(Kernel)对图像进行处理。滤波器通常表示为一个 M×MM \times M 的矩阵 F(X,Y)F(X, Y) ,其中心位于滤波器的中心位置。线性滤波的输出可以通过相关运算或卷积运算来实现。

Correlation

Correlation是线性滤波的一种基本形式,计算方式如下:

 I(X,Y)=i=kkj=kkF(i,j)I(X+i,Y+j)I'(X, Y) = \sum_{i=-k}^{k} \sum_{j=-k}^{k} F(i, j) \cdot I(X + i, Y + j)

复杂度

如果m不是很大,那么复杂度为O(n2)O(n^2)

如果m接近n,那么复杂度为O(n4)O(n^4)

Convolution (卷积)

卷积(Convolution)是一种类似与Correlation的数学运算,但是他有更多数学上的特性。

在实际操作中,通常通过旋转滤波器180度后再进行Correlation来实现卷积。

 I(X,Y)=i=kkj=kkF(i,j)I(X+i,Y+j)I'(X, Y) = \sum_{i=-k}^{k} \sum_{j=-k}^{k} F(-i, -j) \cdot I(X + i, Y + j)

或者可以表示为:

 I(X,Y)=i=kkj=kkF(i,j)I(Xi,Yj)I'(X, Y) = \sum_{i=-k}^{k} \sum_{j=-k}^{k} F(i, j) \cdot I(X - i, Y - j)

比较Correlation和Convolution

如果是Correlation,那么 I(1,1)=1a+2b+3c+4d+5e+6f+7g+8h+9iI'(1, 1) = 1a + 2b + 3c + 4d + 5e + 6f + 7g + 8h + 9i

如果是Convolution,那么 I(1,1)=9a+8b+7c+6d+5e+4f+3g+2h+1iI'(1, 1) = 9a + 8b + 7c + 6d + 5e + 4f + 3g + 2h + 1i

Boundary Effects (边际效应)

其实我们可以发现,当滤波器放置在图像边缘附近会导致滤波器部分超出图像范围

为处理这种情况,常用的方法包括:

  • 忽略边界 (Ignore/discard):不对边界区域进行运算,但是这种方式会导致输出图像比输入图像小。
  • 零填充 (Zero Paddings):在图像边缘填充零值,使输出图像与输入图像大小相同,但可能引入边界伪影。
  • 假设周期性 (Assume periodicity):将图像视为周期性延展,滤波器超出部分从另一边“绕回”图像。
  • 边界反射:通过反射图像边缘的像素值来填充,使边界区域更加平滑。

卷积的数学特性

前面说到,卷积有很多很好的数学特性。

其中结合律对称性为卷积独有,前四个特性Correlation也有。

Superposition (叠加性)

假设 F1F_1 F2F_2 是两个相同尺寸的滤波器,则:

 (F1+F2)I(X,Y)=F1I(X,Y)+F2I(X,Y)(F_1 + F_2) \otimes I(X, Y) = F_1 \otimes I(X, Y) + F_2 \otimes I(X, Y)

Scaling (缩放性)

假设 FF 是一个滤波器,kk 是一个scalar,则:

 (kF)I(X,Y)=k(FI(X,Y))(kF) \otimes I(X, Y) = k(F \otimes I(X, Y))

Shift Invariance (平移不变性)

卷积运算的输出仅依赖于滤波器覆盖区域的像素值,而不依赖于滤波器在图像中的具体位置。这意味着如果输入图像平移,输出图像也会以相同的方式平移。

Associativity (结合律)

假设 F1F_1 F2F_2 是两个滤波器,则:

 F2(F1I(X,Y))=(F2F1)I(X,Y)F_2 \otimes (F_1 \otimes I(X, Y)) = (F_2 \otimes F_1) \otimes I(X, Y)

Symmetry (对称性)

假设 F1F_1 F2F_2 是两个滤波器,则:

 (F1F2)I(X,Y)=(F2F1)I(X,Y)(F_1 \otimes F_2) \otimes I(X, Y) = (F_2 \otimes F_1) \otimes I(X, Y)

常见的线性平滑滤波

Box Filter (箱式滤波器)

又被称为平均滤波器 (average filter or mean filter),简单来说就是把一个方形范围内的像素值做平均就行了。

非旋转对称可分离

然而,箱式滤波器在模拟几何模糊(如焦外模糊)方面表现不佳,因为它将图像中的点扩散为方形区域,而非更自然的圆形或椭圆形。

评价为超级兵

Pillbox Filter (柱状滤波器)

柱状滤波器类似于箱式滤波器,但它在圆形邻域内进行均值计算,而不是方形邻域,所以比较适合模拟几何模糊

旋转对称不可分离

 fr(x,y)={1πr2if x2+y2r20otherwisef_r(x, y) = \begin{cases} \frac{1}{\pi r^2} & \text{if } x^2 + y^2 \leq r^2 \\ 0 & \text{otherwise} \end{cases}

评价为超级兵

Gaussian Filter (高斯滤波)

评价为重量级滤波器,没有高斯滤波我都不知道这课要怎么上

旋转对称可分离非常好低通滤波(low pass)

 Gσ(x,y)=12πσ2exp(x2+y22σ2)G_{\sigma}(x, y) = \frac{1}{2\pi\sigma^2} \exp(-\frac{x^2 + y^2}{2\sigma^2})

其中参数 σ\sigma 为控制滤波器的扩散程度的参数。

  • σ\sigma 越大,平滑程度越高,每个像素的贡献率也会随着距离的增加而逐渐下降。 距离。
  • σ\sigma 越小,平滑程度越低,邻近像素的贡献度下降越快。
  • 如果 σ\sigma 非常小,则完全不会产生模糊/平滑效果。

比如一个3x3的高斯滤波就可以这么计算

低通和高通滤波

高效实现卷积

前面提到了,直接进行卷积/Correlation的时间复杂度为 O(m2n2)O(m^2n^2) , 对于大规模图像和滤波器,这种方法效率较低。为提高效率,可以采用以下两种方法:

Separability (分离再相乘)

对于可分离的高维滤波器,可以把这些滤波器表示为多个一维滤波器的叉积(cross product)。

例如,高斯滤波器是可分离的,可以先对图像的行进行一维高斯滤波,再对列进行一次一维高斯滤波,最后做叉乘



当然并不是所有的滤波器都是可以分离的,比如box和gaussian是可以分离的,但是pillowbox就不行

那么这种情况的的复杂度是多少呢,假设二维

  • 每个像素需要的操作:2m2m 次相乘,一次x,y
  • 总共 2n2n 个像素

所以时间复杂度为O(2mn2)O(2mn^2)

所以分离再乘可以把计算复杂度从 O(m2n2)O(m^2n^2) 降低到 O(mn2)O(mn^2)

Convolution Theorem (卷积定理)

根据卷积定理,我们可以把如下的卷积过程

 i(x,y)=f(x,y)i(x,y)i'(x, y) = f(x, y) \otimes i(x, y)

丢到傅立叶空间

 I(wx,wy)=F(wx,wy)I(wx,wy)\mathcal{I}'(w_x, w_y) = \mathcal{F}(w_x, w_y) \cdot \mathcal{I}(w_x, w_y)

其中,I(wx,wy)\mathcal{I}'(w_x, w_y) , F(wx,wy)\mathcal{F}(w_x, w_y) , I(wx,wy)\mathcal{I}(w_x, w_y) 分别为经过傅立叶变换后的i(x,y)i'(x, y) , f(x,y)f(x, y) i(x,y)i(x, y)

最后再通过iFFT就可以得到卷积后的图像了。

那么这种情况的的复杂度是多少呢

  • 对图像做傅立叶变换: O(n2logn)O(n^2\log{n})
  • 对滤波器做傅立叶变换: O(m2logm)O(m^2\log{m})
  • 相乘: O(1)O(1)

最终的复杂度: O(n2)O(n^2) (至少要比O(m2n2)O(m^2n^2) 好,笑)

Non-Linear Filter (非线性滤波)

Median Filter (中值滤波器)

就是取中间值,简单的去噪滤波器

 I(X,Y)=Median(I(Xk:X+k,Yk:Y+k))I'(X, Y) = \text{Median}(I(X - k : X + k, Y - k : Y + k))

去噪

Bilateral Filter (双边滤波器)

和高斯滤波器相同,但是不同的像素会有不同的权重。

  • 空间距离: 离中心像素越近的像素会有更高的权重,距离越远则权重越低
  • 像素距离:双边滤波器还依赖于像素值的相似性,即越相似的像素会有更高的权重

因为要计算权重,所以这个滤波器的消耗比较多。

 Bσd,σr(x,y,I(X,Y))=12πσd2exp(x2+y22σd2)12πσr2exp((I(X+x,Y+y)I(X,Y))22σr2)B_{\sigma_d,\sigma_r}(x, y, I(X, Y)) = \frac{1}{2\pi\sigma_d^2} \exp\left(-\frac{x^2 + y^2}{2\sigma_d^2}\right) \cdot \frac{1}{2\pi\sigma_r^2} \exp\left(-\frac{(I(X + x, Y + y) - I(X, Y))^2}{2\sigma_r^2}\right)

双边滤波器广泛应用于图像去噪、细节增强和艺术效果生成等领域。例如,连续应用双边滤波器可以产生“卡通化”效果。

去噪

卡通化

ReLU - Rectified Linear Unit

就是把小于0的都变成0,在CNN中通常作为激活函数出现。

Reference

  • Unless specified, all photo are coming from UBC CPSC425 slides @ Leonid Sigal
  • My class note from UBC CPSC425