Brevet FR2507419A1 — publié le 19821210

PROCEDE ET DISPOSITIF D'EXTRACTION DE CONTOUZ D'OBJETS AU MOYEN D'UNE CAMERA VIDEO La présente invention a trait à un procédé d'extraction de contous d'objets et à un dispositif pour la mise en oeuvre de ce#procédé, en particulier dans la domaine de la robotique. Les performances des futurs robots industriels dépendront en grande partie de la qualité et de la rapidité du système de perception de leur environnement. Les caméras vidéo constituent des capteurs privilégiés en robotique, lorsque l'on sait maîtriser la grande quantité d'informations qui en est issue. Malheureusement, l'obtention de caractéristiques pertinentes nécessaires au centre de décision du robot demande souvent des temps de calcul relativement longs. C'est pour rémédier à ces inconvénients que se développent, à l'heure actuelle, des recherches ayant pour but d'élaborer et de mettre en oeuvre des algorithmes récursifs de traitement rapide d'images vidéo. Par ailleurs, l'évolution de la technologie des circuits intégrés a rendu possible l'implantation sous forme de logique cablée de certains algorithmes de traitement d'image. On connait des appareils conçus pour extraire des contours, mais ceux-ci ne donnent pas satisfaction. En effet, ces appareils nécessitent plusieurs passes et leur temps de traitement est long (de l'ordre de la seconde). Par ailleurs, les passes successives entraînent des problèmes d'incohérence entre les image#s mémorisées. Les algorithmes rencontrés dans ces appareils sont le plus souvent basés sur l'utilisation de la méthode du gradiant. La présente invention a pour objectif de rémédier à ces inconvénients et en particulier de fournir un procédé d'extraction de contours d'objets et un dispositif pour la mise en oeuvre de ce procédé, permettant des temps de traitement beaucoup plus courts et ne nécessitant qu'une seule passe. Un autre objectif de la présente invention est de fournir un dispositif notablement moins complexe que ceux de l'art antérieur et donc moins coûteux. A cet effet, le procédé conforme à l'invention pour extraire un contour d'objet à partir d'un signal video généré par une caméra consiste à: - analyser chaque point de l'image en vue de déterminer des points caractéristiques d'un changement de direction des contours des objets, -stocker dans une première mémoire la position de chacun de ces points caractéristiques, ligne par ligne, - stocker dans une seconde mémoire l'adresse correspondant à la position du point caractéristique précédant et/ou suivant sur une même colonne chacun des points caractéristiques en vue d'obtenir une information de chaînage, - ordonner les positions mémorisées des différents points caractéristiques dans l'ordre de parcours des contours en vue de générer des signaux représentatifs de ces contours et, - traiter lesdits signaux représentatifs des contours en vue de délivrer des signaux représentatifs de paramètres prédéterminés des objets. Afin de déterminer ces points caractéristiques, on prend en considération le point en cours d'analyse et trois points voisins, formant ainsi une fenêtre dans laquelle la position relative des points permet de déterminer une combinaison de signaux codés représentative du contour au niveau du point en cours d'analyse. Ces signaux codés sont mémorisés au fur et à mesure de leur rencontre lors du balayage puis extraits des mémoires dans l'ordre de parcours des contours. Le dispositif conforme à la présente invention en vue de la mise en oeuvre du procédé défini ci-dessus comprend essentiellement - une caméra vidéo et des moyens de codage /au moins deux niveaux de luminance, en particulier/ des signaux video selonlaeux niveaux correspona nt au flanc et au noir, - des moyens d'échantillonnage en vue de déterminer les points caractéristiques d'un changement de direction du contour, - des moyens de génération de fonctions de commande d'adressage, - des moyens de mémorisation des données représentatives des points caractéristiques de changement de direction du contour, - des moyens de traitement des données mémorisées dans l'ordre de parcours du contour et, - des moyens de calcul de paramètres caractéristiques des objets en vue de délivrer des signaux de commande aux unités de traitement des objets. D'autres caractéristiques du procédé d'extraction de contours d'objets et du dispositif pour la mise en oeuvre de ce procédé seront mises en évidence par la description ci-après en regard des dessins annexés, donnés à titre d'exemple non limitatif et dans lesquels - la figure 1 schématise une fenêtre de codage du contour au niveau d'un point courant dudit contour, - la figure 2 illustre les différentes configurations possibles et donne un exemple de leur codage, - la figure 3 est un schéma synoptique des différents circuits du dispositif selon l'invention et, - la figure 4 représente un exemple de contour d'objet obtenu. De façon classique, une caméra vidéo délivre un signal vidéo donnant sur un écran une image vidéo constituée d'une pluralité de points répartis en lignes et en colonnes. L'algorithme utilisé dans la présente invention permet une compression de données sur une image analysée en un seul balayage. A titre d'exemple, on utilise seulement la moitié de la trame; le nombre de points traités est alors de 256 x 256 soit 65 536 points ,ce qui correspond à un temps d'analyse de 250 nanosecondespar point. Le signal vidéo délivré par la caméra est numérisé pour chaque point selon deux niveaux de luminance (blanc ou noir) auxquels on attribue une valeur binaire 0 ou 1. La détection des points caractéristiques de changement de direction du contour s'effectue en comparant les informations de luminance relatives à quatre points voisins, à savoir le point en cours d'analyse et les trois points voisins situés sur la ligne et la colonne précédant immédiatement la ligne et la colonne du point en cours d'analyse. On forme ainsi une fenêtre de codage telle que celle schématisée à la figure 1. Sur cette figure, le point en cours d'analyse est le point V(i,j). Si les luminances des points V(i,j) et V(i-l,j) sont différentes, on peut conclure que le contour de l'objet passe entre ces deux points; de même, si les luminances des points V(i,j) et V(i,j-l) sont différentes, on peut conclure que le contour de l'objet passe entre ces deux points. On a alors , autour du pointV(i,j) un changement de direction du contour. La figure 2 donne toutes les possibilités de configuration de contour au niveau d'un point. Cependant, le dispositif ne prend en compte que douze configurations sur les seize configurations possibles car la cohérence entre le balayage horizontal et les lignes horizontales du contour simplifie la recherche du point caractéristique suivant situé sur la même ligne. Les combinaisons prises en compte doivent définir au moins une transition verticale de façon à obtenir une information de chaînage nécessaire pour surmonter les problèmes liés à l'incohérence entre la nature horizontale du balayage et la détection des parties verticales des contours. Pour chaque point caractéristique retenu, on mémorise une information de position (i,j), une information de chaînage permettant de le relier aux points qui l'entourent et une information sur la configuration du contour de l'objet au niveau de ce point. En ce qui concerne l'information de position, il n'est pas nécessaire de mémoriser les deux coordonnées i et j; en effet, puisque chaque point caractéristique définit un changement de direction, un point V(i,j) sera parfaitement défini si l'on connaît i ou j et s'il lui est associé un point suivant ou précédent, lui-même positionné par un j ou par un i. Le choix entre i et j est définipar le sens de parcours du contour mais il y a toujours alternance de i et de j d'un point au suivant. L'information de chaînage est immédiate pour les points caractéristiques dont le suivant ou le précédent est situé sur la même ligne. En effet, si l'on range le point V(i,j) à l'adresse courante ADC, le point suivant sera rangé à l'adresse ADC+1 et le point précédent à l'adresse ADC-1. Par contre, pour les points caractéristiques dont le précédent ou le suivant est situé sur la même colonne, l'information de chaînage est moins évidente puisque, lors du balayage, on peut rencontrer plusieurs points caractéristiques entre deux points caractéristiques situés de façon consécutive sur une même colonne. Pour résoudre ce problème, on utilise un registre indicateur adressé par le numéro j de la colonne analysée et comportant 256 places où l'on peut mémoriser une adresse ADC et un bit d'indexage. Un traitement particulier est nécessaire pour les points doubles, c'est-à-dire pour les points correspondant à la juxtaposition de deux contours élémentaires car ces points possèdent chacun un point précédent et un point suivant. Dans ce cas, on utilise une autre mémoire pour stocker les informations relatives à ce type de point. Enfin, il est également nécessaire de repérer les points de début de contour. Pour les contours pleins, les points de combinaison (0001) seront des points de début de contour s'ils sont validés par un point de combinaison (0010) situé sur la même ligne. De même, pour les contours vides, les points de combinaison (1110) seront des points de début de contour s'ils sont validés par des points de combinaison (1101). On utilise une autre mémoire pour stocker ces infornations en vue d'initialiser le chaînage relatif à chaque objet. De plus, à chaque début de contour validé, on associe l'adresse du dernier point en attente de chaînage vertical en vue de positionner entre eux les différents objets. La figure 3 représente un schéma synoptique des différents circuits du dispositif selon l'invention. Sur cette figure, on peut voir en 1 une caméra vidéo à laquelle sont associés, de manière classique, un écran 2, un circuit 3 de base de temps et un circuit 4 de balayage lignes et colonnes. Le signal vidéo délivré par la caméra est numérisé dans un circuit de codage 5 suivant deux niveaux de luminance correspondant au blanc et au noir. Les signaux numérisés sont acheminés vers des moyens d'échantillonnage comprenant un registre à décalage 6 dont le rôle est de retarder la ligne précédant la ligne en cours d'analyse et un circuit d'échantillonnage 7 dont le rôle est de remettre en phase et de mémoriser pendant la durée d'un cycle les quatre signaux V(i,j), V(i-l,j), V(i,j-l) et Y(i-l,j-l) définissant la fenêtre d'échantillonnage. Ces quatre signaux sont ensuite délivrés à un circuit 8 de génération de fonctions de commande d'un circuit d'adressage 9 des différen#tes mémoires. En 10 est représentée la mémoire de stockage de la position i ou j de chacun des points caractéristiques, en 11 la mémoire de stockage de l'adresse correspondant à la position du point caractéristique précédant et/ou suivant chacun des points caractéristiques, en 12 la mémoire de stockage de la position des points de début de contour et en 13 la mémoire de stockage de la position des points doubles. Ces mémoires sont reliées d'une part à un registre 14 marqueur des points en attente de chainage vertical en vue d'ordonner les positions mémorisées des différents points caractéristiques dans l'ordre de parcours du contour et d'autre part à un micro-processeur 15 de traitement des données différées et un ordinateur 16 par l'intermédiaire d'opérateurs cablés 18. Un écran 17, relié au micro-processeur 15 permet le controle de la bonne marche du dispositif. On peut, en fait, utiliser plusieurs micro-processeur 15. La figure 4 donne un exemple de contours d'ob- jets. Toutes les données ayant été stockées dans les différentes mémoires, on ordonne les points caractéristiques dans l'ordre de parcours du contour. L'initialisation des contours s'effectue à partir de la mémoire 13 des débuts de contour. Chaque adresse de cette mémoire pointe sur l'adresse de la position i ou j d'un point de début de contour qui pointe sur l'adresse de la mémoire 11 des points suivants et/ou précédents. En suivant le chaînage, on remplit une mémoire de copie en rangeant dans des mémoires consécutives la suite des coordon nées i et j alternés. On répète l'opération pour chaque début de contour jusqu'à ce que la mémoire de début de contour soit vide. Chaque objet est numéroté et on lui affecte une indication de contour plein ou vide. On calcule ensuite les pa ramètres nécessaires au traitement ultérieur des objets. Ces paramètres sont par exemple le centre de gravité, la surface, le périmètre, le moment d'inertie, la surface du carré dans lequel peut s'inscrire l'objet, les rayons maximum et minimum des objets etc.... Les performances obtenues avec le dispositif selon l'invention sont nettement supérieures à celles des appareils de l'art antérieur puisque le temps d'extraction est de moins de 1/10 sec au lieu de la seconde. De plus, l'utilisation de micro-processeur en tranche et de logiques cablées peut accroitre ces performances dans un rapport au moins égal à 10. Le dispositif peut être construit en éléments modulaires relativement simples - module de synchronisation de la caméra, - module de numérisation 5 du signal vidéo, - module de génération des index de lignes et de colonnes i et j, - module séquenceur comprenant le registre à décalage 6 dans lequel le décalage est obtenu par exemple à partir de deux signaux de phases différentes, générés par des translateurs discrets et le circuit 7 constitué par exemple par un registre parallèle, - module 8 de génération des fonctions comprenant par exemple une mémoire morte, - module 9 de génération des adresses mémoires comportant essentiellement des compteurs, - module de mémoires comprenant les mémoires vives 10, 11, 12 et 13, - - module marqueur comprenant le registre 14 des points en attente de chaînage, constitué essentiellement par une mémoire vive et - module comprenant le ou les micro-precesseur(s) 15 et les opérateurs cablés 18. Enfin, de nombreuses modifications pourraient être apportées car l'invention ne se limite pas aux termes de la description qui précède mais en comprend au contraire toutes les variantes. REVENDICATIONS 1. Procédé d'extraction de contours d'objets au moyen d'une caméra délivrant un signal vidéo définissant une image constituée de points répartis en lignes et en colonnes, caractérisé en ce que - on analyse chaque point de l'image en vue de déterminer des points caractéristiques d'un changement de direction des contours des objets, - on stocke dans une première mémoire (10) la position de chacun de ces points caractéristiques, ligne par ligne, - on stocke dans une seconde mémoire (11) l'adresse correspondant à la position du point caractéristique précédant et/ou suivant sur une même colonne chacun des points caractéristiques#, en vue d'obtenir une information de chaînage, - on ordonne les positions mémorisées des différents points caractéristiques dans l'ordre de parcours des contours en vue de générer des signaux représentatifs de ces contours et, - on traite lesdits signaux représentatifs des contours en vue de délivrer des signaux représentatifs de para mètres prédéterminés des objets. 2. Procédé d'extraction de contours d'objets selon la revendication 1, caractérisé en ce que, pour déterminer les points caractéristiques d'un changement de direction des contours des objets - on prend en considération le signal aux instants correspondant au point en cours d'analyse et aux trois points voisins situés sur la ligne et/ou sur la colonne précédant immédiatement la ligne et la colonne du point en cours d'analyse et, - on numérise ce signal selon deux niveaux de luminance correspondant à la présence ou à l'absence d'objets en vue d'obtenir une combinaison de signaux codés représentative du contour des objets au niveau du point en cours d'analyse. 3. Procédé d'extraction de contours d'objets selon la revendication 2, caractérisé en ce que, à partir de la combinaison de signaux codés représentative des contours d'objets au niveau du point en cours d'analyse, on génère des fonctions de commande d'adressage de la première mémoire (10), de stockage de la position des points caractéristiques d'un changement de direction et de la seconde mémoire (rl) de stockage de l'adresse correspondant à la position du point caractéristique précédant et/ou suivant chacun des points caractéristiques, situé sur la même colonne, en vue d'éliminer les combinaisons de signaux codés ne correspondant pas à un point caractéristique de changement de direction du contour. 4. Procédé d'extraction de contours d'objets selon la revendication 1, caractérisé en ce que, pour mémoriser la position de chacun des points caractéristiques, on mémorise soit le numéro de la ligne si le point caractéristique suivant est situé sur la même ligne, soit le numéro de la colonne si le point caractéristique suivant est situé sur la même colonne. 5. procédé d'extraction de contours d'objets selon l'une des revendications 1 à 4, caractérisé en ce que l'on stocke dans une troisième mémoire (12) la position des points de début de contour en vue d'ordonner les positions mémorisées des points caractéristiques. 6. Procédé d'extraction de contours d'objets selon l'une des revendications 1 à 5, caractérisé en ce que l'on stocke dans une quatrième mémoire (13) la position des points doubles en vue de choisir un sens de parcours de ces points lors de l'ordonnancement des positions mémorisées des points caractéristiques. 7. procédé d'extraction de contours d'objets selon la revendication 1, caractérisé en ce que l'on met en attente dans une cinquième mémoire (14) la position des points caractéristiques suivis et/ou précédés d'un autre point carac téristique situé sur la même colonne et rencontrés au cours de l'analyse en vue de les restituer dans l'ordre de parcours des contours pour l'ordonnancement des positions mémorisées de ces points. 8. Dispositif d'extraction de contours d'objets pour la mise en oeuvre du procédé selon l'une des revendications 1 à 7, caractérisé en ce qu'il comprend - une caméra vidéo (1) adaptée pour délivrer un signal vidéo définissant une image des objets constituée de points répartis en lignes et en colonnes, - des moyens (5) de codage de ces signaux vidéo selon au moinsdeux niveaux de luminance, agencés à la sortie de la caméra (1), - des moyens (6,7) d'échantillonnage adaptés, pour chaque point des contours, pour sélectionner les signaux codés représentatifs de plusieurs points situés sur des lignes et sur des colonnes voisines de celles du point considéré, en vue de délivrer une combinaison de signaux codés représentative du contour de l'objet au niveau du point considéré, - des moyens (8) de génération de fonctions de commande d'adressage adaptés pour commander la mise en mémoire des données représentatives des points caractéristiques de changement de direction des contours à partir desdites combinaisons de signaux codés, - des moyens (10, 11, 12, 13, 14) de mémorisation desdites données représentativ#es des points caractéristiques de changement de direction des contours, - des moyens (15) de traitement des données mémorisées adaptés pour ordonner les positions mémorisées des différents points caractéristiques dans l'ordre de parcours des contours et - des moyens (16,18) de calcul et de traitement des données mémorisées, adaptés pour délivrer des signaux de commande à des unités de traitement ultérieur des objets. 9. Dispositif d'extraction de contours d'objets selon la revendication 8, caractérisé en ce que les moyens d'échantillonnage comprennent un registre à décalage (6) et un circuit (7) d'échantillonnage adapté pour sélectionner les signaux codés représentatifs de quatre points, à savoir le point considéré et les trois points situés sur la ligne et/ou sur la colonne précédant immédiatement la ligne et la colonne du point considéré. 10. Dispositif d'extraction de contours d'objets selon la revendication 9, caractérisé en ce que le registre à décalage (6) comprend des translateurs discrets adaptés pour pour générer deux signaux de phases différentes assurant le décalage du registre. 11. Dispositif d'extraction de contours d'objets selon l'une des revendications 8 à 10, caractérisé en ce que les moyens de génération de fonctions de commande sont constitués par une mémoire morte comprenant un registre de stockage des adresses des moyens de mémorisation précités. 12. Dispositif d'extraction de contours d'objets selon l'une des revendications 8 à 11, caractérisé en ce que les moyens de mémorisation des données représentatives des points caractéristiques de changement de direction des contours comprennent - une mémoire vive (10) pour la mémorisation de la position des points caractéristiques d'un changement de direction des contours, - une mémoire vive (11) pour la mémorisation de l'adresse correspondant à la position des points caractéristiques précédant et/ou suivant chacun des points caractéristique, situés sur une même colonne, - une mémoire vive (12) pour la mémorisation de la position des points de début de contour et, - une mémoire vive (13) pour la mémorisation de la position des points doubles. 13. Dispositif d'extraction de contours d'objets selon l'une des revendications 8 à 12, caractérisé en ce que les moyens de traitement de données mémorisées comprennent une mémoire vive (14) agencée en communication avec les moyens de mémorisation des données représentatives des points caractéristiques, et adaptée pour mettre en attente -la position des points caractéristiques suivis et/ou précédés d'un autre point caractéristique situé sur la même colonne en vue d'ordonner les différents points caractéristiques dans l'ordre de parcours des contours. 14. Dispositif d'extraction de contours d'objets selon l'une des revendications 8 à 13, caractérisé en ce que les moyens de calcul et de traitement des données mémorisées comprennent des opérateurs cablés (18) et au moins un microprocesseur (15) agencés à la sortie desdits moyens (10,11,12,13) de mémorisation. 15. Dispositif d'extraction de contours d'objets selon l'une des revendications 8 à 14, caractérisé en ce qu'il comprend des moyens (17) de visualisation agencés à la sortie du ou des micro-processeur(s) (15) en vue de permettre un con trolle du fonctionnement du dispositif.