Lissage: OneEuroFilter, implémentation en C# et F#
Dès lors que vous développez avec des capteurs, il se peut que le signal renvoyé ne soit pas stable ou bruité et que vous ayez à le lisser afin d’en faciliter l’exploitation. Kinect par exemple est basé sur des caméras et c’est une source qui vibre par nature. A contrario, une souris renvoie un signal stable (aucune perturbation si vous n’y touchez pas par exemple).
Si comme pour moi, le traitement du signal est plutôt un souvenir d’école, voici quelques rappels.
Tout bon informaticien ayant à lisser une série de données utilise le plus souvent le calcul d’une moyenne mobile. Pour faire simple, vous allez remplacer chaque valeur de la série par la moyenne des valeurs qui l’entourent. Ce système fonctionne mais a plusieurs défauts:
– le filtrage exploite la liste des “n” dernières valeurs sur lesquelles il faut itérer et que vous devez maintenir.
– ce système génère de la latence. La courbe sera certes lissée mais les données proches du signal d’origine arriveront plus tard dans le temps.
– la moyenne de la série est conservée mais l’écart type est diminué.
http://fr.wikipedia.org/wiki/Moyenne_mobile
D’autres filtres plus complexes offrent un paramétrage plus riche qui vous permet de mieux adapter leur comportement suivant la nature de vos données.
Parmi eux, les filtres exponentiels sont simples et couramment utilisés.
http://en.wikipedia.org/wiki/Exponential_smoothing
Dans un filtre à moyenne mobile, les valeurs les plus éloignées de l’historique “valent” autant que la dernière valeur enregistrée. Les filtres à exponentiel font décroitre de manière exponentielle le poids des valeurs selon leur éloignement dans le temps. Ces filtres lissent les données mais offrent également un comportement prédictif.
Il existe beaucoup de systèmes de filtrage plus ou moins complexes à mettre en oeuvre et offrant plus ou moins de paramètres d’entrée.
Une équipe de chercheurs de l’INRIA de Lille avec qui nous avons l’occasion d’échanger dans le domaine des intéractions vient de publier un nouveau type de filtre que nous avons utilisé au sein des projets de Sensorit, notamment avec Kinect.
L’avantage de ce filtre est principalement sa simplicité d’utilisation avec deux paramètres d’entrée permettant de lisser puis de contrer la latence.
Tous les détails ici: CHI 2012 paper (PDF)
ainsi qu’une vidéo:
et une page exposant l’algorithme et des implémentations dans différents langages: http://www.lifl.fr/~casiez/1euro/
Ci-dessous, une démonstration illustrant l’usage de ce filtre sur une série de données fictive.
Vous trouverez une version de l’algorithme en C# et en F# ainsi qu’un fichier zip avec l’ensemble de la solution.
{
public OneEuroFilter(double minCutoff, double beta)
{
firstTime = true;
this.minCutoff = minCutoff;
this.beta = beta;
xFilt = new LowpassFilter();
dxFilt = new LowpassFilter();
dcutoff = 1;
}
protected bool firstTime;
protected double minCutoff;
protected double beta;
protected LowpassFilter xFilt;
protected LowpassFilter dxFilt;
protected double dcutoff;
public double MinCutoff
{
get { return minCutoff; }
set { minCutoff = value; }
}
public double Beta
{
get { return beta; }
set { beta = value; }
}
public double Filter(double x, double rate)
{
double dx = firstTime ? 0 : (x – xFilt.Last()) * rate;
if (firstTime)
{
firstTime = false;
}
var edx = dxFilt.Filter(dx, Alpha(rate, dcutoff));
var cutoff = minCutoff + beta * Math.Abs(edx);
return xFilt.Filter(x, Alpha(rate, cutoff));
}
protected double Alpha(double rate, double cutoff)
{
var tau = 1.0 / (2 * Math.PI * cutoff);
var te = 1.0 / rate;
return 1.0 / (1.0 + tau / te);
}
}
public class LowpassFilter
{
public LowpassFilter()
{
firstTime = true;
}
protected bool firstTime;
protected double hatXPrev;
public double Last()
{
return hatXPrev;
}
public double Filter(double x, double alpha)
{
double hatX = 0;
if (firstTime)
{
firstTime = false;
hatX = x;
}
else
hatX = alpha * x + (1 – alpha) * hatXPrev;
hatXPrev = hatX;
return hatX;
}
}
let mutable firstTime = true
let mutable hatXPrev = 0.0
member v.Last() = hatXPrev
member v.Filter(x:float, alpha:float) =
let mutable hatX = 0
let hatX =
if firstTime then
firstTime <- false
x
else
alpha * x + (1.0 – alpha) * hatXPrev
hatXPrev <- hatX
hatX
type OneEuroFilter(minCutoff:float, beta:float) =
let mutable firstTime = true
let xFilt = new LowpassFilter()
let dxFilt = new LowpassFilter()
let mutable dcutoff = 1.0
let mutable _minCutoff = minCutoff
let mutable _beta = beta
member v.MinCutoff
with get () = _minCutoff
and set (value) = _minCutoff <- value
member v.Beta
with get () = _beta
and set (value) = _beta <- value
member v.Filter(x:float, rate:float) =
let Alpha rate cutoff =
let tau = 1.0 / (2.0 * Math.PI * cutoff)
let te = 1.0 / rate
1.0 / (1.0 + tau / te)
let dx = if firstTime then 0.0 else (x – xFilt.Last()) * rate
if firstTime then firstTime <- false
let edx = dxFilt.Filter(dx, Alpha rate dcutoff)
let cutoff = minCutoff + beta * Math.Abs(edx)
xFilt.Filter(x, Alpha rate cutoff)