Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (498)
Games in Android Showcase (117)
games submitted by our members
Games in WIP (563)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  fast box blur algorithm  (Read 8072 times)
0 Members and 1 Guest are viewing this topic.
Offline phu004

JGO Coder


Medals: 4
Projects: 9
Exp: 10 years


NoSuchPersonException


« Posted 2011-09-20 22:06:07 »

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!

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
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);
         }
      }
   }

}
Offline pitbuller
« Reply #1 - Posted 2011-09-21 08:19:36 »

Try these changes.
Loop from end to 0 not other way around.
1  
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
1  
2  
3  
4  
5  
6  
7  
8  
//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
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #2 - Posted 2011-09-21 08:48:58 »

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. Huh

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

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline nsigma
« Reply #3 - Posted 2011-09-21 09:10:12 »

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!  Angry

Best wishes, Neil

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline sproingie

JGO Kernel


Medals: 202



« Reply #4 - Posted 2011-09-21 19:43:17 »

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

PROVE IT.

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

Offline pitbuller
« Reply #5 - Posted 2011-09-21 19:53:09 »

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

PROVE IT.

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



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.
Offline delt0r

JGO Knight


Medals: 27
Exp: 18 years


Computers can do that?


« Reply #6 - Posted 2011-09-21 21:15:19 »

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:
1  
2  
3  
if(++i<x++){
    System.out.println("I am freaking awesome");
}

To which I say, Yuck!

I have no special talents. I am only passionately curious.--Albert Einstein
Offline sproingie

JGO Kernel


Medals: 202



« Reply #7 - Posted 2011-09-22 01:57:38 »

Quote
if(++i<x++){

Undefined behavior ... execvpe("nethack"), baby (*)!




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


Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #8 - Posted 2011-09-22 08:55:10 »

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

PROVE IT.

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



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.

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.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #9 - Posted 2011-09-22 08:56:00 »

Quote
if(++i<x++){

Undefined behavior ... execvpe("nethack"), baby (*)!

I'm being slow today, what makes this undefined? Huh

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen
« Reply #10 - Posted 2011-09-22 11:54: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.
Offline delt0r

JGO Knight


Medals: 27
Exp: 18 years


Computers can do that?


« Reply #11 - Posted 2011-09-22 12:52:28 »

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.
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.

I have no special talents. I am only passionately curious.--Albert Einstein
Offline sproingie

JGO Kernel


Medals: 202



« Reply #12 - Posted 2011-09-22 16:38:35 »

Quote
if(++i<x++){

Undefined behavior ... execvpe("nethack"), baby (*)!

I'm being slow today, what makes this undefined? Huh

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.

Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #13 - Posted 2011-09-22 17:14:43 »

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.
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.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline sproingie

JGO Kernel


Medals: 202



« Reply #14 - Posted 2011-09-22 17:52:28 »

Ohhhh indeed.  I did not see the 'i' in there, I read it as "++x++"

My old eyes are going bad  Clueless
Offline phu004

JGO Coder


Medals: 4
Projects: 9
Exp: 10 years


NoSuchPersonException


« Reply #15 - Posted 2011-09-22 23:09:40 »



Quote
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. Huh
Presumably you've read this? http://www.gamasutra.com/view/feature/3102/four_tricks_for_fast_blurring_in_.php

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.


Quote
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!  Angry

Best wishes, Neil

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 Smiley
Really nice trick indeed.
 
Offline zyzz

Senior Newbie





« Reply #16 - Posted 2012-03-24 02:28:46 »

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
Offline Roquen
« Reply #17 - Posted 2012-03-24 07:41:30 »

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

Senior Newbie





« Reply #18 - Posted 2012-03-24 13:11:42 »

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

== isn't a declaration operator, just an equality one Shocked
Offline BoBear2681

JGO Coder


Medals: 18



« Reply #19 - Posted 2012-03-24 14:54:16 »

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

== isn't a declaration operator, just an equality one Shocked

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:

1  
2  
3  
4  
int a = 0;
boolean isTrue = ++a == 1;
a = 0;
boolean isAlsoTrue = a++ == 0;
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Grunnt (16 views)
2014-09-23 14:38:19

radar3301 (14 views)
2014-09-21 23:33:17

BurntPizza (31 views)
2014-09-21 02:42:18

BurntPizza (22 views)
2014-09-21 01:30:30

moogie (20 views)
2014-09-21 00:26:15

UprightPath (29 views)
2014-09-20 20:14:06

BurntPizza (33 views)
2014-09-19 03:14:18

Dwinin (48 views)
2014-09-12 09:08:26

Norakomi (75 views)
2014-09-10 13:57:51

TehJavaDev (105 views)
2014-09-10 06:39:09
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!