文档章节

解析opencv中Box Filter的实现并提出进一步加速的方案(源码共享)。

abcijkxyz
 abcijkxyz
发布于 2016/11/22 16:39
字数 3023
阅读 12
收藏 0
点赞 0
评论 0

     

     本文源代码下载地址(VS2010编写):Box Filter 

  说明:本文所有算法的涉及到的优化均指在PC上进行的,对于其他构架是否合适未知,请自行试验。

      Box Filter,最经典的一种领域操作,在无数的场合中都有着广泛的应用,作为一个很基础的函数,其性能的好坏也直接影响着其他相关函数的性能,最典型莫如现在很好的EPF滤波器:GuideFilter。因此其优化的档次和程度是非常重要的,网络上有很多相关的代码和博客对该算法进行讲解和优化,提出了不少O(1)算法,但所谓的0(1)算法也有优劣之分,0(1)只是表示执行时间和某个参数无关,但本身的耗时还是有区别。比较流行的就是累积直方图法,其实这个是非常不可取的,因为稍大的图就会导致溢出,这里我们解析下 opencv的相关代码,看看他是如何进行优化的。

      首先找到opencv的代码的位置,其在\opencv\sources\modules\imgproc\src\smooth.cpp中。

   

     Box Filter 是一种行列可分离的滤波,因此,opencv也是这样处理的,先进行行方向的滤波,得到中间结果,然后再对中间结果进行列方向的处理,得到最终的结果。

     opencv 行方向处理的相关代码如下:

template<typename T, typename ST>
struct RowSum :
        public BaseRowFilter
{
    RowSum( int _ksize, int _anchor ) :
        BaseRowFilter()
    {
        ksize = _ksize;
        anchor = _anchor;
    }

    virtual void operator()(const uchar* src, uchar* dst, int width, int cn)
    {
        const T* S = (const T*)src;
        ST* D = (ST*)dst;
        int i = 0, k, ksz_cn = ksize*cn;

        width = (width - 1)*cn;
        for( k = 0; k < cn; k++, S++, D++ )
        {
            ST s = 0;
            for( i = 0; i < ksz_cn; i += cn )
                s += S[i];
            D[0] = s;
            for( i = 0; i < width; i += cn )
            {
                s += S[i + ksz_cn] - S[i];
                D[i+cn] = s;
            }
        }
    }
};

  这个代码考虑了多个通道以及多种数据类型的情况,为了分析方便我们重写下单通道时的核心代码。

for(Z = 0, Value = 0; Z < Size; Z++)    
    Value += RowData[Z];
LinePD[0] = Value;

for(X = 1; X < Width; X ++)
{
    Value += RowData[X + Size - 1] - RowData[X - 1];    
    LinePD[X] = Value;               
}

  上述代码中RowData是指对某一行像素进行扩展后的像素值,其宽度为Width + Radius + Radius, Radius是值滤波的半径, 而代码中Size = 2 * Radius + 1,LinePD即所谓的中间结果,考虑数据类型能表达的范围,必须使用 int类型。

      对于每行第一个点很简单,直接用for计算出行方向的指定半径内的累加值。而之后所有点,用前一个累计值加上新加入的点,然后去除掉移出的哪一个点,得到新的累加值。这个方法在很多文献中都有提及,并没有什么新鲜之处,这里不多说。

     按照正常的思维,在列方向的处理应该和行方向完全相同,只是处理的方向的不同、处理的数据源的不同以及最后需要对计算结果多一个归一化的过程而已。事实也是如此,有很多算法都是这样做的,但是由于CPU构架的一些原因(主要是cache miss的增加),同样的算法沿列方向处理总是会比沿行方向慢一个档次,解决方式有很多,例如先对中间结果进行转置,然后再按照行方向的规则进行处理,处理完后在将数据转置回去。转置过程是有非常高效的处理方式的,借助于SSE以及Cache优化,能实现比原始两重for循环快4倍以上的效果。还有一种方式就正如opencv中列处理过程所示,这正是下面将要重点描述的。

      在opencv的代码中,并没有直接沿列方向处理,而是继续沿着行的方向一行一行处理,我先贴出我自己翻译的有关纯C的代码进行解说:

    for (Y = 0; Y < Size - 1; Y++)            //    注意没有最后一项哦                      
    {
        int *LinePS = (int *)(Sum->Data + ColPos[Y] * Sum->WidthStep);
        for(X = 0; X < Width; X++)    ColSum[X] += LinePS[X];
    }

    for (Y = 0; Y < Height; Y++)
    {
        unsigned char* LinePD    = Dest->Data + Y * Dest->WidthStep;    
        int *AddPos              = (int*)(Sum->Data + ColPos[Y + Size - 1] * Sum->WidthStep);
        int *SubPos              = (int*)(Sum->Data + ColPos[Y] * Sum->WidthStep);

        for(X = 0; X < Width; X++)
        {
            Value = ColSum[X] + AddPos[X];
            LinePD[X] = Value * Scale;                    
            ColSum[X] = Value - SubPos[X];
        }
    }

      上述代码中定义了一个ColSum用于保存每行某个位置处在列方向上指定半径内各中间元素的累加值,对于第一行,做特殊处理,其他行的每个元素的处理方式和BaseRowFilter里的处理方式很像,只是在书写上有所区别,特别注意的是对第一行的累加时,最后一个元素并没有计算在内,这个处理技巧在下面的X循环里有体现,请大家仔细体味下。

     上述代码这样做的好处是,能有效的减少CPU的cache miss,但是总的计算量是没有改变的,因此能有效的提高速度。

     针对PC,在opencv内部,其在列方向上采用了SSE进行进一步的优化,我们贴出其处理uchar类型的代码:

View Code

  代码比较多,我稍微精简下(注意,精简后的是不可运行的,只是更清晰的表达了思路)。

virtual void operator()(const uchar** src, uchar* dst, int dststep, int count, int width)
{
    int i;
    int* SUM;
    bool haveScale = scale != 1;
    double _scale = scale;
    if( width != (int)sum.size() )
    {
        sum.resize(width);
        sumCount = 0;
    }

    SUM = &sum[0];
    if( sumCount == 0 )
    {
        memset((void*)SUM, 0, width*sizeof(int));
        for( ; sumCount < ksize - 1; sumCount++, src++ )
        {
            const int* Sp = (const int*)src[0];
            i = 0;
           
            for( ; i <= width-4; i+=4 )
            {
                __m128i _sum = _mm_loadu_si128((const __m128i*)(SUM+i));
                __m128i _sp = _mm_loadu_si128((const __m128i*)(Sp+i));
                _mm_storeu_si128((__m128i*)(SUM+i),_mm_add_epi32(_sum, _sp));
            }
            for( ; i < width; i++ )
                SUM[i] += Sp[i];
        }
    }
    else
    {
        src += ksize-1;
    }

    for( ; count--; src++ )
    {
        const int* Sp = (const int*)src[0];
        const int* Sm = (const int*)src[1-ksize];
        uchar* D = (uchar*)dst;

        i = 0;
        const __m128 scale4 = _mm_set1_ps((float)_scale);
        for( ; i <= width-8; i+=8 )
        {
            __m128i _sm  = _mm_loadu_si128((const __m128i*)(Sm+i));
            __m128i _sm1  = _mm_loadu_si128((const __m128i*)(Sm+i+4));

            __m128i _s0  = _mm_add_epi32(_mm_loadu_si128((const __m128i*)(SUM+i)),
                                         _mm_loadu_si128((const __m128i*)(Sp+i)));
            __m128i _s01  = _mm_add_epi32(_mm_loadu_si128((const __m128i*)(SUM+i+4)),
                                          _mm_loadu_si128((const __m128i*)(Sp+i+4)));

            __m128i _s0T = _mm_cvtps_epi32(_mm_mul_ps(scale4, _mm_cvtepi32_ps(_s0)));
            __m128i _s0T1 = _mm_cvtps_epi32(_mm_mul_ps(scale4, _mm_cvtepi32_ps(_s01)));

            _s0T = _mm_packs_epi32(_s0T, _s0T1);

            _mm_storel_epi64((__m128i*)(D+i), _mm_packus_epi16(_s0T, _s0T));

            _mm_storeu_si128((__m128i*)(SUM+i), _mm_sub_epi32(_s0,_sm));
            _mm_storeu_si128((__m128i*)(SUM+i+4),_mm_sub_epi32(_s01,_sm1));
        }
        for( ; i < width; i++ )
        {
            int s0 = SUM[i] + Sp[i];
            D[i] = saturate_cast<uchar>(s0*_scale);
            SUM[i] = s0 - Sm[i];
        }

        dst += dststep;
    }
}

      在行方向上,ColSum每个元素的更新相互之间是没有任何关系的,因此,借助于SSE可以实现一次性的四个元素的更新,并且上述代码还将第一行的特殊计算也用SSE实现了,虽然这部分计算量是非常小的。

     在具体的SSE细节上,对于uchar类型,虽然中间结果是用int类型表达的,但是由于SSE没有整形的除法指令(是否有?),因此上面借用了浮点数的乘法SSE指令实现,当然就多了_mm_cvtepi32_ps 以及 _mm_cvtps_epi32这样的类型转换的函数。如果有整形除法,那就能更好了。

     SSE的实现,无非也就是用_mm_loadu_si128加载数据,用_mm_add_epi32, _mm_mul_ps之类的函数进行基本的运算,用_mm_storeu_si128来保存数据,并没有什么特别复杂的部分,注意到考虑到数据的普遍性,不一定都是16字节对齐的,因此在加载和保存是需要使用u方面的函数,其实现在的_mm_loadu_si128和_mm_load_si128在处理速度上已经没有特别明显的区别了。

      注意到在每个SSE代码后面,总还有部分C代码,这是因为我们实际数据宽度并不一定是4的整数倍,未被SSE处理的部分必须使用C实现,这其实对读者来说是非常好的事情,因为我们能从这部分C代码中搞明白上述的SSE代码是干什么的。

  以上就是opencv的Box Filter实现的关键代码,如果读者去看具体细节,opencv还有针对手机上的Neon优化,其实这个和SSE的意思基本是一样的。

  那是否还有改进的空间呢,从我的认知中,在对垂直方向的处理上,应该没有了,但是水平方向呢, SSE有没有用武之地,经过我的思考我认为还是有的。

  在行方向的计算中,这个for循环是主要的计算。

for(X = 1; X < Width; X ++)
{
    Value += RowData[X + Size - 1] - RowData[X - 1];    
    LinePD[X] = Value;               
}

       本人认为虽然这里的操作是前后依赖的,全局无法并行化,但是观察这一行代码:

Value += RowData[X + Size - 1] - RowData[X - 1];    

      其中RowData[X + Size - 1] - RowData[X - 1]; 并不是前后依赖的,是可以并行的,因此如果提前快速的计算出所有的差值,那么提速的空间还比较大,即需要提前计算出下面的函数:

 for(X = 0; X < (Width - 1); X++)
     Diff[X] = AddPos[X] - SubPos[X];

  这里用SSE实现则非常简单了:

        unsigned char *AddPos = RowData + Size * Channel;
        unsigned char *SubPos = RowData;
        X = 0;                    //    注意这个赋值在下面的循环外部,这可以避免当Width<8时第二个for循环循环变量未初始化            
        __m128i Zero = _mm_setzero_si128();
        for (; X <= (Width - 1) * Channel - 8; X += 8)
        {
            __m128i Add = _mm_unpacklo_epi8(_mm_loadl_epi64((__m128i const *)(AddPos + X)), Zero);        
            __m128i Sub = _mm_unpacklo_epi8(_mm_loadl_epi64((__m128i const *)(SubPos + X)), Zero);        
            _mm_store_si128((__m128i *)(Diff + X + 0), _mm_sub_epi32(_mm_unpacklo_epi16(Add, Zero), _mm_unpacklo_epi16(Sub, Zero)));        //    由于采用了_aligned_malloc函数分配内存,可是使用_mm_store_si128
            _mm_store_si128((__m128i *)(Diff + X + 4), _mm_sub_epi32(_mm_unpackhi_epi16(Add, Zero), _mm_unpackhi_epi16(Sub, Zero)));
        }
        for(; X < (Width - 1) * Channel; X++)
            Diff[X] = AddPos[X] - SubPos[X];

  和列方向的SSE处理代码不同的是,这里加载的是uchar数据,因此加载的函数就有所不同,处理的方式也有区别,上面几个SSE函数各位查查MSDN就能理解其意思,还是很有味道的。

  经过这样的处理,经过测试发现,速度能够比opencv的版本在提高30%,也是额外的惊喜。

      再有的优化可能提速有限,比如把剩下的一些for循环内部分成四路等等。

     在我的I5台式机中,使用上述算法对1024*1024的三通道彩色图像进行半径为5的测试,进行100次的计算纯算法部分的耗时为800ms,如果是纯C版本大概为1800ms;当半径为200时,SSE版本约为950ms, C版本约1900ms;当半径为400时,SSE版本约为1000ms, C版本约2100ms;可见,半径增大,耗时稍有增加,这主要是由于算法中有部分初始化的计算和半径有关,但是这些都是不重要的。

      在不使用多线程(虽然本算法非常适合多线程计算),不使用GPU,只使用单线程\CPU进行计算的情况下,个人觉得目前我这个代码是很难有质的超越的,从某个方面讲,代码中的用于计算的时间占用的时间比从内存等待数据的时间可能还要短,而似乎也没有更好的算法能进一步减少内存数据的访问量。

      本人在这里邀请各位高手对目前我优化的这个代码进行进一步的优化,希望高人不要谦虚。

  运行界面:

  

  本文的代码是针对常用的图像数据进行的优化处理,在很多场合下,需要对int或者float类型进行处理,比如GuideFilter,如果读者理解了本文解读的代码的原理,更改代码以便适应他们则是一件非常简单的事情,如果您不会,那么也请你不要给我留言,或者我可以有偿提供,因为从本质上讲我喜欢提供渔,而不是鱼,渔具已经送给你了,你却找我要鱼,那只能..............。  

 

 ****************************作者: laviewpbt   时间: 2015.12.17    联系QQ:  33184777 转载请保留本行信息**********************

   

本文转载自:http://www.cnblogs.com/Imageshop/p/5053013.html

共有 人打赏支持
abcijkxyz
粉丝 60
博文 6196
码字总数 1876
作品 0
深圳
项目经理
opencv3.0中与CUDA相关的头文件和库解释

目前,opencv中的cuda接口能够实现的算法还比较少,并不是很齐全,使用前需要先确定算法是否存在cuda接口 相对2.x的改动 * 不再使用cv::gpu的命名空间,改用cv::cuda * 头文件中需要单独引用...

sirius_0
04/08
0
0
OpenCV 3.4.1 发布,扩展深度神经网络模块

OpenCV 3.4.1 发布,此次更新主要扩展了 DNN(Deep Neural Networks,深度神经网络) 模块,修复了多个 bug 以及做了一些功能改进。 更新内容包括: 增加了对量化TensorFlow网络的支持。 Open...

雨田桑
04/29
0
0
【OpenCV入门】用VS2008编译生成OpenCV-2.3.0-SDK

不清楚OpenCV的官方网站有没有适合VS2008的SDK,所以决定自己编译生成SDK。 (1)准备:VS2008,OpenCV-2.3.0源码,CMAKE (2)打开CMAKE,将Source目录指向源码,Dest目录指向C盘新建的CVB...

庄金峰
2012/11/16
0
2
VS2010 / MFC + OpenCV 2.4.1打开图片

Windows 7 x64,VS2010 / MFC + OpenCV 2.4.1打开图片显示到Picture控件中。 OpenCV 2.2、OpenCV 2.3同样适用。 工具/原料 WinXP / Win7 x86 / x64 OpenCV 2.2 / 2.3 / 2.4 Visual Studio 20......

LMcallme
2013/04/11
0
0
基于OpenCV的iOS图像处理

关于图片处理 随着科技的发展,AI、机器学习、AR、VR等已经逐渐走进生活,模式识别、图像捕捉、图片拼接等已经成为其中的重要环节。因此,图像处理技术在未来会被移动端广泛使用。其中,有很...

无忌不悔
2017/09/06
0
0
玩转智能路由器-WRTnode添加OpenCV支持

opencv libs库文件ipk编译 opencv ipk源码 利用openwrt package的编译机制仅仅需要一个Makefile即可编译opencv。 为何会如此简单神奇,下面就对Makefile详解(个人看法,欢迎指正): $vim M...

openthings
2015/03/04
0
0
为Visual Studio配置OpenCV

配置的环境是: Windows 8, Visual Studio 2012 openCV_2.47 下面开始详细地讲解整个配置的过程: 步骤1: 首先需要下载openCV,这是Sourceforge的链接:http://sourceforge.net/projects/ope...

Comma_H
05/14
0
0
Visual Studio 安装OpenCV及问题总结

1、VS安装OpenCV基本步骤   1)安装Visual Studio     下载网址https://opencv.org/releases.html#   2)安装OpenCV      下载网址https://www.visualstudio.com/zh-hans/,直接下...

youaremyall
02/02
0
0
在Visual Studio2012中配置openCV

经过了几个小时的努力,最终成功地在Visual Studio 2012中配置好了openCV,为了分享经验以及便于日后的查阅,记录了配置的过程和一些细节。 首先指出我配置的环境是: Windows8(64位), Vis...

JiaMing
2013/12/07
0
13
LSD SLAM的编译以及depth debug window不存在的问题

在回顾LSD SLAM的过程中,想着再跑跑LSD,结果笔记本上面的源码不能重新编译了,所以就重新过了一遍,给后面对SLAM感兴趣的人一点点参考。 首先需要提醒一下的,因为ros版本的升级,编译方式...

osgoodwu
04/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

fiddle 4 初始化

下载 配置fiddle 4 如果证书导出失败,执行下面脚本 D:\programs\Fiddler>makecert.exe -r -ss my -n "CN=DO_NOT_TRUST_FiddlerRoot, O=DO_NOT_TRUST, OU=Created by http://www.fiddler2.c......

柯里昂
5分钟前
0
0
rabbitmq学习记录(六)交换机Exchange-direct

实现功能:一条消息发送给多个消费者 交换机模式:direct 相比于之前的fanout模式,可以进一步的筛选获取消息的消费者。 fanout模式下,只要消费者监听的队列,已经与接收生产者消息的交换机...

人觉非常君
21分钟前
0
0
Java 之 枚举

Java 中声明的枚举类,均是 java.lang.Enum 类的子类,Enun 类中的常用方法有: name() 返回枚举对象名称 ordinal() 返回枚举对象下标 valueOf(Class enumType, String name) 转换枚举对象 ...

绝世武神
30分钟前
0
0
使用爬虫实现代理IP池之放弃篇

啥叫代理IP以及代理IP池 概念上的东西网上搜索一下就好了,这里简单科普一下(大部分会读这篇文章的人,基本是不需要我来科普的),白话说就是能联网并提供代理访问互联网的服务器,它提供的...

一别丶经年
46分钟前
0
0
sqoop导入数据到Base并同步hive与impala

使用Sqoop从MySQL导入数据到Hive和HBase 及近期感悟 基础环境 Sqool和Hive、HBase简介 Sqoop Hive HBase 测试Sqoop 使用Sqoop从MySQL导入数据到Hive 使用复杂SQL 调整Hive数据类型 不断更新 ...

hblt-j
今天
0
0
Dart 服务端开发 文件上传

clent端使用angular组件 upload_component.html form id="myForm" method="POST" enctype="multipart/form-data"> <input type="file" name="fileData"> <!-- file field --></form>......

scooplol
今天
0
0
apache和tomcat同时开启,乱码问题

tomcat和apache同时开启,会走apache的转发,执行的是AJP/1.3协议。所以在tomcat的配置文件server中, <Connector port="8009" protocol="AJP/1.3" redirectPort="8443" useBodyEncodingForU......

Kefy
今天
0
0
使用ssh-keygen和ssh-copy-id三步实现SSH无密码登录 和ssh常用命令

ssh-keygen 产生公钥与私钥对. ssh-copy-id 将本机的公钥复制到远程机器的authorized_keys文件中,ssh-copy-id也能让你有到远程机器的home, ~./ssh , 和 ~/.ssh/authorized_keys的权利 第一步...

xtof
今天
0
0
orcale 查询表结构

SELECT t.table_name, t.colUMN_NAME, t.DATA_TYPE || '(' || t.DATA_LENGTH || ')', t1.COMMENTS FROM User_Tab_Cols t, User_Col_Comments t1WHERE t.table_name......

wertwang
今天
0
0
华为nova3超级慢动作酷玩抖音,没有办法我就是这么强大

华为nova3超级慢动作酷玩抖音,没有办法我就是这么强大!华为nova3超级慢动作酷玩抖音,没有办法我就是这么强大! 在华为最新发布的nova 3手机上,抖音通过华为himedia SDK集成了60fps、超级...

华为终端开放实验室
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部