[Image] Inpainting par Continuation des Isophotes

[pseudocode]

Voici la version finale de la routine d'inpainting utilisée dans le filtre UnNoise.

En esperant que, cette fois, le portage compilera sans erreur dans la MillieLib !

Code java :

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
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
 
import ij.IJ;
import ij.ImagePlus;
import ij.gui.GenericDialog;
import ij.plugin.filter.PlugInFilter;
import ij.process.ByteProcessor;
import ij.process.ImageProcessor;
 
import java.util.ArrayList;
import java.util.List;
 
/**
 *  InPaint by isophote continuation 
 * 
 * @author Xavier Philippeau
 *
 */
public class Inpaint_ implements PlugInFilter {
 
	// Temporary workspace
	private class Channel {
		private int[][] data;
		public Channel(int w,int h) {
			data = new int[h][w];
		}
		public int getValue(int x, int y) {
			return data[y][x];
		}
		public void setValue(int x, int y, int v) {
			data[y][x]=v;
		}
	}
 
	// neighbours offsets (for border spreading)
	private int[] dx4 = new int[] {-1, 0, 1, 0};
	private int[] dy4 = new int[] { 0,-1, 0, 1};
 
    // neighbours offsets (for sampling)
	private int[] dxs = null;
	private int[] dys = null;
 
	// distance Map to the unmasked part of the image
	private Channel distmap = null;
 
	// Output image
	private Channel output = null;
	private int width = 0;
	private int height = 0;
 
	// mask color
	private int[] maskcolor = new int[3];
 
	// isophote preservation factor
	private int preservation = 0;
 
	// About...
	private void showAbout() {
		IJ.showMessage("InPaint...","InPaint Filter by Pseudocode");
	}
 
	public int setup(String arg, ImagePlus imp) {
 
		// about...
		if (arg.equals("about")) {
			showAbout(); 
			return DONE;
		}
 
		// else...
		if (imp==null) return DONE;
 
		// Configuration dialog.
		GenericDialog gd = new GenericDialog("Parameters");
		gd.addNumericField("Sample region size",24,0);
		gd.addStringField("Mask color (R,G,B)","255,0,0");
		gd.addNumericField("Isophote preservation factor",4,0);
 
		int nmbsample = 0;
		String hexamask ="";
		gd.showDialog();
		while(true) {
			if ( gd.wasCanceled() )	return DONE;
 
			nmbsample = (int) gd.getNextNumber();
			hexamask = gd.getNextString();
			this.preservation = (int) gd.getNextNumber();
 
			if (nmbsample<=0) continue;
			if (this.preservation<0) continue;
			if (hexamask.split(",").length!=3) continue;
 
			break;
		}
		gd.dispose();
 
		// Get Mask Color
		String[] split = hexamask.split(",");
		this.maskcolor[0] = Integer.parseInt(split[0]);
		this.maskcolor[1] = Integer.parseInt(split[1]);
		this.maskcolor[2] = Integer.parseInt(split[2]);
 
		// Initialize dxs[] and dys[] tables 
		initSample(nmbsample);
 
		return PlugInFilter.DOES_RGB;
	}
 
	private void initSample(int nmbsample) {
		// Initialize neighbours offsets for sampling 
		dxs = new int[nmbsample];
		dys = new int[nmbsample];
 
		// **** build a spiral curve ****  
 
		// directions: Left=(-1,0) Up=(0,-1) Right=(1,0) Down=(0,1)
		int[] dx = new int[] {-1, 0,1,0};
		int[] dy = new int[] { 0,-1,0,1};
		int dirIndex=0;
		int distance=0;
		int stepToDo=1;
		int x=0, y=0;
		while (true) {
			// move two times with the same StepCount
			for (int i = 0; i < 2; i++) {
				// move
				for (int j = 0; j < stepToDo; j++) {
					x += dx[dirIndex];
					y += dy[dirIndex];
					dxs[distance] = x;
					dys[distance] = y;
					distance++;
					if (distance >= nmbsample) return;
				}
				// turn right
				dirIndex = (dirIndex + 1) % 4;
			}
			// increment StepCount
			stepToDo++;
		}
	}
 
	public void run(ImageProcessor ip) {
 
		// ImageProcessor -> GRAYLEVEL IMAGE
		ByteProcessor input = new ByteProcessor(ip.getWidth(),ip.getHeight());
 
		// ImageProcessor -> BINARY MASK
		ByteProcessor mask = new ByteProcessor(ip.getWidth(),ip.getHeight());
 
		for (int y = 0; y < ip.getHeight(); y++) {
			for (int x = 0; x < ip.getWidth(); x++) {
				int[] rgb = ip.getPixel(x,y,null);
 
				int gray = (rgb[0]+rgb[1]+rgb[2])/3;
				input.set(x,y,gray);
 
				if (rgb[0]==this.maskcolor[0] && rgb[1]==this.maskcolor[1] && rgb[2]==this.maskcolor[2])
					mask.set(x,y,255);
				else
					mask.set(x,y,0);
			}
		}
 
		// Inpaint filter
		inpaintloop(input, mask);
 
		// ByteProcessor -> ImageProcessor conversion
		ImageProcessor result = new ByteProcessor(ip.getWidth(),ip.getHeight());
		for (int y = 0; y < ip.getHeight(); y++) {
			for (int x = 0; x < ip.getWidth(); x++) {
				result.set(x,y,this.output.getValue(x,y));
			}
		}
		ImagePlus newImg = new ImagePlus("Inpaint Filter Result", result);
		newImg.show();
 
	}
 
	// ---------------------------------------------------------------------------------
 
 
	// Compute the initial borderline (unmasked pixels close to the mask)
	private List<int[]> computeBorderline(ByteProcessor mask) {
 
		List<int[]> borderline = new ArrayList<int[]>();
 
		for (int y=0; y<this.height; y++) {
			for (int x=0; x<this.width; x++) {
				// for each pixel NOT masked
				int v = mask.get(x,y);
				if (v>127) continue;
 
				// if a neighboor is masked
				// => put the pixel in the borderline list
				for (int k=0; k<4; k++) {
					int xk = x+dx4[k];
					int yk = y+dy4[k];
					if (xk<0 || xk>=this.width) continue;
					if (yk<0 || yk>=this.height) continue;
					int vk = mask.get(xk,yk);
					if (vk>127) {
						borderline.add(new int[] {x,y});
						break;
					}
				}
			}
		}
		return borderline;
	}
 
	// iteratively inpaint the image
	private void inpaintloop(ByteProcessor input, ByteProcessor mask) {
		this.width = input.getWidth();
		this.height = input.getHeight();
 
		// initialize output image
		this.output = new Channel(this.width,this.height);
		for (int y=0; y<this.height; y++) {
			for (int x=0; x<this.width; x++) {
				if (mask.get(x, y)<127)
					this.output.setValue(x, y, input.get(x, y)); // known value
				else
					this.output.setValue(x, y, -1); // unknown value (masked)
			}
		}
 
		// initialize the distance map
		this.distmap = new Channel(this.width,this.height);
		for (int y=0; y<this.height; y++)
			for (int x=0; x<this.width; x++)
				if (mask.get(x, y)<127)
					this.distmap.setValue(x, y, 0); // outside the mask -> distance = 0
				else
					this.distmap.setValue(x, y, Integer.MAX_VALUE); // inside the mask -> distance unknown
 
		// outer borderline 
		List<int[]> borderline = computeBorderline(mask);
 
		// iteratively reduce the borderline
		while(!borderline.isEmpty()) {
			borderline = propagateBorderline(borderline);
		}
	}
 
	// inpaint pixels close to the borderline 
	private List<int[]> propagateBorderline(List<int[]> boderline) {
 
		List<int[]> newBorderline = new ArrayList<int[]>();
 
		// for each pixel in the bordeline
		for (int[] pixel : boderline) {
			int x=pixel[0];
			int y=pixel[1];
 
			// distance from the image
			int dist = this.distmap.getValue(x, y);
 
			// explore neighbours, search for uncomputed pixels
			for (int k=0; k<4; k++) {
				int xk = x+dx4[k];
				int yk = y+dy4[k];
				if (xk<0 || xk>=this.width) continue;
				if (yk<0 || yk>=this.height) continue;
 
				int vout = this.output.getValue(xk,yk);
				if (vout>=0) continue; // pixel value is already known.
 
				// compute distance to image 
				this.distmap.setValue(xk, yk, dist+1);
 
				// inpaint this pixel
				int v = inpaint(xk, yk);
				if (v<0) { 
					// should not happen.
					System.err.println("inpaint for "+xk+","+yk+" returns "+v);
					this.output.setValue(xk, yk, v);
					continue; 
				}
				this.output.setValue(xk, yk, v);
 
				// add this pixel to the new borderline
				newBorderline.add( new int[]{xk,yk} );
			}
		}
 
		return newBorderline;
	}
 
	// inpaint one pixel
	private int inpaint(int x, int y) {
 
		double wsum = 0;
		double vinpaint = 0;
 
		int dist = this.distmap.getValue(x, y);
 
		// sampling pixels in the region
		List<int[]> region = new ArrayList<int[]>(); 
		for (int k=0; k<dxs.length; k++) {
			int xk = x+dxs[k];
			int yk = y+dys[k];
			if (xk<0 ||xk>=this.width) continue;
			if (yk<0 ||yk>=this.height) continue;
 
			// take only pixels computed in previous loops
			int distk = this.distmap.getValue(xk, yk);
			if (distk>=dist) continue;
 
			region.add( new int[]{xk,yk} );
		}
 
		// mean isophote vector of the region
		double isox = 0, isoy = 0;
		int count=0;
		for (int[] pixel: region) {
			int xk = pixel[0];
			int yk = pixel[1];
 
			// isophote direction = normal to the gradient 
			double[] g = gradient(xk,yk,dist);
			if (g!=null){
				isox += -g[1] * g[2];
				isoy += g[0] * g[2];
				count++;
			}
		}
		if (count>0) {
			isox/=count; isoy/=count;  
		}
		double isolength = Math.sqrt( isox*isox + isoy*isoy );
 
		// contribution of each pixels in the region
		for (int[] pixel: region) {
			int xk = pixel[0];
			int yk = pixel[1];
 
			// propagation vector
			int px = x-xk;
			int py = y-yk;
			double plength = Math.sqrt( px*px + py*py );
 
			// Weight of the propagation:
 
			// 1. isophote continuation: cos(isophote,propagation) = normalized dot product ( isophote , propagation ) 
			double wisophote = 0;
			if (isolength>0) {
				double cosangle = Math.abs(isox*px+isoy*py) / (isolength*plength);
				cosangle = Math.min(cosangle, 1.0);
				/*
				// linear weight version:
				double angle = Math.acos(cosangle);
				double alpha = 1-(angle/Math.PI);
				wisophote = Math.pow(alpha,this.preservation);
				*/
				wisophote = Math.pow(cosangle,this.preservation);
			}
 
			// 2. spread direction: 
			// gradient length = O -> omnidirectionnal
			// gradient length = maxlength -> unidirectionnal
			double unidir = Math.min(isolength/255,1);
 
			// 3. distance: distance to inpaint pixel
			double wdist = 1.0 / (1.0 + plength*plength);
 
			// 4. probability: distance to image (unmasked pixel)
			int distk = this.distmap.getValue(xk, yk);
			double wproba = 1.0 / (1.0 + distk*distk);
 
			// global weight
			double w = wdist * wproba * ( unidir*wisophote + (1-unidir)*1 );
 
			vinpaint += w*this.output.getValue(xk,yk);
			wsum+=w;
		}
		if (wsum<=0) return -1;
		vinpaint/=wsum;
 
		if (vinpaint<0) vinpaint = 0;
		if (vinpaint>255) vinpaint = 255;
		return (int)vinpaint;
	}
 
	// 8 neightbours gradient
	private double[] gradient(int x, int y, int dist) {
		// Coordinates of 8 neighbours
		int px = x - 1;  // previous x
		int nx = x + 1;  // next x
		int py = y - 1;  // previous y
		int ny = y + 1;  // next y
 
		// limit to image dimension
		if (px < 0)	return null;
		if (nx >= this.width) return null;
		if (py < 0)	return null;
		if (ny >= this.height) return null;
 
		// availability of the 8 neighbours
		// (must be computed in previous loops) 
		if (this.distmap.getValue(px,py)>=dist) return null;
		if (this.distmap.getValue( x,py)>=dist) return null;
		if (this.distmap.getValue(nx,py)>=dist) return null;
		if (this.distmap.getValue(px, y)>=dist) return null;
		if (this.distmap.getValue(nx, y)>=dist) return null;
		if (this.distmap.getValue(px,ny)>=dist) return null;
		if (this.distmap.getValue( x,ny)>=dist) return null;
		if (this.distmap.getValue(nx,ny)>=dist) return null;
 
		// Intensity of the 8 neighbours
		int Ipp = this.output.getValue(px,py);
		int Icp = this.output.getValue( x,py);
		int Inp = this.output.getValue(nx,py);
		int Ipc = this.output.getValue(px, y);
		int Inc = this.output.getValue(nx, y);
		int Ipn = this.output.getValue(px,ny);
		int Icn = this.output.getValue( x,ny);
		int Inn = this.output.getValue(nx,ny);
 
		// Local gradient
		double r2 = 2*Math.sqrt(2);
		double gradx = (Inc-Ipc)/2.0 + (Inn-Ipp)/r2 + (Inp-Ipn)/r2;
		double grady = (Icn-Icp)/2.0 + (Inn-Ipp)/r2 + (Ipn-Inp)/r2;
		double norme = Math.sqrt(gradx*gradx+grady*grady);
 
		return new double[] { gradx, grady, norme };  
	}
 
}

Un petit mot sur le facteur de préservation d'isophote. Il permet de contrôler la continuité des lignes d'isophotes dans la region a restaurer:

[progfou]

Il serait, je pense, intéressant de mettre en référence le(s) papier(s) utilisé pour l'algorithme ?

Il existe d'autres méthodes, tenant compte par exemple des textures, est-il envisageable de les implémenter ?

[pseudocode]

Envoyé par progfou

Il serait, je pense, intéressant de mettre en référence le(s) papier(s) utilisé pour l'algorithme ?

Il existe d'autres méthodes, tenant compte par exemple des textures, est-il envisageable de les implémenter ?

A vrai dire, l'algorithme utilisé est assez standard:
1. On calcule la courbe "frontiere" entre l'image et le masque
2. On calcule la valeur des pixels masqués qui sont adjacents de la frontiere.
3. Ces pixels calculés deviennent la nouvelle frontiere => on retourne a l'etape 1

Quand a la formule d'inpaint, elle est faite maison en s'inspirant de plusieurs méthodes.

Mais bon, si on ne devait retenir qu'un papier ce serait celui la:

An Image Inpainting Technique Based onthe Fast Marching Method

Quand a l'inpaint par synthese de texture, c'est autrement plus complexe. On peut garder la partie algorithmie, sauf que l'on avance par "bande" et non plus par "ligne" de pixels. Par contre la formule n'a rien a voir...

S'il y a des gens interessé, j'ai trouvé un bon papier:

Image Repairing: Robust Image Synthesis by Adaptive ND Tensor Voting

[PRomu@ld]

C'est plutôt intéressant comme traitement.

Est-ce que tu as plus d'information sur les cas difficiles à traiter ? (des cas qui font que la restauration n'est pas possible ou alors très difficilement)

Au passage, le deuxième lien est mort pour moi.

[pseudocode]

Envoyé par PRomu@ld

C'est plutôt intéressant comme traitement.

Est-ce que tu as plus d'information sur les cas difficiles à traiter ? (des cas qui font que la restauration n'est pas possible ou alors très difficilement)

Le principe de continuation des isophotes marche "bien" dans le cas ou il y a un et un seul isophote au voisinage du pixel a restaurer. Donc les cas difficiles sont:

- lorsqu'il y a zero isophote, c'est a dire dans une zone avec un gradient tres faible (quasi uniforme)

- lorsqu'il y a trop d'isophotes, c'est a dire au croisements de 2 "objets" blanc/noir

A noter que ma formule est assez simpliste, et gere tres mal ces 2 cas. La formule utilisé dans le 1er lien PDF est bien meilleure. Je vais l'implementer, pour voir...

Au passage, le deuxième lien est mort pour moi.

Oups. Petite erreur de copier/coller... c'est réparé.

[PRomu@ld]

A noter que ma formule est assez simpliste,

Les résultats sur lena sont relativement acceptable (en tout cas de mon point de vue de novice).

Oups. Petite erreur de copier/coller... c'est réparé.

Sympa le papier, les résultats sont bluffants ! Il faudra que je regarde ça de plus près, tout ceci me parait intéressant !

[souviron34]

la seule chose que je trouve étrange, c'est la dernière image du 2ième papier (avec le microphone)...

Il y a de la "création" .. un peu... étrange... Comment se fait-il que derrière le bout du micro ils trouvent des trous ???

Je veux bien que ce soit l'algo, mais ça ça me semble pas être scientifiquement correct, puisqu'il n'y a pas de continuité d'une "feature"....

[pseudocode]

Envoyé par PRomu@ld

Les résultats sur lena sont relativement acceptable (en tout cas de mon point de vue de novice).

C'est sur que ca marche pas mal pour les "petites" surfaces a restaurer.

Des que la surface a restaurer devient trop grande, l'approche pixel/isophote est trop simpliste. Il faut passer au tenseur/texture...


Restauration d'une grande surface avec l'approche pixel/isophote

[PRomu@ld]

Comment se fait-il que derrière le bout du micro ils trouvent des trous ???

Ce ne sont pas des trous, mais des pierres, j'ai pas lu le papier mais a mon avis, il s'agit du motif qui est à droite du micro (tu vois déjà les deux pierres).

Des que la surface a restaurer devient trop grande, l'approche pixel/isophote est trop simpliste.

En même temps, vu la portion importante manquante de ton image (1/9 à vue de nez) ça parait normal.

A mon avis, ton algo, devrait être très bien adapté à la restauration automatique de vieilles photos.

Quand j'aurai un peu de temps il faudra que je code ça et que je teste sur quelques vieilles photos.

[pseudocode]

Envoyé par PRomu@ld

A mon avis, ton algo, devrait être très bien adapté à la restauration automatique de vieilles photos.

Quand j'aurai un peu de temps il faudra que je code ça et que je teste sur quelques vieilles photos.

C'etait un peu le principe du filtre UnNoise... Le probleme c'est de determiner le masque, ni trop petit, ni trop grand.

[PRomu@ld]

A vrai dire, ça serait une combinaison des deux, puisque sur les vieilles photos, tu as deux choses : le craquèlement (dus à la températures et/ou aux manipulations) et une apparition de points (dus la plupart du temps à la poussière qui fini par se coller sur la photo).

Pour le craquèlement, je pensais à l'algo que tu nous présentes aujourd'hui.

[progfou]

C'est effectivement l'utilisation de l'inpainting par continuation d'isophotes la plus courante. La seconde méthode, utilisant les textures, permet des effets spéciaux plus complexes, car elle reconstruit des textures !

Un papier plutôt intéressant :
http://www.google.fr/url?sa=t&ct=res...dFRfUKL-iv3I6w

[pseudocode]

Mise a jour du P.O: Code pour PlugIn ImageJ

[SpaGrave]

Dans la fonction inpaintloop, à quoi correspond "Integer.MAX_VALUE" ?

[pseudocode]

Envoyé par SpaGrave

Dans la fonction inpaintloop, à quoi correspond "Integer.MAX_VALUE" ?

En java, c'est la plus grande valeur positive qui rentre dans un "int".

L'equivalent en C je crois que c'est INT_MAX (defini dans limits.h)

[grob1212]

Bonjour à tous,

je travaille actuellement sur un problème similaire à l'inpainting : j'ai une image préalablement segmentée dont je désire supprimer certaines zones (de petites à moyennes), et si possible, en préservant les structures géométriques.

J'ai lu deux ou trois articles sur l'inpainting et je me demande si c'est applicable à mon cas : pour l'inpainting, on fait de l'interpolation de couleur pendant la propagation. Pour mon traitement, je veux juste que les pixels à remplir prennent forcément une couleur de leurs voisins, sans moyenner.

De plus, je ne suis pas un pro de cette technique et je me pose une question : comment propage-t-on le gradient à l'intérieur de la zone à remplir ? Si on calcule le gradient à partir d'une fenêtre 3x3 autour des pixels de contours, est-ce suffisant pour en avoir une bonne estimation ? En fait, j'aimerais des explications sur cette étape (ma difficulté à exprimer ma question relève très certainement du fait que je n'ai rien compris )

Je ne sais pas si j'ai été très clair, mais merci à vous pour m'avoir lu et répondu !

[pseudocode]

Envoyé par grob1212

De plus, je ne suis pas un pro de cette technique et je me pose une question : comment propage-t-on le gradient à l'intérieur de la zone à remplir ?

Dans mon algo, j'ai choisi la méthode "pelure d'oignon". Ça consiste à remplir uniquement les pixels de la ligne du contour image/masque à chaque itération:

1. On prend un pixel P de la ligne de contour (dans le masque)
2. on fait un sampling dans le voisinage de P
3. on calcule le vecteur gradient moyen G
4. on calcule le vecteur porteur de la ligne d'isophote (orthogonal au gradient)
5. on fait un ème sampling dans le voisinage de P
5a. Pour chaque pixel S du sampling, on calcule l'angle entre le vecteur SP et le vecteur porteur de la ligne d'isophote
5b. si l'angle est nul => S et P sont sur la ligne d'isophote => S participe à la nouvelle valeur de P (= moyenne pondérée en fonction de l'angle)
6. retour au 1 (pour chaque pixel de la ligne de contour).

Si on calcule le gradient à partir d'une fenêtre 3x3 autour des pixels de contours, est-ce suffisant pour en avoir une bonne estimation ?

heu... non. Le pixel central étant dans le masque et la moitié de ses voisins également, ça ne fait pas assez de pixels connus (de l'image) pour estimer le gradient.

[ToTo13]

Bonjour,

si je puis me permettre, voilà une explication et une démonstration en français de ce que vient de nous proposer PseudoCode.

[benDelphic]

salut
s 'il vous plait on peut avoir le code dans un autre langage comme ça on touche une grande part de programmeurs ?

[ToTo13]

Bonjour,

Envoyé par benDelphic

salut
s 'il vous plait on peut avoir le code dans un autre langage comme ça on touche une grande part de programmeurs ?

à toi l'honneur de nous faire une traduction en C++