Brevet FR2634084A1 — publié le 19900112

Description Circuit intégré et dispositif de traitement d'images' L'invention concerne un circuit intégré de trai- tement de signaux numérisés représentatifs d'une image source définie par des éléments d'image, codés sur M bits, disposés selon I lignes et J colonnes, le traitement de cette image source s'opérant en prélevant pas à pas des images locales délimitées par une fenêtre N.P de N lignes et de P colonnes qui glisse pas à pas à chaque élément d'image le long des I lignes de l'image source. Elle concerne également un disposi- tif de traitement d'images. Une invention de ce genre est connue du document US 4 550 437 qui décrit un appareillage pour le traitement parallèle de données d'images locales. Le but qui y est pour- suivi est de concevoir un circuit intégré à grande échelle d'intégration effectuant des opérations de convolution pour le traitement d'images (élimination du bruit, détection des contours,...). Les difficultés rencontrées concernent la grande densité d'intégration et le nombre élevé de plots de connexion que doit posséder le circuit intégré. Le traitement consiste à délimiter une image locale, prise dans l'image globale à l'aide d'une fenêtre, et comportant m rangées de n éléments. Le circuit intégré décrit comporte 4 rangées de 4 éléments qui sont traités par 4 mémoires et 4 processeurs pour le traitement d'une fenêtre 4x4. Les bits d'un élément d'image sont introduits en parallèle dans le premier étage, traités puis décalés vers le processeur suivant et ainsi de suite puis tous les résultats sont additionnés pour délivrer le résultat recherché. Mais lorsque la taille de la fenêtre est de plus grandes dimensions, la réalisation d'un circuit intégré o les bits sont introduits en parallèle devient vite insurmontable à réaliser par le nombre de. connexions vers l'extérieur. De plus rien n'est indiqué sur la manière de réa- liser les circuits de retard, et à plus forte raison sur leur intégration, opérant sur un tel nombre de données qui doivent être présentes simultanément sur les plots de contact d'en- trée. Dans le cas d'un traitement parallèle à fenêtres glissantes, supposons une fenêtre W(i) se déplaçant horizonta- lement dans l'image à traiter et supposons que l'on dispose d'une structure de traitement permettant de calculer la fonc- tion voulue à chaque cycle f(W(i)). A chaque cycle, la fenêtre se décale d'une position vers la droite ce qui oblige à intro- duire N données nouvelles dans la structure de traitement. Par exemple pour une fenêtre 9x9 et un codage des données sur 8 bits, 72 données nouvelles doivent être introduites et 9 re- tards d'une ligne doivent être utilisés pour accéder aux 9 li- gnes consécutives. On arrive donc à des circuits possédant un grand nombre de connexions d'entrée. Le problème posé par l'invention est celui de la réalisation de circuits intégrés de traitement de données nu- mériques à partir d'une fenêtre glissante qui réduit à un mi- nimum le nombre de connexions vers l'extérieur. Selon un pre- mier mode de réalisation la solution à ce problème posé con- siste en ce que le traitement est effectué simultanément sur M images locales délimitées par M fenêtres glissantes ayant toutes les mêmes dimensions mais décalées les unes des autres d'une ligne de l'image source, ce traitement étant effectué par des opérateurs série agissant successivement sur chaque bit de chacun de N+M-1 éléments d'image dont les signaux nu- mérisés sont introduits en série dans le circuit intégré à l'aide de Q plots de contact o Q = N+M-1, chacun des Q plots de contact recevant les signaux numérisés en provenance d'un élément d'image déterminé. Le circuit intégré met en oeuvre un traitement de type série pipeline en utilisant des processeurs 1 bit. La surface de circuit intégré nécessaire est alors approximati- vement divisée par un nombre M égal à la taille des mots des données traitées, mais également la vitesse de calcul est ain- si divisée par M. Pour pouvoir conserver une vitesse de trai- tement nécessaire compatible avec un traitement en temps réel, on traite M fenêtres en parallèle. Approximativement la sur- face d'un tel circuit intégré est semblable à celle du proces- seur parallèle mais par contre le nombre de fils de connexion est différent. En effet pour un dispositif traitant une fené- tre de N lignes il faut N signaux d'entrée de M bits. Avec M processeurs travaillant sur des fenêtres décalées d'une ligne les unes par rapport aux autres, il suffit de N+M-1 lignes d'entrée. Chaque processeur partage N-1 lignes avec le précé- dant. Le gain devient tout à fait significatif même pour des valeurs de M et N pas très élevées. Ainsi avec une fenêtre de 9x9 (N=9) et des mots de 8 bits (M=8), un processeur parallèle nécessite 72 plots de contact et le processeur série de l'in- vention en nécessite seulement 16. Mais l'invention ne se limite pas au cas de l'in- troduction en série des données sur les plots de contact. Il est en effet possible de conserver l'introduction en parallèle des données, à l'aide d'un nombre réduit de plots de contact, puis d'effectuer une transformation interne parallèle/série afin de permettre le même fonctionnement des opérateurs série que précédemment. Pour cela selon un deuxième mode de réalisation le traitement est effectué simultanément sur M images locales délimitées par M fenêtres glissantes ayant toutes les mêmes dimensions mais décalées les unes des autres d'une ligne de l'image source, ce traitement étant effectué par des opéra-. teurs série agissant successivement sur chaque bit de chacun de N+M-1 éléments d'image dont les signaux numérisés sont in- troduits en parallèle dans le circuit intégré à l'aide de Q plots de contact o Q est le premier multiple de M qui égale ou sinon majore N+M-1, le circuit intégré comprenant en outre un circuit de transformation parallèle/série. Les opérateurs série peuvent réaliser différentes opérations sur des données numériques pour lesquelles le trai- tement consiste à exploiter simultanément les données locales définies par une fenêtre. Il peut s'agir d'un traitement d'i- mages, par exemple des opérations de filtrage (convolution), des opérations de tri, ou des déterminations de maximum/mini- mum dans un lot de données déterminé, ou d'autres opérations. Les figures suivantes données à titre d'exemple non limitatif illustrent quelques-uns de ces cas mais l'inven- tion concerne également d'autres opérations que l'homme du mé- tier peut aisément mettre en oeuvre. Figure 1: un schéma général d'un système de traitement utilisant un circuit intégré de traitement selon l'invention. Figure 2A, 2B: des représentations de plusieurs fenêtres superposées sur une image. Figure 3: un schéma concernant un exemple de traitement utilisant 4 modules opérant sur des fenêtres de 5 lignes. Figure 4A: un schéma d'un circuit de transforma- tion de données parallèle en données série. Figures 4B, 4C: deux schémas d'organisation possible de la mémoire d'images. Figure 5: un schéma d'un premier exemple de réa- lisation destiné à effectuer des opérations de convolution. Figure 6: un schéma d'un deuxième exemple de réalisation destiné à effectuer des opérations de tri. La figure 1 représente un dispositif de traite- ment qui comprend une mémoire d'images 11 qui reçoit les don- nées venant du bus 10 soit à partir d'une caméra soit de tout autre dispositif ayant déjà traité des images (non représen- tés). Un processeur de contrôle 13 génère les adresses pour la lecture de la mémoire 11 et un circuit intégré de traitement 14 génère pour chaque point en provenance de la mémoire 11 un résultat qui est fonction du voisinage de ce point. Ce résul- tat sort sur le bus 15 pour une exploitation ultérieure. La mémoire d'image (figure 2A) est une matrice de I.J points caractérisés chacun par une valeur notée dij au point dij o i représente la ligne et j la colonne. Ces valeurs sont codées sur M bits (typiquement M=8), le poids de niveau m du point dij sera noté dij. Le dispositif de traitement opère sur une fenêtre rectangulaire centrée en dij qui a N lignes et P colonnes (figure 2B). La valeur cal- culée sera gij=f(di+n,j+p) o n est compris entre -N/2 et N/2 et o p est compris entre -P/2 et P/2. A titre d'exemple la figure 2A représente une fenêtre de 5x5 (N=P=5). Selon l'invention si une donnée est codée sur M bits (par exemple M=4) le fait d'entrer les don- nées en mode série va réduire la vitesse de traitement d'un facteur M=4. Pour conserver la même vitesse de traitement, se- lon l'invention, on utilise alors 4 fenêtres: W1, W2, W3 et W4. A l'intérieur du circuit intégré chaque colonne d'une fe- nêtre va être traitée respectivement par un module 31, 32, 33, 34 (figure 3). Le bus de données 12 possède N+M-1=8 plots de contact 35 dans cet exemple. Le bus reçoit simultanément les 8 données de 8 lignes d'images lorsque les données entrent en série, et 8 données de 2 lignes d'images lorsque les don- nées entrent en parallèle. En mode série le module 31 reçoit les données de la première à la cinquième ligne. - Le module 32 reçoit les données de la deuxième à la sixième ligne. - Le module 33 reçoit les données de la troisième à la septiè- me ligne. - Le module 34 reçoit les données de la quatrième à la huitiè- me ligne. Les résultats des 4 modules sont sélectionnés par le bloc 36 pour fournir le résultat du traitement opéré. Chaque donnée étant introduite en série, il est nécessaire d'attendre au début que toutes les données soient entrées avant d'obtenir le premier résultat, mais ensuite le flux des données est constant. Lorsque le traitement des 4 lignes de l'image source est terminé les fenêtres sont décalées en bloc de 4 lignes, la fenêtre Wl par exemple s'étend alors de la cinquième ligne à la huitième ligne et de même pour les autres fenêtres décalées. Les données telles qu'elles apparaissent sur les plots de contact sont représentées sur le tableau 1 pour le mode série. Plots T1 T2 T3 T4 T5 T6 1' 2 3 4 I 2 1 d11 d11 d1l d11 d12 d12... 1 2 3 4 1 2 2 d21 d21 d21 d21 d22 d22 1 2 3 4 1 2 3 d31 d31 d31 d31 d32 d32 I 2 3 4 1 2 4 d41 d41 d41 d41 d42 d42 1 2 3 4 1 2 d51 d51 d51 d51 d52 d52 1 2 3 4 1 2 6 d61 d61 d61 d61 d62 d62 1 2 3 4 1 2 7 d71 d71 d71 d71 d72 d72 1 2 3 4 1 2 8 d81 d81 d81 d81 d82 d82.. - - TABLEAU I On constate par exemple que sur le plot 1 les données de l'élément d'image d11 entrent au cours des temps T1, T2, T3 et T4. Le schéma de la figure 4A permet avec un nombre réduit de plots de contact d'entrer les données en mode paral- lèle et de les traiter en mode série par des opérateurs à i bit. Pour entrer les 4 données de 4 bits relatives à une co- lonne, on entre en parallèle les 4 bits de 2 données qui peu- vent être lues simultanément: 1 4 1ère donnée: d11 à d11 (entrée DI) 2ème donnée: d21 à d21 (entrée D2) Celles-ci sont chargées en parallèle respective- ment dans les registres 411 et 412 sur une même commande L. Au coup d'horloge suivant L+T on entre deux autres données: 1 4 3ème donnée: d31 à d31 (entrée D1) 3 4 4ème donnée: d41 à d41 (entrée D2) Elles sont chargées en parallèle dans les regis- tres 413 et 414. On fait de même pour les 4 autres données sur les commandes L+2T et L+3T. Ainsi après 4 coups d'horloge, les 8 données de 4 bits sont chargées dans les registres 411 à 418. Elles sont alors chargées ensemble respectivement dans les re- gistres 421 à 428 par la commande commune CH. Ces registres sont chargés en parallèle et lus en série à l'aide de la com- mande commune de décalage SH. Ainsi à l'aide des 8 plots de contact les données sont entrées en parallèles mais néanmoins utilisées en mode série pour être exploitées par les opéra- teurs 1 bit suivants. Ainsi les bits de poids identique sont successivement présents sur les sorties B1 à B8 pour les 8 éléments d'image. Les données telles qu'elles apparaissent sur les plots de contact sont représentées sur le tableau 2 pour le mode parallèle. I I I Plots Tl T2 T3 T4 T5 T6 1 1 1 1 1 i 1 d1l d31 d51 d71 d12 d32... 2 2 2 2 2 2 2 d11 d31 d51 d71 d12 d32 3 3 3 3 3 3 3 d11 d31 d51 d71 d12 d32 4 4 4 4 4 4 4 d11 d31 d51 d71 d12 d32 1 I 1 1 I 1 d21 d41 d61 d81 d22 d42... 2 2 2 2 2 2 6 d21 d41 d61 d81 d22 d42 3 3 3 3 3 3 7 d21 d41 d61 d81 d22 d42 4 4 4 4 4 4 8 d21 d41 d61 d8a d22 d42 2O _ _ _ _ _ __ -- TABLEAU 2 On constate par exemple que les données de l'élé- ment d'image d11 entrent sur les plots de contact numéro 1, 2, 3 et 4 et que simultanément les données de l'élément d'image d21 entrent sur les plots de contact numéro 5, 6, 7 et 8. Les figures 48 et 4C fournissent un exemple de schéma d'organisation de la mémoire d'images afin de pouvoir lire simultanément les données D1 et D2. La mémoire d'images 11 de la figure 1 se subdivise alors en deux mémoires M1 et. M2 (figure 4B), l'une recevant les lignes paires et l'autre les lignes impaires. La totalité des données D arrivent sur le bus 10. Deux signaux de sélection CS1 et CS2 permettent de sé- lectionner respectivement M1 et-M2. Elles utilisent ainsi le même bus d'adressage d'entrée ADI et le même bus d'adressage 263403B4 de sortie ADO. Ces deux bus peuvent avoir des flux instantanés différents, mais les flux globaux sur la totalité d'une trame sont égaux afin de permettre unfonctionnement en temps réel. Les données D1 et D2 sont ainsi séparées afin de permettre leur lecture pour être introduits en entrée du schéma de la figure 4A. Cette situation correspond au cas o N+M-1 est in- férieur ou égal à 2M (figure 4B). Dans le cas général pour entrer les données en parallèle, le nombre Q de plots de contact sera le premier multiple de M qui majore N+M-1, c'est-àdire lorsque N+M-1 est inférieur ou égal à r.M o r est un nombre entier posi- tif. D'autre part lorsque les données sont entrées en série on a Q=N+M-1. En conséquence il existe des situations o le nombre Q sera le même dans le cas série et dans le cas paral- lèle. Ces situations sont repérées par un astéristique dans le tableau 3 qui donne quelque exemples dans des cas simples. M=4 M=8 N Q Q 2 8 16 3 8 16 4 8 16 5 8* 16 6 12 16 7 12 16 8 12 16 9 12* 16* 10 16 24 11 16 24 12 16 24 13 16* 24 TABLEAU 3 Pour traiter le cas général o Q est inférieur ou égal à r.M, l'organisation de la mémoire peut être celle re- présentée par le schéma de la figure 4C pour former avec le circuit intégré de traitement un dispositif de traitement d'i- mages. La mémoire d'images est alors organisée en r blocs mé- moire M1, M2... Mr. Le fonctionnement est semblable à celui décrit pour la figure 4B, mais au lieu d'obtenir en D1 les données des lignes paires seulement (par exemple), on obtient les données de toutes les r lignes (modulo r). Il est alors nécessaire d'adapter le schéma de la figure 4A pour charger et lire r registres au lieu de 2. Ainsi l'invention concerne éga- lement un dispositif de traitement d'images qui comprend r mé- moires d'images (avec Q=r.M) qui délivrent les données d'en- trée. Les données qu'elles soient introduites en mode série ou en mode parallèle sont exploitées à l'intérieur du circuit intégré par des opérateurs série pour effectuer un traitement selon lequel un élément d'image d'arrivée est une fonction d'un voisinage (délimité par la fenêtre) d'un élément d'image de l'image source. Le flux des données en entrée de la mémoire d'i- mage est incompressible. En conséquence le flux de données en entrée du circuit est identique sur une période de durée lon- gue par exemple une trame. Pour des durées plus brèves, par exemple pour une ligne de mémoire d'mage, ce flux doit être le plus proche possible du flux d'entrée dans la mémoire d'image afin d'éviter à avoir à générer des organisations mémoire com- pliquées. A titre d'exemple deux types différents de trai- tement sont représentés sur les figures 5 et 6. La figure 5 donne un exemple de traitement dans le cas o la fonction choisie est la convolution: gi,j = Somme de an,p.di+n,j+p Pour une fenêtre 5.5, le convolueur 31 est composé de N=5 uni- tés 51, 52, 53, 54, 55 connectées respectivement aux entrées 510, 520, 530, 540 et 550. Les 5 unités sont de conception identique. Leurs sorties sont réunies à l'arbre d'addition- neurs 56 qui délivre le résultat du module convolueur 31. Chaque unité, par exemple l'unité 51, comprend P-1=4 registres à décalage 511, 512, 513, 514 retardant les données de 4 coups d'horloge (M=4 bits) permettant de présenter les données série à multiplier sur les entrées de P=5 multiplieurs pipeline sé- rie 515, 516, 517, 518 et 519. Chaque multiplieur calcule le produit d'un coefficient anp avec la donnée présente sur son entrée. Un tel multiplieur série est par exemple celui décrit dans TOn a bit-serial input and bit-serial output multiplier par R. GNANASEKARAN IEEE Transactions on Computer Vol C32 no 9, septembre 1983. Les résultats en sortie des multiplieurs sont additionnés dans un arbre d'additionneurs série 71. Tou- tes les unités 51, 52, 53, 54 et 55 reçoivent leurs propres données et leurs propres coefficients. Les résultats en sortie de ces unités sont additionnés dans l'arbre d'additionneurs 56. Pour l'ensemble du traitement sur 4 fenêtres il est néces- saire de réaliser 4 modules convolueurs, tels que le module 31, qui partagent un certain nombre de ressources: - la mémoire des coefficients anp est commune - les registres à décalage qui traitent les lignes communes à plusieurs fenêtres peuvent être communs afin de réduire la surface du circuit intégré. Ainsi les opérateurs série effectuent une convo- lution entre les signaux numérisés des éléments des images locales et une matrice de N.P coefficients stockés dans une mémoire. La figure 6 concerne un deuxième exemple pour lequel le traitement consiste à déterminer le tri par exemple le minimum ou le maximum des valeurs dans la fenêtre courante tel que: gi,j= Min/Max (di+n,j+p) o n est compris entre -N/2 et N/2 et o p est compris entre *-P/2 et P/2. La fenêtre a dans cet exemple 4 lignes et 4 co- lonnes. Les données entrent de manière série bit à bit en commençant par le poids faible sur les entrées A, B, C et D. Pour le couple A, B (bloc 311) un soustracteur 1 bit 61 couplé à un registre de mémorisation de retenue 62 permet de calculer le signe de la différence des données entrant en A et B en 4 coups d'horloge (M=4 bits). Ce registre 62 est remis à zéro par un signal R à l'instant o le bit de poids faible est pré- senté en A et B. Ce signal R déclenche en même temps l'intro- duction du bit de signe dans le registre 63 qui mémorise ce signe. Deux registres à décalage 65, 66 de longueur M=4 bits, retardent respectivement les données A et B. La sortie 64 du registre 63 commande un multiplexeur 67 permettant de choisir le minimum ou le maximum des deux valeurs selon la valeur du signe. A l'aide de deux multiplexeurs, il est possible de sor- tir simultanément le minimum et le maximum. Les deux autres données C et D entrent dans un bloc 312 semblable au bloc 311. Leurs deux sorties entrent dans un bloc 313 qui effectue le même traitement que les blocs 311 et 312 et qui délivre le ré- sultat de l'opération entre les quatre données A, B, C, D. Pour effectuer le tri sur l'ensemble d'une fenêtre il suffit de répéter le schéma du module 31 une fois et de lui fournir les 4 résultats intermédiaires obtenus sur 4 colonnes consé- cutives par le module 31 à condition d'avoir mémorisé au préa- lable dans 3 registres 3 de ces 4 résultats. Le traitement sur plusieurs fenêtres s'effectue selon le schéma de la figure 3 déjà décrit. Ainsi les opérateurs série effectuent une opéra- tion de tri parmi les éléments des images locales délimitées. Le convolueur série et le circuit de tri série qui viennent d'être décrits constituent des exemples d'appli- cation et l'homme du métier peut en concevoir d'autres sans sortir du cadre de l'invention. Revendications: 1. Circuit intégré de traitement de signaux numéri- sés représentatifs d'une image source définie par des éléments d'image, codés sur M bits, disposés selon I lignes et J colon- nes, le traitement de cette image source s'opérant en préle- vant pas à pas des images locales délimitées par une fenêtre N.P de N lignes et de P colonnes qui glisse pas à pas à chaque élément d'image le long des I lignes de l'image source, carac- térisé en ce que le traitement est effectué simultanément sur M images locales délimitées par M fenêtres glissantes ayant toutes les mêmes dimensions mais décalées les unes des autres d'une ligne de l'image source, ce traitement étant effectué par des opérateurs série agissant successivement sur chaque bit de chacun de N+M-1 éléments d'image dont les signaux nu- mérisés sont introduits en série dans le circuit intégré à l'aide de Q plots de contact o Q= N+M-1, chacun des Q plots de contact recevant les signaux numérisés en provenance d'un élément d'image déterminé. 2. Circuit intégré de traitement de signaux numéri- sés représentatifs d'une image source définie par des éléments d'image, codés sur M bits, disposés selon I lignes et J colon- nes, le traitement de cette image source s'opérant en préle- vant pas à pas des images locales délimitées par une fenêtre N.P de N lignes et de P colonnes qui glisse pas à pas à chaque élément d'image le long des I lignes de l'image source, carac- térisé en ce que le traitement est effectué simultanément sur M images locales délimitées par M fenêtres glissantes ayant toutes les mêmes dimensions mais décalées les unes des autres d'une ligne de l'image source, ce traitement étant effectué par des opérateurs série agissant successivement sur chaque bit de chacun de N+M-1 éléments d'image dont les signaux numé- risés sont introduits en parallèle dans le circuit intégré à l'aide de Q plots de contact o Q est le premier multiple de M qui égale ou sinon majore N+M-1 le circuit intégré comprenant en outre un circuit de transformation parallèle/série. 3. Dispositif de traitement d'image selon la reven- dication 2, caractérisé en ce qu'il comprend r mémoires d'ima- ges (avec Q=r.M) qui délivrent les données d'entrée. 4. Circuit intégré selon une des revendications 1 à 3, caractérisé en ce que Q=16, les éléments d'image étant co- dés sur 8 bits (M=8) et traités par une fenêtre comprenant 9 lignes (N=9). 5. Circuit intégré selon une des revendications 1 à 4, caractérisé en ce que les opérateurs série effectuent une convolution entre les signaux numérisés des éléments des ima- ges locales et une matrice de N.P coefficients stockés dans une mémoire. 6. Circuit intégré selon une des revendications 1 à 4, caractérisé en ce que les opérateurs série effectuent une opération de tri parmi les éléments des images locales délimi- tées.