13执行代码实现最高效最快捷的积分图像算法。

  研究图像及一定程度的食指,应该还指向积分图像有所了解,大家以百度或者google中还好找到大气底系博客,我此不举行多介绍。用积分图也真正能缓解过剩实际上的问题,比如自己博客中之冲局部均方差相关消息之图像去噪及其于实时磨皮美容算法中的下 一平和我哪怕在网上看众多丁就此总共积分图和乘积积分图来促成了。不过自己浏览了成百上千人口之博客,觉得多人口即是图像方面的像还比较牛之人头都对准是积分图的喻还未成功或者说亮有误,这里发生必要借助自身微弱的力量还校正下。

   
 首先一个普遍的题目即使是:积分图像的尺寸。你可看出,90%和好写的积分图的作者还是拿积分图像定位也W
*
H,但是不亮她们出没发在意到OpenCV里积分图的系文档,我此贴出OpenCV的官方文档:

  C++:`voidintegral`(InputArray image,
OutputArray sum, int sdepth=-1

Parameters:
  • image – Source image as W X H  , 8-bit or floating-point (32f or 64f).
  • sum – Integral image as (W + 1) X (H + 1) , 32-bit integer or floating-point (32f or 64f).
  • sdepth – Desired depth of the integral and the tilted integral images, CV_32SCV_32F, or CV_64F.

 

 

 

     注意到sum这同样码之尺寸了啊, (W +
1) X (H + 1)
而非**W X
H,为什么吧,我们知晓,某个点之积分图反应的凡原图中此岗位左上角所有像素之和,这里是的增长和凡勿包括这点像素本身的,那么如此,对于原图的第一实施和率先排列的富有像素,其针对性诺位置的积分图就应有是0,
这样考虑到所有的像素,为了能包容最后一排和终极一行的场面,最终之积分图就该是
 (W

  • 1) X (H + 1)**大小。

     如果您还是愿意定义成W X
H大小,那么尽管得每次判断你看的积分图的位置,作为写程序来说,这样做对先后的特性及代码的简洁性都是糟糕的,并且你稍微不注意就会见将代码写错。

   
 第二,就是积分图的计算的优化,很多博客也还讲述了他们的优化措施,虽然她们都是讲述的和一个算法,比如百度上比较靠前的博文: 【图像处理】快速计算积分图 
中就是用下述前片幅图描述了外的优化过程:

     
  C++ 1  ———>
 C++ 2  ———>
 C++ 3

                        (1)
 最老方案                 (2)网络直达之优化方案                  (3)我之优化方案

 

     不错,这样做已颇正确了,但是有一个题目即使是咱们需要多一个轻重为W的内存来更新保存每一样排相应的合计和,但是咱只要换成行方向呢,如上面的(3)所示,则只有待一个变量来共行方向上的值,而我辈领略么变量CPU可能会见把他停到寄存器中要么我们好强制将他宣称也register变量的,而列方向上的内存数据就是无法到位就等同沾了。

   
 另外,我们提请了积分图后,是不曾必要先被他来一个清零操作的,因为连续我们见面指向每一个职的价值都填充0的。

   
 好,下面我们贴发出了优化后的代码:

 1 void GetGrayIntegralImage(unsigned char *Src, int *Integral, int Width, int Height, int Stride)
 2 {
 3     memset(Integral, 0, (Width + 1) * sizeof(int));                    //    第一行都为0
 4     for (int Y = 0; Y < Height; Y++)
 5     {
 6         unsigned char *LinePS = Src + Y * Stride;
 7         int *LinePL = Integral + Y * (Width + 1) + 1;                  //    上一行位置            
 8         int *LinePD = Integral + (Y + 1) * (Width + 1) + 1;            //    当前位置,注意每行的第一列的值都为0
 9         LinePD[-1] = 0;                                                //    第一列的值为0
10         for (int X = 0, Sum = 0; X < Width; X++)
11         {
12             Sum += LinePS[X];                                        //    行方向累加
13             LinePD[X] = LinePL[X] + Sum;                            //    更新积分图
14         }
15     }
16 }

   
 代码很粗略,但是并了许多细节信息,只有有中心人才能够领悟。

   
 在PC上,也许要得以考虑到SSE优化,要采用SSE,就必对Sum这个做改造,又使就此一个W长度的int型内存记录,然后针对 LinePD[X]
= LinePL[X] + Sum;
用SSE优化,一次性处理4个数据论的加法,但是如此做SSE的涨潮与前面sum那句的拍卖的耗时坏更决心,我从没失去证明了。

   
 那么点方法(2)的更的语法优化的代码如下(比原作者非常应该效率会哼广大的)

 1 void GetGrayIntegralImage(unsigned char *Src, int *Integral, int Width, int Height, int Stride)
 2 {
 3     int *ColSum = (int *)calloc(Width, sizeof(int));        //    用的calloc函数哦,自动内存清0
 4     memset(Integral, 0, (Width + 1) * sizeof(int));
 5     for (int Y = 0; Y < Height; Y++)
 6     {
 7         unsigned char *LinePS = Src + Y * Stride;
 8         int *LinePL = Integral + Y * (Width + 1) + 1;
 9         int *LinePD = Integral + (Y + 1) * (Width + 1) + 1;
10         LinePD[-1] = 0;
11         for (int X = 0; X < Width; X++)
12         {
13             ColSum[X] += LinePS[X];
14             LinePD[X] = LinePD[X - 1] + ColSum[X];
15         }
16     }
17     free(ColSum);
18 }

  可以看来,在无限内层的大循环里多矣几个内存变量的走访,朋友等可以协调测试,我之优化方案于这同一片的耗时只有方案(2)的一半左右,而且代码更精简。

      当我们需要拜访基本点啊(x,
y),半径为r的界定外的矩形像素内的累积值,相应的坐标计算就活该也:

          Integral(x – r, y –
r) + Integral(x + r + 1, y + r + 1) – Integral(x – r, y + r + 1)
– Integral(x + r + 1, y – r)

  注意上式计算着之加1,这第一是盖积分图是测算左上角像素的累计值这个特性决定的。

   
 那么下面我贴有用积分图实现0(1)的均值模糊的一对代码:

void BoxBlur(unsigned char *Src, unsigned char *Dest, int Width, int Height, int Stride, int Radius)
{
    int *Integral = (int *)malloc((Width + 1) * (Height + 1) * sizeof(int));
    GetGrayIntegralImage(Src, Integral, Width, Height, Stride);
    //#pragma omp parallel for
    for (int Y = 0; Y < Height; Y++)
    {
        int Y1 = max(Y - Radius, 0);
        int Y2 = min(Y + Radius + 1, Height - 1);
        /*int Y1 = Y - Radius;
        int Y2 = Y + Radius + 1;
        if (Y1 < 0) Y1 = 0;
        if (Y2 > Height) Y2 = Height;*/
        int *LineP1 = Integral + Y1 * (Width + 1);
        int *LineP2 = Integral + Y2 * (Width + 1);
        unsigned char *LinePD = Dest + Y * Stride;
        for (int X = 0; X < Width; X++)
        {
            int X1 = max(X - Radius, 0);
            int X2 = min(X + Radius + 1, Width);
            //    int X1 = X - Radius;
            //    if (X1 < 0) X1 = 0;
            //    int X2 = X + Radius + 1;
            //    if (X2 >= Width) X2 = Width - 1;
            int Sum = LineP2[X2] - LineP1[X2] - LineP2[X1] + LineP1[X1];
            int PixelCount = (X2 - X1) * (Y2 - Y1);
            LinePD[X] = (Sum + (PixelCount >> 1)) / PixelCount;
        }
    }
    free(Integral);
}

  代码也死简短,注意下自己注释掉的几独片。

  第一:

    //#pragma omp parallel for

  由于开展的积分图的操作,每个像素点的宽广半径为r区域外之像素之和的测算就是内外无关的了,因此像素和像素之间的盘算就是独自的了,这样就算足以并行执行,这里用了OpenMP作为简易并行实现的一个事例而已。

   
 第二:我原来编程习惯怎么是聊喜欢用max和min这样的函数,我毕竟认为用if这种判断效率应会比较max或者min高,而其实却是max厉害一些,我看了生反汇编,max和min充分利用了准星仍传送指令以cmovg,cmovl,而相似的if语句很十分程度上会见调用jmp指令的(当然跟常数比较相似编译也会见用口径传送替代的,比如和0比较),jmp指令时于耗时的。因此…….

   
 还有一个在意点便是积分图的极可怜X坐标是Width,最老Y坐标是Height,
这点及图像有所不同,正使上述代码所示。

   
 通过积分图技术实现之均值模糊和之前自己当文章解析opencv中Box
Filter的落实并提出越来越加快的方案(源码共享) 中介绍的法(非SSE优化的代码)耗时为主差不多,内存占用呢大抵,但是积分图技术有个优势,就是使某个算法需要计算和一个图像的大多只半径的歪曲值,则积分图只需要算同一不善,只以成千上万之依据多规格C++模糊的算法中呢是能提速的方案有。

   
 上述是常见的总计积分图,我们常常因此之还有平方积分图,还有点儿轴图对应的乘积积分图,本质上同本例是从未底,只需要将 Sum += LinePS[X];
这无异于句子小作改。但是发生少数,一直是我非极端情愿为此积分图的要原因,就是保存积分图数据的内存区域或数据类型问题,普通的积分图还吓,就到底每个像素都为255,也惟有当图像大于2800*3000左右常,才会胜出int类型所能够表达的界定,如果就此uint类型表示,能盛的图像大小又能够增强一加倍,一般的话够了,但是若是平方积分图,int类型在极度气象下只能处理不超
256*256尺寸的图像,这样以实际上被几近是无用的,因此,可能我们不怕用float类型或者int64为来代表。但是,第一,float类型会引来计算速度下降,特别是非PC的条件下。第二,int64会占有更特别的内存,大约是8倍增之原图像内存,同时于32位系统上为会带来速度之大跌。

   
 对于花的图像,处理方式也接近,这里虽无赘述了。

   
 本文对应的代码下载地址:http://files.cnblogs.com/files/Imageshop/IntegralImage.rar

     C++ 4