[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

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

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 !!!

**hbloom** · 06/06/2013, 13h04

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** · 06/06/2013, 19h38

Envoyé par hbloom

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** · 07/06/2013, 09h43

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 ^^

**pseudocode** · 07/06/2013, 20h08

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

Non. On aura

output[5-1][6-1] = 0+4  // Nord-Ouest
output[5  ][6-1] = 0+3  // Nord
output[5+1][6-1] = 0+4  // Nord-Est
output[5+1][6  ] = 0+3  // Est
output[5+1][6+1] = 0+4  // Sud-Est
output[5  ][6+1] = 0+3  // Sud
output[5-1][6+1] = 0+4  // Sud-Ouest

     03 04 05 06 07
    +--------------+
 01 |  |  |  |  |  |
    |--------------|
 05 |  | 4| 3| 4|  |
    |--------------|
 06 |  | 3| 0| 3|  |
    |--------------|
 07 |  | 4| 3| 4|  |
    |--------------|
 08 |  |  |  |  |  |
    +--------------+

et pk les conditions (dy!=0 et dx!=dy) ?
(...)
Mais il n'y a aucune méthode dans le code qui montre qu'on fait par symétrie, vu que vous définissez une partie du masque et après vous utilisez toutes les valeurs

Code java :

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

1
2
3
4
5
6
testAndSet(output, x+dx, y+dy, v+dt);				// P1 (donné dans le masque) -> zone 0-45°
if (dy!=0) testAndSet(output, x-dx, y+dy, v+dt);		// P2, symétrique vertical de P1 -> zone 135-180°
if (dx!=dy) {
	testAndSet(output, x+dy, y+dx, v+dt);			// P3, symétrique diagonal de P1 -> zone 45-90°
	if (dy!=0) testAndSet(output, x-dy, y+dx, v+dt);	// P4, symétrique vertical de P3 -> zone 90-135°
}

Les conditions sont la pour écarter les points qui sont exactement sur l'axe de symétrie (et donc qui ne bougent pas lors de la symétrie).

Idem pour la boucle "backward", qui positionne les points dans les zones 180-360°.

**hbloom** · 10/06/2013, 09h14

Merci bcp !!

[java] Carte des distances (Chamfer)

Contribuez

Vue hybride

Discussions similaires

Partager

Partager