Détection des ponts

1° Algorithmes pour la détection des arêtes.

La détection des arêtes consiste essentiellement à repérer les changements locaux d’intensité. La dérivée, ou le gradient dans le cas des fonctions à plusieurs dimensions, est tout à fait désignée dans un tel cas. Puisqu’une image est une fonction discrète, des méthodes de différences finies sont utilisées pour le calcul du gradient. Les algorithmes de détection d’arête sont constitués de trois étapes :
   Filtrage : La dérivée est très sensible au bruit ; une image doit donc être filtrée afin de ne pas générer trop de fausses arêtes. Cependant, le filtrage diminue aussi la réponse de l’algorithme pour les arêtes réelles. Il y a donc un compromis entre la diminution du bruit et la conservation des arêtes.
   Mise en valeur : Il s’agit de faire ressortir les arêtes. C’est à cette étape que le gradient est calculé.
   Détection : L’algorithme doit pouvoir déterminer, pour chaque pixel, si le gradient y est suffisamment grand pour être sur une arête.

a. Approche gradient Les points de contour dans une image sont caractérisés par des extrema locaux du gradient. Une première approche consiste donc à : 1. calculer la norme du gradient en tous point de l’image, 2. sélectionner les pixels à l’aide d’un seuil fixé a priori pour la norme du gradient.

Pour la détection des contours, deux quantités reliées au gradient sont importantes, la norme et la direction. Des différentes dérivées discrètes du gradient, on peut ressortir deux masques correspondants aux directions orthogonales :

Gx =

Gy =

Les opérateurs simples sont trop sensibles au bruit. Il existe plusieurs filtres moyenneurs directionnels permettant d’atténuer ce problème, par exemple :

   Opérateur de Prewitt Gx =

Gy =

   Opérateur de Sobel Gx =

Gy =

Cet opérateur est assez populaire et correspond à une convolution de l’image par : [1 2 1] * [-1 0 -1]

b. Approche laplacien Le seuillage des images gradient dans les directions x et y donne des contours assez forts dans ces directions, cependant ils ne sont pas isotropes. Si l’on est sensible à cela, on utilise un opérateur Laplacien qui lui est invariant aux rotations de l’image et permet de faire ressortir des contours dans toutes les directions. Néanmoins, la sensibilité au bruit est accrue par rapport au gradient.

ou

c. Convolution « adaptée » Cette technique basée sur la convolution produit une description des lignes minces dans une image d’entrée. Cet opérateur que nous nommerons détection de lignes permet en adaptant la convolution de détecter les lignes d’une largeur définie dans une certaine orientation :

Horizontales :

Verticales :

Obliques (+45°) :

Obliques (-45°) :

Ces masques sont obtimisés pour la détection de lignes claires sur fond foncé, si l’on cherche à faire ressortir des lignes foncées sur fond clair, il faut inverser les valeurs.

d. La transformée de Hough L’application la plus simple permet de reconnaître les lignes d’une image, mais des modifications peuvent être apportées pour reconnaître n’importe quelle forme : c’est la transformée généralisée de Hough. Le principe de la transformée de Hough est qu’il existe un nombre infini de lignes qui passent par un point, dont la seule différence est l’orientation (l’angle). Le but de la transformée est de déterminer lesquelles de ces lignes passent au plus près du schéma attendu.

Afin de déterminer que deux points se trouvent sur une même ligne potentielle, on doit créer une représentation de la ligne qui permet une comparaison dans ce contexte. Dans la transformée de Hough, chaque ligne est un vecteur de coordonnées paramétriques : ρ : la norme du vecteur θ : l’angle

En transformant toutes lignes possibles qui relient un point à un autre, c’est à dire en calculant la valeur de ρ pour chaque θ, on obtient une sinusoïde unique appelée espace de Hough. Si les courbes associées à deux points se coupent, l’endroit où elles se coupent dans l’espace de Hough correspond aux paramètres d’une droite qui relie ces deux points.

Calcul des coordonnées paramétriques : On utilise pour cela la formulation généralisée d’une droite : ρ = x cos α + y sin α. L’orientation locale φ du contour peut être calculée par : φ = arctg (Gy / Gx) où Gx et Gy sont déterminés par l’application d’un opérateur Gradient (Sobel par exemple). Pour chaque point (x,y) dans l’image, il y a exactement un point (φ,ρ) dans l’espace de Hough. Si on additionne la norme du gradient à ce point, les contours forts sont mieux représentés.