Note: Descriptions are shown in the official language in which they were submitted.
CA 02836421 2013-11-14
- 1 -
REGROUPEMENT DYNAMIQUE DE SIGNAUX TRANSITOIRES
CHAMP DE L'INVENTION
La présente invention porte sur des méthodes d'analyse de signaux, et plus
particulièrement sur un système et une méthode de regroupement dynamique
de signaux transitoires.
HISTORIQUE
On retrouve des signaux transitoires dans une multitude de domaines tels les
radars, les décharges partielles, les bruits d'arc (décharge instationnaire
dans
un plasma), les fluctuations du cours de la bourse, la cavitation d'un fluide,
l'émission acoustique, les secousses telluriques et en imagerie.
Un problème récurrent dans plusieurs de ces domaines est que le traitement
distinct de chaque transitoire requiert un effort de calcul exagéré et cible
un
signal bruité.
Les brevets / demandes de brevets US 6,088,658 (Yazici et al.), US 6,868,365
(Balan et al.), US 7,579,843 (Younsi et al.) et US 2008/0088314 (Younsi et
al.)
fournissent des exemples de systèmes et méthodes antérieurs d'analyse de
signaux, impliquant des tâches informatiques et de calcul longues et
gourmandes en ressources.
SOMMAIRE
Un objet de l'invention est de proposer un système et une méthode de
regroupement de signaux transitoires, qui regroupe des transitoires similaires
en une signature caractéristique afin de traiter un nombre réduit de
signatures
pour les groupes, e.g. une signature par groupe. Comme il y a moins de
signatures que de transitoires capturées, le temps de calcul est réduit. Une
- 2 -
signature étant moins bruitée que ses constituants séparés, le résultat du
traitement est d'autant plus précis et le résultat est déjà classifié.
Selon un aspect de la présente invention, il est proposé une méthode de
regroupement de signaux transitoires mise en oeuvre par ordinateur,
comprenant les étapes de:
acquérir les signaux transitoires;
construire dynamiquement des groupes de signaux transitoires similaires
dans un hyperespace selon des règles de comparaison et de regroupement de
manière que chaque nouveau signal transitoire acquis aboutisse dans un
groupe avec des signaux transitoires similaires précédemment acquis;
analyser les groupes pour déterminer des signatures respectives définies
par les signaux transitoires accumulés dans les groupes; et
traiter les signatures pour détecter un phénomène rattachable à un
attribut intrinsèque des signaux transitoires,
dans laquelle l'étape de construire des groupes comprend les étapes de
fusionner des signaux transitoires similaires et des groupes similaires
lorsqu'un
nombre maximum prédéterminé de groupes est atteint, et calculer de nouveaux
paramètres des règles de comparaison et de regroupement applicables au
regroupement de nouveaux signaux transitoires acquis, et
dans laquelle, pour réduire un temps de calcul pour détecter le
phénomène, l'ordinateur s'abstient de déterminer une signature pour chacun
des signaux transitoires et détermine une signature respective pour chacun des
groupes construits dynamiquement.
Selon un autre aspect de la présente invention, il est aussi proposé un
système
informatique ayant un processeur et une mémoire stockant des instructions
exécutables destinées à être exécutées par le processeur pour effectuer les
étapes de la méthode.
Selon un autre aspect de l'invention, il est proposé un support tangible et
non
transitoire de stockage lisible par ordinateur stockant des instructions
CA 2836421 2019-05-06
- 2a -
exécutables destinées à être exécutées par un système informatique pour
effectuer les étapes de la méthode.
Selon un autre aspect de l'invention, il est proposé une méthode d'analyse de
signaux transitoires bruités observés dans le temps ou l'espace mise en oeuvre
par ordinateur, la méthode comprenant les étapes de:
capturer les signaux transitoires bruités;
construire dynamiquement des groupes de signaux transitoires similaires
dans un hyperespace selon des règles de comparaison et de regroupement de
manière que chaque nouveau signal transitoire bruité capturé aboutisse dans
un groupe stocké dans la mémoire avec des signaux transitoires bruités
similaires précédemment capturés au moment de la capture, en comparant
chaque nouveau signal transitoire bruité capturé avec des signatures de
groupes définies par les signaux transitoires bruités précédemment capturés,
les règles de comparaison et de regroupement utilisant des métriques
modélisant chaque groupe près d'une hypersphère ayant un rayon
caractéristique du bruit dans les signaux transitoires bruités accumulés dans
le
groupe, des signaux transitoires similaires et des groupes similaires étant
fusionnés lorsqu'un nombre maximum prédéterminé de groupes est atteint et de
nouveaux paramètres des règles de comparaison et de regroupement
applicables au regroupement de nouveaux signaux transitoires acquis étant
déterminés;
analyser les groupes de sorte que des signatures respectives définies
par les signaux transitoires bruités accumulés dans les groupes soient
déterminées; et
traiter les signatures de manière qu'un phénomène rattachable à un
attribut intrinsèque des signaux transitoires bruités soit détecté, l'étape
d'analyser les groupes s'abstenant de déterminer une signature pour chacun
des signaux transitoires et déterminant une signature respective pour chacun
des groupes construits dynamiquement pour réduire un temps de calcul pour
détecter le phénomène.
CA 2836421 2019-05-06
- 2b -
DESCRIPTION BREVE DES DESSINS
Une description détaillée des réalisations préférées de l'invention sera
donnée
ci-après en référence avec les dessins suivants:
Figure 1 est un organigramme illustrant la méthode selon l'invention.
Figure 2 est un diagramme schématique illustrant deux groupes.
CA 2836421 2019-05-06
CA 02836421 2013-11-14
- 3 -
Figure 3 est un graphique illustrant une signature de décharge partielle d'un
groupe de mesures (ligne large) et un instantané d'une mesure (ligne mince).
Figure 4 est un histogramme illustrant une puissance de résolution.
Figure 5 est un histogramme illustrant une cohérence de groupe.
Figure 6 est un histogramme illustrant un nombre de groupes par séquence.
Figure 7 est un graphique illustrant une diminution du temps de traitement
avec
un paramètre cest.
Figure 8 est un diagramme de décharge partielle à résolution de phase de
groupes superposés.
DESCRIPTION DÉTAILLÉE DES RÉALISATIONS PRÉFÉRÉES
Dans la présente divulgation, le temps ou l'espace peuvent être remplacés par
toute autre dimension de toute autre nature.
La présente invention vise les signaux transitoires qui ont pour
caractéristiques
d'être répétitifs pour une partie de leur population. Par répétitif, on entend
que
l'on peut observer une même transitoire plus d'une fois dans le temps ou
l'espace, avec une amplitude qui peut différer et aussi avec une faible
dissimilitude qui peut s'expliquer par du bruit, une erreur de mesure, une
distorsion temporelle ou spatiale du support de la transitoire ou tout autre
phénomène modélisable (numériquement, analytiquement ou statistiquement).
.. La présente invention propose de regrouper dynamiquement les transitoires,
c'est-à-dire au fur et à mesure qu'elles sont capturées par le système de
mesure ou acquises par un dispositif approprié. Par regrouper, on entend
assembler sous un même groupe les transitoires similaires, un groupe donné
CA 02836421 2013-11-14
- 4 -
contenant alors au moins une transitoire, et le résultat donnant au moins un
groupe ayant plus d'une transitoire lui étant associée. Un regroupement qui
n'est pas dynamique signifie que la comparaison se fait avec toutes les
transitoires en main; bien que plus proche de l'optimalité, le temps de calcul
de
cette approche est exhaustif.
Présenté dans un espace 91", où N est un nombre de points temporels ou
spatiaux caractérisant une transitoire, un regroupement apparait tel un nuage
de points dans cet hyperespace. Le centre de masse de ce regroupement qui
correspond à la moyenne des transitoires du regroupement sera appelé
signature.
La comparaison transitoire-à-transitoire, transitoire-à-signature ou signature-
à-
signature demande un recalage temporel ou spatial afin de maximiser la
corrélation ou de minimiser la distance entre les deux objets de comparaison.
Dans le cas d'un critère de comparaison basé sur la distance, à l'ordre zéro,
le
réalignement est réalisé d'un bloc tel que
Dõ,,,= min 1\li
õ.1
"{ TfT21
décrit la distance entre la transitoire X et la signature S. Il est possible
de
réaliser un réalignement au premier ordre en interpolant la transitoire (ou la
signature) de façon à l'étirer ou la compresser. Il en est de même pour le
second ordre. De plus, une méthode de type adaptation temporelle dynamique
("Dynamic Time Warping") peut être envisagée comme moyen de recalage
pour le calcul de distance. Essentiellement, un recalage adéquat entre les
deux
objets de comparaison doit avoir lieu dans la comparaison.
En référence à la Figure 1, la méthode selon l'invention procède comme suit.
Des transitoires sont capturées tel que représenté par le bloc 2 et font
l'objet
d'un regroupement tel que représenté par le bloc 4 pour une construction
dynamique de groupes avec des signatures des groupes. Les signatures sont
analysées tel que représenté par le bloc 6 de manière à déterminer des
CA 02836421 2013-11-14
- 5 -
caractéristiques de signature utilisable pour un traitement additionnel relié
à la
nature des transitoires à l'étude tel que représenté par le bloc 8. La méthode
peut être mise en oeuvre dans un système informatique ayant un processeur et
une mémoire stockant des instructions exécutables destinées à être exécutées
par le processeur pour effectuer les étapes énumérées ci-dessus. La méthode
peut aussi prendre la forme d'un support tangible et non transitoire de
stockage
lisible par ordinateur stockant des instructions exécutables destinées à être
exécutées par un système informatique pour effectuer les étapes de la
méthode.
Ce qui suit fournit un exemple de réalisation de l'invention dans un contexte
de
détection, localisation et analyse de décharge partielle. Il convient de
préciser
que l'invention n'est pas limitée à de telles réalisation et application, et
que des
changements et modifications peuvent être apportés sans s'écarter de
l'invention.
La méthode selon l'invention peut être utilisée pour une classification de
transitoires par un regroupement temporel dynamique. Dans une voûte
souterraine d'un réseau de distribution électrique, plusieurs centaines de
signaux transitoires peuvent être capturés en quelques secondes, dont
plusieurs sont des décharges partielles (DP). Un traitement de signal et une
reconnaissance de forme pour chaque transitoire prennent beaucoup de temps.
Le groupement de M transitoires en I groupes réduit dramatiquement le temps
de traitement et augmente significativement le rapport signal-bruit des
signatures I correspondantes. Le regroupement peut être fait sur plusieurs
centaines de dimensions N, avec chaque dimension correspondant à un
échantillon temporel de signal. Étant donné que la position temporelle d'une
transitoire est corrompue par une fluctuation temporelle, la fonction de
distance
est calculée pour T alignements temporels différents. Une heuristique
semblable à l'algorithme des k moyennes s'explique sur la base du phénomène
de "durcissement de sphère" ("sphere hardening") et a une complexité
0(T xNxM xl) pour / groupes. Différents outils sont proposés pour évaluer la
CA 02836421 2013-11-14
- 6 -
précision du processus de regroupement et optimiser certains paramètres de la
méthode.
Les signaux à traiter selon l'invention peuvent être échantillonnés e.g. à 1
Gs/s,
filtrés, interpolés et tronqués. Quelques centaines d'échantillons temporels N
décrivent la forme transitoire. Pour une localisation "i' d'émission de DP, en
présumant une signature temporelle normalisée constante si (t) sur des
amplitudes différentes, on obtient
xn,(t)- am = si(t ¨4,7)+ nm(t) (1)
la réalisation de la mesure "rn" d'une signature de transitoire, où am est
l'amplitude de réalisation, tin le délai de réalisation et tin, le bruit
additif. La
modélisation correspondante est
Xmn =am =Sn-dm nmn (2)
avec discrétisation. Les mesures successives prises sur une échelle d'entrée
analogique sont appelées une séquence. La plage dynamique am peut être
inférieure à 10 dB pour une séquence, i.e. le rapport du niveau d'écrêtage sur
le
seuil de réglage de déclenchement. La première étape de regroupement peut
être effectuée pour une échelle fixe. La plage dynamique complète peut ensuite
être obtenue dans une deuxième étape en fusionnant les groupes obtenus à
partir de différentes échelles A/N. Dans certains cas, la plage dynamique a,
peut dépasser 30 dB.
En présumant un bruit gaussien et en négligeant la dynamique am, la projection
91" montre une hypersphère centrée sur la signature "f'
Si = (Si,/ (3)
où les mesures
X,, } (4)
sont près de la frontière de l'hypersphère. L'épaisseur de la frontière est
fonction de la métrique, du rapport signal-bruit (RSB) de mesure et du nombre
d'échantillons temporels N. Pour une métrique euclidienne, la distance
CA 02836421 2013-11-14
- 7 -
N
Dmi = min I n=1 Vntn_d¨si,n)2} (5)
def_I,E1
1 2 2j
a la moyenne prévue
r, = E(D,õ,,)= ,sINE(nm2 n) (5)
pour xm c groupe "r et l'écart-type
csi VE(hm2õ). (7)
En référence à la Figure 2, le rayon et l'épaisseur de la frontière
d'hypersphère
sont respectivement illustrées dans 91N, r, et 2.cr,. Le rapport de
l'épaisseur de
la frontière sur le rayon d'hypersphère tend vers 0 lorsque N---¶*. Ce
phénomène est appelé durcissement de sphère ("sphere hardening"). Calculée
en utilisant de nombreux échantillons bruités, la distance Xm-S, est à peine
constante. Il n'y a pas de mesures dans l'hypersphère sauf près de sa
frontière.
Dans 91", des densités de probabilités de groupes apparaissent comme des
coquilles distribuées avec des rayons et épaisseurs similaires. Avec la
présence d'une dynamique am significative, la signature à point unique est
remplacée par une tige pointant vers l'axe d'origine. La coquille
correspondante
est dilatée le long de l'axe de la tige. L'épaisseur de coquille est augmentée
dans la direction de la tige. Des signatures apparaissent comme des coquilles
distribuées avec une fonction d'élongation inégale de la dynamique
d'amplitude.
L'utilisation d'une métrique appropriée peut surmonter partiellement cette
distorsion de coquille.
Dans un regroupement dynamique, le nombre de groupes et l'emplacement du
centre de masse d'un groupe peuvent être ajustés dynamiquement. La
dimension de travail peut être limitée par imax, le maximum de signatures
permises et imin, le minimum de signatures permises. Une estimation roulante
de la distance moyenne mesure-à-signature peut être réalisée durant le
traitement d'une séquence. La distance moyenne inclut la contribution du bruit
et de la dynamique d'amplitude. La distance permise maximum est définie
CA 02836421 2013-11-14
- 8 -
comme la distance moyenne r multipliée par un coefficient de distance cdist.
Ce
coefficient peut être réglé à environ 1.5. Le traitement peut procéder sur la
base
de règles de comparaison et de regroupement comme suit:
- stocker les premières mesures /min comme nouvelles signatures;
- pour les mesures suivantes, trouver la distance mesure-aux-signatures la
plus proche;
- si la distance la plus proche est inférieure à la distance maximum
permise,
- alors fusionner la mesure à la signature la plus proche et réestimer la
distance moyenne r,
- sinon calculer les distances signature-à-signature et trouver la distance
signature-à-signature la plus proche;
- si la distance est inférieure à la distance maximum permise,
- alors fusionner les deux signatures les plus proches et réestimer la
distance moyenne r,
- sinon placer la mesure comme nouvelle signature ou, si imax est dépassé,
forcer la mesure à se fusionner avec la signature la plus proche;
- après la dernière mesure, l'intervalle d'alignement temporel est doublé,
pour
2 T-> T:
1. calculer les distances signature-à-signature;
2. trouver la distance signature-à-signature la plus proche;
3. si la distance la plus proche est inférieure à la distance maximum
permise:
4. alors fusionner les deux signatures les plus proches, calculer la distance
signatures-à-nouvelle signature, insérer le résultat dans la matrice
triangulaire de distances signature-à-signature, et retourner à l'étape 2;
5. sinon arrêter.
Le durcissement de sphère peut être utilisé pour raffiner les résultats: les
mesures distantes de la frontière de la sphère sont traitées à nouveau et
peuvent être réaffectés à un autre groupe. Le seuil peut être fixé
proportionnellement à Vof +var(0.;) où var(a) est l'incertitude de variance
sur
une estimation o-i.
CA 02836421 2013-11-14
- 9 -
Présumant rf-Yr, la distance moyenne F est estimée récursivement à partir de
la
distance minimum Dmi calculée durant la construction des groupes. Cette
distance moyenne
-2 I r
rk = ---[b=T-2 +D2 ' __ )) r2 = 0 (8)
inclut le bruit de la mesure et l'erreur de position de la signature. Le
facteur de
droite, une fonction de la population Pi, des groupes prend en compte la
variance de la position de la signature. Le coefficient b est un facteur de
pondération> 1.
Le processus de fusionnement Si L..) Si - Si' est
1
(Pis; +1s) (9)
Pi +Pj
pour le calcul de la nouvelle signature où P1 et pi sont les populations des
groupes. Avant la fusion, les signatures sont alignées temporellement par
rapport à la distance minimum. L'alignement temporel des signatures est aussi
pondéré par la population des groupes
7 p
S' -> S. q = int d = I
(10)
Sj,n+s ¨} Sj S = d -q
où d est la distance (Éq. 5) entre les signatures, exprimée en nombre
d'échantillons. L'ordre d'arrivée des mesures affecte légèrement le résultat
final,
mais à la fin
E X k =1. E {..,Xk,n¨dk ,...} = (11)
kegroupei i kegroupe i
Parmi les différentes métriques, le minimum de la distance au carré
\2\
r-,2 2
Si Si
(12)
CA 02836421 2013-11-14
- 10 -
calculé sur T alignements temporels testés peut donner de meilleurs résultats.
Notons que minimiser le terme de droite est comme maximiser la corrélation.
Maximiser seulement la corrélation peut s'avérer inefficace étant donné que
plusieurs petites formes de bruit corréleront avec certaines signatures de DP.
Avec cette métrique, la contribution de la variation d'amplitude de la DP est
réduite pour le deuxième terme.
Une corrélation (i.e. coefficient Bravais-Pearson) peut être utilisée dans le
deuxième regroupement effectué pour fusionner les groupes générés par les
différentes échelles de mesure. Dans cette deuxième étape, le RSB des
signatures de groupes est élevé et aucune erreur ne peut survenir entre une
signature de groupe DP et une signature de bruit.
La complexité de calcul est 0(N xTxMx I) pour la distance mesure-aux-
signatures et 0(1v xTxMx 1(1¨ 1)12) pour la matrice triangulaire de distances
signature-à-signature. Les coefficients Cdist, Imax et Imin établissent un
compromis
entre le temps de calcul et la probabilité d'un mauvais fusionnement. Pour de
nombreuses mesures, lorsque le nombre de groupes est stabilisé, le calcul des
distances signature-à-signature n'est plus requis: la complexité de calcul
générale tend vers 0(N xTxM xi).
Des mesures de précision peuvent inclure certaines informations sur la
dispersion des groupes et la superposition des groupes. Puisque la dernière
information est constante sur un ensemble de données, l'idée est d'optimiser
le
processus en utilisant une ou plusieurs estimations de la précision qui sont
représentatives des erreurs de regroupement. Des estimations proposées sont
basées sur deux approches opposées. D'une part, la puissance de résolution,
définie comme le rapport de la distance inter-groupes sur le rayon des
groupes,
relève de la superposition inter-groupes. D'autre part, la cohérence, le
rapport
de l'énergie cohérente sur l'énergie totale des groupes, relève du groupe lui-
même.
CA 02836421 2013-11-14
- 11 -
La puissance de résolution Re s est une mesure de la capacité de résolution
des groupes. La puissance de résolution
( --/
1 I Pi õ 112
Re s2 = 0..5 = IV - 1) , E E Isk -sir., . = E E lixi j -siv j (13)
i =2 k= 1 j i= 1 j=1
correspond à un rapport signal-bruit (RSB) où l'inter-distance quadratique
moyen (RMS) des groupes est le signal et le rayon quadratique moyen (RMS)
des groupes est le bruit. L'égalité 0.5./(1-1)-= .2Elk-/// explique le
dénominateur du premier terme et EP; --- M.
La cohérence
2 r 2
N
E X k E 1 X k,n¨dk
2 k E groupe i n=1 lcEgroupe i
yi = __________________________________________ (14)
E iixk ii
kEgroupe i [ N
E li E x2
)2 = :ke groupe i n=1 k,n¨d k j
du groupe "i" est calculée à partir des membres P1 de ce groupe. La cohérence
moyenne
Y2 =E/DiY/EPt (15)
est définie pour une séquence considérant tous les groupes qui y contribuent.
L'hypothèse suivante peut être utilisée: la puissance de résolution et la
cohérence moyenne sont à leurs niveaux maximums pour la meilleure solution
et diminuent avec les erreurs cumulatives dans le processus de regroupement.
La Figure 3 montre une signature typique de DP. Les résultats ont été obtenus
pour 1 730 séquences (118 932 mesures) prises dans un réseau de distribution
souterrain. Le premier front est le plus pointu et détermine la polarité de la
DP à
une valeur négative ici. La plage des valeurs de puissance de résolution, 1 à
10 000, appelle à une échelle logarithmique (dB). Le coefficient de distance
cest
doit être réglé à moins que la puissance de résolution. A la gauche de la
Figure
4, les 20 comptes à 0 dB pour cest=10 s'expliquent comme des erreurs de
regroupement car celle' puissance de résolution.
CA 02836421 2013-11-14
- 12 -
La cohérence des groupes est altérée principalement pour les séquences avec
une puissance de résolution petite. Dans la Figure 5, la plupart des séquences
ont une puissance de résolution grande: changer la valeur de Cdist à 10 a peu
d'effet sur la cohérence. Cependant, le même changement réduit
significativement la population des groupes pour certaines des séquences
(Figure 6). La Figure 6 illustre que le maximum de signatures permises /ma,
peut
être réglé à 30. La Figure 7 montre le temps de traitement diminuant avec
Cdist=
Le compromis entre le temps de traitement et la probabilité d'erreur de
regroupement est déterminé par les données elles-mêmes et la confiance
désirée aux fins de diagnostic. Sur la base de ces dernières Figures et
d'autres
résultats, régler cd,st=1.5 cible plus de 99% de la population de données et
donne un temps de traitement près du temps de mesure 8 s).
La contribution du regroupement des transitoires dans le domaine temporel est
observable dans les diagrammes de RPDP (résolution de phase de décharge
partielle) avec une discrimination des groupes. La Figure 8 fait ressortir un
groupe de 65 mesures parmi neuf autres groupes pour un total de 1 182
mesures.
Le regroupement de signaux transitoires dans le domaine temporel comme
première étape d'analyse, avec un traitement de signal additionnel sur les
signatures de groupes, est avantageux au moins de ces manières: (1)
l'information est réduite à quelques signatures plutôt que de nombreuses
mesures; (2) les rapports signal à bruit des signatures augmentent avec la
population des groupes; et (3) le temps post-traitement est réduit. De plus,
les
groupes superposés sont discriminés dans le diagramme de RPDP.
L'heuristique sous-optimale expliquée apparaît aussi rapide et précise. Des
tests utilisant de nombreuses données recueillies sur le terrain peuvent être
réalisés pour ajuster les paramètres et régler le choix des métriques dans la
méthode selon l'invention.
