phu004
Full Member  Posts: 109
NoSuchPersonException
|
 |
«
on:
2011-09-20 18: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 {
public static void filterPixels(int radius, int[] img, int[] offsSreenBuffer){
horizontalBlur(radius, img, offsSreenBuffer);
verticalBlur(radius, offsSreenBuffer, img);
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);
}
}
}
} |
|
|
|
|
|
pitbuller
Sr. Member Posts: 340 Medals: 9
|
|
«
Reply #1 on:
2011-09-21 04: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
| int precalcultedValue = 480 * 639
sourcePositoin = i << 9 + i << 6;destPosition = i + precalcutedValue;
|
|
|
|
|
|
|
Games published by our own members! Go get 'em! 
|
|
|
|
sproingie
JGO Strike Force Posts: 894 Medals: 55
|
|
«
Reply #4 on:
2011-09-21 15: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? |
|
|
|
|
pitbuller
Sr. Member Posts: 340 Medals: 9
|
|
«
Reply #5 on:
2011-09-21 15: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. |
|
|
|
delt0r
Sr. Member Posts: 412 Medals: 12
Computers can do that?
|
|
«
Reply #6 on:
2011-09-21 17: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
|
|
|
sproingie
JGO Strike Force Posts: 894 Medals: 55
|
|
«
Reply #7 on:
2011-09-21 21:57:38 » |
|
if(++i<x++){ Undefined behavior ... execvpe("nethack"), baby (*)! (* - An old version of gcc used to actually do that in response to an unknown pragma) |
|
|
|
|
Orangy Tang
JGO Kernel Posts: 2960 Medals: 37
Monkey for a head
|
|
«
Reply #8 on:
2011-09-22 04: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. |
|
|
|
Orangy Tang
JGO Kernel Posts: 2960 Medals: 37
Monkey for a head
|
|
«
Reply #9 on:
2011-09-22 04:56:00 » |
|
if(++i<x++){ Undefined behavior ... execvpe("nethack"), baby (*)! I'm being slow today, what makes this undefined?  |
|
|
|
Games published by our own members! Go get 'em! 
|
|
Roquen
JGO Strike Force Posts: 823 Medals: 25
|
|
«
Reply #10 on:
2011-09-22 07: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. |
|
|
|
|
delt0r
Sr. Member Posts: 412 Medals: 12
Computers can do that?
|
|
«
Reply #11 on:
2011-09-22 08:52:28 » |
|
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
|
|
|
sproingie
JGO Strike Force Posts: 894 Medals: 55
|
|
«
Reply #12 on:
2011-09-22 12:38:35 » |
|
if(++i<x++){ Undefined behavior ... execvpe("nethack"), baby (*)! I'm being slow today, what makes this undefined? 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.htmlI'm not actually sure whether Java also left it undefined, though the JLS tends to preclude such things as nasal demons. |
|
|
|
|
Orangy Tang
JGO Kernel Posts: 2960 Medals: 37
Monkey for a head
|
|
«
Reply #13 on:
2011-09-22 13: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.htmlI'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. |
|
|
|
sproingie
JGO Strike Force Posts: 894 Medals: 55
|
|
«
Reply #14 on:
2011-09-22 13:52:28 » |
|
Ohhhh indeed. I did not see the 'i' in there, I read it as "++x++" My old eyes are going bad  |
|
|
|
|
phu004
Full Member Posts: 109
NoSuchPersonException
|
|
«
Reply #15 on:
2011-09-22 19:09:40 » |
|
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  Really nice trick indeed. |
|
|
|
|
zyzz
JGO n00b Posts: 19
|
|
«
Reply #16 on:
2012-03-23 22: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
|
|
|
|
|
Roquen
JGO Strike Force Posts: 823 Medals: 25
|
|
«
Reply #17 on:
2012-03-24 03:41:30 » |
|
I think you mean ==. I'm open minded, if you want to be a large bundle of sticks then go you.
|
|
|
|
|
zyzz
JGO n00b Posts: 19
|
|
«
Reply #18 on:
2012-03-24 09: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  |
|
|
|
|
BoBear2681
Full Member Posts: 238 Medals: 8
|
|
«
Reply #19 on:
2012-03-24 10: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 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; |
|
|
|
|
|
|
