WO1994003869A1 - Dispositif electronique pour l'analyse d'image et la vision artificielle - Google Patents
Dispositif electronique pour l'analyse d'image et la vision artificielle Download PDFInfo
- Publication number
- WO1994003869A1 WO1994003869A1 PCT/FR1993/000778 FR9300778W WO9403869A1 WO 1994003869 A1 WO1994003869 A1 WO 1994003869A1 FR 9300778 W FR9300778 W FR 9300778W WO 9403869 A1 WO9403869 A1 WO 9403869A1
- Authority
- WO
- WIPO (PCT)
- Prior art keywords
- processors
- processor
- neighboring
- bit
- inputs
- Prior art date
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T1/00—General purpose image data processing
- G06T1/20—Processor architectures; Processor configuration, e.g. pipelining
Definitions
- the present invention relates to an electronic device for image analysis and artificial vision, with parallel operation, organized in a mesh of n-dimensional processors and based on asynchronous global calculations.
- Machine vision can, schematically, be divided into three phases:
- the first category of treatment has led to many effective architectural achievements based in particular on the organization of an array of processors. It is not the same for the second category, however essential, which can only be executed efficiently on highly parallel machines, sophisticated, expensive and complex to program.
- Image analysis is based on diverse and a priori irregular data movements, which are therefore difficult to parallelize. It turns out, however, that most of these movements can be reduced to simple calculation primitives.
- the related components of these graphs represent fundamental basic entities in image analysis. Number of treatments can thus be reduced to iterations of applications of associative operators (logical OR, maximum, addition) on related components of these graphs. We will call hereafter "associations" of such applications.
- the object of the invention is to provide a device making it possible to offer higher performance than devices of the known art, for a lower cost, while being programmable from a calculation model that is simple to master.
- the invention relates to an electronic device for image analysis and artificial vision comprising a set of elementary processors in which each processor, associated with an image pixel and interconnected by serial links to n neighboring processors, has a memory internal of limited size and can operate in SIMD mode on its internal data, characterized in that each processor can be connected or not to its n neighboring processors according to a connection graph which is a subgraph of the physical connection graph of the processors, so as to be able to directly manipulate connected components of the image, in that an associative operator can be applied to these connected components by means of asynchronous communications, in that a local organ makes it possible to determine the moment when the data remains stable on the processor, stability detectors of the various processors being centralized by a network of doors OR towards a central controller which can determine the instant of occurrence of the end of calculation.
- connection of a processor with the n neighboring processors at a given time is materialized in an n-bit register, each bit representing one of the neighboring processors and being positioned if there is an incident arc in this connection graph.
- processor from the neighboring processor n AND gates associated with the registers and with the n connections coming from the neighboring processors making it possible to mask at zero the data coming from the neighboring processors which are not linked by an incident arc towards this processor.
- the associative operator can be a global OR, or a global sum, or an operator making it possible to transform an undirected graph into a graph oriented by asynchronous arbitration.
- the device of the invention makes it possible to solve problems posed by image analysis with superior performance and a cost structure and of dimension greatly reduced compared to the devices of the prior art.
- the device of the invention has a certain number of decisive advantages:
- this device is very easily integrated, in particular if it is based on a mesh organization
- the device of the invention makes it possible to improve the low-level image processing times (convolution, median filtering, etc.) by a factor of one to ten depending on the treatments, and the analysis times. image (segmentation into regions, etc.) of one or two orders of magnitude, with technology and number of processors given compared to current machines;
- the device of the invention enables very efficient vision machines to be produced at relatively low cost. Ultimately (ten years), it will even be possible to integrate the device of the invention in a reduced volume ( ⁇ 1dm3). There are many potential areas of application, including:
- FIG. 3 gives a representation of a tree bit counter according to - Figure 4 gives a representation of an arbitration circuit according to the invention.
- FIG. 4 gives a representation of an arbitration circuit according to the invention.
- Many processing algorithms can be reduced to applications associative operators (or associations) on sets of connected pixels, in the sense of a certain graph representing, depending on the case, a region, a curve, etc.
- the essential object of the invention is to define a device allowing rapid application of these associations.
- the device of the invention is based on an interconnection of elementary processors according to a given topology, for example a two-dimensional mesh.
- Each elementary processor is interconnected by serial links to its nearest n neighbors.
- Each processor which has an internal memory of limited size (for example 256 bits), can simultaneously receive information from its neighbor on a wide bit and transmit it to it, which requires two communication wires 12 and 13. All processors are controlled by a common controller which can operate in SIMD mode ("Single Instruction Multiple Data") on its internal data.
- SIMD mode Single Instruction Multiple Data
- a unit 17 for combining the neighboring processors it recovers the outputs of the masking unit 15 and combines them either by a global OR, or by counting bits, or by arbitration;
- an arithmetic and logic unit 18 it is a conventional arithmetic and logic unit on four bits, operating between the output of the combination unit 17 and a register 19. The least significant bit
- this unit observes the output 20 of the arithmetic and logic unit 18 and detects its variations.
- the different outputs 22 of the convergence detection units of the various elementary processors are centralized by a global OR so as to detect a global convergence of the device.
- Local stability detection can, for example, be done by periodically comparing output 20 of ALU 18 with its previous value. When all the outputs 20 have a stable value, the asynchronous calculation has converged;
- a memory 23 which can read and write to register 19, to the masking units 15 of the neighboring processors and to the output of the arithmetic and logic unit 18.
- Each elementary processor also includes various communications buses between the memory and some of the diagrammed resources, as well as multiplexers making it possible also to use the arithmetic and logical unit to perform operations between local data. These functions, presenting no originality, are not shown in FIG. 2.
- the tree bit counter shown in Figure 3, includes seven adders with three inputs (two bits and one carry) and two outputs (sum and carry).
- the first three adders 25, 26 and 27 receive the eight bits 24 to be considered; the sums of the first three adders 25, 26 and 27 are connected to the inputs of a fourth adder 28, the sum of which constitutes the least significant output bit S1;
- the retentions of the adders 25, 26 and 27 are connected to the inputs of a fifth adder 29; the carry of the fourth adder 28 and the sum of the fifth adder
- the model of the device of the invention makes it possible to gain approximately an order of magnitude on the application of a general convolution, a factor of 3 on the maximum filtering and more than an order of magnitude on the median filtering;
- Objects can be of two types: compact (regions) or filiform (contours). For example, by considering regions, the device of the invention makes it possible to rapidly perform a parallel fusion of these in order to carry out a segmentation of the image (with a constant time per fusion step).
- - oriented graphs most of the considered ones until now were non-oriented.
- each node will r, during Association, the result of the application of the operator to the nodes which are downstream from it.
- a special case of an interesting oriented graph is a chain (two neighbors per node), insofar as it allows to apply in constant time an operator with a parallel prefix ("segmented scan"), whether along an axis or a curve any.
- a similar interest presents itself for a tree which makes it possible to carry out searches quickly;
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Image Processing (AREA)
Abstract
L'invention concerne un dispositif électronique pour l'analyse d'image et la vision artificielle comportant un ensemble de processeurs élémentaires (10) dans lequel chaque processeur (10), associé à un pixel d'image, est interconnecté par des liens série (12) à n processeurs voisins (10), possède une mémoire interne de taille limitée et peut opérer en mode SIMD sur ses données internes. Chaque processeur peut être connecté ou non à ses n processeurs voisins selon un graphe de connexion qui est un sous-graphe du graphe de connexion physique des processeurs, de manière à pouvoir manipuler directement des composantes connexes de l'image. Un opérateur associatif peut être appliqué à ces composantes connexes grâce à des communications asynchrones. Un organe local permet de déterminer le moment où les données restent stables sur le processeur, des détecteurs de stabilité des différents processeurs étant centralisés par un réseau de portes OU vers un contrôleur central qui peut déterminer l'instant d'occurrence de la fin de calcul. Application notamment à l'analyse d'image et à la vision artificielle.
Description
"Dispositif électronique pour l'analyse
d'image et la vision artificielle"
DESCRIPTION
Domaine technique La présente invention a pour objet un dispositif électronique pour l'analyse d'image et la vision artificielle, à fonctionnement parallèle, organisé en maille de processeurs à n dimensions et reposant sur des calculs globaux asynchrones.
Le domaine de l'invention est celui de la vision artificielle. La vision artificielle peut, schématiquement, être découpée en trois phases :
- le traitement de bas niveau, où l'on reconstruit une image à partir d'une transformation prenant en compte la valeur d'un pixel et des pixels plus proches voisins de celui-ci ;
- l'analyse d'image où l'on cherche à extraire des caractéristiques globales d'une image ; et
- la vision de haut niveau, proche des techniques d'intelligence artificielle.
La première catégorie de traitement a conduit à de nombreuses réalisations architecturales efficaces reposant notamment sur l'organisation en tableau de processeurs. Il n'en est pas de même pour la deuxième catégorie, pourtant essentielle, qui ne peut être exécutée efficacement que sur des machines fortement parallèles, sophistiquées, coûteuses et complexes à programmer.
L'analyse d'image est basée sur des mouvements de données divers et a priori irréguliers, donc difficilement parallélisables. Il s'avère cependant que la plupart de ces mouvements peuvent se ramener à des primitives de calculs simples. On considère
l'ensemble d'une image comme un graphe, dont les noeuds sont les pixels et tel qu'un arc existe si les pixels sont voisins dans l'image et appartiennent à la même entité (région de l'image, courbe, etc...). Les composantes connexes de ces graphes représentent des entités de base fondamentales en analyse d'image. Nombre de traitements peuvent ainsi se ramener à des itérations d'applications d'opérateurs associatifs (OU logique, maximum, addition) sur des composantes connexes de ces graphes. On appelera par la suite "associations" de telles applications.
Plusieurs solutions sont envisageables pour réaliser des associations à l'aide de machines parallèles. Tout d'abord, il est possible d'utiliser des architectures en maille traditionnelle mais, du fait du diamètre relativement important de la structure, l'application pas à pas d'un tel opérateur est relativement lente. Des architectures à plus fort degré sont également intéressantes. C'est le cas des hypercubes qui peuvent réaliser efficacement des associations grâce aux opérations à préfixe parallèle, et des pyramides qui profitent de leurs possibilités de centralisation et de diffusion rapide d'informations. L'inconvénient de ces structures est leur volume et leur coût important, qui interdit leur utilisation dans la plupart des applications qui justifieraient de l'emploi de vision artificielle.
L'état de la technique antérieure
Du fait des contraintes de vitesse et d'encombrement des applications de vision, une tendance récente vise à utiliser différemment les ressources intégrées. C'est par exemple le cas des communications asynchrones du "tore polymorphe" proposé par Li et
Maresca, de la structure "Gated Connection Network" proposée par Nash, du projet "Image Understanding Architecture" de l'Université du Massachusetts, telles que décrites dans L'article de H. Li et Q. Stout intitulé "Reconfigurable Massively Parallel Computers" et celui de B. Shu, j. Nash, M. Eshaghian et K. Kim intitulé "Implementation and Application of a Gated-Connection Network in Image Understanding", ou encore de La machine PAPIA II, en cours d'étude à l'Université de Pavie. Dans toutes ces structures, i l est possible de reconfigurer un tableau de processeurs à deux dimensions à l'aide de commutateurs CMOS, pour établir directement des connexions distantes entre pixels ou groupes de pixels quelconques par commutation de circuit. Ces communications se faisant de manière asynchrone, la rapidité du temps de traversée d'un noeud compense Largement la nécessité de traverser un grand nombre de processeurs. Cette organisation permet de résoudre élégamment certains problèmes d'analyse d'image, mais la seule utilisation de reconfiguration au niveau des connexions ne permet pas d'accélérer de manière suffisante L'ensemble des traitements, qui impliquent fréquemment certains calculs arithmétiques.
Une autre approche est d'utiliser des opérateurs analogiques pour profiter de la rapidité des traitements analogiques. Cette approche permet d'obtenir des structures compactes et efficaces ; par contre, elle souffre du manque de p r o g r a mm a bilité des traitements analogiques et se justifie principalement dans des systèmes dédiés.
Exposé de l'invention
L'objet de l'invention est de proposer
un dispositif permettant d'offrir des performances supérieures aux dispositifs de l'art connu, pour un moindre coût, tout en étant programmable à partir d'un modèle de calcul simple à maîtriser.
L'invention concerne un dispositif électronique pour l'analyse d'image et la vision artificielle comportant un ensemble de processeurs élémentaires dans lequel chaque processeur, associé à un pixel d'image et interconnecté par des liens série à n processeurs voisins, possède une mémoire interne de taille limitée et peut opérer en mode SIMD sur ses données internes, caractérisé en ce que chaque processeur peut être connecté ou non à ses n processeurs voisins selon un graphe de connexion qui est un sous-graphe du graphe de connexion physique des processeurs, de manière à pouvoir manipuler directement des composantes connexes de l'image, en ce qu'un opérateur associatif peut être appliqué à ces composantes connexes grâce à des communications asynchrones, en ce qu'un organe local permet de déterminer le moment où les données restent stables sur le processeur, des détecteurs de stabilité des différents processeurs étant centralisés par un réseau de portes OU vers un contrôleur central qui peut déterminer l'instant d'occurence de la fin de calcul.
Avantageusement la connexion d'un processeur avec les n processeurs voisins à un instant donné est matérialisée dans un registre à n bits, chaque bit représentant un des processeurs voisins et étant positionné s'il y a dans le graphe de connexion un arc incident vers ce processeur depuis le processeur voisin, n portes ET associées aux registres et aux n connexions provenant des processeurs voisins permettant de masquer à zéro les données provenant des processeurs voisins qui ne sont pas liés par un arc incident vers ce processeur.
L'opérateur associatif peut être un OU global, ou une somme globale, ou un opérateur permettant de transformer un graphe non orienté en un graphe orienté par arbitrage asynchrone.
Pour des applications d'analyse d'image, il est intéressant d'utiliser un graphe de connexion physique en maille à deux dimensions, mais le modèle de calcul est applicable sur tout type de topologie et d'autres réseaux peuvent présenter un intérêt particulier suivant les applications.
Le dispositif de l'invention permet de résoudre des problèmes posés par l'analyse d'image avec des performances supérieures et une structure de coût et de dimension fortement réduite par rapport aux dispositifs de l'art antérieur.
En effet, le dispositif de l'invention présente un certain nombre d'avantages déterminants :
- tout d'abord, du fait de la simplicité des processeurs élémentaires, ce dispositif est très aisément intégrable, notamment s'il repose sur une organisation en maille ;
- de par l'utilisation de communications asynchrones, on arrive à des temps de calcul incroyablement rapides. Ainsi le dispositif de l'invention permet d'améliorer les temps de traitement d'image de bas niveau (convolution, filtrage médian, etc...) d'un facteur de un à dix suivant les traitements, et les temps d'analyse d'image (segmentation en régions, etc...) d'un ou deux ordres de grandeur, à technologie et nombre de processeurs donnés par rapport aux machines actuelles ;
- enfin, du point de vue du programmeur, les communications dans la machine sont basées sur des opérations de très haut niveau, certes non
conventionnelles, mais somme toute relativement naturelles dans le contexte visé. Le dispositif de l'invention offre un modèle de programmation simple qui devrait faciliter les développements logiciels.
Le dispositif de l'invention permet de réaliser à coût relativement faible des machines de vision très performantes. A terme (dix ans), il sera même possible d'intégrer le dispositif de l'invention dans un volume réduit (<1dm3). Les domaines d'application potentiels sont très nombreux, notamment :
- l'aide à la conduite de véhicule (voire véhicule autonome) ;
- la robot i que ;
' - la télésurveillance ;
ainsi que la plupart des autres domaines d'application de La vision artificielle (biomédical, analyse de qualité industrielle, images satellites). description des dessins
- La figure 1 donne une représentation du dispositif de l'invention ;
- la figure 2 donne une représentation d'un processeur élémentaire selon
- la figure 3 donne une représentation d'un compteur de bits arborescent selon - la figure 4 donne une représentation d'un circuit d'arbitrage selon l'invention. détaillé de modes de réalisation De très nombreux algorithmes de traitement peuvent se ramener à des applications
d'opérateurs associatifs (ou associations) sur des ensembles de pixels connexes, au sens d'un certain graphe représentant suivant les cas une région, une courbe, etc...
L'invention a pour but essentiel de définir un dispositif permettant une application rapide de ces associations.
Le dispositif de l'invention, comme représenté sur la figure 1, repose sur une interconnexion de processeurs élémentaires suivant une topologie donnée, par exemple une maille à deux dimensions. Chaque processeur élémentaire est interconnecté par des liens série à ses n plus proches voisins. Chaque processeur, qui possède une mémoire interne de taille limitée (par exemple 256 bits), peut simultanément recevoir des informations de son voisin sur un bit de large et lui en transmettre, ce qui nécessite deux fils de communication 12 et 13. Tous les processeurs sont pilotés par un contrôleur commun qui peut opérer en mode SIMD ("Single Instruction Multiple Data") sur ses données internes. La base de la mise en oeuvre de performances de calcul rapide sur cette structure est l'utilisation de communications asynchrones entre processeurs voisins.
Dans la suite de la description, pour simplifier l'explication, on prendra comme exemple une maille à deux dimensions, chaque processeur étant interconnecté et ses huit processeurs voisins.
Chaque processeur élémentaire est le noeud de traitement de base de la machine. L'organisation de principe de son chemin de données pour réaliser des opérations rapides entre processeurs voisins est représentée en figure 2. Chaque processeur comprend donc :
- une unité 15 de masquage des processeurs voisins : elle comprend huit registres de un bit associés chacun à chacun des processeurs voisins, et huit portes ET. A la sortie de cette unité on a le ET de chaque bit du registre et du bit envoyé par le processeur voisin correspondant. Il est ainsi possible de ne conserver qu'un sous-ensemble du voisinage, en remplaçant les autres valeurs par "0" , si les opérateurs de base utilisés possèdent le "0" comme élément neutre. Cette unité 15 de masquage des processeurs voisins reçoit donc les bits 16 envoyés par les huit processeurs voisins ;
- une unité 17 de combinaison des processeurs voisins : elle récupère les sorties de l'unité de masquage 15 et les combine soit par un OU global, soit par un comptage de bits, soit par un arbitrage ;
- une unité arithmétique et logique 18 : c'est une unité arithmétique et logique classique sur quatre bits, opérant entre la sortie de l'unité de combinaison 17 et un registre 19. Le bit de poids faible
20 de la sortie de l'unité arithmétique et logique 18 peut être ensuite rediffusé vers les processeurs voisins de manière asynchrone ;
- une unité de détection de convergence
21 : cette unité observe la sortie 20 de l'unité arithmétique et logique 18 et détecte ses variations. Les différentes sorties 22 des unités de détection de convergence des divers processeurs élémentaires sont centralisées par un OU global de manière à détecter une convergence globale du dispositif. Comme les communications sont asynchrones, il est nécessaire de disposer d'une telle unité pour savoir quand un calcul est terminé. La détection locale de stabilité peut, par exemple, se faire en comparant périodiquement
la sortie 20 de l'ALU 18 avec sa valeur précédente. Lorsque toutes les sorties 20 ont une valeur stable, le calcul asynchrone a convergé ;
- une mémoire 23 qui peut accéder en lecture et en écriture au registre 19, aux unités de masquage 15 des processeurs voisins et à la sortie de l'unité arithmétique et logique 18.
Chaque processeur élémentaire comprend également divers bus de communications entre la mémoire et certaines des ressources schématisées, ainsi que des multiplexeurs permettant d'utiliser également l'unité arithmétique et logique pour réaliser des opérations entre données locales. Ces fonctions, ne présentant aucune originalité, ne figurent pas sur la figure 2.
Le découpage réalisé à la figure 2 a été fait pour des raisons de simplicité. Mais pour des raisons d'optimisation de calcul il est tout à fait possible de combiner partiellement la valeur locale directement avec les valeurs venant des processeurs voisins.
Si l'on suppose que le graphe représentant les objets connexes est matérialisé dans les registres de l'unité de masquage des processeurs voisins 15, en sélectionnant chaque processeur voisin correspondant à un arc incident sur le processeur, il est possible de réaliser des opérations globales de la manière suivante :
- réalisation d'un OU global : on suppose que l'on a un graphe non orienté. Il suffit de mettre le bit dont on veut faire le OU global dans le poids faible du registre 19, de réaliser le OU des processeurs voisins dans l'unité de combinaison des processeurs voisins 17, et de faire un OU de sortie
des processeurs voisins 17 et du registre 19 avec l'ALU 18. Le bit est ainsi combiné avec celui des processeurs voisins connectés et, de manière asynchrone, réenvoyé aux processeurs voisins, de sorte que le OU s'effectue sur l'ensemble d'une composante connexe du graphe. Il est également possible d'effectuer ce calcul sur un graphe orienté. Dans ce cas, finalement chaque noeud connaîtra le résultat de l'application du OU à l'ensemble de ses noeuds en aval. La réalisation d'un OU permet, en itérant sur les bits successifs, d'obtenir également un opérateur MAXIMUM. Pour cela, on suppose que l'on cherche le maximum d'une variable i non signée. On fait le OU global du poids fort de i sur la composante et, si ce OU global est à "1", on remplace i par "0" partout où le poids fort de i est à "0". En itérant sur les différents bits de i jusqu'au poids faible, la suite des OU globaux donne le maximum de i sur chaque composante connexe ;
- réalisation d'une somme globale : Il est nécessaire de supposer que le graphe est un arbre (orienté fils- -> père). On met le mot à intégrer dans le registre 19 et on transmet le bit de poids faible vers les processeurs voisins. L'unité de combinaison des processeurs voisins 17 compte le nombre de bits provenant des voisins connectés (par une structure arborescente d'additionneurs de type arbre de Wallace, comme représenté sur la figure 3). Le résultat est additionné avec le registre 19 par l'unité arithmétique et logique 18, avec retransmission asynchrone du bit de poids faible du résultat etc... Le bit de poids faible du résultat arrive ainsi à la racine de l'arbre. Il suffit de décaler d'un cran le registre 19 et d'itérer pour chacun des bits du résultat. Chaque noeud a effectué la somme des valeurs en aval dans l'arbre, et la racine contient la somme globale sur l'ensemble
de la composante connexe. Il est ensuite possible en symétrisant le graphe de rediffuser le résultat vers tous les processeurs. Le compteur de bits arborescent, représenté à la figure 3, comprend sept additionneurs à trois entrées (deux bits et une retenue) et deux sorties (somme et retenue). Les trois premiers additionneurs 25, 26 et 27 reçoivent les huit bits 24 à considérer ; les sommes des trois premiers additionneurs 25, 26 et 27 sont connectées aux entrées d'un quatrième additionneur 28, dont la somme constitue le bit de sortie de poids faible S1 ; Les retenues des additionneurs 25, 26 et 27 sont reliées aux entrées d'un cinquième additionneur 29 ; la retenue du quatrième additionneur 28 et la somme du cinquième additionneur
29 sont reliées à deux entrées du sixième additionneur
30 dont la somme constitue le second bit de sortie de poids faible S1 ; Les retenues du cinquième et sixième additionneurs 29 et 30 sont reliées à deux entrées du septième additionneur 31 dont la somme constitue le bit de sortie de poids suivant S2 et La retenue constitue le bit de sortie de poids fort S3. - extraction d'un arbre recouvrant : La réalisation d'une somme globale implique de disposer d'un arbre recouvrant d'un graphe a priori non orienté. Pour extraire rapidement un arbre recouvrant, un module spécial de l'unité de combinaison des processeurs voisins est utilisé. C'est un module d'arbitrage asynchrone réalisé à partir d'un arbre de bascules RS 35, suivies chacune d'un OU exclusif 36, comme représenté sur la figure 4. Ces bascules sont initialement dans l'état interdit (RS=00) et la sortie des OU exclusifs est donc à "0". Ce qui force les
bascules RS des étages suivants également dans l'état interdit : on suppose que l'on a initialement choisi un processeur par composante connexe qui sera la racine de l'arbre. Pour cela, on peut supposer que chaque processeur possède un numéro spécifique (son adresse), que l'on calcule le maximum des adresses sur la composante connexe comme décrit ci-dessus, et que l'on choisi comme racine le processeur dont l'adresse est égale au maximum. On positionne une variable à "1" sur la racine et à "0" ailleurs pour chaque composante connexe. On met cette variable en bit de poids faible du registre 19, et on réalise un OU entre ce registre et la sortie de l'arbitre 17 (initialement à "0") par l'ALU 18. On fait partir ainsi un "1" de la racine de l'arbre. Dès que ce "1" arrive sur un des arbitres, les bascules RS 35 concernées commutent en mémorisant l'origine du "1", les OU exclusifs 36 passent à "1", ainsi que la sortie de l'arbitre qui traverse l'unité arithmétique et logique (ALU) 18, en retransmettant le "1" vers les processeurs voisins. Comme un seul processeur voisin est retenu par l'arbitre, on réalise ainsi un arbre orienté père - -> fils, dont on peut récupérer les arcs dans chacun des registres de l'arbitre en utilisant une porte NOR 39 à trois entrées branchées respectivement, comme représenté sur la figure 4, sur l'une des sorties des bascules RS du premier, du second ou du troisième étage 40, 41 et 42. Il suffit ensuite de retourner les arcs, en regardant leur contenu sur les processeurs voisins, pour avoir un graphe orienté fils - -> père et pouvoir effectuer une somme globale.
De manière à évaluer les algorithmes mis en oeuvre dans le dispositif de l'invention, il est nécessaire de modéliser Le temps d'une association.
Celui-ci est en effet variable et comprend Le temps d'émission de l'instruction et de positionnement des données (qui est constant), la propagation asynchrone (qui est une fonction approximativement linéaire du plus grand diamètre des composantes connexes du graphe de connexion) et Le temps de détection de convergence globale (qui est une fonction logarithmique de la taille du dispositif), le tout étant quantifié temporellement par l'horloge principale du dispositif. Une conception soignée du processeur peut rendre le temps de traversée d'un processeur très court, de sorte que, en se basant sur des hypothèses réalistes par rapport à l'état actuel de la technologie et au contexte applicatif, ce temps variera entre le temps de deux instructions SIMD (pour des graphes de connexion de faible diamètre, jusqu'à quelques dizaines de pixels) et une dizaine d'instructions pour les plus grands diamètres que l'on peut rencontrer pratiquement dans des graphes extraits d'images.
En première approximation, il semble donc raisonnable de supposer que, quel que soit le diamètre du graphe de connexion, ce temps est constant et de l'ordre de grandeur d'une instruction réalisant un accès local dans le dispositif.
Le dispositif de l'invention présente un certain nombre d'avantages déterminants :
. Tout d'abord, du fait de la simplicité des processeurs élémentaires, de son faible degré, et de son organisation, par exemple à deux dimensions, cette structure est très aisément intégrable. Le nombre de transistors par processeur élémentaire est de 3000-4000 et le nombre d'entrées d'un circuit de P processeurs est en 8 × √P. Ainsi, un circuit intégrant un tableau de 16×16 processeurs nécessite un circuit
d'un million de transistors et implique 128 ent rées/sorties pour les communications (plus quelques dizaines pour les instructions et les différents signaux de service), Le tout étant parfaitement réalisable avec la technologie actuelle. Il est ainsi possible de réaliser une machine de taille 256×256 en quatre cartes de soixante quatre circuits. Les progrès prévisibles en terme d'intégration permettent d'espérer intégrer une machine 256×256 sur tranche entière (WSI) d'ici la fin de La décennie.
. De par l'utilisation de communications asynchrones, on arrive à des temps de calcul particulièrement intéressants. Pour une machine de 64K processeurs élémentaires, en se basant sur un temps actuel de traversée de porte de l'ordre de 0,4 ns, on arrive à des temps de calcul pour une association variant entre 100 et 500 ns pour un bit, suivant le diamètre du graphe de connexion, et environ entre 5 et 30 μs pour un mot de 32 bits, ce qui représente de deux à trois ordres de grandeur d'amélioration par rapport à un hypercube possédant le même nombre de processeurs (en utilisant un algorithme optimal pour cette machine), pour un coût considérablement plus faible. Le temps de calcul d'une association étant directement lié non pas à la fréquence d'horloge mais au temps de traversée d'une porte élémentaire, donc à la technologie, et les communications étant toujours locales, la structure tirera pleinement profit des diminutions prévisibles des dimensions de gravure. On peut donc espérer gagner un facteur d'un ordre de grandeur sur le temps de calcul d'une association d'ici à la fin de la décennie.
. Enfin, du point de vue du programmeur, les communications dans la machine sont basées sur des opérations. de très haut niveau, relativement naturelles dans le contexte applicatif visé. On peut donc espérer avoir une mise en oeuvre logicielle des applications raisonnablement simples.
Ainsi, même si une telle structure présente dès aujourd'hui un intérêt certain, i l semble raisonnable de supposer à l'horizon de quelques années que cette technique permettra de réaliser des machines compactes d'un volume de quelques dm3, entièrement programmables, et réalisant des associations en un temps moyen d'une microseconde. Les applications industrielles potentielles d'une telle machine sont, bien entendu, considérables (automobiles, robotique, etc...).
Un tel dispositif présente un grand intérêt potentiel pour la vision artificielle, dans le domaine :
- des traitements de bas-niveau : même si la machine a été initialement conçue pour l'analyse d'image, la possibilité de prise en compte globale d'un ensemble de pixels présente un intérêt certain pour les traitements de bas niveau (qui se ramènent ainsi à des associations sur un graphe de connexion limité au strict voisinage d'un processeur). Ainsi, le modèle du dispositif de l'invention permet de gagner environ un ordre de grandeur sur l'application d'une convolution générale, un facteur 3 sur le filtrage maximum et plus d'un ordre de grandeur sur le filtrage médian ;
- de la manipulation d'objets connexes : la manipulation d'objets connexes est de première importance en analyse d'image et se trouve être d'ailleurs la motivation première de cette architecture.
Les objets peuvent indifféremment être de deux types : compacts (régions) ou filiformes (contours). Par exemple, en considérant des régions, le dispositif de L'invention permet d'effectuer rapidement une fusion paraLlèle de celles-ci pour réaLiser une segmentation de L'image (avec un temps constant par étape de fusion).
Dans tous Les cas, on peut réaLiser des opérations simples sur ces objets en temps constant (étiquetage, rectangle englobant, moments d'inertie,...) et des opérations plus complexes (enveloppe convexe, approximation polygonale,...) en temps logarithmique ;
- des graphes implicites : il s'agit dans ce cas de considérer des graphes liés à La structure de l'image et non aux données. Divers graphes de ce type présentent un intérêt particulier en vision. Des associations sur des droites parallèles permettent de réaliser en temps constant des projections. La transformée de Hough (ou de Radon) ne nécessite que ces itérations de projections sur des droites dont l'angle est variable. Des courbes plus sophistiquées permettent de mettre en oeuvre La transformée de Hough géneralisée. En groupant dans un même graphe des régions régulières de taille croissante, il est possible de en temps constant une structure resolution (pyramide), utile pour de nombreux algoritmes de vision, ou pour appliquer des techniques de type "diviser pour régner". Enfin, dans un autre d'idées, il est possible d'effectuer en temps des produits matrice-vecteur (utiles, par pour effectuer une classification par réseau -ones) ;
- des graphes orientés : la plupart des considérés jusqu'à présent étaient non-orientés. e cas d'un graphe orienté, chaque noeud va r, lors de L'association, le résultat de
l'application de l'opérateur aux noeuds qui sont en aval de lui. Un cas particulier de graphe orienté intéressant est une chaîne (deux voisins par noeud), dans la mesure où cela permet d'appliquer en temps constant un opérateur à préfixe parallèle ("scan segmenté"), que ce soit suivant un axe ou une courbe quelconque. Un intérêt similaire se présente pour un arbre qui permet d'effectuer rapidement des recherches ;
- des graphes values : dans ce cas, on suppose que chaque arc possède un poids spécifique. De nombreux problèmes, soit en vision, soit dans d'autres domaines, impliquent de rechercher un chemin minimal entre deux noeuds d'un graphe. Là encore, il est possible de programmer le dispositif pour résoudre rapidement le problème.
Claims
1. Dispositif électronique pour l'analyse d'image et la vision artificielle comportant un ensemble de processeurs élémentaires (10) dans lequel chaque processeur (10), associé à un pixel d'image, et interconnecté par des liens série (12) à n processeurs (10) voisins, possède une mémoire interne de taille limitée et peut opérer en mode SIMD sur ses données internes, caractérisé en ce que que chaque processeur (10) peut être connecté ou non à ses n processeurs voisins selon un graphe de connexion qui est un sous-graphe du graphe de connexion physique des processeurs, de manière à pouvoir manipuler directement des composantes connexes de l'image ; en ce qu'un opérateur associatif ( OU logique, addition) peut être appliqué à ces composantes connexes grâce à des communications asynchrones ; en ce qu'un arbre orienté recouvrant peut être extrait du sous-graphe par des communications asynchrones ; en ce qu'un organe local permet de déterminer le moment où les données restent stables sur le processeur, des détecteurs de stabilité des différents processeurs étant centralisés par un réseau de portes OU vers un contrôleur central qui peut déterminer l'instant d'occurence de la fin de calcul.
2. Dispositif selon la revendication 1, caractérisé en ce que la connexion du processeur (10) avec les n processeurs voisins à un instant donné est matérialisée dans un registre à n bits, chaque bit représentant un des processeurs voisins, et étant positionné s'il y a dans le graphe de connexion un arc incident vers ce processeur depuis Le processeur voisin, n portes ET associées aux registres et aux n connexions provenant des processeurs voisins permettant de masquer à zéro les données qui proviennent des processeurs voisins qui ne sont pas liés par un arc incident vers ce processeur.
3. Dispositif selon l'une quelconque des revendications 1 ou 2, caractérisé en ce que chaque processeur élémentaire (10) comprend :
- une unité (15) de masquage des processeurs voisins ;
- une unité (17) de combinaison des processeurs voisins qui récupère les sorties de l'unité de masquage ;
- une unité arithmétique et logique (18) opérant entre la sortie de l'unité de combinaison (17) et un registre (19) ;
- une unité de détection des convergences (21) qui observe la sortie de l'unité arithmétique et logique (18) et en détecte les variations ;
- une mémoire (23) qui peut accéder au registre (19) et aux unités de masquage des processeurs voisins, et à la sortie de l'unité arithmétique et logique (18).
4. Dispositif selon la revendication 1, caractérisé en ce que, chaque processeur étant interconnecté à huit processeurs voisins, l'opérateur associatif étant une somme globale, ledit dispositif comprend un compteur de bits arborescent qui comporte sept additionneurs à trois entrées (deux bits et une retenue) et deux sorties (somme et retenue), les trois premiers additionneurs (25, 26 et 27) reçoivent les huit bits (24) à considérer, les sommes des trois premiers additionneurs (25, 26 et 27), étant connectées aux entrées d'un quatrième additionneur (28) dont la somme constitue le bit de sortie de poids faible (S0), les retenues des trois additionneurs (25, 26 et 27) étant reliées aux entrées d'un cinquième additionneur (29), la retenue du quatrième additionneur (28) et la somme du cinquième additionneur (29) étant reliées à deux entrées du sixième additionneur (30) dont la somme constitue le second bit de sortie de poids faible (S1), les retenues du cinquième et sixième additionneurs (29 et 30) étant reliées à deux entrées du septième additionneur (31) dont la somme constitue le bit de sortie de poids suivant (S2) et la retenue constitue le bit de sortie de poids fort (S3).
5. Dispositif selon la revendication 1, caractérisé en ce qu'il comprend un module d'arbitrage réalisé par un arbre de bascules RS (35) suivies chacune d'une porte OU excusif (36) ; des portes NOR (39) à trois entrées branchées respectivement sur l'une des sorties des bascules RS du premier (40), du second (41) et du troisième (42) étages de l'arbre permettant de récupérer les arcs de l'arbre orienté père - - -> fi ls.
6. Dispositif selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il comprend des détecteurs de stabilité qui comparent périodiquement la valeur de sortie d'un noeud à la valeur précédente pour déterminer s'il y a ou non stabi lité.
7. Dispositif selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il a une structure en maille à deux dimensions, chaque processeur élémentaire étant connecté à ses huit processeurs élémentaires voisins.
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| EP93917839A EP0606458A1 (fr) | 1992-07-31 | 1993-07-29 | Dispositif electronique pour l'analyse d'image et la vision artificielle |
| JP6505054A JPH06511586A (ja) | 1992-07-31 | 1993-07-29 | 人工視覚画像解析用電子デバイス |
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR92/09529 | 1992-07-31 | ||
| FR9209529A FR2694430B1 (fr) | 1992-07-31 | 1992-07-31 | Dispositif électronique pour l'analyse d'image et la vision artificielle. |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| WO1994003869A1 true WO1994003869A1 (fr) | 1994-02-17 |
Family
ID=9432512
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| PCT/FR1993/000778 WO1994003869A1 (fr) | 1992-07-31 | 1993-07-29 | Dispositif electronique pour l'analyse d'image et la vision artificielle |
Country Status (4)
| Country | Link |
|---|---|
| EP (1) | EP0606458A1 (fr) |
| JP (1) | JPH06511586A (fr) |
| FR (1) | FR2694430B1 (fr) |
| WO (1) | WO1994003869A1 (fr) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109997154A (zh) * | 2017-10-30 | 2019-07-09 | 上海寒武纪信息科技有限公司 | 信息处理方法及终端设备 |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB2129589A (en) * | 1982-11-08 | 1984-05-16 | Nat Res Dev | Array processor cell |
-
1992
- 1992-07-31 FR FR9209529A patent/FR2694430B1/fr not_active Expired - Fee Related
-
1993
- 1993-07-29 JP JP6505054A patent/JPH06511586A/ja active Pending
- 1993-07-29 WO PCT/FR1993/000778 patent/WO1994003869A1/fr not_active Application Discontinuation
- 1993-07-29 EP EP93917839A patent/EP0606458A1/fr not_active Withdrawn
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB2129589A (en) * | 1982-11-08 | 1984-05-16 | Nat Res Dev | Array processor cell |
Non-Patent Citations (1)
| Title |
|---|
| LI H ET AL.: "reconfigurable simd massively parallel computers", PROCEEDINGS OF THE IEEE, vol. 79, no. 4, April 1991 (1991-04-01), NEW YORK US, pages 429 - 443, XP000238523, DOI: doi:10.1109/5.92038 * |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109997154A (zh) * | 2017-10-30 | 2019-07-09 | 上海寒武纪信息科技有限公司 | 信息处理方法及终端设备 |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH06511586A (ja) | 1994-12-22 |
| EP0606458A1 (fr) | 1994-07-20 |
| FR2694430A1 (fr) | 1994-02-04 |
| FR2694430B1 (fr) | 1994-09-09 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP3660849B1 (fr) | Circuit mémoire adapté à mettre en oeuvre des opérations de calcul | |
| EP0552074B1 (fr) | Système de traitement de données multiprocesseur | |
| EP3053108B1 (fr) | Circuit electronique, notamment apte a l'implementation d'un reseau de neurones, et systeme neuronal | |
| EP3084588B1 (fr) | Module de traitement du signal, notamment pour reseau de neurones et circuit neuronal. | |
| CA1289261C (fr) | Systeme de traitement d'images pour reseau maille polymorphe | |
| Lopich et al. | Asynchronous cellular logic network as a co‐processor for a general‐purpose massively parallel array | |
| CA2401422A1 (fr) | Procede et dispositif de perception automatique | |
| FR2850768A1 (fr) | Dispositif electronique configurable a granularite mixte | |
| EP0206892B1 (fr) | Procédé de traitement de signaux numérisés représentatifs d'une image origine | |
| WO1994003869A1 (fr) | Dispositif electronique pour l'analyse d'image et la vision artificielle | |
| EP3394799A1 (fr) | Circuit electronique, notamment apte a l'implementation de reseaux de neurones a plusieurs niveaux de precision | |
| Liu et al. | A new systolic array algorithm for discrete Fourier transform | |
| Galilee et al. | Parallel asynchronous watershed algorithm-architecture | |
| EP0540402B1 (fr) | Réseau de résistances binaires et son utilisation pour l'étiquetage de composantes connexes d'images numérisées en vision artificielle | |
| CN117292433A (zh) | 一种基于FPGA部署的改进Yolov8行人检测系统 | |
| EP0780775A1 (fr) | Architecture d'un système de tableaux de processeurs à structures parallèles multiples | |
| EP4202770A1 (fr) | Reseau de neurones avec generation a la volee des parametres du reseau | |
| FR2563349A1 (fr) | Multiplieur matriciel systolique de traitement de donnees numeriques | |
| EP4242855B1 (fr) | Générateur d'adresses pour un calculateur à architecture de type " instruction unique, données multiples | |
| FR3144687A1 (fr) | Architecture de réseau neuronal pour un réseau systolique de processeurs et procédé de traitement de données utilisant un réseau neuronal | |
| Dutta et al. | Low Latency and Area Efficient Very Large Scale Integration Architecture of 2-Dimensional Bicubic Interpolation using Carry Save Adder Based Fast Multiplier | |
| FR2918190A1 (fr) | Dispositif d'adressage pour processeur parallele. | |
| Zhang et al. | Universal Pre-Calculating Structure: Reducing Complexity of Ising Chips with Arbitrary Connectivity | |
| Valkenburg et al. | Parallel implementation of vision algorithms on a hybrid pipelined/multitransputer architecture | |
| Andreou et al. | Neuromorphic Chiplet Architecture for Wide Area Motion Imagery Processing |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| AK | Designated states |
Kind code of ref document: A1 Designated state(s): JP US |
|
| AL | Designated countries for regional patents |
Kind code of ref document: A1 Designated state(s): AT BE CH DE DK ES FR GB GR IE IT LU MC NL PT SE |
|
| WWE | Wipo information: entry into national phase |
Ref document number: 1993917839 Country of ref document: EP |
|
| ENP | Entry into the national phase |
Ref country code: US Ref document number: 1994 211335 Date of ref document: 19940426 Kind code of ref document: A Format of ref document f/p: F |
|
| 121 | Ep: the epo has been informed by wipo that ep was designated in this application | ||
| WWP | Wipo information: published in national office |
Ref document number: 1993917839 Country of ref document: EP |
|
| WWW | Wipo information: withdrawn in national office |
Ref document number: 1993917839 Country of ref document: EP |