[java] Carte des Distances (Chamfer)

[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]

Envoyé par 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

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 :

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

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

Code :

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]

Envoyé par 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' ?

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 :

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]

Envoyé par Xav00007

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]

Envoyé par Xav00007

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]

Envoyé par pseudocode

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]

Envoyé par Xav00007

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]

Envoyé par Xav00007

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]

Envoyé par 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?

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]

Envoyé par galadorn

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 :

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 :

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 !