[java] Carte des Distances (Chamfer)

pseudocode · 16/01/2008, 19h10

Une petite classe java pour calculer la carte des distances par la méthode des masques de Chamfer.

La methode compute() prend en entré un tableau binaire et retourne un tableau de flotant. Chaque case [x][y] du tableau contient la distance entre le pixel [x][y] et le "1" le plus proche dans l'image binaire.

A gauche: l'image binaire en entrée
A droite: la carte des distances (l'intensité représente la distance)

Code java :

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
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
 
/**
 * Chamfer distance
 * 
 * @author Code by Xavier Philippeau <br> Kernels by Verwer, Borgefors and Thiel 
 */
public class ChamferDistance  {
 
	public final static int[][] cheessboard = new int[][] {
		new int[] {1,0,1},
		new int[] {1,1,1}
	};
 
	public final static int[][] chamfer3 = new int[][] {
		new int[] {1,0,3},
		new int[] {1,1,4}
	};
 
	public final static int[][] chamfer5 = new int[][] {
		new int[] {1,0,5},
		new int[] {1,1,7},
		new int[] {2,1,11}
	};
 
	public final static int[][] chamfer7 = new int[][] {
		new int[] {1,0,14},
		new int[] {1,1,20},
		new int[] {2,1,31},
		new int[] {3,1,44}
	};
 
	public final static int[][] chamfer13 = new int[][] {
		new int[] { 1,  0,  68},
		new int[] { 1,  1,  96},
		new int[] { 2,  1, 152},
		new int[] { 3,  1, 215},
		new int[] { 3,  2, 245},
		new int[] { 4,  1, 280},
		new int[] { 4,  3, 340},
		new int[] { 5,  1, 346},
		new int[] { 6,  1, 413}
	};
 
	private int[][] chamfer = null; 
	private int normalizer = 0; 
 
	private int width=0,height=0;
 
	public ChamferDistance() {
		this(ChamferDistance.chamfer3);
	}
 
	public ChamferDistance(int[][] chamfermask) {
		this.chamfer = chamfermask;
		this.normalizer = this.chamfer[0][2];
	}
 
	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;
	}
 
	public double[][] compute(boolean[][] input, int width, int height) {
 
		this.width = width;
		this.height = height;
		double[][] output = new double[width][height]; 
 
		// initialize distance
		for (int y=0; y<height; y++)
			for (int x=0; x<width; x++)
				if (  input[x][y] )
					output[x][y]=0; // inside the object -> distance=0
				else
					output[x][y]=-1; // outside the object -> to be computed
 
		// 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;
	}
}

exemple d'utilisation:

Code java :

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

1
2
 
double[][] distancemap = new ChamferDistance(ChamferDistance.chamfer5).compute(binaryarray, 300, 200);

pseudocode · 02/04/2008, 18h43

Quelques mots d'explications sur cet algo.

Le principe du calcul de la carte des distances c'est de partir des points du contour de l'objet (distance=0) et de calculer la distance des voisins.

si (x,y) est un point du contour de l'objet, alors on a d(x,y)=0, et pour les 9 voisins on a:

d(x+1,y) = d(x,y)+1 = 1
d(x+1,y+1) = d(x,y)+racine(2) = racine(2)
d(x,y+1) = d(x,y)+1 = 1
...
d(x-1,y) = d(x,y)+racine(2) = racine(2)
d(x-1,y-1) = d(x,y)+1 = 1

Ensuite on calcule les voisins des voisins et ainsi de suite. Si on tombe sur un pixel déja calculé, on conserve la distance la plus petite.

On a besoin de faire seulement 2 passes sur l'image (forward, backward) pour avoir la totalité de la carte.

L'utilisation des masques de Chamfer permet d'accélérer les calculs:

comme les calculs impliquant les réels (racine(2)) sont couteux, on préfere utiliser seulement des distances entières (en multipliant par un facteur), et en redivisant les distances à la fin.

Pour affiner les calculs, on ne calcule pas les voisins immédiats d'un pixel, mais les voisins qui minimise l'erreur liée a l'approximation entiere.

Ca nous donne les masques de Chamfer, par exemple pour un voisinage 5x5:

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
    +--------------+   +-------------------+    +-------------------+
    |  |11|  |11|  |   |   |2.2|   |2.2|   |	|   |V¯5|   |V¯5|   |
    |--------------|   |-------------------|	|-------------------|
    |11| 7| 5| 7|11|   |2.2|1.4| 1 |1.4|2.2|   	|V¯5|V¯2| 1 |V¯2|V¯5|
1   |--------------|   |-------------------|   	|-------------------|
- x |  | 5| 0| 5|  | = |   | 1 | 0 | 1 |   | ~= |   | 1 | 0 | 1 |   |
5   |--------------|   |-------------------|	|-------------------|
    |11| 7| 5| 7|11|   |2.2|1.4| 1 |1.4|2.2|	|V¯5|V¯2| 1 |V¯2|V¯5|
    |--------------|   |-------------------|	|-------------------|
    |  |11|  |11|  |   |   |2.2|   |2.2|   |	|   |V¯5|   |V¯5|   |
    +--------------+   +-------------------+	+-------------------+

      chamfer 5x5           chamfer 5x5            valeurs idéales
       (entier)              (décimal)

Dans ce masque, on calcule 16 voisins pour chaque pixel.

b_reda31 · 03/04/2008, 02h11

Citation:

Envoyé par pseudocode

Quelques mots d'explications sur cet algo.

Merci,j'en avais besoin

batoub · 03/04/2008, 08h39

Bonjour tout le monde,

Merci pour ces explications, ca aide énormément!

Cependant j'ai une petite question (dsl :/).
Tu dis qu'il ne faut que deux passes ?

- une forward : tu prend chaque pixel et tu applique le masque des distances (seulement aux pixels du contour alors ?)

- une backward : tu prend chaque pixel du contour + les pixels qui ont déja une distance ( les voisins directs du contour en quelque sorte ?)

En fait je pense que je viens de répondre tout seul à ma question, il ne faut pas prendre que le contour lors de la première passe mais aussi les points que tu viens juste de changer c'est ca ?

Merci pour ces supers explications !!

pseudocode · 03/04/2008, 09h33

Citation:

Envoyé par batoub

En fait je pense que je viens de répondre tout seul à ma question, il ne faut pas prendre que le contour lors de la première passe mais aussi les points que tu viens juste de changer c'est ca ?

oui, c'est exactement ça !

batoub · 03/04/2008, 10h24

Héhé super

C'est pas bon d'essayer de comprendre un algo le matin à 8h :/ Fallait le temps que le cerveau se mette en marche !

Bon je vais essayer de coder ca, et je vous donne le résultat a la fin

Merci beaucoup !!!

b_reda31 · 11/08/2008, 04h04

Bonjour,
J'aurai besoin de quelques précisions concernant la procédure Compute :
Cette méthode qui consiste à faire un passage directe puis un passage inverse afin de parcourir tous les pixels,a t elle un nom ?

Ma deuxième question est encore plus ridicule

Cela concerne l'origine du mot "Chamfer" pour les masques.En traduisant ce mot en français j'obtient Chanfrein.Ensuite en cherchant sur Google :

Citation:

Chanfrein
Petite surface conique, petite surface inclinée de faible dimension, supprimant une arête vive.

Me suis je perdu dans le sens de ce mot! car je ne comprend vraiment pas le rapport avec les masques

pseudocode · 11/08/2008, 10h57

Citation:

Envoyé par b_reda31

Cette méthode qui consiste à faire un passage directe puis un passage inverse afin de parcourir tous les pixels,a t elle un nom ?

heu... je n'en connais pas.

Citation:

Ma deuxième question est encore plus ridicule

Cela concerne l'origine du mot "Chamfer" pour les masques.En traduisant ce mot en français j'obtient Chanfrein.

Chanfrein (Francais) = Chamfer (Anglais).

Le mot "chanfrein" désigne effectivement la petite surface qu'on obtient en "cassant" une arête vive (ah... souvenirs du bac E).

Pourquoi l'utiliser ici ? Et bien, c'est lié à la figure obtenue en reliant les points a une distance de "1" du centre. Dans un espace continu, cette figure est un cercle de rayon 1(

). Dans un espace discret, on obtient un polygone régulier convexe, le nombre de faces dépendant de la mesure utilisée. Plus on augmente la précision de la mesure, plus le polygone a de faces: carré -> héxagone -> octogone -> ... Ce qui revient a successivement "casser" les arête du polygone, pour converger vers un cercle.

sufetul · 10/04/2009, 00h25

salut pour tous, je suis debutant , je cherche une definition exacte de la carte de distance(surtout par rapport à quoi est calcule la distance d'un pixel)

et les etapes de creation ( en java) .

pseudocode · 10/04/2009, 09h39

Citation:

Envoyé par sufetul

salut pour tous, je suis debutant , je cherche une definition exacte de la carte de distance(surtout par rapport à quoi est calcule la distance d'un pixel)

On calcule la distance d'un pixel par rapport a d'autres pixels.

On marque certains pixels comme étant des références (en mettant leur distance a 0) et l'algo calcule pour tous les pixel la distance la plus courte jusqu'a ces pixels de références.

Citation:

et les etapes de creation ( en java) .

Bah, j'ai donné le code dans le 1er post.

Saber2009 · 10/04/2009, 11h11

Citation:

Envoyé par pseudocode

On calcule la distance d'un pixel par rapport a d'autres pixels.

On marque certains pixels comme étant des références (en mettant leur distance a 0) et l'algo calcule pour tous les pixel la distance la plus courte jusqu'a ces pixels de références.

mais je n'arrive pas à comprendre le role du ( boolean input[][] )

pseudocode · 10/04/2009, 11h39

Citation:

Envoyé par Saber2009

mais je n'arrive pas à comprendre le role du ( boolean input[][] )

c'est le tableau utilisé pour "marquer" les pixels de référence.

Si tu veux que le pixel (a,b) de ton image soit un pixel de référence distance=0), alors tu mets à 'true" la valeur du tableau: input[a][b]=true;

Saber2009 · 10/04/2009, 12h19

Citation:

Envoyé par pseudocode

c'est le tableau utilisé pour "marquer" les pixels de référence.

Si tu veux que le pixel (a,b) de ton image soit un pixel de référence distance=0), alors tu mets à 'true" la valeur du tableau: input[a][b]=true;

Merci pseudocode

Esooo · 16/04/2009, 13h08

Merci pour le code

Juste une question: comment on fait après pour convertir le double[][] en image?

J'ai essayé de créer un byte[] et ensuite créer un bufferedImage comme ca mais j'ai l'impression que ca deforme un peu l'image :s

pseudocode · 16/04/2009, 14h32

Citation:

Envoyé par Esooo

Merci pour le code

Juste une question: comment on fait après pour convertir le double[][] en image?

J'ai essayé de créer un byte[] et ensuite créer un bufferedImage comme ca mais j'ai l'impression que ca deforme un peu l'image :s

Ca déforme forcément. La distance peut aller de zéro à l'infini alors que les niveaux de gris vont généralement de 0 a 255. Pour l'image d'exemple j'ai utilisé une echelle Log:

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

Esooo · 16/04/2009, 14h53

merci

Le seul problème est que maintenant, là ou la distance vaut 0, j'ai un point blanc.
Regarde l'image:

pseudocode · 16/04/2009, 16h32

Citation:

Envoyé par Esooo

merci

Le seul problème est que maintenant, là ou la distance vaut 0, j'ai un point blanc.
Regarde l'image:

ca ne devrait pas. Si distmap[x][y]=0, alors

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

Esooo · 16/04/2009, 17h34

Oui c'est ce que je me suis dit aussi

Je pense que le problème est la conversion de données...j'ai un int[] et je cherche à obtenir une image, pour cela je fais

Code :

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

1
2
3
4
5
6
7
8
9
MemoryImageSource memoryimagesource =
			new MemoryImageSource(
				width,
				height,
				ColorModel.getRGBdefault(),
				distmap,
				0,
				width);
		return Toolkit.getDefaultToolkit().createImage(memoryimagesource);

mais ca me rend une image toute noire

Xav00007 · 23/05/2009, 08h58

Bonjour,

Que représente et à quoi servent le matrices : chessboard, chamfer3,chamfer5, ...

Je suppose qu'il s'agit des masques, mais comment ceux-ci fonctionnent-ils?

Un tout grand merci d'avance!

pseudocode · 23/05/2009, 13h05

Citation:

Envoyé par Xav00007

Que représente et à quoi servent le matrices : chessboard, chamfer3,chamfer5, ...

Je suppose qu'il s'agit des masques, mais comment ceux-ci fonctionnent-ils?

J'ai expliqué le principe de l'algo au post #2.

Les masques sont stockés sous la forme {i, j, valeur}, où i,j sont les coordonnées de la case du masque (centré en 0,0). Le masque est complètement symétrique donc on ne stocke pas les cases {i,-j} {-i,j} {-i,-j}. La première case stockée est toujours {1,0}, cette case nous donne donc le "facteur" de multiplication utilisé pour le masque.

Pour ce qui est du "comment" on calcule les valeurs d'un masque, je vous conseille une petite recherche internet avec les mot clés: chamfer coefficient Farey triangulation.

03/04/2008, 08h39	#4
batoub Invité régulier Inscription : avril 2008 Messages : 6 Détails du profil Informations forums : Inscription : avril 2008 Messages : 6 Points : 6 Points : 6	Bonjour tout le monde, Merci pour ces explications, ca aide énormément! Cependant j'ai une petite question (dsl :/). Tu dis qu'il ne faut que deux passes ? - une forward : tu prend chaque pixel et tu applique le masque des distances (seulement aux pixels du contour alors ?) - une backward : tu prend chaque pixel du contour + les pixels qui ont déja une distance ( les voisins directs du contour en quelque sorte ?) En fait je pense que je viens de répondre tout seul à ma question, il ne faut pas prendre que le contour lors de la première passe mais aussi les points que tu viens juste de changer c'est ca ? Merci pour ces supers explications !!
	00

03/04/2008, 10h24	#6
batoub Invité régulier Inscription : avril 2008 Messages : 6 Détails du profil Informations forums : Inscription : avril 2008 Messages : 6 Points : 6 Points : 6	Héhé super C'est pas bon d'essayer de comprendre un algo le matin à 8h :/ Fallait le temps que le cerveau se mette en marche ! Bon je vais essayer de coder ca, et je vous donne le résultat a la fin Merci beaucoup !!!
	00

10/04/2009, 00h25	#9
sufetul Invité de passage Inscription : avril 2009 Messages : 1 Détails du profil Informations forums : Inscription : avril 2009 Messages : 1 Points : 1 Points : 1	salut pour tous, je suis debutant , je cherche une definition exacte de la carte de distance(surtout par rapport à quoi est calcule la distance d'un pixel) et les etapes de creation ( en java) .
	00

16/04/2009, 13h08	#14
Esooo Invité de passage Inscription : avril 2008 Messages : 14 Détails du profil Informations forums : Inscription : avril 2008 Messages : 14 Points : 3 Points : 3	Merci pour le code Juste une question: comment on fait après pour convertir le double[][] en image? J'ai essayé de créer un byte[] et ensuite créer un bufferedImage comme ca mais j'ai l'impression que ca deforme un peu l'image :s
	00

23/05/2009, 08h58	#19
Xav00007 Candidat au titre de Membre du Club Inscription : mai 2009 Messages : 13 Détails du profil Informations forums : Inscription : mai 2009 Messages : 13 Points : 13 Points : 13	Bonjour, Que représente et à quoi servent le matrices : chessboard, chamfer3,chamfer5, ... Je suppose qu'il s'agit des masques, mais comment ceux-ci fonctionnent-ils? Un tout grand merci d'avance!
	00

Outils de la discussion
Afficher une version imprimable Envoyer un lien vers cette page par email