Vous ne l’avez certainement pas manqué en tant que lecteur assidu de ce blog : Le Kinect pour Windows SDK beta est disponible!

Pour le moment toutefois il n’y a pas de services de reconnaissance de gestes (gestures). Nous allons donc essayer tout au long de cet article de créer notre propre librairie qui se chargera de détecter des mouvements simples tels que le swipe (c’est à dire le déplacement latéral de gauche à droite ou de droite à gauche) mais également des mouvements plus complexes comme le tracé d’un cercle avec la main.

Cette détection de gestures nous permettra par exemple de piloter Powerpoint à la mode Jedi (comme dans la démonstration Kinect Keyboard Simulator).

Si vous n’êtes pas familier avec le Kinect pour Windows SDK, je vous invite à lire ce premier article qui débroussaille le sujet: http://blogs.msdn.com/b/eternalcoding/archive/2011/06/14/fr-prenez-le-contr-244-le-avec-kinect-pour-windows-sdk.aspx

Comment détecter des gestures ?

Il existe une infinité de solutions pour détecter une gesture. Nous allons dans cet article en retenir deux:

La recherche algorithmique
La recherche à base de templates

Il faut noter également que ces deux techniques disposent d’un grand nombre de variantes et de raffinements. Le but ici est de donner des pistes et une proposition de solutions qui fonctionnent.

Vous pourrez d’ailleurs trouver le code de cet article juste ici : http://kinecttoolbox.codeplex.com/

Dans tous les cas, il s’agira d’enregistrer les différentes positions dans le temps d’un joint d’un squelette pour les analyser par la suite. Les techniques se différencieront dans leur manière de traiter ces positions.

La classe GestureDetector

Pour uniformiser l’usage de notre système de gestures, nous allons donc proposer une classe abstraite GestureDetector dont hériteront toutes les implémentations de nos techniques de recherches:

Cette classe fournit la méthode Add pour enregistrer les différentes positions du joint du squelette que nous suivons.

Elle fournit également la méthode abstraite LookForGesture qui sera à la charge de ses filles.

Elle stocke dans la propriété Entries une liste d’Entry dont le rôle est de sauvegarder les coordonnées et le timing de chaque position enregistrée.

Dessin des positions enregistrées

La classe Entry stocke également une ellipse WPF qui sera utilisée pour dessiner la position enregistrée:

Via la méthode TraceTo de la classe GestureDetector, nous allons indiquer sur quel canvas WPF l’utilisateur veut dessiner les positions stockées.

Au final, l’ensemble du travail est fait dans la méthode Add qui se compose ainsi :

public virtual void Add(Vector position, SkeletonEngine engine)
{
    Entry newEntry = new Entry {Position = position.ToVector3(), Time = DateTime.Now};
    Entries.Add(newEntry);
 
    if (displayCanvas != null)
    {
        newEntry.DisplayEllipse = new Ellipse
        {
            Width = 4,
            Height = 4,
            HorizontalAlignment = HorizontalAlignment.Left,
            VerticalAlignment = VerticalAlignment.Top,
            StrokeThickness = 2.0,
            Stroke = new SolidColorBrush(displayColor),
            StrokeLineJoin = PenLineJoin.Round
        };
 
 
        float x, y;
 
        engine.SkeletonToDepthImage(position, out x, out y);
 
        x = (float)(x * displayCanvas.ActualWidth);
        y = (float)(y * displayCanvas.ActualHeight);
 
        Canvas.SetLeft(newEntry.DisplayEllipse, x – newEntry.DisplayEllipse.Width / 2);
        Canvas.SetTop(newEntry.DisplayEllipse, y – newEntry.DisplayEllipse.Height / 2);
 
        displayCanvas.Children.Add(newEntry.DisplayEllipse);
    }
 
    if (Entries.Count > WindowSize)
    {
        Entry entryToRemove = Entries[0];
        
        if (displayCanvas != null)
        {
            displayCanvas.Children.Remove(entryToRemove.DisplayEllipse);
        }
 
        Entries.Remove(entryToRemove);
    }
 
    LookForGesture();
}

Notez l’utilisation de la méthode SkeletonToDepthImage qui sait convertir une coordonnée 3D (celle d’un joint) vers une coordonnées 2D entre 0 et 1 sur chaque axe.

Ainsi en plus de sauvegarder les informations de positions des joints, la classe GestureDetector permet de dessiner ces dernières pour donner un retour visuel qui facilite grandement la mise en place de nos techniques de recherches:

Comme nous le voyons ci-dessus, les positions en cours d’analyses apparaissent en rouge par-dessus l’image de Kinect. Pour activer ce service, le développeur doit juste mettre un canvas au dessus de l’image qui affiche le retour de la caméra Kinect et donner ce canvas à la méthode GestureDetector.TraceTo:

<Viewbox Margin="5" Grid.RowSpan="5">
    <Grid Width="640" Height="480" ClipToBounds="True">
        <Image x:Name="kinectDisplay"></Image>
        <Canvas x:Name="kinectCanvas"></Canvas>
        <Canvas x:Name="gesturesCanvas"></Canvas>
        <Rectangle Stroke="Black" StrokeThickness="1"/>
    </Grid>
</Viewbox>

La Viewbox permet ici de garder tout ce petit monde aligné tout en autorisant de retailler l’ensemble en fonction de l’interface.

Le second canvas permet quand à lui de dessiner le squelette (grâce à une autre classe du sample : SkeletonDisplayManager)

Approche événementielle

La classe GestureDetector fournit un dernier service à ses filles via la méthode RaiseGestureDetected qui permet de signaler la détection d’une nouvelle gesture (au travers d’un évènement OnGestureDetected). L’énumération SupportedGesture contient ainsi les valeurs suivantes:

SwipeToLeft
SwipeToRight
Circle

Bien évidemment la solution est enrichissable sans problème et je vous encourage même à rajouter de nouvelles gestures au système.

La méthode RaiseGestureDetected permet également via la propriété MinimalPeriodBetweenGestures de garantir un certain délai entre deux signalement de gestures pour éviter les faux positifs (comme par exemple un SwipeToLeft juste après un SwipeToRight correspondant en fait au retour naturel du bras).

Maintenant que nos bases sont posées, nous allons pouvoir nous attaquer aux classes filles qui vont donc fournir la détection proprement dite.

Recherche algorithmique

La recherche algorithmique consiste à parcourir la liste des positions en vérifiant que les contraintes prédéfinies sont constamment valides.

C’est la classe SwipeGestureDetector qui se charge de cette recherche:

Pour la gesture SwipeToRight, elle se base sur les contraintes suivantes:

Chaque nouvelle position doit être à la droite de la précédente
Chaque position ne doit pas dépasser en hauteur la première d’une certaine distance (20 cm)
Le temps passé entre la première et la dernière position de la gesture doit être entre 250ms et 1500ms
La gesture doit au moins faire 40cm de long (de la première à la dernière gesture donc)

La gesture SwipeToLeft se base sur les même contraintes sauf pour le sens de progression évidemment.

Pour gérer ces deux gestures efficacement, nous allons donc partir sur un algorithme générique qui se chargera de vérifier les quatre contraintes citées précédemment:

bool ScanPositions(Func<Vector3, Vector3, bool> heightFunction, Func<Vector3, Vector3, bool> directionFunction, Func<Vector3, Vector3, bool> lengthFunction, int minTime, int maxTime)
{
    int start = 0;
 
    for (int index = 1; index < Entries.Count – 1; index++)
    {
        if (!heightFunction(Entries[0].Position, Entries[index].Position) || !directionFunction(Entries[index].Position, Entries[index + 1].Position))
        {
            start = index;
        }
 
        if (lengthFunction(Entries[index].Position, Entries[start].Position))
        {
            double totalMilliseconds = (Entries[index].Time – Entries[start].Time).TotalMilliseconds;
            if (totalMilliseconds >= minTime && totalMilliseconds <= maxTime)
            {
                return true;
            }
        }
    }
 
    return false;
}

Pour se servir de cette méthode, il faut donc fournir 3 fonctions et une période à vérifier.

Donc pour gérer nos deux gestures, il suffit d’appeler le code suivant:

protected override void LookForGesture()
{
    // Swipe to right
    if (ScanPositions((p1, p2) => Math.Abs(p2.Y – p1.Y) < SwipeMaximalHeight, // Height
        (p1, p2) => p2.X – p1.X > -0.01f, // Progression to right
        (p1, p2) => Math.Abs(p2.X – p1.X) > SwipeMinimalLength, // Length
        SwipeMininalDuration, SwipeMaximalDuration)) // Duration
    {
        RaiseGestureDetected(SupportedGesture.SwipeToRight);
        return;
    }
 
    // Swipe to left
    if (ScanPositions((p1, p2) => Math.Abs(p2.Y – p1.Y) < SwipeMaximalHeight,  // Height
        (p1, p2) => p2.X – p1.X < 0.01f, // Progression to right
        (p1, p2) => Math.Abs(p2.X – p1.X) > SwipeMinimalLength, // Length
        SwipeMininalDuration, SwipeMaximalDuration))// Duration
    {
        RaiseGestureDetected(SupportedGesture.SwipeToLeft);
        return;
    }
}

Grâce à cette classe il est donc possible de rajouter des gestures simplement détectables via des contraintes.

Stabilité de la position du squelette

Pour bien garantir le fonctionnement de notre détection, nous devons valider que le squelette est effectivement statique pour ne pas générer de faux positifs (par exemple la détection d’un swipe lié au déplacement du corps entier et non pas juste à celui de la main).

Pour effectuer cette vérification, nous allons recourir à la classe BarycenterHelper :

public class BarycenterHelper
{
    readonly Dictionary<int, List<Vector3>> positions = new Dictionary<int, List<Vector3>>();
    readonly int windowSize;
 
    public float Threshold { get; set; }
 
    public BarycenterHelper(int windowSize = 20, float threshold = 0.05f)
    {
        this.windowSize = windowSize;
        Threshold = threshold;
    }
 
    public bool IsStable(int trackingID)
    {
        List<Vector3> currentPositions = positions[trackingID];
        if (currentPositions.Count != windowSize)
            return false;
 
        Vector3 current = currentPositions[currentPositions.Count – 1];
 
        for (int index = 0; index < currentPositions.Count – 2; index++)
        {
            Debug.WriteLine((currentPositions[index] – current).Length());
 
            if ((currentPositions[index] – current).Length() > Threshold)
                return false;
        }
 
        return true;
    }
 
    public void Add(Vector3 position, int trackingID)
    {
  ��     if (!positions.ContainsKey(trackingID))
            positions.Add(trackingID, new List<Vector3>());
 
        positions[trackingID].Add(position);
 
        if (positions[trackingID].Count > windowSize)
            positions[trackingID].RemoveAt(0);
    }
}

En fournissant à cette classe les positions successives du squelette, elle nous indiquera via la méthode IsStable si le squelette est en mouvement ou statique.

Ainsi, nous pouvons nous servir de cette information pour n’envoyer les positions des joints aux systèmes de détection que lorsque le squelette n’est pas en mouvement:

void ProcessFrame(ReplaySkeletonFrame frame)
{
    Dictionary<int, string> stabilities = new Dictionary<int, string>();
    foreach (var skeleton in frame.Skeletons)
    {
        if (skeleton.TrackingState != SkeletonTrackingState.Tracked)
            continue;
 
        barycenterHelper.Add(skeleton.Position.ToVector3(), skeleton.TrackingID);
 
        stabilities.Add(skeleton.TrackingID, barycenterHelper.IsStable(skeleton.TrackingID) ? "Stable" : "Unstable");
        if (!barycenterHelper.IsStable(skeleton.TrackingID))
            continue;
 
        foreach (Joint joint in skeleton.Joints)
        {
            if (joint.Position.W < 0.8f || joint.TrackingState != JointTrackingState.Tracked)
                continue;
 
            if (joint.ID == JointID.HandRight)
            {
                swipeGestureRecognizer.Add(joint.Position, kinectRuntime.SkeletonEngine);
                circleGestureRecognizer.Add(joint.Position, kinectRuntime.SkeletonEngine);
            }
        }
 
        postureRecognizer.TrackPostures(skeleton);
    }
 
    skeletonDisplayManager.Draw(frame);
 
    stabilitiesList.ItemsSource = stabilities;
 
    currentPosture.Text = "Current posture: " + postureRecognizer.CurrentPosture.ToString();
}

Outil d’enregistrements et de replay

Un autre point important lorsque l’on développe avec le Kinect pour Windows SDK, c’est la possibilité de tester. Cela peut paraitre idiot mais pour tester il faut se lever, venir devant le capteur et effectuer la gestuelle adéquate. Et à moins d’avoir un assistant, cela peut vite devenir pénible.

Nous allons donc nous doter d’un service d’enregistrements et de replay des informations des squelettes envoyés par Kinect.

Enregistrement

La partie enregistrement est assez simple en ce sens qu’il suffit de prendre une SkeletonFrame et de parcourir chaque squelette pour sérialiser son contenu:

public void Record(SkeletonFrame frame)
{
    if (writer == null)
        throw new Exception("You must call Start before calling Record");
 
    TimeSpan timeSpan = DateTime.Now.Subtract(referenceTime);
    referenceTime = DateTime.Now;
    writer.Write((long)timeSpan.TotalMilliseconds);
    writer.Write(frame.FloorClipPlane);
    writer.Write((int)frame.Quality);
    writer.Write(frame.NormalToGravity);
 
    writer.Write(frame.Skeletons.Length);
 
    foreach (SkeletonData skeleton in frame.Skeletons)
    {
        writer.Write((int)skeleton.TrackingState);
        writer.Write(skeleton.Position);
        writer.Write(skeleton.TrackingID);
        writer.Write(skeleton.EnrollmentIndex);
        writer.Write(skeleton.UserIndex);
        writer.Write((int)skeleton.Quality);
 
        writer.Write(skeleton.Joints.Count);
        foreach (Joint joint in skeleton.Joints)
        {
            writer.Write((int)joint.ID);
            writer.Write((int)joint.TrackingState);
            writer.Write(joint.Position);
        }
    }
}

Replay

La problématique au niveau du replay se situe au niveau de la reconstruction. En effet, les classes de Kinect sont scellées et n’exposent pas leur constructeur. Pour contourner ce problème, nous allons reproduire la hiérarchie de classe en rajoutant des opérateurs de cast implicites vers les classes de Kinect:

Grâce à ces opérateurs de cast, nos méthodes vont travailler avec les classes de replay tout en acceptant également les classes de bases de Kinect (qui seront alors automatiquement converties).

La classe en charge du replay est la classe SkeletonReplay dont la méthode Start permet de lancer l’exécution:

public void Start()
{
    context = SynchronizationContext.Current;
 
    CancellationToken token = cancellationTokenSource.Token;
 
    Task.Factory.StartNew(() =>
    {
        foreach (ReplaySkeletonFrame frame in frames)
        {
            Thread.Sleep(TimeSpan.FromMilliseconds(frame.TimeStamp));
 
            if (token.IsCancellationRequested)
                return;
                                      
            ReplaySkeletonFrame closure = frame;
            context.Send(state =>
                            {
                                if (SkeletonFrameReady != null)
                                    SkeletonFrameReady(this, new ReplaySkeletonFrameReadyEventArgs {SkeletonFrame = closure});
                            }, null);
        }
    }, token);
}

Au final, nous pouvons donc enregistrer des gestuelles et les rejouer à l’infini pour débugger ou développer notre application:

Vous pouvez télécharger ici un exemple de fichier de replay: http://www.catuhe.com/msdn/davca.replay.zip

Savoir quand commencer

Le dernier problème qu’il nous reste à résoudre est de savoir quand commencer l’analyse des gestures. Nous savons déjà que nous ne devons le faire que quand le corps est stable mais cela n’est pas suffisant.

En effet, même si je reste statique, lorsque je parle en tant que bon latin, je m’exprime beaucoup avec les mains et je peux déclencher des gestures malencontreusement.

Pour nous protéger de cela, il est possible de compléter la détection en ajoutant une condition sur une posture. Ainsi, nous pourrions définir que l’on passe au slide suivant dans Powerpoint si l’on détecte SwipeToRight ET que la main gauche fait “Hello”.

C’est donc ici que nous allons faire appel à la classe PostureDetector qui va fournir les algorithmes adéquats:

public class PostureDetector
{
    const float Epsilon = 0.1f;
    const float MaxRange = 0.25f;
    const int AccumulatorTarget = 10;
 
    Posture previousPosture = Posture.None;
    public event Action<Posture> PostureDetected;
    int accumulator;
    Posture accumulatedPosture = Posture.None;
 
    public Posture CurrentPosture
    {
        get { return previousPosture; }
    }
 
    public void TrackPostures(ReplaySkeletonData skeleton)
    {
        if (skeleton.TrackingState != SkeletonTrackingState.Tracked)
            return;
 
        Vector3? headPosition = null;
        Vector3? leftHandPosition = null;
        Vector3? rightHandPosition = null;
 
        foreach (Joint joint in skeleton.Joints)
        {
            if (joint.Position.W < 0.8f || joint.TrackingState != JointTrackingState.Tracked)
                continue;
 
            switch (joint.ID)
            {
                case JointID.Head:
                    headPosition = joint.Position.ToVector3();
                    break;
                case JointID.HandLeft:
                    leftHandPosition = joint.Position.ToVector3();
                    break;
                case JointID.HandRight:
                    rightHandPosition = joint.Position.ToVector3();
                    break;
            }
        }
 
        // HandsJoined
        if (CheckHandsJoined(rightHandPosition, leftHandPosition))
            return;
 
        // LeftHandOverHead
        if (CheckHandOverHead(headPosition, leftHandPosition))
        {
            RaisePostureDetected(Posture.LeftHandOverHead);
            return;
        }
 
        // RightHandOverHead
        if (CheckHandOverHead(headPosition, rightHandPosition))
        {
            RaisePostureDetected(Posture.RightHandOverHead);
            return;
        }
 
        // LeftHello
        if (CheckHello(headPosition, leftHandPosition))
        {
            RaisePostureDetected(Posture.LeftHello);
            return;
        }
 
        // RightHello
        if (CheckHello(headPosition, rightHandPosition))
        {
            RaisePostureDetected(Posture.RightHello);
            return;
        }
 
        previousPosture = Posture.None;
        accumulator = 0;
    }
 
    bool CheckHandOverHead(Vector3? headPosition, Vector3? handPosition)
    {
        if (!handPosition.HasValue || !headPosition.HasValue)
            return false;
 
        if (handPosition.Value.Y < headPosition.Value.Y)
            return false;
 
        if (Math.Abs(handPosition.Value.X – headPosition.Value.X) > MaxRange)
            return false;
 
        if (Math.Abs(handPosition.Value.Z – headPosition.Value.Z) > MaxRange)
            return false;
 
        return true;
    }
 
 
    bool CheckHello(Vector3? headPosition, Vector3? handPosition)
    {
        if (!handPosition.HasValue || !headPosition.HasValue)
            return false;
 
        if (Math.Abs(handPosition.Value.X – headPosition.Value.X) < MaxRange)
            return false;
 
        if (Math.Abs(handPosition.Value.Y – headPosition.Value.Y) > MaxRange)
            return false;
 
        if (Math.Abs(handPosition.Value.Z – headPosition.Value.Z) > MaxRange)
            return false;
 
        return true;
    }
 
    bool CheckHandsJoined(Vector3? leftHandPosition, Vector3? rightHandPosition)
    {
        if (!leftHandPosition.HasValue || !rightHandPosition.HasValue)
            return false;
 
        float distance = (leftHandPosition.Value – rightHandPosition.Value).Length();
 
        if (distance > Epsilon)
            return false;
 
        RaisePostureDetected(Posture.HandsJoined);
        return true;
    }
 
    void RaisePostureDetected(Posture posture)
    {
        if (accumulator < AccumulatorTarget)
        {
            if (accumulatedPosture != posture)
            {
                accumulator = 0;
                accumulatedPosture = posture;
            }
            accumulator++;
            return;
        }
 
        if (previousPosture == posture)
            return;
 
        previousPosture = posture;
        if (PostureDetected != null)
            PostureDetected(posture);
 
        accumulator = 0;
    }
}

Le fonctionnement de la classe PostureDetector s’appuie sur l’analyse comparée des positions des éléments qui nous intéressent. Par exemple pour la posture Hello, nous cherchons à savoir si la main est à la même hauteur que la tête et si elle est au moins à 25cm sur le coté.

De plus, la détection d’une posture s’appuie sur un accumulateur qui permet de ne lever l’événément de détection que lorsque la posture est stable (sur un certain nombre d’images).

Encore une fois cette classe est largement extensible.

Recherche à base de templates

Le principal défaut de l’approche à base d’algorithmes est que toutes les gestures ne sont pas facilement descriptibles avec des contraintes. Nous allons donc nous pencher sur une autre approche plus générale.

Nous allons partir du principe qu’une gesture peut être enregistrée et que par la suite, le système se chargera de savoir si la gesture courante correspond à celle qui est déjà connue : on parle ici de système de recherches à base de templates (modèles).

Notre objectif va donc être finalement de savoir comparer deux gestures.

Comparer le comparable

Avant de nous lancer dans un algorithme de comparaison, nous allons nous faciliter la tâche en “uniformisant” nos données.

En effet, une gesture est une suite de points (pour cet article nous allons nous contenter de comparer des gestures 2D comme le cercle). Toutefois les coordonnées de ces points sont des distances vers le capteur et il va nous falloir les rassembler vers un repère commun. Pour ce faire nous allons effectuer les opérations suivantes;

Ramener les gestures à un nombre défini de points en calculant la distance moyenne entre chaque point
Amener le point 0 sur l’angle 0 via une rotation
Amener les points dans un repère de 1×1 via un zoom d’un ratio (1/largeur, 1/hauteur)
Centrer la gesture sur l’origine (0,0) via une translation

Ce qui nous donne le schéma suivant:

Grâce à ces transformations, nous allons pouvoir comparer des tableaux de points de même taille centrés sur un repère commun avec une orientation commune.

Le code qui permet d’effectuer tout cela se situe dans la classe GoldenSection :

public static List<Vector2> Pack(List<Vector2> positions, int samplesCount)
{
    List<Vector2> locals = ProjectListToDefinedCount(positions, samplesCount);
 
    float angle = GetAngleBetween(locals.Center(), positions[0]);
    locals = locals.Rotate(-angle);
 
    locals.ScaleToReferenceWorld();
    locals.CenterToOrigin();
 
    return locals;
}

Les différentes méthodes et méthodes d’extension utilisées sont présentes dans la classe statique GoldenSectionExtensions :

public static class GoldenSectionExtensions
{
    // Get length of path
    public static float Length(this List<Vector2> points)
    {
        float length = 0;
 
        for (int i = 1; i < points.Count; i++)
        {
            length += (points[i – 1] – points[i]).Length();
        }
 
        return length;
    }
 
    // Get center of path
    public static Vector2 Center(this List<Vector2> points)
    {
        Vector2 result = points.Aggregate(Vector2.Zero, (current, point) => current + point);
 
        result /= points.Count;
 
        return result;
    }
 
    // Rotate path by given angle
    public static List<Vector2> Rotate(this List<Vector2> positions, float angle)
    {
        List<Vector2> result = new List<Vector2>(positions.Count);
        Vector2 c = positions.Center();
 
        float cos = (float)Math.Cos(angle);
        float sin = (float)Math.Sin(angle);
 
        foreach (Vector2 p in positions)
        {
            float dx = p.X – c.X;
            float dy = p.Y – c.Y;
 
            Vector2 rotatePoint = Vector2.Zero;
            rotatePoint.X = dx * cos – dy * sin + c.X;
            rotatePoint.Y = dx * sin + dy * cos + c.Y;
 
            result.Add(rotatePoint);
        }
        return result;
    }
 
    // Average distance betweens paths
    public static float DistanceTo(this List<Vector2> path1, List<Vector2> path2)
    {
        return path1.Select((t, i) => (t – path2[i]).Length()).Average();
    }
 
    // Compute bounding rectangle
    public static Rectangle BoundingRectangle(this List<Vector2> points)
    {
        float minX = points.Min(p => p.X);
        float maxX = points.Max(p => p.X);
        float minY = points.Min(p => p.Y);
        float maxY = points.Max(p => p.Y);
 
        return new Rectangle(minX, minY, maxX – minX, maxY – minY);
    }
 
    // Check bounding rectangle size
    public static bool IsLargeEnough(this List<Vector2> positions, float minSize)
    {
        Rectangle boundingRectangle = positions.BoundingRectangle();
 
        return boundingRectangle.Width > minSize && boundingRectangle.Height > minSize;
    }
 
    // Scale path to 1×1
    public static void ScaleToReferenceWorld(this List<Vector2> positions)
    {
        Rectangle boundingRectangle = positions.BoundingRectangle();
        for (int i = 0; i < positions.Count; i++)
        {
            Vector2 position = positions[i];
 
            position.X *= (1.0f / boundingRectangle.Width);
            position.Y *= (1.0f / boundingRectangle.Height);
 
            positions[i] = position;
        }
    }
 
    // Translate path to origin (0, 0)
    public static void CenterToOrigin(this List<Vector2> positions)
    {
        Vector2 center = positions.Center();
        for (int i = 0; i < positions.Count; i++)
        {
            positions[i] -= center;
        }
    }
}

Golden Section

La comparaison entre nos données pourraient se faire via une simple fonction de distance moyenne entre chaque point. Toutefois, cette solution n’est pas assez précise et laisse passer de nombreux cas.

J’ai donc utilisé un algorithme beaucoup plus puissant appelé Golden Section Search. Il est issu d’un papier disponible ici: http://www.math.uic.edu/~jan/mcs471/Lec9/gss.pdf

Une implémentation Javascript est disponible ici : http://depts.washington.edu/aimgroup/proj/dollar/

La mise en œuvre en C# donne :

public static float Search(List<Vector2> current, List<Vector2> target, float a, float b, float epsilon)
{
    float x1 = ReductionFactor * a + (1 – ReductionFactor) * b;
    List<Vector2> rotatedList = current.Rotate(x1);
    float fx1 = rotatedList.DistanceTo(target);
 
    float x2 = (1 – ReductionFactor) * a + ReductionFactor * b;
    rotatedList = current.Rotate(x2);
    float fx2 = rotatedList.DistanceTo(target);
 
    do
    {
        if (fx1 < fx2)
        {
            b = x2;
            x2 = x1;
            fx2 = fx1;
            x1 = ReductionFactor * a + (1 – ReductionFactor) * b;
            rotatedList = current.Rotate(x1);
            fx1 = rotatedList.DistanceTo(target);
        }
        else
        {
            a = x1;
            x1 = x2;
            fx1 = fx2;
            x2 = (1 – ReductionFactor) * a + ReductionFactor * b;
            rotatedList = current.Rotate(x2);
            fx2 = rotatedList.DistanceTo(target);
        }
    }
    while (Math.Abs(b – a) > epsilon);
 
    float min = Math.Min(fx1, fx2);
 
    return 1.0f – 2.0f * min / Diagonal;
}

Grâce à cet algorithme, nous pouvons simplement comparer un template avec la gesture courante et obtenir un score (entre 0 et 1). Charge à nous de définir le score minimal pour considérer qu’il y a une égalité.

Learning Machine

Pour améliorer notre taux de réussite, il nous suffit de disposer de plusieurs templates. Pour cela, nous allons travailler avec la classe LearningMachine dont le rôle est précisément de stocker nos templates (i.e. d’apprendre de nouveaux modèles) et de les confronter avec la gesture courante. Elle sait bien entendu se sérialiser et se désérialiser et via sa méthode Match elle parcourt ses RecordedPath(qui sont donc des listes de points normalisés) pour les comparer avec la liste courante:

public class LearningMachine
{
    readonly List<RecordedPath> paths;
 
    public LearningMachine(Stream kbStream)
    {
        if (kbStream == null || kbStream.Length == 0)
        {
            paths = new List<RecordedPath>();
            return;
        }
 
        BinaryFormatter formatter = new BinaryFormatter();
 
        paths = (List<RecordedPath>)formatter.Deserialize(kbStream);
    }
 
    public List<RecordedPath> Paths
    {
        get { return paths; }
    }
 
    public bool Match(List<Vector2> entries, float threshold, float minimalScore, float minSize)
    {
        return Paths.Any(path => path.Match(entries, threshold, minimalScore, minSize));
    }
 
    public void Persist(Stream kbStream)
    {
        BinaryFormatter formatter = new BinaryFormatter();
 
        formatter.Serialize(kbStream, Paths);
    }
 
    public void AddPath(RecordedPath path)
    {
        path.CloseAndPrepare();
        Paths.Add(path);
    }
}

Chaque RecordedPath implémente la méthode Match qui fait donc appel à la Golden Section Search:

public bool Match(List<Vector2> positions, float threshold, float minimalScore, float minSize)
{
    if (positions.Count < samplesCount)
        return false;
 
    if (!positions.IsLargeEnough(minSize))
        return false;
 
    List<Vector2> locals = GoldenSection.Pack(positions, samplesCount);
 
    float score = GoldenSection.Search(locals, points, –MathHelper.PiOver4, MathHelper.PiOver4, threshold);
 
    return score > minimalScore;
}

Si un RecordedPath trouve une correspondance nous pouvons alors indiquer avoir trouvé une gesture connue.

Ainsi, grâce à notre algorithme de détection et à la learning machine, nous sommes en présence d’un système à la fois fiable et très peu dépendant de la qualité des informations transmises par Kinect.

Vous trouverez ci-après un exemple de base de connaissances pour reconnaitre un cercle : http://www.catuhe.com/msdn/circleKB.zip.

Conclusion

Nous avons donc à notre disposition un ensemble d’outils permettant de travailler simplement avec Kinect. De plus nous disposons de deux systèmes permettant de détecter de très nombreuses gestures.

A vous de jouer maintenant pour utiliser ces services dans vos applications Kinect !

FR – Gestures & Kinect