Detection de contours par approximation locale par splines

Philippe Chose


Le but de ce projet est d'effectuer une détection de contour en recherchant ces contours sur une image construite par approximation splines. Cette approximation consiste à remplacer localement l'image par le produit (en x et en y) de deux polynômes. Cette approximation est décrite dans la partie I. On effectue ensuite une recherche de contour
en calculant le lieu de maximums du gradient dans la direction du gradient, ce qui peut être effectuer aisement puisque l'on dispose d'une fonction f(x,y) représentant l'image; ceci sera decrit dans la partie II. La partie III présentera les résultats obtenus.

I Interpolation spline

Le principe de l'interpolation spline est de remplacer l'image fi,j localement par deux polynômes du troisième degré dans notre cas. Ces deux polynômes p1(x) et p2(y) sont choisis de telle sorte que F(x,y)=p1(x)p2(y) corresponde bien à la luminosité de l'image (noir et blanc) pour toutes les coordonnées (x,y) entières, c'est à dire que F(x,y) =  fi,j pour tout x,y entiers. L'intérêt de cette interpolation est que l'on dispose alors d'une fonction continue F(x,y) pour représenter l'image avec l'assurance que f(x,y) coincide bien avec l'image aux points de coordonnées entières. On peut alors calculer facilement des gradients et autres laplaciens en dérivant simplement cette fonction. Cette interpolation permet aussi de changer facilement la taille d'une image.

L'interpolation spline choisie pour ce projet est la suivante (i = E(x) et j =E(y), parties entières)

    F(x,y) = Hj-1(x)C3(y-j)+Hj(x)C2(y-j)+Hj+1(x)C1(y-j)+Hj+2(x)C0(y-j)

où
    Hj(x) =  fi-1,jC3(x-i)+fi,jC2(x-i)+fi+1,jC1(x-i)+fi+2,jC0(x-i)
et
   C0(t) = -at3+at2
    C1(t) = -(a+2)t3+(2a+3)t2-at
    C2(t) = (a+2)t3-(a+3)t2+1
    C3(t) = at3-2at2+at
avec -1<a<0.

On verifie bien que F(x,y) =  fi,j lorsque x et y sont entiers.

II Détection des contours

Ayant maintenant à notre diposition une fonction continue F(x,y) représentant l'image, on peut detecter les contours en cherchant les maximums du gradient dans la direction du gradient, en recherchant les zeros de la fonction:

    D(x,y) = (gt . H .g) / (gt . g)

avec g le gradient et H la matrice des derivées secondes.

Les différentes derivées de F(x,y) sont aisement calculées analytiquement puisque ce sont des combinaisons linéaires des derivées des polynômes C présentés au paragraphe précedent. Dès lors que l'on dispose de cette fonction D(x,y), on peut en rechercher les zéros et marquer ces points comme faisant partie des contours. Un seuillage sur les valeurs trop faibles de D(x,y) est effectué pour supprimer du bruit.

III Implémentation et résultats

L'algorithme a été implémenté en C++ et peut être consulté en suivant ce lien. Il enchaîne un filtrage de l'image pour éliminer un peu le bruit (moyenne uniforme 3x3), puis une interpolation par spline et une recherche de zéros. Deux paramètres peuvent être controlés: il s'agit du coefficient a de l'interpolation par splines et du seuil que l'on utilise pour éliminer les trop petites valeurs de la fonction D(x,y). Tous les exemples ont été calculés avec les valeurs -0.5 pour a et 0.08 pour le seuil. Ce programme a été testé sur une série d'images synthétisés comportant des contours simples et contrastés et s'est correctement comporté sur ces images. Voici les résultats obtenus sur des images "réeles":
 
 

Image originale

 

On observe que la plupart des contours sont detectés, mais que lorsque le contraste au niveau du contour est faible, rien n'est detecté, notamment pour le couloir partant sur la gauche au premier plan. Les dalles sont elles bien detectées mais de facon peu precise. Notons que la détection des contours est effectuée sur une grille deux fois plus précise que l'image originale d'ou la différence de taille entre les deux images. Il en sera de même pour tous les autres exemples. On remarque aussi que les gradients de luminosité sur les surfaces
planes ne sont pas detectés comme étant des contours ce qui est plutôt un bon point pour cette méthode.
 

Image originale

 

Pour cette image où les zones delimitées par les contours sont assez homogènes avec des textures assez simples, l'algorithme ne se debrouille pas trop mal. De nombreux contours sont detectés. Mais bizarrement des contours qui auraient pu sembler évidents à detecter comme celui du fruit sombre au milieu de la corbeille, ne le sont pas. Les contours dans la texture du panier sont detectés mais pas de facon precise: il aurait peut être fallut effectuer la recherche de contours sur une grille encore plus fine.
 

Image originale

 

Ici, les contours tres marqués sont les contours rectilignes des bassins: ceux-ci sont bien detectés. Les contours rectilignes du bâtiment sont
eux aussi reconnus de même que les grandes dalles blanches situées au centre. Il ne faut pas trop s'inquiéter en ce qui concerne les arbres ou la pelouse: un filtrage mieux adapté en entrée aurait sûrement permis d'éliminer ces faux contours.
 
 

Image originale

 

Sur cette derniere image, la détection du visage et des mains peut être considerée comme tout à fait convainquante bien que peu precise.
On retrouve quelques contours dans les cheveux mais ceux-ci ne sont que de pietre qualite

IV Conclusion

La détection de contour au moyen d'une interpolation de l'image par splines est une methode permettant d'obtenir des contours d'assez bonne qualite. Un de ces avantages est de pouvoir effectuer cette détection avec une précision arbitraire en effectuant la recherche des contours sur une image sur-échantillonnée, ceci en interpolant au moyen de splines. Des prétraitements devraient pouvoir améliorer grandement la qualité des résultats obtenus.

Bibliographie

[1] Le traitement de images, Henri Maître, Cours de l'ENST.
[2] Curves and Surfaces for Computer Aided Geometric Design, Gerald Farin, Academic Press.
[3] Efficient image magnification by bicubic spline interpolation, Michael J. Aramini, http://www.ultranet.com/~aramini/design.html