Brevet FR2292388A1 — publié le 19760618

La présente invention concerne les procédée et dispositifs dtélaboration de représentation d'images bidimensionnelles disponibles sous forme numérique. Des études ont déjà été effectuées pour fournir d'une image bidimensionnelle une représentation par des lignes de contour, à l'aide d'un traitement numérique. De tels travaux ont notamment été effectués à l1Université de Maryland ; à partir de cette représentation, on peut résoudre un certain nombre de problèmes, tels que la surface de taches contrastées sur 1'image. Mais ce mode de représentation ne permet pas une corrélation satisfaisante du même objet sur deux images successives de celui-ci. On a également réalisé des traitements de corrélation de deux images d'un stme objet par voie numérique, en utilisant des fonc tions simples du signal d1 analyse de l'image suivant une trame, signal utilisé globalement et sans sélection de points caractéristi- ques. En particulier, on a tenté d'appliquer de tels procédés aux images de télévision. N#me si on met en oeuvre des fonctions tenant compte des déformations de l'image, on n'arrive pas à des résultats pleinement satisfaisants, en mettant en oeuvre des moyens de calcul numérique énormes. La présente invention vise à fournir une représentation des images par des points caractéristiques de celles-ci, représentation qui présente un degré d'invariance élevé à l'égard des variations d'apparence dues à des différences dans les conditions de prise de vue. Dans ce but, l'invention propose notamment un procédé d'élaboration d'une représentation d'images bidimensionnelles par des points caractéristiques de celles-ci, caractérisé en ce qu'on effectue sur une représentation numérique des points de l'image, répartis suivant une matrice rectangulaire, un traitement destiné à faire apparaître ceux des points de contour de l'image auxquels ledit contour fait un angle et en ce qu'on mémorise, pour chacun desdits points caractéristiques ainsi déterminés, les coordonnées, la variance et l'angle. l'angle sera déterminé par les directions des deux vecteurs qui le délimitent par rapport à la matrice, c'est-à-dire de façon plus significative que par une simple valeur de l'angle. l'objet à poursuivre étant identifié par un petit nombre de points, la corrélation sur deux images différentes est rendue possible en un temps beaucoup plus court. Il faut noter au passage que la présente demande de brevet ne concerne pas cette corrélation proprement dite et en particulier qu'aucune revendication n'est formulée en ce qui concerne les programmes d'ordinateur susceptibles de permettre de telles corrélations. L'invention est en conséquence susceptible d'être appliquée dans presque tous les cas où l'on doit mettre en oeuvre une corrélation automatique d'images, C'est notamment le cas lorsque l'on veut asservir un système en direction sur un objet en déplacement. Si la direction est matérialisée par un collimateur, il suffit alors de maintenir ce collimateur dans une position invariable par rapport à la constellation de points caractéristiques qui définissent l'objet (au centre de gravité par exemple). On peut également citer la télémétrie automatique, le recalage automatique sur image optique ou fournie par un système détecteur tel que sonnar ou-radar, la photogramétrie automatique, la détection des différences entre deux images bidimensionnelles du même objet, la reconnaissance des formes. Dans un mode particulier de mise en oeuvre de l'invention, on détermine et on mémorise la variance en chaque point de la matrice; on fait apparaitre les points des contours en faisant la différence suivant E - pour les huit points qui entourent chaque point de la matrice - des valeurs- absolues du gradient circulaire Gc et du gradient radial Gr qu'on affecte du signe G c si I Gc I I Gri puis en retenant comme points de contour ceux pour lesquels les valeurs absolues des- valeurs maximum Y et minimum K de K pour les huit points dépassent des seuils prédéterminés ; on retient ceux des points pour lesquels le maximum et le minimum ne sont pas alignés ; on remplace par O la variance mémorisée pour tous les points ne répondant pas aux conditions ci-dessus ; et on sélectionne comme points caractéristiques ceux pour lesquels la variance est supérieure à celle des huit points qui l'entourent. L'invention propose également un dispositif permettant de mettre en oeuvre le procédé ci-dessus défini, essentiellement constitué par des circuits de calcul et de mémorisation. Il faut noter au passage que la complexité de ces circuits différera suivant la rapidité de traitement recherchée (une rapidité élevée conduisant à effectuer le maximum d'opérations en parallèle) ou l'importance de l'installation (la recherche d'une économie de circuits de calcul conduisant à effectuer séquentiellement différentes opérations).Il va sans dire que ces diverses constitutions doivent entre regardées core équivalentes, étant donné d'ailleurs qu'elles comporteront des circuits câblés destinés aux aénear calculs, mais avec un arrangement différent des mémoires et des lo- giques d'écriture et surtout de lecture, et, dans le cas d'un système destiné à atteindre une grande rapidité, la duplication de circuits qui remplissent plusieurs fonctions successives dans le cas d'un système simple. Quel que soit le iode de réalisation adopté, on constate que lton passe d'une représentation de l'image par N x P points répartis suivant une matrice rectangulaire à N lignes et P colonnes à une représentation par un nombre de points qui ne peut en aucun cas dépasser 25 % des points d'origine, qui en général sera de l'ordre de 10 %, ce qui facilite considérablement les traitenents ultérieurs de corrélation effectués sur l'image. L invention sera mieux comprise à la lecture de la description qui suit d'un mode particulier de réalisation donné b titre d'exen, ple non limitatif. La description se réfère aux dessina qui l'ac coipagnent dans lesquels : - les figures la et lb sont des blocs diagrannea représentant deux fractions du dispositif, - la figure 2 est un schéma montrant la façon dont s'effectue l1ex- ploration autour de chaque point de la matrice pour déterminer les gradients circonférentiels G c et les gradients radiaux Gr. Le dispositif sera maintenant décrit de façon succincte en faisant en même temps référence aux étapes du procédé lises en oeuvre. Pour clarifier l'exposé, certaines des étapes du procédé seront toutefois décrites d'une façon séquentielle, alors que le dispositif donné à titre d'exemple autorise un traitement sexi-paral- lèle. Toujours pour plus de clarté, on fera de place en place réfé- rence à un exemple dans lequel l'image est constituée de N x P = 50 x 50 points répartis suivant une matrice rectangulaire et repré- sentés chacun par un nombre I de 5 chiffres binaires ou "bits". Le procédé peut entre regardé colline constitué de trois étapes successives et les sous-ensembles du dispositif correspondant à ces étapes seront successivement décrits. La première étape consiste à mémoriser les nombres représentatifs des points I et à calculer et à mémoriser les variances correspondant à chacun de ces points. Si l'on suppose que les nombres sont appliqués de façon séquentielle sur une entrée 10 à une cadence fixée par une horloge (non représentée), la mémorisation des valeurs de I s'effectue de façon très simple dans une mémoire vive Il sous la commande d'une logique 12 intervenant par l'intermédiaire d'un aiguilleur 13.La variance en chaque point est déterminée pour chaque point I par un traitement des signaux de représentation numérique de I et des huit points qui l1 entourent. Le circuit de calcul 16 peut comporter une première branche de calcul de EI2 de façon itérative par élévation au carré de chacune des valeurs de I à son tour et accumulation dans une mémoire intermédiaire sur trois lignes successives et une seconde branche de calcul de la moyenne par accumulation des valeurs de I. La variance est alors déterminée par un circuit soustracteur, le résultat#étant inscrit dans la position convenable de la mémoire 15.Un tel circuit de calcul peut avoir la constitution générale décrite dans la demande de brevet déposée ce jour au nom du même demandeur pour "Perfectionnements aux procédés et dispositifs de normalisation d'images numériques". Il faut noter au passage que les valeurs de I fournies à lten- trée du dispositif de la figure 1 peuvent être non pas les valeurs de I correspondant à l'exploration directe de l'image, mais les valeurs normalisées provenant d'un dispositif du type décrit et revendiqué dans la demande de brevet déjà mentionnée. Au cours de cette première étape, seuls interviennent les organes appartenant au sous-ensemble 14 de la figure ia. La seconde étape du procédé consiste en l'identification des points appartenant à un contour et auxquels ce contour fait un angle. Pour cela, l'environnement de chacun des points I de la mémoire doit d'abord être exploré afin de déterminer huit valeurs du gradient circonférentiel Gc et huit valeurs correspondantes du gra dient radial G données par G, G I, - Ic 1c désignant le nombre correspondant au point central, et n le point adjacent au point central pour lequel le gradient est déterminé (n variant de O à 7). On peut par exemple affecter aux points placés autour du point central C les nombres indiqués sur la figure 2 et effectuer un ba- layage suivant le circuit indiqué par une flèche en trait plein. Ce balayage de la mémoire 16 est effectué, par l'intermédiaire de l'aiguillage 13, sous la commande d'une logique 17 de lecture à mémoire morte, l'avance étant provoquée par des impulsions d'horloge (non représentée) appliquées sur une entrée 18. Dans le cas illustré sur la figure ia, la logique 17 commence par inscrire dans une mémoire 19 constituée par un registre la valeur de Ic (au cours du premier pas de balayage). Cette valeur de 1c reste ensuite stockée pendant tout le balayage. La logique est prévue pour qu'apparaissent dans deux autres mémoires 20 et 21 les valeurs In 1 et In+1. A chaque pas, correspondant à un point n, le circuit soustracteur 22 fournit, sur sa sortie 23, Gc en grandeur et en signe. Simultanément, les valeurs In 1 - Ic et In+1 - 1c sont fournies par des soustracteurs 24 et 25.Des logiques de commande respectives 26 et 27 provoquent l'inscription dans des positions convenables de mémoires 28 et 29, d'une part de Gc, #d'autre part de Gr. Dans le cas de nombres I de 5 bits, la mémoire 28 devra avoir huit positions de chacune 5 bits Dans la pratique, on constituera cette mémoire 28 de cinq registres en parallèle à huit positions chacune. Simultanément, la logique 27 provoquera l'inscription de Gr dans la mémoire 29 qui, toujours dans l'exemple précédent, comportera huit positions à 5 bits, plus 1 bit de signe. Dans le mode de réalisation illustré, deux circuits soustracteurs 24 et 25 sont prévus et attaquent la mémoire 29 par l'intermédiaire d'un aiguillage 30, ce qui permet de ne pas allonger le temps de calcul, l'aiguillage 30 effectuant une commutation de l'un des soustracteurs à l'autre lorsque, l'exploration étant terminée, il convient d'enre- gistrer In+1 - Ic au lieu de In 1 - Ic On voit par exemple que lorsque G c pour le point 2 (figure 2) sera enregistré en position 2 de la mémoire 28, I1 - Ic qui sera alors disponible sur le circuit 24 sera enregistré en position 1 de la mémoire 29. En même temps que se remplissent les mémoires 28 et 29 mais avec un temps d'horloge de retard, un comparateur 31 détermine si la condition I Gc I I Gr I est remplie. Des logiques de lecture des mémoires 28 et 29 (non représentées) permettent d'appliquer à tout instant aux entrées du comparateur 31 le contenu des positions correspondantes des mémoires. Ces logiques de lecture appliquent en même temps les valeurs absolues de G c et Gr à un soustracteur 32 dont la sortie est reliée à un dispositif d'aiguillage 33 commandé par le comparateur 31. Si la condition ci-dessus définie est remplie, l'aiguilleur fournit à sa sortie 34 un signal de zéro appliqué sur une seconde entrée. Si elle n'est pas remplie, l'aiguilleur fait apparattre sur sa sortie 34 | Gc | - | Gr | Cette sortie est reliée à un registre 35 à six positions binaires (5 bits significatifs et I bit de signe) ; le bit de signe est reçu du soustracteur 22. les huit valeurs K successivement formées dans le registre 35 sont transmises à une mémoire 36 à huit positions de chacune cinq bits et un bit de signe. En général, certaines des positions binaires seront occupées par des 0 et d'autres par une valeur finie K affectée d'un signe.On aura par exemple, pour les huit points In entourant un point Ic : Point In !0 ! 1 ! 2 ! 3 ! 4 ! 5 ! 6 ! 7 ~~~~~~ ! ~~~~~~ ! ~~~~~~ ! ~~~~~~! ~~~~~~! ~~~~~~ ! ~~~~~~ K ! +001 ! 000 ! 000 ! +101 ! -010 ! -100 ! -001 ! 000 Pour plus de simplicité, seuls ont été représentés les bits les moins significatifs, les autres bits étant supposés être tous des 0. Une fois la mémoire 56 complète, on effectue sur son contenu des opérations destinées à déterminer Si le point C a) correspond à un contour, b) dans l'affirmative, correspond à un angle du contour. Au passage, il faut remarquer que la mémoire des variances correspond uniquement à (P - 2) x (N - 2) points, c'est-à-dire dans l'exemple envisagé 48 x 48, étant donné l'impossibilité de déterminer une variance significative sur la première et la dernière ligne, ainsi que sur le premier et le dernier point de chaque ligne. a) La première détermination s1 effectue en vérifiant si les conditions KM i S I Km I s sont simultanément remplies. Dans la pratique, S et s seront en général égaux. La valeur du seuil sera constituée par un compromis entre la recherche d'un n# bre de points caractéristiques aussi élevé que possible (ce qui tend à faire choisir un seuil relativement bas) et une stabilité élevée de ces points, permettant de les retrouver sur des images, telles que des photographies, différentes d'un mdme objet (ce qui implique un seuil relativement élevé). Un dispositif d'aiguillage 38 applique successivement les valeurs de K correspondant aux huit points entourant le point C à deux canaux correspondant chacun à la vérification d'une des conditions ci-dessus. Dans le mode de réalisation illustré, la vérification de la première condition s'effectue de façon séquentielle en utilisant un ensemble comprenant un circuit d'aiguillage 39, un registre 40 et un comparateur 41, ainsi qu'un comparateur supplémentaire 42. Ce système permet d'effectuer siuultanément la recherche du maximum et sa comparaison avec le seuil. Le circuit d'aiguillage 39 reçoit sur une entrée les valeurs positives de K provenant du circuit d'aiguillage 38 et sur l'autre entrée la valeur du seuil S. La valeur de E est en aSie temps appliquée sur une des entrées du comparateur 41. Le système slinitialise à réception d'un signal de cormande sur le registre 40, signal qui provoque l'inscription de S dans le registre. Le comparateur 41 détermine si la valeur de E alors appliquée est supérieure à S et, dans ce cas, commande le circuit d'aiguillage 39 pour transférer la valeur en question de K dans le registre 40. Si au contraire la valeur de E est inférieure à S, c'est cette valeur S qui subsiste dans le registre. La meme opération est effectuée sur toutes les valeurs positives de E. lorsque le balayage est terminé, le coiparateur 42 déterlaine si la valeur qui est dans le registre 40 est égale au seuil, auquel cas il émet un signal de sortie qui commande un circuit de blocage 43. De façon similaire, toutes les valeurs successives négatives de E sont comparées au seuil 8 dans un circuit similaire au précédent, comprenant un circuit d'aiguillage 39', un registre 40', un comparateur 41' entre la valeur de E et le contenu du registre 40', et enfin un comparateur 42' qui, en cas d'identité entre le contenu final du registre et le seuil, fournit un signal d'identité à un circuit de blocage 43'. Si l'un ou l'autre des circuits 43 et 43' est excité, il active un circuit 45 dtinscription d'un 0 dans la position de la mémoire des variances 15 (figure fa) qui correspond au point C. En même temps, le circuit 45 inscrit un 0 dans la position d'une matrice à 46 x 46 positions correspondant au point C. Dans l'exemple qui a été envisagé ci-dessus, ai le seuil est égal à 11, on voit qu'aucun des circuits de blocage 43 et 43' n'est excité. En conséquence, l'indication de la variance subsiste dans la position-mémoire correspondant au point C exploré. b) Par ailleurs, un point n'est considéré comme caractéristique que si le-contour n'est pas rectiligne en ce point. Cette condition peut s'exprimer par le fait que i et Ka ne correspondent pas à des points symétriques par rapport à C. En se reportant à la figure 2, on constate que cette condition s'exprime par le fait que la différence entre les valeurs de n pour les deux points corres pondant à i et K est différente de 4.Dans le mode de réalisation m illustré en figure lb, deux mémoires 47 et 47' à trois positions binaires affichent le contenu d'un compteur 55 qui reçoit des signaux de remplissage à partir de l'horloge de commande, à partir du début de la recherche de i et Km et jusqu'à réception du dernier signal de basculement du circuit d'aiguillage fourni par le comparateur 41 ou 41'. On retrouve ainsi finalement dans les mémoires 47 et 47' les valeurs de n1 et n2 (c'est-à-dire les valeurs de n correspondant au maximum et au minimum). Un circuit soustracteur 48 applique la différence à un comparateur 49 qui reçoit en permanence un signal représentatif de 22 (100 en binaire). En cas d'égalité, le comparateur commande le circuit 45 à travers la porte 44 par sa sortie 50.Les signaux qui apparaissent sur les sorties 51 et 52 en cas d'inégalité dans un sens ou dans l'autre commandent, par l'intermédiaire d'une porte OU 53, le circuit 54 qui fournit à la matrice 54 les valeurs de n1 et n2 (sous forme de deux nombres de trois chiffres binaires) et commandent en m#me temps l'inscription dans cette mémoire tampon des coordonnées (ligne et colonne par exemple), dérivées de l'horlo#, et la variance, provenant de la mémoire 15. Si l'on se reporte encore à l'exemple mentionné ci-dessus, on voit que la différence n1 - n2 est égale à 2 (10 en binaire). En conséquence, on inscrira dans la mémoire tampon 46 les coordonnées du point C, la valeur correspondante de la variance prélevée dans la mémoire 15 et les valeurs n1 = 3 et n2 = 5. Une telle disposition correspond à un contour faisant un angle du genre indiqué en tirets sur la figure 2. La meme détermination est effectuée sur chacun des points C de la matrice, exception faite de ceux de la première et de la dernière lignes et du premier et du dernier points de chaque ligne, c'est à-dire sur (N - 2) (P - 2) points. Il suffit donc que la mémoire tampon 46 ait un nombre de positions égal à (N - 2) (P - 2). Enfin, une fois tous les points répondant à la double condition d'autre sur un contour (i et EX supérieurs aux seuils S et s) et en un emplacement où le contour fait un angle (n1 -n2 # 4) mémorisés, des moyens (non représentés) interviennent en réponse à un signal d'achèvement du balayage et comparent dans la mémoire 15 chaque variance non nulle à la variance de tous les points adjacents ; cette opération peut s'effectuer à l'aide d'une mémoire de lecture simple, type télévision, de mémoires tampons dont la capacité est égale à trois lignes, et de comparateurs : pour chaque point que les comparateurs constatent que la variance en un point C est supérieure à celle en'tours les points adjacents, ils provoquent le transfert des données correspondant au point C de la mémoire tampon 46 dans une mémoire de travail (non représentée) dont la capacité peut n'être que 25 % de N x P, car la dernière condition implique que si un point est considéré comme caractéristique, aucun des huit points adjacents ne peut 1'8trie. En fait d'ailleurs, on constate que le nombre de points caractéristiques sur des images courantes ne dépasse pas 10 ffi de celui des points d'origine. A partir des points caractéristiques ainsi mémorisés, on peut suivre d'une image d'un objet à la suivante 1' emplacement d'un même objet et réaliser notamment une poursuite automatique, meme en cas de déformation progressive de l'image. L'invention est susceptible de nombreuses variantes et est également utilisable dans le cas d1 images tridimensionnelles ou holographiques, au prix d'une complication du dispositif. Par ailleurs, comme il a été indiqué plus haut, le procédé peut être séquentiel, ce qui ralentit la cadence de traitement et donc diminue la fréquence maximum des images que peut accepter le dispositif. Toutefois, la rapidité des circuits numériques disponibles fait que, dans de nombreux cas, un tel mode de fonctionnement sera acceptable. Il va sans dire que la portée du présent brevet s'étend aux variantes et utilisations restant dans le cadre des équivalences. REVENDICATIONS 1. Procédé d'élaboration d'une représentation d'image bidimensionnelle par des points caractéristiques de celle-ci, caractérisé en ce qu'on effectue sur une représentation numérique des points de l'image, répartis svtue matrice rectangulaire, un traitement destiné à faire apparaître ceux des points de contour de l'image auxquels ledit contour est un angle et en ce qu'on mémorise pour chacun desdits points les coordonnées, la variance et 11 angle. 2. Procédé suivant la revendication 1, caractérisé en ce qu'on détermine et on mémorise la variance en chaque point; on en fait apparattre les points des contours/déterminant la différence K - pour les huit points qui entourent chaque point de la matrice - des valeurs absolues du gradient circulaire Gc et du gradient radial Grç , différence qu'on affecte du signe de G c si IGCI > (GrI et qu'on prend égale à O si IGcI ( f G, I puis en retenant comme points de contour ceux pour lesquels les minimum valeurs absolues des valeurs maximum KM et/ Km de K pour les huit points dépassent des seuils prédéterminés; on-détermine parmi ces points de contour ceux qui correspondent à un angle en vérifiant que le maximum et le minimum ne sont pas alignés; on remplace par O la variance mémorisée pour tous les points où les deux conditions ci-dessus ne sont pas remplies; et on sélectionne comme points caractéristiques ceux pour lesquels la variance est supérieure à celle des huit points qui l'entourent. 3. Dispositif d'élaboration d'une représentation d'image bidimensionnelle par des points caractéristiques de celle-ci à partir d'une représentation numérique des points de l'image réDartis suivant une matrice rectangulaire, caracterisé en ce qu'il comprend - des premiers moyens pour déterminer, à partir de la représentation numérique, la variance en chaque point et l'inscrire dans une première mémoire vive - des seconds moyens pour déterminer pour chaaue point C les huit gradients circulaires Gc, les huit qradients Gr, en déduire les huit valeurs du paramètre K défini par K = (signe de G ) c K=O et mémoriser ces huit valeurs de K - des troisièmes moyens pour déterminer les valeurs maximum KM leset minimum Km de K en mémoire et déterminer Si elles remplissent les conditions tKM J > s Km i > s, S et s étant des seuils prédéterminés - des quatrièmes moyens excités par les troisièmes moyens lorsque lesdites conditions sont remplies et destinés à fournir un signal si K M et Km correspondent à des directions non opposées par rapport au point G - des cinquièmes moyens pour, en réponse à l'absence de l'un ou l'autre desdits signaux provenant des troisièmes et quatrièmes moyens, remplacer par O la variance mémorisée pour le point I correspondant et, en réponse à la présence desdits signaux, mémoriser les coordonnées du point I correspondant, la variance et l'angle entre les directions correspondant à K M et K. m 4. Dispositif suivant la revendication 3, caractérisé en ce que les seconds moyens comprennent une mémoire de stockage des nombres Iij de représentation des N x P points de la matrice, une logique de lecture de ladite mémoire de stockage qui, à partir de chaque point Iij, adresse successivement les huit positions mémoires correspondant aux points qui l'entourent et transmet leur contenu à des registres et des circuits soustracteurs, et deux mémoires vives à huit positions destinées à recevoir l'une les valeurs de Grs l'autre, les valeurs de GC, un circuit de calcul de K comprenant un comparateur de | Gr | et |GC| etun soustracteur dont les entrées sont reliées auxdites deux mémoires, et une mémoire à huit positions de stockage temporaire des huit valeurs de K. 5. Dispositif suivant la revendication 4, caractérisé en ce que, la logique de lecture étant prévue pour adresser les huit valeurs dans l'ordre correspondant à un balayage circulaire autour du point G, les quatrièmes moyens sont prévus pour fournir un signal de sortie lorsque la différence d'ordre entre les points correspondant à KM et Km est autre que 4.