来自 mm小游戏 2019-09-16 07:07 的文章
当前位置: 澳门新葡亰平台游戏 > mm小游戏 > 正文

Filter的实现并提出进一步加速的方案

    表达:本文全部算法的涉及到的优化均指在PC上进展的,对于其他构架是还是不是妥帖未知,请自行试验。

      BoxFilter,最优良的一种世界操作,在数不胜数的场所中都具有广大的利用,作为三个很基础的函数,其品质的上下也平昔影响着其余有关函数的习性,最卓越莫如现在很好的EPF滤波器:GuideFilter。由此其优化的程度和程度是不行重大的,网络上有比相当多连锁的代码和博客对该算法举办教学和优化,建议了大多O(1)算法,但所谓的0(1)算法也会有高低之分,0(1)只是代表实施时间和有些参数非亲非故,但自己的耗费时间照旧有分别。相比较盛行的便是积存直方图法,其实那么些是十二分不可取的,因为稍大的图就能够招致溢出,这里大家解析下 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类型的代码:

mm小游戏 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的测量试验,实行98遍的乘除纯算法部分的耗费时间为800ms,假诺是纯C版本大致为1800ms;当半径为200时,SSE版本约为950ms, C版本约一九零五ms;当半径为400时,SSE版本约为一千ms, C版本约2100ms;可知,半径增大,耗费时间稍有扩展,那第一是由于算法中有一对开头化的计量和半径有关,不过这几个都是不首要的。

      在不行使四线程(尽管本算法特别适合多线程总括),不选择GPU,只行使单线程CPU举办总计的景观下,个人认为日前本人那些代码是很难有质的超出的,从有些地方讲,代码中的用于计算的时日侵夺的时日比从内部存款和储蓄器等待数据的日子或者还要短,而仿佛也从没更加好的算法能更进一竿削减内部存款和储蓄器数据的访谈量。

      本人在此地特邀各位高手对现阶段我优化的那些代码实行更为的优化,希望高人不要客气。

  运营分界面:

mm小游戏 2

mm小游戏,  

  本文的代码是针对性常用的图像数据开展的优化管理,在好些个场子下,须求对int或许float类型实行管理,举个例子GuideFilter,假诺读者知道了本文解读的代码的规律,改变代码以便适应他们则是一件极度简单的政工,假若您不会,那么也请你不要给本身留言,或然笔者得以有偿提供,因为从实质上讲自身欣赏提供渔,并不是鱼,渔具已经送给您了,你却找小编要鱼,那只好..............。

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

mm小游戏 3

 

 

 ****************************笔者: laviewpbt   时间: 二零一四.12.17    联系QQ:  33184777 转发请保留本行音信**********************

   

本文由澳门新葡亰平台游戏发布于mm小游戏,转载请注明出处:Filter的实现并提出进一步加速的方案

关键词: