解析opencv中央博物院克斯 Filter的贯彻并提议进一步加快的方案(源码共享)。

    表明:本文全数算法的涉及到的优化均指在PC上进展的,对于别的构架是不是适当未知,请自行试验。

      BoxFilter,最经典的壹种世界操作,在很多的地方中都拥有广泛的运用,作为1个很基础的函数,其属性的3陆九等也间接影响着其余相关函数的性质,最杰出莫如今后很好的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 = 二 * Radius +
    一,LinePD即所谓的中游结果,思索数据类型能表达的界定,必须接纳int类型。

     
对于每行第贰个点不会细小略,直接用for总计出游方向的钦点半径内的累加值。而之后全体点,用前二个累计值加上新投入的点,然后去除掉移出的哪一个点,获得新的累加值。那一个点子在很多文献中都有谈到,并不曾什么独特之处,那里不多说。

   
 根据平常的合计,在列方向的拍卖相应和行方向完全相同,只是处理的自由化的例外、处理的数据源的差别以及尾声索要对计量结果多一个归一化的进度而已。事实也是那样,有为数不少算法都是那样做的,但是出于CPU构架的1部分原因(首若是cache
miss的加码),同样的算法沿列方向处理总是会比沿行方向慢1个水准,化解方法有无数,例如先对中级结果开始展览转置,然后再依据行方向的条条框框进行拍卖,处理完后在将数据转置回去。转置进度是有10分高效的处理格局的,借助于SSE以及Cache优化,能兑现比原来两重for循环快4倍以上的法力。还有壹种艺术就正如opencv中列处理进度所示,那就是上边将要重点描述的。

     
在opencv的代码中,并未一直沿列方向处理,而是继续本着行的样子1行1行处理,作者先贴出笔者要好翻译的关于纯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用于保存每行有些地点处于列方向上内定半径内各中等成分的累加值,对于第3行,做尤其处理,别的行的种种成分的处理方式和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_si12八加载数据,用_mm_add_epi32, _mm_mul_ps之类的函数进行基本的运算,用_mm_storeu_si12八来保存数据,并未怎么尤其复杂的一对,注意到思索到数码的普遍性,不肯定都以16字节对齐的,由此在加载和保留是亟需使用u方面包车型大巴函数,其达成在的_mm_loadu_si128和_mm_load_si12八在处理速度上曾经没有尤其扎眼的差异了。

     
注意到在种种SSE代码后边,总还有壹些C代码,那是因为大家其实多少上涨幅度并不一定是肆的平头倍,未被SSE处理的1对必须利用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;               
}

     
 本人认为纵然那里的操作是上下注重的,全局不能并行化,可是观望那1行代码:

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的本子在拉长3/10,也是额外的喜怒哀乐。

     
再有的优化或然提速有限,比如把结余的部分for循环内部分成肆路等等。

   
 在自家的I伍台式机中,使用上述算法对拾2四*102四的叁通道彩色图像实行半径为5的测试,举行九四回的盘算纯算法部分的耗费时间为800ms,假设是纯C版本大约为1800ms;当半径为200时,SSE版本约为950ms,
C版本约一九〇〇ms;当半径为400时,SSE版本约为一千ms,
C版本约二十0ms;可知,半径增大,耗费时间稍有扩展,那至关心重视就算由于算法中有一部分初叶化的总括和半径有关,然则那几个都以不重大的。

     
在不采纳拾2线程(尽管本算法格外适合八线程总计),不行使GPU,只行使单线程\CPU进行总括的事态下,村办觉得日前作者那么些代码是很难有质的跨越的,从有些方面讲,代码中的用于总计的时辰占据的小时比从内部存款和储蓄器等待数据的时间也许还要短,而就像是也从未更好的算法能更为收缩内部存款和储蓄器数据的访问量。

     
本身在此处诚邀各位高手对眼下自家优化的这么些代码举行更进一步的优化,希望高人不要客气。

  运维界面:

图片 2

  

  本文的代码是对准常用的图像数据开展的优化处理,在诸多场合下,供给对int大概float类型进行拍卖,比如GuideFilter,借使读者知道了本文解读的代码的法则,更改代码以便适应他们则是一件非凡简单的业务,固然您不会,那么也请你不用给本人留言,或许我得以有偿提供,因为从本质上讲自个儿欢乐提供渔,而不是鱼,渔具已经送给你了,你却找笔者要鱼,那只可以…………..。

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

图片 3

 

 

 ****************************小编:
laviewpbt   时间: 20壹5.1贰.一柒    联系QQ:  33184777转发请保留本行音讯**********************