源码共享

来源:http://www.goldns.net 作者:手机APP 人气:101 发布时间:2019-12-14
摘要:   表达:本文全数算法的关系到的优化均指在PC上进展的,对于此外构架是或不是伏贴未知,请自行试验。       BoxFilter,最精髓的风流倜傥种世界操作,在广大的场面中都颇有广大

    表达:本文全数算法的关系到的优化均指在PC上进展的,对于此外构架是或不是伏贴未知,请自行试验。

      BoxFilter,最精髓的风流倜傥种世界操作,在广大的场面中都颇有广大的采纳,作为一个很幼功的函数,其特性的上下也平素影响着此外连锁函数的习性,最优异莫如未来很好的EPF滤波器:GuideFilter。因而其优化的档案的次序和档案的次序是不行主要的,互联网上有相当多有关的代码和博客对该算法进行讲明和优化,建议了成都百货上千O(1卡塔尔算法,但所谓的0(1卡塔尔(英语:State of Qatar)算法也是有优劣之分,0(1卡塔尔(英语:State of Qatar)只是表示实行时间和某些参数无关,但作者的耗费时间照旧有分别。相比盛行的正是积攒直方图法,其实这一个是老大不可取的,因为稍大的图就能够招致溢出,这里大家深入分析下 opencv的连带代码,看看他是怎么着举行优化的。

      首先找到opencv的代码的岗位,其在opencvsourcesmodulesimgprocsrcsmooth.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类型的代码:

图片 1View 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的BoxFilter完毕的主要性代码,假若读者去看具体细节,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的本子在抓好百分之三十三,也是额外的大悲大喜。

      再有的优化大概提速有限,比如把剩余的有个别for循环内部分成四路等等。

     在本身的I5笔记本中,使用上述算法对1024*1024的三通道彩色图片举行半径为5的测验,举行玖拾四次的计量纯算法部分的耗费时间为800ms,即便是纯C版本差不离为1800ms;当半径为200时,SSE版本约为950ms, C版本约1905ms;当半径为400时,SSE版本约为1000ms, C版本约2100ms;可以知道,半径增大,耗时稍有增添,那首假使由于算法中有一点初步化的臆度和半径有关,然则那一个都是不根本的。

      在不利用八线程(就算本算法非常符合十二线程总结),不接收GPU,只利用单线程CPU举行测算的图景下,个体感觉这两天本身这么些代码是很难有质的超常的,从某些地方讲,代码中的用于总计的时日并吞的日子比从内部存款和储蓄器等待数据的光阴恐怕还要短,而就像也从未越来越好的算法能越来越裁减内部存款和储蓄器数据的访问量。

      本身在此边约请各位高手对现阶段本身优化的那一个代码进行更进一竿的优化,希望高人不要自持。

  运营界面:

图片 2

  

  本文的代码是本着常用的图像数据开展的优化管理,在不菲场子下,要求对int可能float类型举办拍卖,例如GuideFilter,尽管读者领会了本文解读的代码的规律,校正代码以便适应他们则是生机勃勃件特轻便的事情,如若你不会,那么也请您不要给小编留言,也许本人能够有偿提供,因为从精气神儿上讲作者垂怜提供渔,并不是鱼,渔具已经送给你了,你却找小编要鱼,那只好..............。

      本文源代码下载地址(VS二零零六编写制定):Box Filter 

图片 3

 

 

 ****************************小编: laviewpbt   时间: 2014.12.17    联系QQ:  33184777 转发请保留本行消息**********************

   

本文由澳门新葡亰娱乐场发布于手机APP,转载请注明出处:源码共享

关键词:

最火资讯