Brevet FR2662835A1 — publié le 19911206

La présente invention concerne un appareil pour la détection de formes dans une image en temps réel. Elle s' appuie sur le principe consistant, sur une image seuillée, à affecter en permanence à chaque forme présente dans l'image un état déterminé à partir de deux informations - son état à la ligne précédente, - sa largeur dans la ligne courante, le nouvel état étant donné par une fonction de transition telle que état t = trans (état n,? , largeur) Cette fonction de transition est réalisée au moyen d'une mémoire RAM. La fonction de transition est établie selon les formes que l'on désire détecter, puis chargée dans la mémoire RAM qui n'est ensuite utilisée qu en lecture. Selon ce principe, on détecte la présence d'une forme s'étendant sur un nombre de lignes quelconque tout en ne mémorisant les états que d'une seule ligne, de sorte qu'il n'y a besoin d'aucun stockage global de l'image. De ce fait l'analyse d'image s effectue donc "à la volée", en temps réel, à mesure de l'entrée du signal vidéo de balayage, et elle ne nécessite la mise-en-oeuvre que de peu de moyens. Comme, dans une ligne donnée de l'image analysée, se succèdent de nombreuses formes différentes un état est associé à chacune de ces formes et des moyens séquenceurs sont alors prévus pour détecter la continuité d'une forme, la fin d'une forme et les débuts d'une nouvelle forme. L'appareil de détection de formes selon la présente invention, mettant en application le principe indiqué ci-avant, comprend les éléments suivants - un moyen de segmentation ou de seuillage placé sur le signal d'entrée et, selon le seuil de celui-ci, attribuant un signal "classe" suivant la couleur du pixel, - un moyen de comptage de largeur, conçu pour compter les pixels de même classe et pour être remis à zéro chaque fois que le signal "classe" issu du moyen de segmentation ou de seuillage change - un moyen de détection de transition, conçu pour détecter le long de la ligne chaque limite entre classes, - une mémoire RAM de fonction de transition délivrant à chaque changement de formes, à partir d'une information d'état de forme à la ligne n-1 et d'une information de largeur de forme à la ligne n, provenant du moyen de comptage de largeur, une information d'état de forme à la ligne n, - une mémoire de formes, du type premier entré-premier sorti Fifo, conçue pour mémoriser les états des formes d'une ligne reçus de la mémoire RAM ainsi que les positions dans la ligne du pixel de chacune de ces formes situé le plus à droite, et pour restituer ces états des formes à la mémoire RAM pour l'établissement des formes de la ligne suivante, - un registre d'état relié à la mémoire de formes Fifo et conçu pour bloquer la valeur de l'état de forme à la ligne n-l , sous l'action d'un signal de verrouillage, lorsque la forme sur la ligne n-l se termine plus à gauche qu'à la ligne n, - un compteur de position, qui assure le comptage des pixels sur chaque ligne et qui est remis à zéro à chaque début de ligne, - un registre d'indice, pouvant être une mémoire, dans lequel on stocke chaque valeur d'état ayant permis de reconnaître une forme, ainsi que la position correspondante et aussi le numéro de ligne, - un moyen séquenceur, se présentant sous la forme d'un automate assurant le contrôle des autres éléments, en recevant les indications de position sur la ligne n (provenant du compteur de position) et sur la ligne n-1 (provenant de la mémoire de formes) et les indications de transition en provenance du détecteur de transition, et en fournissant les commandes d'écriture et de lecture à la mémoire de formes, la commande de verrouillage du registre d'état, et la commande d'initiation uu registre d'indice. Avantageusement, on dispose entre le registre d'état et la mémoire RAM de fonction de transition un multiplexeur relié au moyen séquenceur et conçu, sous l'action d'un signal émis par ce dernier indiquant l'apparition d'une nouvelle forme, pour fournir à la mémoire RAM de fonction de transition non pas l'information sur l'état de forme effectif sur la ligne précédente, mais un état de forme fictif. Selon une variante dite "asynchrone" de l'appareil selon l'invention, utilisable si le taux de transitions dans l'image est inférieur à une transition pour quatre pixels ce qui est généralement le cas, on peut disposer d'un débit d'entrée nettement supérieur. Il convient alors d'ajouter une mémoire de formes Fifo supplémentaire qui, pour chaque transition noir-blanc ou blanc-noir dans le signal d'entrée, mémorise la position du pixel dans la ligne ainsi que la distance mesurée depuis la dernière transition rencontrée. Le reste du fonctionnement est le même, sauf que le moyen séquenceur est également chargé de commander la lecture des transitions dans la mémoire de formes Fifo supplémentaire sous la condition évidente qu'au moins une transition soit présente dans cette mémoire. Avec cette disposition, au lieu d'être sollicité à chaque pixel, le tableau de transition ne l'est plus que pour les pixels utiles de l'image c'est-à-dire ceux qui contiennent une transition. La vitesse limite de fonctionnement de l'appareil devient alors un nombre de transitions par seconde et se trouve donc largement accrue. En outre, dans le cas de problèmes complexes de reconnaissance de formes, il peut s'avérer impossible de programmer une seule mémoire RAM de fonction de transition pour l'ensemble des cas de figure. On peut alors multiplier l'ensemble constitué par la mémoire de fonction de transition, la mémoire de formes Fifo, le registre d'état et le multiplexeur, le reste des éléments étant commun, et programmer de façons différentes et appropriées les mémoires de fonction de transition. L'appareil selon l'invention comporte des applications très diverses parmi lesquelles on citera, sans caractère limitatif - le suivi de trajectoires d'objets dans l'espace, dont on peut faciliter la recherche en y collant des mires de forme et de couleurs déterminées, - le contrôle de qualité dans l'industrie, en vérifiant la conformité d'un objet à un modèle, - en matière musicale, le suivi des positions des doigts de la main dans l'espace devant une caméra, à partir desquelles peuvent être calculés des paramètres musicaux appliqués à des synthétiseurs. Pour bien faire comprendre l'appareil selon l'invention on en décrira ci-après, à titre d'exemples sans caractère limitatif, une forme d'exécution préférée ainsi qu'une variante, en référence au dessin schématique annexé dans lequel la figure 1 est un schéma synoptique montrant les différents éléments d'un appareil selon l'invention pour la détection de formes dans une image la figure 2 est un schéma synoptique montrant les divers éléments d'une variante de l'appareil de la figure 1 ; la figure 3 est un schéma- montrant l'application de l'appareil selon l'invention à la détection dans une image d'une forme de triangle ; et la figure 4 est un schéma montrant l'application de l'appareil selon l'invention à la détection d'une suite de formes dans une image. En référence à la figure 1, l'appareil selon l'invention comporte un élément de seuillage 1, recevant le signal vidéo de balayage, qui selon que ce signal est inférieur ou supérieur au seuil considère que le pixel est noir ou blanc et délivre un signal "classe" constitué d'un seul bit. L'élément de seuillage 1 est relié d'une part à un compteur de largeur 2, qui compte les pixels d'une même classe et qui est remis à zéro chaque fois que le signal "classe" change, et d'autre part à un détecteur de transition 3 qui détecte les limites entre classes le long de la ligne.Le compteur de largeur 2 est relié à une entrée 4 d'un élément de fonction de transition 5, constitué par une mémoire RAM, pour fournir à celui-ci une information de largeur de forme, alors que la sortie de l'élément 5 est reliée à une entrée 6 d'une mémoire de formes de type Fifo 7, conçue pour mémoriser les états de formes, ainsi que la position dans la ligne du pixel situé le plus à droite de la forme. Une sortie 8 de la mémoire de formes 7 est reliée à l'entrée d'un registre d'état 9 à laquelle elle fournit une information d'état de forme à la ligne n-l, ce registre d'état permettant de bloquer l'information d'état de forme à la ligne n-l, sous le contrôle d'un signal de verrouillage, lorsque la forme sur la ligne n-l se termine plus à gauche que sur la ligne n.La sortie du registre d'état 9 est reliée à une entrée 10 d'un multiplexeur 11 dont le rôle est de fournir à une seconde entrée 12 de l'élément de fonction de transition soit l'information d'état de forme effectif à la ligne n-l, soit une information d'état de forme fictif en cas d'apparition d'une nouvelle forme. On a schématisé en 13 un compteur de position, conçu pour compter les pixels sur chaque ligne et remis à zéro à chaque début de ligne, dont la sortie est reliée à une seconde entrée 14 de la mémoire de formes 7 à qui elle fournit l'information relative à la position dans la ligne n du pixel le plus à droite dans la forme. La sortie du compteur de position 13 est également reliée à une entrée 15 d'un séquenceur 16, constitué par un petit automate assurant le contrôle de l'ensemble des éléments du dispositif. Une seconde entrée 17 du séquenceur 16 est reliée à une seconde sortie 18 de la mémoire de formes 7, fournissant une information sur la position dans la ligne n-l du pixel le plus à droite de la forme, alors qu'une troisième entrée 19 du séquenceur 16 est reliée à la sortie du détecteur de transition 3. Des sorties 20 et 21 du séquenceur 16 sont reliées à des entrées 22, 23 de la mémoire de formes 7 pour commander sélectivement l'écriture de l'état de forme à la ligne n et la lecture de l'état de forme à la ligne n-l stocké, respectivement. Une autre sortie 24 du séquenceur 16 est reliée à une entrée 25 du registre d'état 9 pour commander sélectivement le blocage de celui-ci, alors qu'une autre sortie encore 26 du séquenceur 16 est reliée à une entrée 27 du multiplexeur 11 pour fournir à celui-ci l'information de commande relative à l'apparition d'une nouvelle forme. Une autre entrée 28 du multiplexeur 11 est reliée à la sortie de l'élément de seuillage 1. Enfin on a représenté en 29 un registre d'indice dont deux entrées 30, 31 sont reliées respectivement aux sorties 8, 18 de la mémoire de formes 7, et dont une troisième entrée 32 est reliée à une sortie 33 du séquenceur 16. Lorsqu'une forme a été reconnue sur certaines valeurs d'état, on stocke dans ce registre 29, constitué par une mémoire, la valeur de Tétat et la position. On peut aussi stocker dans ce registre, d'une façon non représentée, le numéro de ligne. La sortie du registre d'indice 29 est reliée à un microprocesseur (non représenté) afin d'exploiter les données stockées dans ce registre. On expliquera maintenant le fonctionnement du dispositif et on expliquera d'abord, en relation avec la figure 3, le principe de fonctionnement≈pour la détection dans l'image d'une forme unique .en triangle. Pour cela on a représenté sur l'écran la forme en triangle et on a matérialisé les lignes successives de balayage, se succédant de haut en bas, ce balayage s'effectuant de la gauche vers la droite sur chaque ligne. On voit ainsi que la largeur de la forme sur la ligne 1 est 1 (correspondant à 1 pixel), que cette largeur est de 3 (3 pixels) sur la ligne 2, de 5 (5 pixels) sur la ligne 3 et de 7 (7 pixels) sur la ligne 4 La ligne 0 est arbitrairement considérée comme étant dans l'état 1, et on décide que la ligne 1 devra être dans l'état 11, la ligne 2 dans l'état 12, la ligne 3 dans l'état 13 et la ligne 4 dans l'état 14, le choix des numéros d'état étant tout à fait arbitraire.La fonction de transition réalisée par l'élément de fonction de transition 5 étant du type - état de forme à la ligne n = fonction de transition (état de forme à la ligne n-l, largeur de forme à la ligne n), ce qu'on écrit état n = trans (état n-l, largeur) la fonction de transition sera donc telle que trans (état = 1, largeur = 1) = 11 trans (état = 11, largeur = 3) = 12 trans (état = 12, largeur = 5) = 13 trans (état = 13, largeur = 7) = 14 les autres valeurs de la fonction de transition seront mises par exemple à 0. Ainsi, si l'état en un point quelconque de l'image analysée vaut 14, on est alors certain de la présence d'un triangle à cet endroit. On peut donc détecter la présence d'une forme s'étendant sur un nombre de lignes quelconque, tout en ne mémorisant les états que d'une seule ligne. I1 n'y a donc besoin d'aucun stockage global de l'image et on comprend l'avantage considérable que cela procure, l'analyse d'image s'effectuant "à la volée", en temps réel, à mesure de l'entrée du signal vidéo et ne nécessitant la mise-en-oeuvre que de peu de moyens. En référence à la figure 4 on donnera maintenant une explication plus complète du fonctionnement du dispositif, lorsque dans une ligne donnée se succèdent de nombreuses formes différentes. Dans ce cas, un état est associé à chacune de ces formes et le séquenceur 16 doit alors détecter la continuité d'une forme, la fin d'une forme et le début d'une nouvelle forme. Comme on l'a représenté sur cette figure le balayage s'effectue par pixels croissants vers la droite (32 pixels par ligne), puis par lignes croissantes vers le bas. Quand le balayage arrive au point A en bout de la ligne 1, l'état de la seule forme I présente, blanche et de largeur 32, est stocké dans la mémoire de formes 7. Sur la ligne 2, à l'arrivée du balayage au point B, le séquenceur 16 constate que le segment blanc de 6 pixels se terminant en ce point continue la forme I. L'élément de fonction de transition calcule l'état en ce point c'est-à-dire état I = trans (état I, largeur 6) et cet état est stocké dans la mémoire de formes 7. Au point C le segment noir de 4 pixels est le début d'une nouvelle forme II et l'élément de fonction de transition calcule état II = trans (état II = 1, largeur 4) l'état = 1 est un état fictif fourni par le multiplexeur 11 et imposé par le séquenceur 16 à partir de sa sortie 26 annonçant le début d'une forme noire. Au point D, fin de la deuxième ligne, on a une troisième forme III qui est la suite de la forme I. Sur la ligne 3 les trois formes I, II et III se continuent. A la ligne 4, au point E, on a une continuation de la forme II. Au point F on a l'apparition d'une nouvelle forme blanche IV dont l'état est état IV = trans (état IV = 2, largeur 2) l'état = 2 étant encore un état fictif imposé par l'apparition d'une nouvelle forme, cette valeur fictive étant 2 pour la forme blanche au lieu de 1 pour la forme noire. Au point G apparalt d'une forme V dont l'état est état V = trans (état II, largeur 3) puisqu'elle continue la forme II. Aux points H et J on verra apparaltre de nouvelles formes noires, etc A la figure 2 on a représenté une variante du dispositif selon l'invention, utilisable si le taux de transition dans l'image est inférieur à une transition pour quatre pixels, en autorisant alors un débit d'entrée nettement supérieur.Pour cela on utilise une mémoire Fifo supplémentaire 33, désignée comme mémoire de transitions, qui est disposée entre le compteur de largeur 2 et la mémoire de fonction de transition 5. Cette mémoire de transitions 33 est également reliée à la sortie de l'élément de seuillage 1, du compteur de position 13 et du détecteur de transitions 3, ainsi qu'à une sortie 34 de commande d'écriture du séquenceur 16. Une sortie 35 de la mémoire de transitions 33 est reliée au multiplexeur 11. Avec cette disposition, la mémoire de transitions 33 mémorise, pour chaque transition noir-blanc ou blanc-noir dans le signal d'entrée, le numéro du pixel dans la ligne (c'est-à-dire la position de ce pixel) ainsi que la distance mesurée depuis la dernière transition rencontrée, c' est-à-dire la largeur du segment noir ou blanc. Le reste du fonctionnement est similaire à celui du dispositif de la figure 1, si ce n'est que le séquenceur 16 est chargé d'une tâche supplémentaire consistant à lire les transitions stockées dans la mémoire de transitions 33, à la condition bien sûr qu'au moins une transition soit présente dans- la mémoire 33. Ainsi, au lieu d'être sollicitée pour chaque pixel, l'élément de fonction de transition 5 ne l'est plus que pour les pixels utiles de l'image, c'est-à-dire ceux qui contiennent une transition.La vitesse limite de fonctionnement est donc accrue puisqu'elle ne correspond plus à un nombre de pixels par seconde, mais à un nombre de transitions par seconde. On comprendra que la description ci-dessus a été donnée à simple titre d'exemple, sans caractère limitatif, et que des adjonctions ou des modifications constructives pourraient y être apportées sans sortir du cadre de l'invention. En particulier, on a décrit par simplification. l'utilisation, sur le signal d'entrée, d'un élément de seuillage 1 fournissant un signal "classe" (considérant le pixel noir ou blanc) constitué d'un seul bit. Toutefois, sans sortir du cadre de l'invention on pourrait remplacer l'élément de seuillage par un élément de segmentation, plus élaboré, susceptible de "segmenter" l'image suivant des critères de couleur et de texture par exemples, et coder la classe à laquelle appartient le pixel sur plusieurs bits (par exemple 1 = noir, 2 = rouge, 3 = vert, etc ....). REVENDICATIONS. 1. Appareil de détection de formes dans une image en temps réel utilisant un procédé consistant à établir et mémoriser un fichier électronique représentatif des états des formes rencontrées lors d'un balayage d'une ligne de l'image, au cours du traitement de la ligne suivante de l'image à établir un tableau électronique de segments relatif aux caractéristiques géométriques de position et de couleur des segments de l'image sur la ligne et, à partir à la fois dudit fichier électronique de formes relatif à la ligne précédente et dudit tableau électronique de segments relatif à la ligne actuelle, à établir électroniquement un nouveau fichier électronique de formes exploitable au cours du balayage de la ligne suivante, caractérisé en ce qu'il comprend les éléments suivants - un élément de classement (1) du signal d'entrée de balayage, attribuant une classe à chaque pixel en fonction de sa couleur, - un compteur de largeur (2) recevant l'information de classe délivrée par l'élément de classement (1) et fournissant une information de largeur constituée par le nombre de pixels successifs d'une même classe, - un élément de fonction de transition (5) dont les entrées reçoivent une information relative à l'état de forme rencontré dans la ligne précédente et l'information de largeur dans la ligne actuelle fournie par le compteur de largeur, et dont la sortie fournit une information relative à l'état de forme existant dans la ligne actuelle, - un élément de mémoire de formes (7) recevant et stockant ladite information d'état de forme dans la ligne actuelle et fournissant audit élément de fonction de transition (5) ladite information relative à l'état de forme dans la ligne précédente, et - un élément séquenceur (16) relié audit élément de mémoire de formes (7) pour contrôler sélectivement, dans cette dernière, la lecture de l'information d'état de forme dans la ligne précédente et l'écriture de l'information d'état de forme dans la ligne actuelle. 2. Appareil selon la revendication 1, caractérisé en ce que ladite information d'état de forme dans la ligne précédente est fournie à l'entrée dudit élément de fonction de transition (5) par l'intermédiaire d'un registre d'état (9) disposé à la sortie de la mémoire de formes (7) et d'un multiplexeur (11) recevant les sorties du registre d'état (9) et de l'élément de classement (1) alors que sa sortie est connectée à l'entrée de l'élément de fonction de transition (5), ledit registre d'état (9) étant contrôlé par l'élément séquenceur (16) pour bloquer la valeur de l'état de forme dans la ligne précédente lorsque la forme sur la ligne précédente se termine plus à gauche que sur la ligne actuelle, et ledit multiplexeur (11) étant contrôlé par le séquenceur (16) pour fournir à l'élément de fonction de transition (5) un état de forme dans la ligne précédente fictif à l'apparition d'une nouvelle forme dans la ligne actuelle. 3. Appareil selon la revendication 1 ou la revendication 2, caractérisé en ce qu'il comprend un élément détecteur de transition (3) qui reçoit l'information de classe fournie par l'élément de classement (1) et détecte les limites entre classes le long de la ligne pour fournir à l'élément séquenceur (16) une information relative à l'apparition d'une transition. 4. Appareil selon l'une quelconque des revendications précédentes comprenant un compteur de position (13), comptant les pixels le long de la ligne, qui fournit à la mémoire de formes (7) pour stockage et au séquenceur (15) une information de position le long de la ligne actuelle, alors que la dite mémoire de formes (7) fournit à l'élément séquenceur (15) une information de position le long de la ligne précédente. 5. Appareil selon la revendication 4, caractérisé en ce qu'il comprend un registre d'indice (29) relié aux deux sorties de la mémoire de formes (7) pour recevoir des informations d'état de forme dans la ligne actuelle et des informations de position le long de la ligne actuelle pour emmagasiner, sous le contrôle de l'élément séquenceur (16), chaque valeur d'état ayant permis la reconnaissance d'une forme ainsi que la position correspondante. 6. Appareil selon l'une quelconque des revendications précédentes, caractérisé en ce que ledit élément de fonction de transition (5) est une mémoire RAM. 7. Appareil selon l'une quelconque des revendications précédentes, caractérisé en ce que ledit élément de classement (1) est un dispositif de seuillage distinguant entre un pixel noir et un pixel blanc et fournissant un signal de classe constitué d'un seul bit. 8. Appareil selon l'une quelconque des revendications 1 à 6, caractérisé en ce que ledit élément de classement (1) est un dispositif assurant une segmentation de l'image selon des critères tels que la couleur et la texture, et codant la classe à laquelle appartient le pixel sur plusieurs bits. 9. Appareil selon l'une quelconque des revendications 3 à 8, caractérisé par une mémoire de transitions (33) recevant l'information de classement provenant de l'élément de classement (1) et l'information de largeur provenant du compteur de largeur (2) et transmettant ces informations respectivement au multiplexeur (11) et à l'élément de fonction de transition (5), alors qu'elle reçoit une information de position sur la ligne à partir du compteur de position (13), la commande d'écriture dans ladite mémoire de transitions (33) étant assurée par le détecteur de transitions (3) alors que la commande de lecture dans cette mémoire de transitions (33) est assurée par l'élément séquenceur (16), de sorte que pour chaque transition rencontrée ladite mémoire (33) mémorise la position du pixel dans la ligne et la distance mesurée depuis la dernière transition rencontrée.