本站使用了 Pjax 等基于 JavaScript 的开发技术,但您的浏览器已禁用 JavaScript,请开启 JavaScript 以保证网站正常显示!

为什么现在对图像边缘的处理大多数是用卷积而不是傅里叶变换?

这个问题源于知乎上的一个问题,起初也是按照自己的理解尝试着答了以下。但或许问题没多少人关注,截至目前(2019.06.05)为止,总回答数量仅有5个。芒果便将之前的答案整理一下作为记录。

问题理解

卷积是一种运算操作,傅里叶变换是一种变换操作。卷积在图像处理的应用中一个重要作用是卷积滤波,即用一个卷积模板(卷积核/滤波器)去对图像进行滤波。而傅里叶变换在信号处理中往往是变换时域和频域,在图像处理中则是变换空域和频域。那么我先把你说的边缘处理就认为是图像滤波里面的一种好了。如此一来,那问题就理解为是图像处理空域滤波时域滤波的对比了。即问题的的关键就是要搞懂为什么如今的图像滤波处理大多采用空域滤波非频域滤波

空域卷积滤波

首先,先看一下空域滤波,现如今图像处理的空域滤波大多为卷积滤波或者相关滤波,但两者原理相似。理解卷积滤波即可明白原因所在。卷积滤波的基本原理可以简单理解为用一个卷积核与整幅图像进行卷积运算操作,有关卷积更详细的理解可以参考这篇博文c++实现二维卷积。这里附上代码实现

void conv2(int** filter, int **mat, int** res, const int filter_rows, const int filter_cols, const int mat_rows, const int mat_cols)
{
    assert(filter_cols < mat_cols && filter_rows < mat_rows);
    for(int i = 0; i < mat_rows - 1; ++i)
        for (int j = 0; j < mat_cols - 1; ++j)
        {
            int tmp = 0;
            for (int m = 0; m < filter_rows; ++m)
                for (int n = 0; n < filter_cols; ++n)
                    if(0 <= i -m  && i - m < mat_rows && 0 <= j - n && j - n < mat_cols)
                        tmp += filter[m][n] * mat[i - m][j - n];//卷积公式

            res[i][j] = tmp;
        }
}

按照卷积运算,可以计算算法的复杂度

卷积算法复杂度

可以得到,假如原图是MxN大小,卷积核为m*n, 时间复杂度约为M x N x m x n
而卷积核通常比较小,一般有 3 x 3 和 5 x 5等,所以可以卷积滤波算法复杂度可以约为c x M x N ,c为常数

频域傅里叶变换滤波

频域域滤波过程与一般信号处理一样,就是傅里叶变换到时域->在时域进行操作->傅里叶反变换回空域。

  • 原图像大小 M * N
  • 扩充后, 2M * 2 N
  • fft变换到频域, 计算量 2M 2N log( 2M 2N), 即 4M N log (4M N)
  • 对应相乘, 计算量 2M 2N ,即4M N
  • ifft变换回空域, 计算量 2M 2N log( 2M 2N), 即 4M N log (4M N)
  • 所以可以得到频域滤波算法复杂度为4MN + 4M N log (4M N)

即MN(4 + log(4M N))。 所以与 c M N 相比,算法复杂度上频域滤波一般是没什么优势的。

引入高频分量

然后另一个点是,在频域滤波第2(扩充图像)步中,扩充图像回引入高频分量,从而带来干扰。
why-convolution-not-fft.jpg
如图,扩充后,两个边界就会引入高频分量。

两个主要原因

所以芒果认为,一是算法复杂度没有相比卷积没有优势,二是可能会引入高频分量干扰。卷积的方法会更适合在实际应用的处理之中,而傅里叶变换到频域去我觉得更适合用来分析就好。

其他回答

  • 甜草莓
用卷积就是等价于在用傅里叶变换之后做频域乘法.....

时域卷积就是频域相乘,其实就是在滤波= =

不同的地方是卷积核不同会导致频域分量不同,是高频分量通过还是低频分量通过。

其实有不少卷积算法就是用快速傅里叶变换实现的。
  • 斯温
虽然不是很理解,谈谈个人的看法。傅里叶变换通过保留低频特征可以留下边界信息。但这个边界信息应该是整个图像的,而且是一种类似非监督的简单特征变换方法。而卷积,如fcn分割实例得到边缘这一类是有监督的学习过程。二者的区别就好比,前者好似问题的最小二乘,后者是学习算法收敛出来的。前者给定数据就给定了投影方式,单纯的用投影联系变量关系,后者还要建立算法去猜测变量关系。傅里叶变换就是谱,在频域能加以处理,就很类似矩阵谱分解之后的若干trick.什么是trick,就是把握了不同频谱高低与图像构成的关系,抓住这个关系,做了一个看似漂亮的再加工。但trick也终究是trick,它的来源是定型的描述了上述关系,但如何对于不同的样本图片,施加合适:)不同强度与构造:)的trick呢,又不能拍脑袋,就只能靠卷积学习来量化了。因为卷积的特征选择与学习,对特征的处理方式是以量化目标为指导的,该提取哪些,留下哪些并不是臆断的,更为精确。当然,也有人很喜欢那些trick.因为统计或模式识别意义明确,那还要机器学习干啥。不看效果,你是可以随便选的。

尾巴

以上是芒果对此问题的一些理解,可能不太全面,但应该是原因之一。或许还可能是因为编程的难易程度不同,使得卷积滤波相比傅里叶变换更受欢迎。


本文由芒果浩明发布,转载需注明来源。
本文链接:https://mangoroom.cn/algorithm/why-convolution-not-fft.html


 继续浏览关于 图像处理图像处理算法算法卷积傅里叶变换 的文章

 本文最后更新于:2019/06/09 14:29:32,可能因经年累月而与现状有所差异

 引用转载请注明:芒果的Blog > 算法 > 为什么现在对图像边缘的处理大多数是用卷积而不是傅里叶变换?