查看: 2780|回复: 3|关注: 0

[已答复] 图像高斯滤波的可分离性与算法复杂度

[复制链接]

论坛优秀回答者

入门

429 麦片

财富积分


50500


1

主题

1022

帖子

90

最佳答案
  • 关注者: 15
发表于 2015-7-8 08:58:00 | 显示全部楼层 |阅读模式
本帖最后由 zype1128 于 2015-7-8 17:26 编辑

严格来说 我问的问题和matlab无关。。。
我要用vc(不借助opencv)实现图像的高斯滤波。。。
请各位版主大大表删俺第一次发帖子。。。

其实已经做出来了,但是。。。
很多资料里头提到一句(如度娘百科):
由于高斯函数可以写成可分离的形式,因此可以采用可分离滤波器实现来加速。所谓的可分离滤波器,就是可以把多维的卷积化成多个一维卷积。具体到二维的高斯滤波,就是指先对行做一维卷积,再对列做一维卷积。这样就可以将计算复杂度从O(M*M*N*N)降到O(2*M*M*N),M,N分别是图像和滤波器的窗口大小。

我理解为:卷积就相当于是加权平均,如果滤波器窗口大小为N*N,对每个像素进行一次滤波,就要做N*N次乘法和(N*N-1)次加法。那对M*M的图像来说,O(M*M*N*N)的计算复杂度也就可以得出来了。

O(2*M*M*N)是怎么回事?恕我愚钝无法理解。。。

假设高斯核大小为3*3,对图像的一个点进行高斯模糊,需要多少次计算?

可以给出测试数据:

  1. % I为图像,对中心点进行计算
  2. I = [2 2 2; 3 2 3; 4 6 4];
  3. % F为二维高斯核,用杨辉三角形近似
  4. F = [1 2 1; 2 4 2; 1 2 1]/16;
复制代码


可以写出加权平均的算式:
(2*1+2*2+2*1+3*2+2*4+3*2+4*1+6*2+4*1)/16    =     3

有结论:高斯核大小为N*N时,高斯滤波需要N*N次乘法和N*N-1次加法。(除法忽略)

如果按照一维分离滤波。。先做一维,就已经N*(N次乘法+(N-1)次加法)了,再对新的向量进行处理,又得做(N次乘法+(N-1)次加法),乘法次数是肯定超过N*N了。

就算考虑到一维高斯轴对称的性质,也就能把数据量降低一半而已。。。

那个O(2*M*M*N)怎么算的。。。求大神给出方法。。。






015_PicImg.jpg
014_PicImg.jpg
回复主题 已获打赏: 0 积分

举报

论坛优秀回答者

入门

429 麦片

财富积分


50500


1

主题

1022

帖子

90

最佳答案
  • 关注者: 15
 楼主| 发表于 2015-7-8 16:12:05 | 显示全部楼层
纳尼 没人回答么。。。
求大神。。。
回复此楼 已获打赏: 0 积分

举报

新手

5 麦片

财富积分


050


1

主题

6

帖子

0

最佳答案
发表于 2015-9-5 11:17:13 | 显示全部楼层
楼主为何不用opencv库来实现呢,我说的是利用opencv库来自己实现高斯滤波。我做过实验,可分离的模板高斯滤波速度确实比2次for循环的快很多。说实在的,如果模板不可分,时间复杂度就是M*N*k,M,N为图像的高、宽。k为模板长度。如果用可分离,我理解是一个K*k变为k*2,不知道对不对。
回复此楼 已获打赏: 0 积分

举报

论坛优秀回答者

入门

429 麦片

财富积分


50500


1

主题

1022

帖子

90

最佳答案
  • 关注者: 15
 楼主| 发表于 2015-9-5 11:36:23 | 显示全部楼层
derk1992 发表于 2015-9-5 11:17
楼主为何不用opencv库来实现呢,我说的是利用opencv库来自己实现高斯滤波。我做过实验,可分离的模板高斯滤 ...

我就是不理解这个k*2是怎么来的
高斯模板长度是k
那这个长度为k的向量 是要和 窗口里面的每个向量 都要做一次卷积的啊
每次都是k,再重复k次,还是k*k啊
回复此楼 已获打赏: 0 积分

举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

关闭

站长推荐上一条 /5 下一条

快速回复 返回顶部 返回列表