Homemade Pixels

Des pixels frais qui sortent du four le blog de MrHelmut.

Hoy : derrière la reconnaissance de postures avec Kinect

Il y a peu, j’ai ressorti Hoy de mes cartons afin de le montrer en public à une soirée. Je ne l’avais pas modifié depuis sa création qui m’avait pris une poignée d’heures au cours de la Global Game Jam 2012. J’avais entre temps pesté sur la politique de licensing de Microsoft au sujet de Kinect sur PC, puis plus ou moins abandonné l’idée de continuer tout développement sur Hoy. Mais le ressortir a été une bonne occasion pour m’y remettre, et notamment pour passer à la dernière version du SDK Kinect qui, entre la création de Hoy et aujourd’hui, est passé de la Beta 2 à la version finale 1.6.

Pas de bol pour moi, les changements dans le SDK étaient plutôt majeurs et j’ai du au final re-coder l’ensemble de Hoy (pas bien long cela dit, en tout et pour tout, j’ai 600 lignes de code). Quitte à tout refaire, j’en ai profité pour remettre à plat mon algorithme de reconnaissance de postures. D’où le présent article, histoire de poser un peu la démarche.

(Lisez l’article en pleine page si les figures sont rognées.)

Mais qu’est-ce que Hoy déjà ?

Voir la vidéo de gameplay.

Hoy est un jeu PC pour Kinect au principe tout simple : une posture apparait à l’écran, le joueur doit la reproduire et crier “Hoy !” pour la valider. Si elle est bien reproduite, le jeu passe à la posture suivante. Le but du jeu est alors d’enchainer un maximum de postures en une minute, l’ordre des postures étant aléatoire (parmi 10 postures différentes).

Un principe tout bête mais qui marche diablement bien en soirée et qui fait perdre des kilos (et donnait des méga crampes à son concepteur avant que le SDK Kinect n’intègre Kinect Studio).

L’enjeu, d’un point de vue programmation, est de reconnaître ces fameuses 10 postures avec Kinect. Mais en fin de compte, Kinect n’a pas grand chose à voir la dedans, c’est un problème purement algorithmique.

Les 10 postures de Hoy

Les 10 postures de Hoy.

Le SDK Kinect, la simplicité même

Le SDK Kinect officiel a un très très gros avantage sur ses “concurrents” (tels que OpenKinect) : l’API est d’une simplicité rare et la reconnaissance du corps est très performante.

Je vous aurais bien fait un article dédié à l’utilisation du SDK, mais honnêtement, il est déjà super bien documenté et sa mise en œuvre est un jeu d’enfant. C’est simple, en C#, cela se résume à de la programmation événementielle : on déclare un délégué qu’on associe à un événement. Et voilà, c’est fini, Kinect appelle alors votre délégué à chaque fois qu’un (ou des) squelette est reconnu (30x/seconde). Le SDK vous renvoie alors l’intégralité des squelettes, des jointures reconnues, leurs positions dans l’espace, leurs angles, etc. Et il se charge aussi tout seul du tracking.

Tous les joints que Kinect reconnait

Tous les joints que Kinect reconnait.

Première version de Hoy, approche très naïve

Dans la première version que j’avais développé, complètement à l’arrache en ~4h, j’avais implémenté une reconnaissance ultra basique où je mesurais simplement le positionnement de points relativement à d’autres. Prenons l’exemple de la posture suivante.

Les joints important dans la reconnaissance de cette posture

Les joints important dans la reconnaissance de cette posture.

Grosso modo, pour déterminer si le joueur est en train de faire cette posture, je vérifie si les coudes sont vers l’extérieur (elbowRight.X < handRight.X && elbowLeft.X > handLeft.X) et que les mains sont bien levées au dessus de la tête (handRight.Y < head.Y && handLeft.Y < head.Y). Simple comme bonjour, et efficace dans la majorité des cas.

Problème : plus on a de postures différentes, et plus certaines conditions commencent à se recouvrir. Dans les faits, l’algorithme a des fois des ratés et peut considérer une posture comme étant valide alors que le joueur en fait une autre qui partage des similarités. Par effet de bord, si le joueur valide une posture et que la posture suivante fait parti de ces cas limites, alors le jeu valide directement la posture (car très peu de temps s’est écoulé et que le cri de validation est encore actif). Pour résumer, mes conditions et mes postures ne sont pas suffisamment discriminées pour que cette approche soit optimale. De plus, Kinect part ponctuellement en sucette et donne pendant une fraction de seconde des valeurs aberrantes, qui parfois peuvent ressembler à une posture.

Résultat : le jeu accorde bien plus de postures qu’il n’est censé le faire, et donc dans de rares cas, 2, 3 ou 4 postures peuvent être validées d’un coup d’un seul.

Donc Thomas W., si tu me lis, NON, TU N’ES PAS LE CHAMPION DE HOY, tu as juste fait un putain de bug exploit. ^^ (Et le connaissant il me répondra que les bug exploit font parti de la maîtrise d’un jeu, et enchainera avec les speedruns, etc.)

J’ai tenté bien des choses pour amortir le problème. Ajouter un timestamp pour empêcher trop de validations si le joueur cri comme un barbare, empêcher que des postures trop semblables se suivent, avoir des conditions plus nombreuses et précises, etc. Ça marchait plus ou moins, mais je n’en étais pas vraiment satisfait parce que ça atrophiait un peu trop le gameplay rapide du jeu.

Nouvelle version, pattern matching et apprentissage

Un autre problème de la méthode précédente est que les valeurs des conditions ont été choisies sur base de ma propre physionomie et de ma propre compréhension des postures. Ce qui fait que le jeu n’est pas adapté à tous et ça énerve certains joueurs. Je considère qu’à partir du moment où le joueur doit crier 4 fois “Hoy !” pour valider, mon algorithme a chier dans le pâté. Et ça arrivait régulièrement.

Comment faire pour que ma reconnaissance soit générique pour toutes les physionomies, tout en ayant un certain degré de tolérance pour que tout le monde fasse les postures à sa façon et tout en levant le problème de l’ambiguïté entre certaines postures ? Le Pattern Matching ! (ou reconnaissance de patron)

Le pattern matching consiste à comparer deux ensembles de points entre eux, point à point, et de mesurer une “distance” entre ces deux ensembles. Plus la distance est courte, plus les deux ensembles sont similaires. C’est par exemple ce type d’algorithmes qui est utilisé pour la reconnaissance d’empreintes digitales (les points étant les nœuds et imperfections naturelles de votre peau). Voyez un peu ça comme une version informatique d’un jeu de formes pour enfant.

Une illustration un peu quelconque du pattern matching piqué au pif sur google images (http://www.cs.helsinki.fi/research/pmdm/cpm/)

Une illustration un peu quelconque du pattern matching piqué au pif sur google images (source en lien sur l'image).

Un tel algorithme repose alors sur une base de données de patterns (ensembles de points) représentant les postures à détecter.

Une schématisation de la base de données de patterns de Hoy (et non, le point dans l'entre jambe n'est pas ce que vous vous imaginez, bande de perverts).

Une schématisation de la base de données de patterns de Hoy (et non, le point dans l'entre jambes n'est pas ce que vous vous imaginez, bande de pervers).

Une fois que l’on a une base de données de points, on compare tous les patterns à ce que Kinect a reconnu comme points. Dans la pratique, j’ai implémenté un algorithme de comparaison point à point assez simple connu, elastic matching. Vous ai-je déjà dit que je suis chercheur en informatique ? Car oui le lien précédent pointe vers un article scientifique et que ça m’arrive de mettre en application une partie de mes recherches dans mes jeux (en l’occurrence, j’ai repris un algorithme que j’avais déjà développé pour faire de la reconnaissance d’écriture manuscrite, ça marche aussi à base de points). En sorti de cet algorithme, on a un histogramme du résultat de la reconnaissance.

Un exemple de reconnaissance, une valeur de 1 étant une concordance parfaite avec une figure.

Un exemple de reconnaissance, une valeur de 1 étant une concordance parfaite avec une posture.

On peut alors aisément supposer que la posture ayant le meilleur taux de reconnaissance est la posture que le joueur est bel et bien en train de faire. Bingo ? Pas tout à fait.

Le problème des algorithmes de matching (cette catégorie ci en tout cas) est que leur qualité dépend grandement de la base de données de patterns sous-jacente. Dans mon cas, cette base de données a été faite à partir de mes propres postures, et donc toujours de ma seule et unique physionomie. Ce qui fait que l’algorithme marche très bien avec des gens qui me ressemblent, mais lorsque que d’autres personnes s’y collent, les taux de reconnaissance se resserrent. Comment être certain que la meilleure posture reconnue est bien la bonne lorsque la suivante a à peine 2% d’écart ? L’incertitude est trop faible pour que l’on puisse conclure de manière sure, et donc valider la posture en toute sérénité.

Il faut donc construire une base de patterns la plus générique possible, et pour cela, j’ai enregistré tout un ensemble de patterns sur la base de postures de deux amis à la physionomie radicalement différente de la mienne. Résultat ?

Le même exemple qu'avant avec une base de patterns composées à partir de plusieurs personnes.

Le même exemple qu'avant avec une base de patterns composées à partir de plusieurs personnes.

Les écarts sont beaucoup plus importants ! Ce qui signifie que deux choses : qu’il y a beaucoup moins d’ambiguïté entre les postures et que l’algorithme est beaucoup plus tolérant aux différentes physionomies.

Mieux encore, la base de données de patterns peut être enrichi à volonté au fur et à mesure que Hoy est joué. Vous vous souvenez des postures mal reconnues où le joueur cri plus de 4 fois ? Lorsqu’un tel cas de figure survient, je considère toujours que l’algorithme a merdé, mais ici, je peux ajouter la posture du joueur au pattern de la posture qu’il est censé reproduire. Ceci aura pour effet d’alimenter la base de donnée et de la rendre de plus en plus générique au fil des échecs de l’algorithme. En d’autres termes, Hoy apprend et devient de plus en plus performant au fur et à mesure qu’il est joué.

A titre de comparaison, l’algorithme de Kinect qui reconnait le squelette a un peu été conçu de la même manière. Sauf que chez Microsoft, on n’y va pas avec le dos de la cuillère et on utilise des centaines de milliers d’échantillons. Et je suis persuadé que des jeux comme Dance Central fonctionnent sur ce genre de principe, avec une dimension temporelle en plus cela dit (car il s’agit de mouvements, et non plus de simple poses).

Fun facts autour de Hoy

  • Je ne reconnais pas le mot “Hoy” en tant que tel lorsqu’un joueur le cri. Je reconnais uniquement le volume ! C’est assez rigolo car le tutoriel demande bien de dire “Hoy”, mais la supercherie est telle que les gens ne s’en rendent pas compte et crient “Hoy” comme des damnés ^^. Tout ce que je fais, c’est une mesure du bruit de fond à chaque début de partie pour déterminer le seuil de volume qui représente un cri. Kinect peut faire de la vrai reconnaissance vocale, mais il y a une trop grande latence pour que ce soit exploitable dans le gameplay rapide de Hoy.
  • Dans sa première version, sur certaines postures, je ne reconnaissais pas tout. Par exemple sur les postures avec les bras bien écartés, je ne faisais pas de reconnaissance sur les bras. On pouvait mettre les bras comme on voulait. Mais les joueurs étaient bernés par le fait que l’image leur demandait d’écarter les bras, et en faisaient donc autant. Je me suis bien poilé à regarder les gens jouer tout en sachant qu’ils transpiraient pour RIEN.
  • Kinect permet de localiser spatialement un son. En clair, on est capable de déterminer si c’est bien le joueur qui vient de crier. J’ai donc voulu implémenter un mode versus, où deux joueurs font chacun des postures et doivent crier. Dans la théorie c’était parfait, mais Kinect ne fait pas de mesure de son suffisamment rapidement. Il donne la position générale d’un son que toutes les 500ms environ, un temps beaucoup trop grand qui est bloquant. J’ai donc laissé tomber le mode versus.

Si vous n’êtes pas membres wefrag, vos commentaires peuvent être recueillis par mail :

contact

7 commentaires pour “Hoy : derrière la reconnaissance de postures avec Kinect”

  1. Lucyberad dit :

    “Et je suis persuadé que des jeux comme Dance Central fonctionnent sur ce genre de principe, avec une dimension temporelle en plus cela dit (car il s’agit de mouvements, et non plus de simple poses).”
    J’en sais quelquechose et je confirme ;)

    “mais la supercherie est telle que les gens ne s’en rendent pas compte”
    Ma joie au quotidien en tant que programmeur :P

    Très bon article. J’ai beaucoup appris durant les game jam aussi et je suis admiratif du rapport simplicité/efficacité de Hoy.

  2. daemonhell dit :

    Sympathique à lire.
    Mais si je suis méchant, je jouerai à ton jeu sans faire la bonne position, juste en montrant mon majeur à Kinect et en criant Hoy quatre fois de suite afin de pourrir tes stats de reconnaissance ! =D

  3. Hubebert dit :

    Super article. Pour le mode multijoueur c’est vraiment dommage, tu pourrais pas faire une solution a base de cri différents? Tu ne pourrais plus utiliser ta supercherie mais tu pourrais trouver une autre astuce… Un qui crie aigu, l’autre grave ?

    Ou tout simplement un cri qui valide les positions des deux joueurs, et tant pis pour le retardataire. Je trouve que ce genre de jeux prends tout son sens quand on à l’air con a deux =)

  4. MrHelmut dit :

    Merci pour vos réactions. :-]

    @daemonhell : haha, bonne remarque. Dans des cas comme ca, si la figure “ratée” a une reconnaissance inférieure à 70%, je l’ignore et passe à la suivante. Ce qui fait que la figure doit quand même ressembler à peu pres à la figure cible. Mais c’est clair qu’il y a quand même moyen de biaiser le système ^^. Pour éviter ca, il faudrait que j’organise des séances de calibration dédiées, et que je désactive l’apprentissage pour jouer.

    @Hubebert : aigu/grave, pourquoi pas. Je ne m’y connais pas trop en traitement de signal, il faut que je vois ce que je peux tirer des données brutes.
    L’intervention de Lucyberad m’a indirectement donné l’idée de faire défiler des figures avec un tempo, et de les passer même si elles sont ratées. A la Just Dance en somme.
    Ou alors, mettre qu’une seule figure, que les deux joueurs doivent faire, et valider dès qu’un des deux crie et seules les postures bonnes donnent des points. La ce serait carrément du gros battle où il faut être plus rapide que l’adversaire et le griller en criant en premier. Mais ca peut devenir l’anarchie ^^.

  5. Daemetrius dit :

    Article très intéressant, d’autant que j’attaque avec des collègues étudiants le développement d’un petit jeu de ce genre pour les enfants autistes.
    Ça répond à certaines questions que je me posais sur l’apprentissage, et je m’en vais lire le .pdf sur l’Elastic Matching, merci Helmut !

  6. Lucyberad dit :

    L’intervention de Lucyberad m’a indirectement donné l’idée de faire défiler des figures avec un tempo, et de les passer même si elles sont ratées. A la Just Dance en somme.

    Just Dance fait dans la suivi d’une chorégraphie et note la qualité de cette dernière. Alors que Hoy se propose plutôt d’imposer un rythme définit par le joueur. La qualité principale de Hoy ne réside pas dans la qualité de reproduction des poses/mouvements (puisque contrairement à Just Dance qui note le mouvement de 0% à 100%, Hoy ne fait que valider la pose par = à 50%); mais simplement du Rythme que se donne le joueur: le joueur impose sa propre difficulté au départ et Hoy invite ce dernier à la repousser de plus en plus. De ce fait, le challenge est immédiat et le reward quasiment toujours présent puisque nous avons majoritairement tendance à nous sous-estimer dans un domaine inconnu (instinct de conservation). Il ne faudrait vraiment pas perde cette “Unique Selling Point” en faisant que Hoy impose le rythme comme une chorégraphie classique.

    Ou alors, mettre qu’une seule figure, que les deux joueurs doivent faire, et valider dès qu’un des deux crie et seules les postures bonnes donnent des points.

    C’est un très bon mode de jeu multi. C’est participatif et finalement il y 4 cas possibilités:
    - le joueur 1 à l’initiative du rythme et réussit mieux que le joueur 2.
    - le joueur 2 a l’initiative du rythme mais le joueur 1 réussit mieux les poses (très intéressant comme cas).
    - l’inverse du cas n°1.
    - l’inverse du cas n°2.
    Dans un référentiel Game Design, c’est un bon potentiel pour un jeu 2 joueur et se montre déjà plus riche qu’un simple duel à 2 cas (aka: “ki à le plus gros kiki”) comme le diaporama de postures.

    Mais ca peut devenir l’anarchie ^^.

    Ironiquement, tant que l’anarchie proviens des joueurs et non du jeu, alors c’est ce qui marche le mieux en soirée (jeu de groupe).
    C’est d’ailleurs là dessus que se repose le karaoké, c’est l’anarchie quand le chanteur est mauvais et c’est drôle et sa force l’admiration de ses camarades quand le chanteur est bon. Le jeu lui ne fait que proposer une partition.

    Un qui crie aigu, l’autre grave ?

    Probablement en faisant la moyenne du signal avec un filtre haut et un filtre passe bas on arriverai à différencier les deux. Mais dans la pratique ça sent plutôt le casse gueule, suffit de voir les jeux de karaoké qui ont du mal à gérer les différent diapasons des chanteurs/joueurs qui ont eux même du mal à savoir s’ils sont juste ou pas.
    Faire un “Hoy” et un “Hey”, je sais pas si c’est assez flagrant pour différencier mais quoiqu’il en soit, si Kinect est en mesure de faire la différence il y aura le problème premier que ce dernier mets beaucoup trop de temps à interpréter le résultat.
    Et de doute façon, si le joueur 1 est plus rapide à faire défiler que le joueur 2, alors finalement on revient à un duel classique moins intéressant que le “Hoy” accessible aux 2 joueurs.

    Au final, il suffit de voir le nombre de variable que le joueur peut affecter et il y en a 2:
    - qualité de pose.
    - rythme/temps imposé par le “Hoy”.
    Les meilleurs modes de jeu sont ceux qui utiliseront à 100% ces 2 variables pour les joueurs soit 2²=4 (ce qui coïncide avec le gamemode du Hoy partagé).
    Bien sûr, il est possible d’enrichir le jeu avec d’autres variables (il faut juste faire gaffe à éviter que ça devienne trop riche au point de ruiner son accessibilité).

    Ps: Si vous voulez des détails sur la technique utilisée sur Just Dance, vous pouvez toujours m’envoyer des questions par mail et je verrais ce que je peut partager sans divulguer de données sensibles ou de secret de fabrication du jeu bien sûr.

  7. MrHelmut dit :

    Merci pour cet intéressant retour de game design !

    Je suis tout à fait d’accord avec le fait que la clef de Hoy, c’est le rythme imposé par le joueur. En fait, tout ton commentaire me parle beaucoup.

    Lucyberad a dit :
    tant que l’anarchie proviens des joueurs et non du jeu, alors c’est ce qui marche le mieux en soirée

    Vu sous cet angle, c’est clairement le petit zeste qui change tout. Je vais rester sur ce principe ! C’est le plus simple à implémenter et à la fois celui au game design le plus probant comme tu le soulignes.

    Le mode solo sera toujours la pour le scoring pur et dur.

    Je songe aussi à rajouter un mode solo “spécial”, où certaines figures “impossibles” (qui valent plus de points) peuvent apparaitre, mais qu’on ne sera pas obligé de faire. Histoire de rajouter un paramètre de prise de risque et contrôle du score. A voir aussi pour adjoindre un multiplicateur de combo.

    Ca me motive à continuer à le développer. Un mode versus et un peu de polish, et hop. Du genre les classiques “mets ta tronche facebook”, “tweet ton score” et éventuellement un scoreboard en ligne. Mais ca ferait éventuellement intervenir un clavier et ca prendrait à contrepied l’utilisabilité générale que je me fais du jeu.

Laisser un commentaire

Vous devez être connecté avec votre compte Wefrag pour publier un commentaire.