CCP Informatique PSI 2018

Thème de l'épreuve Système d'aide à l'arbitrage : le Hawk-Eye
Principaux outils utilisés intégration numérique, traitement d'images, algèbre linéaire, bases de données relationnelles
Mots clefs Hawk-Eye, tennis, triangulation, analyse de données

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                                               

Rapport du jury

(télécharger le PDF)
     

Énoncé obtenu par reconnaissance optique des caractères


SESSION 2018 ! ! ! PSIIN07 ! ÉPREUVE SPÉCIFIQUE - FILIÈRE PSI! !!!!!!!!!!!!!!!!!!!!" INFORMATIQUE Vendredi 4 mai : 8 h - 11 h! !!!!!!!!!!!!!!!!!!!!" N.B. : le candidat attachera la plus grande importance à la clarté, à la précision et à la concision de la !"#$%&'()*+,'+-)+%$)#'#$&+./&+$0.)"+1+!.2"!.!+%.+3-'+2.-&+4-'+/.054.!+6&!.+-).+.!!.-!+#7")()%"8+'4+4.+ /'9)$4.!$+/-!+/$+%(2'.+.&+#.:!$+2(-!/-':!.+/$+%(02(/'&'()+.)+.;24'3-$)&+4./+!$'/()/+#./+')'&'$&':./+3-7'4+ a été amené à prendre.! ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" ! ! ! Les calculatrices sont interdites ! ! ! ! ! ! ! Le sujet est composé de 4 parties, toutes indépendantes. ! ! ! ! L'épreuve est à traiter en langage Python, sauf les questions sur les bases de données qui seront ! traitées en langage SQL. La syntaxe de Python est rappelée en annexe, page 16. ! Les différents algorithmes doivent être rendus dans leur forme définitive sur la copie en respectant les ! éléments de syntaxe du langage (les brouillons ne sont pas acceptés). ! Il est demandé au candidat de bien vouloir rédiger ses réponses en précisant bien le numéro de la question traitée et, si possible, dans l'ordre des questions. La réponse ne doit pas se cantonner à la ! rédaction de l'algorithme sans explication, les programmes doivent être expliqués et commentés. ! ! Sujet : page 1 à page 15 ! Annexe : page 16 ! ! ! ! ! ! 1/16 ! SYSTÈME D'AIDE À L'ARBITRAGE : LE HAWK-EYE Partie I - Présentation générale du système Le système Hawk-eye est un système d'aide à la décision arbitrale utilisé dans le sport de haut niveau, notamment le tennis, un des plus connus. Il a été développé par le Paul Hawkins en 1999 avec pour objectif d'augmenter la qualité des décisions arbitrales et fournir un résultat rapide, clair et précis lors des moments décisifs de rencontres sportives (figure 1). Il a été utilisé pour la première fois au tennis lors du Masters de Miami en 2006. Chaque joueur peut faire appel trois fois par set de cette décision. Figure 1 ­ Décision officielle du système Hawk-eye Pour analyser la trajectoire et la position de la balle, le système Hawk-Eye se compose de dix caméras, réparties à égale distance autour du court de tennis dans les tribunes (figure 2). Ces caméras peuvent photographier "en rafale" des objets se déplaçant à une grande vitesse grâce à un capteur photographique. Elles peuvent enregistrer jusqu'à 1 000 images par seconde. Ces images sont ensuite envoyées au poste de commande du système. Figure 2 ­ Position des caméras haute vitesse autour du terrain de tennis L'objectif de l'étude proposée est de réaliser le programme de suivi (tracking) de la trajectoire de la balle de tennis par le système Hawk-eye, la reconstruction de la trajectoire et enfin l'identification de la position de l'impact de la balle avec le sol pour savoir si la balle est dans les limites du terrain ou non. Afin de mieux appréhender le problème, nous commencerons par la modélisation et l'étude théorique de la trajectoire d'une balle de tennis et montrerons en quoi cette seule modélisation est insuffisante pour l'aide à l'arbitrage. Dans tout le sujet, il sera supposé que les bibliothèques sont déjà importées dans le programme. Attention, l'utilisation des fonctions min et max ne sera pas acceptée. 2/16 Partie II - Modélisation de la trajectoire de la balle L'objectif de cette partie est de déterminer la trajectoire théorique d'une balle de tennis et de montrer les limites du résultat obtenu. La trajectoire d'une balle de tennis dépend de plusieurs paramètres : - la vitesse de frappe par la raquette du joueur ; - l'angle de frappe ; - les frottements dans l'air ; - la vitesse de rotation donnée à la balle par la raquette du joueur. Le schéma de la figure 3 représente un terrain de tennis pour une partie en simple et la trajectoire de la balle dans l'espace de coordonnées (x, y, z). Le repère est choisi de sorte que le plan (0, x,z) soit horizontal. Figure 3 ­ Paramétrage du terrain de tennis et trajectoire d'une balle Paramétrage - La balle a une masse m et un rayon R. - Le mouvement de la balle est étudié dans le référentiel R lié au terrain et supposé galiléen. On lui associe le repère (O, #» x , #» y , #» z ), avec O le point de coordonnées (0, 0, 0). - La position initiale de la balle est définie dans le référentiel supposé galiléen lié au terrain au point I par (x0 , y0 , z0 ). - La balle est repérée par la position de son centre d'inertie G auquel est associé le vecteur # » OG = (x + x0 ). #» x + (y + y0 ). #» y + (z + z0 ). #» z. #» #» - La vitesse de la balle est notée V = v x #» x + vy #» y + vz #» z et sa vitesse initiale V0 . #» - L'angle de frappe entre le plan (O, #» x , #» z ) et V0 est . #» - La vitesse de rotation sur elle-même de la balle est notée = #» z. - #» g = - g #» y est l'accélération de la pesanteur. Hypothèses - On supposera dans toute la suite de cette partie que la balle ne se déplace que dans le plan (O, #» x , #» y ). Par conséquent, à chaque instant, vz = 0. #» - Les différents efforts s'exerçant sur la balle de tennis sont représentés sur la figure 4, page 4. t est un vecteur unitaire tangent à la trajectoire et dirigé suivant le sens de la trajectoire. #» n est un vecteur unitaire normal à la trajectoire. 3/16 Figure 4 ­ Efforts de l'air sur la balle Équation du mouvement de la balle Le mouvement de la balle de tennis est défini par l'équation suivante # » d2 OG #» #» m 2 = m. #» g + FT + F P dt (1) 1 #» #» # » n où air est la masse volumique de l'air avec FT = - ..R2 .air .C1 .V 2 . t et F P = air .R3 .C2 .V.. #» 2 3 (environ 1 kg /m à température ambiante), V la vitesse de la balle et C1 et C2 deux coefficients sans dimension qui dépendent du nombre de Reynolds. L'équation (1) une fois projetée dans le plan (O, #» x , #» y ) devient : d2 x(t) 1 m = - ..R2 .air .C1 .V 2 . cos() - air .R3 .C2 .V.. sin() 2 dt 2 m (2) 1 d2 y(t) ..R2 .air .C1 .V 2 . sin() + air .R3 .C2 .V.. cos(). = - m.g - dt2 2 (3) u0 u v v dx(t) dy(t) et v(t) = et dont la condition initiale est Y = 0 . On pose Y = , avec u(t) = dt dt x0 x y y0 Q1. Mettre les équations (2) et (3) sous la forme d'un problème de Cauchy du type : dY = F(Y, t). dt La résolution numérique des équations différentielles (2) et (3) repose sur leur discrétisation temporelle et conduit à déterminer à différents instants ti une approximation de la solution. On note ui et vi les approximations des composantes du vecteur vitesse (u(t),v(t)) et xi et yi les approximations des composantes du vecteur position (x(t), y(t)) à l'instant ti . On note t = ti+1 - ti , le pas de temps constant. Le schéma d'Euler conduit à la relation de récurrence suivante : Yi+1 = Yi + tF(ti , Yi ). 4/16 Q2. Compléter sur votre copie la fonction euler(T,N,F,Y0) ci-dessous permettant de construire le schéma d'Euler. d e f e u l e r ( T , N, F , Y0 ) : Y= z e r o s ( ( l e n ( Y0 ) ,N) ) t = a r a n g e ( 0 , T , T / N) # c o n d i t i o n s i n i t i a l e s à compl é t e r f o r i i n range ( 1 ,N) : # z o n e à compl é t e r r e t u r n ( t , Y) La reconstruction de la trajectoire d'une balle de tennis à partir des lois physiques et des conditions initiales ne se révèle pas satisfaisante en terme de précision pour l'aide à la décision arbitrale. En effet, les paramètres climatiques (vent, pluie, pression atmosphérique...), de déformation de la balle ou tout autre aléa ne sont pas pris en compte a posteriori. Il convient donc d'adopter une autre méthode vérifiant à tout instant la position de la balle ; c'est ce que permet le système Hawk-eye. Nous allons nous intéresser dans la suite à une partie de l'algorithme permettant de vérifier si une balle est bonne et de reconstruire la trajectoire de la balle. Partie III - Tracking et reconstruction de la trajectoire de la balle de tennis Comme nous l'avons vu dans la partie présentation et plus particulièrement sur la figure 2, page 2, le système Hawk-eye est composé de 10 caméras réparties autour du terrain de tennis. Pour pouvoir obtenir la trajectoire de la balle et déterminer le point d'impact de cette dernière avec le terrain, il est nécessaire de faire appel à une unité de traitement des données de différentes caméras. Cette unité de traitement des données fait appel à un algorithme de calcul qui se décompose en 7 étapes : - Étape 1 : on détermine les limites du terrain ; - Étape 2 : on réalise le calibrage de la caméra (détermination de sa position, son orientation et ses paramètres intrinsèques) ; - Étape 3 : on identifie les pixels représentant la balle et on calcule la position 2D dans chaque image de chaque caméra ; - Étape 4 : on calcule la position 3D de la balle par triangularisation ; - Étape 5 : on assemble les images obtenues ; - Étape 6 : on détermine l'impact de la balle avec le sol sur le terrain ; - Étape 7 : on reconstruit la trajectoire 3D de la balle que l'on affichera pour les spectateurs. Nous nous proposons dans la suite du sujet de nous intéresser plus spécifiquement aux étapes 3 , 4 , 5 , 6 et 7 . III.1 - Détermination de la taille des fichiers récupérés L'image acquise par la caméra est une image en couleur constituée de trois couches de pixels (Red - Green - Blue). La résolution de l'écran est de 1 024 pixels horizontalement et 768 verticalement. Les données de l'image sont stockées dans un tableau de type list à trois dimensions : la première dimension correspond à la coordonnée selon x, la seconde à la coordonnée selon y et la troisième correspond à la couleur (rouge, vert ou bleu, indice 0, 1 ou 2). 5/16 Ainsi, les dimensions du tableau sont : n × m × 3 où n = 1 024 et m = 768. La valeur associée à chaque pixel est un entier compris entre 0 et 255. Un point joué désigne l'ensemble des coups exécutés par les joueurs, service compris, jusqu'à ce que l'un d'entre eux commette une faute ou un coup gagnant. Un échange désigne un couple de coups joués par les joueurs. Q3. On suppose que l'on stocke dans la variable image1 une image enregistrée par la caméra. Indiquer la valeur des expressions suivantes : - len(image1) - len(image1[12][244]) Indiquer le type de l'expression suivante : - len(image1[12][244][2]) Q4. Déterminer, en justifiant succinctement votre calcul, la taille de l'espace mémoire occupé par le tableau représentant l'image émise par la caméra. Q5. Estimer un ordre de grandeur de l'espace de stockage à prévoir pour sauvegarder toutes les images des 10 caméras rapides (1 000 images/s) correspondant à un point joué, puis à un set. Un set comporte en moyenne 100 points joués. On pourra estimer à 10 s la durée moyenne d'un point joué. Indiquer quel moyen de stockage pourra convenir à la sauvegarde des données. Q6. Définir ce qu'on appelle la mémoire vive d'un ordinateur. Indiquer les inconvénients liés à l'utilisation des données décrites à la question précédente. III.2 - Calcul de la position 2D de la balle (étape 3 ) L'objectif de l'algorithme que nous allons étudier ici est d'identifier la position de la balle en prenant en compte sa taille et sa forme sur chaque image enregistrée à l'aide d'une caméra rapide. L'algorithme doit renvoyer les coordonnées x et y de la balle dans le repère (O, #» x , #» y , #» z ) et l'instant correspondant t lorsque celle-ci est détectée. Si la balle n'est pas détectée dans le champ de vision de la caméra, l'information retournée sera None. L'algorithme proposé se déroule en plusieurs étapes : - première étape : détecter tous les objets en mouvement grâce à l'analyse de deux images successives, - deuxième étape : éliminer les objets en mouvement qui ne peuvent pas correspondre à une balle de tennis selon des critères géométriques, - troisième étape : éliminer les "balles fausses" détectées en prenant en compte la trajectoire de la balle. La première étape est réalisée en comparant deux images successives (donc séparées d'un laps de temps très bref). Ces 2 images (image1 et image2) sont quasiment identiques exceptées les zones en mouvement. L'objectif est de créer un nouveau tableau de dimension n × m (avec n = 1 024 et m = 768) dans lequel l'élément correspondant à un pixel est un entier compris entre 0 et 255. Cet entier correspond à un niveau de gris (le noir correspondant à l'entier 0 et le blanc à l'entier 255). Les zones blanches ou claires seront considérées comme des objets en mouvement. Les images sont celles décrites en début de sous-partie III.2 et correspondent à des tableaux à 3 dimensions de type list : n × m × 3. Pour détecter les zones en mouvement, l'algorithme propose de 6/16 calculer pour chaque pixel la somme des différences au carré associées à chaque couleur = (r1 - r2 )2 + (g1 - g2 )2 + (b1 - b2 )2 (4) où ri , gi et bi représentent respectivement les niveaux de rouge, vert et bleu d'un pixel de coordonnées (x, y) de l'image1 et de l'image2. En cas de variation importante de couleur, peut atteindre une valeur supérieure à 255 ce qui pose des difficultés dans la suite de l'algorithme. On veut garantir 0 255 et on impose donc la valeur 255 dans le cas où la formule précédente fournirait une valeur supérieure. Q7. Écrire une fonction detection(image1,image2) qui prend en argument 2 images décrites à la sous-partie III.2 (page 5) et qui renvoie un tableau de dimension n × m d'entiers compris entre 0 et 255 dans lequel chaque élément correspond à . Écrire l'instruction qui permet d'affecter à la variable image_gray le résultat de cette fonction appliquée à deux images im1 et im2. Le tableau ainsi obtenu est ensuite filtré pour éliminer les pixels trop clairs qui correspondent à des parties figées de l'image. Le seuil doit pouvoir être ajusté pour chaque caméra suivant la luminosité et les conditions météorologiques. Q8. Écrire une fonction filtre(image,seuil) qui prend en argument un tableau à deux dimensions (de type list de list) et qui renvoie un nouveau tableau de même dimension que celui passé en argument. Chaque élément de ce nouveau tableau prend la valeur 0 si l'élément correspondant du tableau image est inférieur à la valeur seuil et prend la valeur 1 sinon. Nous avons alors obtenu un tableau qui permet de repérer tous les éléments en mouvement dans l'image. Il reste maintenant à détecter les éléments en mouvement qui peuvent être une balle de tennis. Compte-tenu de la position des caméras latérales et de leur résolution, une balle de tennis occupe au minimum 4 pixels. Nous allons commencer par éliminer tous les pixels en mouvement qui sont isolés dans le tableau : aucun des pixels adjacents parmi les 8 possibles n'est considéré en mouvement. Q9. La fonction filtre_pixel(image) prend en argument un tableau image à deux dimensions, rempli de 0 et de 1. Cette fonction doit permettre de balayer tous les éléments du tableau image et de tester s'ils correspondent à un pixel isolé. Proposer deux schémas permettant d'illustrer le cas d'un pixel isolé et donc à éliminer et celui d'un pixel à conserver. On considère un pixel de coordonnées (p,c) tel que ce pixel ne soit pas situé sur le bord de l'image. Parmi les 4 tests suivants, choisir celui qui permet de détecter si ce pixel est isolé et, si c'est le cas, de l'éliminer. Test 1 i f image [ c - 1 ] [ p -1]==0 or image [ c - 1 ] [ p +1]==0 or image [ c + 1 ] [ p -1]==0 or image [ c + 1 ] [ p +1] == 0 : image [ p ] [ c ]=0 Test 2 i f image [ c - 1 ] [ p -1]==0 and image [ c - 1 ] [ p +1]==0 and image [ c + 1 ] [ p -1]==0 and image [ c + 1 ] [ p +1] == 0 : image [ p ] [ c ]=0 7/16 Test 3 i f image [ p ] [ c ] = = 1 : n b _ p i x e l =-1 f o r k i n [ p -1 , p , p + 1 ] : f o r j i n [ c -1 , c , c + 1 ] : n b _ p i x e l += image [ k ] [ j ] i f n b _ p i x e l ==0: image [ p ] [ c ]=0 Test 4 i f image [ p ] [ c ] = = 1 : n b _ p i x e l =-1 f o r k i n range ( p -1 , p +1) : f o r j i n range ( c -1 , c +1) : n b _ p i x e l += image [ k ] [ j ] i f n b _ p i x e l ==0: image [ p ] [ c ]=0 Une fonction est ensuite implémentée pour éliminer les objets en mouvement trop grands et qui ne peuvent correspondre à une balle de tennis. Ces objets sont en général représentés par des chaînes de pixels à 1 représentant le contour d'un objet en mouvement. Cette fonction ne sera pas étudiée ici. Le script présenté ci-dessous permet de réaliser le prétraitement à partir des images extraites des vidéos enregistrées par une caméra. Les images issues d'un même point sont stockées dans un dossier sequence_ enregistrées au format .bmp et sont nommées image_ numéro de l'image dans la séquence vidéo. 1 2 3 4 5 6 7 8 9 10 11 12 p o i n t = i n p u t ( " R e n t r e r l e numé r o du p o i n t l i t i g i e u x à analyser " ) d i r s = l i s t d i r ( " sequence_ " + point ) f o r image i n d i r s : index_max = 0 i n d e x = i n t ( image [ 6 : 1 1 ] ) i f i n d e x >= index_max : index_max = i n d e x s e q _ b a l l e = [ [ x0 , y0 ] ] # [ x0 , y0 ] p o s i t i o n i n i t i a l e de l a b a l l e # donn é e p a r un a u t r e t r a i t e m e n t f o r image i n d i r s : i n d e x _ i n i t = index_max - 3000 # i n d i c e de l a p r e m i è r e image de l a s é q u e n c e a n a l y s é e 13 i f i n t ( image [ 6 : 1 1 ] ) == i n d e x _ i n i t : 14 image2=i m r e a d ( " s e q u e n c e _ "+ p o i n t +" / "+image ) 15 e l i f i n t ( image [ 6 : 1 1 ] ) > i n d e x _ i n i t : 16 image1 = d e e p c o p y ( image2 ) 17 image2=i m r e a d ( " s e q u e n c e _ "+ p o i n t +" / "+image ) 18 l i s t e _ b a l l e s = t r a i t e m e n t ( image1 , image2 ) 19 s e q _ b a l l e . append ( l i s t e _ b a l l e s ) 8/16 Éléments de documentation - la commande listdir s'applique à un dossier et renvoie une liste de tous les noms de fichiers contenus dans ce dossier, - la commande imread construit un tableau n × m × 3 à partir d'une image bitmap (.bmp), - la fonction traitement renvoie une liste des positions des balles éventuelles détectées dans une image. Cette fonction fait appel aux fonctions précédemment programmées. (Il n'est pas demandé de détailler cette fonction). Q10. Commenter les lignes 2 et 3, puis indiquer l'intérêt de chaque boucle for. Préciser l'intérêt de ce programme. Après les différents traitements définis précédemment, nous avons pour chaque image une liste des coordonnées de la balle. Malgré ces traitements, une image peut contenir plusieurs points pouvant être assimilés à la balle de tennis. Par exemple, dans le cas d'une image i qui contient 2 balles possibles, on stocke les coordonnées dans une liste : image i : xi1 , yi1 , xi2 , yi2 . Chaque liste associée à une image est placée dans une liste qui regroupe ainsi toutes les images de la séquence à analyser : seq_balle = x0 , y0 , ..., xi1 , yi1 , xi2 , yi2 , x(i+1)1 , y(i+1)1 , x(i+1)2 , y(i+1)2 , ... image i image i + 1 À partir de la liste seq_balle et de la vitesse initiale, nous allons chercher à ne conserver que les "balles bonnes" en prenant en compte la trajectoire. On suppose qu'entre deux images successives, la vitesse de la balle varie peu. Ainsi, à partir de la balle détectée à l'image i - 1 (de coordonnées (xi-1 , yi-1 )), nous allons chercher la balle suivante dans une zone rectangulaire dont le centre (xc , yc ) sera calculé à partir de la position de la balle (xi-1 , yi-1 ) et du vecteur déplacement (d x i-1 , dy i-1 ) : xc = xi-1 + d x i-1 et yc = yi-1 + dy i-1 . Le rectangle aura pour dimension Lx = 2d x i-1 + 1 suivant x et Ly = 2dy i-1 + 1 suivant y avec au minimum 3 pixels suivant x et 3 pixels suivant y, c'est-à-dire au minimum Lx = 3 et Ly = 3. - Si plusieurs balles sont présentes dans cette zone (balles candidates), on choisira celle dont la position sera la plus proche du centre. En cas d'égalité, on conservera arbitrairement l'une des 2 positions. - Si aucune balle n'est présente dans la zone, on renverra pour l'image i + 1 la liste [None, None] et on cherchera directement une balle dans l'image suivante i + 2 en doublant les dimensions de la zone de recherche 2Lx - 1 et 2Ly - 1 et en prenant comme pixel central : xc = xi + 2d x i-1 et yc = yi + 2dy i-1 . Les images successives étant prises à intervalles de temps égaux, on définit le vecteur déplacement à l'instant i (ou à l'image i) comme une liste à deux éléments : dep_i = d x i , dy i = xi - xi-1 , yi - yi-1 . L'algorithme proposé dans cette sous-partie est illustré figure 5, page 10. 9/16 sse Ly ite ur v te Vec Lx Balle détectée à l'image précédente Balles candidates Centre de la zone de recherche Balle détectée Figure 5 ­ Détection des "balles bonnes" Q11. a) Écrire une fonction deplacement(pos1,pos2) qui prend en argument 2 listes à 2 éléments (pos1 et pos2) et qui renvoie le vecteur déplacement associé (sous la forme d'une liste à deux éléments). On précisera le type des éléments constituants les listes. Écrire la ou les instructions permettant d'affecter aux variables Lx et Ly les dimensions de la zone de recherche. b) Écrire une fonction distance_quad(xc,yc,liste_balle_i) où xc,yc sont les coordonnées du pixel central et liste_balle_i la liste des balles possibles. Cette fonction doit renvoyer une liste des carrés des distances séparant chaque balle possible du pixel central. c) Écrire une fonction cherche_balle(xc,yc,Lx,Ly,liste_balle_i) où xc,yc sont les coordonnées du pixel central, Lx,Ly les dimensions de la zone de recherche et liste_balle_i la liste des balles possibles. Cette fonction doit renvoyer une liste contenant les coordonnées de la balle détectée ou la liste [None, None] si aucune balle n'est détectée. Cette fonction fera appel à la fonction distance_quad. 10/16 d) Écrire une fonction traj_balle qui prend en argument la liste seq_balle définie précédemment et la vitesse initiale vit_init (liste à 2 éléments). Cette fonction doit renvoyer la liste des "balles bonnes" présentes dans la zone de recherche : x0 , y0 , x1 , y1 , ..., xi , yi , ... . On ne traitera pas le cas où dans 2 images successives aucune balle ne se trouve dans la zone de recherche. Q12. Indiquer les limites ou défauts de l'algorithme étudié dans cette sous-partie. III.3 - Calcul de la position 3D de la balle par triangularisation (étape 4 ) L'objectif de cette sous-partie est de déterminer la position de la balle dans le repère global défini par rapport au terrain à partir de la position de la balle dans deux images de deux caméras différentes. Une fois que la configuration des caméras a été calibrée, la position de la balle peut être reconstruite dans le repère 3D par stéréo-triangulation. Cela consiste à déterminer la localisation du centre de la balle (noté M de coordonnées (x, y, z) dans le repère global) à partir de la connaissance de la position du centre de la balle dans les images obtenues par deux caméras. La position de la balle dépend de l'espacement e des caméras, également appelé "longueur de la ligne de base stéréo des caméras", de la distance focale f des caméras et de la disparité d qui est la distance entre les centres de la balle dans les images de chaque caméra, ainsi que des coordonnées du centre de la balle dans chacune des images (figure 6). Figure 6 ­ Position de la balle à l'instant i dans les images des caméras 1 et 2 11/16 Hypothèses - On s'intéressera ici à la triangularisation sur deux caméras : les caméras 1 et 2. - On suppose que la balle est bien détectée par les deux caméras et que les coordonnées relevées correspondent au centre de la balle. Les coordonnées du centre de la balle à l'instant i sont notées respectivement : P1 de coordonnées (x1 , y1 ) pour la caméra 1 et P2 de coordonnées (x2 , y2 ) pour la caméra 2 dans leurs repères respectifs. - On suppose que les deux caméras sont disposées à la même hauteur autour du terrain et que leur plan focal est identique. - On suppose que le temps est bien synchronisé sur les deux caméras. - On suppose que tous les paramètres de calibration des deux caméras sont connus (matrices intrinsèques et extrinsèques, distance focale, position...). On calcule les coordonnées du centre de la balle à l'instant i dans le repère de la caméra 1 (x1i, y1i, z1i) e e e grâce aux formules suivantes : x1i = x1 , y1i = y1 et z1i = f , avec d = x1 - x2 . Ces coordonnées d d d sont placées dans une liste telle que : pos1i=[x1i,y1i,z1i]. Q13. Écrire une fonction pos_loc(e,f,x1,x2,y1,y2) qui prend en argument les positions de la balle dans la caméra 1 (x1,y1) et la caméra 2 (x2,y2) à un instant i puis calcule et renvoie une liste des coordonnées (x1i, y1i, z1i) de la balle dans le repère local de la caméra 1 à un instant i pos1i=[x1i,y1i,z1i]. On calcule ensuite les coordonnées x, y et z dans le repère global à l'aide des matrices de passage de la caméra 1 par rapport au repère global. La position et l'orientation de la caméra 1 par rapport au repère global du système sont définies par trois matrices : T sa matrice de translation suivant #» x , #» y et #» #» #» z , R x sa matrice de rotation d'angle suivant x et Ry sa matrice de rotation d'angle suivant y . On obtient la même chose pour la caméra 2 en remplaçant les 1 par des 2. Ces matrices sont supposées connues à chaque instant (résultats de l'étape 2 non abordée). La figure 7 illustre la position de la caméra 1 à l'instant t. Figure 7 ­ Position de la caméra 1 à l'instant t t x1 T 1 = ty1 tz1 1 0 0 ; R x1 = 0 cos 1 - sin 1 0 sin 1 cos 1 cos 1 0 sin 1 0 1 0 et Ry1 = - sin 1 0 cos 1 . On rappelle que si R1 est la matrice de rotation entre les bases 0 et 1, alors R1 .U1 = U0 , avec U0 un 12/16 vecteur défini dans la base 0 et U1 un vecteur défini dans la base 1. Q14. Écrire une fonction pos_glo(pos1i,T1,Rx1,Ry1) qui prend en argument la liste pos1i et les matrices de translation et rotations T1, Rx1 et Ry1, qui calcule et renvoie une liste des coordonnées de la balle dans le repère global à l'instant i posgi=[xgi,ygi,zgi]. On pourra utiliser les fonctions de numpy pour effectuer les produits matrice-vecteur qui sont rappelées en annexe. III.4 - Assemblage des positions 3D (étape 5 ) L'objectif de cette partie est d'assembler les positions 3D de la balle dans le repère global obtenues à l'étape 4 . Les hypothèses sont les mêmes que dans la sous-partie III.3. Les coordonnées locales successives de la balle dans le repère de la caméra 1 sont stockées dans une liste coord_loc=[[x10,y10,z10], [x11,y11,z11],...,[x1i,y1i,z1i],...,[x1N,y1N,z1N]]. La trajectoire complète est obtenue en assemblant les positions successives de la balle dans la repère global. Q15. Écrire une fonction traj3D(coord_loc,T1,Rx1,Ry1) qui prend en argument la liste coord_loc et renvoie une liste de l'assemblage dans l'ordre chronologique des N coordonnées de la balle dans le repère global coord_glo=[[xg0,yg0,zg0],[xg1,yg1,zg1],..., [xgi,ygi,zgi],...,[xgN,ygN,zgN]]. On pourra utiliser des fonctions de la sous-partie III.3. III.5 - Détermination de l'impact de la balle avec le sol sur le terrain (étape 6 ) L'objectif de cette partie est de déterminer le point d'impact de la balle avec le sol afin de savoir si la balle est restée dans les limites du terrain ou non. Les hypothèses sont les mêmes que dans la sous-partie III.3. Cette partie de l'algorithme est primordiale, en effet, c'est à partir du résultat obtenu par cette partie de l'algorithme que l'arbitre rendra sa décision. Le système réel permet de déterminer la forme de l'impact entre la balle et le sol en fonction de la déformation de la balle. Afin de faciliter la résolution du problème, la déformation de la balle ne sera pas prise en compte. Hypothèses - On suppose que la balle est indéformable (et donc que le point d'impact est ponctuel) et de rayon 0,033 m. - La position du terrain (et donc les lignes) est parfaitement connue dans le repère global. - On considère dans notre cas que le point étudié se fait durant l'échange de balle entre les joueurs et non sur un service. - On suppose que le terrain est parfaitement plat. Les coordonnées du point d'impact de la balle avec le sol sont déterminées de la manière suivante : on vient détecter quand la coordonnée suivant y est égale à R et on relève les positions correspondantes suivant x et z. Si la position y comprise entre R et R+ ne se trouve dans aucune image, on détermine les coordonnées moyennes suivant x et z des deux images successives où il y a eu inversion du sens de déplacement de la balle selon y (descente, puis remontée). La donnée sera notée eps dans le programme. 13/16 Q16. Écrire une fonction det_impact(coord_glo,eps) qui prend en argument la liste coord_glo et le flottant eps puis calcule et renvoie la position de l'impact de la balle dans le repère global : une liste de dimension 2 impact=[x_imp,z_imp]. Le terrain comme présenté sur la figure 3 fait L = 24 m de long sur l = 11 m de large. On considère que le point origine du repère global est le point O. Q17. Écrire une fonction res_final(impact,L,l) qui prend en argument la liste impact, les dimensions du terrain L et l et qui renvoie IN si l'impact de la balle a eu lieu dans les limites du terrain et OUT sinon. III.6 - Reconstruction de la trajectoire 3D de la balle (étape 7 ) L'objectif de cette sous-partie est d'afficher la trajectoire 3D de la balle reconstruite à l'étape 5 pour que les spectateurs puissent la visualiser. Q18. À partir de la documentation sur le tracé 3D en Python, fournie en annexe, écrire une fonction vis_traj3D(coord_glo) qui prend en argument la liste coord_glo et permet d'afficher la trajectoire 3D de la balle. Partie IV - Exploitation des données fournies par le Hawk-eye L'objectif de cette partie est de montrer comment utiliser les informations fournies par le système Hawk-eye à des fins d'entraînement ou de visualisation à la télévision. Le système Hawk-eye est une mine d'informations pour analyser les statistiques des matchs de tennis. Les données sont ainsi utilisées par les chaînes de télévisions lors des retransmissions des matchs mais également par les entraîneurs après les matchs en vue d'adapter leurs programmes d'entraînement. Ces données d'un tournoi sont stockées dans une base de données constituée de deux tables. La table MATCHS contient les différents matchs d'un tournoi avec les attributs : - id : identifiant de type entier, clé primaire ; - nom : nom du match de type texte ; - numero : numéro du match dans la planification du tournoi ; - date : date où le match s'est déroulé ; - joueur1 : nom du premier joueur ; - joueur2 : nom du deuxième joueur (les joueurs 1 et 2 sont rangés par ordre alphabétique) ; - autres attributs non détaillés... La table POINTS contient des entités correspondant aux points joués lors d'un match. Elle contient les attributs : - id : identifiant de type entier, clé primaire ; - mid : identifiant du match correspondant à la définition de type entier ; - nombre : nombre d'échanges de type entier ; - fichier : nom du fichier image de la trajectoire (stockée) correspondant au point ; - autres attributs non détaillés... Q19. Rappeler la définition et l'intérêt d'une clé primaire. Q20. Écrire une requête SQL permettant d'afficher les identifiants des matchs joués par Federer, joueur pris pour exemple. 14/16 Q21. Écrire une requête SQL permettant d'afficher le nombre d'échanges maximum lors du match dont l'identifiant du match est mid=4. Q22. Écrire une requête SQL permettant de récupérer le nom des fichiers de toutes les images qui correspondent au match dont le nom est "Federer-Murray". FIN 15/16 ANNEXE Rappels des syntaxes en Python Remarque : sous Python, l'import du module numpy permet de réaliser des opérations pratiques sur les tableaux : from numpy import *. Les indices de ces tableaux commencent à 0. tableau à une dimension accéder à un élément ajouter un élément tableau à deux dimensions (matrice) : accéder à un élément extraire une portion de tableau (2 premières colonnes) tableau de 0 ( 2 lignes, 3 colonnes) dimension d'un tableau T de taille (i, j) produit matrice-vecteur (est identique pour le produit matrice-matrice) séquence équirépartie quelconque de 0 à 10.1 (exclus) par pas de 0.1 définir une chaîne de caractères taille d'une chaîne extraire des caractères Python L=[1,2,3] (liste) v=array([1,2,3]) (vecteur) v[0] renvoie 1 L.append(5) uniquement sur les listes M=array(([1,2,3],[3,4,5])) M[1,2] ou M[1][2] donne 5 M[:,0:2] zeros((2,3)) T.shape donne [i,j] a = array ([[1 ,2 ,3] ,[4 ,5 ,6] ,[7 ,8 ,9]]) b = array ([1 ,2 ,3]) p r i n t ( a . dot ( b ) ) >>> a r r a y ( [ 1 4 , 3 2 , 5 0 ] ) arange(0,10.1,0.1) mot="Python" len(mot) mot[2:7] for i in range (10) : print ( i ) boucle For définir une fonction qui possède un argument et renvoie 2 résultats tracé d'une courbe de deux listes de points x et y tracé d'une courbe de trois listes de points x, y et z d e f f ( param ) : a=param b=param param return a , b plot(x,y) gca(projection='3d').plot(x,y,z) xlabel(texte) ylabel(texte) title(texte) ajout d'un titre sur les axes d'une figure ajout d'un titre principal sur une figure 16/16 I M P R I M E R I E N A T I O N A L E ­ 18 1065 ­ D'après documents fournis i f ( i >3) : print ( i ) else : print ( " hello " ) condition If

Extrait du corrigé obtenu par reconnaissance optique des caractères


 CCP Informatique PSI 2018 -- Corrigé Ce corrigé est proposé par Virgile Andreani (ENS Ulm) ; il a été relu par Emma Kerinec (ENS Lyon) et Julien Dumont (professeur en CPGE). Ce sujet d'une vingtaine de questions traite du fonctionnement du système HawkEye, utilisé au tennis comme assistance à l'arbitrage sur la validité des impacts des balles sur le terrain. On passe en revue une grande partie du système, de l'identification automatique de la balle sur les images des caméras à la visualisation finale de sa trajectoire en 3D. · Une première partie très courte, proche du cours, demande de programmer un schéma d'Euler pour simuler la trajectoire de la balle à partir de conditions initiales. Cette simulation n'est pas suffisamment précise pour détecter la validité de l'impact d'une balle, de nombreux paramètres (météo, déformation de la balle...) n'étant pas pris en compte. · La deuxième partie remédie à ce problème en présentant le système Hawk-Eye. Après plusieurs questions portant sur l'architecture d'un ordinateur et la représentation des données en mémoire, on demande d'écrire quelques fonctions de traitement d'image pour repérer la position de la balle sur les films capturés par les caméras. Après la segmentation, le tracking est abordé et il faut implémenter un algorithme permettant de suivre la trajectoire de la balle au cours du temps. Puis de l'algèbre linéaire permet de reconstruire la position de la balle en 3D sur le terrain à partir de ses positions dans les champs de vision des caméras. Enfin, on détermine la position de l'impact de la balle sur le sol. · La dernière partie pose quatre questions faciles sur les bases de données. Le système étudié est complexe et intéressant. Cependant, pour pouvoir en aborder presque tous ses aspects, le sujet a dû les simplifier à l'extrême et la plupart des questions sont quasiment immédiates : aucune ne requiert de réelle réflexion, que ce soit sur l'algorithmique ou sur la programmation. C'est en conséquence un sujet accessible dès la première année, mais d'un intérêt limité pour les révisions. De plus, il contient plusieurs erreurs, y compris dans les sections de code à commenter, et n'encourage pas de bonnes pratiques de programmation en Python. Indications Partie II 1 Ne pas oublier d'exprimer en fonction des éléments de Y. Partie III 4 Multiplier la taille en mémoire d'un élément du tableau par le nombre d'éléments de celui-ci. 10 Indice : il y a une erreur dans la première boucle for, qui ne se comporte pas comme elle le devrait. 11 Attention, les coordonnées sont stockées « à plat » dans la liste liste_balle_i : c'est une liste 1D. Il faut donc faire un peu d'arithmétique pour y accéder. 12 Que se passerait-il si, par malchance, le signal le plus proche du centre de la zone ne correspondait pas à une balle ? 14 Il est facile de se tromper dans cette question. Commencer par écrire les formules de changement de base entre le repère d'origine et le repère translaté, puis celui translaté et tourné une fois, et enfin celui de la caméra (translaté et tourné deux fois). 16 La précision de l'énoncé (le point se situe durant un échange) est importante : elle signifie que le premier impact de la balle sur la terre n'est peut-être pas celui que l'on souhaite étudier. Une hypothèse raisonnable est que le dernier impact est celui qui nous intéresse. 17 Pour rappel, Python permet d'écrire de manière concise une double inégalité : a <= b <= c au lieu de a <= b and b <= c. Partie IV 20 Ne pas utiliser le champ nom, mais plutôt les deux champs joueur. II. Modélisation de la trajectoire de la balle 1 Il s'agit d'écrire la dérivée de Y en fonction de ses composantes. On a d'abord du d2 x 1 1 = 2 =- R2 air C1 V2 cos - air R3 C2 V sin dt dt 2m m dv d2 y 1 1 ainsi que = 2 = -g - R2 air C1 V2 sin + air R3 C2 V cos dt dt 2m m Pour fairedisparaître la variable , on remarque que u(t) = V cos et v(t) = V sin avec V = u2 + v 2 , soit p 1 1 du =- R2 air C1 u(t) u(t)2 + v(t)2 - air R3 C2 v(t) dt 2m m p dv 1 1 et = -g - R2 air C1 v(t) u(t)2 + v(t)2 + air R3 C2 u(t) dt 2m m Les dérivées des deux dernières composantes sont données par dx =u dt Enfin, et dy =v dt 1 1 2 3 2 + v2 - u - R C u R C v air 1 air 2 u 2m m 1 d v = -g - f 12mR2 air C1 v u2 + v 2 + air R3 C2 u m dt x u y v Il est impératif d'exprimer toutes les variables en termes de u, v, x et y : en particulier, il ne doit rester ni ni V dans l'expression finale, car on risquerait de les considérer comme constantes. 2 L'énoncé demande l'implémentation d'un schéma d'Euler explicite. Les conditions initiales doivent être définies dans la première colonne de Y0. Dans la boucle, on affecte à la colonne i le contenu de la colonne précédente, auquel on ajoute le produit de la dérivée de Y par l'intervalle de temps T/N. def euler(T, N, F, Y0): Y = zeros((len(Y0), N)) t = arange(0, T, T/N) Y[:, 0] = Y0 # Affectation des conditions # initiales à la première colonne for i in range(1, N): # Une étape du schéma d'Euler explicite Y[:, i] = Y[:, i-1] + T/N * F(t[i-1], Y[:, i-1]) return (t, Y) III. Tracking et reconstruction de la trajectoire de la balle 3 L'expression len(image1) retourne la longueur de la première dimension de l'expression image1. L'énoncé donnant les dimensions du tableau (n*m*3), on a len(image1) = 1024 De même, image1[12] est le tableau de dimension m*3 situé à l'indice 12 de l'expression image1, et image1[12][244] est le tableau de dimension 3 correspondant aux données de couleur, situé à l'indice 244 de image1[12]. On a donc len(image1[12][244]) = 3 Enfin, le tableau stocke des entiers, qui sont en Python du type int. Par suite, image1[12][244][2] est de type int. Cet entier représente la couleur 2, le bleu, du pixel de coordonnées (12, 224). Vu la question suivante, il y avait bien sûr une erreur dans le sujet : la question ne porte pas sur le type de len(image1[12][244][2]) mais bien sur celui de image1[12][244][2]. Le type de ces deux expressions est ici le même, mais seul le second est utile pour déterminer la taille occupée en mémoire par le tableau. 4 L'ensemble des valeurs entre 0 et 255 peut être représenté sur huit bits, soit un octet. Au minimum, la taille de ce tableau en mémoire vaut donc le nombre total d'éléments du tableau fois un octet, soit 2,4 Mo (ou 19 Mb, ou 2,3 Mio, ou 18 Mib). Par défaut, Python est loin d'être aussi efficace que cela ; il n'est d'ailleurs pas clair, étant donnée la formulation de la question, de savoir ce que le concepteur du sujet attendait exactement. Python représente les petits entiers, jusqu'à 260 , avec 32 octets. Cependant, il est difficile d'en tirer directement la taille du tableau complet, d'une part parce qu'il a besoin d'une mémoire non nulle pour représenter la structure de liste elle-même, d'autre part parce qu'il est capable d'effectuer des optimisations en « réutilisant » des objets, de sorte que [10, 11] est représenté sur 144 octets, alors que [10, 10] n'en nécessite que 112. En pratique, dans la mémoire de Python, l'image complète représente environ 82 Mo. On peut forcer une représentation efficace à l'aide de la bibliothèque numpy en utilisant le type uint8, prévu pour représenter des entiers positifs sur 8 bits : np.array(image, dtype='uint8'). Pour rappel, deux systèmes d'unités cohabitent pour désigner des tailles de données informatiques. On peut les baser tous les deux sur le bit, de symbole b, l'octet o, ou encore sur le byte B. Un bit est une unité d'information pouvant prendre seulement deux valeurs. Un octet est un ensemble de huit bits, et un byte est la plus petite quantité de bits qu'un programme peut lire ou écrire à la fois (généralement huit). Le premier système d'unités utilise les préfixes traditionnels du SI (k, M, G, etc.). Appliqués à l'octet noté o, on a conversions habituelles 103 o = 1000 o = 1 ko, 103 ko = 1 Mo, etc. Le second système, plus adapté en informatique avec un bit à deux valeurs, utilise des préfixes spécifiques aux puissances binaires : Ki (prononcé kibi), Mi (mébi), Gi (gibi), etc. Le facteur de conversion est alors une puissance de deux soit, avec l'octet, 210 o = 1024 o = 1 Kio, 210 Kio = 1 Mio, etc.