Discussion :

[nadjib2007]

Bonjour;

j'essaie de faire une implémentation sous builder C++ de la méthode "Fast Marching " -Sethian -, pour cela je suivre l'algorithme suivant:



Avec l'équation (3.8) discrétiser (équation Eikonal):




et les différents termes nécessaires discrétisés:



Le choix de la plus petite valeurs de T est faite par un tri par tas, quand j'ai chercher sur le net j'ai trouver le code source suivant mais j'ai rien comprer:

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
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
Implémentation du tris par tas générique. Bloomwhite 2002-2004
 
 Simple fonction (en fait c'est un objet utilisé en fonction).
 exemple: TriTas<int>(tab, taille(tab)); // ici, tab est un tableau d'entiers (int).
 
 Entrées:
 Le premier argument est un tableau de type C (vecteur). Il peut être de type quelconque.
 Le second argument est la taille du tableau en nombre d'éléments.
 (ou du dernier élément +1 à trier)
 Le troisième argument est optionnel:
 c'est une fonction de comparaison selon laquelle va être trié le tableau,
 si cette fonction est de type >, le tableau sera trié dans l'ordre croissant.
 Si elle n'est pas précisée, l'opérateur > sera utilisé par défaut;
 il faudra alors que cet opérateur soit définit pour le type contenu dans le tableau.
 
 Sorties:
 Aucune sortie. Le tableau sera trié.
 
 A Public OpenSource Project.
*/
#
 #ifndef _TriTas_H_
 #define _TriTas_H_
 
 
 // Je fourni la fonction utilisée par défaut pour le tri.
 // Pour des raisons aussi bien obscures que mystérieuses, j'ai pas pu la mettre dans la classe.
 template<class Type>
 inline bool _compare_defaut_tritas (Type a, Type b) { return (a>b); }
 // En fait, je pense que c'est parce qu'elle est utilisée en argument par défaut dans la classe.
 
 
 template<class Type>
 class TriTas
 {
 public:
 TriTas(Type*, int, bool (__cdecl*)(Type, Type)=_compare_defaut_tritas); // Tableau,taille,fct
 ~TriTas() {};
 private:
 inline void echange(Type& a, Type& b) { Type temp= a; a= b; b= temp; }
 bool (*compare) (Type, Type); // Donnée membre et non fonction (pointeur sur fonction).
 
 void entasser (int =0); // Par défaut entasser la racine.
 void construit (); // Tri.
 
 int _taille; // Taille du tableau.
 Type* _a; // Tableau à trier.
 };
 
 
 template<class Type>
 TriTas<Type>::TriTas(Type* a, int taille, bool (*comp)(Type, Type)) : _taille(taille), _a(a)
 {
 compare = comp;
 construit(); // D'abord préparation
 for (--_taille; _taille > 0; --_taille)
 {
 echange(_a[_taille],_a[0]); // Puis tri.
 entasser();
 }
 }
 
 template<class Type>
 void TriTas<Type>::entasser(int noeud)
 {
 int max,
 gauche= 2*noeud+1,
 droite= gauche+1;
 max = noeud;
 if (gauche<_taille && compare(_a[gauche],_a[noeud])) max = gauche;
 if (droite<_taille && compare(_a[droite],_a[max]) ) max = droite;
 
 if (max != noeud)
 {
 echange(_a[max],_a[noeud]);
 entasser(max);
 }
 }
 
 template<class Type>
 void TriTas<Type>::construit()
 {
 int last;
 for(last= _taille/2 - 1; last>=0; --last) // on commence au dernier ayant
 entasser(last); // un fils jusqu'au premier (la racine)
 }
 
 #endif //_TriTas_H_

alors est ce que je peut l'utiliser?!

Pour l'implémentation j'ai déclarer plusieurs matrices comme suit:

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
void __fastcall TForm1::FastMarching1Click(TObject *Sender)
{
// Méthode du Fast Marching-----FMM--------FMM--------FMM-------------FMM------------FMM-------
 
int H=Image1->Height;
int W=Image1->Width;
 
//declaration des  matrices  ------------------------------
 
//matrice de l'image
   float**m=new float*[H];
       for(int i=0;i<H;i++)
          {
           m[i]=new float[W];
          }
//matrice de contour
      float**mc=new float*[H];
       for(int i=0;i<H;i++)
          {
           mc[i]=new float[W];
          }
//matrice des valeurs acceptées
     float**accepte=new float*[H];
       for(int i=0;i<H;i++)
          {
           accepte[i]=new float[W];
          }
//matrice des valeurs Essai
float**essai=new float*[H];
       for(int i=0;i<H;i++)
          {
           essai[i]=new float[W];
          }
//matrice des valeurs Inconnu
float**inconnu=new float*[H];
       for(int i=0;i<H;i++)
          {
           inconnu[i]=new float[W];
          }
 
 
//declaration de la  matrice intermediaire (dis)-----------------------------------------------
 
     float**dis=new float*[H];
       for(int i=0;i<H;i++)
          {
           dis[i]=new float[W];
          }
 
//declaration de la matrice de sortie (Ms)
 
     float**Ms=new float*[H];
        for(int i=0;i<H;i++)
           {
            Ms[i]=new float[W];
           }

Et après je met:

- Sur le contour: mc[i][j]=0;
- à l'intérieure du contour: mc[i][j]=-1;
- à l'extérieure du contour: mc[i][j]=1;

Aprés:

Code :

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

1
2
3
4
5
6
7
8
9
10
 
for(int i=1;i<H-1;i++)
          for(int j=1;j<W-1;j++)
             if (dis[i][j]==0)
               {
                 accepte[i][j]=dis[i][j];// l'algorithme indique que accepte=courbe initiale
 
                 essai[i][j]=dis[i+1][j]+dis[i-1][j]+dis[i][j+1]+dis[i][j-1]; /* est ce que je peut écrire ça (une somme)=  voisins(accepte) ?! */
 
                 inconnu[i][j]=m[i][j]-accepte[i][j]-essai[i][j];

est ce que c'est juste ce qui est écrit précédemment?!

pour la deuxième partie du l'algorithme, comme je peut écrire :

Tant que essai != ensemble vide (je veut dire comment je vais écrire "ensemble vide") ?!


à la fin est ce qu'il y a quelqu'un qui peut me dire comment résoudre l'équation précédente et l'implémenter sous builder C++.

Je vous remercie beaucoup

[johnnyjohnny]

je me suis pas penché en détail sur ton programme, mais pour ma part j'ai écarté un certain nombre de problèmes en utilisant une toolbox développée en c++ disponible sur mathworks.
Fast Marching Toolbox

la toolbox a été développée en c++, par contre elle est faite pour marcher sous matlab et mex. Si tu ne travaille pas sous matlab il risque d'y avoir un peu de blabla.

avec un peu de chance tu arriveras à t'inspirer de ceci pour régler tes problèmes au niveau des formules.

[nadjib2007]

Salut;

Merci pour la réponse; pour "FastMarching Toolbox " j'ai la consulter avant que je poste mon message et elle a beaucoup d'erreurs non résolus.

Merci

[Danious]

Bonjour,

Dans ton algorithme, ACCEPTE, ESSAI et INCONNU sont des ensembles. Tu peux tout à fait utiliser des vecteurs, tableaux ou autres listes (à la place des matrices) pour implémenter ces ensembles. D'ailleurs, l'algorithme du tri par tas, qui m'a l'air juste, utilise en entrée un vecteur. Ca me paraît un peu bizarre de faire un tri par tas sur une matrice.

Tu peux certainement aussi utiliser des matrices, mais dans ce cas je ne comprends pas trop le :

essai[i][j]=dis[i+1][j]+dis[i-1][j]+dis[i][j+1]+dis[i][j-1];

qui à mon avis correspond plutôt à :
essai[i+1][j] = 1; /* par exemple 1 pour indiquer que (i+1,j) appartient à ESSAI*/
essai[i-1][j] = 1;
essai[i][j+1] = 1;
essai[i][j-1] = 1;

Si tu veux conserver les matrices comme structure pour l'implémentation, ce serait pas mal d'ajouter un entier initialisé à 0 et qui suit le nombre d'éléments égaux à 1 dans ta matrice essai. A ce moment là, ESSAI est l'ensemble vide si cet entier est égal à 0.

Honnetement, j'aurais aussi choisi d'utiliser des matrices à ta place. A mon avis, dans ton algorithme, c'est la ligne 5 qui va être la plus problématique avec des matrices.

[nadjib2007]

Merci beaucoup beaucoup pour votre réponse qui m'a aider; je vais utiliser qu'es que vous m'avez dit et on va voir...

Merci