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.

 

 

 

C#

public class OneEuroFilter
{
    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;
    }
}

 

F#

type LowpassFilter() =
    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)

https://skydrive.live.com/embed?cid=7BD91AE7F5096B79&resid=7BD91AE7F5096B79%21207&authkey=AKqZ6OuAtDXOFE8