Accueil🇫🇷Chercher

Algorithme de Savitzky-Golay

L'algorithme de Savitzky-Golay est une méthode utilisée en traitement du signal pour lisser une courbe et en extraire les dérivées successives. Il a été décrit en 1964 par Abraham Savitzky (en) et Marcel Golay[1].

Description de l'algorithme

Algorithme de Savitzky-Golay appliqué sur un signal gaussien bruité avec un polynôme de degré 3 et une largeur de 9 points. De haut en bas : le signal lissé, la dérivée et la dérivée seconde.
Lissage point par point (mêmes conditions que l'image précédente). L'arc de courbe rouge montre le résultat de la régression sur la fenêtre considérée ; les arcs de courbe en jaune montrent l'extrapolation du polynôme de régression. Les points obtenus pour le lissage sont représentés par des ronds.

Considérons une courbe y = ƒ(x), et présentant des « aspérités », des oscillations de faibles amplitudes ; on parle de signal bruité. Il s'agit d'une courbe discrète, c'est-à-dire définie par un nuage de points (x(i), y(i))1 ≤ i ≤ n.

L'algorithme de lissage le plus simple est la méthode des moyennes glissantes :

  • on considère une fenêtre, un intervalle, de « demi-largeur » â„“ (nombre de points) ;
  • on calcule la moyenne yâ„“ + 1 de la fonction sur l'intervalle [1 ; 2 × â„“ + 1] (l'intervalle a donc une largeur de 2â„“ + 1, â„“ n'est pas exactement la demi-largeur) ;
  • on définit un nouveau point (x(â„“ + 1), yliss(â„“ + 1)) avec yliss(â„“ + 1) = yâ„“ + 1 ;
  • on fait glisser l'intervalle d'un point et l'on recommence.

Cet algorithme est simple, mais « violent » : il atténue énormément les fortes variations, il écrête les pics.

Pour la suite, nous désignons l'intervalle i comme étant [i – ℓ ; i + ℓ ], l'intervalle de milieu i et de largeur 2ℓ + 1.

Une manière plus fine consiste à considérer un polynôme de degré d, avec d < 2ℓ + 1. Pour chaque intervalle i, on effectue une régression pour déterminer le polynôme Pi minimisant l'erreur au sens des moindres carrés. On définit la valeur lissée

Par ailleurs, si le polynôme est au moins de degré 1, on peut déterminer la dérivée

et de manière générale, on peut déterminer la d-ième dérivée.

On voit que la méthode des moyennes glissantes est un lissage de Savitzky-Golay avec un polynôme de degré 0.

Illustration du fonctionnement de l'algorithme de Savistky-Golay sur le lissage d'un signal bruité représentant des pics.
Illustration du fonctionnement de l'algorithme de Savistky-Golay sur le lissage d'un signal bruité représentant des pics.

Choix des paramètres

Dans la pratique :

  • un polynôme de degré 2 permet de prendre en compte la courbure ; un polynôme de degré 3 permet de prendre en compte des points d'inflexion ; il est rarement nécessaire d'aller au-delà ;
  • le nombre de points d'un intervalle doit être suffisamment grand devant le degré du polynôme pour que le lissage soit effectif ; s'ils sont égaux, le polynôme passe exactement par tous les points de l'intervalle, il n'y a donc pas de lissage.

On prend donc en général un polynôme de degré 3 et une fenêtre glissante d'au moins 5 points.

Plus la fenêtre est large, plus la courbe est lissée, mais plus on atténue les variations de petite longueur d'onde. La largeur limite est de l'ordre de la longueur d'onde des détails que l'on veut conserver. Si par exemple on s'intéresse à des pics — cas très fréquents en spectrométrie et en diffractométrie —, on prend en général pour largeur de fenêtre la largeur à mi-hauteur du pic le plus fin.

Cas d'un pas constant

Concrètement, les coefficients de la régression polynomiale sont calculés par une combinaison linéaire des points de l'intervalle glissant. La valeur lissée, et les valeurs des dérivées, sont donc elles-mêmes des combinaisons linéaires :

;
;
…

Si le pas h = xi – xi - 1 est constant[2], les coefficients bk, b'k, sont les mêmes partout ; on se retrouve dans le cas d'un filtre à réponse impulsionnelle finie (filtre RIF). On peut donc déterminer au départ les coefficients bk, b'k, …, ce qui fournit un algorithme rapide et facile à mettre en œuvre — par exemple avec un tableur ; on parle alors de coefficients de convolution.

Dans ces conditions, on trouve que :

  • le lissage est identique que l'on utilise un polynôme de degré 2 (quadratique) ou 3 (cubique) ;
  • la dérivation est identique que l'on utilise un polynôme de degré 3 (cubique) ou 4 (« quartique Â») ;
  • la dérivée seconde est identique que l'on utilise un polynôme de degré 4 (« quartique ») ou 5 (« quintique Â») ;
  • les coefficients sont symétriques ou anti-symétriques, selon l'ordre de dérivation :
bk = b2ℓ – k ; b'k = –b'2ℓ – k ; …
  • on a toujours b'l = 0 : le point xi ne contribue pas au calcul de y'liss i.

Les valeurs des coefficients sont tabulées pour des tailles de fenêtre (intervalle glissant) données. Par exemple, pour une fenêtre de 5 points et un polynôme de degré 3 :

;
;
.

Les tableaux ci-dessous donnent les coefficients de convolution pour des degrés de polynôme et des largeurs de fenêtre données.

Coefficients de convolution pour le lissage
Degré 2/3 (quadratique/cubique) 4/5 (quartique/quintique)
Largeur 579 79
–4 –2115
–3 –2145–55
–2 –3339–3030
–1 1265475135
0 17759131179
1 1265475135
2 –3339–3030
3 –2145–55
4 –2115
Normalisation 3521231231429
Coefficients de convolution pour la dérivée
Degré 2 (quadratique) 3/4 (cubique/quartique)
Largeur 579 579
–4 –486
–3 –3–322–142
–2 –2–2–21–67–193
–1 –1–1–1–8–58–126
0 000000
1 111858126
2 222–167193
3 33–22142
4 4–86
Normalisation 10h28h60h12h252h1 188h

Remarque : la normalisation utilise le pas d'échantillonnage h.

Coefficients de convolution pour la dérivée seconde
Degré 2/3 (quadratique/cubique) 4/5 (quartique/quintique)
Largeur 579 579
–4 28−4 158
–3 57–11712 243
–2 20–8–36034 983
–1 –1–3–1748–171−6 963
0 –2–4–20–90–630−12 210
1 –1–3–1748–171−6 963
2 20–8–36034 983
3 57–11712 243
4 28−4 158
Normalisation 7h242h2462h236h21 188h256 628h2

Calcul des coefficients de convolution

On se place en un point k donné. Les coordonnées du point expérimental sont (xk, yk).

Pour déterminer les coefficients de corrélation, on effectue un changement de variable afin d'avoir une abscisse centrée réduite — c'est-à-dire que l'intervalle sur lequel on effectue la régression devient [–ℓ ; ℓ ] : on pose

où

  • x est la moyenne des valeurs de x sur l'intervalle [xk – â„“ ; xk + ℓ ] considéré, c'est le centre de la fenêtre ;
  • h est le pas d'échantillonnage (distance entre deux points voisins).

L'abscisse z prend les valeurs (–ℓ ; –ℓ + 1 ; … ; –1 ; 0 ; 1 ; … ℓ ). Par exemple, pour une fenêtre glissante de 5 points, on a (zi)1 ≤ i ≤ 5 = (–2 ; –1 ; 0 ; 1 ; 2).

Le polynôme de degré d s'exprime alors sous la forme :

Considérons la fonction vectorielle

avec

Sa matrice jacobienne s'écrit

La solution des équations normales

est donc

La valeur de la courbe lissée est la valeur du polynôme au centre de l'intervalle :

;

Pour les dérivées successives :

;
.

Par exemple, pour un polynôme de degré d = 3 et une fenêtre de 5 points, donc ℓ = 2 :

.

On a donc :

;
;
.

Notes et références

  1. Abraham Savitzky et Marcel J. E. Golay, « Smoothing and Differentiation of Data by Simplified Least Squares Procedures », Analytical Chemistry, vol. 8, no 36,‎ , p. 1627–1639 (DOI 10.1021/ac60214a047)
  2. on n'a pas toujours un pas constant, on peut avoir un pas variable
    • pour des raisons d'optimisation : on veut mesurer plus finement une zone et plus grossièrement une autre (pour gagner du temps) ;
    • pour des raisons matérielles :
      • le système générant la valeur d'entrée x n'a pas une réponse linéaire,
      • pour des mesures très précises, la boucle de régulation peut prendre beaucoup de temps pour stabiliser la valeur d'entrée à la valeur de consigne xth, on peut alors gagner du temps en mesurant un point alors que la consigne n'est pas totalement atteinte, la valeur de x étant relevée de manière très précise.
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.