了解超快速模糊算法 [英] Understanding super fast blur algorithm
问题描述
我正在尝试理解超快速模糊算法背后的算法。下面是java的端口，它与android一起作为测试。看起来这个版本做了一些我不太理解的优化，也没有任何评论。
I'm trying to understand the algorithm behind the super fast blur algorithm. Below is the port to java that works with android as a test. Looks like this version makes some optimisations that I don't quite understand and there aren't any comments either.
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);
}
如果我的猜测错了，请纠正我：
Correct me if I'm wrong by my speculations:
以下循环有什么作用？它与预先计算内核表有关吗？怎么样的div，是内核表的大小？我想我想问的是，什么是dv []应该存储？
What does the below loop do? Is it associated with pre-computing the kernel table? What about div, is that the kernel table size? I guess what I'm trying to ask is, what is dv[] supposed to store?
int dv[]=new int[256*div];
for (i=0;i<256*div;i++){
dv[i]=(i/div);
}
查看水平传递：
以下循环看起来像是总结单独的RGB值，但它只在每行的起始像素处执行此操作，因为 yi 仅在我们完成处理所有像素后才递增，直到达到宽度。这是因为我们在处理下一个循环中的像素时最终会增加RGB总和吗？
Looking at the horizontal pass:
The below loop looks like it's summing up the separate RGB values, but it only does this at the starting pixel for each row, since yi is only incremented once we finish processing all pixels up until the width is reached. Is this because we end up adding to the RGB sums as we process the pixels in the next loop?
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;
}
我们是否只根据半径选择最左边的像素和最右边的像素和当前像素位置？
Are we only selecting the left most pixel and right most pixel according to the radius and the current pixel position?
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总数？
Next is what is confusing me the most: Am I correct to say that were getting the difference between right and left pixels and adding that the running RGB totals that we have?
rsum+=((p1 & 0xff0000)-(p2 & 0xff0000))>>16;
gsum+=((p1 & 0x00ff00)-(p2 & 0x00ff00))>>8;
bsum+= (p1 & 0x0000ff)-(p2 & 0x0000ff);
我没看过第二遍，因为这几乎是我的头脑。任何澄清都会受到赞赏，对垂直传递循环的任何评论都会有所帮助。
I haven't had a look at the second pass since this is pretty much going over my head. Any clarification would be appreciated and any commentary on the loop on the vertical pass would be helpful as well thanks.
推荐答案
自从我写完以来那个我想我最好解释一下： - ）
Since I wrote that one I guess I can explain best :-)
int dv[]=new int[256*div];
for (i=0;i<256*div;i++){
dv[i]=(i/div);
}
此行预先计算查找表，查找可能出现的所有可能平均值。这是为了避免在内环中进行昂贵的划分。在某些系统中直接进行除法而不是进行数组查找现在实际上可能更快，但是当我写它时查找是更快的方式。
This line precalculates a lookup table for all the possible mean values that can occur. This is to avoid costly division in the inner loop. On some systems doing the division directly instead of a doing an array lookup might actually be faster nowadays, but when I wrote it the lookup was the faster way.
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;
}
这个算法速度快的原因是它使用滑动窗口因此减少了所需的像素查找次数。窗口从左边缘向右边滑动（在第二次从顶部到底部），只在右边添加一个像素，从左边移除一个像素。上面的代码通过使用最左边的像素预填充窗口来初始化窗口，具体取决于内核大小。
The reason why this algorithm is fast is that it uses a sliding window and thus reduces the number of required pixel lookups. The window slides from the left edge to the right (and in the second pass from top to bottom) and only adds one pixel at the right and removes one from the left. The code above initializes the window by prefilling the window with the leftmost edge pixel depending on the kernel size.
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]];
这是添加新像素但同时处理边界条件的部分（当窗口尝试读取或删除位图外的像素。
This is the part that adds a new pixel but at the same time handles the border conditions (when the window tries to read or remove pixels outside the bitmap).
rsum+=((p1 & 0xff0000)-(p2 & 0xff0000))>>16;
gsum+=((p1 & 0x00ff00)-(p2 & 0x00ff00))>>8;
bsum+= (p1 & 0x0000ff)-(p2 & 0x0000ff);
rsum，gsum和bsum是滑动窗口内累积的像素总和。你看到的是右侧的新像素被添加到总和中，窗口中最左边的像素被从总和中移除。
rsum, gsum and bsum is the accumulated sum of pixels inside the sliding window. What you see is the new pixel on the right side being added to the sum and the leftmost pixel i nthe window being removed from the sum.
这篇关于了解超快速模糊算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
