Brevet FR2769733A1 — publié le 19990416

- 1 PROCEDE D'EXTRACTION AUTOMATIQUE D'INSCRIPTIONS IMPRIMEES OU MANUSCRITES SUR UN FOND, DANS UNE IMAGE NUMERIQUE MULTINIVEAUX La présente invention concerne un procédé d'extrac- tion automatique d'inscriptions imprimées ou manuscrites sur un fond, dans une image numérique multiniveaux. Plus précisément, elle concerne un procédé pour traiter une image numérique à N niveaux de gris, N étant un entier supérieur à 2, qui comporte, d'une part, un fond préalablement imprimé et, d'autre part, des données inscrites sur ce fond par impression ou écriture manuscrite, afin d'extraire ces données en vue d'opérations ultérieures d'analyse et de reconnaissance automatiques. L'invention s'applique notamment à la saisie automatique de montants de chèques et sera plus particuliè- rement décrite ici dans cette application. Néanmoins, plus généralement, l'invention peut être appliquée dans de nombreux domaines qui utilisent l'analyse automatique de documents dont le fond pose problème, comme par exemple dans le domaine de la cartographie. En matière de saisie automatique de montants de chèques, une opération essentielle consiste à détecter et extraire automatiquement les montants en chiffres et en lettres imprimés ou manuscrits sur les chèques. La diffi- culté majeure de cette opération provient de ce que le fond préimprimé des chèques est généralement complexe et n'est pas restitué avec les qualités requises par les capteurs d'image couramment utilisés qui fournissent une image binaire des chèques à analyser. Le problème consistant à éliminer le fond du chèque et extraire les montants en chiffres et en lettres dans une image binaire ne peut donc être résolu de façon satisfai- sante par une simple technique classique de binarisation par seuillage, qui attribuerait à la partie "fond" les pixels ayant une valeur de niveau de gris supérieure à un seuil fixe choisi au préalable, et à la partie "montant" les pixels ayant une valeur de niveau de gris inférieure à ce seuil fixe. L'application de techniques classiques de binarisa- tion par seuillage conduit en effet à de nombreuses erreurs d'interprétation: des chiffres ou des lettres des montants à reconnaître peuvent être filtrés par erreur comme apparte- nant au fond préimprimé du chèque, et vice versa. L'ambi- guïté entre le fond et les inscriptions est d'autant plus grande que sur l'image de gris de certains chèques, il arrive que des pixels du fond soient plus foncés que des pixels correspondant à l'image du montant du chèque. La présente invention a pour but de pallier les inconvénients précités en proposant un seuillage adaptatif, particulièrement adapté à l'élimination du fond dans les images à traiter, et fondé sur la détection de configura- tions géométriques bidimensionnelles particulières, suscep- tibles de correspondre aux inscriptions imprimées ou manuscrites recherchées. Dans ce but, la présente invention propose un procédé d'extraction automatique d'inscriptions imprimées ou manuscrites sur un fond, dans une image numérique à N niveaux de gris, N étant un entier supérieur à 2, suivant lequel, pour chaque ensemble constitué d'une ligne ou de plusieurs lignes contiguës de pixels de l'image: (a) on compare la valeur de niveau de gris de chaque pixel aux valeurs respectives d'au moins deux autres pixels appartenant à un voisinage prédéterminé de ce pixel, et on retient les valeurs des pixels qui, après comparaison, vérifient simultanément au moins deux inégalités prédétermi- nées; puis, pour chaque groupe d'inégalités à vérifier simultanément: (b) on établit un histogramme donnant, pour chaque valeur de niveau de gris comprise entre 0 et N-l, le nombre de pixels retenus à l'issue des comparaisons effectuées à l'étape (a); (c) à partir de l'histogramme, on détermine, parmi les N valeurs de niveau de gris, un seuil S; (d) on répartit les pixels retenus en une première catégorie, pour laquelle la valeur est supérieure à S, et une deuxième catégorie, pour laquelle la valeur n'est pas supérieure à S; (e) on balaie horizontalement, respectivement verticalement, ledit ensemble constitué d'une ligne ou de plusieurs lignes de l'image et on détermine sur chaque ligne, respectivement chaque colonne, des précurseurs horizontaux, respectivement verticaux, comme étant des ensembles de pixels contigus horizontalement, respectivement verticalement, et qui ont été classés à l'étape (d) dans la deuxième catégorie; (f) parmi les précurseurs horizontaux, respective- ment verticaux, déterminés précédemment, on extrait des polygones verticaux, comprenant un nombre Yv de précurseurs horizontaux connexes verticalement, et des polygones horizontaux, comprenant un nombre xh de précurseurs verti- caux connexes horizontalement; (g) lorsque le nombre total y, de précurseurs horizontaux connexes verticalement est inférieur à un nombre prédéterminé pv ou lorsque le nombre total xh de précurseurs verticaux connexes horizontalement est inférieur à un nombre prédéterminé Ph, on réitère les étapes (d) à (f) avec une valeur de seuil S modifiée; lesdites inscriptions étant obtenues sous la forme desdits polygones extraits. Dans un mode particulier de réalisation, à l'étape (a), on teste si les couples suivants d'inégalités sont vérifiés: (i) g(x,y) g (x-l,y) et g(x+l,y) 0 g(x,y) (ii) g(x,y) O g (x,y-1) et g(x,y+l) O g(x,y) (iii) g(x,y) G g (x-l,y-1) et g(x+1,y+l) O g(x,y) (iv) g(x, y) 0 g (x+l,y-l) et g(x-l,y+l) Q g(x,y) (v) g(x,y) g (x-2,y) et g(x+2,y) g(x,y) (vi) g(x,y) g (x,y-2) et g(x,y+2) g(x,y) (vii) g(x,y) g (x-2,y-2) et g(x+2,y+2) O g(x,y) (viii) g(x,y) g (x+2, y-2) et g(x-2,y+2) g(x,y) o g(x,y) désigne la valeur de niveau de gris du pixel situé au croisement de la ym' ligne et de la x= colonne de l'image, et o le signe O peut être l'un quelconque des signes s, . Selon un mode particulier de réalisation, à l'étape (c), on peut rechercher un maximum local de l'histogramme, déterminer la tangente à l'histogramme en un point d'in- flexion ayant une abscisse inférieure à l'abscisse de ce maximum local, et choisir comme seuil S la valeur de niveau de gris située à l'intersection de ladite tangente avec l'axe des abscisses de l'histogramme. En variante, à l'étape (c), on peut rechercher deux maxima locaux de l'histogramme et, le cas échéant, choisir comme seuil S la valeur de niveau de gris située au milieu du segment joignant les abscisses de ces deux maxima locaux. En variante, à l'étape (c), (cl) on établit pour chaque ligne un histogramme tel que celui défini à l'étape (b); (c2) dans chaque histogramme H(g), o g, 0 0; (c3) pour chaque valeur de niveau de gris, on additionne le nombre de valeurs go satisfaisant aux condi- tions définies à l'étape (c2) relevées dans tous les histogrammes; (c4) on choisit pour seuil S la valeur de niveau de gris pour laquelle le total obtenu à l'issue de l'étape (c3) est maximal, en excluant le choix S = 0. Une variante à l'étape (c2) consiste à déterminer, dans chaque histogramme H(g), les valeurs go pour lesquelles H(g0-1) 2 H(g0) et H(g0) L'ensemble de lignes contiguës précité peut compren- dre 8 lignes contiguës de l'image, en particulier si l'image à traiter a été comprimée conformément à la norme JPEG. Les inscriptions consistant en des traits verticaux sont extraites sous la forme de polygones verticaux, et les inscriptions consistant en des traits horizontaux sont extraites sous la forme de polygones horizontaux. D'autres buts et aspects de la présente invention apparaîtront à la lecture de la description détaillée qui suit de modes particuliers de réalisation, donnés à titre d'exemples non limitatifs. La description se réfère aux dessins qui l'accompagnent, dans lesquels: - la figure 1 est un organigramme du procédé conforme à la présente invention, dans un mode particulier de réalisation; - les figures 2A à 2H illustrent les différents types de voisinages considérés à l'étape (a) du procédé conforme à la présente invention, dans un mode particulier de réalisation; - la figure 3 représente un exemple d'histogramme susceptible d'être obtenu à l'issue de l'étape (b) du procédé conforme à la présente invention, dans un mode particulier de réalisation; et - la figure 4 représente de façon schématique quatre polygones de forme arbitraire, susceptibles d'être obtenus à l'issue de l'étape (e) du procédé conforme à la présente invention, dans un mode particulier de réalisation. Dans ce qui suit, on considère une image numérique à N niveaux de gris, N étant un entier supérieur à 2, dite image numérique "multiniveaux". A titre indicatif, on peut avoir N = 256. Cette image peut avoir été obtenue à l'aide d'un capteur classique, du type caméra de télévision, barrette de CCD ou réseau de diodes. Dans l'application de la présente invention à la saisie automatique de montants de chèques, il s'agit de l'image d'un chèque, comportant un fond préimprimé et des inscriptions imprimées ou manuscrites sur ce fond, qui indiquent généralement le montant du chèque en chiffres et en lettres, le bénéficiaire, le lieu et la date du chèque, ainsi que la signature de la personne ayant établi le chèque. A titre indicatif, la taille moyenne d'un chèque étant de 80 x 175 mm2, et l'image étant par exemple échan- tillonnée à environ 240 d.p.i. (c'est-à-dire 240 points par pouce, en anglais "dots per inch"), ce qui équivaut approxi- mativement à 8 à 10 pixels par mm, on dispose d'une image ayant une taille de l'ordre de grandeur de 800 x 1750 pixels. On cherche à extraire de façon automatique ces inscriptions imprimées ou manuscrites, et plus particulière- ment à extraire des traits verticaux, horizontaux et obliques qui les constituent. Pour cela, on considère un ensemble de L lignes contiguës de pixels de l'image, L étant un entier supérieur ou égal à 1 et on effectue l'ensemble des traitements sur cet ensemble de L lignes. A titre d'exemple non limitatif, si l'image est codée suivant la norme JPEG, on considère des ensembles de L = 8 lignes. Au cours d'une première étape, on définit différents voisinages d'un pixel central donné. Dans un mode particu- lier de réalisation, on définit huit voisinages comprenant chacun deux pixels en plus du pixel central. Ces voisinages sont illustrés par les figures 2A à 2H, o chaque pixel est représenté par un carré. En variante, on peut définir des voisinages compre- nant plus de deux pixels en plus du pixel central. On note g(x,y) la valeur de niveau de gris du pixel situé au croisement de la yéa ligne et de la x^ colonne de l'image. A titre d'exemple non limitatif, on peut choisir une échelle de niveaux de gris telle que plus un pixel est clair, plus sa valeur g est grande. Pour chaque pixel de l'ensemble de L lignes de l'image à traiter, on considère un voisinage déterminé et on compare la valeur de niveau de gris du pixel central aux valeurs de niveau de gris de ses deux voisins. Le voisinage représenté sur la figure 2A comprend un pixel central et ses voisins directs de gauche et de droite. On compare g(x,y), d'une part, à g(x-l,y), valeur de niveau de gris du pixel voisin de gauche, et d'autre part, à g(x+l,y), valeur de niveau de gris du pixel voisin de droite. On teste si les deux inégalités suivantes sont vérifiées simultanément: g(x,y) g(x-l,y) et g(x+l,y) g(x,y) o le signe 0 est un signe d'inégalité choisi: ou >. On choisit par exemple le signe niveau de gris décroissantes de gauche à droite, c'est-à- dire sont de plus en plus foncés de gauche à droite. Les voisinages représentés sur les figures 2B à 2H donnent lieu à la vérification de couples d'inégalités analogues. Si on considère un voisinage tel que représenté sur la figure 2B, on teste si les deux inégalités suivantes sont vérifiées simultanément: g(x,y) Q g(x,y-1) et g(x,y) O g(x,y+l) Si on considère un voisinage tel que représenté sur la figure 2C, on teste si les deux inégalités suivantes sont vérifiées simultanément: g(x,y) g(x-l,y-1) et g(x,y) g(x+l,y+l) Si on considère un voisinage tel que représenté sur la figure 2D, on teste si les deux inégalités suivantes sont vérifiées simultanément: g(x,y) O g(x+l,y-1) et g(x,y) O g(x-l,y+l) - 8 Si on considère un voisinage tel que représenté sur la figure 2E, on teste si les deux inégalités suivantes sont vérifiées simultanément: g(x,y) g(x-2,y) et g(x,y) g(x+2,y) Si on considère un voisinage tel que représenté sur la figure 2F, on teste si les deux inégalités suivantes sont vérifiées simultanément: g(x,y) g(x,y-2) et g(x,y) O g(x,y+2) Si on considère un voisinage tel que représenté sur la figure 2G, on teste si les deux inégalités suivantes sont vérifiées simultanément: g(x,y) O g(x-2,y-2) et g(x,y) O g(x+2,y+2) Si on considère un voisinage tel que représenté sur la figure 2H, on teste si les deux inégalités suivantes sont vérifiées simultanément: g(x,y) O g(x+2,y-2) et g(x,y) O g(x-2,y+2) On retient les pixels qui vérifient un couple d'inégalités parmi les précédents. Ces pixels sont dits "pixels différentiels". Pour un ensemble de pixels différentiels vérifiant un couple d'inégalités donné, comme l'indique la figure 1, on établit un histogramme portant, en abscisse, les valeurs g de niveau de gris, et en ordonnée, le nombre correspondant de pixels différentiels. On observe qu'un tel histogramme comporte un ou plusieurs maxima locaux. La figure 3 représente, à titre d'exemple non limitatif, un histogramme de forme arbitraire, établi pour N = 256 niveaux de gris et comportant un maximum. L'étape suivante du procédé selon l'invention, comme l'indique la figure 1, consiste à déterminer, à partir de l'histogramme, une valeur de niveau de gris seuil S, en deçà de laquelle les pixels différentiels seront considérés comme susceptibles d'appartenir à des inscriptions et au-delà de laquelle les pixels différentiels seront considérés comme susceptibles d'appartenir au fond de l'image. Ce seuil S de décision peut être déterminé de plusieurs façons. Dans le mode particulier de réalisation illustré par la figure 3, on détermine la tangente T à l'histogramme en un point d'inflexion I de l'histogramme situé à gauche du maximum, c'est-à-dire ayant une abscisse inférieure à l'abscisse du maximum. La tangente T coupe l'axe des abscisses en un point S, dont la valeur de niveau de gris est choisie comme seuil. En variante, on peut rechercher deux maxima locaux de l'histogramme. S'ils existent, on peut choisir pour valeur seuil S le milieu du segment joignant les abscisses des deux maxima. Une autre variante pour déterminer le seuil S consiste, à l'étape (c), à établir tout d'abord un histo- gramme des pixels différentiels de chaque ligne, noté H(g), o g désigne la valeur de niveau de gris, O O. Il peut y avoir plusieurs valeurs go pour chaque ligne. Une variante consiste à déterminer les valeurs go pour lesquelles H(g0- l) > H(g0) et H(g0) variante généralise le cas précédent. On additionne ensuite, pour chaque valeur de niveau de gris, le nombre de valeurs go relevées dans tous les histogrammes. Pour cela, on ne tient pas compte des valeurs de niveau de gris extrêmes, à titre d'exemple, O, 1, 2 et 13, 14, 15 pour 16 valeurs de niveau de gris, car ces valeurs risquent de produire des points aberrants. On choisit pour seuil S la valeur de niveau de gris pour laquelle le nombre de valeurs go est le plus grand. L'étape suivante du procédé consiste à rechercher, parmi les pixels différentiels, des ensembles de pixels contigus, horizontalement et verticalement. Par balayage horizontal, on détermine ainsi des ensembles comprenant au moins 2 pixels différentiels contigus horizontalement, appelés "précurseurs horizontaux", et par balayage vertical, on détermine des ensembles comprenant au moins 2 pixels différentiels contigus vertica- lement, appelés "précurseurs verticaux". Ensuite, on recherche des ensembles de précurseurs verticaux connexes horizontalement. Ces configurations, dites "polygones horizontaux", sont susceptibles de corres- pondre à des traits horizontaux constituant les inscriptions à extraire. On recherche de même des ensembles de précurseurs horizontaux connexes verticalement, dits "polygones verti- caux". La figure 4 donne l'allure d'un ensemble 1 de précurseurs verticaux recouvrant une courbe. L'ensemble 1 est formé de 8 précurseurs verticaux 101,..., 108. On voit sur la figure 4 que les pixels de deux précurseurs adjacents du polygone 1 sont situés dans des colonnes adjacentes de l'image. Cela illustre la connexité des précurseurs, condition nécessaire d'appartenance à un polygone. La figure 4 donne également l'allure d'un polygone horizontal 2 recouvrant un trait horizontal. On voit que les précurseurs formant un polygone ne sont pas nécessairement de taille égale. La figure 4 donne en outre l'allure de deux polygo- nes verticaux 3 et 5, formés respectivement de 9 précurseurs horizontaux et 8 précurseurs horizontaux. Il peut arriver que le nombre yv de précurseurs horizontaux trouvés formant un polygone soit insuffisant pour extraire un trait vertical sur toute sa hauteur. On obtient dans ce cas plusieurs polygones disjoints, tels que les polygones 3 et 5 de la figure 4. La même situation peut se produire pour le nombre xh de précurseurs verticaux. Cela signifie que le seuil S de décision choisi précédemment n'est pas judicieux. On détermine un nombre Pv de précurseurs horizontaux connexes verticalement à atteindre pour former un polygone vertical estimé de hauteur suffisante. Le choix de pv est fonction de la largeur moyenne attendue des polygones verticaux, ainsi que du nombre de lignes toléré entre deux polygones verticaux disjoints susceptibles de couvrir un même trait vertical. De même, on détermine un nombre Ph de précurseurs verticaux connexes horizontalement à atteindre pour former un polygone horizontal estimé de longueur suffisante. De façon analogue, le choix de Ph est fonction de la hauteur moyenne attendue des polygones horizontaux, ainsi que du nombre de colonnes toléré entre deux polygones horizontaux disjoints susceptibles de couvrir un même trait horizontal. Si Yv réitère les étapes de classification des pixels différen- tiels, de détermination des précurseurs et de recherche des polygones. Par adaptation du seuil S, on obtient ainsi des polygones verticaux couvrant des traits verticaux sur toute leur hauteur et des polygones horizontaux couvrant des traits horizontaux sur toute leur longueur. Une fois les inscriptions extraites conformément au procédé de l'invention, les pixels extraits peuvent faire l'objet d'un traitement de reconnaissance de formes connu, par exemple en vue de saisir automatiquement le montant porté sur le chèque traité, dans l'exemple d'application à la reconnaissance automatique de montant de chèque. L'image traitée peut également être recomprimée. REVENDICATIONS 1. Procédé d'extraction automatique d'inscriptions imprimées ou manuscrites sur un fond, dans une image numéri- que à N niveaux de gris, N étant un entier supérieur à 2, suivant lequel, pour chaque ensemble constitué d'une ligne ou de plusieurs lignes contiguës de pixels de l'image: (a) on compare la valeur de niveau de gris de chaque pixel aux valeurs respectives d'au moins deux autres pixels appartenant à un voisinage prédéterminé de ce pixel, et on retient les valeurs des pixels qui, après comparaison, vérifient simultanément au moins deux inégalités prédétermi- nées; puis, pour chaque groupe d'inégalités à vérifier simultanément: (b) on établit un histogramme donnant, pour chaque valeur de niveau de gris comprise entre 0 et N-i, le nombre de pixels retenus à l'issue des comparaisons effectuées à l'étape (a); (c) à partir de l'histogramme, on détermine, parmi les N valeurs de niveau de gris, un seuil S; (d) on répartit les pixels retenus en une première catégorie, pour laquelle la valeur est supérieure à S, et une deuxième catégorie, pour laquelle la valeur n'est pas supérieure à S; (e) on balaie horizontalement, respectivement verticalement, ledit ensemble constitué d'une ligne ou de plusieurs lignes de l'image et on détermine sur chaque ligne, respectivement chaque colonne, des précurseurs horizontaux, respectivement verticaux, comme étant des ensembles de pixels contigus horizontalement, respectivement verticalement, et qui ont été classés à l'étape (d) dans la deuxième catégorie; (f) parmi les précurseurs horizontaux, respective- ment verticaux, déterminés précédemment, on extrait des polygones verticaux, comprenant un nombre y, de précurseurs horizontaux connexes verticalement, et des polygones horizontaux, comprenant un nombre xh de précurseurs verti- caux connexes horizontalement; (g) lorsque le nombre total Yv de précurseurs horizontaux connexes verticalement est inférieur à un nombre prédéterminé pv ou lorsque le nombre total xh de précurseurs verticaux connexes horizontalement est inférieur à un nombre prédéterminé ph, on réitère les étapes (d) à (f) avec une valeur de seuil S modifiée; lesdites inscriptions étant obtenues sous la forme desdits polygones extraits. 2. Procédé selon la revendication 1, suivant lequel, à l'étape (a), on teste si les couples suivants d'inégalités sont vérifiés: (i) g(x,y) g (x-l,y) et g(x+l,y) g(x,y) (ii) g(x,y) O g (x, y-1) et g(x,y+1) O g(x,y) (iii) g(x,y) O g (x-l,y-1) et g(x+l,y+l) O g(x,y) (iv) g(x,y) G g (x+l,y-1) et g(x-l,y+1) O g(x,y) (v) g(x,y) O g (x-2,y) et g(x+2,y) G g(x,y) (vi) g(x,y) O g (x,y- 2) et g(x,y+2) O g(x,y) (vii) g(x,y) O g (x-2,y-2) et g(x+2,y+2) O g(x,y) (viii) g(x,y) O g (x+2,y-2) et g(x-2,y+2) O g(x,y) o g(x,y) désigne la valeur de niveau de gris du pixel situé au croisement de la yè" ligne et de la xi= colonne de l'image, et o le signe O peut être l'un quelconque des signes 5, , >. 3. Procédé selon la revendication 1 ou 2, suivant lequel, à l'étape (c), on recherche un maximum local de l'histogramme, on détermine la tangente à l'histogramme en un point d'inflexion ayant une abscisse inférieure à l'abscisse de ce maximum local, et on choisit comme seuil S la valeur de niveau de gris située à l'intersection de ladite tangente avec l'axe des abscisses de l'histogramme. 4. Procédé selon la revendication 1 ou 2, suivant lequel, à l'étape (c), on recherche deux maxima locaux de 14 - l'histogramme et, le cas échéant, on choisit comme seuil S la valeur de niveau de gris située au milieu du segment joignant les abscisses de ces deux maxima locaux. 5. Procédé selon la revendication 1 ou 2, suivant lequel, à l'étape (c), (cl) on établit pour chaque ligne un histogramme tel que celui défini à l'étape (b); (c2) dans chaque histogramme H(g), o g, O s g O; (c3) pour chaque valeur de niveau de gris, on additionne le nombre de valeurs go satisfaisant aux condi- tions définies à l'étape (c2) relevées dans tous les histogrammes; (c4) on choisit pour seuil S la valeur de niveau de gris pour laquelle le total obtenu à l'issue de l'étape (c3) est maximal. 6. Procédé selon la revendication 1 ou 2, suivant lequel, à l'étape (c), (cl) on établit pour chaque ligne un histogramme tel que celui défini à l'étape (b); (c2) dans chaque histogramme H(g), o g, O s g additionne le nombre de valeurs go satisfaisant aux condi- tions définies à l'étape (c2) relevées dans tous les histogrammes; (c4) on choisit pour seuil S la valeur de niveau de gris pour laquelle le total obtenu à l'issue de l'étape (c3) est maximal. 7. Procédé selon l'une quelconque des revendications 1 à 6, suivant lequel on effectue les étapes (a) à (f) pour chaque ensemble de 8 lignes contiguës de l'image. - 15 8. Procédé selon l'une quelconque des revendications 1 à 7, suivant lequel on extrait des inscriptions consistant en des traits verticaux, respectivement horizontaux, sous la forme de polygones verticaux, respectivement horizontaux.