[java] [Image] Algorithmes de Flou rapide

Version imprimable

Bonjour,

Voici 2 algorithmes que j'ai repris du site Mario Klingeman adaptés au Java pour faire un flou rapide suivant un certain rayon.

Le résultat est proche d'un flou gaussien, mais il peut y avoir certains artefacts pour de grosses images (>4000*4000).

V1 Box Blur :

Code:

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/**
 * 
 */
package filmlooking;
 
import java.awt.image.BufferedImage;
 
import millie.plugins.GenericPluginFilter;
import millie.plugins.PluginInfo;
import millie.plugins.parameters.IntSliderParameter;
 
/**
 * 
 *  Inspiré du code de Mario Klingemann (incubator)
 *  
 * @author florent
 */
@PluginInfo(name = "Fast Blur", category = "Flou")
public class FastBlurFilter extends GenericPluginFilter {
 
	public FastBlurFilter() {
		setPluginName("Fast Blur");
		setRefreshable(true);
		setLongProcessing(true);
 
		addParameter(new IntSliderParameter("rayon", "Rayon", 1, 50, 3));
 
	}
 
	@Override
	public BufferedImage filter() throws Exception {
		BufferedImage input = getInputImage();
		BufferedImage output = new BufferedImage(input.getWidth(), input
				.getHeight(), input.getType());
		int rayon = getIntValue("rayon");
 
		int width = input.getWidth();
		int height = input.getHeight();
		int maxWH = Math.max(width, height);
 
		int widthm = width - 1;
		int heightm = height - 1;
		int aire = width * height;
		int div = 2 * rayon + 1;
		int r[] = new int[aire];
		int g[] = new int[aire];
		int b[] = new int[aire];
		int rsum, gsum, bsum, p, p1, p2, yp, yi, yw;
		int vmin[] = new int[maxWH];
		int vmax[] = new int[maxWH];
 
		int[] pixels = input.getRGB(0, 0, width, height, null, 0, width);
 
		int dv[] = new int[256 * div];
		for (int i = 0; i < 256 * div; i++) {
			dv[i] = (i / div);
		}
 
		yw = yi = 0;
 
		for (int y = 0; y < height; y++) {
			rsum = gsum = bsum = 0;
			for (int i = -rayon; i <= rayon; i++) {
				p = pixels[yi + Math.min(widthm, Math.max(i, 0))];
				rsum += (p & 0xff0000) >> 16;
				gsum += (p & 0x00ff00) >> 8;
				bsum += p & 0x0000ff;
			}
			for (int x = 0; x < width; x++) {
 
				r[yi] = dv[rsum];
				g[yi] = dv[gsum];
				b[yi] = dv[bsum];
 
				if (y == 0) {
					vmin[x] = Math.min(x + rayon + 1, widthm);
					vmax[x] = Math.max(x - rayon, 0);
				}
				p1 = pixels[yw + vmin[x]];
				p2 = pixels[yw + vmax[x]];
 
				rsum += ((p1 & 0xff0000) - (p2 & 0xff0000)) >> 16;
				gsum += ((p1 & 0x00ff00) - (p2 & 0x00ff00)) >> 8;
				bsum += (p1 & 0x0000ff) - (p2 & 0x0000ff);
				yi++;
			}
			yw += width;
		}
 
		for (int x = 0; x < width; x++) {
			rsum = gsum = bsum = 0;
			yp = -rayon * width;
			for (int i = -rayon; i <= rayon; i++) {
				yi = Math.max(0, yp) + x;
				rsum += r[yi];
				gsum += g[yi];
				bsum += b[yi];
				yp += width;
			}
			yi = x;
			for (int y = 0; y < height; y++) {
				pixels[yi] = 0xff000000 | (dv[rsum] << 16) | (dv[gsum] << 8)
						| dv[bsum];
				if (x == 0) {
					vmin[y] = Math.min(y + rayon + 1, heightm) * width;
					vmax[y] = Math.max(y - rayon, 0) * width;
				}
				p1 = x + vmin[y];
				p2 = x + vmax[y];
 
				rsum += r[p1] - r[p2];
				gsum += g[p1] - g[p2];
				bsum += b[p1] - b[p2];
 
				yi += width;
			}
		}
 
		output.setRGB(0, 0, width, height, pixels, 0, width);
		return output;
	}
 
}

V2 :

Code:

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
/**
 * 
 */
package filmlooking;
 
import java.awt.image.BufferedImage;
 
import millie.plugins.GenericPluginFilter;
import millie.plugins.PluginInfo;
import millie.plugins.parameters.IntSliderParameter;
 
/**
 * Inspiré du code de Mario Klingemann (incubator)
 * 
 * @author florent
 * 
 */
@PluginInfo(name = "Stack Blur", category = "Flou")
public class StackBlurFilter extends GenericPluginFilter {
 
	public StackBlurFilter() {
		setPluginName("Stack Blur");
		setRefreshable(true);
		setLongProcessing(true);
 
		addParameter(new IntSliderParameter("rayon", "Rayon", 1, 50, 3));
 
	}
 
	@Override
	public BufferedImage filter() throws Exception {
		BufferedImage input = getInputImage();
		BufferedImage output = new BufferedImage(input.getWidth(), input
				.getHeight(), input.getType());
		int rayon = getIntValue("rayon");
 
		int width = input.getWidth();
		int height = input.getHeight();
		int maxWH = Math.max(width, height);
 
		int widthm = width - 1;
		int heightm = height - 1;
		int aire = width * height;
		int div = 2 * rayon + 1;
		int r[] = new int[aire];
		int g[] = new int[aire];
		int b[] = new int[aire];
		int rsum, gsum, bsum, p, yp, yi = 0, yw = 0;
		int vmin[] = new int[maxWH];
 
		int[] pixels = input.getRGB(0, 0, width, height, null, 0, width);
 
		int divsum = (div + 1) >> 1;
		divsum *= divsum;
		int dv[] = new int[256 * divsum];
		for (int i = 0; i < 256 * divsum; i++) {
			dv[i] = (i / divsum);
		}
 
		int[][] stack = new int[div][3];
		int stackpointer;
		int stackstart;
		int[] sir;
		int rbs;
		int r1 = rayon + 1;
		int routsum, goutsum, boutsum;
		int rinsum, ginsum, binsum;
 
		for (int y = 0; y < height; y++) {
			rinsum = ginsum = binsum = routsum = goutsum = boutsum = rsum = gsum = bsum = 0;
			for (int i = -rayon; i <= rayon; i++) {
				p = pixels[yi + Math.min(widthm, Math.max(i, 0))];
				sir = stack[i + rayon];
				sir[0] = (p & 0xff0000) >> 16;
				sir[1] = (p & 0x00ff00) >> 8;
				sir[2] = (p & 0x0000ff);
				rbs = r1 - Math.abs(i);
				rsum += sir[0] * rbs;
				gsum += sir[1] * rbs;
				bsum += sir[2] * rbs;
				if (i > 0) {
					rinsum += sir[0];
					ginsum += sir[1];
					binsum += sir[2];
				} else {
					routsum += sir[0];
					goutsum += sir[1];
					boutsum += sir[2];
				}
			}
			stackpointer = rayon;
 
			for (int x = 0; x < width; x++) {
 
				r[yi] = dv[rsum];
				g[yi] = dv[gsum];
				b[yi] = dv[bsum];
 
				rsum -= routsum;
				gsum -= goutsum;
				bsum -= boutsum;
 
				stackstart = stackpointer - rayon + div;
				sir = stack[stackstart % div];
 
				routsum -= sir[0];
				goutsum -= sir[1];
				boutsum -= sir[2];
 
				if (y == 0) {
					vmin[x] = Math.min(x + rayon + 1, widthm);
				}
				p = pixels[yw + vmin[x]];
 
				sir[0] = (p & 0xff0000) >> 16;
				sir[1] = (p & 0x00ff00) >> 8;
				sir[2] = (p & 0x0000ff);
 
				rinsum += sir[0];
				ginsum += sir[1];
				binsum += sir[2];
 
				rsum += rinsum;
				gsum += ginsum;
				bsum += binsum;
 
				stackpointer = (stackpointer + 1) % div;
				sir = stack[(stackpointer) % div];
 
				routsum += sir[0];
				goutsum += sir[1];
				boutsum += sir[2];
 
				rinsum -= sir[0];
				ginsum -= sir[1];
				binsum -= sir[2];
 
				yi++;
			}
			yw += width;
		}
		for (int x = 0; x < width; x++) {
			rinsum = ginsum = binsum = routsum = goutsum = boutsum = rsum = gsum = bsum = 0;
			yp = -rayon * width;
			for (int i = -rayon; i <= rayon; i++) {
				yi = Math.max(0, yp) + x;
 
				sir = stack[i + rayon];
 
				sir[0] = r[yi];
				sir[1] = g[yi];
				sir[2] = b[yi];
 
				rbs = r1 - Math.abs(i);
 
				rsum += r[yi] * rbs;
				gsum += g[yi] * rbs;
				bsum += b[yi] * rbs;
 
				if (i > 0) {
					rinsum += sir[0];
					ginsum += sir[1];
					binsum += sir[2];
				} else {
					routsum += sir[0];
					goutsum += sir[1];
					boutsum += sir[2];
				}
 
				if (i < heightm) {
					yp += width;
				}
			}
			yi = x;
			stackpointer = rayon;
			for (int y = 0; y < height; y++) {
				pixels[yi] = 0xff000000 | (dv[rsum] << 16) | (dv[gsum] << 8)
						| dv[bsum];
 
				rsum -= routsum;
				gsum -= goutsum;
				bsum -= boutsum;
 
				stackstart = stackpointer - rayon + div;
				sir = stack[stackstart % div];
 
				routsum -= sir[0];
				goutsum -= sir[1];
				boutsum -= sir[2];
 
				if (x == 0) {
					vmin[y] = Math.min(y + r1, heightm) * width;
				}
				p = x + vmin[y];
 
				sir[0] = r[p];
				sir[1] = g[p];
				sir[2] = b[p];
 
				rinsum += sir[0];
				ginsum += sir[1];
				binsum += sir[2];
 
				rsum += rinsum;
				gsum += ginsum;
				bsum += binsum;
 
				stackpointer = (stackpointer + 1) % div;
				sir = stack[stackpointer];
 
				routsum += sir[0];
				goutsum += sir[1];
				boutsum += sir[2];
 
				rinsum -= sir[0];
				ginsum -= sir[1];
				binsum -= sir[2];
 
				yi += width;
			}
		}
 
		output.setRGB(0, 0, width, height, pixels, 0, width);
		return output;
 
	}
}

Exemple avec une image de 4200*2800.
Une convolution classique avec un rayon de 10 donne un temps de 30sec (sur ma machine)
Avec le deuxième algo, j'ai un temps de 5sec pour un rayon de 50 (ce qui est raisonnable avec la taille de l'image)

En haut à gauche, originale, en haut à droite, Fast Blur avec rayon 50, en bas à gauche, Stack Blur avec rayon 50

http://humbert-florent.developpez.co...e/gaussien.jpg

Citation:

Envoyé par millie

Le résultat est proche d'un flou gaussien, mais il peut y avoir certains artefacts pour de grosses images (>4000*4000).

Pour le flou gaussien avec un grand sigma² (= grand rayon), on peut accélérer les calculs en approximant une convolution sigma²=4 par une réduction d'image à 50% (cf. la théorie des scale-space).

Donc, pour un sigma²=625 (rayon=50), on peut approximer le filtrage par:

sigma² = 625 = 4*4*4*4*2.44 = 4^4 * 2.44

1. réduction à 6.25% (0.5^4)
2. convolution par une gaussienne sigma²=2.44 (rayon=3)
3. agrandissement à 1600% (2^4)

Pour un bon résultat visuel, il faut plutot choisir un noyaux d'agrandissement gaussien et donc calculer le sigma² plus finement. Par exemple:

1. réduction à 12.5% (0.5^3)
2. convolution par une gaussienne sigma²=9.51 (rayon=6)
3. agrandissement à 800% (2^3)
4. convolution par une gaussienne sigma²=16 (rayon=8)

Ce qui nous donne au final également sigma² = (4^3)*9.51 + 16 = 625.

On a ainsi une bonne approximation d'un flou gaussien de rayon 50 par l'utilisation de 2 flous gaussiens de rayon 6 et 8. Sur ma machine, les temps de calculs sont considérablement réduits:

Image 3543x2362:
Flou gaussien rapide (sigma²=625, rayon=50) : 4.8s
Flou gaussien normal (sigma²=625, rayon=50) : 4m 25s

http://xphilipp.developpez.com/tmp/fastblur.jpg

Exemple de code (pas très optimisé :?)

Code:

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
107
108
109
public static float[] gaussianKernel1D(double sigma2) {
	int radius = (int)Math.round(2*Math.sqrt(sigma2));
	// compute gaussian values
	float[] data = new float[1+2*radius];
	for(int r=-radius;r<=radius;r++)
		data[r+radius] = (float)Math.exp(-(r*r)/(2.0*sigma2));
	// normalize
	float sum=0;
	for(int i=0;i<data.length;i++) sum+=data[i];
	for(int i=0;i<data.length;i++) data[i]/=sum;
	return data;
}
 
public static void convolve2DSeparate(BufferedImage input, float[] kernel) {
	float r,g,b;
 
	int width = input.getWidth(), height=input.getHeight();
	WritableRaster raster = input.getRaster();
	int kernelradius = kernel.length/2;
 
	// horizontal
	int[][] wbuffer = new int[width][3];
	for(int y=0;y<height;y++) {
		for(int x=0;x<width;x++) {
			wbuffer[x][0]=raster.getSample(x,y,0);
			wbuffer[x][1]=raster.getSample(x,y,1);
			wbuffer[x][2]=raster.getSample(x,y,2);
		}
		for(int x=0;x<width;x++) {
			r=g=b=0;
			for(int k=-kernelradius;k<=kernelradius;k++)
				if (x+k>=0 && x+k<width) {
					r+=kernel[kernelradius+k]*wbuffer[x+k][0];
					g+=kernel[kernelradius+k]*wbuffer[x+k][1];
					b+=kernel[kernelradius+k]*wbuffer[x+k][2];
				}
			raster.setSample(x, y, 0, (int)r);
			raster.setSample(x, y, 1, (int)g);
			raster.setSample(x, y, 2, (int)b);
		}
	}
 
 
	// vertical
	int[][] hbuffer = new int[height][3];
	for(int x=0;x<width;x++) {
		for(int y=0;y<height;y++) {
			hbuffer[y][0] = raster.getSample(x,y,0);
			hbuffer[y][1] = raster.getSample(x,y,1);
			hbuffer[y][2] = raster.getSample(x,y,2);
		}
 
		for(int y=0;y<height;y++) {
			r=g=b=0;
			for(int k=-kernelradius;k<=kernelradius;k++)
				if (y+k>=0 && y+k<height) {
					r+=kernel[kernelradius+k]*hbuffer[y+k][0];
					g+=kernel[kernelradius+k]*hbuffer[y+k][1];
					b+=kernel[kernelradius+k]*hbuffer[y+k][2];
				}
			raster.setSample(x, y, 0, (int)r);
			raster.setSample(x, y, 1, (int)g);
			raster.setSample(x, y, 2, (int)b);
		}
	}
}
 
public static BufferedImage fastGaussianBlur(BufferedImage input, double sigma2) {
	int factor=1;              // reduction factor
	double ds_sigma2=sigma2;   // downscale gaussian sigma2
	double us_sigma2=1.0;      // final upscale gaussian sigma2
 
	// find best reduction factor and sigma2
	int scale=0;
	while(us_sigma2<ds_sigma2) {  
		// exit when downscale/upscale sigma2 are equivalents
 
		// compute sigma2 for next scale
		scale++;
		double next_us_sigma2 = Math.pow(factor, 2);
		double next_ds_sigma2 = (sigma2 - next_us_sigma2) / Math.pow(4, scale); 
		if (next_ds_sigma2<=0) break;
 
		factor*=2;
		ds_sigma2 = next_ds_sigma2;
		us_sigma2 = next_us_sigma2;
	}
 
	// downscale (fast)
	int width = input.getWidth(), height=input.getHeight();
	BufferedImage dwnscaled = new BufferedImage(width/factor, height/factor, BufferedImage.TYPE_INT_RGB);
	dwnscaled.createGraphics().drawImage(
			input.getScaledInstance(width/factor, height/factor, BufferedImage.SCALE_AREA_AVERAGING)
			, 0, 0, null);
 
	// convolve with gaussian 
	convolve2DSeparate(dwnscaled,gaussianKernel1D(ds_sigma2));
 
	// upscale (fast)
	BufferedImage upscaled = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
	upscaled.createGraphics().drawImage(
			dwnscaled.getScaledInstance(width, height, BufferedImage.SCALE_FAST)
			, 0, 0, null);
 
	// convolve with gaussian
	convolve2DSeparate(upscaled,gaussianKernel1D(us_sigma2));
 
	return upscaled;
}

20/11/2009, 07h50
PRomu@ld

Citation:

pas très optimisé

En même temps c'est du java :aie:

:dehors:

Citation:

Flou gaussien rapide (sigma²=625, rayon=50) : 4.8s
Flou gaussien normal (sigma²=625, rayon=50) : 4m 25s

A whouai quand même !!! 8O

Tu peux faire une différence entre les deux images pour voir où se situent les différences (parce que visuellement c'est difficile de voir les difs, s'il y en a)
20/11/2009, 09h46
pseudocode

Citation:

Envoyé par PRomu@ld

Tu peux faire une différence entre les deux images pour voir où se situent les différences (parce que visuellement c'est difficile de voir les difs, s'il y en a)

Oui, il y a des différences (c'est quand meme une approximation). Voila visuellement les écarts, en echelle Log sinon on ne voit rien :D

http://xphilipp.developpez.com/tmp/fblurdiff.jpg

La corrélation entre les 2 images est de :
- Canal rouge : 0.9999758908494483
- Canal vert : 0.9999745410443774
- Canal bleu : 0.9999700577679397

La SSD est de
- Canal rouge : 1.98496456860112 par pixel
- Canal vert : 1.939436338316505 par pixel
- Canal bleu : 1.9394487657742079 par pixel

(pas mal, non ? :D)
20/11/2009, 09h51
millie

Dis moi si je me trompe.

Mais plus le noyau est petit et plus la différence sera grande ?
20/11/2009, 12h20
pseudocode

Citation:

Envoyé par millie

Dis moi si je me trompe.

Mais plus le noyau est petit et plus la différence sera grande ?

Oui, tout a fait. De plus, le traitement risque d'etre plus long qu'avec une convolution classique.

C'est une technique à réserver pour les grands noyaux (du genre rayon>10). Ca peut être utilisé pour faire une "preview" avant d'appliquer le filtre réel.
20/11/2009, 19h48
PRomu@ld

Citation:

Ca peut être utilisé pour faire une "preview" avant d'appliquer le filtre réel.

Oui, c'est ce à quoi je pensais. Mais pour que la preview soit acceptable, il faut que la preview soit suffisamment représentative d'où ma question. Vu les coefs de corrélation ça parait plutôt bon
[MODE RECHERCHE ON]
Mais attention différentier les canaux c'est pas toujours la panacée. Il faudrait peut-être faire une corrélation sur une distance couleur (et/ou perceptuelle)
[/MODE RECHERCHE OFF]

Mais en tout cas merci pour la visualisation des différences. ;)
24/11/2009, 10h36
pseudocode

Je reposte ma version au format millie-plugins (sources incluses dans le jar).

http://xphilipp.developpez.com/contr...BlurPlugin.jar
18/01/2011, 17h04
Gsyltc

Hum....

Et personne n'aurait cela en Ocaml par hasard ?? :roll:

Car je dois pondre un algorithme de flou.
Déjà, je ne sais pas comment on fait du flou, alors écrire le code ^^

Quelqu'un pourrait m'expliquer le principe du flou s'il vous plait ?

Voici ce que j'en sais après (des heures) de recherches

Il faut faire la moyenne des pixels aux alentours (ou quelque chose comme cela) et l'appliquer au pixel courant.

Après j'ai vu des formules "de la mort qui tue" avec plein d'intégrale et de dérivées, mais bon...

Voilà, c'est tout ce que j'ai retenu de mes recherches, le reste c'est un peu comme apprendre une langue extra-terrestre !!

Bon déjà, merci pour ce post. Je vais tenter de décortiquer les algorithmes présents et tenter d'adapter cela en Ocaml.

Mais si vous avez de plus amples informations, je suis preneur :)
18/01/2011, 17h26
pseudocode

Citation:

Envoyé par Gsyltc

Mais si vous avez de plus amples informations, je suis preneur :)

Les algos proposés dans cette discussion sont des approximations/optimisations. Peut-être voudras-tu commencer par un algo plus usuel : le flou gaussien par convolution

Pour ce qui est de l'idée générale, il s'agit effectivement de faire la moyenne des pixels voisins. C'est une moyenne pondérée : les pixels éloignés ont un coefficient plus faible.
18/01/2011, 18h11
Gsyltc

Merci beaucoup je vais partir sur ton lien afin de mieux comprendre la problématique.

Merci pour la réponse rapide :)