Brevet FR2685107A1 — publié le 19930618

La présente invention se rapporte à des processeurs de corrélations et vise à produire un semblable processeur qui est en mesure de manipuLer une grande quantité de données à une vitesse relativement élevée. En général, te processus de corrélation consiste à déterminer le degré de similarité existant entre deux groupes distincts, ou plus, de données ou des parties choisies de celles-ci. La corrélation est une opération utilisée dans de nombreux systèmes de traitement de signaux, et l'une de ses principales utilisations est celle d'un filtre qui optimise la détection de signaux au milieu d'un bruit. Des processeurs simples existent qui peuvent recevoir, en entrée, deux courants de données et qui fournissent une indication de ta corrélation à court terme entre eux. De sérieuses difficultés pratiques surviennent lorsque l'on tente de comparer de grandes quantités de données pour déterminer le degré de similarité existant entre elles. Par exemple, il est souvent nécessaire de déterminer le degré de similarité existant entre deux ensembles bidimensionnels de données qui peuvent représenter des images ou des aires superficielles observées ; il est possible de balayer une importante aire formant un champ de vi sée pour déterminer si une partie de celui-ci correspond à une aire de référence relativement petite dont Les caractéristiques sont déjà connues. Dans un tel contexte, le processus de corrélation consiste à comparer chaque région possible de la scène observée avec l'aire de référence et à déterminer quelles positions donnent la meilleure adaptation parmi toutes les positions possibles. Comme la scène observée peut consister en un nombre extrêmement grand de pointsdtimage distincts, La quantité de traitement nécessaire peut être extrêmement importante. Si la scène est observée en temps réel, les données peuvent changer si rapidement que toute corrélation utile doit s'effectuer extrêmement rapidement. Ces conditions peuvent être très difficiles à satisfaire, et les situations dans Lesquelles de grandes quantités de données doivent être rapidement corréLées ne se limitent en aucun cas à L'exemple précédent. Cette invention vise à fournir un procédé de corrélation perfectionné, ainsi qu'un processeur permettant de mettre en oeuvre le procédé. Selon un premier aspect de l'invention, un procédé de corrélation de données numériques comprend les opérations suivantes : appliquer des données de référence et une quantité plus importante de données de signaux à plusieurs cellules de corrélation en blocs numériques qui possèdent chacun un nombre prédéterminé de bits, ces mêmes données de référence étant appliquées concurremment à chaque cellule et les données de signaux étant appliquées séquentiellement à chaque cellule tour à tour afin de corréler les données de signaux avec les données de référence ; et recycler les données de signaux présentant un format numérique moindre que ledit nombre prédéterminé de bits via lesdites cellules afin de corréler lors de cycles ultérieurs les données de signaux qui n'ont pas été corrélées lors d'un cycle précédent. Dans certains systèmes, on préfère recycler des données de signaux présentant un format de mot numérique moindre que ledit nombre prédéterminé de bits via lesdites cellules jusqu'à ce que toutes les données de signaux ont été corrélées avec lesdites données de référence. L'invention convient particulièrement à la corrélation de deux ensemble de données numériques possédant des longueurs de mot différentes (c'est-à-dire des nombres différents de bits numériques). Typiquement, la longueur de mot la plus courte comprend simplement un seul bit, tandis que la longueur de mot la plus grande peut consister en de nombreux bits supplémentaires, par exemple six bits. Les configurations de données représentées par des amplitudes variables peuvent nécessiter jusqu'à six bits pour donner une indication suffisamment précise des valeurs absolues, et elle nécessite donc des structures de corrélation assez complexes lorsque de grandes quantités de données doivent être corrélées rapidement avec un bloc de référence de données qui est quantifié sur le même nombre de bits.Généralement, une telle structure traite des données binaires d'une manière très insuffisante, car sa capacité de manipulation est fortement sous-utilisée. Il est toutefois coûteux et peu commode de prévoir des corrélateurs spéciaux distincts pour traiter chaque longueur de mot numérique suivant laquelle une donnée peut se présenter, et il est extrêmement peu pratique de programmer un calcultateur à usage multiple pour qu'il effectue une semblable fonction sur une échelle de temps raisonable, car le processus de corrélation implique souvent la manipulation de très importantes quantités de données. Le processeur de corrélation selon l'invention permet d'ajuster directement la vitesse de corrélation (ou le temps nécessaire à la corrélation) avec la longueur de mot des données, de sorte que des données binaires constituées par des bits uniques (c'est-à-dire des "1" et des "0") peuvent être traitées n fois plus vite que des données se présentant dans le format de mot numérique à n bits. Selon un deuxième aspect de l'invention, il est proposé un processeur de corrélation dont la structure est conçue de façon à mettre en oeuvre le procédé de corrélation ci-dessus présenté. Le processeur est destiné à traiter des mots ayant une dimension de bits prédéterminée maximale. Dans l'exemple suivant, la longueur de mot maximale est de 6 bits et la structure est ainsi conçue pour traiter des données se présentant sous forme de mots numériques de 6 bits, et des données binaires. Pour les données binaires, chaque cellule de corrélation corrèle six bits binaires de données de signaux avec six bits de données de référence simultanément. La description suivante, conçue à titre d'illustration de l'invention, vise à donner une meilleure compréhension de ses caractéristiques et avantages ; elle s'appuie sur les dessins annexés, parmi lesquels la figure 1 représente deux zones de données qui doivent être corrélées l'une avec l'autre ; la figure 2 montre un élément classique d'un processeur de corrélation ; la figure 3 montre un processeur de corrélation selon l'invention, sous forme de schéma de principe ; et la figure 4 montre une partie du processeur de corrélation de manière plus détaillée. La corrélation est une opération fondamentale utilisée dans de nombreux systèmes de traitement de signaux. L'une de ses principales utilisations se rapporte à La mise en oeuvre de filtres adaptés, car des filtres de ce type peuvent être utilisés pour optimiser la détection de signaux au milieu du bruit, et en raison du fait qu'ils peuvent être largement utilisés dans Le traitement de signaux pour des applications des radars, de l'acoustique, etc. Dans l'exemple suivant, on utilise la corrélation pour obtenir la reconnaissance d'une configuration de référence située à l'intérieur d'un ensemble bidimensionneL plus grand de données. Les données peuvent être de nature binaire ou peuvent être constituées par des mots numériques à plusieurs niveaux. Le processus de corrélation implique la comparaison de données de référence avec des données de signaux d'entrée et Le calcul d'une série de résultats chiffrés décrivant la similarité de La donnée de référence avec La partie des données de signaux qui est en court de traitement. Ultérieurement, le résultat le plus élevé est utilisé pour identifier la partie des données de signaux qui correspond le plus étroitement aux données de référence. On se reporte à la figure 1. Il y est représenté une aire de référence 1 relativement petite, indiquée par le bloc en trait continu, qui est constitué de données placées,à titre illustratif, sous forme d'un ensemble bidimensionnel de données. En tant que tel, il représente une aire connue qui est emmagasinée à l'intérieur du système de corrélation. Une zone relativement importante de données de signaux 2 représente l'information qui est produite, typiquement par un système de formation d'image, et emmagasinée, éventuellement après un certain prétraitement, sous une forme permettant un accès facile pour la corrélation. En pratique, la nature des données 2 varie avec Le temps et, si elles représentent des signaux vidéo, ou des signaux analogues, elles peuvent changer rapidement. Le but du processus de corrélation est de déterminer quelle partie de l'aire 2 correspond le plus étroitement à l'aire de référence 1. Lorsque la référence 2 présente une taille notable, Le nombre des opérations nécessaires pour la corréler avec L'aire 2 plus grande peut être effectivement très important. Par exemple, si l'aire de référence 1 est constituée d'un ensemble de données bidimensionnel de 64 x 64 points et que L'aire plus grande comprend 256 x 256 points, le nombre minimal d'opérations nécessaires pour la corrélation est d'environ 2 x 108. La corrélation de chaque position possible donne naissance à un résultat chiffré qui décrit la similarité avec la référence. L'aire 1 de données de référence possède initialement la position présentée sur la figure 1 par rapport à l'aire 2 de données de signaux, et ses 64 x 64 points sont en principe corrélés avec les points de l'aire de données 2 qu'elle recouvre (les aires 1 et 2 sont toutes deux limitées par des lignes en trait continu). Dans cet exemple, dix cellules de corrélation sont liées ensemble afin de constituer un corrélateur. Le nombre de cellules de corré Cation ne doit pas nécessairement être 64, car le choix dépend de la vitesse de corrélation voulue. En pratique, on choisit le nombre de corrélateurs associés en fonction de la vitesse de corrélation nécessaire, et celle-ci est généralement associée à la vitesse à laquelle les données de signaux se modifient et, ou bien, sont remises à jour. Les dix cellules de corrélation travaillent toutes en même temps, chacune calculant des résultats de corrélation successifs pour le recouvrement complet de la référence à 64 x 64 points par la scène. Ensuite, L'aire de données 1 se déplace de dix points à un certain moment (par exemple jusqu'à la position 41, ligne en trait interrompu) et, à chaque position, Les dix résultats de corrélation totaux suivants sont calculés. Lorsque l'extrémité de la première ligne a été atteinte, il a été produit une ligne complète de la surface de corrélation. L'aire de données 1 est alors placée au début de la ligne suivante de la scène (par exemple à la position 42, ligne en trait mixte), et le processus se répète pour produire la ligne suivante de résultats de corrélation. Ce processus se poursuit jusqu'à ce que toutes les positions possibles de l'aire de données de référence 1 par rapport à l'aire de données de signaux 2 aient été corrélées. Pour chaque point, le processus de corrélation produit un "résultat" qui est une mesure de La similarité, et le résultat le plus éLevé est supposé donner La meilleure corrélation, c'est-à-dire La partie localisée de L'aire de données 2 qui est Le plus semblable à l'aire de données de référence 1. La figure 2 montre un exemple d'une opération ou d'une fonction produite par une unique cellule de corrélation dans laquelle un signal de référence d'entrée 3 est corrélé avec un signal de 4 bits emmagasiné 4, ceci étant destiné à illustrer le principe de la corrélation. Les données de référence et les données de signaux en correspondance sont multipliées par des multiplicateurs distincts 5 et ce qui est obtenu est additionné dans un dispositif d'addition 6 pour donner un "résuLtat". En terme strict, il est nécessaire de normaliser le résultat en divisant la somme des carrés des données de signaux, mais ceci n' est pas toujours fait en pratique. En transférant Les données de signaux d'entrée 3 via un registre à décalage cadencé 7, on compare tous les points possibles des données de signaux d'entrée avec Les données de référence 4 emmagasinées. Puisque la multiplication demande plus de temps de mise en oeuvre matérielle que, par exemple, l'addition, il est possible de préparer des algorithmes de comparaison reposant sur des opérations plus simples. Ci-dessous sont donnés des exemples de tels algorithmes (a) pour l'algorithme des moindres carrés, le résultat de corrélation, soit S = (signal2 réfé rence)2 signaL de référence (b) pour L'algorithme de la différence absolue, S = X | signaL - réference) signal de référence (c) pour L'algorithme des moindres cubes, S = E |(Signal - référence)3 Signal de référence (d) pour la corrélation binaire, Signal e référence Signal de référence où î = ET ou NI exclusif. Le processeur de corrélation décrit sur les figures 3 et 4 est en mesure d'effectuer l'un quelconque de ces algorithmes, mais il n'effectue pas réellement ces calculs ; il accède à une table de recherche dans laquelle Les résultats appropriés sont emmagasinés. La figure 3 montre, sous forme de schéma de principe, le processeur de corrélation à dix points selon l'invention. IL possède deux entrées 10 et 11 au niveau desquelles Les données de référence et les données de signaux sont reçues. Ces courants de données sont assemblés dans des mémoires vives respectives (MEV) 12 et 13. Il n'est pas nécessaire que la capacité de la MEV 13 soit suffisante pour contenir la base de données de signaux tout entière à n'importe quel moment, car l'information relative aux signaux peut être introduite progressivement au fur et à mesure que l'aire de données de référence 1 ci-dessus (en relation avec La figure 1) balaye l'aire des données de signaux 2. Les données venant des deux mémoires 12 et 13 sont délivrées sous commande d'un circuit 14 de commande et d'horloge au corrélateur 15. La nature du corrélateur 15 est décrite ultérieurement de manière plus détaillée en relation avec la figure 4. Le corrélateur 15 a pour fonction de comparer les deux signaux d'entrée qu'il reçoit et de produire un signal de sortie lorsque chaque résultat de corrélation a été calculé. Chacun des signaux de sortie représente le résultat effectif, ou la similarité, pour chaque position de corrélation. Comme le montre la figure 4, Le corrélateur 15 est constitué d'un certain nombre de cellules identiques 19. Dans cet exemple, pour sauvegarder la simplicité, seules trois cellules 19, 24 et 25 sont représentées, mais, en pratique, le nombre des cellules est déterminé par La vitesse de corrélation voulue, et, dans cet exemple, ce serait dix, comme précédemment indiqué, de manière à permettre la corrélation de dix points en même temps. Des données de signaux et des données de référence se correspondant qui ont été mises sous forme numérique de six bits sont extraites des MEV 12 et 13 de la figure 3 et sont utilisées comme zones d'adresses d'une autre MEV 20. En pratique, cette MEV est un dispositif de 4K x 12 bits. La MEV 20 fait fonction de table de recherche permettant la mise en oeuvre de l'algorithme de corrélation voulue. Elle a été préprogrammée de manière à produire la réponse voulue à toutes les combinaisons possibles de signaux d'entrée valables. La valeur obtenue est délivrée par la MEV 20 et est ajoutée au contenu d'un accumulateur à 24 bits désigné par la référence 21. Lorsque tous les éléments de référence et de signaux se correspondant ont été traités de cette manière, l'accumulation totale représente le résultat de corrélation et est fourni à une borne de sortie 22. La même donnée de référence est simultanément appliquée aux cellules restantes 24 et 25. Les données de signaux reçues par Les cellules suivantes sont extraites via un dispositif de verrouillage à six bits 26 qui sert à retarder Le signal par rapport à la référence de manière que les cellules ultérieures 24 et 25 produisent une position de corrélation différente. Dans cet exemple, on suppose que chaque mot numérique possède six bits, de sorte que le circuit de verrouillage 26 possède une capacité de six bits. Chacune des cellules présente également un signal de sortie indicatif de son résultat de corrélation. Jusqu'ici, le fonctionnement du corrélateur a été décrit en relation avec des mots de données présentant la longueur maximale, c'est-à-dire six bits. Lorsque des données binaires doivent être corrélées, elles sont introduites dans les MEV 12 et 13 et sont délivrées en "groupes" de six bits aux cellules de corrélation de façon à adresser la MEV 20. Chaque groupe de 6 bits représente six mots binaires (c'est-à-dire des "1" ou des "0"). Ils sont traités exactement de la même manière que précédemment, à L'exception du fait que la MEV 20 contient maintenant, à chaque emplacement d'adresse, le résultat relatif à la réalisation et à l'accumuation de ces six corrélations binaires. Toutefois, puisque les données binaires se produisant à l'intérieur d'un groupe de six bits de données de référence ne sont pas corrélées à des données binaires d'autres groupes de données de signaux, il est nécessaire de recycler les données de référence et les données de signaux via la chaine des cellules du corrélateur, cinq fois plus pour obtenir l'effet correspondant à une corrélation croisée compLète des données binaires, qui a été expliquée en relation avec La figure 2 pour des données de 6 bits. En pratique, les données binaires sont simplement lues dans les MEV 12 et 13 à chacune des six occasions se succédant, les positions relatives des deux courants de données étant décalées d'une position de bit à chaque fois.Cette opération équivaut à recycler matériellement les données et elle peut être mise en oeuvre par décalage des signaux de sortie des MEV 12 ou 13 à raison d'une Longueur de mot, c'est-à-dire de 1 bit à chaque occasion. Ainsi, six fois plus de points de données binaires sont corrélés dans les six cycles de fonctionnement du corrélateur. Toutefois, puisque la taille des données de référence est six fois plus petite, car elle est, elle aussi, une donnée binaire par comparaison aux mots de six bits, ceci est équivalent à la corrélation de six points des aires de données I et 2. Il est donc possible de corréler un nombre donné de points de données binaires six fois plus rapidement que ceLa n'est possible pour des mots numériques à plusieurs niveaux ayant chacun six bits. Toutefois, dans certains systèmes, il peut ne pas être nécessaire, ni même souhaitable, de recycler toutes les données de signaux lors des cinq occasions supplémentaires. Lors de la première occasion à laquelle les données de signaux ont été corrélées, seul un point sur six dans la fonction de corrélation est produit, mais il est possible d'identifier, à partir de cela, L'emplacement probable du pic de corrélation. Ainsi, seuls des points intermédiaires de l'aire de cet emplacement peuvent être obtenus par le recyclage des données de signaux. Cet approche peut réduire considérablement le temps nécessaire pour compléter le processus de corrélation. Bien que L'invention ait été décrite, dans un but de simplicité, en relation avec la corrélation de données de référence et de données de signaux se présentant sous forme d'ensembles bidimensionnels, il est clair que ceci n'est pas une obligation, car Les données peuvent se présenter en tout format convenable. Le processeur de corrélation est extrêmement souple, car il est simplement nécessaire d'introduire des données nouvelLes dans les mémoires 20 pour effectuer différents algorithmes de comparaison. En outre, si un certain nombre d'algorithmes sont disponibles, l'aLgorithme utilisé peut être modifié dynamiquement de sorte que Le meilleur algorithme reLatif au but visé à ce moment peut être sélectionné. Puisque la commande de toutes les cellules de l'ensemble à plusieurs cellules est la même, on peut facilement ajouter des cellules supplémentaires ou les commuter en circuit au fur et à mesure des besoins. Bien entendu, l'homme de l'art sera en mesure d'imaginer, à partir du procédé et du dispositif dont la description vient d'être donnée à titre simplement illustratif et nullement limitatif, diverses variantes et modifications ne sortant pas du cadre de L'invention. REVENDICATIONS 1. Procédé de corrélation numérique caractérisé en ce qu'il comprend les opérations suivantes : appliquer des données de référente (10) et une quantité supérieure de données de signaux (11) à plusieurs cellules de corrélation (19) en blocs numériques, dont chacun possède un nombre prédéterminé de bits, Les mêmes données de référence étant appliquées à chaque cellule concurremment et les données de signaux étant appliquées séquentiellement à chaque cellule tour à tour afin de corréler les données de signaux avec les données de référence ; et recycler les données de signaux ayant un format de mot numérique moindre que ledit nombre prédéterminé de bits via Lesdites cellules afin de corréler lors de cycles suivants les données de signaux qui ne sont pas corrélées lors d'un cycle précédent, jusqu'à ce que toutes les données de signaux aient été corrélées avec lesdites données de référence. 2. Procédé selon la revendication 1, caractérisé en ce que des données de signaux ayant un format de mot numérique moindre que ledit nombre prédéterminé de bits sont recyclées jusqu'à ce que toutes les données de signaux aient été corrélées avec lesdites données de référence. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce que, à chaque occasion où les données de signaux sont recyclées, elles sont décalées par rapport aux données de référence d'une quantité équivaLente à un mot numérique. 4. Procédé selon la revendication 1, 2, ou 3, caractérisé en ce que, dans chaque cellule, les données de référence et les données de signaux sont utilisées pour accéder aux résultats emmagasinés d'algorithmes correspondant à des processus de corrélation prédéterminés. 5. Processeur de corrélation caractérisé en ce qu'il comprend : plusieurs cellules de corrélation (19) en cascade ; des moyens (10, 11) servant à appliquer des données de référence et des données de signaux aux cellules de façon que chacune des cellules en cascade reçoivent simultanément Les mêmes données de référence tandis que Les données de signaux sont appliquées séquentiellement à chaque cellule tour à tour afin de corréler les données de signaux avec les données de référence, les données se présentant sous forme de blocs numériques ayant chacun un nombre prédéterminé de bits ; et des moyens servant à recycler les données ayant un format de mot numérique moindre que ledit nombre prédéterminé de bits via lesdites cellules jusqu a ce que toutes les données de signaux aient été corrélées avec lesdites données de référence. 6. Processeur seLon la revendication 5, caractérisé en ce que chaque cellule contient une table de recherche emmagasinée (20) contenant les résultats d'un algorithme de corrélation particulier, et lesdites données de référence et lesdites données de signaux constituent ensemble une zone d'adresse pour ladite table, à laquelle adresse sont emmagasinés les résultats dudit algorithme relativement auxdites données de référence et de signaux. 7. Processeur selon La revendication 6, caractérisé en ce que chaque cellule comporte un accumulateur (21) auquel est délivré le contenu de l'empLacement adressé de Ladite table 8. Processeur selon la revendication 7, caractérisé en ce que chaque cellule comporte un circuit de verrouillage (26) servant à emmagasiner temporairement chaque bloc numérique de données de signaux délivré à La cellule, et un moyen servant à transmettre le bloc numérique à la cellule de corrélation suivante.