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.