| Dans cet article, Nous décrivons un nouvel algorithme de détection de lignes, qui utilise des opérateurs de détection de contours basés sur la dérivation fonctionnant sans seuillage interne ni aucun autre paramètre (voir plus bas). La version anglaise en a été présentée au Third Workshop on Electronic Control and Measuring Systems, Université Paul Sabatier (Toulouse), les 2-3 juin 1997. La version présentée ici est une traduction française de la version publiée dans les actes (cette dernière faisant foi). | |
PDF version ici | |
| |
Dans cet article, nous décrivons une nouvelle méthode d'extraction de lignes, à base d'opérateurs de dérivation, fonctionnant sans seuillage ni aucun autre paramètre intermédiaire. Cette propriété permet de repousser les décisions de détection vers les phases ultérieures du système d'analyse d'images, et d'y réduire le nombre de paramètres à régler. Cette méthode permet aussi aux lignes de faible contraste d'être détectées, sans augmenter le nombre de fausses alarmes, en raison du fait que les pixels isolés indiqués comme des contours dans les premières phases ne seront pas validés dans la phase suivante de la détection de ligne. Cette méthode est principalement basée sur des filtres de convolution linéaires simples qui devraient permettre un fonctionnement à vitesse élevée lors d'une implémentation matérielle.
Les algorithmes de détection de lignes à base de contour comprennent habituellement les étapes suivantes : lissage, détection de contour, amincissement, chaînage, vectorisation et restauration. Dans notre méthode, la seconde étape (détection de contour) comprend deux dérivations à base des filtres laplacien et gradients [Wang94] pour déterminer les localisation et orientation des pixels de contour. Les trois dernières étapes forment la détection de ligne. Les étapes de lissage et d'amincissement, courantes chez plusieurs auteurs, ne sont pas réalisées directement car elles sont implicites dans les opérateurs de dérivation choisis.
Notre algorithme se décompose en cinq phases : détection de contour, calcul des directions de contour, chaînage, vectorisation et restauration.
Dans cette première phase, les contours minces sont détectés sur les passages à zéro du laplacien calculé par filtre de convolution. Le filtre utilisé est la somme de filtres directionnels en une dimension selon deux ou quatre directions (en utilisant les diagonales dans ce dernier cas). La taille du filtre détermine la bande passante du lissage implicite réalisé lors de la convolution.
Les filtre de White-Rohrer (deux directions, [Whit83]) et Marr-Hildreth (quatre directions, [Hara84]) utilisent respectivement les matrices MWR et MMH (équations 1 et 2).
(1), ![Laplacien 3×3 : [L=(1 -2 1)] L+L'+rot(L,45°)+rot(L',45°)](eq2.gif)
(2)
(3)
(4)
Les figures 1 et 2 sont des lignes extraites d'une zone de l'image où se trouvaient des contours. Avec la même correction, et donc des niveaux de bruit égaux, on voit que la réponse du filtre de Marr-Hildreth est meilleure (les pics correspondant au signal ont une plus grande amplitude).
Les figures 3 et 4 sont des lignes extraites d'une image de contour dans une zone sans contour. La réponse au filtre de White-Rohrer a été corrigée afin d'égaliser les niveaux de bruit (mesurés par l'écart type de la ligne échantillon).
|
|
| figure 1 : laplacien par filtre de White-Rohrer corrigé | figure 2 : laplacien par filtre de Marr-Hildreth |
 écart type mesuré : 7.62 |
 écart type mesuré : 7.59 |
| figure 3 : échantillon de bruit (White-Rohrer corrigé) | figure 4 : échantillon de bruit (Marr-Hildreth) |
Un pixel est marqué comme pixel de contour si la réponse du filtre laplacien présente un passage à zéro dans la direction verticale ou horizontale, c'est à dire si deux pixels voisins dans cette direction ont des signes différents. L'intensité du passage à zéro est la valeur absolue de la différence d'intensité de ces deux pixels ; l'intensité du contour est affectée à la plus haute des intensités du passage à zéro (ligne et/ou colonne). Nous n'utilisons pas de seuil à ce niveau pour éliminer les contours de faible contraste. Le résultat de cette recherche est appelé carte de contours.
Les passages à zéro du laplacien correspondent à des points d'inflexion dans la direction du gradient de la fonction du plan que représente l'image. Cependant, tous les points d'inflexion ne représentent pas nécessairement des contours : par exemple, lorsque le signe de la dérivation du premier ordre est le même que celui de la dérivation du troisième ordre ([Flec92]). Nous allons le montrer par des exemples sur des fonctions de continûment dérivables au voisinage du point considéré.
Un point d'inflexion d'une fonction f(x) sera déclaré contour dans les conditions suivantes.
Dans ces deux cas, les signes d'f' et f''' sont différents. Dans les deux autres cas (figures 5.b et 5.d), le point d'inflexion ne correspond pas à un contour.
|
|
| figure 5.a : f croissant avec un maximum local d'f' | figure 5.b : f croissant avec un minimum local d'f' |
|
|
| figure 5.c : f décroissant avec un minimum local d'f' | figure 5.d : f décroissant avec un maximum local d'f' |
La phase habituelle d'amincissement qui précède le chaînage n'est pas nécessaire ici car la méthode du passage à zéro du laplacien donne des contours fins. Cependant, des pixels de contour voisins dans la direction du gradient peuvent apparaître ([Torr86]) lorsque des contours antiparallèles sont distants d'un pixel, ou lorsqu'un passage à zéro selon la direction horizontale est voisin d'un passage à zéro selon la direction verticale au voisinage d'un coin.
2.2 Calcul des directions de contour
Dans cette seconde phase, l'orientation de chaque contour détecté est déterminée par deux filtres directionnels de gradient (vertical et horizontal), ce qui permet d'estimer les deux composantes du vecteur gradient. Les matrices utilisées et les opérations de dérivations correspondantes sont indiquées équations 5 et 6.
Composante verticale : 
, 
(5),
composante horizontale :
, 
(6)
Ces opérateurs sont assez sensibles au bruit et peu précis en localisation. On peut le voir sur les images des figures 6 et 7 qui représentent les réponses à la détection de contour par ces filtres et par le filtre du laplacien de White-Rohrer.
|
|
| Figure 6 : détection de contour par gradient selon x et y. | Figure 7 : détection de contours par laplacien |
|
| Figure 8 : contour et gradient |
Pour cette raison, ils ne sont pas efficaces pour faire de la détection de contour ; Cependant, il n'est pas nécessaire de connaître la direction de contour avec une grande précision, puisqu'elle ne sert qu'au chaînage selon une connexité à huit voisins. La direction du gradient est donc calculée par ces filtres et mémorisée avec une précision de 3 bits (une direction parmi 8, avec une erreur maximale de 22,5°, Cf. figure 9).
|
| Figure 9 : Répartition des classes de direction |
Dans cette troisième phase, les contours sont chaînés selon leur connexité et la direction de leur gradient. Dans cette étape, un contour est chaîné avec son voisin si la droite portée par ces deux pixels et les directions de leur contour (normale au gradient) ne forment pas un écart supérieur à 45°. Le résultat est un ensemble de chaînes représentant des contours minces (de largeur 1 pixel).
|
|
| Figure 10 : extrait d'une image | Figure 11 : direction et amplitude du gradient dans cet extrait |
La direction du contour sur le pixel est telle qu'elle ne permet comme successeur que l'un des trois pixels bêta, epsilon ou thêta. Le plus proche de ces trois (epsilon) présente un contour dont la direction est telle qu'elle ne permet comme prédécesseur que l'un des trois pixels bêta, alpha ou delta. Le chaînage delta-epsilon est donc compatible avec la direction de chacun des deux contours. D'autre part, les directions de contour des pixels delta et epsilon appartiennent à des classes voisines (respectivement 0 et 7 modulo 8). Nous pouvons alors chaîner dans cet ordre delta et epsilon.
Le pixel suivant sera thêta car celui-ci est un pixel de contour appartenant aux trois successeurs possibles d'epsilon (dzéta, iota et thêta), epsilon est un prédécesseur possible de thêta (parmi epsilon, delta et êta), et les directions de contours des deux pixels epsilon et thêta sont identiques.
Cette méthode ne chaîne pas des contours voisins dans la direction de leur gradient (contours antiparallèles rendus jointifs dans les images à texture à haute fréquence). La carte de contour issue de la phase 2 a donc besoin d'une étape de suppression des contours de gradient non-maximum avant d'effectuer la phase 3. Cette étape intermédiaire revient à réduire les composantes de haute fréquence de l'image en éliminant certains contours. La suppression des contours de gradient non-maximum élimine les pixels de contour qui ont, dans une direction normale à leur direction de contour, un voisin pixel de contour de plus grande intensité. Cette direction normale est en fait la direction du gradient. Nous calculons pour chaque pixel pe les deux voisins correspondant à la direction du gradient. Si l'un de ces deux voisins est un pixel de contour d'intensité supérieure à celle du pixel pe, alors le contour du pixel pe est éliminé. Le nombre de pixels ainsi éliminé est relativement faible.
Nous avons représenté l'extrait d'une image où se trouvait un coin figure 12 et les contours au voisinage de ce coin figure 13. On voit que le pixel de contour qui fait le coin (d'amplitude 164) a, dans la direction de son gradient, un voisin pixel de contour d'amplitude plus élevée (204). Ce pixel du coin sera éliminé.
|
|
| Figure 12 : extrait d'une image au niveau d'un coin | Figure 13 : direction et amplitude du gradient dans cet extrait |
|
| Figure 14 : vectorisation d'une chaîne |
Les lignes obtenues présentent en effet des défauts par rapport aux lignes recherchées. Le principal est la dislocation des coins. Puisque nous utilisons des contours minces et de directions de classes voisines de proche en proche, un pixel de contour ne peut y avoir que deux voisins et ne peut pas former avec eux d'angle droit. Nous ne pouvons donc pas avoir d'intersection de lignes, ni de lignes jointives avec un angle supérieur à 45°.
Cette contrainte ne nous gêne pas dans notre application finale, qui repose sur des images à distribution d'intensité bimodale représentant une image binaire (pour la zone utile), et pour laquelle il ne peut pas y avoir d'intersections de lignes.
Il peut aussi arriver qu'une ligne soit fragmentée, où qu'un coin soit disloqué en raison de défauts de contraste ou de composantes de haute-fréquences dans l'image.
Les figures 16 et 17 montrent l'ensemble de lignes issues de l'image de la figure 15 avant et après la restauration. On peut voir que l'ensemble est plus cohérent après la restauration même si certains défauts ne sont pas visibles. Sur la figure 16, les lignes en bas et à gauche du symbole sont représentées par deux longues lignes orthogonales. La disjonction évoquée précédemment ne se voit pas car les deux extrémités qui forment l'angle sont sur deux pixels voisins. Ces deux extrémités sont donc distantes d'exactement 1 pixel et semblent former deux segments sécants.
|
|
| Figure 15 : image contenant des lignes | Figure 16 : lignes vrutes (extraites de la figure 15) |
|
|
| Figure 17 : lignes restaurées à partir de la figure 16 (superposées sur l'image originale) |
Cette méthode a été utilisée avec succès dans la détection et localisation de codes symboliques Data-Matrix (dérivés des codes-à-barre bi-dimensionnels) dans des images à distribution d'intensité bimodale. Nous présentons figures 18 à 20 le résultat de la recherche de lignes sur l'image d'un symbole Data-Matrix.
|
|
| Figure 18 : image d'un symbole Data Matrix | Figure 19 : résultat de la détection de lignes |
|
|
| Figure 20 : résultat de la détection de lignes superposée à l'image 18 |