FR 2680292 A1 19930212 FR 9110425 A 19910809 -À FILTRE BIDIMENSIONNEL A REPONSE IMPULSIONNELLE FINIE La présente invention concerne les filtres bidimen- sionnels à réponse impulsionnelle finie tels qu'utilisés notamment pour le codage d'images de télévision, par exemple pour réaliser un codage dit par "sous-bandes" On décrira ici l'application de 1 ' invention au traitement d'une image de télé- vision dans laquelle une mémoire contient les pixels successifs d'une image Il est toutefois clair que 1 'invention s'applique de façon générale au filtrage de données rangées selon une matrice bidimensionnelle.10 Etant donné une image constituée de pixels Pij, tels que représentée en figure 1, o i est un indice de ligne compris entre 1 et M et j est un indice de colonne compris entre 1 et N, un filtrage bidirectionnel de type à réponse impulsionnelle finie ou FIR (Finite Impulse Response) consiste à faire des opérations de combinaison linéaire sur des séquences de pixels d'une ligne et sur des séquences de pixels d'une colonne On dira que le filtrage est d'ordre 2 p+l si la séquence considérée est une séquence associant 2 p+l pixels successifs. Ainsi, un filtrage vertical se définit par la relation ( 1) ci-dessous: k=i+p Qij = Ck*Pkj ( 1) k=i-p et un filtrage horizontal se définit par la relation ( 2) ci- dessous: k=j+p Rij = 7 Dk*Qik ( 2) k=j-p Ces opérations étant linéaires, on notera qu'il est indifférent d'inverser l'ordre des filtrages horizontal et vertical. La figure 2 représente un schéma classique de filtre à réponse impulsionnelle finie, servant de base à la construction d'un filtre horizontal ou vertical Ce filtre est constitué d'une succession de modules identiques Mi à M 2 p+ 1 Dans la figure, seul le module M 2 a été identifié par un encadrement en pointillés Ce module comnprend une borne d'entrée de données e 2 vers un multiplieur 1-2 o la donnée d'entrée est multipliée par un coefficient C 2 Dans la figure, on a présenté la donnée arri- vant sur une ligne unique En fait, cette donnée sera générale- ment un mot binaire de plusieurs bits et l'entrée e 2 correspond à un bus comprenant autant de lignes que le mot cnomprend de bits La sortie du multiplieur 1-2 est envoyée à la première entrée d'un additionneur 2- 2 dont la deuxième entrée reçoit la sortie du module précédent La sortie de l'additionneur est reliée à l'entrée d'un registre à échantillonage sur un front d'horloge 3-2 dont la sortie est connectée à la deuxième entrée de l'additionneur du module suivant Ces registres sont tous comnmandés par une horloge CK qui permet, au rythme de 1 'intro- duction des données, de lire la donnée présente à la sortie de l'additionneur precédent et d'envoyer la donnée précédemment mémorisée vers 1 ' additionneur suivant.30 Il apparaîtra clairement qu'un tel filtre dont toutes les entrées sont interconnectées permet de réaliser l'opération indiquée par la formule ( 1) En effet, si l'on considère le cas o p= 2 ( 5 modules), et que l'on introduit successivement des données Pl Pn, on obtient sur la sortie S, au sixième temps d'horloge: Q 13 = Cl Pll + C 2 P 12 + C 3 P 13 + C 4 P 14 + C 5 P 15, au septième temps d'horloge: Q 14 = Cl P 12 + C 2 P 13 + C 3 P 14 + C 4 P 15 + C 5 P 16, et ainsi de suite. Divers correctifs pourront être apportés par l'homme de l'art pour fournir, si nécessaire, les données Q 11, Q 12 qui sont incomplètes avec le circuit élémentaire décrit ci-dessus. Ainsi, dans le cas classique o la matrice de données, à savoir une image de pixels de télévision est balayée par lignes hori-10 zontales, les données des rangées arrivent séquentiellement et le filtre se prête très simplement à la réalisation d'un fil- trage horizontal. Par contre, pour un filtrage vertical, il faut fournir séquentiellement au filtre les pixels Pll, P 21, P 31 p Ml avant de passer aux pixels P 12, P 22 PM 2 Ceci impose, toujours dans le cas du balayage horizontal classique, de prévoir en amont du filtre des lignes à retard ayant sensiblement la durée d'une ligne Pour un filtre d'ordre 2 p+ 1, il faudra prévoir 2 p lignes à retard Une telle architecture est par exemple décrite dans l'Article de Rao et al publié dans Proceedings of IEEE International Symposium on Circuits and Systems, New Orleans, Louisiane, mai 1990, pages 3050-3052 Les lignes à retard sont classiquement réalisées au moyen de mémoires et, par exemple pour un filtre d'ordre 17 et des pixels définis sur 8 bits, il25 faudra prévoir 16 mémoires reliées au filtre par 16 bus de 8 bits Si le filtre et les lignes à retard sont réalisés dans des puces différentes, ceci oblige pour la puce de filtre à prévoir un nombre de plots de liaison extrêmement important d'o il résulte un coût de boîtier élevé et des performances limitées.30 En conséquence, on a proposé d'inclure les mémoires servant de lignes à retard dans la puce du filtre Mais alors, elle repré- sente une surface de silicium très importante En outre, les technologies de fabrication de mémoire optimisées ne sont géné- ralement pas les mêmes que celles utilisées pour la fabrication des cellules d'un filtre Il en résulte que la puoe d'ensemble n'est pas optimisée De toute façon, cette intégration sur une seule puce des filtres et des mémoires devient impossible quand l'ordre du filtre devient trop élevé, par exemple 65, ou quand 5 les mots de données à traiter comprennent un trop grand nombre de bits, par exemple 16 ou 32. Ce problème est d'autant plus aigu que, dans certains circuits de télévision, par exemple ceux prévus en télévision haute définition, dans lesquels on veut réaliser une technique10 de codage sous-bandes, on prévoit plusieurs filtres par télé- viseur. Ainsi, un objet de la présente invention est de prévoir une nouvelle architecture de filtre bidimensionnel à réponse impulsionnelle finie (FIR) permettant d'optimiser la15 réalisation du filtre vertical sans reporter la difficulté sur le filtre horizontal associé. Un autre objet de la présente invention est de prévoir un filtre bidimensionnel FIR dans lequel la partie mémoire et la partie filtre proprement dite puissent être réalisées dans des20 puces séparées avec un ncnbre de liaisons limité entre les deux puces. Pour atteindre ces objets ainsi que d'autres, la pré- sente invention prévoit de façon générale un filtre numérique bidimensionnel d'ordre 2 p+ 1 pour le traitement de données matri- cielles, comprenant séquentiellement un filtre "vertical" et un filtre "horizontal" Les données matricielles sont appliquées au filtre vertical par un moyen de balayage vertical de bandes horizontales d'une hauteur de p données de la matrice de données et en ce que le filtre horizontal reçoit les données de sortie du filtre vertical selon le même type de balayage. Plus particulièrement, la présente invention prévoit un filtre bidimensionnel à réponse impulsionnelle finie d'ordre 2 p 1 pour le traitement de données associant un filtre "verti- cal" et un filtre "horizontal", chaque filtre comportant 2 p+l cellules dont chacune comprend une entrée de données reliée à un multiplieur par un coefficient déterminé, la sortie du multi- plieur étant reliée à la première entrée d'un additionneur, dont la sortie est reliée à un registre, la sortie du registre étant connectée à la deuxième entrée de l'additionneur de la èllule suivante, les registres étant commandés au rythme de l'intro- duction des données Le filtre vertical comprend des moyens pour balayer verticalement les données par bandes d'une hauteur de p données; des moyens pour fournir simultanément sur une première ligne une donnée d'une bande, sur une deuxième ligne une donnée de la bande précédente décalée de p données, sur une troisième ligne une donnée de la bande encore précédente décalée encore de p données; et des moyens pour, à chaque temps d'horloge, con- necter chaque entrée de cellule à l'une des trois lignes. Selon un mode de réalisation de la présente invention, le filtre horizontal comprend des moyens pour fournir simulta- nément à ses entrées les données de sortie du filtre vertical mutuellement décalées de p+l données. Selon un mode de réalisation de la présente invention, les entrées sur les lignes 1, p+l et 2 p+l du filtre vertical sont directes et les autres entrées sont équipées de multi- plexeurs à deux voies commandés de sorte que la séquence de connexion des entrées aux lignes est la suivante: entrée 1: toujours connectée à la première ligne; entrée 1 (kkp+l): 1-1 fois à la deuxième ligne puis p-l+ 1 fois à la première ligne; entrée p+i toujours connectée à la deuxième ligne; entrée m (p laquelle débute cette séquence. Ces objets, caractéristiques et avantages ainsi que d'autres de la présente invention seront exposés en détail dans la description suivante de modes de réalisation particuliers faite en relation avec les figures jointes parmi lesquelles la figure 1, précédemment décrite, représente une mémoire d'image; la figure 2, précédemment décrite, représente une cellule classique de filtre à réponse impulsionnelle finie; la figure 3 illustre un mode de balayage utilisé selon la présente invention; la figure 4 représente 1 ' architecture d'ensemble d'un filtre selon la présente invention; la figure 5 représente la partie de filtre proprement dite d'un filtre vertical selon la présente invention; et la figure 6 représente la partie de filtre proprement dite d'un filtre horizontal selon la présente invention. Pour faciliter et simplifier la réalisation pratique d'un filtre bidimensionnel à réponse impulsionnelle finie, la présente invention propose d'utiliser un balayage vertical par bandes plutôt qu'un balayage horizontal par trames classique. La figure 3 est destinée à illustrer le mode de ba- layage utilisé et les notations qui seront utilisées dans la suite du présent texte. Dans ce qui suit, pour simplifier l'exposé, on consi- dèrera le cas particulier d'un filtre récursif d'ordre 9, c'est-à-dire p= 4 et 2 p+ 1 = 9 Dans ce cas, la présente invention propose de réaliser un balayage vertical par bandes d'une hau- teur de p= 4 pixels La figure 3 illustre trois bandes de balayage successives, les éléments de la première bande étant désignés verticalement par l A, 2 A, 3 A, 4 A; 5 A, 6 A, 7 A, 8 A; 9 A, l OA, ll A, 12 A; 13 A, les éléments correspondants des deux bandes suivantes étant désignés par le même chiffre et respec- tivement les lettres B et C. La figure 4 représente 1 'architecture générale d'un système de filtrage bidimensionnel, vertical et horizontal, selon la présente invention. Ce système comprend un circuit de conversion de ba- layage 10 fournissant un balayage vertical par bandes du type illustré en figure 3 sur une sortie 11 Ce circuit est suivi de deux mémoires de retard de p lignes + p données (ici p= 4) On désigne par C, B et A la sortie du circuit de conversion de balayage 10, de la première mémoire de retard 12 et de la10 deuxième mémoire de retard 14, respectivement Ces sorties C, B, A sont envoyées sur un filtre vertical 16 et éventuellement vers d'autres filtres verticaux analogues non représentés La sortie du filtre vertical est envoyée à un filtre horizontal 18 et éventuellement à d'autres filtres horizontaux non représentés. La figure 5 représente un mode de réalisation du fil- tre vertical 16 et précise ses connexions avec les bus A, B et C Le filtre 16 est du type illustré en figure 2. Pour des raisons qui apparaîtront ci-après, l'entrée el de la cellule Ml est reliée au bus A, l'entrée ep+l de la cellule Mp+l est reliée au bus B, et l'entrée e 2 p+l de la cellule M 2 p+l est reliée au bus C Les cellules comprises entre la èllule Ml et la èllule Mp+l ont leur entrée qui peut être reliée par un multiplexeur MUX à l'un ou l'autre des bus A et B, et les èllules comprises entre la cellule Mp+l et25 la èllule M 2 p+l ont leur entrée qui peut être reliée par un multiplexeur à l'un ou l'autre des bus B et C. En se référant aux notations de la figure 3, il ap- parait clairement que l'on veut fournir séquentiellement aux entrées el à e 9, dans le cas o p= 4, les signaux suivants: el 1 A 2 A 3 A 4 A A 6 A 7 A 8 A 9 A A 11 A 12 A 13 A 14 A e 2 e 3 e 4 e 5 e 6 e 7 e 8 e 9 2 A 3 A 4 A l B 6 A 7 A 8 A B A 11 A 12 A 9 B B 3 A 4 A l B 2 B 7 A 8 A B 6 B 11 A 12 A 9 B B 4 A l B 2 B 3 B 8 A B 6 B 7 B 12 A 9 B B l B 2 B 3 B 4 B B 6 B 7 B 8 B 9 B B 2 B 3 B 4 B 1 C 6 B 7 B 8 B C 6 C 3 B 4 B 1 C 2 C 7 B 8 B C 6 C 4 B 1 C 2 C 3 C 8 B C 6 C 1 C 2 C 3 C 4 C C 6 C S l S temps On déduit de ce tableau la règle générale à suivre Le bus B doit présenter les données du bus A décalées de p (= 4) lignes plus p (= 4) périodes d'horloge et de même le bus C doit présenter celles du bus B retardées de p lignes plus p périodes d'horloge afin, par exemple, de présenter simultanément au fil- tre les pixels 9 A, 5 B et 1 C; 10 A, 6 B et 2 C; 11 A, 7 B et 3 C Ce résultat est obtenu avec les circuits de retard réglés de la25 façon indiquée en figure 4 Par ailleurs, on voit que les séquences de commande des multiplexeurs de chacune des entrées sont: A B A A A A A A temps B B B C B B B B A B B B A A B B CCC CCC B C C BBC Cette séquence est périodique de période 4 (p) et commence en même temps qu'est présenté un pixel de la ligne supérieure ( 1 A par exemple) Un séquenceur 10 déclenché par un signal de synchronisation permet d'assurer cette fonction On 5 voit à partir du tableau précédent que les entrées 1, 5 et 9 ( 1, p+l et 2 p+ l) n'ont pas besoin d'être associées à un multi- plexeur. Plus généralement, pour un filtre d'ordre 2 p+l, chacun des trois bus A, B, C balaye p lignes vidéo et la séquence de comanmande du multiplexeur, périodique de période p, est la sui- vante: Entrée el: toujours connectée à A Entrée e 2: 1 fois B, puis (p- l) fois A Entrée el (kkp+l): 1-1 fois B, puis (p-l+l) fois A Entrée ep+l: toujours connectée à B Entrée em (p+km En revenant sur la figure 4, on constate que le cir- cuit selon la présente invention permet de relier des ensembles de circuits de mémoire et de conversion de balayage à un circuit de filtre proprement dit par seulement trois bus au lieu de 2 p dans l'art antérieur Ceci est très significatif quand le filtre est d'ordre élevé (p= 8, 16, ou 32) et que les données à filtrer comprennent un grand nombre de bits ( 8, 16 ou 32) Ainsi, on pourra fabriquer les circuits de filtre avec des technologies de type processeur particulièrement bien adaptées à cette fabrica- tion et fabriquer le circuit comprenant les mémoires avec égale-30 ment des circuits adaptés, par exemple des circuits de mémoire DRAM, qui permettent d'intégrer un très grand nombre de cellules sur une surface relativement réduite. On notera que, par rapport au circuit de l'art anté- rieur, la partie mémoire proprement dite selon la présente invention, comprend deux mémoires de p lignes plus une mémoire également de p lignes pour la conversion de balayage Alors que, dans l'art antérieur, seulement 2 p mémoires d'une ligne étaient utilisées Cet inconvénient de l'invention n'est qu'apparent, d'une part, en raison de l'avantage très important de réduction 5 du nombre de bus reliant les mémoires au filtre et donc du nombre de plots du circuit de filtre, d'autre part, parce que selon l'invention, les mémoires peuvent être réalisées sur une puce séparée de technologie adaptée En outre, on notera que le circuit de conversion de balayage est souvent utilisé également10 dans d'autres parties d'un système de traitement d'images de télévision. Par ailleurs, on va montrer en relation avec la figure 6 que la simplification importante apportée par la présente invention à la réalisation du filtre vertical n'entraîne pas une canplexification notable du filtre horizontal. A la sortie du filtre vertical, les données sont ba- layées par bandes Le filtre horizontal doit donc recevoir sur ses entrées sucèssives des données espacées les unes des autres de p+l coups d'horloge Ceci est facilement réalisé avec le circuit illustré en figure 6, o de mêmes références désignent de mêmes éléments que dans les figures précédentes et o l'on notera qu'entre chacune des entrées est prévue une mémoire 21, 22 de retard de p+l données, c'est- à-dire une mémoire de petite capacité devant les mémoires d'une durée d'une ligne (rappelons que couramment en télévision classique, une ligne ccmprend environ 700 pixels et en télévision haute définition, environ 2 000 pixels). Dans des applications de codage par sous-bandes, on prévoira de façon classique une élimination d'un nombre choisi de données d'une séquence à la sortie de chaque filtre et une cadence de balayage appropriée. il REVENDICATIONS 1 Filtre numérique bidimensionnel d'ordre 2 p+l pour le traitement de données matricielles, comprenant séquentiel- lement un filtre "vertical" ( 16) et un filtre "horizontal" ( 18), caractérisé en ce que lesdites données matricielles sont appli- quées au filtre vertical par un moyen ( 10) de balayage vertical de bandes horizontales d'une hauteur de p données de la matrice de données et en ce que le filtre horizontal reçoit les données de sortie du filtre vertical selon le même type de balayage. 2 Filtre bidimensionnel à réponse impulsionnelle finie d'ordre 2 p+l pour le traitement de données associant un filtre "vertical" ( 16) et un filtre "horizontal"( 18), chaque filtre comportant 2 p+l cellules (M) dont chacune comprend une entrée de données (e) reliée à un multiplieur ( 1) par un coef- ficient déterminé, la sortie du multiplieur étant reliée à la première entrée d'un additionneur ( 2), dont la sortie est reliée à un registre ( 3), la sortie du registre étant connectée à la deuxième entrée de l'additionneur de la cellule suivante, les registres étant commandés au rythme de 1 ' introduction des données, caractérisé en ce que le filtre vertical comprend: des moyens ( 10) pour balayer verticalement les don- nées par bandes d'une hauteur de p données; des moyens ( 11, 12, 14) pour fournir simultanément: * sur une première ligne (C) une donnée d'une bande, * sur une deuxième ligne (B) une donnée de la bande précédente décalée de p données, * sur une troisième ligne (A) une donnée de la bande encore précédente décalée encore de p données; et des moyens pour, à chaque temps d'horloge, connecter chaque entrée de cellule à l'une desdites trois lignes. 3 Filtre bidimensionnel selon la revendication 1, caractérisé en ce que le filtre horizontal ( 18) comprend des moyens pour fournir simultanément à ses entrées les données de sortie du filtre vertical ( 16) mutuellement décalées de p+l données. 4 Filtre bidimensionnel selon la revendication 2, caractérisé en ce que les entrées sur les lignes 1, p+l et 2 p+l sont directes et en ce que les autres entrées sont équipées de multiplexeurs à deux voies (MUX) commandés de sorte que la sé- 5 quence de connexion des entrées aux lignes est la suivante: entrée 1: toujours connectée à la première ligne; entrée 1 (kkp+l): 1-1 fois à la deuxième ligne puis p-l+l fois à la première ligne; entrée p+l toujours connectée à la deuxième ligne; entrée m (p par laquelle débute cette séquence.