Brevet FR2643986A1 — publié le 19900907

PROCEDE D'ANALYSE D'UN SIGNAL PAR ONDELETTES La présente invention se rapporte aux procédés d'analyse d'un signal qui permettent de décomposer ce signal en utilisant une base orthonormée de fonctions appelée ondelettes. Il est très connu d'utiliser pour analyser des signaux, soit une décomposition en série de Fourier si ce signal est périodique, soit une intégrale de Fourier si ce signal n'est pas périodique. Ces méthodes sont très puissantes mais elles présentent un certain nombre d'inconvénients. Ces inconvénients sont particulièrement notables pour le cas des signaux de courte durée pour lesquels ces méthodes ne sont manifestement pas adaptées. On sait cependant que les signaux de courte durée représentent une partie importante des phénomènes naturels, particulièrement dans le domaine sonore o les bruits de toute nature durent rarement plus de quelques secondes et sont souvent bien inférieurs à la seconde. Jean MORLET a proposé, il y a quelques années, une méthode d'analyse dite par ondelettes qui est particulièrement adaptée à ce domaine des signaux de courte durée, et notamment aux bruits impulsifs. Cette analyse par ondelettes est exposée de manière très compréhensible dans le numéro de septembre 1987 de la revue POUR LA SCIENCE. Cet article comporte en particulier une explication des raisons pour lesquelles la méthode de Fourier est mal adaptée aux signaux de courte durée. Etant donné une base orthonormée d'ondelettes comprenant m+1 ondelettes0 à m et une échelle m la décomposition d'un signal S(t) s'effectue selon une série d'opérations représentées schématiquement sur la figure 1: le signal S (t) échantillonné sur N points est convolué avec l'ensemble des vecteurs de la base orthonormée m0 à met par m. Le produit de convolution de S(t) par l 0 donne N points déterminant les coefficients d'ondelette d'ordre 0. Le produit de convolution de S(t) par 1 donne N points qui sont les coefficients d'ondelette d'ordre i etc., jusqu'au produit de convolution de S(t) par m qui donne les N coefficients m d'ondelette d'ordre m. Enfin le produit de convolution de S(t) par * m donne N points qui sont Ies coefficients d'échelle d'ordre m. On remarque que -l'on obtient ainsi pour définir le signal analysé, qui comporte lui-même N points, (m + 2) N points d'analyse. Il y a donc une redondance d'information, qui est cependant nécessaire dans cette méthode de décomposition, utilisée notamment avec les ondelettes dites de Haar. Ingrid DAUBECHIES, de L'AT&T Bell Laboratories à Murray Hill, a calculé des ondelettes dites à support compact qui sont parfaitement adaptées à un algorithme de décomposition rapide imaginé par Stéphane MALLAT, de l'Université de Pennsylvanie. Dans cet algorithme, représenté en figure 2, on part aussi d'un signal S(t) échantillonné sur N points, mais on n'utilise que l'ondelette 4 et l'échelle 4 0 dans une série de p étapes successives. A la première étape, on effectue un produit de convolution de S(t) par $ 0 et par e 0 et on sélectionne un point sur deux des N points de ces produits de convolution, ce qui donne deux fois N/2 points, soit N points comme au départ. Bien entendu ce sous-échantillonnage s'effectue encore plus faci- lement en ne procédant dans les calculs des produits de convolution qu'à un calcul sur deux. Les N/2 points provenant du produit de convolution de S par 4 0 sont mis en mémoire et on procède dans une deuxième étape aux produits de convolution par 0 et par " 0 des N/2 points provenant de e O dans la première étape en sélectionnant un point sur 2 des N/2 points provenant du calcuI. Cette deuxième étape est donc tout à fait Identique à la première sauf que l'on part non pas du signal S (t) défini sur N points, mais du produit de convolution de S(t) par 0 défini sur N/2 points. La suppression d'un point sur deux donne donc 2 fois N/4 points. Pour l'étape suivante, on mémorise les N/4 points du traitement par * 0 et l'on recommence le même calcul sur les N/4 points provenant de la convolution par 0' Et ainsi de suite. A l'étape p on effectue les produits de convolution par *0 et 0# des N/2P'I points provenant de la convolution par #0 à l'étape p -1 en sélectionnant un point sur 2 ce qui donne deux fois N/2P. On voit ainsi qu'à cette étape p on dispose des 2 fois N/2P points provenant de cette étape p, plus les N/2, N/4 etc. N/2P'1 points mis en mémoire lors des étapes 1 à pl, soit au total N points qui représente l'analyse du signal S(t) par rondelette 4 O et l'échelle * 0' Il n'y a donc pas de redondance dans le Jeu de coefficients obtenu et dont MALLAT a démontré qu'ils représentent correctement S(t). Cet algorithme peut se poursuivre bien entendu jusqu'à une étape p telle que 2P = N, mais on a observé expérimentalement que les coefficients ainsi obtenus se stabilisaient très rapidement au bout de quelques étapes, par exemple 5 à 6. On peut donc s'arrêter très rapidement dans les calculs successifs et cette pratique a été Justifiée en procédant à la reconstruction du signal S (t) à partir des N points obtenus à l'étape p, en effectuant le traitement inverse. On a constaté que le signal S(t) ainsi reconstitué était très semblable au signal initial dès que les coefficients étaient stabilisés après 5 ou 6 itérations comme décrit plus haut. Cette décomposition étant effectuée, il reste à utiliser les N coefficients pour obtenir par exemple une classification des signaux analysés. Le problème est de même nature que celui qui consiste, lorsque l'on utilise la décom- position en série de Fourier, à déterminer l'origine du signal décomposé à partir du spectre obtenu. C'est ainsi que l'on distingue le son émis par un violon de celui émis par un saxophone, parce qu'ils n'ont pas le même spectre. On remarquera que ces deux instruments pris pour exemple peuvent émettre un son continu susceptible d'être correctement analysé par une série de Fourier. Dans le cas d'un piano, qui émet des notes brèves, l'utilisation d'une série de Fourier est bien moins indiquée et celle de la décomposition en ondelettes serait beaucoup plus intéressante. Différents procédés pour interpréter les coefficients d'ondelettes ont été proposés. On peut ainsi introduire ces coefficients dans un réseau neuronique qui procédera à la classification par auto-apprentissage. Une autre méthode consiste à appliquer les signaux sur un dispositif de visua- lisation XY. On obtient ainsi des figures telles que celles qui sont représentées sur les pages 35 et 36 de l'article de POUR LA SCIENCE cité plus haut. On ne sait pas encore très bien identifier ces figures, et l'un des problèmes qui se pose est qu'elles se présentent sous une forme arborescente qui est relativement confuse. Cette forme arborescente provient de ce que l'on a, selon l'algorithme de MALLAT, un nombre de signaux qui décroît au fur et à mesure des étapes. Pour pallier cet inconvénient et obtenir un jeu de signaux homogènes l'invention propose un procédé d'analyse d'un signal S(t) échantillonné sur N points par une ondelette O0 et une échelle * 0 principalement caractérisé par les étapes suivantes: - une première étape o on effectue les convolutions de S(t) par l0 et O O en sous-échantillonnant d'un facteur 1/2 les résultats de ces convolutions pour obtenir deux premiers ensembles de N/2 points; - une deuxième étape o on effectue les convolutions de chacun des deux premiers ensembles par 40 et *0 en souséchantillonnant d'un facteur 1/2 les résultats de ces convolutions pour obtenir 4 deuxièmes ensembles de N/4 points - une itération arborescente de ces étapes jusqu'à: - une plème étape o on effectue les convolutions (P - P2P) de chacun des 2P'1 ensemble de l'étape p-1 par *D et 0 en souséchantillonnant d'un facteur 1/2 les résultats de ces convolutions pour obtenir un 2P pième ensemble de N/2P points. (reven). D'autres particularités et avantages de l'invention apparaîtront clairement dans la description suivante faite à titre d'exemple non limitatif en regard des figures annexées qui représentent: - la figure 1: le schéma de décomposition en ondelettes selon les bases de la théorie des ondelettes; - la figure 2: un schéma de décomposition selon l'algorithme de MALLAT; la figure 3: un schéma de décomposition selon l'invention; et - la figure 4: le schéma d'un dispositif permettant de mettre en oeuvre la décomposition selon l'invention. On a représenté sur la figure 3, avec les mêmes conventions que pour les figures 1 et 2, la décomposition d'un signal S(t) échantillonné sur N points selon le procédé suivant l'invention. Dans une première étape, identique à celle de l'algorithme de MALLAT, on procède à une convolution de S(t) par * 0 et Jo et on réduit par 2 le nombre de points obtenus pour obtenir N/2 points provenant de la convolution par 0 et N/2 points de la convolution par e0. Cette réduction équivaut à un sous-échantlllonnage. Dans la deuxième étape on effectue, là aussi comme dans l'algorithme de MALLAT, une convolution par *0 et 0 sur les N/2 points provenant de la convolution précédente par 0 mais, au lieu de limiter cette étape à ce point en mémorisant les N/2 points de la convolution par * 0 dans l'étape 1, on effectue également une convolution par * 0 et G b0 sur ces N/2 points de la convolution par 0 dans l'étape 1. On obtient ainsi 4 fois N/4 points, provenant de deux convolutions par O 0 et de deux convolutions par 0 sur les 2 fois N/2 points provenant de l'étape 1, compte tenu de la réduction par 2 du nombre de points provenant de la convolution, c'est-à-dire bien entendu de la limitation des caleuls à ceux uniquement nécessaires. Dans Ies étapes suivantes on itère ce processus pour parvenir à I'étape p dans laquelle on procède à 2P-1 convolution par ip 0 et 2P-1 convolution par e 0 sur les 2P-1 fois N/2P-1 points provenant de l'étape p-1. Au total on a donc bien au terme de l'étape p N points provenant de l'analyse du signal S (t) par r'ondelette 0 et l'échelle 4 0. On peut limiter le nombre d'étapes en fonction des mêmes critères que ceux utilisés pour l'application de l'algorithme de MALLAT. On constate que la répartition de ces N points après l'étape P est homogène, ce qui permet d'appliquer les signaux correspondant par exemple sur un dispositif de visualisation comportant 2P rangées et N/2p colonnes. Tous les points d'un tel dispositif de visualisation sont homogènes quant à leur signification, ce qui permet de faciliter l'interprétation des figures obtenues et leur classification. On a représenté sur la figure 4 le schéma d'un dispositif permettant de mettre en oeuvre la décomposition selon l'invention. Le signal S(t), supposé analogique, est appliqué à un convertisseur analogique/numérique 101. Celui-cl échantillonne le signal S à une fréquence H0, déterminée par un circuit d'horloge 102, et il numérise ensuite les échantillons ainsi obtenus. La fenêtre sur laquelle le signal S sera échantillonné dépend des phénomènes à analyser. Elle peut être pour des signaux sonores audibles de l'ordre de quelques dizaines de ms. La fréquence d'échantillonnage sera alors par exemple de quelques dizaines de KHz et l'échelle de numérisation portera par exemple sur 14 éléments binaires. Le signal ainsi échantillonné/numérisé est alors convolué dans deux dispositifs de convolution 201 et 202 respectivement avec le signal d'ondelette * 0 et le signal d'échelle * 0' Ces signaux forment une base orthogonale à support compact, et de préférence sont ceux des ondelettes de DAUBECHIES qui sont représentées par les valeurs contenues dans le tableau en figure 5 (limité à un ordre 10). Les valeurs numériques données dans ce tableau sont mémorisées dans une mémoire 103 qui les délivre aux circuits 201 et 202. Ces circuits reçoivent par ailleurs des signaux d'horloge H1 délivrés par le circuit 102, qui sont à la fréquence moitié de H afin d'obtenir un échantillonnage des signaux convolués à la fréquence moitié de celle de l'échantillonnage du signal S(t), comme on l'a expliqué plus haut. Les signaux S 1,1 délivrés par le circuit 201 sont alors appliqués à deux circuits de convolution 301 et 302 qui fonctionnent exactement de la même manière que les circuits 201 et 202, mais sous l'action d'un signal d'horloge H2 fourni par le circuit 102 à la fréquence moitié du signal H1, et donc au 1/4 de la fréquence du signal H0. De même le signal S1,2 fourni par le circuit 202 est fourni à deux circuits 303 et 304 qui fonctionnent comme les circuits 301 et 302, à partir aussi de l'horloge H2. Le dispositif se développe ensuite de manière arborescente selon la même loi pour arriver à un étage p comportant 2P circuit de convolution P1 à p2p identiques aux circuits de base 201 et 202. Ces circuits reçoivent deux par deux les signaux provenant de l'étage précédent, ainsi que les signaux d'ondelettes du circuit 103 et une horloge H à la P fréquence 1/2P par rapport à la fréquence de l'horloge H0. On obtient ainsi en sortie de cet étage les signaux Sp1 à Sp, 2p. L'ensemble des signaux S,1 A Sp 2p sortant de tous les étages est appliqué à un sélecteur 104 qui permet de sélectionner la profondeur de I'analyse, c'est-A-dire l'étage sur lequel on va effectuer la visualisation des résultats obtenus par la décomposition. Ce sélecteur permet de sélectionner l'ensemble des signaux correspondant A un étage, c'est-A-dire par exemple S11 et S12 o Sp1 A Sp2p. 1,1 1,2 pl p,2p' En effet, comme on l'a vu plus haut, la décomposition devient rapidement stationnaire et il n'est pas alors nécessaire de poursuivre le traitement pl]us loin, ce qui est intéressant puisque les produits de convolution correspondent A des calculs relativement longs. Les signaux ainsi sélectionnés peuvent être appliqués à différents appareils d'interprétation. On a représenté sur la figure 4 un appareil d'interprétation simple 105 qui est un simple dispositif de visualisation comportant 2P rangées et N/2P colonnes. Les signaux sont appliqués sur les rangées et leur variation le long des colonnes correspond A une échelle de temps qui est celle de la fenêtre d'analyse du signal S(t) divisé en N/2P points. Selon la profondeur de la sélection choisie un même signal pourra être appliqué A plusieurs rangées, puisque leur nombre est prévu pour appliquer le nombre maximum de signaux délivrés par l'étage p. Dans un autre exemple, les signaux sont appliqués A un réseau neuronal 106. Celui-ci, comme on le sait, se configure automatiquement, selon un système d'auto-apprentissage au fur et A mesure qu'on lui applique des signaux d'analyse. Après avoir reçu un certain nombre de signaux correspondant A des classes différentes de signaux S(t) analysés, le réseau neuronaI donnera une réponse permettant de classer tout signal S(t) analysé ensuite dans l'une des diverses catégories résultant justement de l'autoapprentissage du réseau neuronal. Comme on le constate, la seule opération de calcul effectuée dans ce dispositif est un produit de convolution et les résultats sont obtenus par la combinaison de ces produits, ainsi que bien entendu par l'usage des coefficients d' ondelette et des fréquences d'horloge appropriées. On peut donc très bien, à titre de variante, utiliser un nombre réduit de circuits de convolution tels que 201 et 202, et même à la limite un seul de ces circuits, en lui appliquant par un jeu de commutateurs appropriés, obtenus par exemple à l'aide d'un circuit combinatoire, les signaux nécessaires. Ces signaux sont d'une part les résultats précédents convenablement mémorisés, et d'autre part les signaux d'ondelettes fournis à la demande par la mémoire 103, ainsi que les signaux d'horloge fournis eux aussi à la demande par le circuit 102. Les temps de traitement seront bien entendu nettement plus longs et les signaux pour une même profondeur d'analyse ne seront pas tous disponibles au même moment, puisqu'ils seront progressivement mémorisés dans la mémoire Intermédiaire. En contrepartie le volume du matériel utilisé sera bien moins Important. Dans ces conditions, et comme autre variante de réalisation, on peut utiliser un ordinateur standard convenablement programmé pour effectuer toutes ces opérations. Le produit de convolution en lui-même est un calcul qui s'effectue couramment dans un ordinateur avec des programmes existant dans le commerce, et la séquence des traitements successifs peut être obtenue par une programmation adéquate dans laquelle on range les résultats intermédiaires en mémoire pour les ressortir lorsqu'ils sont nécessaires. De même les coefficients d'ondelettes sont placés dans la mémoire centrale de l'ordinateur, et dans la séquence des opérations on prévoit d'effectuer le produit de convolution sur le nombre de points nécessaires pour le pas de la décomposition. Bien que la conversion analogique/numérique puisse se faire elle aussi dans l'ordinateur, il est quand même souhaitable d'utiliser pour cette fonction un circuit spécialisé qui sera plus rapide. On peut également utiliser un circuit spécialisé pour effectuer la convolution, là aussi pour des questions de rapidité, puisque beaucoup de micro-ordinateurs prévoient l'usage d'un coprocesseur associé au microprocesseur afin de faire des calculs particuliers. REVENDICATIONS 1. Procédé d'analyse d'un signal S (t) échantillonné sur N points par une ondelette * 0 et une échelle 0' caractérisé par les étapes suivantes - une première étape o on effectue les convolutions (201, 202) de S(t) par *0 et o O en sous-échantillonnant d'un facteur 1/2 les résultats de ces convolutions pour obtenir deux premiers ensembles de N/2 points - une deuxième étape o on effectue les convolutions (301-304) de chacun des deux premiers ensembles par 4 0 et d0en sous-échantillonnant d'un facteur 1/2 les résultats de ces convolutions pour obtenir 4 deuxièmes ensembles de N/4 points; - une itération arborescente de ces étapes jusqu'à - une pième. étape o on effectue les convolutions (Pl P2p) de chacun des 2p'1 ensemble de l'étape p-i par 40 et 4O en sous-échantillonnant d'un facteur 1/2 les résultats de ces convolutions pour obtenir un 2P pième ensemble de N/2P points. 2. Procédé selon la revendication 1, caractérisé en ce que l'échelle et l'ondelette utilisées forment une base orthogonale compacte. 3. Procédé selon la revendication 2, caractérisé en ce que l'échelle et l'ondelette utilisées sont une échelle et une ondelette de DAUBECHIES. 4. Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce que l'on arrête l'analyse à un stade intermédiaire lorsque les résultats deviennent sensiblement stationnaires. 5. Dispositif pour la mise en oeuvre du procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce qu'il comprend un convertisseur analogique/numérlque (101) permettant d'échantillonner et de numériser sur N points un signal S(t) entrant, un circuit d'horloge (102) permettant de délivrer un signal d'horloge H0 à la fréquence d'échantillonnage et des signaux d'horloge H1-Hp dont les fréquences successives sont des sous-multiples de 2 de H0, un circuit de mémoire (103) permettant de mémoriser et de délivrer les signaux d'échelle 7 0 et d'ondelette * 0, et p ensembles de convoluteurs (201, p2p), chaque ensemble j comportant 21convoluteur recevant deux par deux respectivement les 23-1 signaux fournis par l'ensemble de rang j-1, ainsi que les signaux 40 et 0 et le signal d'horloge Hj, des moyens de sélection (104) recevant l'ensemble des signaux des convoluteurs et permettant de sélectionner les signaux fournis par un ensemble de convoluteurs, et des moyens (105, 106) d'interprétation des signaux ainsi sélectionnés. 6. Dispositif pour la mise en oeuvre du procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce qu'il comporte un convoluteur (201), un circuit de mémoire (103) permettant de mémoriser et de délivrer les signaux 40 et 0 et un circuit d'horloge permettant de délivrer un signal d'horloge H0 à la fréquence d'échantillonnage et des signaux d'horloge H1 - Hp sous-multiple de 2p de H0, un circuit de mémoire permettant de mémoriser les calculs intermédiaires et un circuit de sélection permettant de faire effectuer par le circuit unique de convolution I'ensemble des calculs de convolution des p étages. 7. Dispositif pour la. mise en oeuvre de l'une quelconque des revendications 1 à 4, caractérisé en ce qu'il comporte un ordinateur convenablement programmé. 8. Dispositif selon l'une quelconque des revendications 5 à 7, caractérisé en ce que les circuits d'interprétation sont constitués d'un dispositif de visualisation (105) comportant 2P rangées et NP colonnes. 9. Dispositif selon l'une quelconque des revendications 5 à 7, caractérisé en ce que le circuit d'interprétation conporte un réseau neuronal (106).