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
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
|
import java.awt.image.BufferedImage;
import java.util.Iterator;
import java.util.List;
import imageTiTi.ImageConverter;
import imageTiTi.ImageDrawer;
import mathematics.Bresenham;
import mathematics.metrics.Euclidian;
import mathematics.metrics.Metric;
import mathematics.primitives.pointsTiTi.Point;
import mathematics.primitives.pointsTiTi.Point3DI;
import mathematics.primitives.pointsTiTi.PointI;
import mathematics.primitives.pointsTiTi.PointIManager;
import utils.times.Chronometer;
/**
* <p>Description: Classe qui definit un diametre geodesique en 2D. Elle stocke l'ensemble des points du diametre, sa longueur
* ainsi que la plus courte distance (variation diametrale) entre chaque point et le bord de l'objet.</p>
* <p>Package(s) required: displays, imageTiTi, mathematics, utils.</p>
* <p>Copyright: Copyright (c) 2007-2010.</p>
* <p>Laboratories/Teams: CMM (Mines-ParisTech/ENSMP), I&M (ex LXAO) LSIS.</p>
* <p>Updates:<br>
* 06 Janvier 2010 => Correction afin de gerer les formes touchant le bord de l'image et la variation diametrale n'est calculee
* que si la carte de distance est non nulle.<br>
* 02 Avril 2008, 2.0 => Adaption aux nouvelles formes des distances et des cartes de distances.<br>
* 21 Aout 2007 => Creation.<p>
*
* @author Guillaume THIBAULT
* @version 2.0
*/
public class GeodesicDiameter
{
/** Constante qui definissent le type d'affichage.*/
public final int POINTS = 0 ;
/** Constante qui definissent le type d'affichage.*/
public final int LIGNES = 1 ;
private double[] VariationDiametrale = null ;
private double VariationDiametraleMoyenne = 0.0 ;
private double Longueur = 0.0 ;
private PointIManager Minimum = new PointIManager("DiametreGeodesiqueMinimum") ;
private PointIManager Total = new PointIManager("DiametreGeodesiqueTotal") ;
private DistanceMap Arrivee = new DistanceMap() ;
private String Nom = null ;
/** Un constructeur.*/
public GeodesicDiameter()
{
}
/** Methode qui calcule le diametre geodesique d'une forme.
* @param image L'image contenant la forme.
* @param Contour Les points de contour de la forme (la frontiere de la forme).
* @param Barycentre Le barycentre de la forme.
* @param Dist La distance a utiliser pour le calcul des cartes de distances.
* @param DM La carte de distance de la forme. Permettra de calculer la variation diametrale.
* @param TrouverChemin true => on calcule le chemin exact, false sinon.
* @param Chrono Le chronometre pour mesurer la duree de l'execution.*/
public void Compute(BufferedImage image, PointIManager Contour, Point Barycentre, Distance Dist, DistanceMap DM, boolean TrouverChemin, Chronometer Chrono)
{
boolean[][] input = ImageConverter.ImageToBoolean(image) ;
Compute(input, Contour, Barycentre, Dist, DM, TrouverChemin, Chrono) ;
input = null ;
}
/** Methode qui calcule le diametre geodesique d'une forme.
* @param Input Le tableaude booleen contenant la forme.
* @param Contour Les points de contour de la forme (la frontiere de la forme).
* @param Barycentre Le barycentre de la forme.
* @param Dist La distance a utiliser pour le calcul des cartes de distances.
* @param DM La carte de distance de la forme. Permettra de calculer la variation diametrale.
* @param TrouverChemin true => on calcule le chemin exact, false sinon.
* @param Chrono Le chronometre pour mesurer la duree de l'execution.*/
public void Compute(boolean[][] Input, PointIManager Contour, Point Barycentre, Distance Dist, DistanceMap DM, boolean TrouverChemin, Chronometer Chrono)
{
int marker = 0 ;
if ( Chrono != null )
{
System.out.print("Calcul du diametre geodesique : ") ;
marker = Chrono.setMarker() ;
}
if ( Dist.isChamfrein() ) throw new IllegalArgumentException("Une distance de Montanari est nécessaire pour ce calcul") ;
ComputeDiameter(Input, Contour, Barycentre, Dist) ;
if ( Chrono != null )
{
System.out.println(Chrono.getTimeSinceMarker(marker)) ;
Chrono.FreeMarker(marker) ;
}
if ( TrouverChemin )
{
if ( Chrono != null )
{
System.out.print("Calcul du chemin du diamètre géodésique : ") ;
marker = Chrono.setMarker() ;
}
TracerDiametre(Input, Dist, DM) ;
if ( Chrono != null )
{
System.out.println(Chrono.getTimeSinceMarker(marker)) ;
Chrono.FreeMarker(marker) ;
}
}
}
/** Methode qui calcule les deux points extremes du diametre geodesique.
* @param input L'entree contenant la forme.
* @param Contour Le contour de la forme.
* @param Barycentre Le barycentre de la forme.
* @param Dist La distance a utiliser pour calculer le diametre geodesique.*/
private void ComputeDiameter(boolean[][] input, PointIManager Contour, Point Barycentre, Distance Dist)
{
boolean Fin ;
int i, nb ;
double vmax ;
double[] distances = new double[20] ;
DistanceMap DMG = new DistanceMap() ;
PointI depart = new Point3DI() ;
PointIManager Geo = new PointIManager("Diamètre géo") ;
PointI p, pmax = null ;
DistanceMapComputer ccd = new DistanceMapComputer() ;
Metric dist = new Euclidian() ;
Minimum.RemoveAll() ;
Total.RemoveAll() ;
//if ( Minimum.Size() > 0 ) throw new Error("Calcul déjà effectué.") ;
if ( Contour.NbPoints() <= 1 ) throw new Error("Nombre de points du contour <= 1.") ;
if ( !input[(int)(Barycentre.getY()+0.5)][(int)(Barycentre.getX()+0.5)] ) // Si le barycentre n'est pas dans la forme.
{ // On prend le point de la forme le plus proche.
vmax = 10000.0 ;
for (i=0 ; i < Contour.Size() ; i++)
{
p = Contour.Point(i) ;
if ( dist.Distance(Barycentre, p) < vmax )
{
pmax = Contour.Point(i) ;
vmax = dist.Distance(Barycentre, p) ;
}
}
depart.setXY(pmax.getX(), pmax.getY()) ;
}
else depart.setXY((int)(Barycentre.getX()+0.5), (int)(Barycentre.getY()+0.5)) ;
nb = 0 ;
Fin = false ;
do { // On calcule les deux points du diametre géodésique.
if ( Geo.NbPoints() == 0 ) ccd.ComputeStartingPoints(input, Dist, depart) ;
else
if ( Geo.Size() % 2 == 0 ) ccd.ComputeStartingPoints(input, Dist, Geo.Points()) ;
else ccd.ComputeStartingPoints(input, Dist, Geo.Point(Geo.Size()-1)) ;
DMG.Map = ccd.getMap() ;
vmax = 0.0 ;
pmax = Contour.Point(0) ;
for (i=1 ; i < Contour.Size() ; i++)
{
p = Contour.Point(i) ;
if ( vmax < DMG.Map[p.getY()][p.getX()] )
{
pmax = Contour.Point(i) ;
vmax = DMG.Map[p.getY()][p.getX()] ;
}
}
try {
Geo.Add(pmax) ;
}
catch ( CloneNotSupportedException e )
{
e.printStackTrace();
throw new Error() ;
}
if ( Geo.Size() % 2 == 0 ) distances[nb++] = vmax ;
if ( Geo.Size() % 2 == 0 && Geo.Size() > 2 )
if ( distances[nb-1] <= distances[nb-2] ) Fin = true ;
} while ( !Fin ) ;
Longueur = distances[nb-2] ; // On ajoute ces deux points à la liste.
Minimum.InsertPointAt(0, Geo.Point(Geo.Size()-3).getX(), Geo.Point(Geo.Size()-3).getY()) ;
Minimum.InsertPointAt(1, Geo.Point(Geo.Size()-4).getX(), Geo.Point(Geo.Size()-4).getY()) ;
Geo.RemoveAll() ;
Geo = null ;
distances = null ;
DMG = null ;
depart = null ;
dist = null ;
}
/** Methode qui calcule un premier chemin totalement brut et non optimise, base sur une distance de taille 2.
* @param input L'entree contenant la forme.*/
private void PreliminaryPath(boolean[][] input)
{
double min ;
int i, x, y, X, Y, xmin, ymin ;
int width = input[0].length ;
int height = input.length ;
boolean Fin = false ;
Distance dist = DistanceTools.CreerDistanceMontanari(2, 2) ;
DistanceMapComputer ccd = new DistanceMapComputer() ;
ccd.ComputeStartingPoints(input, dist, Minimum.Point(1)) ;
Arrivee.Map = ccd.getMap() ;
xmin = Minimum.Point(0).getX() ;
ymin = Minimum.Point(0).getY() ;
i = 0 ;
do {
X = xmin ;
Y = ymin ;
min = Double.MAX_VALUE ;
for (y=-1 ; y <= 1 ; y++)
for (x=-1 ; x <= 1 ; x++)
if ( y != 0 || x != 0 )
if ( 0 <= X+x && X+x < width && 0 <= Y+y && Y+y < height && input[Y+y][X+x] )
if ( Arrivee.Map[Y+y][X+x] < Arrivee.Map[Y][X] )
if ( Arrivee.Map[Y+y][X+x] < min )
{
min = Arrivee.Map[Y+y][X+x] ;
xmin = X + x ;
ymin = Y + y ;
}
if ( (Minimum.Point(i+1).getX() == xmin) && (Minimum.Point(i+1).getY() == ymin) ) Fin = true ;
else
{
Minimum.InsertPointAt(i+1, xmin, ymin) ;
i++ ;
}
} while ( !Fin ) ;
}
/** Methode qui trace le diametre geodesique. Elle calcule tout d'abord une solution non optimisee, puis converge vers le diametre geodesique.
* @param input L'entree booleenne representant l'objet.
* @param Dist La distance a utiliser pour calculer la longueur du diametre geodesique.
* @param DM La carte de distance de la forme pour calculer la variation diametrale.*/
private void TracerDiametre(boolean[][] input, Distance Dist, DistanceMap DM)
{
int i, Old, Securite, nb ;
boolean Fin, Sens ;
double distance ;
PointI p = null ;
Metric dist = new Euclidian() ;
PreliminaryPath(input) ;
List<PointI> Resultat = null ;
Iterator<PointI> iter = null ;
Securite = Old = 0 ;
do {
Old = Minimum.Size() ;
for (i=0 ; i < Minimum.Size()-1 ; i++) // On va remplir Total.
{
Resultat = Bresenham.TracerListe(Minimum.Point(i).getX(), Minimum.Point(i).getY(), Minimum.Point(i+1).getX(), Minimum.Point(i+1).getY()) ;
iter = Resultat.iterator() ;
if ( iter.hasNext() ) iter.next() ; // On ne met pas le premier.
nb = 0 ;
while ( iter.hasNext() )
{
p = iter.next() ;
if ( iter.hasNext() ) // On ne met pas le dernier
{
Minimum.InsertPointAt(i+nb+1, p.getX(), p.getY()) ;
nb++ ;
}
}
i += nb ;
}
Sens = true ;
do { // On simplifi l'ensemble des points trouvés car la plupart ne sont pas correctes.
Fin = true ;
if ( Sens )
{
for (i=0 ; i < Minimum.Size()-2 ;)
if ( TraceCorrecte(input, Minimum.Point(i), Minimum.Point(i+2)) )
{ // On élime les points inutiles et ceux qui sont mal placés.
Minimum.Remove(i+1) ;
Fin = false ;
}
else i++ ;
}
else
{
for (i=Minimum.Size()-1 ; i-2 >= 0 ;)
if ( TraceCorrecte(input, Minimum.Point(i), Minimum.Point(i-2)) )
{ // On élime les points inutiles et ceux qui sont mal placés.
Minimum.Remove(i-1) ;
Fin = false ;
i-- ;
}
else i-- ;
}
Sens = !Sens ;
} while ( !Fin ) ;
Securite++ ;
} while ( Old != Minimum.Size() && Securite < 20 ) ;
Total.Add(Minimum.Point(0).getX(), Minimum.Point(0).getY()) ; // On met le point d'origine.
distance = 0.0 ;
for (i=0 ; i < Minimum.Size()-1 ; i++) // On va remplir Total.
{
distance += dist.Distance(Minimum.Point(i), Minimum.Point(i+1)) ;
Resultat = Bresenham.TracerListe(Minimum.Point(i).getX(), Minimum.Point(i).getY(), Minimum.Point(i+1).getX(), Minimum.Point(i+1).getY()) ;
iter = Resultat.iterator() ;
if ( iter.hasNext() ) iter.next() ; // On ne met pas le premier.
while ( iter.hasNext() )
{
p = iter.next() ;
Total.Add(p.getX(), p.getY()) ;
}
}
Longueur = distance ;
VariationDiametrale = null ;
if ( DM != null )
{
VariationDiametrale = new double[Total.Size()] ; // Remplissage de la variation diametrale
for (i=0 ; i < VariationDiametrale.length ; i++) VariationDiametrale[i] = DM.Map[Total.Point(i).getY()][Total.Point(i).getX()] ;
for (i=0 ; i < VariationDiametrale.length ; i++) VariationDiametraleMoyenne += VariationDiametrale[i] ;
VariationDiametraleMoyenne /= (double)VariationDiametrale.length ;
}
}
/** Methode qui permet de savoir si le trace entre deux points du diametre est correcte : c'est-a-dire si le segment qui relie les points est dans la forme.
* @param input L'entree contenant la forme.
* @param depart Le point de depart.
* @param arrivee Le point d'arrivee.
* @return true => le segment/chemin est dans la forme, false sinon.*/
protected boolean TraceCorrecte(boolean[][] input, PointI depart, PointI arrivee)
{
PointI p = null ;
List<PointI> Resultat = Bresenham.TracerListe(depart.getX(), depart.getY(), arrivee.getX(), arrivee.getY()) ;
Iterator<PointI> iter = Resultat.iterator() ;
while ( iter.hasNext() )
{
p = iter.next() ;
if ( !input[p.getY()][p.getX()] ) return false ;
}
return true ;
}
/* --------------------------------------------------- Les implémentations --------------------------------------------------- */
/** Methode qui permet de dessiner l'objet dans l'image.
* @param image L'image dans laquelle on doit dessiner.
* @param color Le tableau de float contenant la couleur dans laquelle l'objet doit etre dessine.
* @param order L'ordre du point => Taille = 2 x Ordre +1.*/
public void Draw(BufferedImage image, float[] color, int order)
{
ImageDrawer imdraw = new ImageDrawer() ;
for (int i=0 ; i < Minimum.Size()-1 ; i++)
imdraw.Line(image,
Minimum.Point(i).getX(), Minimum.Point(i).getY(), Minimum.Point(i+1).getX(), Minimum.Point(i+1).getY(),
order, color) ;
imdraw = null ;
}
/* --------------------------------------------------- Les getters & setters --------------------------------------------------- */
/** Retourne la longueur du diametre.
* @return La longueur du diametre.*/
public double getLength()
{
return Longueur ;
}
/** Methode qui retourne les points strictements necessaires a la representation du diametre.
* @return L'ensemble des points minimum du diametre.*/
public PointIManager getMinimum()
{
return Minimum ;
}
/** Methode qui retourne le Ieme point de la representation minimum du diametre.
* @param index L'index du point a retourner.
* @return Le Ieme point a retourner.*/
public PointI getIemeMinimum(int index)
{
return Minimum.Point(index) ;
}
/** Methode qui retourne le nombre de points minimum a la representation du diametre.
* @return Le nombrede point du diametre minimum.*/
public int getMinimumSize()
{
return Minimum.Size() ;
}
/** Methode qui retourne la totalite des points du diametre.
* @return L'ensemble des points du diametre.*/
public PointIManager getTotal()
{
return Total ;
}
/** Methode qui retourne le Ieme point du diametre.
* @param index L'index du point qui l'on souhaite retourner.
* @return Le Ieme point du diametre.*/
public PointI getIemeTotal(int index)
{
return Total.Point(index) ;
}
/** Methode qui retourne le nombre de point du diametre.
* @return Le nombre de points du diametre.*/
public int getTotalSize()
{
return Total.Size() ;
}
/** Methode qui retourne le tableau contenant la varation diametrale.
* @return La variation diametrale du diametre.*/
public double[] getVariationDiametrale()
{
return VariationDiametrale ;
}
/** Methode qui retourne la Ieme valeur de la variation diametrale.
* @param index L'index de la valeur de la variation diametrale que l'on souhaite.
* @return La valeur de la IndexIeme variation diametrale.*/
public double getIemeVariationDiametrale(int index)
{
return VariationDiametrale[index] ;
}
/** Methode qui retourne la variation diametrale moyenne.
* @return La variation diametrale moyenne.*/
public double getVariationDiametraleMoyenne()
{
return VariationDiametraleMoyenne ;
}
public String getName()
{
return Nom ;
}
public void setName(String Nom)
{
this.Nom = Nom ;
}
/** On surcharge la methode afin que le nom soit correctement affiche dans l'IHM.
* @return Le nom de la classe.*/
public String toString()
{
return Nom ;
}
} |
