Bonjour à toutes et tous.

Mon problème n'est pas des plus simple mais bon, je tente quand même ma chance ici

Alors voila : dans le cadre d'un projet scolaire, je doit réaliser un jeu vidéo qui utilise non pas une souris mais une webcam qui filme l'écran.
En analysant l'image, on en déduit où la caméra vise et on place le curseur à cet endroit.

Le problème est que la caméra ne donne qu'environ 20 images par secondes et donc le déplacement de la souris est très saccadé.

J'aurais donc besoin de votre aide pour la réalisation d'une fonction d'interpolation de x points précédents pour en déduire la position du point visé entre 2 prises de vue de la caméra.


En bref :
J'ai x points 2D(x,y) dépendant du temps t.
Comment interpoler ces points pour en créer un entre 2 temps t.

Bonjour,

Il y a plusieurs types d'interpolations possibles : la page wikipédia sur l'interpolation numérique en donne quelques unes.

Dans votre cas, je suggère que vous fassiez une simple interpolation linéaire puisque vous n'avez pas besoin d'être très précis : encore une fois, 'interpolation linéaire' sur wikipédia vous donnera toutes les informations nécessaires.

Si vous ne voulez ajouter qu'un seul point entre deux autres points, les coordonnées de ce point sont plutôt simples à calculer et sont:
<math>\(x_{i+1/2} = \frac{x_{i+1}+x_i}{2}\)</math>,
<math>\(y_{i+1/2} = \frac{y_{i+1}+y_i}{2}\)</math>.

Oui, mais c'est légèrement plus complexe que ça ...
Comme dis plus haut, les points dépendent du temps.
En effet, il y a parfois 10 images par secondes, parfois 30 ...
Tout dépend de la charge de travail du CPU et de la caméra.

Donc une interpolation linéaire entre 2 points successif est difficilement envisageable.

Peut-être ai-je mal compris le problème.

Citation : lorrio

J'aurais donc besoin de votre aide pour la réalisation d'une fonction d'interpolation de x points précédents pour en déduire la position du point visé entre 2 prises de vue de la caméra.

À la vue de cette phrase, il semble plutôt s'agir d'un problème d'extrapolation. Si je comprends bien vous voulez à l'instant t prévoir le position du curseur à l'instant <math>\(t+\Delta t/2\)</math> en utilisant les x points précédents. Si c'est le cas, alors il faut se pencher du côté des interpolations polynomiales.

extrapolation, interpolation, ça se ressemble non ?

Sinon, ce que je voudrais faire, c'est calculer la position de la souris toutes les 10 ms sachant que j'ai une image de temps en temps.

Exemple :

t = 0 ms : une image
t = 55 ms : une autre image
t = 112 ms : une autre image
t = 165 ms : une autre image
t = 220 ms : une autre image
t = 265 ms : une autre image

et le but serait donc de faire une position de la souris à :

t = 100 (prévoir quelques images avant de commencer)
t = 110
t = 120
t = 130
...

Yep interpolation polynomiale avec quelque points precedent .. ou mieu... spline cubique !

Souhaites-tu avoir une position pour t=270ms si ta dernière image est à 265ms ou est-ce que tu as toujours quelques images d'avance ?

Je pense que pour éviter les problèmes, il est préférable de rejoindre petit à petit le point de la dernière image (donc une souris avec un peu de retard) plutôt que d'imaginer des points sans vraiment savoir ou l'on va.

Après, interpolation polynomial, j'ai un peu cherché, mais j'ai seulement trouvé comment interpoler des fonction de R vers R : y=f(x) et pas R vers R² : (x,y)=f(t)

Ça ne pose pas de problèmes, tu peux interpoler séparément les deux composantes x et y.
Franchement, l'extrapolation avec des polynômes d'ordre élevé te permettra même de savoir avec assez bien de précision ou tu vas, à condition que tu aie régulièrement des coordonnées quand même.
Tu peux d'ailleurs une fois que ce sera implémenté comparer au moment ou tu reçoit une nouvelle coordonnée cette valeur avec celle que ton programme "prédit". Je pense que tu peux espérer une excellente précision, surtout si les mouvements ne sont pas particulièrement rapides.

Bonjour,

On peut appeler <math>\(t_i\)</math> les instants où tu as les coordonnées <math>\((x_i, y_i)\)</math> du pointeur de la souris.
Dans ton exemple
<math>\(t_0 = 0 ms, t_1 = 55 ms, t_2 = 112 ms, t_3 = 165 ms, t_4 = 220 ms, t_5 = 265 ms\)</math>

Tu peux faire deux splines cubiques naturelles d'interpolation :

• une pour les nœuds <math>\((t_i, x_i)\)</math>, tu obtiendras une fonction de R dans R, <math>\(\sigma_x\)</math>.
• une autre pour les nœuds <math>\((t_i, y_i)\)</math>, tu obtiendras une fonction de R dans R, <math>\(\sigma_y\)</math>

Pour chaque instant t, tu auras <math>\((\sigma_x(t), \sigma_y(t))\)</math> comme coordonnées du pointeur.
Par contre, les nœuds <math>\((t_i, x_i)\)</math> et <math>\((t_i, y_i)\)</math> ne sont pas équidistants. Les formules sont un peu chiadées.

Merci pour toutes vos réponses,
Je suis en train de tester tout ça
(notamment un algorythme d'extrapolation polynomial)
Je vous tiens au courant.