搜索
当前位置: 678彩票官网 > 递归算法 >

高斯模糊算法的全面优化过程分享(一)

gecimao 发表于 2019-04-13 12:56 | 查看: | 回复:

  仔细观察和理解上述公式,在forward过程中,n是递增的,因此,如果在进行forward之前,把in数据先完整的赋值给w,然后式子(9a)就可以变为:

  在backward过程中,n是递减的,因此在backward前,把w的数据完整的拷贝到out中,则式子(9b)变为:

  从编程角度看来,backward中的拷贝是完全没有必要的,因此(1b)可以直接写为:

  从速度上考虑,浮点除法很慢,因此,我们重新定义b1=b1/b0,b2=b2/b0,b3=b3/b0,最终得到我们使用的递归公式:

  上述公式是一维的高斯模糊计算方法,针对二维的图像,正确的做法就是先对每个图像行进行模糊处理得到中间结果,再对中间结果的每列进行模糊操作,最终得到二维的模糊结果,当然也可以使用先列后行这样的做法。

  另外注意点就是,边缘像素的处理,我们看到在公式(a)或者(b)中,w[n]的结果分别依赖于前三个或者后三个元素的值,而对于边缘位置的值,这些都是不在合理范围内的,通常的做法是镜像数据或者重复边缘数据,实践证明,由于是递归的算法,起始值的不同会将结果一直延续下去,因此,不同的方法对边缘部分的结果还是有一定的影响的,这里我们采用的简单的重复边缘像素值的方式。

  由于上面公式中的系数均为浮点类型,因此,计算一般也是对浮点进行的,也就是说一般需要先把图像数据转换为浮点,然后进行高斯模糊,在将结果转换为字节类型的图像,因此,上述过程可以分别用一下几个函数完成:

  CalcGaussCof,这个很简单,就按照论文中提出的计算公式根据用户输入的参数来计算,当然结合下上面我们提到的除法变乘法的优化,注意,为了后续的一些标号的问题,我讲上述公式(a)和(b)中的系数B写为b0了。

  由上述代码可见,B0+B1+B2+B3=1,即是归一化的系数,这也是算法可以递归进行的关键之一。

  接着为了方便中间过程,我们先将字节数据转换为浮点数据,这部分代码也很简单:

  水平方向的前向传播按照公式去写也是很简单的,但是直接使用公式里面有很多访问数组的过程(不一定就慢),我稍微改造下写成如下形式:

  有了GaussBlurFromLeftToRight的参考代码,GaussBlurFromRightToLeft的代码就不会有什么大的困难了,为了避免一些懒人不看文章不思考,这里我不贴这段的代码。

  那么垂直方向上简单的做只需要改变下循环的方向,以及每次指针增加量更改为Width*3即可。

  那么我们来考虑下垂直方向能不能不这样处理呢,指针每次增加Width*3会造成严重的Cachemiss,特别是对于宽度稍微大点的图像,我们仔细观察垂直方向,会发现依旧可以按照Y--X这样的循环方式也是可以的,代码如下:

  就是说我们不是一下子就把列方向的前向传播进行完,而是每次只进行一个像素的传播,当一行所有像素都进行完了列方向的前向传播后,在切换到下一行,这样处理就避免了Cachemiss出现的情况。

  注意到列方向的边缘位置,为了方便代码的处理,我们在高度方向上上下分别扩展了3个行的像素,当进行完中间的有效行的行方向前向和反向传播后,按照前述的重复边缘像素的方式填充上下那空出的三行数据。

  在有效的范围内,上述浮点计算的结果不会超出byte所能表达的范围,因此也不需要特别的进行Clamp操作。

  正如上所述,分配了Height+6行的内存区域,主要是为了方便垂直方向的处理,在执行GaussBlurFromTopToBottom之前按照重复边缘的原则复制3行,然后在GaussBlurFromBottomToTop之前在复制底部边缘的3行像素。

  至此,一个简单而又高效的高斯模糊就基本完成了,代码数量也不多,也没有啥难度,不晓得为什么很多人搞不定。

  按照我的测试,上述方式代码在一台I5-6300HQ2.30GHZ的笔记本上针对一副3000*2000的24位图像的处理时间大约需要370ms,如果在C++的编译选项的代码生成选项里的启用增强指令集选择--流式处理SIMD扩展2(/arch:sse2),则编译后的程序大概需要220ms的时间。

  我们尝试利用系统的一些资源进一步提高速度,首先我们想到了SSE优化,关于这方面Intel有一篇官方的文章和代码:

  我只是简单的看了下这篇文章,感觉他里面用到的计算公式和Deriche滤波器的很像,和本文参考的Recursiveimplementation不太一样,并且其SSE代码对能处理的图还有很多限制,对我这里的参考意义不大。

  我们先看下核心的计算的SSE优化,注意到GaussBlurFromLeftToRight的代码中,其核心的计算部分是几个乘法,但是他只有3个乘法计算,如果能够凑成四行,那么就可以充分利用SSE的批量计算功能了,也就是如果能增加一个通道,使得GaussBlurFromLeftToRight变为如下形式:

  而对于Y方向的代码,你仔细观察会发现,无论是及通道的图,天然的就可以使用SSE进行处理,详见下面的代码。

  第二个函数ConvertBGR8U2BGRAF按照上述分析需要重新写,因为需要增加一个通道,新的通道的值填0或者其他值都可以,但建议填0,这对有些SSE函数很有用,我把这个函数的SSE实现共享一下:

  可能有人注意到了intBlock=(Width-2)/BlockSize;这一行代码,为什么要-2操作呢,这也是我在多次测试发现程序总是出现内存错误时才意识到的,因为_mm_loadu_si128一次性加载了5+1/3个像素的信息,当在处理最后一行像素时(其他行不会),如果Block取Width/BlockSize,则很有可能访问了超出像素范围内的内存,而-2不是-1就是因为那个额外的1/3像素起的作用。

  和上面的4通道的GaussBlurFromLeftToRight_SSE比较,你会发现基本上语法上没有任何的区别,实在是太简单了,注意我没有用_mm_storeu_ps,而是直接使用_mm_store_ps,这是因为,第一,分配Data内存时,我采用了_mm_malloc分配了16字节对齐的内存,而Data每行元素的个数又都是4的倍数,因此,每行起始位置处的内存也是16字节对齐的,所以直接_mm_store_ps完全是可以的。

  最有难度的应该算是ConvertBGRAF2BGR8U的SSE版本了,由于某些原因,我不太愿意分享这个函数的代码,有兴趣的朋友可以参考opencv的有关实现。

  对于同样的3000*2000的彩色图像,SSE版本的代码耗时只有145ms的耗时,相对于普通的C代码有约2.5倍左右的提速,这也情有可原,因为我们在执行SSE的代码时时多处理了一个通道的计算量的,但是同编译器自身的SSE优化220ms,只有1.5倍的提速了,这说明编译器的SSE优化能力还是相当强的。

  比如我们指定openmp使用2个线程,在上述机器上(四核的),纯C版本能优化到252ms,而纯SSE的只能提高到100ms左右,编译器自身的SSE优化速度大约是150ms,基本上还是保持同一个级别的比例。

  对于灰度图像,很可惜,上述的水平方向上的优化方式就无论为力了,一种方式就是把4行灰度像素混洗成一行,但是这个操作不太方便用SSE实现,另外一种就是把水平方向的数据先转置,然后利用垂直方向的SSE优化代码处理,完成在转置回去,最后对转置的数据再次进行垂直方向SSE优化,当然转置的过程是可以借助于SSE的代码实现的,但是需要额外的一份内存,速度上可能和普通的C相比就不会有那么多的提升了,这个待有时间了再去测试。

  前前后后写这个大概也花了半个月的时间,写完了整个流程,在倒过来看,真的是非常的简单,有的时候就是这样。

  本文并没有提供完整的可以直接执行的全部代码,需者自勤,提供一段C#的调用工程供有兴趣的朋友测试和比对(未使用OPENMP版本)。

  后记:后来测试发现,当半径参数较大时,无论是C版本还是SSE版本都会出现一些不规则的瑕疵,感觉像是溢出了,后来发现主要是当半径变大后,B0参数变得很小,以至于用float类型的数据来处理递归已经无法保证足够的精度了,解决的办法是使用double类型,这对于C语言版本来说是秒秒的事情,而对于SSE版本则是较大的灾难,double时换成AVX可能改动量不大,但是AVX的普及度以及.....,不过,一般情况下,半径不大于75时结果都还是正确的,这对于大部分的应用来说是足够的,半径75时,整个图像已经差不多没有任何的细节了,再大,区别也不大了。

  解决上述问题一个可行的方案就是使用Deriche滤波器,我用该滤波器的float版本对大半径是不会出现问题的,并且也有相关SSE参考代码。

本文链接:http://windsorflowers.net/diguisuanfa/25.html
随机为您推荐歌词
推荐文章

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部