fast box blur algorithm

Performance Tuning
#1

Hi guys, I am trying to implement a real time box blur filter on a 640 x 480 screen. My strategy is doing 2 separate 1D blurs, blur pixels in horizontal direction in the first pass, then blur vertically in the second pass. So we effectively end up using a cross shaped kernel instead of the square shape (hence less pixels to be processed over all).

Below is my code, it works fine, result looks great, but i wonder if you guys can suggest anything which could further speed up the algorithm?

Thanks in advance!



public class BlurFilter {
	//Blur filter set the value of each pixel to the average value of its neighboring pixels.
	//the filter kernel used here has a cross shape instead of square, the size of the kernel depends on radius.
	public static void filterPixels(int radius, int[] img, int[] offsSreenBuffer){
		
		//blur image in horizontal direction then vertical direction
		horizontalBlur(radius, img, offsSreenBuffer);
		verticalBlur(radius, offsSreenBuffer, img);
		
		//repeat for another time for better quality
		horizontalBlur(radius, img, offsSreenBuffer);
		verticalBlur(radius, offsSreenBuffer, img);
		
	}
	
	public static void horizontalBlur(int radius, int[] source, int[] dest){
		int i,j,sourcePositoin, destPosition,rgb1, rgb2, tr, tg, tb, pixelCount;
		for(i = 0; i < 480; i++){
			sourcePositoin = i * 640;
			destPosition = i + 480 * 639;
			
			tr = 0; tg = 0; tb = 0;
			for(j = 0; j <= radius; j++){
				rgb1 = source[sourcePositoin + j];
				tr+=((rgb1 & 0xff0000) >> 16);
				tg+=((rgb1 & 0x00ff00) >> 8);
				tb+=(rgb1 & 0xff);
			}
			pixelCount = radius + 1;
			dest[destPosition] = ((tr/pixelCount)<<16)|((tg/pixelCount)<<8)|(tb/pixelCount);
			sourcePositoin++;
			destPosition-=480;
			pixelCount++;
			for(j = 1; j <= radius; j++, sourcePositoin++, destPosition-=480, pixelCount++){
				rgb1 = source[sourcePositoin + radius];
				tr+=((rgb1 & 0xff0000) >> 16);
				tg+=((rgb1 & 0x00ff00) >> 8);
				tb+=(rgb1 & 0xff);
				dest[destPosition] = ((tr/pixelCount)<<16)|((tg/pixelCount)<<8)|(tb/pixelCount);
			}
			pixelCount--;
			for(j = radius + 1; j < 640 - radius; j++, sourcePositoin++, destPosition-=480){
				rgb1 = source[sourcePositoin + radius];
				rgb2 = source[sourcePositoin - radius - 1];
				tr+=(((rgb1 & 0xff0000) - (rgb2 & 0xff0000)) >> 16);
				tg+=(((rgb1 & 0x00ff00) - (rgb2 & 0x00ff00)) >> 8);
				tb+=((rgb1 & 0xff) - (rgb2 & 0xff));
				dest[destPosition] = ((tr/pixelCount)<<16)|((tg/pixelCount)<<8)|(tb/pixelCount);
			}
			pixelCount--;
			for(j = 640 - radius; j < 640; j++, sourcePositoin++, destPosition-=480, pixelCount--){
				rgb2 = source[sourcePositoin - radius - 1];
				tr-=((rgb2 & 0xff0000) >> 16);
				tg-=((rgb2 & 0x00ff00) >> 8);
				tb-=(rgb2 & 0xff);
				dest[destPosition] = ((tr/pixelCount)<<16)|((tg/pixelCount)<<8)|(tb/pixelCount);
			}
		}
	}
	
	public static void verticalBlur(int radius, int[] source, int[] dest){
		int i,j,sourcePositoin, destPosition,rgb1, rgb2, tr, tg, tb, pixelCount;
		for(i = 0; i < 640; i++){
			sourcePositoin = i * 480;
			destPosition = 639 -i;
			
			tr = 0; tg = 0; tb = 0;
			for(j = 0; j <= radius; j++){
				rgb1 = source[sourcePositoin + j];
				tr+=((rgb1 & 0xff0000) >> 16);
				tg+=((rgb1 & 0x00ff00) >> 8);
				tb+=(rgb1 & 0xff);
			}
			pixelCount = radius + 1;
			dest[destPosition] = ((tr/pixelCount)<<16)|((tg/pixelCount)<<8)|(tb/pixelCount);
			sourcePositoin++;
			destPosition+=640;
			pixelCount++;
			for(j = 1; j <= radius; j++, sourcePositoin++, destPosition+=640, pixelCount++){
				rgb1 = source[sourcePositoin + radius];
				tr+=((rgb1 & 0xff0000) >> 16);
				tg+=((rgb1 & 0x00ff00) >> 8);
				tb+=(rgb1 & 0xff);
				dest[destPosition] = ((tr/pixelCount)<<16)|((tg/pixelCount)<<8)|(tb/pixelCount);
			}
			pixelCount--;
			for(j = radius + 1; j < 480 - radius; j++, sourcePositoin++, destPosition+=640){
				rgb1 = source[sourcePositoin + radius];
				rgb2 = source[sourcePositoin - radius - 1];
				tr+=(((rgb1 & 0xff0000) - (rgb2 & 0xff0000)) >> 16);
				tg+=(((rgb1 & 0x00ff00) - (rgb2 & 0x00ff00)) >> 8);
				tb+=((rgb1 & 0xff) - (rgb2 & 0xff));
				dest[destPosition] = ((tr/pixelCount)<<16)|((tg/pixelCount)<<8)|(tb/pixelCount);
			}
			pixelCount--;
			for(j = 480 - radius; j < 480; j++, sourcePositoin++, destPosition+=640, pixelCount--){
				rgb2 = source[sourcePositoin - radius - 1];
				tr-=((rgb2 & 0xff0000) >> 16);
				tg-=((rgb2 & 0x00ff00) >> 8);
				tb-=(rgb2 & 0xff);
				dest[destPosition] = ((tr/pixelCount)<<16)|((tg/pixelCount)<<8)|(tb/pixelCount);
			}
		}
	}

}
#2

Try these changes.
Loop from end to 0 not other way around.

for(i = 480-1; i >= 0; --i)

Use ++i not i++. In c++ world this have small performance difference. Don’t know about java.

Try these


//outside of loop
int  precalcultedValue = 480 * 639

//in loop
sourcePositoin = i << 9 + i << 6;//same as i*640
destPosition = i + precalcutedValue;

//for *480 = 512-32
#3

Perhaps you could explain your current algorithm a bit? It looks like an attempt to do a running-average, but I can’t follow it fully, it seems to have too many loops and magic numbers. ???

Presumably you’ve read this? http://www.gamasutra.com/view/feature/3102/four_tricks_for_fast_blurring_in_.php

#4

I use this class (http://code.google.com/p/praxis/source/browse/ripl/src/net/neilcsmith/ripl/ops/Blur.java) if you’re interested in a comparison. It uses the same principle of separating horizontal and vertical passes. It was derived from an earlier iteration of this class from PulpCore (http://code.google.com/p/pulpcore/source/browse/pulpcore-runtime/src/main/java/pulpcore/image/filter/Blur.java), which in turn was derived from code by Romain Guy in Filthy Rich Clients (http://filthyrichclients.org/)

My suggestion would be to look at Romain’s code as it might be easiest to follow. Go to the Filthy Rich Clients webpage -> Examples -> Chapter 16. Static Effects, and look for FastBlur. Bloody site uses JavaScript which means deep linking isn’t easy! >:(

Best wishes, Neil

#5

PROVE IT.

Didn’t I just see this claim made in another post?

#6

Maybe I should not belive my professor so naively. But its common belive and there is lot of fun stuff at google about that. I triead to test that with nanotimer but results was too wide margin to get anything statistically significant.

#7

If ++i is faster than i++ in this context it is because you have a crap compiler or you forgot to use your -O3 switch (or even just plain -O). This is what is called a peephole optimization, like changing i=i*2 to i=i<<1, its very easy to and cost no compile time.

The only time i think it could possibly make a difference is if you use the post increment/pre increment behavior somehow. Say like this:


if(++i<x++){
    System.out.println("I am freaking awesome");
}

To which I say, Yuck!

#8

[quote]if(++i<x++){
[/quote]
Undefined behavior … execvpe(“nethack”), baby (*)!

(* - An old version of gcc used to actually do that in response to an unknown pragma)

#9

Pre-increment may be faster in C++ when applied to objects. This most commonly occurs with iterators where you do ++iterator at the end of a loop. With the post-increment there’s a temporary object created and discarded, but not with the pre-increment. Of course stupid people like your professor probably just start parroting ‘pre increment is faster’ without understanding that.

Of course with a good optimising compiler the temporary may even be optimised out, but IMHO it’s not good style to rely on that.

#10

Undefined behavior … execvpe(“nethack”), baby (*)!
[/quote]
I’m being slow today, what makes this undefined? ???

#11

Even with primitives it depends on a lot of on specific arch & code sequence factors, consider these two comparisons:

(0 == --i) vs. (0 == i--)

Examples:

  • what ops set the zero flag, dec-jump-on-zero, etc
  • counter in register vs. spilled (does load set zero flag)
  • surrounding code (filling any delays, etc.)

So no generalization is possible even for some fixed targets.

#12

[quote]Of course with a good optimising compiler the temporary may even be optimised out, but IMHO it’s not good style to rely on that.
[/quote]
If your compiler can’t do this, throw it away, or dust out that F77 compiler and stick with that, or even assembly. Its been 30 years since compilers needed to be baby sat through every instruction.

#13

I’m being slow today, what makes this undefined? ???
[/quote]
The C standard says the precise behavior of mixing preincrement and postincrement is undefined. Now in a sane world, that just means the precise ordering can’t be relied upon: one implementation might post-increment x after preincrement, another might end up incrementing only the unincremented x, making the post-increment a no-op. But there are some more exotic interpretations of “undefined behavior” out there, such as the Jargon File’s “causes demons to fly out of your nose” tradition: http://catb.org/jargon/html/N/nasal-demons.html

I’m not actually sure whether Java also left it undefined, though the JLS tends to preclude such things as nasal demons.

#14

Are you sure you’re not confusing this with modifying multiple times without a sequence point? The code snippit is incrementing two separate variables, which I think should be ok. Now if they were both operating on the same variable I think you’d be right.

#15

Ohhhh indeed. I did not see the ‘i’ in there, I read it as “++x++”

My old eyes are going bad :clue:

#16

Yeah , I did have a look at the link above , but most of my code was inspired from Jerry’s image processing page (http://www.jhlabs.com/ip/). I found Jerry’s page easier to follow up thanks to the live applet demo he put up there.

I have read through the code of “Romain Guy”, as you said it is quite easy to follow. I was able to replace all my “/” operations by lookup tables and got 3fps boost in performance :slight_smile:
Really nice trick indeed.

#17

I know this is an old thread, but generally:

int a = 0;

void derrfunction(){
++a = 1;
a++ = 0;
}

it’s incredibly asinine to argue about its speed though (like, it does NOT matter at all whatsoever), but it definitely feels better to know when to utilize the proper increment operators at any given time

#18

I think you mean ==. I’m open minded, if you want to be a large bundle of sticks then go you.

#19

== isn’t a declaration operator, just an equality one :o

#20

Aye, but you’ve changed your example from what it was when Roquen read it, and what you have now wouldn’t even compile (a++ and ++a are invalid lvalues). His point was that in your original post, you probably meant something more like this:


int a = 0;
boolean isTrue = ++a == 1;
a = 0;
boolean isAlsoTrue = a++ == 0;