Brevet FR2552605A1 — publié le 19850329

Domaine technique : Télécopie. Etat de la technique : Dans le domaine de la télécopie, de nombreux dispositifs ont été proposés depuis la fin des années 1970, fondés sur le prin cipe de la reconnaissance des formes, oui permettent une réduction notable du débit de transmission par rapport aux dispositifs plus traditionnels de télé- copie numerique. Ce sont les dispositifs de PRITT et all. (2) SEGEN et JOHN- SEN (3), JOLY et ROMEO (4). Ces dispositifs obéissent tous au schéma de la figure 1.Le principe en est le suivant L'inage est codée numériquement par le lecteur d'image (1) ; les symboles (ensemble connexe de noirs de taille non limitée) et éventuellement les graphismes (ensemble connexe de noirs de taille non limitée) sont extraits l'un après l'autre de l'image numérisée (2) ; cette phase est appelée phase d'extraction.Le résidu (s'il en existe) est codé directement par un procédé de télécopie numérique traditionnel ; les graphismes font l'obiet d'un codage indépendant ; enfin et surtout, les symboles extraits sont tout d'abord l'objet d'une reconnaissance pour ~a oir s ils ont déjà ete trouves au moins une fois dans l'image ; ils sont codés dans une mémoire d'image. la reconnaissance est faite en comparant le symbole à tous les symboles de la bibliothèque- mémoire re numérique contenant les images numérisées de toutes les formes de -symboles 'symboles-prototype" déjà rencontrés- Si une ressemblance est trouvée avec le le symbole-prototype x de la bibliothèque, le numéro du symbole-prototype ainsi que les co-rdonnées du symbole dans l'image sont codés (3.3) ; pour améliorer la vitesse de traitement, la comparaison à la bibilothèque est faite en deux temps Une première phase (3.1) de pré-reconnaissance permet de trier très rapidement, mais grossièrement, tous les symboles prototypes très différents de notre symbole ; une deuxième phase (3.2) de reconnaissance fine appelée "template matching" réalise une comparaison soigneuse mais couteuse de notre symbole avec les symbe'e-prototypes les plus ressemblants ; les symbole-prototypes de la bi biotheque sont ensuite codés (3.4.) ; l'ensemble des codes sortant des blocs (3.3), (3. ), (4) et (5) sont ensuite regroupés par un organe de formation du message (6) et expédiés vers le récepteur de télécopie via la voie téléphonique. Les trois procédés proposés jusqu'a présent sont très couteux en temps de calcul d'crdinateur et celui-ci risque d'être très largement supérieur au temps de transmission proprement dit. Le cout élevé du traitement de l'image pour en extraire son code est lié essentiellement à la conception de l'organe d'extraction (2) qui effectue l'extraction des symboles les uns après les autres, ce qui oblige à de nombreuses et coûteuses manipulations de l'image. Le dispositif décrit ici a pour but de remédier à cet inconvénient afin de diminuer les temps de traitement de l'image avant son expédition. Principe du dispositif : (cf. Figures 1 et 2) (1) Un lecteur linéaire d'image pouvant être par exemple un lecteur de type CCD (Charge CoupledDevice) qui se déplace de haut en bas (ou de bas en haut) de l'image selon un pas constant et qui fournit pour chaque ligne-lue une séquence de bits représentant la succession -selon un pas horizontal constant- des noirs et blancs (bit = 1 pour un noir, bit = o pour un blanc) avec éventuellement un signal de synchronisation en début de chaque ligne. (cf. figures 3 et 4). (2) Un extracteur fonctionnant itérativement ligne apyres ligne et composé comme suit (cf. Figure 2). (2.1) Une unité de conversion transformant à la ligne courante les si-; gnaux du lecteur d' image en une série d'informations stockées dans une mémoire tampon l-D. Ces informations constituent la représentation par longueur de zone : ce sont le nombre de zones rencontrées et pour chaque zone de noir rencontrée : l'abaisse abc du point le plus à gauche sur la ligne, la longueur 1 de noir (Figure 5). (2.2) Une unité de numérotation de zone qui adjoint au tableau précédent le numéro de la branche à laquelle appartient la zone, et qui choisit - si nécessaire- pour chaque branche un numéro d'état définissant le symbole auquel elle appartient (Figure 6). (2.3) Une unité de chargement qui stocke au fur et à mesure de la lecture dans une mémoire numérique,appelée mémoire d'image, l'information abcisse gauche, largueur de noire pour chaque numéro de zone à hauteur courant?, à compter de la hauteur de départ de la branche (cf. Figure 7). Ce mode de stockage en mémoire est appelé représentation par branche. Les états des branches sont stockés dans une mémoire spéciale, lorsque l'unité de numérotation de zone trouve absente une branche attendue, si cette branche est la dernière de son numéro d'état, elle déclanche une ålarme de fin de symbole. (cf. Figure 7). Les symboles n'apparaissent oas danslamémoire d'image comme un tout comme dans les autres méthodes (2), (3), (4), au contraire, les branches scnt distinctes,avec ua numéro d'état figurant leur appartenance à un symbole. Four lire un symbole en mémoire d' image, il faut connaltre son numéro d'état et tirer toutes les branches ayant ce numéro d'état, c'est l'ensemble de ces branches qui constitue le symbole. (3) Une unité de codage des symboles décompose de façon classique en (3.1), une unité de préreconnaissance et (3.2) une unité de "template mat ch ing". (3.1) Unité de préreccnnaissance : Celle-ci effectue sur chaque symbole de la bibliothèque stockée sous forme par branche, une comparaison de plus en plus fine avec le symbole disponible en mémoire. Sa mise en fonction est ef fectuée sur envoi d'une alar.rile symbole. Le principe de cette unité est de travailler directement sur les informations des branches constituant le symbole telles qu'elles apparaissent dans la moire d'image. La facilité du fonctionnement provient de ce que le symbole et son homologue recherché en bibliothèque se déduisent l'un de l'autre par une translation seulement et pas par une rotation ou une homothétie. L'unité lit en memoire d'image toutes les branches dont le numéro d'état est celui émis à l'instant de l'alarme. Ces branches sont celles du symbole à traiter. Une formule de réalisation préférentielle consiste en (1) comparer le hauteur du symbole, (2) comparer Je nombres de branches et leurs coordonnées de début et de fin, (3) comparer les abcisses de début et de fin des branches. L'unité de préreconnaissance permet ainsi de trier un maximum de symboles-prototype auxquels ne ressemble pas le symbole. Sur les autres symbolesprototype est appliqué l'unité de reconnaissance fine. (3.2) Unité de reconnaissance fine ("template-matching" ) Celle-ci compare, point à point, le symbole et le symbole-prototype et selon une réalisation particulière, n'accepte pas de variations de forme supérieure à un pas de quantification entre les deux symboles. A la suite du "template-matching", le dispositif peut répondre à la question de savoir si le symbole est nouveau ou est identique au symboleprototype nO i de la bibliothèque. Si le symbole n'a pas été reconnu, on stocke ses branches dans la bibliothèque selon le meme mode de stockage que la mémoire d'image. (3.3) et (3.4) Unités de codage Pcur chaque symbole on code, qu'il ait été reconnu ou pas dans la bibliothèque, son numéro dans la bibliothèque, ainsi que ses coordonnées dans l'image (3.3). Chaque symbole de la bibliothèque est codé parallèlement par l'unité de codage (3.4). Le codage est réalisé soit au fur et à mesure du traitement de l'image, scit une fois que l'image a été complètement traitée. orque la reconnaissance et le cokage du SyFw ole cnt été terminés, les branches correspondantes dans la mémoire d'image sont effacée ainsi que leur numéro et le numéro d'état de symbole. Les zones noires qui ne sont pas dans le sens de la hauteur ne rentrent pas dans le cadre des symboles. Elles peuvent, par exemple, faire l'objet d'un codage à titre de résidu (4) selon les méthodes connues de codage à deux dimensions (1), ou alors être codées en tant que graphismes (5). Elements innovatifs Le dispositif décrit ne diffère pas dans sa structure générale des au- tres dispositifs de télécopie à reconnaissance. Son originalité réside 1) dans son extracteur rapide susceptible de faire d'un seul coup l-'extraction de tous les symboles d'une ligne de texte d'un document dactylographié en codant l'image directement sous forme de sa représentation par branche. 2) Dans le choix de la représentation par branche qui est bien adaptée à la recornaissance et au codage des symboles typographiques répétitifs par l'unité de préreconnaissance qui compare directement les différentes branches du symbole se trouvant en mémoire d'image,avec les symboles-prototype déjà enregistrés dans la bibliothèque de symboles. BIBLIOGRAPHIE (1) G. Aaron - Codage bidimensionnel d'images monochromes pour la télécopie. Acta Electronica, 21, 1, 1978, pp39 - 53. (2) W.K. Pratt, P.J. Capitant, W.H. Chen, E.R. Hamilton, R.H. Wallis Combined Symbol Matching Facsimile Data Compression System. Proc. IEEE, Vol. 68, n 7, Juillet 1980. (3) J.Segen, O. Johnsen. Facsimile Compression by Pattern Matchir.g. Proc. Pattern Reccngnition and Image Processing. Juin 1982. Las Vegas, pp. 191-196. (4) P. Joly et F. Roméo. Présentation d'une méthode de compression d'images. Note tech- vue CNET I4T/PAA/OGE/TDT/818. Octobre 1982. LISTE DES FIGURES ET LEGENDES PLANCHE 1/4 : FIGURE 1 : Diagramme général du dispositif de télécopie à reconnaissance - (B. Bibliothèque). PLANCHE 2/4 : FIGURE 2 : Diagramme général de 11 extracteur itératif. (A * Alarme, ME : Mémoire d'état de branches, MI : Mémoire tampon l-D, TC : Tableau complet, TP : tableau complet à la ligne précédente). PLANCHE 3/4 FIGURE 3 : Représentation par longueur de zone (1 : Branche n 1, 2 : Branche n 2, 3 : abolisse gauche de la zone courante, 4 : longueur de la zone courante). FIGURE 4 : Codage binaire ligne par ligne en sortie du lecteur image. PLANCHE 4/4 FIGURE 5 : Mémoire tampon l-D FIGURE 6 : Tableau complet Légende commune à la figure 5 et à la figure 6 : 1 : Nombres de zones à la hauteur courante, 2 : abolisse gauche de la lèpre zone, 3 : longueur de la 1ère zone, 4 : abscisse gauche de la 2ème zone, 5 : longueur de la 2ème zone, 6 et 7 : numéros des branches. FIGURE 7 : Organisation de la mémoire d' image. (1 : numéro de branche, 2 : état, 3 : branche-départ, 4 : branche-arrivée, 5 : ordonne de début de branche, 6 : longueur de la branche, 7 : abolisse de début de branche, 8 : abolisse au point courant de la branche (abcisse relative), 9 longueur de zone au point courant de la branche). REVENDICATIONS 1. Procédé de reconnaissance de symboles figurant dans une image à coder, procédé selon lequel l'image est lue et numérisée, et les informations numériques représentatives des symboles sont comparées avec des informations stockées dans une bibliothèque de symboles prototypes constituée au fur et à mesure du codage de l'image, caractérisé en ce que - l'image est analysée ligne par ligne pour extraire des informations caractérisant les branches constitutives des symboles figurant sur l'image, et - les informations caractérisant les branches sont utilisées pour comparer chaque symbole extrait aux différents symboles déjà trouvés dans l'image et stockés dans la bibliothèque en tant que symboles prototypes. 2. Procédé selon la revendication 7, caractérisé en ce que les informations caractérisant chaque branche comprennent un ensemble de données représentant la forme de la branche et un numéro d'état correspondant au symbole extrait auquel appartient la branche. 3. Procédé selon la revendication 2, caractérisé en ce que chaque ligne d'image est analysée pour fournir une représentation de la ligne par zones correspondant à des parties de symboles lus sur l'image, un même numéro de branche est associé aux différentes zones qui sont sur des lignes successives et qui appartiennent à une même branche, et le numéro d'état est associé dynamiquement à chaque branche en fonction du symbole auquel elle appartient. 4. Procédé selon la revendication 3, caractérisé en ce que le même numéro d'état est associé aux branches constituant un même symbole, deux branches ayant le même numéro d'état appartenant à un même symbole. 5. Procédé selon l'une quelconque des revendications 3 et 4, caractérisé en ce que les informations Ca- ractérisant chaque branche d'un symbole extrait comprennent une ou plusieurs des informations représentant les caractéristiques qui figurent dans le groupe constitué par : le numéro de la branche, le numéro d'état correspondant au symbole, les coordonnées de début et de fin de la branche, la longueur de la branche, l'abscisse et la longueur de chaque zone faisant partie de la branche. 6. Procédé selon l'une quelconque des revendications 1 à 5, caractérisé. en ce que les symboles extraits sont comparés séquentiellement aux symboles prototypes en comparant des caractéristiques apparaissant dans leur représentation par branches et en appliquant à chaque fois une série de tests de complexité croissante. 7. Procédé selon la revendication 6, caractérisé en ce que la comparaison est effectuée, dans un premier stade, en comparant, selon un ordre de complexité croissante :la hauteur du symbole, le nombre de branches et leurs ordonnées de début et de fin, et les abscisses de début et de fin des branches. 8. Dispositif de reconnaissance de symboles destiné à la mise en oeuvre du procédé selon l'une quelconque des revendications 1 à 7, dispositif comportant un extracteur associé à un lecteur d'image pour fournir des informations numériques représentant les symboles lus sur une image à coder, une bibliothèque dans laquelle sont enregistrées des informations numériques représentant des symboles prototypes et qui est constituée au fur et à mesure du codage de l'image, et des moyens de comparaison entre les informations représentant les symboles extraits et-les informations représentant les symboles prototypes, caractérisé en ce que - l'extracteur est agencé de manière à analyser l'image ligne par ligne pour extraire des informations caractérisant les branches constitutives des symboles lus sur l'image, - une mémoire d'image reçoit les informations de l'extracteur pour mémoriser, pour chaque symbole extrait, les informations caractérisant les différentes branches constitutives du symbole, et - les moyens de comparaison sont reliés à la mémoire d'image pour permettre la reconnaissance de symboles par comparaison effectuée à partir des informations caractérisant les branches constituant les symboles. 9. Procédé de télécopie rapide selon lequel les symboles figurant dans une image à transmettre qui est lue et numérisée sont reconnus par comparaison avec des symboles prototypes stockés dans une bibliothèque constituée au fur et à mesure de l'analyse de l'image, et chaque symbole reconnu est converti sous forme d'une information comprenant un code identifiant le symbole-prototype correspondant et les coordonnées du symbole dans l'image, caractérisé en ce que le reconnaissance des symboles est effectuée suivant le procédé de l'une quelconque des revendications 1 à 7.