Brevet FR2665598A1 — publié le 19920207

i Procédé pour déterminer en temps réel l'existence d'une configuration rectiligne de pixels dans une image numérisée La présente invention concerne un procédé et un disposi- tif pour localiser des configurations rectilignes dans une image numérisée. Cette opération, souvent connue sous le nom de " test de configuration ", consiste, après avoir traité une image brute formée d'une trame bidimensionnelle de pixels présentant chacun un niveau binaire déterminé, par exemple l'image délivrée par une caméra vidéo après un certain nombre de traitements appropriés éventuels (filtrage, extraction de contours, rebouchage de trous, etc), à déterminer, pour chaque pixel appartenant à une configura- tion, si ce pixel appartient à une configuration rectiligne auquel cas on lui affectera par exemple la valeur " 1 "-, ou non auquel cas on lui affectera la valeur " 0 ". Cette dernière étape, qui fait l'objet du procédé de l'invention, peut notamment être l'une des étapes d'un traitement d'analyse d'une scène dans laquelle on cherche à reconnaître des formes caractérisées par des contours rectilignes. Cette application à la reconnaissance de formes n'est cependant pas limitative de la présente invention, qui peut égale- ment être utilisée pour d'autres applications, chaque fois que l'on cherche à reconnaître dans une image des configurations rectilignes, c'est-à-dire à déterminer ou estimer si certaines traces de l'image sont droites (configuration rectiligne) ou non (configuration curvi- ligne). Plus précisément, le test de configuration consiste à tes- ter, en chaque point M de coordonnées (x,y) appartenant à une trace sur l'image, si les points de cette même trace présents dans un voisi- nage donné de ce point M(x,y) sont susceptibles de constituer des segments de droite passant par ce point M auquel cas on décidera que ce point M appartient à un contour rectiligne. A cet effet, on compare le voisinage de chaque point M avec un certain nombre de " masques " ou configurations de réfé- rence différents censés approximer un segment de contour recti- ligne. Si l'on détermine qu'il y a concordance effective du voisi- nage étudié avec l'un quelconque de ces masques de référence, alors on décide que l'on est effectivement en présence d'une configuration rectiligne. La difficulté de cette opération tient principalement au choix du voisinage considéré pour effectuer le test. En effet, jusqu'à présent, le choix d'un masque de voisi- nage de dimension suffisante pour assurer une précision satisfai- sante du point de vue de l'estimation du caractère rectiligne aboutis- sait toujours à des algorithmes de traitement ou des architectures matérielles ne permettant pas d'effectuer en temps réel (c'est-à-dire à la cadence vidéo des images produites) le test de configuration, a fortiori d'effectuer en temps réel un traitement d'image complet incluant un tel test de configuration. L'un des buts de l'invention est de proposer un traite- ment particulier, avec son architecture adaptée, permettant de réali- ser en temps réel ce traitement de reconnaissance des configurations rectilignes. A cet effet, dans un procédé du type précité dans lequel on compare le voisinage d'un pixel donné de cette image à une série de configurations caractéristiques et on désigne ce pixel comme appartenant à une configuration rectiligne si et seulement si la com- paraison détermine une concordance du voisinage de ce pixel avec l'une de ces configurations caractéristiques, le voisinage considéré comprend, selon l'invention, deux couronnes concentriques et non jointives, typiquement des couronnes carrées, définies autour du pixel considéré. Ces deux couronnes carrées concentriques et non join- tives peuvent notamment être constituées par la couronne 5 x 5 et par la couronne 9 x 9 entourant le pixel considéré. Par ailleurs, selon une caractéristique particulièrement avantageuse de la présente invention, l'ensemble desdites configura- tions caractéristiques est défini sous forme d'une équation logique unique appliquée au contenu dudit voisinage, le pixel considéré étant désigné comme étant un pixel de configuration rectiligne si et seulement si cette équation logique est vérifiée. Cette équation logique unique peut notamment être une factorisation de vecteurs logiques CE et CI tels que: * CElil = 1 si et seulement si le iième élément de la cou- ronne externe est non nul, * CIlil = 1 si et seulement si, pour i pair, le (i/2)ième élé- ment de la couronne interne est non nul, et a CIlil = 1 si et seulement si, pour i impair, le ((i-i)/2)ièml ou le ((i+l)/2)ième élément de la couronne interne est non nul. L'invention a également pour objet un dispositif pour déterminer l'existence d'une configuration rectiligne de pixels dans une image numérisée, comprenant des moyens pour mémoriser le voisinage d'un pixel, et des moyens pour comparer ce voisinage à une série de configurations caractéristiques de manière à désigner le pixel correspondant comme appartenant à une configuration recti- ligne si et seulement si la comparaison détermine une concordance du voisinage de ce pixel avec l'une de ces configurations caractéristi- ques, ce dispositif étant caractérisé en ce que ledit voisinage sur lequel on opère la comparaison comprend deux couronnes carrées concentriques et non jointives définies autour du pixel considéré. Lesdits moyens pour comparer ce voisinage à une série de configurations caractéristiques comprennent avantageusement un circuit logique programmable, programmé conformément à une équation logique unique appliquée audit voisinage mémorisé, le pixel considéré étant désigné comme étant un pixel de configuration rectiligne si et seulement si cette équation logique est vérifiée. On va maintenant décrire un mode de mise en oeuvre de l'invention, en référence aux dessins -annexés. La figure 1 montre les deux couronnes concentriques définissant le voisinage utilisé lors de l'étape de test de configura- tion. La figure 2 montre une partie des masques correspon- dant aux différentes configurations caractérisant un contour recti- ligne. La figure 3 est un schéma par blocs illustrant une archi- tecture permettant de mettre en oeuvre en temps réel le traitement selon l'invention. Comme on l'a indiqué plus haut, l'invention concerne une étape de test de configuration, dans laquelle on compare le voisinage de chaque point M avec un certain nombre de masques ou configura- tions de référence différents censés approximer un segment de con- tour rectiligne. Si l'on détermine qu'il y a concordance effective du voisi- nage étudié avec l'une quelconque de ces configurations de réfé- rence, alors on décide que l'on est effectivement en présence d'un contour rectiligne. Le choix du voisinage en question est une question importante. En particulier, du seul point de vue de la qualité du trai- tement, l'augmentation de la taille du voisinage se traduit par une meilleure précision en ce qui concerne l'estimation du caractère rec- tiligne des segments retenus, un voisinage étendu permettant de mieux distinguer un contour effectivement rectiligne d'un contour légèrement curviligne. Mais en revanche, il est bien évident que plus le voisi- nage sera étendu plus la réalisation matérielle des circuits sera ren- due difficile, l'augmentation du nombre de paramètres à prendre en compte entraînant une complexité et un dimensionnement crois- sants des circuits. Ainsi, si par exemple un masque de voisinage de dimen- sion 9 x 9 constitue un choix satisfaisant du point de vue de la qua- lité du traitement, il faut normalement traiter un voisinage consti- tué de 9 x 9 = 81 pixels, entraînant une complexité et un dimension- nement des circuits incompatible avec un traitement en temps réel à la cadence vidéo. L'invention propose, pour limiter la complexité des cal- culs, au lieu de retenir pour le test de configuration l'ensemble de ces 81 pixels, de limiter le voisinage à deux couronnes concentriques et non jointives, la première consistant en une couronne 5 x 5 d'un pixel de large, et la seconde en une couronne 9 x 9, également d'un pixel de large (ces dimensions n'étant bien entendu données qu'à titre illustratif, sans aucun caractère limitatif). Ces deux couronnes ont été illustrées sur la figure 1 en CI (couronne interne 5 x 5) et CE (couronne externe 9 x 9), et l'on voit ainsi que l'on peut se contenter d'étudier un ensemble de 48 points seulement, soit près de la moitié seulement d'un voisinage complet de 81 pixels. On a représenté sur la figure 2 une partie du jeu de confi- gurations de référence ou " masques de voisinage " pour lesquels on considère qu'il y a effectivement contour rectiligne. Le sous-ensemble de masques illustré figure 2 corres- pond à des directions de segment formant un angle compris entre O et 450 par rapport à l'horizontale (avec les conventions de la figure). Les autres masques de l'ensemble se déduisent simple- ment du sous-ensemble illustré figure 2 par des symétries d'axe ver- tical et horizontal et des rotations d'un quart de tour, afin de couvrir toutes les directions comprises entre 45 et 3600. On obtient ainsi 102 masques différents Si le voisinage constitué par les 48 points des deux couronnes 5 x 5 et 9 x 9 du pixel considéré concorde avec l'un quelconque de ces 102 masques, on considérera alors que le pixel central appartient à une configuration rectiligne. Très avantageusement, pour simplifier le calcul, on va réunir l'ensemble de ces configurations de référence sous la forme d'un ensemble restreint d'équations logiques, ce qui permettra de réduire le nombre de comparaisons nécessaires au test (il faudrait sinon effectuer 102 comparaisons, à savoir une pour chaque configu- ration de référence). Ainsi, le test de l'une (i) des N configurations peut être réalisé par une équation logique de la forme: L(i) = B O ^ Bl(i) ^ B 2 (i) A B 3 (i) ^ B 4 (i), o: À Bk(i) est VRAI si et seulement si le pixel situé dans le kième élément de la configuration est non nul, et * B O est VRAI si et seulement si le pixel traité est un point de contour. Le résultat du test est donné par un OU logique sur les résultats de tous les tests L(i): L = V L(i) i=l n On va maintenant montrer que l'on peut, par une défini- tion appropriée de vecteurs logiques, mettre ce test L sous forme d'une factorisation de vecteurs. Notons à cet effet CE (Couronne Externe) et CI (Cou- ronne Interne) les vecteurs logiques définis de la manière suivante: * CElil = 1 si et seulement si le iième élément de la cou- ronne externe est non nul, * CIlil = 1 si et seulement si, pour i pair, le (i/2)ième élé- ment de la couronne interne est non nul, et * CIlil = 1 si et seulement si, pour i impair, le ((i-1)/2)iîme ou le ((i+ 1)/2)ième élément de la couronne interne est non nul. Par ailleurs, si A et B désignent deux vecteurs logiques, notons: * Alil AAli-1 l v Alil v Ali+ 1 l, * (A A B)lil = Alil ^ Blil, * VA =Al O l v Al 1 l vv Aln-1 l, * A+ = (Aln-1 l, Al O l Aln/2-1 l (c'est-à-dire la moitié supérieure des composantes), et * A = (Aln/2-1 l, Aln/2 lAln-1 l (c'est-à-dire la moitié inférieure des composantes). Le test peut alors être mis en facteur sous la forme: L = Bo A V((CE A CI)+ A (CE ACI-) En d'autres termes, on examine si l'on trouve deux élé- ments voisins situés respectivement sur la couronne interne et la couronne externe (test (CE A CI)+) puis si, dans la direction opposée, il existe également deux éléments voisins situés respectivement sur la couronne interne et la couronne externe (test (CE ^ CI)-), et l'on teste enfin si ces deux demi-segments sont situés en vis-à-vis (test global (CE A CI)+ ^ (CE ^ C)-). Ce test global est effectué pour chacun des N points du voisinage considéré (opérateur général OU V). Si ce OU global est VRAI et que le pixel central est un point de contour (Bo VRAI), alors le contour auquel appartient ce pixel est un contour rectiligne. Ce procédé peut être mis en oeuvre par une architecture telle que celle illustrée figure 2, permettant d'opérer en temps réel, même pour des cadences vidéo très élevées (pouvant atteindre jusqu'à 20 M Hz pour la cadence des pixels). En particulier, le test de configuration peut être effectué par un étage comprenant un composant logique programmable de type EPLD (Erasable Programmable Logical Device), référencé 1 sur la figure. Ces composants, qui, typiquement, permettent de réali- ser un nombre important d'opérations logiques à cadence rapide, sont constitués, de manière en elle-même bien connue, de portes logiques OU et ET groupées en cellules terminées par des registres de mémorisation Au moyen d'un outil de développement adapté, l'utili- sateur programme chaque cellule ainsi que les connexions entre les cellules de manière à matérialiser l'expression logique voulue corres- pondante. Dans le cas présent, on réalise le test de configuration par exemple au moyen d'un composant EPM 5128 commercialisé par ALTERA, qui est un circuit comprenant 128 macrocellules. Ce composant est ainsi programmé de façon à réaliser la fonction logique indiquée plus haut, correspondant au test de confi- guration. Essentiellement, pour mettre en oeuvre les équations de ce test, il est nécessaire d'une part d'avoir à chaque coup d'horloge accès au voisinage 9 x 9 complet et, d'autre part, de calculer les valeurs logiques en mode pipeline Ceci peut être réalisé en seule- ment trois étapes, en considérant que le voisinage est stocké en mode glissant dans une mémoire vidéo 2, ce qui implique d'avoir en tout 8 x 9 valeurs binaires; à chaque coup d'horloge, 9 pixels sont alors acquis et mémorisés. A chaque coup d'horloge, on a donc accès au voisinage complet, constitué des 9 pixels de la ligne courante et des 9 pixels de chacune des huit lignes précédentes, stockées dans la mémoire vidéo 2. On montre que la mise en oeuvre des équations mention- nées plus haut peut être ainsi réalisée avec seulement 108 cellules (entrées, registres, etc), ce qui permet d'utiliser un composant EPLD disponible de type courant, par exemple le composant EPM 5128 précité à 128 macrocellules. On notera que, en choisissant une implémentation con- forme aux équations explicitées plus haut, on peut arriver à un nom- bre de cellules inférieur à 128, permettant d'aboutir à l'optimisation recherchée Autrement, et même en élaborant des algorithmes réuti- lisant des morceaux d'équations de manière temporelle, on abouti- rait à un nombre d'équations et de retards associés supérieur à 128, impliquant donc l'utilisation d'EPL Ds d'au moins 128 cellules, ce qui rendrait impossible toute optimisation. En ce qui concerne la mémoire vidéo 2, on peut utiliser notamment le circuit universel " MIP Video Memory ", qui est l'un des circuits développés dans le cadre du programme européen EUR KA (projet " MIP " N O EU 34: Modular Image Processing). Ce circuit Video Memory permet notamment de mémori- ser quatre lignes vidéo de 1024 pixels chacune (taille maximale, pro- grammable par commande externe, et limitée ici à 9 pixels) et offre la possibilité de scinder la mémoire en deux sous-mémoires alimen- tées séparément par deux signaux vidéo distincts, permettant donc de mémoriser huit lignes, comme le requiert la présente invention pour opérer sur un voisinage 9 x 9. La mémoire 2 est ainsi en mesure de délivrer, à la cadence vidéo, une colonne de cinq pixels (les quatre pixels mémori- sés plus le pixel courant) à l'EPLD 1 placé en aval. REVENDICATIONS 1 Un procédé pour déterminer l'existence d'une configu- ration rectiligne de pixels dans une image numérisée, procédé dans lequel on compare le voisinage d'un pixel donné de cette image à une série de configurations caractéristiques et on désigne ce pixel comme appartenant à une configuration rectiligne si et seulement si la com- paraison détermine une concordance du voisinage de ce pixel avec l'une de ces configurations caractéristiques, procédé caractérisé en ce que ledit voisinage comprend deux couronnes (CE, CI) concentriques et non jointives définies autour du pixel considéré. 2 Le procédé de la revendication 1, dans lequel les deux couronnes concentriques et non jointives sont des couronnes carrées. 3 Le procédé de la revendication 2, dans lequel les deux couronnes carrées concentriques et non jointives sont constituées par la couronne 5 x 5 et par la couronne 9 x 9 entourant le pixel con- sidéré. 4 Le procédé de la revendication 1, dans lequel l'ensem- ble desdites configurations caractéristiques est défini sous forme d'une équation logique unique appliquée au contenu dudit voisinage, le pixel considéré étant désigné comme étant un pixel de configura- tion rectiligne si et seulement si cette équation logique est vérifiée. Le procédé de la revendication 4, dans lequel ladite équation logique unique est une factorisation de vecteurs logiques CE et CI tels que: * CElil = 1 si et seulement si le ieime élément de la cou- ronne externe est non nul, * CIlil = 1 si et seulement si, pour i pair, le (i/2)ième élé- ment de la couronne interne est non nul, et * CIlil = 1 si et seulement si, pour i impair, le il ((i-1)/2)ieme ou le ((i+ l)/2)ième élément de la couronne interne est non nul. 6 Un dispositif pour déterminer l'existence d'une confi- guration rectiligne de pixels dans une image numérisée, compre- nant: des moyens ( 2) pour mémoriser le voisinage d'un pixel, et des moyens ( 1) pour comparer ce voisinage à une série de configurations caractéristiques de manière à désigner le pixel correspondant comme appartenant à une configuration rectiligne si et seulement si la com- paraison détermine une concordance du voisinage de ce pixel avec l'une de ces configurations caractéristi- ques, dispositif caractérisé en ce que ledit voisinage sur lequel on opère la comparaison comprend deux couronnes carrées concen- triques et non jointives définies autour du pixel considéré. } Le dispositif de la revendication 6, caractérisé en ce que lesdits moyens ( 1) pour comparer ce voisinage à une série de configurations caractéristiques comprennent un circuit logique pro- grammable, programmé conformément à une équation logique uni- que appliquée audit voisinage mémorisé, le pixel considéré étant désigné comme étant un pixel de configuration rectiligne si et seule- ment si cette équation logique est vérifiée.