Brevet FR2641882A1 — publié le 19900720

Procédé et dispositif de binarisation d'image à deux dimensions, par comparaison à un seuil L'invention concerne la binarisation d'image, c' est-à-dire la conversion d'un signal donnant la valeur d'un paramètre optique, tel que la brillance ou la réflectivité, en des points élémentaires répartis suivant un réseau régulier dans l'image en un signal ayant l'une de deux valeurs binaires en chaque point élémentaire ou pixel. L'invention est susceptible de nombreuses applications ; en particulier elle est utilisable chaque fois qu'on cherche à identifier, dans une image, des objets de forme particulière ayant un contraste déterminé par rapport au fond. Pour simplifier, on considérera dans ce qui suit qu'il s'agit d'objets sombres sur fond clair (ou inversement), du fait d'un niveau de réflectivité ou de brillance différente. Mais le paramètre caractéristique d'un pixel de l'image peut être d'autre nature, par exemple lié à sa couleur. A titre d'exemple d'application, on peut notamment citer l'identification d'objets industriels dans l'image fournie par un capteur (ce problème se posant notamment en robotique) et la lecture optique ; dans ce dernier cas, le problème est facilité du fait que les caractères alphanumériques sont des objets à structure de traits, l'épaisseur des traits ainsi que leur longueur maximum étant approximativement connues. Un problème majeur que pose la binarisation d'une image est que le niveau de gris du fond n'est généralement pas uniforme, pas plus que le niveau de gris associé aux objets. Il est en conséquence impossible de différencier les pixels des objets des pixels du fond par simple comparaison avec un seuil de valeur constante dans toute l'image. Le niveau de gris des pixels du fond aussi bien que des pixels des objets varie d'un point à l'autre de l'image soit par suite d'une inhomogénéité d'éclairement, soit de manière inhérente au fond et aux objets (ou à leur support). De plus, les capteurs d'image et l'électronique qui leur est associée ont un bruit propre. On a déjà proposé de nombreux procédés de binarisation d'image. En particulier, on a proposé des procédés utilisant des algorithmes d'itération. Ils sont difficilement implémentables en temps réel, donc pratiquement incompatibles avec la lecture optique ou avec la binarisation d'images industrielles pour des applications telles que la robotique. On a également proposé des algorithmes de calcul dynamique d'un seuil local, constitué par une moyenne du niveau de gris sur un environnement particulier autour de chaque pixel. Mais ces procédés exigent qu'on définisse a priori la taille de l'environnement sur lequel est calculée la moyenne, donc qu'on dispose de connaissances sur la taille des objets. Si cette situation se présente dans certains cas de lecture numérique, à condition que les caractères aient une taille uniforme, cette contrainte enlève beaucoup de généralité au procédé et le rend peu intéressant en pratique. Un autre procédé encore utilise le signe d'un laplacien pour marquer les points d'entrée et les points de sortie d'un objet au cours d'un balayage de l'image selon des lignes particulières. Par exemple, la traversée de la frontière à l'entrée dans un objet noir (et à la sortie) est reconnue par le passage du laplacien d'une valeur potitive à une valeur négative (et inversement). Cette solution présente l'avantage de pouvoir être implémentée en temps réel de façon relativement simple en logiciel ou en utilisant une logique câblée. Mais elle se heurte à un défaut fondamental du laplacien qui est sa tendance à amplifier les variations de contraste locales, par exemple celles dues à des défauts microscopiques d'impression dans le cas de la lecture optique. Les performances d'un tel procédé sont également altérées en présence de bruits perturbant le laplacien qui, comme toutes les opérations qui s'apparentent à une dérivation, est sensible aux bruits de haute fréquence. On constate qu'effectivement une séquence d'entrée dans un objet noir ou de sortie de cet objet peut être "oubliée". Ce défaut ne peut être écarté qu'à partir d'une information a priori sur la dimension des objets rencontrés au cours d'un balayage suivant la direction utilisée de l'image : mais le procédé n'a plus la généralité souhaitable. L'invention vise notamment à fournir un procédé de binarisation d'image à deux dimensions, utilisable en temps réel et sans qu'il soit nécessaire de faire d'hypothèse sur la taille des objets présents dans l'image. Pour cela, elle utilise la constatation qu'on peut établir un lien entre céux des pixels intérieurs aux objets qui sont situés au voisinage du contour des objets, et ceux qui en sont éloignés sous la forme tous les pixels intérieurs aux objets sont caractérisés par un niveau de gris différent du niveau de gris des pixels extérieurs situés au voisinage. Il est alors possible d'étiqueter les pixels par comparaison à un seuil à la condition de connaitre les niveaux de gris caractéristiques de l'intérieur et de l'extérieur des objets : un laplacien de haute fréquence va permettre de connaitre ces niveaux de gris. Pour mettre en oeuvre cette constatation, l'invention propose notamment un procédé suivant lequel (a) on soumet l'image à un filtrage par convolution avec un filtre de réponse impulsionnelle gaussienne pour obtenir une transformée de l'image (b) on soumet la transformée à un filtrage par convolution avec un filtre de réponse gaussienne ayant un noyau plus étendu que le premier filtre et correspondant F un environnement sur lequel un laplacien est significatif (c) on évalue les niveaux de gris caractéristiques de l'intérieur et de l'extérieur des objets par réactualisation le long d'une ligne de balayage, du niveau de blanc ou de noir selon le signe du laplacien pour ce pixel (d > on détermine un seuil de discrimination par moyenne, éventuellement pondérée, entre les niveaux de blanc et de noir ; et (e) on étiquette chaque pixel par comparaison avec le seuil correspondant. L'invention propose également un dispositif permettant de mettre en oeuvre le procédé ci-dessus défini, susceptible d'avoir une constitution entièrement en "pipe-line", d'implémentation peu coûteuse ; l'architecture en pipe-line permet de fonctionner à la volée sur un signal video numérisé délivré par un capteur. La seule contrainte est d'exiger qu'on choisisse un contraste minimum, mais dans beaucoup d'applications (binarisation de documents, par exemple) ce serait plutôt un avantage. L'invention sera mieux comprise à la lecture de la description qui suit d'un mode particulier de réalisation, donné à titre d'exemple non limitatif. La description se réfère aux dessins qui l'accompagnent, dans lesquels - la Figure 1 montre un exemple de variation de réflectivité sur une ligne d'image à numériser - la Figure 2 est un schéma de principe d'un dispositif suivant l'invention - la Figure 3 est un schéma montrant le signal du laplacien en des points élémentaires d'une image qu'on peut considérer comme représentative, où figurent les caractères M-8 en noir sur fond blanc (les signes + et - indiquant respectivement un laplacien positif et un laplacien négatif tandis qu'un zéro indique un laplacien nul) - la Figure 4 montre, du haut en bas : une image réelle à numériser des caractères PL/M-86, en noir sur fond blanc ; deux représentations successives de l'image, constituées par l'image binaire et le signe du laplacien, et l'image du seuil - la Figure 5, similaire à la Figure 4, correspond à une règle modifiée de réactualisation des seuils. Avant d'exposer l'invention, il peut être utile de faire apparaître le problème posé par la variation du seuil qui différencie les portions appartenant à des objets sombres de celles d'un fond clair, le long d'une ligne de balayage d'image d'ordonnée yo. On voit sur la Figure 1 que la ligne traverse-des objets sombres qui ne peuvent être identifiés par un même seuil fixe Mais le laplacien de haute fréquence L1 permet de connaître les niveaux de gris en donnant, par son signe, une indication sur l'évolution du gris. Sur la Figure 1, on voit que le signe-du laplacien L1 (x,yO) s'inverse à chaque frontière sur la ligne I (x,yO). Le -laplacien en chaque pixel de l'image peut être déterminé notamment à l'aide du montage schématisé en Figure 2. Un capteur 10, tel qu'une caméra video, fournit, d'une scène 8 à binariser, une image sous forme d'un tableau de n x p pixels codés chacun sur 2x niveaux de gris, chaque pixel étant représenté par un mot de x bits ; on utilise fréquemment une numérisation des pixels par 1 octet, donc à 256 niveaux de gris. On supposera que le capteur comporte une mémoire d'image capable de stocker les n x p pixels à l'issue d'un balayage complet de l'image et jusqu'à apparition de l'image suivante. Un premier opérateur 12, qui peut être programmé ou cabalé, fournit, à partir de l'image (I(j,k) fournie par le capteur 10, une transformée I1(j,k). L'opérateur 12 est constitué par un filtre de convolution ayant une réponse impulsionnelle gaussienne. On peut notamment utiliser un filtre ayant un noyau de convolution g de 3 x 3. On supposera dans ce qui suit que l'image transformée Il(j,k) obtenue par convolution de l'image I(j,k) par le filtre 12 est Le masque de convolution g de la formule (1) constitue une approximation de la fonction = 0,5 L'image transformée Il est appliquée à un second filtre 14 de convolution dont le noyau G(j,k > est lié à g par la relation G(j,k) = g*g*g. Le noyau G a une taille 7 x 7 et constitue une approximation de la fonction où #22 3 #12 = 1,5. A partir des images I1(j,k), fournie par le filtre 12, et I2(,k), fournie par le filtre 14 (cette dernière constituant une représentation filtrée, à basse fréquence spatiale), on peut obtenir une approximation du laplacien gaussien L(j,k > - de 11(j,k > calculée sur un environnement qui est, dans le cas de la formule (l) ci-dessus, de 7 x 7 L(j,k) = ,k) - 12(j,k > (2 > à l'aide d'un soustracteur 15. Dans ce qui suit, pour simplifier, on désignera par "laplacien gaussien" l'approximation en différence finie de l'opérateur laplacien fourni par les opérateurs donnés à titre d'exemples. La Figure 3 montre la répartition du signe du laplacien L1 aux emplacements des pixels d'une image des caractères M-8 que l'on peut considérer comme représentative. Ceux des pixels situés à l'intérieur des caractères qui sont proches du contour de ces caractères sont caractérisés par un laplacien négatif. Ceux des pixels situés à l'extérieur des caractères qui sont eux aussi proches du voisinage d'un contour sont caractérisés par un laplacien positif, la notion de voisinage étant relative à l'étendue du domaine sur lequel est calculé le laplacien, ici un environnement 7 * 7 centré sur chaque pixel : à chaque frontière, il y a inversion de signe du laplacien L1. Les niveaux locaux de blanc B (x,yO) et de N (x, pour pour les points x, yO, peuvent alors être réactualisés en tenant compte qu'un laplacien positif indique le fond, du moins à proximité de la frontière d'un objet, et inversement. On peut adopter, comme règle de réactualisation, des niveaux de blanc et de noir B(x, yO) = N(x,yO) I(x, yO) si L1 > O sinon, B(x-dx, yO), c'est-à-dire B conserve la valeur qu'il avait précédemment le long de la ligne I(x, yO) siL1 On voit que - B(x, yO) est réactualisé au cours d'un balayage selon les x croissants chaque fois qu'on approche d'un ca ractère : on connaîtra donc le niveau local du blanc. - N(x, yO) est réactualisé chaque fois qu'on entre ou qu'on sort du caractère : on connaîtra donc le niveau local du noir. Si la probabilité de présence des pixels blancs et noirs est ignorée, ce qui est le cas le plus fréquent, on choisira avantageusement comme seuil de discrimination S(x, yO) : S(x, yO) = EB(x, yO) + N(x, y0 > ) / 2 dont la valeur sera réactualisée à chaque changement de signe du laplacien Ll. La seule contrainte à respecter est que, dans un intervalle tel que [x2,x3] où Ll(x) = O (Figure 1), le niveau de gris ne varie pas de manière significative par rapport à S(x).Dans l'exemple illustré en Figure 1, à la première traversée de frontière I(x) Cette contrainte, d'autant plus facile à respecter que le contraste sur le bord d'entrée de l'objet est important, n'est en général pas gênante. La Figure 2 montre comment l'algorithme peut être implémenté, à partir de l'image filtrée passe-bas 12(j,k). Le dispositif représenté comprend un opérateur 16 d'apprentissage du seuil S et un comparateur 18 permettant d'obtenir directement l'image binarisée. Ce comparateur donne le pixel comme blanc si Il(j,k) noir dans le cas contraire (B=O). L'opérateur 16 d'apprentissage de seuil S doit fournir au comparateur 18 un seuil S élaboré suivant la règle de réactualisation donnée plus haut. Pour cela, des niveaux initiaux de blanc BO et de-noir NO doivent être fournis au début de chaque ligne. On peut notamment, en faisant l'hypothèse qu'en début de ligne l'image représente le fond, adopter pour chaque ligne d'ordonnée y = j, (1) B (j,O) = I2(j,0) N (j,O) = O. Les règles d'actualisation de B et N peuvent être mises en oeuvre par des opérateurs 22 et 24 qui re#çoivent Il (ou I2) et le signal de sortie - soit d'un comparateur 20 fournissant le signe du laplacien L1 lorsque ce signe est utilisé comme paramètre de décision (Figure 2), - soit Il et I2 (lignes en tirets) dans le cas où on utilise par exemple les règles (2) (3) Si Il(j,k) > I2(,k) alors B(j,k > . 12(j,k > et si N(j,k > > I2(S,k) alors N(j,k) = 12(j,k > . Si 11(j,k > ,k) s I2( > ,k). On voit que les niveaux de B et N réactualisés ne correspondent pas à l'image Il, mais à l'image filtrée passe-bas I2 : on réduit ainsi les variations erratiques de ces niveaux dues au bruit de fond. La deuxième ligne de chaque règle a pour fonction d'interdire qu'à la suite d'une réactualisation le niveau de noir soit supérieur au niveau de blanc (ou inversement). Cette situation pourrait en effet se produire en présence de variations lentes des niveaux de gris, en l'absence de cette seconde ligne. Enfin, l'opérateur 26 de calcul de moyenne fournit S par la règle (4) S(j,k) = [ B(j,k) + N(jjk > ] /2 La Figure 4 montre que le procédé qui vient d'être décrit fournit une représentation satisfaisante (seconde ligne) de l'image réelle (première ligne) là où des objets sont présents, ce qui montre que le seuil S y est correctement réactualisé. Les règles ci-dessus sont cependant prises en défaut lorsque le laplacien devient positif à l'intérieur des objets, ce qui se produit en haut à gauche et au milieu en bas du M (lignes 2 et 3 de la Figure 4).Par contre, dans les zones où le fond est seul présent, le signe du laplacien est plus satisfaisant comme indicateur d'intérieur et d'extérieur d'objet, ce qui se traduit par l'existence de halos blancs autour des objets, halos eux-mêmes entourés de zones où certain pixels de fond sont étiquetés "noir". Lorsqu'il est nécessaire ou souhaitable d'écarter ou d'atténuer ces défauts de binarisation du fond, on peut remplacer les règles (2) et (3) par (2bis) Si [I1,(j,k) > I2(j,k > ) et [I2(j,k) > S(j,k > ) alors B(j,k > = I2(j,k) (3bis) Si tIl(,k) = I2( > ,k) où CT est un contraste local minimum prédéterminé égal par exemple à 1/32 de la pleine échelle de numérisation. La règle (2bis) assure la réactualisation du niveau de blanc B si le laplacien L1 est non négatif, à condition que le pixel soit à l'extérieur des objets : le niveau de blanc suit ainsi le niveau du fond. La règle (3bis) assure la réactualisation du niveau de noir si le laplacien L1 est négatif : le pixel correspondant est présumé situé à l'intérieur d'un objet. On distingue un objet véritable d'un bruit au moyen du contraste local minimum CT. La Figure 5 montre le résultat obtenu en utilisant les règles (abris) et (3bis). On voit que le seuil S (image du bas) reste bas dans les zones où aucun objet n'est présent et qu'il varie en fonction du contraste local dans les zones où des objets sont présents. On ne décrira pas de mode d'implémentation des règles (2bis) et (3bis) car il en découle directement. Le procédé est directement transposable à une image dans laquelle les objets sont clair et le fond sombre. Les règles (1), (2bis), (3bis) et (4) sont alors modifiées d'une façon qui découle directement de l'invention. La règle (1) devient par exemple B(j,O) = 2m-1 N(j,O > I2(j,O > ou 2m-1 représente le niveau maximum numérisable, par exemple 28-1 = 255, lorsqu'on suppose que le début de chaque ligne est constitué par le fond. REVENDICATIONS 1. Procédé de binarisation d'image à deux dimensions, utilisable en temps réel, suivant lequel (a) on soumet l'image à un filtrage par convolution avec un filtre de réponse impulsionnelle gaussienne pour obtenir une transformée de l'image ; (b) on soumet la transformée à un filtrage par convolution avec un filtre de réponse gaussienne ayant un noyau plus étendu que le premier filtre et correspondant à un environnement sur lequel un laplacien est significatif (c) on évalue les niveaux de gris caractéristiques de l'intérieur et de l'extérieur des objets par réactualisation le long d'une ligne de balayage, du niveau de blanc ou de noir selon le signe du laplacien pour ce pixel (d) on détermine un seuil de discrimination par moyenne, éventuellement pondérée, entre les niveaux de blanc et de noir ; et (e) on étiquette chaque pixel par comparaison avec le seuil correspondant. 2. Procédé selon la revendication 1, caractérisé en ce qu'on réactualise les niveaux de noir N et de blanc B par application des règles (2) (3) Si I1(j,k) > I2(j,k) alors B(j,k) = I2(,k) et si N(j,k) > I2(j,k > alors N(j,k) = I2(j,k). Si Il(jlk) et si B(j,k) où Il et 12 désignent respectivement les images provenant des opérations (a) et (b). 3. Procédé selon la revendication 1, caractérisé en ce qu'on réactualise les niveaux de blanc 8 et de noir N par application des règles (2bis) (3bis) Si [ k) > I2(j,k > ) et I2(j,k) > S(j,k)) alors B(j,k) = I2(j,k) Si (I1(j,k > = I2(j,k > . où CT est un contraste local minimum prédéterminé et où Il et 12 désignent respectivement les images provenant des opérations (a) et (b > . 4. Procédé selon les revendications 1 à 3, caractérisé en ce qu'on initialise B et N au début de chaque ligne aux valeurs B = t2 N = O. 5. Dispositif de binarisation d'image à deux dimensions par le procédé suivant la revendication 1, caractérisé en ce qu'il comprend - un premier filtre de convolution ayant une réponse impulsionnelle gaussienne ; - un second filtre de convolution ayant une réponse gaussienne, ayant un noyau plus étendu que le premier filtre et correspondant à un environnement sur lequel un laplacien est significatif - des moyens d'évaluation des niveaux de gris caractéristique de l'intérieur et de l'extérieur des objets par réactualisation le long d'une ligne de balayage, du niveau de blanc ou de noir,selon le signe du laplacien pour ce pixel - des moyens pour déterminer un seuil de discrimination en calculant une moyenne, éventuellement pondérée, entre les niveaux de blanc et de noir ; et - des moyens d'étiquettage de chaque pixel par comparaison avec le seuil correspondant.