# Gnral Dveloppement > Algorithme & Mathmatiques > Traitement d'images >  Dtection des concavits avec un Gvf Snake

## MSN9149

Bonjour tout le monde. voici mon probleme:
j'ai programme un contour actif classique avec comme energie externe un champs de flux de gradient, pour pouvoir bien detecter les zones concaves..
sauf que, on le testant sur l'image de la feuille de trefle du tutoriel de developpez suivant:http://khayyam.developpez.com/articl...ntours-actifs/
 j'obtiens le resultat suivant:



ps:dans mon algorithme j'ajoute(resp supprime) a chaque iteration des noeuds si la distance entre eux est superieur(resp inferieur), a un certain seuil.
et j'ai essaye de changer les parametres de l'energie de courbure, de continuite ca donne rien, pourtant l'image pretraite est bien seuillee et non bruitee.

----------


## pseudocode

> ps:dans mon algorithme j'ajoute(resp supprime) a chaque iteration des noeuds si la distance entre eux est superieur(resp inferieur), a un certain seuil.


Faire cela  chaque itration, ca peut poser des problmes dans les goulets d'tranglement comme c'est le cas ici.

Il vaut mieux laisser les points du Snake voluer sans cette contrainte pendant plusieurs itrations (10-20), puis faire la phase d'ajout/suppression.

Le mieux tant de recalculer la position "idale" des points sur le contour du Snake. Ca permet non seulement d'avoir le nombre idal de points, mais aussi de tous les espacer uniformment.




> et j'ai essaye de changer les parametres de l'energie de courbure, de continuite ca donne rien, pourtant l'image pretraite est bien seuillee et non bruitee.


Normalement ca devrait converger sans problmes avec simplement une nergie d'attraction et une nergie de courbure.

----------


## MSN9149

> Faire cela  chaque itration, ca peut poser des problmes dans les goulets d'tranglement comme c'est le cas ici.
> 
> Il vaut mieux laisser les points du Snake voluer sans cette contrainte pendant plusieurs itrations (10-20), puis faire la phase d'ajout/suppression.


je vais essayer de faire ce que tu dis, meme si je converge generalement en 40 iterations donc il va ajouter/suppr 4 fois a peu pres.




> Le mieux tant de recalculer la position "idale" des points sur le contour du Snake. Ca permet non seulement d'avoir le nombre idal de points, mais aussi de tous les espacer uniformment.


je comprends pas vraiment ce que tu veux dire par recalculer la position ideale?

----------


## pseudocode

> je comprends pas vraiment ce que tu veux dire par recalculer la position ideale?


Plutot que de s'occuper seulement des points problmatiques (trop prs/loigns), on recalcule la position de TOUS les points.

Voila comme je procde personnellement pour le recalcule (cf la mthode rebuild de la contribution).

Au dpart, on a un Snake est compos d'une suite de M points {P1, P2, ... ,Pm}. 
- On calcule la longueur du Snake = clength. 
- On divise cette longueur par l'espacement moyen voulu "space", ce qui nous donne le nouveau nombre de points dans le Snake = clength/space = N.
- On cre donc un nouveau Snake compos de N points {Q1, Q2, ..., Qn}. Chaque point Qi est calcul en interpolant les coordonnes des points correspondants dans le snake de dpart.

J'ai utilis une reprsentation paramtrique du snake pour simplifier le calcul : Snake(t), avec t variant entre 0 et clength.

Snake 
original    P1--P2----P3---------P4-------P5----P6-- .... ----Pm


paramtre   |-----------|-----------|------------|-- .... ----|
            0         space      2*space       3*space        clength

Snake
recalcul   Q1----------Q2----------Q3----------Q4-- .... ----Qn

----------


## MSN9149

donc si j'ai bien compris ce traitement, tu le fais a chaque iteration?
dans ce cas est ce qu'on a besoin d'ajouter/supprimer les points qui sont trop loin ou trop pres?

Autres questions: c'est quoi l'espacement voulu(comment il est calcule)?
et comment on calcule les Qi par interpolation des Pi?

ps: j'ai lu la fonction build de ta contribution, je comprends toujours pas a quoi sert l'interpolation cubique dans ce cas

merci!

----------


## pseudocode

> donc si j'ai bien compris ce traitement, tu le fais a chaque iteration?


Non, toutes les 10-20 iterations.




> dans ce cas est ce qu'on a besoin d'ajouter/supprimer les points qui sont trop loin ou trop pres?


Non, effectivement.




> Autres questions: c'est quoi l'espacement voulu(comment il est calcule)?


Ca peut tre est un nombre fixe, totalement empirique (genre 4 ou 8 pixels). 




> et comment on calcule les Qi par interpolation des Pi?
> 
> ps: j'ai lu la fonction build de ta contribution, je comprends toujours pas a quoi sert l'interpolation cubique dans ce cas


Comme je l'ai dit, l'ide c'est de reprsenter le snake sous forme d'une courbe paramtrique. Le paramtre tant ici la "distance" depuis le point de dpart. C'est plus pratique pour interpoler que le simple "index" dans une liste.

L'interpolation cubique c'est simplement pour avoir des points plus joliment placs (ca fait une courbe plus naturelle).

----------


## MSN9149

donc pour pouvoir detecter les concavites on doit avoir un snake, avec des points equidistants.
d'ailleurs comme la methode precedante(celle qui ajoute/supprime les noeuds) ne donne rien, donc je suis oblige de comprendre la tienne... ::aie:: 

qu'est ce qui peut etre facultatif dans la methode rebuild(l'interpolation cubique par exemple :p)?

----------


## pseudocode

> donc pour pouvoir detecter les concavites on doit avoir un snake, avec des points equidistants.


Il n'y a rien d'obligatoire. C'est simplement que je remarque que ca marche mieux dans ce cas. 

C'est certainement li au fait qu'on utilise un schma explicite pour faire converger le snake (dans mon cas une approche glouton o chaque point est dplac vers son minimum local).




> qu'est ce qui peut etre facultatif dans la methode rebuild(l'interpolation cubique par exemple :p)?


Oui, l'interpolation linaire est suffisante.

----------


## MSN9149

moi aussi j'utilise une approche gloutonne(algorithme greedy) avec comme energie externe, un champ de gvf.
je me suis dit qu'il faut a tout prix profiter de l'avantage des gvf, i.e. detection des concavites.

ca me rassure de savoir que j'ai pas a programmer les interpolations cubiques,
donc je m'arrete sur le point(dans rebuild), ou les points seront equidistants avant leur representation?

----------


## pseudocode

> ca me rassure de savoir que j'ai pas a programmer les interpolations cubiques,
> donc je m'arrete sur le point(dans rebuild), ou les points seront equidistants avant leur representation?


Il faut tout de meme interpoler la position des "nouveaux" points.

Comme j'ai essay de le montrer dans mon schma du post #4, les "anciens" points peuvent former des paquets... Un nouveau point (Q_i) se trouve donc quelque-part entre deux anciens points conscutifs (P_k et P_k+1).

----------


## MSN9149

j'avais trouver dans le programme de Xu & Prince(gvf), une fonction d'interpolation mais qui se faisait a chaque iteration.
a vrai dire je comprends pas vraiment ce que fait l'iinterpolation?  ::aie:: 

merci

----------


## pseudocode

[quote=MSN9149;5991714]j'avais trouver dans le programme de Xu & Prince(gvf), une fonction d'interpolation mais qui se faisait a chaque iteration.
a vrai dire je comprends pas vraiment ce que fait l'iinterpolation?  ::aie:: 

L'interpolation, c'est pour placer le "nouveau" point exactement o il faut entre les 2 anciens points.

AncienSnake {P0, P1, P2}, longueur du snake = 10
Position P0 = 0
Position P1 = 2 // le point P1 s'est agglutin prs du point P0
Position P2 = 10

NouveauSnake {Q0, Q1, Q2}, longueur du snake = 10
Position Q0 = 0
Position Q1 = 5
Position Q2 = 10

On en dduit que 
Q0 = P0
Q1 = quelque-part entre P1 et P2
Q2 = P2

Pour calculer Q1, on interpole les valeurs de P1 et P2
0 1 2 3 4 5 6 7 8 9 10
----|-----|---------|--->
    |     |         |
    P1    |         P2
          |
          Q1
    <-d1-><----d2--->
    
    <----d=d1+d2---->
          
Q1 = (d2/d)*P1 + (d1/d)*P2



> mais dans son programme il ajoute/supprime des points alors que dans le tien je crois pas que ca soit le cas, sauf si je me trompe!


Dans mon programme j'ajoute/supprime des points toutes les 10-20 itrations (paramtrable). Et  la fin, pour faire joli, je recalcule le snake pour avoir des points espacs uniformment. Mais ce re-calcul n'influence pas la convergence puisque c'est fait  la fin.

Ce que je te conseille, c'est de faire ce re-calcul toutes les 10-20 itrations afin d'avoir des points espacs uniformment pendant la convergence. Normalement, cet espacement est gr automatiquement par une des nergies du snake. Mais en pratique, je trouve que ca converge mieux en forcant les positions.

----------


## MSN9149

merci beaucoup pour tes explictions sur l'interpolation. Du coup je crois qu'on a deja etudie ca en cours  ::aie:: 
[quote=pseudocode;5991767]


> Dans mon programme j'ajoute/supprime des points toutes les 10-20 itrations (paramtrable). Et  la fin, pour faire joli, je recalcule le snake pour avoir des points espacs uniformment. Mais ce re-calcul n'influence pas la convergence puisque c'est fait  la fin.


c'est pas que pour faire joli j'espere  :8O: , je croit que ca va m'aider dans ma convergence dans les zones concaves puisque ca a fonctionnne dans le programme de Xu et Prince.




> Ce que je te conseille, c'est de faire ce re-calcul toutes les 10-20 itrations afin d'avoir des points espacs uniformment pendant la convergence. Normalement, cet espacement est gr automatiquement par une des nergies du snake. Mais en pratique, je trouve que ca converge mieux en forcant les positions.


normalement, il devrait etre gerer par l'energie de continuite, mais comme elle n'arrive pas rendre les points equidistants, je suis oblige de passer par l'interpolation.

----------


## MSN9149

ce que tu viens de faire sur ton dernier poste, c'est de l'interpolation lineaire?
si c'est le cas est ce que je peux me baser sur cette formule(en fonction des deux points p1 et p2) dans un algorithme?


-une autre question a propos de ta contribution(fonction rebuild-> partie interpolation cubique):pourquoi tu ajoute 0.5 au total dans le calcul du nombre de noeuds du nouveau snake, et pourquoi tu ajoute toujours ce meme nombre aux nouveaux x et y?

merci de tes reponses

----------


## pseudocode

> ce que tu viens de faire sur ton dernier poste, c'est de l'interpolation lineaire?


oui.




> si c'est le cas est ce que je peux me baser sur cette formule(en fonction des deux points p1 et p2) dans un algorithme?


Heu... oui.




> -une autre question a propos de ta contribution(fonction rebuild-> partie interpolation cubique):pourquoi tu ajoute 0.5 au total dans le calcul du nombre de noeuds du nouveau snake, et pourquoi tu ajoute toujours ce meme nombre aux nouveaux x et y?


C'est parce que je cherche a convertir des "double" en "int" avec la meilleur approximation. Le cast en "(int)" supprime les chiffres aprs la virgule, ce qui n'est pas terrible comme approximation pour les valeurs comme "0.999". En ajoutant 0.5, c'est mieux.

M'enfin bon, c'est pas franchement ncessaire dans le cas prsent. C'est plus une habitude de codage qu'une ncessit.

----------


## MSN9149

merci de tes reponses.

mais il reste toujours un probleme qui me tracasse avant d'elaborer mon algorithme avec la formule que tu m'as donner (celle de l'interpolation lineaire),
c'est comment passer a un plus grand nombre de noeuds?

exemple on a 3 noeuds mal positionnes, apres calcul en utilisant la distance ideale, on se rend compte qu'il nous faut plus de noeuds..
ou est ce que on doit les ajouter, pour pouvoir appliquer cette formule dessus?  ::aie::

----------


## pseudocode

> exemple on a 3 noeuds mal positionnes, apres calcul en utilisant la distance ideale, on se rend compte qu'il nous faut plus de noeuds..
> ou est ce que on doit les ajouter, pour pouvoir appliquer cette formule dessus?


Bah heu, ca ne change rien. Un noeud Q_i  sera toujours entre deux noeuds P_k et P_k+1.

0 1 2 3 4 5 6 7 8 9 10
|---|---|---|-|-|---|--->
P0  |   |   | P1|   P2
|   |   |   |   |   |
|   |   |   |   |   |
Q0  Q1  Q2  Q3  Q4  Q5


Q0 = P0
Q1 = (5*P0 + 2*P1)/7
Q2 = (3*P0 + 4*P1)/7
Q3 = (1*P0 + 6*P1)/7
Q4 = (2*P1 + 1*P2)/3
Q5 = P2

----------


## MSN9149

merci beaucoup, maintenant je comprends mieux.
une derniere question(enfin j'espere que c'est la derniere  ::aie:: ):

mathematiquement, ta formule est differente de celle que je trouve sur wikipedia, parce que j'ai lu tout l'article sur l'interpolation lineaire sur wikipedia et c'est une tout autre formule qui est mentionnee? elle est fondee sur quoi?

sur wikipedia, ca parle de dessiner une droite qui passe par les deux points(x = 2 et 3), et que pour trouver l'ordonnee du point au milieu, il suffisait juste de remplacer le x(qu'on a deja 2,5) dans l'equation de la droite.

----------


## MSN9149

autre question tres importante:
comment je vais calculer les coordonnes(x,y) des nouveaux points Qi en utilisant cette formule?

----------


## pseudocode

> sur wikipedia, ca parle de dessiner une droite qui passe par les deux points(x = 2 et 3), et que pour trouver l'ordonnee du point au milieu, il suffisait juste de remplacer le x(qu'on a deja 2,5) dans l'equation de la droite.


Ma formule est celle d'un barycentre pondr de deux points:  Q = w1*P1 + w2*P2, avec w1+w2=1

avec un peu de mathmatique :

Q = w1*P1 + w2*P2 =  (1-w2)*P1 + w2*P2 = w2*(P2-P1) + P1

ce qui est l'quation d'une droite : y = ax + b  :;): 




> autre question tres importante:
> comment je vais calculer les coordonnes(x,y) des nouveaux points Qi en utilisant cette formule?


C'est du calcul vectoriel. Il suffit d'appliquer la formule sur chaque coordonnes x et y.

Q.x = w1*P1.x + w2*P2.x
Q.y = w1*P1.y + w2*P2.y

----------


## MSN9149

merci pour les explications sur l'application de la formule.
en fait, c'est la meme que celle sur wikipedia (l'equation de droite).
j vais pouvoir l'implementer maintenant que j'ai compris comment ca fonctionne.

----------


## MSN9149

mais est ce que cette interpolation est rapide(en temps d'execution)?

----------


## pseudocode

> mais est ce que cette interpolation est rapide(en temps d'execution)?


Oui, c'est assez rapide, compar aux autres calculs du Snake (gvf, energies, ...)

----------


## MSN9149

j'ai implemente l'algorithme des interpolation lineaire comme tu me l'as dit,
mais j'arrive toujours pas detecter les zones concaves.

voici ce que j'obtiens:



j'avoue que la convergence de la courbe est plus agreable a regarder  ::mouarf:: .

----------


## pseudocode

Il faut avoir suffisamment de points qui composent le Snake, afin de pouvoir suivre la concavit sans tre gn par les contraintes (energies internes).

Par exemple, ca fonctionne dans mon programme si je mets un point tous les 8 pixels (bien que je n'utilise pas un vrai GVF).

----------


## MSN9149

tu vois les points en rouge sur mon  contour actif dans mon poste precedant.
c'est les points qui composent mon contour actif.

j'ai demarre avec un nombre de noeuds egale a 50 ca se bloque au meme endroit...

en lisant le code de ta contribution, je me suis apercu que tu utilisais 4 energies:
deux energies internes de continuite et de courbure(pas de probleme puisque je les utilise aussi.)
les energies externes:
flow : c'est la carte de distance donc c'est semblable aux champs de gvf.
inertia: si j'ai bien compris, c'est l'energie de gradient(cellle la je l'ai pas dans mon energie finale).

pense-tu que si je l'ajouterais je pourrais avoir un resultat similaire au tien?
ou bien tu me propose quelque chose d'autre?

----------


## pseudocode

> tu vois les points en rouge sur mon  contour actif dans mon poste precedant.
> c'est les points qui composent mon contour actif.


Ah, effectivement tu en as dj beaucoup, peut-tre meme un peu trop.




> j'ai demarre avec un nombre de noeuds egale a 50 ca se bloque au meme endroit...


Personnellement, je ne fixe pas  l'avance le nombre de noeuds, mais je fixe l'espacement min/max entre les noeuds.




> en lisant le code de ta contribution, je me suis apercu que tu utilisais 4 energies:
> deux energies internes de continuite et de courbure(pas de probleme puisque je les utilise aussi.)
> les energies externes:
> flow : c'est la carte de distance donc c'est semblable aux champs de gvf.
> inertia: si j'ai bien compris, c'est l'energie de gradient(cellle la je l'ai pas dans mon energie finale).
> 
> pense-tu que si je l'ajouterais je pourrais avoir un resultat similaire au tien?
> ou bien tu me propose quelque chose d'autre?


Pour l'exemple que je viens de poster ci-avant, je n'ai utilis que 2 energies : courbure et flow.

Je n'ai pas besoin de la "continuit" car j'ai recalcul le snake toutes les 10 itrations. Et l'energie "inertia" n'est pas vraiment utile lorsque le snake a beaucoup de points.

----------


## MSN9149

l'energie flow(la carte des distances) elle est semblable a l'energie du gvf, puisque je ne fais que calculer la norme de u et v dans tout point de la carte.

qu'est ce qui bien etre different dans mon algorithme compare au tien?
t'as utilise un algorithme glouton moi l'algorithme greedy. c'est pareil je trouve.
n'empeche j'arrive pas avoir les memes resultats que toi.  ::aie:: 

ps: moi aussi je ne fixe pas le nombre de noeuds initial, puisque j'utilise l'interpolation lineaire comme tu me l'as explique(elle est recalculee toute les 10 iterations).
j'avais juste essayer de demarrer avec un grand nombre de noeuds pour voir..

----------


## MSN9149

mon probleme, c'est qu'une fois la forme trouvee:
les pixels vont avoir tendance, sur le pont surlequel il se bloque, de converger vers les contour verticaux, au lien d'essayer de trouver le contour horizental dans la concavite.

----------


## pseudocode

> mon probleme, c'est qu'une fois la forme trouvee:
> les pixels vont avoir tendance, sur le pont surlequel il se bloque, de converger vers les contour verticaux, au lien d'essayer de trouver le contour horizental dans la concavite.


Justement, en convergeant vers les parois verticales, le snake s'enfonce progressivement. Il faut juste s'assurer qu'il y ait toujours des noeuds sur le "pont" entre les deux parois.

----------


## MSN9149

il y a toujours assez de points sur "le pont", mais comme je te l'ai dit ils sont attires par les parois horizontales qui sont au meme niveau qu'eux
ce qui fait qu'ils n'essayent pas de descendre.

c'est bizarre puisque: en l'initialisant a i'interieur de la forme, il detecte parfaitement les concavitees.

j'ai augmente le nombre d'iterations du calcul du gvf, ca se bloque toujours au meme endroit.

----------


## pseudocode

> il y a toujours assez de points sur "le pont", mais comme je te l'ai dit ils sont attires par les parois horizontales qui sont au meme niveau qu'eux
> ce qui fait qu'ils n'essayent pas de descendre.


Ah, ok. Dans mon cas aussi les noeuds se dplacent horizontalement  cet endroit.

Mais  cause de l'interpolation linaire, tes noeuds sur le pont sont exactement  la mme hauteur que ceux sur les parois : ils se dplacent horizontalement et finissent par se confondent avec les noeuds des parois.

Avec une interpolation cubique, les noeuds sur le pont sont plus bas que ceux des parois : ils se dplacent horizontalement mais arrivent un peu en dessous des noeuds des parois.

----------


## MSN9149

j'espere que t'as raison  ::roll:: 
donc je suis dans l'obligation d'implementer cette interpolation cubique.
dans ce cas la j'ai besoin de ton aide.
sachant que j'ai deja implemente l'interpolation lineaire, rassure moi je dois pas tout refaire a zero?

ps: a propos de l'interpolation cubique, j'ai deja vu les lois sur ta contribution mais je comprend pas ce que c'est, a part que ca donne des contour plus courbe, que ceux obtenus par interpolation lineaire

----------


## pseudocode

> j'espere que t'as raison 
> donc je suis dans l'obligation d'implementer cette interpolation cubique.
> dans ce cas la j'ai besoin de ton aide.
> sachant que j'ai deja implemente l'interpolation lineaire, rassure moi je dois pas tout refaire a zero?


Pour l'interpolation linaire, on a besoin de 2 noeuds conscutifs P[k] P[k+1] et de la position relative entre les deux noeuds ("t" variant entre 0 et 1)

P(t) = flinear(t,P[k],P[k+1]) = P[k] + t*(P[k+1]-P[k])

Pour l'interpolation cubique, on a besoin de 4 noeuds conscutifs : le noeud avant P[k] (P[k-1]) et le noeud apres P[k+1] (P[k+2]). Et toujours notre paramtre de position relative entre P[k] P[k+1], "t" variant entre 0 et 1.

P(t) = fspline(t,P[k-1],P[k],P[k+1],P[k+2])

La formule est un peu plus complique (cf le code ds rebuild(), ou alors les formules de wikipedia), mais le principe est le mme.




> ps: a propos de l'interpolation cubique, j'ai deja vu les lois sur ta contribution mais je comprend pas ce que c'est, a part que ca donne des contour plus courbe, que ceux obtenus par interpolation lineaire


Comme tu le dis, ca donne des contour plus courbes. C'est tout.

----------


## MSN9149

apres avoir lu ta contribution(parce que j'avais implemente l'interpolation lineaire a ma maniere), j'ai compris que je pourrais pomper sur mon implementation de l'interpolation lineaire pour implementer l'interpolation cubique.
mais il y a une ligne que je ne comprends pas:
double t =  (dist-clength[i])/(clength[i+1]-clength[i]);

si tu m'expliquais ce que represente le "t" concretement, peut etre je pourrais le definir d'une autre maniere selon mes donnees? meme le "dist" j'ai pas vraiment compris ce qu'il represente..

le reste c'est de l'application numerique normalement.

merci pour ton aide

----------


## pseudocode

> apres avoir lu ta contribution(parce que j'avais implemente l'interpolation lineaire a ma maniere), j'ai compris que je pourrais pomper sur mon implementation de l'interpolation lineaire pour implementer l'interpolation cubique.
> mais il y a une ligne que je ne comprends pas:
> double t =  (dist-clength[i])/(clength[i+1]-clength[i]);
> 
> si tu m'expliquais ce que represente le "t" concretement, peut etre je pourrais le definir d'une autre maniere selon mes donnees? meme le "dist" j'ai pas vraiment compris ce qu'il represente..


"t" c'est la position relative du "nouveau" noeud Q par rapport aux 2 "anciens" noeuds P[k] et P[k+1]. Cette position "t" varie entre 0 et 1.

t=0 --> Q = P[k]
t=1 --> Q = P[k+1]
0<t<1 --> Q est entre P[k] et P[k+1]

Cela reste vrai quel que soit le type d'interpolation (linaire, cubique, ...).

----------


## MSN9149

> avec un peu de mathmatique :
> Q = w1*P1 + w2*P2 = (1-w2)*P1 + w2*P2 = w2*(P2-P1) + P1


dans l'interpolation lineaire le t = w2, representais la distance entre le point P2 et le point Qi cree par interpolation lineaire.
mais dans le cas de l'interpolation cubique, j'arrive pas a cerner la signification concrete de t.

ca serait pas ("t") le quotient  de la distance de Qi a P[i-1] sur la distance entre P[i] et P[i-1]?

merci

----------


## pseudocode

> ca serait pas ("t") le quotient  de la distance par rapport au point p[i-1] sur la distance entre p[i] et p[i-1]?


oui, c'est exactement cela.  ::ccool:: 
  P[k]         Q           P[k+1]
---|-----------|------------|------>   
   
 t |------------------------| 
   0                        1

----------


## MSN9149

merci beaucoup pour ton aide, je viens d'implementer l'interpolation lineaire,
resultat ca donne une courbe bien courbe des la premiere iteration.
mais sur mon image(celle contenant des concavites), ca converge toujours pas.

du coup je pense que c'est pas a cause de l'interpolation que ca converge pas,
peut etre que j'applique mal les champs de Gvf.

Ps: d'apres les tests que j'ai fait: j'ai remarque que l'interpolation cubique n'est pas une operation a faire a chaque iteration, sinon(dans mon cas), le snake va se retracter jusqu'a disparaitre. c'est normal?

----------


## pseudocode

> Ps: d'apres les tests que j'ai fait: j'ai remarque que l'interpolation cubique n'est pas une operation a faire a chaque iteration, sinon(dans mon cas), le snake va se retracter jusqu'a disparaitre. c'est normal?


C'est ce que j'observe galement. Si on fait le recalcule a chaque itration, on change l'emplacement de tous les noeuds et l'algo ne converge plus.

----------


## MSN9149

si je comrpends bien tu utilise une carte des distances.
mais comment ca se calcule?
j'ai pas compris la loi que t'as mis sur ta contribution. pourquoi il y a deux noeuds? le premier c'est le point actuel mais le deuxieme c'est quoi?

merci

----------


## pseudocode

> si je comrpends bien tu utilise une carte des distances.
> mais comment ca se calcule?


Il y a une contribution qui permet de calculer la carte des distances. Il y a galement, quelque part dans la discussion sur le Snake, un exemple de calcul du GVF.




> j'ai pas compris la loi que t'as mis sur ta contribution. pourquoi il y a deux noeuds? le premier c'est le point actuel mais le deuxieme c'est quoi?


Loi ? deux noeuds ?  ::koi::  ?

----------


## MSN9149

t'as deux points en parametres de la fonction qui calcule la distance, le premier ca doit surement etre le point surlequel on calcule notre carte des distances,
mais le deuxieme j'arrive pas a comprendre ce que c'est?

----------


## pseudocode

> t'as deux points en parametres de la fonction qui calcule la distance, le premier ca doit surement etre le point surlequel on calcule notre carte des distances,
> mais le deuxieme j'arrive pas a comprendre ce que c'est?


 ::koi::  

Tu peux citer la ligne de code en question ? Je ne vois absolument pas de quelle paramtres et de quelle fonction tu parles.

----------


## MSN9149

dans les fonctions intertia et flow.

----------


## pseudocode

> dans les fonctions intertia et flow.


Ah. Et bien le premier point est la position actuelle du noeud, et le deuxime est la position o l'on souhaite dplacer le noeud ( = un des 8 voisins ).

----------


## MSN9149

Merci de ta reponse!
si c'est de cette maniere que tu converge dans les concavitees, alors
comment je pourrais adapter mon gvf snake(selon ta methode) pour pouvoir converger aussi?

parce que moi j'utilise la norme du gvf directement comme energie externe, et l'algorithme greedy de Williams et Shah qui consiste juste a choisir le point voisin qui le plus petite total d'energie.

----------


## pseudocode

> Merci de ta reponse!
> si c'est de cette maniere que tu converge dans les concavitees, alors
> comment je pourrais adapter mon gvf snake(selon ta methode) pour pouvoir converger aussi?
> 
> parce que moi j'utilise la norme du gvf directement comme energie externe, et l'algorithme greedy de Williams et Shah qui consiste juste a choisir le point voisin qui le plus petite total d'energie.


Moi aussi, c'est la mthode que j'utilise.  ::D:

----------


## MSN9149

pourquoi ton programme converge dans les zones concaves et pas le mien alors?
je vais commencer a etre jalou  ::?: 

ps: dans l'algorithme de greedy que j'utilise, on commence par collecter toutes les energies du voisinage, les normaliser, puis on se deplace vers la plus petite.

----------


## pseudocode

> pourquoi ton programme converge dans les zones concaves et pas le mien alors?
> je vais commencer a etre jalou 
> 
> ps: dans l'algorithme de greedy que j'utilise, on commence par collecter toutes les energies du voisinage, les normaliser, puis on se deplace vers la plus petite.


Je te l'ai dit. Si le mien converge c'est parce que je recalcule la position des points du snake avec une spline cubique, et donc ca me place a chaque fois un noeud "plus bas" dans la concavit.

Mais c'est vraiment un coup de chance que ca ne reste pas bloqu.  ::aie::

----------


## MSN9149

et moi je t'ai deja dit, que j'avais implemente les interpolation cubiques, comme tu me l'as montre, mais ca converge toujours pas.  ::aie:: 

peut etre que dans mon cas , le recalcul de la courbe par interpolation cubique, placait ce meme point plus haut dans la concavitee, ... mais ca serait du a quoi d'apres toi?

----------


## pseudocode

> et moi je t'ai deja dit, que j'avais implemente les interpolation cubiques, comme tu me l'as montre, mais ca converge toujours pas. 
> 
> peut etre que dans mon cas , le recalcul de la courbe par interpolation cubique, placait ce meme point plus haut dans la concavitee, ... mais ca serait du a quoi d'apres toi?


Aucune ide. Je pense que ca converge chez moi par "chance".

L'approche 'Greedy' point-par-point n'est pas vraiment adapte pour converger dans ce genre de cas, car on tombe vite sur des solutions qui sont des minimums locaux.

----------


## MSN9149

> L'approche 'Greedy' point-par-point n'est pas vraiment adapte pour converger dans ce genre de cas, car on tombe vite sur des solutions qui sont des minimums locaux.


donc Xu et Prince (ceux qui ont cree le gvf), on du utiliser un autre algorithme que le greedy pour converger dans les zones concaves.

----------


## pseudocode

> donc Xu et Prince (ceux qui ont cree le gvf), on du utiliser un autre algorithme que le greedy pour converger dans les zones concaves.


Je ne sais pas. Mais ca me semble curieux qu'un schma explicite puisse converger a coup sr dans des concavits trs marques.

----------


## MSN9149

peut etre, mais le gvf snake de Xu n'utilise pas un schema implicite(level sets & co), pourtant il converge dans les concavitees.

----------


## pseudocode

> peut etre, mais le gvf snake de Xu n'utilise pas un schema implicite(level sets & co), pourtant il converge dans les concavitees.


Ah, oui, c'est vrai qu'on parle du GVF. J'tais rest sur mon implmentation avec la carte des distances...  ::aie:: 

C'est vrai qu'avec un GVF on ne devrait pas avoir une force purement horizontale dans la cavit. La force devrait tre oriente vers le fond de la cavit, et donc les points du snake devraient converger sans erreurs. Peut-tre un problme dans ton calcule du GVF (pas assez d'itrations, ou alors une perte de prcision) ?

----------


## MSN9149

je crois pas que ca soit le nombre d'iteration parce que je l'ai teste avec plus d'iteration, des fois il se fige meme.

pour la perte de precision, je crois aussi que c'est ce qu'il faut corriger, parce que une fois en debuguant j'ai vu les valeurs du voisinage et il y avait une des valeurs qui etait egale a #nan pourtant j'utilise des matrices a scalaires de 64 bits.

peut etre une division par zero ou quelque chose du genre?

----------


## pseudocode

> je crois pas que ca soit le nombre d'iteration parce que je l'ai teste avec plus d'iteration, des fois il se fige meme.
> 
> pour la perte de precision, je crois aussi que c'est ce qu'il faut corriger, parce que une fois en debuguant j'ai vu les valeurs du voisinage et il y avait une des valeurs qui etait egale a #nan pourtant j'utilise des matrices a scalaires de 64 bits.
> 
> peut etre une division par zero ou quelque chose du genre?


Je ne vois pas trop o il pourrait y avoir une division par zro  ::koi:: 

A la rigueur on pourrait avoir une norme de gradient trs faible, mais ce me semble improbable.



```

```

----------


## MSN9149

a premier vue ta fonction gvf c'est la meme que la mienne.
la question a se poser maintenant est est ce que tu arrive a converger avec cette norme comme fonction externe sur l'image concave precedante?

----------


## pseudocode

> a premier vue ta fonction gvf c'est la meme que la mienne.
> la question a se poser maintenant est est ce que tu arrive a converger avec cette norme comme fonction externe sur l'image concave precedante?


Bah, j'arrive dj a converger en utilisant une simple carte de distance. Alors oui.  ::D:

----------


## MSN9149

et tu utilise la norme du gvf comme energie externe couplee a une energie de courbure c'est ca? leurs coefficient c'est combien deja?

peut etre que c'est parce que j'utilise le filtre de Sobel sur x et sur y pour calculer le edge map? alors que toi tu utilise un simple gradient.

Au fait mu et le nombre d'iteration dans le calcul du gvf, ils sont egaux a quoi?

----------


## pseudocode

> et tu utilise la norme du gvf comme energie externe couplee a une energie de courbure c'est ca? leurs coefficient c'est combien deja?


oui c'est ca. J'ai mis le meme coef sur les deux energies.




> peut etre que c'est parce que j'utilise le filtre de Sobel sur x et sur y pour calculer le edge map? alors que toi tu utilise un simple gradient.


Non, je ne pense pas que ca change grand chose. 




> Au fait mu et le nombre d'iteration dans le calcul du gvf, ils sont egaux a quoi?


J'ai test avec mu=0.1 et 0.2 (cf le papier de Xu et Prince). Ca marche dans les deux cas. J'ai mis un critre d'arrt automatique pour les itrations (lorsque la variation max est plus petite que 1E-4), ca me donne environ 1000 itrations.

----------


## MSN9149

chez moi a 1000 iterations mon programme se bloque  ::aie::  (mu = 0.2).



> J'ai mis un critre d'arrt automatique pour les itrations (lorsque la variation max est plus petite que 1E-4), ca me donne environ 1000 itrations.


tu peux m'en dire un peu plus sur la manier avec laquelle t'as fait ca, par ce que sur le programme que tu m'as donne, le nombre d'iterations est fixe.

la variation c'est quoi au juste le u ou bien le v ou la norme des deux?

----------


## pseudocode

> chez moi a 1000 iterations mon programme se bloque  (mu = 0.2).
> 
> tu peux m'en dire un peu plus sur la manier avec laquelle t'as fait ca, par ce que sur le programme que tu m'as donne, le nombre d'iterations est fixe.
> 
> la variation c'est quoi au juste le u ou bien le v ou la norme des deux?


J'ai pris la norme de la "variation", c'est a dire le terme qu'on ajoute  "u" et  "v". Mais c'est juste un truc empirique. Sur plusieurs images de test, je tombe toujours autour des 1000 itrations.

----------


## MSN9149

mais la variation maximale c'est dans le voisinage ou bien dans toute la carte des champs de gvf?

----------


## pseudocode

> mais la variation maximale c'est dans le voisinage ou bien dans toute la carte des champs de gvf?


Moi j'ai pris la variation maximale sur toute la carte. Mais bon, tu peux mettre un nombre d'itration fixe. L'important c'est d'avoir suffisamment d'itrations pour que le gradient se soit propag sur la carte du gvf, et que la norme du gvf ressemble en gros  l'image que j'ai poste (a gauche).



Edit: tiens, je viens de me rendre compte que j'ai oubli de diviser par 2 ma diffrenciation lors de l'initialisation de la edge-map.  ::P: 


```

```

----------


## MSN9149

D'accord.
mais j'ai une question idiote  ::roll:: 
comment tu fait pour afficher le gvf en vert et rouge?  :8O: 

question plus technique, donc d'apres ton test sur la variation maximale,
plus le nombre d'iteration augmente, plus la norme du gvf diminue?

----------


## pseudocode

> D'accord.
> mais j'ai une question idiote 
> comment tu fait pour afficher le gvf en vert et rouge?


le vert c'est les pixels ou la norme du gradient est suprieur au seuil (paramtrable) = ce sont les points "source" du gvf.

Le rouge c'est la norme du gvf, normalise pour etre entre 0 et 255 ce qui est plus pratique pour afficher des couleurs.

(Note, en fait c'est l'inverse de la norme sur mon dessin, vu que je me suis tromp en l'affichant. Ca devrait tre rouge prs de la source du gradient, et noir en s'loignant   ::P: .)




> question plus technique, donc d'apres ton test sur la variation maximale,
> plus le nombre d'iteration augmente, plus la norme du gvf diminue?


Oui. A cause des lissages successifs la norme globale du flux  tendance  diminuer.

----------


## MSN9149

Bonjour
dis tu peux pas me filer le code que t'as utiliser directement pour ibtenir l'image verte et rouge du gvf?. ca sera plus facile pour moi pour trouver les erreurs dans mon code qui ne font que j obtienne pas une bonne detection des concavites

----------


## pseudocode

> Bonjour
> dis tu peux pas me filer le code que t'as utiliser directement pour ibtenir l'image verte et rouge du gvf?. ca sera plus facile pour moi pour trouver les erreurs dans mon code qui ne font que j obtienne pas une bonne detection des concavites


Heu non. J'utilise mes propres librairies pour dessiner/afficher des images, et ce n'est pas publiable (ni utilisable) en l'tat.

Par contre, je peux te donner la mthode complete du calcul du gvf pour cet exemple. Je l'ai un peu remis au propre. 



```

```

----------


## MSN9149

je comprends pas deux trucs dans ton code:
1) la division par 4*255*1.4142,  dans le filtrage par sobel.

2) le seuillage du edge map alors que moi j ai trouve dans le programme de Xu et Prince une normalisation du edge map (f-fmin/fmax-fmin).

----------


## pseudocode

> je comprends pas deux trucs dans ton code:
> 1) la division par 4*255*1.4142,  dans le filtrage par sobel.


- on divise pas 4 car c'est la somme des coefficients du noyau de Sobel (1,2,1)

- on divise par 255 car l'intensit est entre 0 et 255, et qu'on la veut entre 0 et 1

- on divise par racine(2) car la norme du vecteur (fx,fy) doit tre entre 0 et 1. Et sans cela, la norme maximale serait racine(1+1).




> 2) le seuillage du edge map alors que moi j ai trouve dans le programme de Xu et Prince une normalisation du edge map (f-fmin/fmax-fmin).


Ca c'est mon implmentation perso. Le seuillage est l pour supprimer les petits bruits parasites. Cela dit, sur une image binaire, il n'y a pas de bruit.

----------


## MSN9149

bon moi dans mon implementation la normalisation du gradient de sobel je la fait suivant la loi: f-fmin/fmax-fmin, ca me donne comme dans ton cas, un f dans [0, 1].
mais j'ai pas diviser le masque de Sobel par 4, tu pense que c'est du a ca?

----------


## pseudocode

> bon moi dans mon implementation la normalisation du gradient de sobel je la fait suivant la loi: f-fmin/fmax-fmin, ca me donne comme dans ton cas, un f dans [0, 1].
> mais j'ai pas diviser le masque de Sobel par 4, tu pense que c'est du a ca?


Si tu renormalises le gradient de cette facon, tu n'as pas besoin de diviser par 4, 255, ou quoi que ce soit. 

Attention cependant a normaliser le vecteur (en utilisant racine(fx + fy)), et pas normaliser sparment chaque composante fx puis fy.

----------


## MSN9149

bon voici les etapes que j'ai suivi:
1) je calcule le edge map f = 1- Image/255.
2)je fais la normalisation de f (f = f-fmin/fmax-fmin)
3)je calcule le gradient de f (filtre de sobel) soient(fx,fy) et la magnitude au carre (fx^2+fy^2)

et j'entre dans la boucle en utilisant ces paramtres

ps: c'est la methode qu'ont utilise Xu et Prince dans leur programme matlab.

----------


## pseudocode

> bon voici les etapes que j'ai suivi:
> 1) je calcule le edge map f = 1- Image/255.
> 2)je fais la normalisation de f (f = f-fmin/fmax-fmin)
> 3)je calcule le gradient de f (filtre de sobel) soient(fx,fy) et la magnitude au carre (fx^2+fy^2)
> 
> et j'entre dans la boucle en utilisant ces paramtres
> 
> ps: c'est la methode qu'ont utilise Xu et Prince dans leur programme matlab.


Ah, "f" c'est l'intensit de l'image. Je croyais que c'tait le vecteur gradient.

Dans ce cas, il te faut une 4eme tape pour normaliser le gradient. Il faut absolument que (fx^2+fy^2) soit infrieur ou gal  1, sinon ca risque de diverger.

Si tu as correctement appliqu le filtre de sobel, les valeurs de fx (et fy) varient entre -1 et 1. Ce qui fait que (fx^2+fy^2) varie entre 0 et 2. Il te faut donc diviser fx (et fy) par racine(2).

----------


## MSN9149

donc si je comprends bien, il me suffit juste de diviser (fx^2+fy^2) par 2 directement, si le filtre de Sobel est deja normalise (fx et fy dans [-1,1])

----------


## pseudocode

> donc si je comprends bien, il me suffit juste de diviser (fx^2+fy^2) par 2 directement, si le filtre de Sobel est deja normalise (fx et fy dans [-1,1])


Il faut galement diviser fx (et fy) par racine(2).

Il ne faut pas juste diviser la norme mais aussi chacune des 2 composantes, car les composantes interviennent dans le calcul du gvf.

----------


## MSN9149

bonjour 
j'ai toujours le meme probleme; j'ai fais ce que tu m'as dit (i.e division des composantes du gradient fx et fy par racine de 2), et j'ai toujours le meme probleme pendant la convergence de regions concaves.

----------


## pseudocode

> bonjour 
> j'ai toujours le meme probleme; j'ai fais ce que tu m'as dit (i.e division des composantes du gradient fx et fy par racine de 2), et j'ai toujours le meme probleme pendant la convergence de regions concaves.


Vrifie que la norme (fx^2+fy^2) est bien toujours infrieur  1.

----------


## MSN9149

j'avais oublie de diviser par 4 les deux filtres de sobel et le laplacien,
donc maintenant lorsque j'essaye d'afficher la norme du gvf, j'obtiens une image assez ressemblante a la tienne.

Mais j'ai affiche les valeurs des fx et fy (les reponses par sobel), les valeurs ne sont pas vraiment entre 0 et 1..
je dois peut etre les normaliser moi meme, non?

merci pour tes conseils

----------


## pseudocode

> Mais j'ai affiche les valeurs des fx et fy (les reponses par sobel), les valeurs ne sont pas vraiment entre 0 et 1..
> je dois peut etre les normaliser moi meme, non?


Pourtant, elles devraient l'tre. Si l'image de dpart a des valeurs entre 0 et 1, le rsultat du filtre de Sobel est entre -1 et +1.

----------


## MSN9149

> Si l'image de dpart a des valeurs entre 0 et 1, le rsultat du filtre de Sobel est entre -1 et +1.


oui! justement, je voulais juste te dire te dire qu'on a pas utiliser la meme methode pour calculer le gradient du edge map. Moi je me suis base sur le programme original, dans lequel on normalise f = 1 - image/255, la normalisation se fait par f = (f - fmax) / (fmax - fmin)

----------


## MSN9149

c'est bon.
j'ai obtenu fx et fy bornes entre 0 et 1.
et (fx^2+fy^2) est inferieur a 1 meme sans avoir diviser fx et fy par racine(2).

u, v et la norme (u^2 + v^2) sont aussi compris entre 0 et 1, pourtant je n'obtiens pas une bonne convergence dans les zones concaves, meme au bout de 1000 iterations dans le calcul du gvf.

voici l'image que j'ai obtenu (norme du gvf au bout de 1000 iterations):
.

biensur a 5000 iterations par exemple j'obtiens un champs de gvf plus large.

----------


## pseudocode

> c'est bon.
> j'ai obtenu fx et fy bornes entre 0 et 1.
> et (fx^2+fy^2) est inferieur a 1 meme sans avoir diviser fx et fy par racine(2).
> 
> u, v et la norme (u^2 + v^2) sont aussi compris entre 0 et 1, pourtant je n'obtiens pas une bonne convergence dans les zones concaves, meme au bout de 1000 iterations dans le calcul du gvf..


Bon dj, un GVF correct, c'est un bon dbut.  ::ccool:: 

Maintenant, pour la convergence dans les zones concaves, il faut sans doute travailler sur l'algo du snake. La mthode explicite, consistant a dplacer chaque noeud indpendamment les uns des autres, converge souvent vers un minimum local. C'est sans doute ce qui se passe pour les zones trop concaves.

J'ai bien peur qu'il faille passer par une autre mthode de convergence.

----------


## MSN9149

tu veux dire que si je veux une convergence dans les zones concaves, il faut peut etre utiliser un autre algorithme a la place de l'algorithme greedy.
je crois que t'as raison puisque sur le programme gvf de Xu et Prince, ils n'ont pas utilise cet algorithme.

mais toi tu es quand meme arrive a converger avec cet algorithme (greedy) non?

sinon qu'est ce que je dois utiliser a sa place?

deuxieme question, bon pour normaliser les filtres laplacien et filtres de sobel on les divise par 4, celui de roberts par 2, mais par quoi on doit deviser celui de prewitt?

----------


## pseudocode

> tu veux dire que si je veux une convergence dans les zones concaves, il faut peut etre utiliser un autre algorithme a la place de l'algorithme greedy.
> je crois que t'as raison puisque sur le programme gvf de Xu et Prince, ils n'ont pas utilise cet algorithme.
> 
> mais toi tu es quand meme arrive a converger avec cet algorithme (greedy) non?


Oui, mais c'est sans doute de la chance. Mon algo ressemble  du recuit-simul, ce qui permet de temporairement lever les contraintes d'nergies internes durant l'exploreration.




> sinon qu'est ce que je dois utiliser a sa place?


Il y a des schma semi-implicites, dans lesquels on calcule l'nergie externe de manire explicite (au temps t) et l'nergie interne de manire implicite (au temps t+1). 

cf. "Snakes: Active contour models", by Kass ,Witkin and Terzopoulos, 1988. 

Je conseille aussi la lecture de la thse de J.Ivins




> deuxieme question, bon pour normaliser les filtres laplacien et filtres de sobel on les divise par 4, celui de roberts par 2, mais par quoi on doit deviser celui de prewitt?


on fait la somme des coefs positifs filtre (Sp), la somme des coefs ngatifs du filtre (Sn), et on prend la plus grande des deux en valeur absolue ( coef_normalization = max(|Sp|,|Sn|) ).

----------


## MSN9149

> on fait la somme des coefs positifs filtre (Sp), la somme des coefs ngatifs du filtre (Sn), et on prend la plus grande des deux en valeur absolue ( coef_normalization = max(|Sp|,|Sn|) ).


1)Alors dans le filtre de roberts on les divise par 1, et le filtre de prewitt on le divise par 3, mais pourquoi la norme par laquelle on divise se calcule de cette maniere?

2)En parlant de schema implicite, la convergence dans les zones concaves est parfaite avec un algorithme level set, mais le temps de calcul est tres important.
par schema implicite tu voulais viser les level set?

3)je vais jeter un coup d oeil a cette these meme si pour le moment le lien que tu m'as donne ne marche pas!

merci pour ton aide

----------


## pseudocode

> 1)Alors dans le filtre de roberts on les divise par 1, et le filtre de prewitt on le divise par 3, mais pourquoi la norme par laquelle on divise se calcule de cette maniere?


C'est simplement un moyen simple d'avoir un rsultat dans [-1,+1] lorsque l'entre est dans [0,1].

Comme c'est un filtre linaire, le rsultat le plus grand possible c'est lorsque tous les coefs positifs sont associ  '1' et les coefs ngatifs  '0'. Et rciproquement pour le rsultat le plus petit.




> 2)En parlant de schema implicite, la convergence dans les zones concaves est parfaite avec un algorithme level set, mais le temps de calcul est tres important.
> par schema implicite tu voulais viser les level set?


Non. 

- Pour simplifier, le schma explicite c'est lorsqu'on calcule les positions futures uniquement a partir des positions actuelles.

Un+1 = Un + Fonction(Un)

(c'est la mthode que j'ai utilise : la position future d'un noeud du Snake dpend uniquement des positions actuelles des noeuds).


- Un schema implicite, c'est lorsqu'on a besoin des positions actuelles et futures dans le calcul.

Un+1 = Un + Fonction(Un,Un+1)


- Un schema semi-implicite, c'est lorsqu'on a besoin sparment des positions futures et des positions actuelles dans le calcul.

Un+1 = Un + Fonction1(Un) + Fonction2(Un+1)




> 3)je vais jeter un coup d oeil a cette these meme si pour le moment le lien que tu m'as donne ne marche pas!


Exact. Pourtant ca fonctionnait ce matin.

----------


## MSN9149

moi aussi mon algorithme greedy, c'est un schema explicite puisque la position futur de chaque noeud est calculee a partir de la position actuelle, en deplacant le noeud dans le voisinage de la position actuelle.

par contre le recuit simule je crois pas que je l'ai utilise parce que je sais meme pas ce que c'est  ::aie:: .

----------


## pseudocode

> par contre le recuit simule je crois pas que je l'ai utilise parce que je sais meme pas ce que c'est .


Ca n'a pas de rapport direct avec les Snakes. C'tait juste une analogie pour tenter d'expliquer pourquoi le hasard fait que ca converge parfois dans mon cas.

----------

