Brevet FR2731855A1 — publié le 19960920

L'invention concerne un procédé inversible de décomposition complexe en fréquence d'un signal numérique, et plus particuliérement un procédé à décimation maximale, à recouvrement et commutation. L'invention concerne également, mais non exclusivement, I'application de ce procédé à un dispositif de réduction du flux d'informations de signaux audionumériques. Le procédé selon l'invention concerne la décomposition fréquentielle de signaux réels ou complexes. Il s'applique notamment aux domaines du traitement d'images, de sons, mais aussi à la réalisation de fonctions de lissage et d'interpolation. On peut appliquer le procédé, notamment, à des systèmes de compression exploitant l'information de phase, ou de manière plus générale, à tout système susceptible de tirer partie de la représentation complexe d'un signal, par exemple dans un but de détection ou de quantification. Les transformations linéaires discrètes à reconstruction dite "parfaite" permettant d'obtenir l'information de phase d'un signal sont en général dérivées de la transformation discrète de Fourier. Celle-ci admet des algorithmes rapides, dits "FFT" (pour l'expression anglo-saxonne "Fast Fourier Transform"). De tels algorithmes sont décrits, par exemple, dans l'article de P. Duhamel et M. Vetterli Fast Fourier Transforms : A Tutorial Review and a State of Art", paru dans "Note Technique", CNRS/TOAE/CRPE 1972, janvier 1989. Parmi ces transformations possédant un algorithme rapide, on peut citer la transformation de Hartley, éventuellement dupliquée pour analyser des signaux complexes, ainsi que des transformées proches, comme les transformations W', Ufl , WlV et, plus récemment, "W généralisée" On pourra se reporter aux articles suivants: - L'article de Z. Wang : "Fast Algorithms for the discrete W Transform and for the Discrete Wavelet Transform", paru dans "IEEE Transactions on Acoustics, Speech and Signal Processing", vol. 32, No. 4, pages 803-816, août 1993 ; - L'article de Z. Wang : "The generalized discrete W transform and its applications to interpolation", paru dans "Signal Processing", Vol. 36, pages 99109, 1994. Les techniques connues, notamment celles qui viennent d'être rappelées, ne sont pas sans inconvénients. Elles présentent des taux de réjection fréquentielle entre sous-bandes assez faibles. Ceci est du à la faible taille des vecteurs de base, assimilés à des filtres, et au petit nombre de paramètres permettant de faire varier les décompositions précédentes. La thèse de Paillard : "Codage perceptuel des signaux de haute qualité" (Thèse de l'université de Sherbrooke) met en évidence ce phénomène. Le gain de codage obtenu à l'aide de ces transformées est plus faible que celui obtenu avec des transformations ne permettant pas d'accéder à la phase, par exemple des transformation du type Karnuhen-Loeve, Transformation en Cosinus Discret ou "DCT" (de l'expression anglo-saxonne "Discrete Cosine Transform"), ou du type "ELT" (de l'expression anglo-saxonne "Extended Lapped Transforms"). On pourra se reporter aux documents suivants - Le livre de N. S. Jayant: "Digital coding of waveforms", Englewood Cliffs, Prentice Hall 1984, en ce qui concerne le gain de codage, - L'article de H. S. Malvar : "Extended Lapped Transforms : properties, Applications, and Fast Algorithms", paru dans "IEEE Transactions on Signal Processing", Vol. 40, No. 11, pages 2703-2714, novembre 1992, pour la transformation de type "ELT" D'autre part, ces techniques sont basées sur des matrices carrées. Chaque bloc analysé est donc traité indépendamment, avec les problèmes de discontinuité entre blocs que cela entraîne lorsque l'on construit le signal après l'avoir modifié dans l'espace de fréquences. D'autre part, adopter un recouvrement entre blocs pour pallier ces effets dits "de bloc" conduit à supprimer la propriété de décimation maximale permise par ces techniques et qui est d'une grande importance en compression numérique. Par ailleurs, les techniques faisant appel à des transformées avec recouvrement et décimation maximale de l'art connu, de type "TDAC" (de l'expression anglo-saxonne "Time Domain Aliasing Cancellation") ou, plus généralement "ELT" (voir ci-dessus), ne permettent pas de récupérer une phase issue de deux composantes de signaux en quadrature. En ce qui concerne les transformées dite "TDAC", on pourra se référer à l'article de J. P. Princen et A.B. Bradley "Analysis/Sythesis Filter Bank Based on Time Domain Aliasing Cancellation", paru dans "WEE Transactions on Acoustics, Speech and Signal Processing", Vol. 34, No. 10, pages 1153-1161, octobre 1986. L'invention vise à pallier les inconvénients des procédés de l'art connu, et dont certains ont été rappelés. Pour ce faire, selon une caractéristique importante du procédé de l'invention, dans un mode de réalisation préfére, on détermine une transformée orthogonale, donc réversible, à décimation maximale, de taille adaptable le long des blocs, qui fournit une interprétation fréquentielle complexe d'un signal réel ou complexe monodimensionnel ou multidimensionnel. Selon l'invention, on peut choisir le nombre de sous-bandes complexes, la longueur des filtres utilisés, la forme de ceux-ci, sous la réserve de contraintes qui seront précisées, et la valeur de divers autres paramètres, influant sur l'interprétation fréquentielle finale. Divers algorithmes rapides, connus en soi, peuvent être utilisés lors de certaines étapes du procédé. L'invention a donc pour objet un procédé inversible de décomposition complexe en fréquence d'un signal numérique comprenant une étape de décomposition en sous-bandes de sortie de ce signal numérique et une étape de recomposition de ces sous-bandes de sortie, ladite décomposition étant effectuée à l'aide d'une transformée basée sur un filtre dit "prototype" et une transformation unitaire déterminés, caractérisé en ce que ledit filtre est de taille multiple de ladite transformation et en ce que cette transformation et choisie de sorte que, une fois définie par des lignes et colonnes dans une base orthonormée déterminée, elle possède un ensemble non vide de colonnes, appariables par paires, telles que chacun des points en dimension 2, dont les coordonnées sont les coefficients d'une même ligne de chacune desdites deux colonnes appariées, appartient à un cercle de rayon prédéterminé. L'invention a encore ppour objet l'application de ce procédé à un dispositif de réduction du flux d'informations de signaux audionumériques. Le procédé selon l'invention présente notamment l'avantage d'opérer une décimation maximale d'un signal à analyser et de changer de banc de filtres en cours d'analyse du signal. Le procédé peut en outre être associé à des transformations supplémentaires visant à recombiner des sous-bandes entre-elles ou à les dupliquer le long du signal analysé. L'invention sera mieux comprise et d'autres caractéristiques et avantages apparaîtront à la lecture de la description qui suit en référence à la figure 1 qui illustre schématiquement un exemple de dispositif de réduction du flux d'informations de signaux audionumériques mettant en oeuvre le procédé selon l'invention. On va maintenant rappeler quelques caractéristiques des filtres dits "MOT", c'est-à-dire à Transformation à Modulation Orthogonale. Dans la description qui va suivre, les notations suivantes seront adoptées - N désignera l'ensemble des entiers naturels - Z désignera l'ensemble des entiers relatifs - R désignera le corps des nombres réels - C désignera le corps des nombres complexes, - i désignera la racine carrée de - 1 dans C; -#0= 1 et #m # Z, m # 0 # #m = 0. Il a été montré dans l'article de J. Mau "Rectangular M-Band Modulated Orthogonal Transforms" paru dans "ICASSP 1994, que sous les hypothèses et définitions suivantes - L, M, N entiers strictement positifs quelconques entre eux, - [dk(n)](k,n)#{0,1,...,M-1} est une transformation unitaire de taille M; - [dk(n)](k,n)#{0,1,...,M-1}*Z est obtenue par périodisation de période M, - h(n) est un filtre de support de longueur au plus L, vérifiant la relation suivante #n # {0,..,L-1}, #m # Z, +h(N - 1 - n - r . M)h(N - 1 - n - r . M - m .M)} = 2#m - Vn E Z hiun) = (1/2)[h(N- 1 - n) + h(n)] - #n # Z hA(n) = (1/2)[h(N - 1 - n) - h(n)] - #n # Z hk(n) = hS(n)dk(n) - hA(n)dk(N - 1 - n) Dans ces relations, I'indice S est utilisé pour "Symétrique" et le l'indice A pour "Antisymétrique" Les filtres hk définissent un banc de filtres orthogonaux à reconstruction parfaite. Ces filtres vérifient les relations suivantes #(k,1) # {0,...,M - 1}, #(m.p) # Z, Dans ce qui suit, h sera appelé filtre prototype du banc des filtres. Selon une des caractéristiques importantes du procédé de l'invention, on choisit en outre des relations particulières entre L, M et N, telles que: -L=p.Moùp E N; D'autre part, il est supposé que, sans restriction, le support de filtre est inclus dans (0, . . , L - 1).La condition portant sur h devient: #n # {0, ... , L-1}, #j # [0,..,p-1}, +h((p - i)M - n - 1)h((p - i - j)N - 1 - n) = 2#, On va maintenant définir une classe de transformations particulières qui répond à la relation suivante et qui constitue une caractéristique importante du procédé de l'invention: ## # {0, 1,.., M-1}, card(#) > 1, ## [## # {0, 1,..,M-1}\#] Vk E #, Vn E Z, dk 2(n) + dA(k) kn) = 21M (1) On peut interpréter ces relations de la manière suivante : à tout vecteur [dk(n)]nez, tel que k soit un élément de n on peut associer un vecteur [d#(k)(n)]n#Z tel que les points de coordonnées (dk(n), d#(k)(n)) soient situés sur un même cercle, indépendamment de n. L'existence effective de transformations de ce type sera montrée ci-après. On peut récupérer la phase. Si la relation (1) est réalisée, on dispose d'un couple (Q, A). On peut alors poser: Vk E #, Vn, #k,n, dk(n) + i. dAk (n) = (2/M) ei wA;n par hypothèse sur [dk(n)](k,n)# n*z, [(pk,n] est périodique selon n de période M. En cherchant à établir un filtre complexe, on obtient alors #k # #, #n, hk(n) + i.h#k(n)=(2/M){h(n)cos#k,n - ih(N - 1 - n)sin#k,n) On va associer aux bancs de filtres des algorithmes particuliers. La mise en oeuvre de banc de filtres permet de tirer parti des algorithmes disponibles pour la transformation utilisée. Par exemple, si la transformation de Hartley (ou W) est utilisée, I'implémentation du banc de filtres permet d'utiliser un algorithme de complexité en M log(M), notamment si M est une puissance de deux. De manière plus générale, quelque soit le rapport entre la longueur du filtre prototype, ou filtre de base, et la taille de la transformation choisie, un seul appel à la transformation suffit à traiter un bloc de M échantillons. Pour simplifier les notations (dans le cas contraire, il suffit d'effectuer une inversion temporelle), on va considérer que les filtres obtenus ci-dessus sont des filtres de synthèse.La transformée du bloc de taille M et d'indice m peut s'écrire sous les deux formes suivantes, la première définissant le signal en sous-bandes [Xm(k)]k#{0,.., M-1} obtenues en filtrant le signal d'entrée [x(mM+1)]/#{0. , -hA((q + 1)M - 1 - n)x((m + q + 1)M - 1 - )]} On constate donc que sous la seconde forme, un seul passage par la transformation est suffisant, et ceci indépendamment de la condition de la relation (1). Ceci est donc valable pour toute transformation orthogonale. De même pour la synthèse, qui va donner le signal [x(mM+n)]n#{0,...,M-1} où il a été défini Par conséquent, si les (p - 1) derniers vecteurs [um(n)]nefO M-1}sont mémorisés, on peut se contenter d'une seule transformation par bloc, indépendamment de la transformation choisie. On va maintenant montrer qu'il est possible de passer d'un type de banc de filtres, définis par un filtre prototype et une transformation orthogonale, à un autre type de banc de filtres en cours d'analyse de signal, tout en garantissant la reconstruction parfaite. Il s'agit donc d'une opération de commutation. Les applications de ce résultat sont nombreuses, dès lors qu'il s'agit d'adapter un banc de filtres aux variations locales du signal (application de détection, de compression, etc.). On va se limiter, dans un but de simplicité formelle au cas p = 2, étant bien entendu que ceci ne limite en rien la portée du procédé de l'invention. On considère un banc de filtres correspondant àp =2, de filtre prototype noté h. On peut représenter ce banc de filtres par une matrice H de taille [M, 2M], elle-même décomposée en deux matrice carrées Ho et H1. On pose donc H [H0, H1] Les conditions de reconstructions imposent les égalités suivantes tH1.H0 = 0 tH1.H1 + tH0.H0 = IM avec l'opérateur "'" désignant la transposée et IM la matrice identité de dimension M. Les calculs aboutissent à: #k # {0, 1,..,M-1}, #l # {0, 1,..,M-1}, (tH1.H1)k,l=(){h(M + k) + h(M - 1 - k)}.#K-1 + (){h(2M - I - k)h(M+ k) - h(k)h(M- 1 -k)). #M-1-k-l On constate que la matrice tH1.H1 ne possède que des zéros en dehors de ses deux diagonales.Par conséquent, Vk, sous-espace vectoriel engendré par les vecteurs de la base canonique d'indices k et (M- 1 i - k) et stable par rH1.H1 en d'autres termes, I'image de Vk par tH1.H1 est incluse dans Vk. Le calcul du déterminant de la restriction de tH1.H1 à @ Vk donne la valeur 0. Celui de la trace donne la valeur 1. Par conséquent, comme la matrice 'Hl.Hl est symétrieque, tH1.H1 est un projecteur orthogonal sur un espace de dimension M/2. On en déduit que 'Ho.Ho est le projecteur sur l'espace complémentaire orthogonal. On considère que l'on cherche à passer d'un banc de filtres représenté par une matrice de taille [M, 2M], notée [Ho, H1], à un banc de filtres représenté par la matrice [Ko, K1], de taille [R, 2R]. Pour obtenir une reconstruction parfaite, en faisant usage des matrices transposées, on doit filtrer le dernier bloc de taille M et le premier de taille R par une matrice notée [A, B], de taille [rl, M + R], où q est un entier qui sera déterminé ultérieurement, A une matrice de taille [rl, M] et B une matrice de taille [#, R].Les équations de reconstruction parfaite donnent 'B.A = 0 tH1.H1 + tA.A = IM tB.B + tK0.K0 = IR Les deux dernières équations déterminent les rangs de A et B, respectivement M/2 et R/2, d'où l'on déduit par la première équation ##M/2 + R/2 La solution optimale, du point de vue de la décimation, est le cas d'égalité dans l'équation ci-dessus, solution qui sera conservée ci-après, sous l'hypothèse de parité de la somme NI + R. La notation Im(X) désignera l'image de l'espace de départ de la matrice X.On considère ensuite - (W0, . ., WM/2-1} base orthonormée de Im(H0), complétée en {W0,. ,WM-1} base orthonormée de RM - (w0, . ., wR/2-1} 1} base orthonormée de l",(Ho), complétée en {w0,..,wR-1} base orthonormée de Rk. -(Ek)k#{0,...,#-1} base orthonormée de R# - P PA, matrice [M, rl] telle que #k # {0,..,(R/2)-1} PA.Wk = Ek #K # {(M/2),..,M-1} PA.Wk = 0 - PB, matrice [m, P] telle que Vk E (0,. . , (R/2)-1} A Wk = Ek+W2 #k # {(M/2),..,M-1} PA.Wk=0 si on pose A = PA.Ho et B = PB.Kl, I'orthonormalité des bases garantit les conditions de reconstruction parfaite. La commutation de banc de filtre est donc réalisable. Par conséquent, on peut changer la forme du filtre prototype, changer sa taille, ou encore changer de transformation orthogonale, tout en conservant une décimation maximale. On va maintenant décrire deux exemples particuliers de filtres prototypes, l'un pourp = 2, L'autre pourp = 3. Dans le premier cas, les conditions de reconstruction imposent sur h les relations suivantes: h(n)h(M+ n) + h(M- 1 - n)h(2M- 1 - n) = 0 h(n) + h(M - 1 - n) + h(M + n)2 + h(M - 1 - n) = 2 Ces conditions doivent être vérifiées pour tout n dans {0,..,M/2-1}. Pour de telles valeurs de n, une paramétrisation de h vérifiant les conditions cidessus est h(n) = #2cos#n cos#n h(M - 1 - n) = #2cos#n sin#n h(M + n) = -#2sin#n sin#n h(2M - 1 - n) = #2sin#n cos#n Pour le second cas (p = 3), les conditions de reconstruction imposent sur h les relations suivantes: h(n) + h(M + n) + h(2M + n) + h(M - 1 - n) + h(2M - 1 - n) + h(3M - 1 - n) = 2 h(n) + h(N + n) + h(N + n)h(2N + n) + h(N - 1 - n) + h(2N- 1 - n)h(3N- 1 - n)= O h(n) + h(2N + n) + h(N - 1 - n)h(3N - I - n) = 0 Comme précédemment, ces conditions doivent être vérifiées pour tout n dans {0,.., M/2-1}.De même, il est possible de déterminer, pour de telles valeurs de n, une paramétrisation de h: h(n) = #2cos(#n + #n) cos#n cos#n h(M + n) = #2cos#nsin#n h(2M + n) = #2sin(#n + #n) cos#n sin#n h(M - 1-n) = -#2sin(#n + #n) cos#n sin#n h(2M - 1 -n) = #2 sin#nsin#n h(3M - 1 -n) = -#2 cos(#n + #n) cos#n cos#n on va maintenant expliciter des exemples de transformations orthogonales., en choisissant les transformations WI et On suppose que dk obéit à la relation suivante: dk(n)=(2/M)sin(#/4 + kn(2#/M)). On choisit la transformation Wz, plus connue sous le nom de transformation de Hartley. Cette transformation est décrite dans l'article précité de Z. Wang : "Fast Algorithms for the discrete W Transform and for the Discrete Wavelet Transform" L'orthogonalité se vérifie aisément. On peut aussi choisir: dk(n) = (2/M) sin(#/4 + k(n + Dans ce cas, on obtient la transformation WIII, également présentée dans l'article rappelé. Il reste à vérifier l'assertion selon la relation (1). On peut montrer que, pour chacune des deux transformations rappelées, la relation suivante est vérifiée #n # Z, #k # {1,..,M/2-1}, dk(n) + dM-k(n) = 2/M De sorte qu'il suffit de poser: # = {1,..,M/2 - 1} et #k # #, #(k) = M - k On va maintenant considérer le cas des transformations WII et WIV. Si on pose: dk(n) = (2/M)sin(#/4 + (k + )n(2#M)) ou dk(n) = (2/M) sin(#/4 + (k # )(n + )(2#/M)), on retrouve, respectivement, les transformations W et telles que décrites dans l'article précité. L'assertion (1) se vérifie de manière analogue à celle utilisée précédemment Vn E Z, Vk E (1, . . M/2 -1), dk(n)2 + dM-1-k(n) = 2/NI Par conséquent, il peut en être déduit # = {1,..,M/2 - 1} et #k # #, #(k) = M - 1 - k on peut récupérer la phase dans les exemples précédents. Par exemple, pour la transformation WZ, on obtient: #n # Z, #k # {1,..,M/2}, #k,n = -(#/4) Pour la transformation , on obtient: #n # Z, #k # {1,..,M/2-1}, #k,n = -(#/4) + k(n + )(2#/M). On va maintenant illustrer l'application du procédé de l'invention à un dispositif de réduction d'informations d'un flux de signaux audionumériques, par référence à la figure 1. Le dispositif illustré sur cette figure 1, sous la forme de schéma bloc, comprend les modules suivants en cascade un banc de filtres d'analyse 10 recevant, en entrée, les signaux audionumériques précités Se et créant 2M échantillons en M sous-bandes, un module 1 1 d'appariement des M sous-bandes, un module de conversion 12, un module 13 de réduction d'informations audionumériques avec exploitation de la phase, un module de conversion 14, un module 15 d'extraction des parties réelles et complexes et un banc de filtre de synthèse 16, et créant 2Méchantillons en Msous-bandes, et délivrant les signaux de sortie S5. il comprend également un module 16 de calcul de la valeur M. Ce dernier module 16 reçoit également les signaux audionumériques Se d'entrée. Dans l'exemple illustré sur la figure 1, le module 16 détecte la nonstationarité de ces signaux et permet de choisir entre un banc de filtres à 128 sousbandes et un banc de filtres à 512 sous-bandes, avec une valeur de transition possible de 320. La valeur de Mest transmise aux deux modules 10 et 16. Pour chacune de ces longueurs, on dispose d'un filtre prototype et de la transformation WII de taille associée. En sortie du banc de filtres 10, les 2M échantillons en M sous-bandes sont associés 2 à 2, dans le module 11, conformément à la fonction A précédemment définie. A chaque paire, il est associé un complexe comme il a été défini ci-dessus. Ce complexe peut être considéré comme le résultat d'un filtrage complexe, le filtre complexe résulte de la relation (1) et de la formule rappelée ci-dessus pour la transformation . Les filtres réels associés 2 à 2 présentent des réponses en fréquence voisines, car ils sont chacun le résultat de la modulation du filtre prototype par une fonction de type sinus de même période. Par contre, ils sont en quadrature, puisque l'othogonalîté de la transformation modulante garantit celle du banc de filtres. On peut alors procéder au calcul du module de phase pour chaque paire, sur laquelle on effectue un traitement spécifique dépendant de l'algorithme de réduction d'information retenu, ce en tenant compte de l'interprétation fréquentielle de la sortie de chaque filtre complexe. La reconstruction s'effectue dans des conditions inverses, le procédé selon l'invention assurant cette propriété d'inversibilité. De façon plus précise, dans l'exemple illustré, le module de conversion 13 effectue cette conversion de manière à ce que les relations suivantes soient satisfaites # = |zk|, #k = Arg(zk), avec k # {0,..,M/2 - 1) De même, le module de conversion inverse 14 effectue une conversion répondant à la relation suivante: zk = #k(cos#k + sin#k), avec k # {0,..,M/2 - 1} I'extraction des parties réelles et complexes est une fonction tout à fait classique, qu'il est inutile de détailler. A la sortie du banc de filtres de synthèse 16, le signal d'entrée est donc reconstruit, avec un certain délai. A la lecture de la description qui précède, on constate aisément que l'invention atteint bien les buts qu'elle s'est fixés. Cependant, il doit être clair que l'invention n'est pas limitée aux seuls exemples de réalisations précisément décrits, notamment en relation avec la figure 1. Il doit être clair aussi que, bien que particulièrement adaptée à l'application de réduction d'informations audionumériques décrite également en regard de la figure 1, on ne saurait cantonner l'invention à ce seul type d'applications. Elle s'applique tout aussi bien, comme il a été rappelé, à de nombreux domaines : traitements d'images, à la réalisation de fonctions de lissage et d'interpolation ou de manière plus générale, à tout système susceptible de tirer partie de la représentation complexe d'un signal, par exemple dans un but de détection ou de quantification. REVENDICATIONS 1. Procédé inversible de décomposition complexe en fréquence d'un signal numérique comprenant une étape de décomposition en sous-bandes de sortie de ce signal numérique et une étape de recomposition de ces sous-bandes de sortie, ladite décomposition étant effectuée à l'aide d'une transformée basée sur un filtre dit "prototype" et une transformation unitaire déterminés, caractérisé en ce que ledit filtre est de taille multiple de ladite transformation et en ce que cette transformation et choisie de sorte que, une fois définie par des lignes et colonnes dans une base orthonormée déterminée, elle possède un ensemble non vide de colonnes, appariables par paires, telles que chacun des points en dimension 2, dont les coordonnées sont les coefficients d'une même ligne de chacune desdites deux colonnes appariées, appartient à un cercle de rayon prédéterminé. 2. Procédé selon la revendication 1, caractérisé en ce que ladite recomposition de ces sous-bandes de sortie est réalisée à partir des colonnes appariées de la dite transformation. 3. Procédé selon les revendications 1 ou 2, caractérisé en ce que pendant ladite étape de recomposition des sous-bandes de sortie, les caractéristiques dudit filtre prototype déterminé sont modifiées adaptativement aux caractéristiques dudit signal numérique. 4. Procédé selon les revendications 1 ou 2, caractérisé en ce que pendant ladite étape de recomposition des sous-bandes de sortie, les caractéristiques de ladite transformation déterminée sont modifiées adaptativement aux caractéristiques dudit signal numérique. 5. Application du procédé selon l'une quelconque des revendications précédentes à un dispositif de réduction du flux d'informations de signaux audionumériques.