解析opencv中Box Filter的兑现并指出更加快的方案美学原理(源码共享)。

        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];
for(X = 1; X < Width; X ++)
{
    Value += RowData[X + Size - 1] - RowData[X - 1];    
    LinePD[X] = Value;               
}
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;
    }
}
 for(X = 0; X < (Width - 1); X++)
     Diff[X] = AddPos[X] - SubPos[X];

  以上就是opencv的Box
Filter实现的机要代码,如若读者去押具体细节,opencv还有针对性手机上的Neon优化,其实这个和SSE的意基本是如出一辙的。

     
本人于这边邀请各位高手对当前自优化的此代码举办更的优化,希望高人不要客气。

  在履行方向的臆度着,这一个for循环是要的计量。

     
上述代码中定义了一个ColSum用于保存每行某个地方处于列方向上指定半径内各国中元素的累加值,对于第一举行,做特殊处理,其他执行之每个元素的处理格局和BaseRowFilter里的处理情势很像,只是当挥洒上有所区别,特别注意的是对准第一实施的长时,最终一个要素并没总计在内,那么些处理技术在底下的X循环里生反映,请我们细心回味下。

  代码相比较多,我不怎么强简下(注意,精简后的是不足运行的,只是再也清楚的表明了思路)。

 ****************************笔者:
laviewpbt   时间: 2015.12.17    联系QQ:  33184777
转载请保留本行音讯**********************

      Box
Filter,最经典的同种世界操作,在广大底场面被都富有广泛的采纳,作为一个不胜基础的函数,其特性的高低与否直影响在此外相关函数的习性,最登峰造极莫如现在很好的EPF滤波器:GuideFilter。因此其优化的水平和水平是老首要的,网络达到出过多连锁的代码和博客对拖欠算法举行讲解和优化,提议了诸多O(1)算法,但所谓的0(1)算法为生优劣的分,0(1)只是表示执行时间跟某某参数无关,但我的耗风尚是有分。相比流行的哪怕是积累直方图法,其实这是坏不可取的,因为有些深的图就是会见招溢起,这里大家分析下
opencv的连锁代码,看看他是何许开展优化的。

 

     
 本人认为虽然此的操作是左右依赖的,全局不可能并行化,不过阅览这一行代码:

  上述代码中RowData是乘对有平行像从举办扩展后的像素值,其调幅为Width

  本文的代码是指向常用之图像数据实行的优化处理,在多场面下,需要对int或者float类型举办拍卖,比如GuideFilter,假若读者了然了本文解读的代码的法则,更改代码以便适应他们虽是一律项分外简单的事体,假使你不晤面,那么为要您绝不让自己留言,或者我得以有偿提供,因为自本质上称我喜爱提供渔,而未是鱼,渔具都送给您了,你倒是招来我一旦鱼,这只能…………..。

  

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;               
}

    表明:本文所有算法的干到之优化均据于PC上举行的,对于其余构架是否适合未知,请自行试验。

   
 遵照正常的记挂,在排方向的处理相应和行方向完全相同,只是处理的动向的不比、处理的数据源的不等与最后索要针对计量结果基本上一个归一化的进程而已。事实吧是这么,有那些算法都是如此做的,可是出于CPU构架的有些由(首假诺cache
miss的长),同样的算法沿列方向处理总是会较沿行方向慢一个水准,解决智发出不少,例如先对中等结果举办转置,然后再一次比如实施方向的条条框框举办拍卖,处理完后以将数据转置回去。转置过程是发出特别神速的处理格局的,借助于SSE以及Cache优化,能兑现相比较原来两再for循环快4加倍以上的职能。还有平等栽格局就正好而opencv中列处理过程所示,这多亏下边将重点描述的。

     
在行方向上,ColSum每个元素的换代相互之间是无另外关联的,由此,借助于SSE可以实现两次性的季只因素的翻新,并且上述代码还拿率先执之出格统计也用SSE实现了,即便当时部分总结量是充分小之。

美学原理 1

     
注意到当每个SSE代码前边,总还有有C代码,这是因我们其实数据小幅并不一定是4的平头倍增,未吃SSE处理的有的必须下C实现,这实则对读者来说是生好的业务,因为我们能自当下有些C代码中为通晓上述的SSE代码是怎么的。

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

     
对于每行第一独点好粗略,直接用for统计出行方向的指定半径内的累加值。而其后所有点,用前一个累计值加上新进入的触及,然后去破除移出的哇一个沾,得到新的累加值。这些办法以众文献中都生提及,并不曾什么出格的处在,这里不多说。

  和排方向的SSE处理代码不同的是,这里加载的是uchar数据,由此加载的函数就截然不同,处理的艺术啊发分,上边几乎单SSE函数各位查查MSDN就可以领会其意思,仍旧坏有味道的。

      其中RowData[X + Size – 1] –
RowData[X – 1]美学原理,;
并无是上下依赖的,是可互相的,由此只要提前迅速的乘除暴发所有的差值,那么提速的上空还比较深,即用提前统计出下的函数:

  这多少个代码考虑了大半独通道以及余数码列的景,为了分析好我们还写下单通道时之核心代码。

     
在opencv的代码中,并从未直接沿列方向处理,而是继续本着行之大势一行一行处理,我先行贴有自己好翻译的有关纯C的代码举办分解:

美学原理 2

   
 在自家的I5台式机中,使用上述算法对1024*1024之三通道彩色图像举行半径为5底测试,举办100软的测算纯算法部分的耗时啊800ms,要是是纯C版本大概为1800ms;当半径为200时常,SSE版本约为950ms,
C版本约1900ms;当半径为400时时,SSE版本约为1000ms,
C版本约2100ms;可见,半径增大,耗时稍微有搭,这主要是由算法中爆发一对初叶化的测算和半径有关,不过这一个都是勿首要的。

     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循环内部分成四路等等。

  运行界面:

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

美学原理 3View Code

   

  经过如此的处理,经过测试发现,速度可以比opencv的版本在增高30%,也是额外的悲喜。

  那里用SSE实现则卓殊简单了:

   
 针对PC,在opencv内部,其以列方向上选取了SSE举行进一步的优化,大家贴有该处理uchar类型的代码:

   
 在实际的SSE细节上,对于uchar类型,固然中结果是用int类型表明的,可是由于SSE没有整形的除法指令(是否出?),因而地点借用了浮点数的乘法SSE指令实现,当然就基本上了_mm_cvtepi32_ps
以及 _mm_cvtps_epi32如此的类型转换的函数。倘诺爆发整形除法,那即使会还好了。

   
 上述代码这样做的补益是,能管用的滑坡CPU的cache
miss,不过毕竟的统计量是没有改动的,因而能有效的增高速度。

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

  • Radius + Radius, Radius是值滤波的半径, 而代码中Size = 2 * Radius +
    1,LinePD即所谓的中游结果,考虑数据类型能发布的限,必须拔取int类型。

   
 SSE的实现,无非也就是是故_mm_loadu_si128加载数据,用_mm_add_epi32, _mm_mul_ps之类的函数举办着力的运算,用_mm_storeu_si128来保存数据,并从未什么特别复杂的一对,注意到考虑到数量的普遍性,不肯定都是16字节针对同的,由此在加载与封存是急需使用u方面的函数,其实现在底_mm_loadu_si128和_mm_load_si128当处理速度上业已远非专门引人注目的界别了。

  这是否还有改进之上空为,从自我的咀嚼中,在对垂直方向的拍卖达成,应该没了,然则程度方向为,
SSE有无有用武之地,经过自己的思索自己以为要有的。

     
在非使多线程(就算本算法相当适合多线程统计),不动GPU,只行使单线程\CPU举办总结的情事下,私认为眼前本身这代码是杀麻烦发生质的越的,从某个方面讲,代码中之用来总计的日子占据的光阴较打内存等待数的时光或许还要少,而若为从未还好的算法能更加削减内存数据的访问量。

    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];
        }
    }

 

   

     Box Filter
是千篇一律种植队列可分其余滤波,因而,opencv也是这般处理的,先举行行方向的滤波,拿到中结果,然后又对中级结果开展排方向的拍卖,拿到最终的结果。