Discussion :

[Xav00007]

Je ne comprends pas comment reconstruire le masque complet sur base de ce qui est stocké.

Par exemple, pour Chessboard, on a :
1 1 0
0 0 0 ?
0 1 1

J'essaie de passer cet algorithme en C, mais je ne comprends pas les accès aux valeurs des masques dans l'algo :

dx = chamfer[k][0];
dy = chamfer[k][1];
dt = chamfer[k][2];

Quelles valeurs récupère-t-on dans le cas du chessboard ?
Et que vaut ce masque ?

Merci d'avance,

[pseudocode]

Je ne comprends pas comment reconstruire le masque complet sur base de ce qui est stocké.

Par exemple, pour Chessboard, on a :
1 1 0
0 0 0 ?
0 1 1

Non. Le stockage est sous la forme {i,j,valeur} donc :

chessboard[1][0] = 1 // {1,0,1}
chessboard[1][1] = 1 // {1,1,1}

ce qui nous donne le 1/8 de masque (la partie Est / NordEst):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
  |  | 1
--+--+--
  |  | 1 
--+--+--
  |  |

par symétrie verticale + horizontale + diagonale, on obtient la totalité du masque

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 1| 1| 1
--+--+--
 1|  | 1 
--+--+--
 1| 1| 1

[Xav00007]

J'ai un peu du mal, je comprends pas la logique des indices utilisés.

[1][0] c'est quelle élément de la matrice ?
et [1][1] ?

Et [2][2] qui représente 'dt' ?
et [0][2] qui représente le 'normalizer' ?

[pseudocode]

J'ai un peu du mal, je comprends pas la logique des indices utilisés.

[1][0] c'est quelle élément de la matrice ?
et [1][1] ?

Et [2][2] qui représente 'dt' ?
et [0][2] qui représente le 'normalizer' ?

Bah je vois pas comment expliquer mieux. Exemple avec le masque chamfer5:

public final static int[][] chamfer5 = new int[][] {
new int[] {1,0,5},
new int[] {1,1,7},
new int[] {2,1,11}
};

Ce masque est composé de 3 éléments:

chamfer5[0]={1,0,5} // 1er element : position=(1,0) valeur=5
chamfer5[1]={1,1,7} // 2eme element : position=(1,1) valeur=7
chamfer5[2]={2,1,11} // 3eme element : position=(2,1) valeur=11

Ce qui nous donne cela:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
     -2 -1 00 +1 +2
    +--------------+
 +2 |  |  |  |  |  |  
    |--------------|  
 +1 |  |  |  | 7|11|  
    |--------------|  
 00 |  |  |  | 5|  | 
    |--------------|  
 -1 |  |  |  |  |  |  
    |--------------|  
 -2 |  |  |  |  |  |  
    +--------------+

[Xav00007]

Ok, maintenant je vois comment on numérote.
La plupart du temps on numérote comme ceci :

0 1 2 3

1

2

3

Si je veux implémenter en C, je peux faire ceci ? :

int chessboard[3][3];
chessboard[0][0] = 1;
chessboard[0][1] = 1;
chessboard[0][2] = 1;
chessboard[1][0] = 1;
chessboard[1][1] = 0;
chessboard[1][2] = 1;
chessboard[2][0] = 1;
chessboard[2][1] = 1;
chessboard[2][2] = 1;

Et l'utiliser comme dans ton algo ?

normalizer = chessboard[0][2];
... ?

L'autre truc, pour ce masque par exemple, normalizer est bien l'élément chessboard[0][2] = 1; dans mon implémentation ?

Et puis, quelque soit la taille du masque, normalizer c'est l'élément [0][2], dt l'élément [k][2], ... ?

Tu pourrais m'indiquer ces valeurs dans le cas de chamfer5?

Merci beaucoup

[pseudocode]

Si je veux implémenter en C, je peux faire ceci ? :

int chessboard[3][3];
chessboard[0][0] = 1;
chessboard[0][1] = 1;
chessboard[0][2] = 1;
chessboard[1][0] = 1;
chessboard[1][1] = 0;
chessboard[1][2] = 1;
chessboard[2][0] = 1;
chessboard[2][1] = 1;
chessboard[2][2] = 1;

Non. le masque "chessboard" utilise la distance de Manhattan. Donc les 4 cases Nord, Sud, Est, Ouest autour du centre sont à "1" et celles en diagonal sont à "2"

Et l'utiliser comme dans ton algo ?

normalizer = chessboard[0][2];
... ?

L'autre truc, pour ce masque par exemple, normalizer est bien l'élément chessboard[0][2] = 1; dans mon implémentation ?

Et puis, quelque soit la taille du masque, normalizer c'est l'élément [0][2], dt l'élément [k][2], ... ?

Non. Le coefficient de normalisation c'est celui qui te permet de retrouver la "vraie" distance entre le centre du masque et une case. C'est donc la valeur d'une des 4 cases autour du centre, car ces cases sont censées être a une distance de "1" du centre

Les coordonnées de ces cases dans le repere centré en 0 sont donc (-1,0) (0,1) (1,0) (0,-1).

Dans ton exemple C ca donnerait l'une des 4 cases:
chessboard[0][1], chessboard[1][0], chessboard[2][1], chessboard[1][2],

Tu pourrais m'indiquer ces valeurs dans le cas de chamfer5?

Le masque complet est indiqué au post #2. Attention, dans le masque de chamfer5 il y a des "trous" : certaines cases du masque n'ont pas de valeur, et donc ne doivent pas être utilisées.

[Xav00007]

Je vais y arriver

Dans le cas de Chamfer3 alors, on a :

4 3 4
3 0 3 ?
4 3 4

normalizer = 3 ? toujours ?

Pour les pixels N - S - O - E, on ajoute 3?
Pour les pixels NO - NE - SE - SO, on ajoute 4 ?

[pseudocode]

Dans le cas de Chamfer3 alors, on a :

4 3 4
3 0 3 ?
4 3 4

oui.

normalizer = 3 ? toujours ?

heu... oui. Le coefficient de normalisation est global au masque, donc c'est "toujours" 3 dans ce masque là. Le but c'est, au final, d'avoir une approximation de la "vraie" distance, c'est a dire la distance euclidienne = racine (X²+Y²). Idéalement, on aurait

- Les cases N, S, E, O sont à une distance de "1"
- Les cases NO, NE, SE, SO sont à une distance de "racine(2)"
etc.

Les masques sont des approximations calculées en multipliant par un entier (le coefficient de normalisation) et en gardant seulement la partie entière.

Le masque "Chamfer3" multiplie par "3" et garde la partie entière.
- N, S, E, O -> int(1*3) = 3
- NO, NE, SE, SO -> int(racine(2)*3)= int(4.24264...) = 4

Pour les pixels N - S - O - E, on ajoute 3?
Pour les pixels NO - NE - SE - SO, on ajoute 4 ?

Oui.

[Xav00007]

double gray = 255 * Math.min( 1 , Math.log(1+distmap[x][y]/50) );

D'où vient cette fonction de mise à l'échelle ?
Comment l'expliquer ?

[pseudocode]

D'où vient cette fonction de mise à l'échelle ?
Comment l'expliquer ?

Y a pas d'explication. Je trouve juste que ca fait joli.

[Xav00007]

Et ton 50, c'est ton petit doigt qui te l'a dit ou y'a une explication ?

[pseudocode]

Et ton 50, c'est ton petit doigt qui te l'a dit ou y'a une explication ?

c'est un facteur de changement d'echelle pour avoir un joli dégradé. Le but c'est d'avoir un dégradé de gris entre 0->255. Donc le facteur doit etre telle que pour la distance de chamfer max (DMAX) la formule nous donne la valeur 255.

[Xav00007]

Et cette valeur maximum, tu sais la trouver comment?
Si j'ai une image de 40 pixels sur 40, ma valeur maximale sera sqrt(2*40²) ?
Ou est-ce que cette distance dépend de la méthode utilisée?

[pseudocode]

Et cette valeur maximum, tu sais la trouver comment?
Si j'ai une image de 40 pixels sur 40, ma valeur maximale sera sqrt(2*40²) ?
Ou est-ce que cette distance dépend de la méthode utilisée?

Rappel : Cette formule de conversion ne fait pas partie du calcul de le carte des distances. Je l'ai juste utilisée pour faire un affichage joli sur la première page de la discussion.

Ceci dit. La distance max "DMAX" dépend de chaque image. Donc il faut parcourir le tableau retourné par la fonction pour la trouver. Une fois qu'on a cette valeur, il suffit de prendre le facteur tel que "formule(DMAX)=255".

255 * Math.min( 1 , Math.log(1+DMAX/FACTOR) ) = 255
=> Math.log(1+DMAX/FACTOR) = 1
=> 1+DMAX/FACTOR = exp(1)
=> FACTOR = (exp(1)-1)/DMAX

FACTOR ~= 1.718/DMAX

[galadorn]

bonjour a tous,
comme déjà mentionné dans un autre post, je recherche a implémenter l'algorithme des contours actifs à la 3D. Pour cela je dois aussi modifier ce bout de code pour la 3D.
En 2D je conçois aisément qu'un simple "aller-retour" suffit a calculer la carte des distances, mais comment s'y prendre pour travailler en 3D?
Etant donne que la distance d'un pixel doit prendre en compte les bords des coupes inférieures et supérieures, je ne peux pas me permettre d'appliquer l'algorithme 2D à toutes mes coupes pour avoir un semblant de carte des distances 3D.
Mais je ne vois vraiment pas comment m'y prendre.

Merci en tout cas pour ton précieux code !

Galadorn

[pseudocode]

En 2D je conçois aisément qu'un simple "aller-retour" suffit a calculer la carte des distances, mais comment s'y prendre pour travailler en 3D?

Idem. Il suffit d'un aller-retour sur tous les voxels:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
// forward
for (int z=0; z<=depth-1; z++)
	for (int y=0; y<=height-1; y++)
		for (int x=0; x<=width-1; x++)
 
// backward
for (int z=depth-1; z>=0; z--)
	for (int y=height-1; y>=0; y--)
		for (int x=width-1; x>=0; x--)

La différence est bien sûr qu'il faut utiliser des masques 3D. Par exemple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
public final static int[][] chamfer3D_5x5x5 = new int[][] {
	// (x,y,z,  weight)
	new int[] {1,0,0,5},
	new int[] {1,1,0,7},
	new int[] {1,1,1,9},
	new int[] {2,1,0,11},
	new int[] {2,1,1,12},
	new int[] {2,2,1,15}
};

[galadorn]

un tout grand merci !

[hbloom]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
public ChamferDistance() {
		this(ChamferDistance.chamfer3);
	}

pk c'est chamfer3 et pas les autres ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
	private void testAndSet(double[][] output, int x, int y, double newvalue) {
		if(x<0 || x>=this.width) return;
		if(y<0 || y>=this.height) return;
		double v = output[x][y];
		if (v>=0 && v<newvalue) return;
		output[x][y] = newvalue;
	}
 
 
		// forward
		for (int y=0; y<=height-1; y++) {
			for (int x=0; x<=width-1; x++) {
				double v = output[x][y];
				if (v<0) continue;
				for(int k=0;k<chamfer.length;k++) {
					int dx = chamfer[k][0];
					int dy = chamfer[k][1];
					int dt = chamfer[k][2];
 
					testAndSet(output, x+dx, y+dy, v+dt);
					if (dy!=0) testAndSet(output, x-dx, y+dy, v+dt);
					if (dx!=dy) {
						testAndSet(output, x+dy, y+dx, v+dt);
						if (dy!=0) testAndSet(output, x-dy, y+dx, v+dt);
					}
				}
			}
		}
 
		// backward
		for (int y=height-1; y>=0; y--) {
			for (int x=width-1; x>=0; x--) {
				double v = output[x][y];
				if (v<0) continue;
				for(int k=0;k<chamfer.length;k++) {
					int dx = chamfer[k][0];
					int dy = chamfer[k][1];
					int dt = chamfer[k][2];
 
					testAndSet(output, x-dx, y-dy, v+dt);
					if (dy!=0) testAndSet(output, x+dx, y-dy, v+dt);
					if (dx!=dy) {
						testAndSet(output, x-dy, y-dx, v+dt);
						if (dy!=0) testAndSet(output, x+dy, y-dx, v+dt);
					}
				}
			}
		}
 
		// normalize
		for (int y=0; y<height; y++)
			for (int x=0; x<width; x++)
				output[x][y] = output[x][y]/normalizer;
 
		return output;
	}
}

Pourriez vous s'il vous plait m'expliquer la methode test and set et comment elle fonctionne pour remplir les output ?

[pseudocode]

pk c'est chamfer3 et pas les autres ?

Il s'agit du constructeur par défaut de la classe Java. Si aucun paramètre de masque n'est spécifié à l'appel du constructeur, c'est le masque chamfer3 qui sera utilisé.

Pourriez vous s'il vous plait m'expliquer la methode test and set et comment elle fonctionne pour remplir les output ?

testAndSet() remplace la valeur "output[x][y]" par "newvalue", si cette dernière est inférieure à la valeur actuelle.

Le test "if (v>=0 ...)" vérifie que la valeur actuelle est valide avant de faire la comparaison (car au départ le tableau output[][] est initialisé à -1).

[hbloom]

Merci pour votre réponse !

J'ai d'autres questions s'il vous plait, quand par exemple on parcoure l'image et on tombe sur output[5][6] = 0 ( donc sur un point de l'objet ) on a donc output [5+4][6+3]= 0+4 ? pour le masque chamfer 3

et pk les conditions (dy!=0 et dx!=dy) ?

Merci énormément ^^