• Julien Cohen-Bengio
• Claude-Alexis Gras

Introduction

Conclusion

Références

Introduction

    L'algorithme de la corde mince permet  de segmenter une image. Le nom même de l'algorithme provient du fait qu'il s'agit de tendre une corde le long de contours, ceci avec une certaine tension determinée paramétriquement.

    Il s'agit de coller la corde au plus près du contour, de façon continue, la corde ayant une longueur minimale. Ainsi, pour exprimer ces conditions, il convient de minimiser l'énergie E, somme de :
 
• D qui mesure l'écart quadratique entre la corde et l'image à segmenter,
• S qui estime la déformation de la corde,
• P, terme de pénalité proportionnel à la longueur de la corde.
   

          N                2
D =  /  (u-d)   dx
            0

                2         N       2
S =   Lbd   .  / (u')   dx
                      0

 
P = Alp . L

où

• u est la corde,
• d est l'image,
• Lbd et Alp sont des paramètres de l'algorithme à régler.

2. Resolution et mise en oeuvre

    L'implémentation pratique sur une image impose d'adapter l'algorithme au cas discret. Pour résoudre ce problème de minimisation, nous avons eu recours à deux fonctions hrs  et vrs où rs représente une clique horizontale pour h et verticale pour v ; s'il existe un contour entre r et s, hrs (respectivement vrs) est mis à 1, sinon 0.
 

Par exemple,

 
                                                s4
                                      |
                  ________  | _________
                  |                   |
                  |                   |
                  |                   |
     s3------ r ------- s1
                  |                   |
                  |                   |
                  |                   |
                  |                   |
                                      |
                                    s2
 

En rouge les contours.
 

Dans ce cas, on a :
 
        hrs3 = vrs4 = 1
        hrs1 = vrs2 = 0
 

On choisit  au départ  u = d, et on détermine les hrs et vrs qui minimisent l'énergie totale E. De là, on recalcule u à partir des valeurs hrs et vrs.
 

Dans le cas discret, l'énergie est sous la forme :
 
 

    E =   S ( ui,j - di,j )
                  i,j
                             2                                            2                                                           2
                  +  Lbd . S [ ( ui,j - ui-1,j ) ( 1 - hi,j ) + ( ui,j - ui-1,j ) ( 1 - vi,j ) ]  
                                            i,j
 

                                   + Alp . (  hi,j + vi,j )
 

où  S est le signe somme

    On peut remarquer que le terme :   sqrt( Alp ) / Lbd   est l'ordre de grandeur du pas de résolution, c'est-à-dire du seuil de détection du contour par la corde.
Ainsi, dans les exemples suivants, on fera varier ce rapport.
 

3. Exemples et résultats
 
Nous allons tester cet algorithme sur différentes images, à différents pas.
 
 
 

Les trois images suivantes montrent les résultats pour un pas croissant (lambda décroissant ou alpha croissant). La première image fait apparaître de très petits éléments de corde (correspondant en fait au bruit) : le pas est donc trop faible.
 
 
 
 
Inversement, cette troisième image présente l'effet opposé : les contours ne sont pas fermés par choix d'un pas trop fort (certains contours ne sont pas détectés).
La seconde image semble être le meilleur équilibre.

 
 
 
 
 
 

Les détails fins provenant de la texture des cheveux  amènent des contours parasites dans le résultat.Or si l'on veut les supprimer en prenant un pas très grand, on perd les contours essentiels, l'image étant peu contrastée.

 
Conclusion

Le principe de cet algorithme est intéressant, cependant la simplification qu'a nécessitée l'implémentation de cet algorithme rapproche les résultats d'une détection par simple gradient. Ainsi la condition de continuité est peu ou pas respectée.

Références

Visual Reconstruction, A. Blake et A. Zisserman, The MIT Press, Cambridge 1987.