我正在尝试理解 super fast blur algorithm 背后的算法.下面是与 android 一起工作的 java 端口作为测试。看起来这个版本做了一些我不太了解的优化，也没有任何评论。

void fastblur(Bitmap img, int radius){

    if (radius<1){
        return;
    }
    int w= img.getWidth();
    int h=img.getHeight();
    int wm=w-1;
    int hm=h-1;
    int wh=w*h;
    int div=radius+radius+1;
    int r[]=new int[wh];
    int g[]=new int[wh];
    int b[]=new int[wh];
    int rsum,gsum,bsum,x,y,i,p,p1,p2,yp,yi,yw;
    int vmin[] = new int[Math.max(w,h)];
    int vmax[] = new int[Math.max(w,h)];
    int[] pix= new  int[w*h];

    img.getPixels(pix, 0, w, 0,0,w, h);

    int dv[]=new int[256*div];
    for (i=0;i<256*div;i++){
        dv[i]=(i/div);
    }

    yw=yi=0;

    for (y=0;y<h;y++){
        rsum=gsum=bsum=0;
        for(i=-radius;i<=radius;i++){
            p=pix[yi+Math.min(wm,Math.max(i,0))];
            rsum+=(p & 0xff0000)>>16;
            gsum+=(p & 0x00ff00)>>8;
            bsum+= p & 0x0000ff;
        }
        for (x=0;x<w;x++){

            r[yi]=dv[rsum];
            g[yi]=dv[gsum];
            b[yi]=dv[bsum];

            if(y==0){
                vmin[x]=Math.min(x+radius+1,wm);
                vmax[x]=Math.max(x-radius,0);
            }
            p1=pix[yw+vmin[x]];
            p2=pix[yw+vmax[x]];

            rsum+=((p1 & 0xff0000)-(p2 & 0xff0000))>>16;
            gsum+=((p1 & 0x00ff00)-(p2 & 0x00ff00))>>8;
            bsum+= (p1 & 0x0000ff)-(p2 & 0x0000ff);
            yi++;
        }
        yw+=w;
    }

    for (x=0;x<w;x++){
        rsum=gsum=bsum=0;
        yp=-radius*w;
        for(i=-radius;i<=radius;i++){
            yi=Math.max(0,yp)+x;
            rsum+=r[yi];
            gsum+=g[yi];
            bsum+=b[yi];
            yp+=w;
        }
        yi=x;
        for (y=0;y<h;y++){
            pix[yi]=0xff000000 | (dv[rsum]<<16) | (dv[gsum]<<8) | dv[bsum];
            if(x==0){
                vmin[y]=Math.min(y+radius+1,hm)*w;
                vmax[y]=Math.max(y-radius,0)*w;
            }
            p1=x+vmin[y];
            p2=x+vmax[y];

            rsum+=r[p1]-r[p2];
            gsum+=g[p1]-g[p2];
            bsum+=b[p1]-b[p2];

            yi+=w;
        }
    }

    img.setPixels(pix,0, w,0,0,w,h);
}

如果我的猜测有误，请纠正我:

下面的循环是做什么的？它与预计算内核表有关吗？ div 呢，那是内核表的大小吗？我想我想问的是，dv[] 应该存储什么？

int dv[]=new int[256*div];
for (i=0;i<256*div;i++){
    dv[i]=(i/div);
}

看水平传球: 下面的循环看起来像是在对单独的 RGB 值求和，但它只在每一行的起始像素处执行此操作，因为 yi 只有在我们处理完所有像素直到达到宽度后才会递增.这是因为我们在下一个循环中处理像素时最终添加到 RGB 总和吗？

        for(i=-radius;i<=radius;i++){
            int ind = yi+Math.min(wm,Math.max(i,0));
            p=pix[ind];
            rsum+=(p & 0xff0000)>>16;
            gsum+=(p & 0x00ff00)>>8;
            bsum+= p & 0x0000ff;
        }

我们是否只根据半径和当前像素位置选择最左边和最右边的像素？

 if(y==0){
   vmin[x]=Math.min(x+radius+1,wm);
   vmax[x]=Math.max(x-radius,0);
  } 

  p1=pix[yw+vmin[x]];
  p2=pix[yw+vmax[x]];

接下来是最让我困惑的: 我说的是获得左右像素之间的差异并添加我们拥有的运行 RGB 总计是否正确？

  rsum+=((p1 & 0xff0000)-(p2 & 0xff0000))>>16;
  gsum+=((p1 & 0x00ff00)-(p2 & 0x00ff00))>>8;
  bsum+= (p1 & 0x0000ff)-(p2 & 0x0000ff);

我还没有看过第二遍，因为这几乎超出了我的理解范围。任何澄清将不胜感激，并且对垂直传递循环的任何评论也会有所帮助，谢谢。

最佳答案

既然我写了那个，我想我可以解释得最好 :-)

 int dv[]=new int[256*div]; 
 for (i=0;i<256*div;i++){
     dv[i]=(i/div); 
}

此行为所有可能出现的平均值预先计算了一个查找表。这是为了避免在内循环中进行昂贵的划分。在某些系统上，直接进行除法而不是进行数组查找现在可能实际上更快，但当我编写它时，查找是更快的方法。

for(i=-radius;i<=radius;i++){
            int ind = yi+Math.min(wm,Math.max(i,0));
            p=pix[ind];
            rsum+=(p & 0xff0000)>>16;
            gsum+=(p & 0x00ff00)>>8;
            bsum+= p & 0x0000ff;
        }

此算法之所以快，是因为它使用了滑动窗口，从而减少了所需的像素查找次数。窗口从左边缘向右滑动(并且在第二遍中从上到下)并且只在右侧添加一个像素并从左侧移除一个像素。上面的代码通过根据内核大小用最左边的像素预填充窗口来初始化窗口。

 if(y==0){
   vmin[x]=Math.min(x+radius+1,wm);
   vmax[x]=Math.max(x-radius,0);
  } 

  p1=pix[yw+vmin[x]];
  p2=pix[yw+vmax[x]]; 

这是添加新像素但同时处理边界条件的部分(当窗口试图读取或移除位图外的像素时)。

 rsum+=((p1 & 0xff0000)-(p2 & 0xff0000))>>16;
  gsum+=((p1 & 0x00ff00)-(p2 & 0x00ff00))>>8;
  bsum+= (p1 & 0x0000ff)-(p2 & 0x0000ff);

rsum、gsum和bsum是滑动窗口内像素的累加和。您看到的是右侧的新像素被添加到总和中，而窗口中最左边的像素被从总和中删除。

关于java - 了解超快速模糊算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21418892/