CCINP Informatique PSI 2015

SESSION 2015

PSIIN07

EPREUVE SPECIFIQUE - FILIERE PSI

INFORMATIQUE
Durée : 3 heures

N.B. : le candidat attachera la plus grande importance à la clarté, à la 
précision et à la concision de
la rédaction. Si un candidat est amené à repérer ce qui peut lui sembler être 
une erreur d'énoncé, il le
signalera sur sa copie et devra poursuivre sa composition en expliquant les 
raisons des initiatives
qu'il a été amené à prendre.

Les calculatrices sont interdites
Le sujet comporte 12 pages dont :
­ 9 pages de texte de présentation et énoncé du sujet ;
­ 3 pages d'annexe.
Toute documentation autre que celle fournie est interdite.
REMARQUES PRELIMINAIRES
L'épreuve peut être traitée en langage Python ou langage Scilab. Il est demandé 
au candidat
de bien préciser sur sa copie le choix du langage et de rédiger l'ensemble de 
ses réponses dans
ce langage. Les syntaxes Python et Scilab sont rappelées en annexe V.1, page 10.
Les différents algorithmes doivent être rendus dans leur forme définitive sur 
la copie en respectant les éléments de syntaxe du langage choisi (les 
brouillons ne seront 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.

1/12

Robot Evolap - Suivi d'instrument chirurgical
I

Présentation

La laparoscopie est une technique chirurgicale mini-invasive de diagnostic et 
d'intervention
abdominale. Une ou plusieurs petites incisions sont réalisées dans la paroi 
abdominale pour
y insérer, au travers de canules appelées trocarts, de longs instruments 
chirurgicaux et un
endoscope rigide - appelé laparoscope - surmonté d'une caméra. Ce laparoscope 
est également
connecté à une source de lumière froide pour éclairer la cavité abdominale. Le 
robot EVOLAP
est un robot d'assistance à la chirurgie laparoscopique développé par 
l'Université Catholique
de Louvain (UCL). Il permet d'éviter à l'assistant chirurgical de porter le 
laparoscope pendant
les opérations et améliore le bon déroulement de celles-ci.
Objectif
L'objectif de l'étude proposée est de réaliser le programme de suivi de 
l'instrument
chirurgical par le robot EVOLAP, ce qui permet au chirurgien une vision optimale
de la zone d'intervention.

a - Principe de la laparoscopie

b - Robot Evolap avec simulateur abdominal

Figures 1 ­ Laparoscope manuel et robotisé.
Le robot possède deux moteurs qui permettent d'orienter le laparoscope selon 
deux angles
indépendants autour du point de passage de l'appareil.
Le programme de suivi d'un instrument chirurgical à partir de l'analyse d'image 
de la zone
de travail est constitué de plusieurs parties fondamentales :
­ définition du motif à suivre dans l'image,
­ acquisition d'une nouvelle image (issue du flux vidéo de la caméra),
­ recherche du motif dans la nouvelle image,
­ pilotage des moteurs pour aligner la caméra sur le motif détecté.
Dans tout le sujet, il sera supposé que les modules et bibliothèques sont déjà
importés dans le programme.

2/12

II

Définition du motif à suivre dans l'image

x
A partir du flux vidéo, un module permet d'extraire une
image en couleur (RGB) à chaque instant de l'analyse. On no(P x,P y)
tera image cette image. On définit sa largeur par la variable y
image_width et sa hauteur par la variable image_height déH
finies en pixels (ou points) de 800 × 600. Le point supérieur
gauche de l'image a pour coordonnées [0,0], le point inférieur
L
droit [799,599] en Python et respectivement (1,1) et (800,600)
en Scilab.
Pour définir le motif à suivre dans l'image, l'utilisateur doit spécifier les 
coordonnées (en
pixels) du point supérieur gauche (P x,P y) d'une fenêtre ainsi que sa largeur 
L et sa hauteur H.
La fonction demande_valeur(text) est utilisée pour récupérer une valeur entière 
demandée
à l'utilisateur. La vérification du type de donnée renvoyée par cette fonction 
est implantée dans
celle-ci. L'argument text est le message affiché à l'écran pour demander la 
valeur à l'utilisateur.
Q1. Définir une fonction demande_fenetre() qui utilise la fonction 
demande_valeur(text)
pour demander à l'utilisateur de définir la zone d'intérêt et qui renvoie une 
variable sous forme
de tableau contenant les 4 informations recueillies [Px,Py,L,H]. Dans le 
programme principal,
le retour de cette fonction sera nommé fenetre.
Q2. Définir une fonction verification_fenetre(image_width,image_height,fenetre) 
qui
vérifie que la fenêtre soit bien à l'intérieur de l'image et qui renvoie un 
booléen True si la fenêtre
est définie correctement et False sinon.
Plutôt que de spécifier manuellement la zone à suivre, l'utilisateur peut 
choisir un motif
correspondant à un instrument chirurgical donné à partir d'une base de données, 
qui permet
de connaître les vues d'un instrument particulier quelle que soit son 
orientation, sa taille...
Cette base de données est constituée de deux tables.
La table INSTRUMENTS contient les différents types
d'instruments avec les attributs :
­ id : identifiant de type entier, clé primaire,
­ name : nom de l'instrument de type texte,
­ serialnumber : numéro de série du produit,
­ purshasedate : date d'achat de l'instrument,
­ autres attributs non détaillés...

INSTRUMENTS
id
name
serialnumber
purshasedate
...

DEFINITIONS
id
mid
height
width
filename

La table DEFINITIONS contient des entités qui correspondent à la définition 
d'un instrument
pour une configuration donnée (nommée motif). Elle contient les attributs :
­ id : identifiant de type entier, clé primaire,
­ mid : identifiant de l'instrument correspondant à la définition de type 
entier,
­ height : hauteur en pixels du motif de type entier,
­ width : largeur en pixels du motif de type entier,
­ filename : nom du fichier image de type texte (stocké sur réseau) 
correspondant à ce motif.
A un instrument peut correspondre une ou plusieurs définitions.
Q3. Ecrire une requête SQL permettant de récupérer les noms de toutes les 
images qui correspondent à l'instrument dont le nom est "pince".

3/12

III

Pilotage des moteurs pour déplacer la caméra

La caméra envoie à chaque instant t une image en couleur. L'image à l'instant t 
+ dt est
appelée image courante tandis que l'image à l'instant t est appelée image 
précédente.
La partie suivante va permettre de comprendre comment extraire de l'image 
courante une
nouvelle fenêtre homothétique de la fenêtre définie dans l'image précédente.
La nouvelle fenêtre étant déterminée, on cherche ensuite à recentrer la caméra 
sur l'image,
c'est-à-dire que la fenêtre doit se trouver au centre de l'image. On suppose 
que, sur la première
image, la fenêtre autour de l'instrument est bien centrée.
Q4. Ecrire une fonction centre(fenetre) permettant de calculer le centre de la 
fenêtre définie
par fenetre=[Px,Py,L,H].
Cela permet de calculer la loi de mouvement à imposer aux moteurs du robot qui 
porte le
laparoscope afin de suivre la fenêtre d'étude.

IV

Recherche d'un motif dans une image

La difficulté de l'algorithme est de déterminer la fenêtre dans la nouvelle 
image à partir de
l'analyse du mouvement des pixels de la fenêtre entre l'ancienne image et la 
nouvelle.
Après un traitement de l'image courante (conversion en niveaux de gris), 
connaissant la fenêtre dans l'image précédente (figure 2a), on extrait tout 
d'abord de la fenêtre d'étude quelques
pixels d'intérêt répartis régulièrement (figure 2b). On recherche ensuite le 
déplacement moyen
de chacun de ces pixels d'une image à l'autre. Il est alors nécessaire de 
procéder à une élimination des pixels pour lesquels le déplacement obtenu est 
incohérent. Plusieurs vérifications sont
donc mises en place pour décider de l'élimination de ces pixels aberrants. Une 
fois le motif
identifié dans l'image courante, on estime le grossissement possible de ce 
motif et on renvoie la
nouvelle fenêtre d'étude qui englobe ces pixels (figure 2c).
Les parties suivantes vont permettre de spécifier les algorithmes et fonctions 
nécessaires à
la recherche du motif dans l'image courante.

fenêtre

a - Image instant t et fenêtre entourant le motif

b - Image instant t et fenêtre avec les pixels d'intérêt

c - Image instant t + dt et
fenêtre avec les pixels d'intérêt

Figures 2 ­ Illustrations de la recherche de la fenêtre définie dans une image 
dans une nouvelle
image.

4/12

IV.1

Traitement de l'image courante

L'image acquise par la caméra est une image en couleur constituée de trois 
couches (RGB).
Les données de l'image sont stockées dans un tableau à trois dimensions : la 
première dimension
correspond à la couleur (rouge, vert ou bleu, indice 0, 1 ou 2), la seconde 
correspond à la
coordonnée selon x et la troisième à la coordonnée selon y . Ainsi, les 
dimensions du tableau
sont : 3 × m × n où m = 800 et n = 600.
La valeur associée à chaque pixel est un entier compris entre 0 et 255.
Q5. Donner la quantité de mémoire nécessaire en octets pour stocker le tableau 
représentant
l'image émise par la caméra en justifiant le codage retenu pour un pixel d'une 
couche.
La première étape de l'algorithme de suivi d'image est de convertir l'image en 
couleur en
niveaux de gris. La méthode consiste à rechercher le maximum et le minimum pour 
chaque
pixel sur les trois couches, puis à faire la moyenne de ces maxima et minima et 
ainsi obtenir la
valeur du nouveau pixel en niveaux de gris.
On note imagecolor le tableau représentant une image en couleur.
Q6. Ecrire une fonction grayscale(imagecolor) qui renvoie une image en niveaux 
de gris
(qui sera notée image dans l'algorithme principal), sous forme de tableau à 
deux dimensions
de taille m × n contenant des valeurs entières comprises entre 0 et 255, en 
suivant l'algorithme
décrit ci-dessus. Remarque : il est possible d'utiliser les fonctions min et 
max internes au langage
choisi.

IV.2

Extraction des pixels d'intérêt de la fenêtre d'étude

Pour déterminer le déplacement du motif, il est nécessaire d'extraire les 
pixels de la fenêtre
définie initialement. Pour améliorer l'efficacité de la stratégie, on ne 
sélectionne pas tous les
pixels mais uniquement un petit nombre, nommés pixels d'intérêt, de cette 
fenêtre (figure 2b).
numM > 1 est le nombre de points souhaités horizontalement.
numN > 1 est le nombre de points souhaités verticalement.
Les points doivent être équirépartis sur la zone décrite par la
fenêtre.
Un point est défini par ses coordonnées x et y, respectivement
l'indice de la colonne et l'indice de la ligne, en prenant comme
origine le coin supérieur gauche de l'image, bord inclus.

PnumN+1
P1
P2
..
.

numN

numM
Q7. Ecrire une fonction construction_coordonnees_pts(fenetre,numM,numN) qui 
renvoie
un tableau de points noté pts=[P1x,P1y,P2x,P2y,...] dans l'algorithme principal 
(le parcours
des points se fait de haut en bas puis de la gauche vers la droite). On ne 
traitera pas les cas
pour lesquels numN ou numM sont égaux à 1. On rappelle que fenetre=[Px,Py,L,H].

IV.3

Recherche des pixels d'intérêt dans l'image courante

On note imgJ le tableau à deux dimensions permettant d'accéder aux valeurs des 
pixels
en niveau de gris de l'image courante (au temps t + dt) et imgI celui pour 
l'image précédente
(temps t).
On utilise la méthode de Lucas-Kanade pour trouver les pixels d'intérêt de 
l'image précédente dans l'image courante.
Cette méthode suppose que le déplacement d'un point de l'image entre deux 
instants consécutifs est petit et se fait à vitesse constante. Pour estimer ce 
déplacement, on considère une zone
de quelques pixels centrée autour du pixel d'intérêt étudié et on suppose que 
le déplacement est
5/12

le même pour tous les pixels de cette zone. La résolution de ce problème se 
fait par la méthode
des moindres carrés explicitée dans la suite du sujet.
IV.3.1

Définition de l'algorithme

Pour mettre en place la méthode de Lucas-Kanade, il est nécessaire de partir 
d'une définition
continue de l'image et de l'algorithme.
On note I(t) l'image en niveaux de gris à l'instant t et I(t + dt) l'image en 
niveaux de gris
obtenue à un instant t + dt. Pour repérer un point de l'image, on utilise la 
notation I(t)[P ] qui
désigne la valeur en niveaux de gris de l'image à l'instant t au point P de 
coordonnées [x,y].
Soit u un point de coordonnées [ux,uy] sur l'image I(t).
L'algorithme permet de trouver les coordonnées de ce point dans l'image I(t + 
dt) (notées
v = [vx,vy] = u + d) en supposant que la valeur du pixel ne change pas, 
c'est-à-dire :
I(t)[u] = I(t + dt)[v] (on parle de stationnarité de la fonctionnelle I(x,y,t)).
Le vecteur d = [dx = Vx dt, dy = Vy dt] représente le déplacement du pixel à la 
vitesse
constante V = [Vx ,Vy ]. Les variations dx, dy autour d'un point sont exprimées 
en pixels. En
pratique, le déplacement n'est que de quelques pixels.
Ainsi, étudier la stationnarité du pixel revient à résoudre le problème suivant 
:
Ix dx + Iy dy = -It dt
I(t)[u]
I(t)[u]
et Iy =
sont les dérivées spatiales (dérivées en un point de coordonx
y
I(t)[u]
nées u suivant les directions x ou y de l'image I(t)) et It =
est la dérivée temporelle
t
de l'image (dérivée en un point de coordonnée u entre l'image I(t) et I(t + 
dt)).
où Ix =

Q8. Proposer des approximations pour définir numériquement les termes Ix, Iy et 
It en fonction
de imgI, imgJ, ux, uy et dt. On ne traitera pas les cas où le point u est sur 
le bord de l'image.
Pour définir une dérivée numérique spatiale, on prendra des variations dx, dy 
égales à ±1 pixel.
On note Itdt le produit It par le pas de temps dt défini par le 
rafraîchissement des images
de la caméra. On définit la fonction calc_LK_terms(pixP,imgI,imgJ) qui permet 
de calculer
et de retourner les termes de l'équation de stationnarité, Ix,Iy,Itdt, définie 
précédemment
pour un pixel pixP donné :
Ix dx + Iy dy = -Itdt.
On suppose cette fonction connue ce qui permet de répondre à la suite du 
problème indépendamment de la spécification de la question précédente.
IV.3.2

Implantation et résolution

L'algorithme indique que la relation précédente est écrite pour quelques pixels 
dans un
voisinage proche d'un pixel d'intérêt P apparP
tenant au motif étudié (question Q7, page 5).
Patch de taille 5 pixels
Il est donc nécessaire de définir ce voisinage auautour du point P
tour du point P que l'on appellera patch. Ce
voisinage contiendra 5 × 5 points contigus dont le point central sera le point 
P . On fait l'hypothèse que le point P n'est pas près du bord et qu'il y a 
toujours suffisamment de pixels
disponibles autour du point P pour définir le patch.
6/12

Q9. Ecrire une fonction creation_patch(P,patch_size) où P=[Px,Py] est le pixel 
étudié et
patch_size=5 est le nombre de points choisis horizontalement et verticalement 
dans le voisinage
du point P . Cette fonction renverra un tableau de coordonnées 
patch=[P1x,P1y,P2x,P2y...]
classé du haut vers le bas et de gauche à droite comme à la question Q7, page 
5. On supposera
que la variable patch_size est impaire.
En écrivant l'équation de stationnarité pour tous les pixels du patch et en 
supposant
que le déplacement est le même que celui du point P , on obtient un système 
composé de
patch_size × patch_size équations à 2 inconnues (d = [dx,dy]). On doit ainsi 
résoudre un
système qui s'écrit sous la forme A.d = b.
Q10. Ecrire une fonction calc_Ab(imgI,imgJ,patch), utilisant la fonction 
calc_LK_terms,
qui renvoie un tableau de taille (patch_size × patch_size) × 2 (noté A dans la 
suite) et un
vecteur (noté b) de taille (patch_size × patch_size) × 1.
Le système A.d = b n'a pas de solution. On cherche cependant un déplacement d 
qui
minimise au sens des moindres carrés la norme quadratique de Ad - b. Ceci 
revient à résoudre
le système matriciel 2 × 2 : AT A.d = AT .b où AT représente la transposée de A.
Q11. Ecrire une fonction resoud_LK(A,b) qui renvoie les deux composantes dx et 
dy de d. On
supposera que la matrice AT A est inversible et on ne fera donc aucune 
vérification concernant
son inversibilité. Détailler la résolution sans utiliser de solveur interne au 
langage choisi en
séparant et en commentant correctement chaque partie de l'algorithme.
IV.3.3

Synthèse : algorithme de recherche de pixels déplacés

Les sous-fonctions définies dans les parties précédentes permettent de 
déterminer le déplacement des pixels d'intérêt de la fenêtre de l'image 
précédente imgI et ainsi de retrouver ces
pixels dans l'image courante imgJ.
On définit alors le tableau des pixels trouvés noté fpts dans l'image courante 
imgJ et stocké
de la même manière que le tableau pts défini à la question Q7, page 5.
Q12. Définir une fonction recherche_points(imgI,imgJ,pts) qui utilise les 
fonctions précédentes et qui renvoie un tableau de points qui correspondent aux 
pixels déplacés. La résolution
du système pouvant donner des valeurs non entières de pixels, on approchera les 
solutions obtenues par leur partie entière. On supposera de plus que cette 
résolution fournit toujours une
solution.
Q13. Expliquer, en quelques phrases, les limites de l'algorithme proposé en 
discutant des cas
qui pourraient ne pas fournir de solution.

IV.4

Vérification des points obtenus

Les points obtenus par résolution du système ne correspondent pas forcément à 
chaque pixel
déplacé. C'est pourquoi il est nécessaire de mettre en place une ou plusieurs 
vérifications pour
éliminer les points qui ne conviennent pas.
La première vérification consiste à s'assurer qu'il est possible de retrouver 
les points initiaux
de imgI en partant des points obtenus dans l'image courante imgJ par la même 
méthode. Par
exemple, P1 dans imgI donne P1n dans imgJ, qui donne P1nn dans imgI. Si P1nn 
est différent
de P1, alors il est éliminé, sinon il est conservé.

7/12

Q14. Ecrire la partie du programme principal qui permet d'obtenir un tableau de 
booléen (noté
statut dans le programme principal) de la taille du nombre de points 
représentant le motif.
Chaque case contient True si le point a été retrouvé et False sinon. On 
utilisera les variables
définies tout au long du sujet et la fonction recherche_points.
La deuxième vérification fait appel à la fonction suivante qui utilise les 
pixels sélectionnés
(points1) de l'image précédente et les pixels trouvés (points2) de l'image 
courante.
Définition Python
def c a l c u l 1 ( points1 , points2 ) :
r e t u r n s q r t ( ( p o i n t s 1 [ 0 : : 2 ] - p o i n t s 2 [ 0 : : 2 ] ) 
2+( p o i n t s 1 [ 1 : : 2 ] - p o i n t s 2 [ 1 : : 2 ] )   2 )

Définition Scilab
function c a l c u l 1 ( points1 , points2 )
r e t u r n s q r t ( ( p o i n t s 1 ( 1 : 2 : $ )-p o i n t s 2 ( 1 : 2 : $ ) 
) ^2+( p o i n t s 1 ( 2 : 2 : $ )-p o i n t s 2 ( 2 : 2 : $ ) ) ^2)
endfunction

Q15. Indiquer quelle opération mathématique est réalisée par cette fonction 
calcul1 et préciser
le type et la dimension de ce que renvoie la fonction.
Pour éliminer des points, on calcule la médiane des valeurs obtenues et on 
supprime les
points dont la valeur est trop éloignée de la médiane.
Q16. Ecrire une fonction mediane(a), basée sur un algorithme de tri de votre 
choix, qui renvoie
la valeur médiane du tableau de valeurs a. On suppose que les valeurs de a sont 
strictement
positives et que la longueur de a est impaire.
Q17. Nommer l'algorithme de tri utilisé et donner sa complexité dans le 
meilleur et le pire des
cas.
Q18. Ecrire une fonction verification_pts(pts,fpts,statut) qui renvoie un 
nouveau tableau de points (noté nouveaux_pts dans le programme principal) pour 
lesquels le premier
critère est vérifié et la valeur obtenue par le deuxième critère est inférieure 
ou égale à la médiane.
Il est possible d'ajouter un troisième critère pour plus de précision 
concernant cette détection. On peut par exemple calculer une corrélation 
croisée (CCORR) entre les images imgI et
imgJ sur des patchs autour de chaque point de la fenêtre d'étude. Des 
librairies permettent de
réaliser cette corrélation croisée normée. La documentation de la fonction 
correspondante est
détaillée dans l'annexe V.2.
Q19. En utilisant cette documentation, expliquer quelles commandes taper pour 
calculer cette
corrélation croisée normée pour chaque point. Préciser ce que renvoie la 
fonction. On utilisera
à nouveau la fonction creation_patch(P,patch_size).

8/12

IV.5

Définition de la nouvelle fenêtre

Le tableau des points trouvés dans l'image courante peut être inclus dans une 
nouvelle
fenêtre image de la fenêtre définie initialement. Celle-ci a subi une 
homothétie appelée facteur
de grossissement.
On donne en annexe V.3 la fonction determine_fenetre permettant de renvoyer la 
nouvelle
fenêtre dans l'image imgJ et le facteur de grossissement à partir des points 
valides trouvés dans
la nouvelle image. Cette fonction a été développée par une autre personne. Le 
développeur a
utilisé sa propre spécification des variables : c'est-à-dire que la façon de 
stocker les grandeurs
d'entrées et de sorties est différente de celle définie dans le programme 
principal et adoptée
depuis le début du sujet. On sait que bb0 correspond à la fenêtre dans l'image 
précédente, pt0
aux points dans l'image précédente et pt1 aux points dans l'image courante.
Q20. Préciser les variables qui ont été définies différemment et indiquer ce 
qui doit être modifié
afin que la fonction puisse être utilisée dans le programme principal. Il n'est 
pas demandé de
réécrire cette fonction.
Q21. Indiquer sur votre copie ce que font les parties de programmes entre les 
zones de commentaires en précisant le numéro du commentaire (com1 à com6). Des 
commentaires d'une à
deux lignes maximum sont attendus.
Fin de l'énoncé

9/12

V

Annexes

V.1

Rappels des syntaxes en Python et Scilab

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.
Remarque : sous Scilab, les indices des tableaux commencent à 1.
Python

Scilab

tableau à une dimension

L=[1,2,3] (liste)
v=array([1,2,3]) (vecteur)

v=[1, 2, 3] ou [1 2 3]

accéder à un élément

v[0] renvoie 1

v(1) renvoie 1

ajouter un élément

L.append(5)
uniquement sur les listes

v($+1) = 5

tableau à deux dimensions
M=array(([1,2,3],[3,4,5])) M=[1,2,3;3,4,5]
(matrice) :
accéder à un élément

M[1,2] ou M[1][2] donne 5

M(2,3) donne 5

extraire une portion de taM[:,0:2]
bleau (2 premières colonnes)

M(:,1:2)

tableau de 0 ( 2 lignes, 3 cozeros((2,3))
lonnes)

zeros(2,3)

dimension d'un tableau T de
T.shape donne [i,j]
taille (i,j)

length(T) donne (i,j)

séquence équirépartie quelconque de 0 à 10.1 (exclus) arange(0,10.1,0.1)
par pas de 0.1

[0:0.1:10]

définir une chaîne de caracmot="Python et Scilab"
tères

mot="Python et Scilab"

taille d'une chaîne

len(mot)

length(mot)

extraire des caractères

mot[2:7]

part(mot,[11:16])

boucle For

f o r i in range (10) :
print ( i )

f o r i =1:10
disp ( i ) ;
end

i f ( i >3) :
print ( i )
else
print (" hello ")

i f ( i >3) then
disp ( i )
else
disp (" hello ")
end

d e f f o n c t i o n ( param ) :
r e s=param
r e s 2=paramparam
return res1 , res2

f u n c t i o n [ r e s , r e s 2 ]= f o n c t i o n (
param )
r e s=param
r e s 2=paramparam
endfunction

condition If

définir une fonction qui possède un argument et renvoie
2 résultats

10/12

V.2

Documentation de la fonction match_template
Compares a template against overlapped image regions.
Python : result=cv2.matchTemplate(image, templ, method)
Scilab : result=matchTemplate(image, templ, method)

Parameters :
­ image : Image where the search is running. It must be 8-bit or 32-bit 
floating-point.
­ templ : Searched template. It must be not greater than the source image and 
have the same data
type. result : Map of comparison results. It must be single-channel 32-bit 
floating-point. If image
is W × H and templ is w × h , then result is (W - w + 1) × (H - h + 1).
­ method : Parameter specifying the comparison method (see below).
The function slides through image , compares the overlapped patches of size w × 
h against templ using
the specified method and stores the comparison results in result . Here are the 
formulae for the available
comparison methods (I denotes image, T template, R result). The summation is 
done over template
and/or the image patch : x = 0...w - 1, y  = 0...h - 1
· method=CV_TM_SQDIFF

R(x,y) =
(T (x ,y  ) - I(x + x ,y + y  ))2
x ,y 

· method=CV_TM_SQDIFF_NORMED

R(x,y) = 

,y  ) - I(x + x ,y + y  ))2

  2

 2
x ,y  T (x ,y ) ·
x ,y  I(x + x ,y + y )
x ,y  (T (x

· method=CV_TM_CCORR
R(x,y) =

(T (x ,y  ) · I(x + x ,y + y  ))

x ,y 

· method=CV_TM_CCORR_NORMED

R(x,y) = 

,y  ) · I(x + x ,y + y  ))

  2

 2
x ,y  T (x ,y ) ·
x ,y  I(x + x ,y + y )
x ,y  (T (x

· method=CV_TM_CCOEFF
R(x,y) =

(T  (x ,y  ) · I  (x + x ,y + y  ))

x ,y 

where
T  (x ,y  ) = T (x ,y  ) - 1/(w · h) ·

T (x ,y  )

I  (x + x ,y + y  ) = I(x + x ,y + y  ) - 1/(w · h) · x ,y I(x + x ,y + y  )

· method=CV_TM_CCOEFF_NORMED

R(x,y) = 

x ,y 

(x ,y  ) · I  (x + x ,y + y  ))

   2

 2
x ,y  T (x ,y ) ·
x ,y  I (x + x ,y + y )
x ,y  (T

After the function finishes the comparison, the best matches can be found as 
global minimums
(when CV_TM_SQDIFF was used) or maximums (when CV_TM_CCORR or CV_TM_CCOEFF was 
used) using the
minMaxLoc function. In case of a color image, template summation in the 
numerator and each sum in the
denominator is done over all of the channels and separate mean values are used 
for each channel. That is,
the function can take a color template and a color image. The result will still 
be a single-channel image,
which is easier to analyze.

11/12

V.3

Définition de la fonction determine_fenetre
Définition Python

def determine_fenetre ( bb0 , pt0 , pt1 ) :
nPts = len ( pt0 )
ofx = []
ofy = []
# A COMPLETER ( com1 )
for i in range ( nPts ) :
ofx . append ( pt1 [ i ][0] - pt0 [ i ][0])
ofy . append ( pt1 [ i ][1] - pt0 [ i ][1])
# A COMPLETER ( com2 )
dx = mediane ( ofx )
dy = mediane ( ofy )
# A COMPLETER ( com3 )
dist0 =[]
for i in range ( nPts ) :
for j in range ( i +1 , nPts ) :
temp0 = (( pt0 [ i ][0] - pt0 [ j ][0]) **2 + ( pt0 [ i ][1] - pt0 [ j ][1]) 
**2) **0.5
temp1 = (( pt1 [ i ][0] - pt1 [ j ][0]) **2 + ( pt1 [ i ][1] - pt1 [ j ][1]) 
**2) **0.5
dist0 . append ( temp1 / temp0 )
shift = mediane ( dist0 )
# A COMPLETER ( com4 )
s0 = 0.5 * ( shift - 1) * bb0 [2]
s1 = 0.5 * ( shift - 1) * bb0 [3]
# A COMPLETER ( com5 )
x1 = bb0 [0] - s0 + dx
y1 = bb0 [1] - s1 + dy
x2 = bb0 [2] + s0 + dx
y2 = bb0 [3] + s1 + dy
w = x2 - x1
h = y2 - y1
# A COMPLETER ( com6 )
bb1 = [ int ( x1 ) , int ( y1 ) , int ( w ) , int ( h ) ]
return [ bb1 , shift ]

12/12

I M P R I M E R I E N A T I O N A L E ­ 15 1323 ­ D'après documents fournis

Définition Scilab
function [ bb1 , shift ]= determine_fenetre ( bb0 , pt0 , pt1 )
nPts = length ( pt0 )
ofx = zeros ( nPts )
ofy = zeros ( nPts )
// A COMPLETER ( com1 )
for i = [1: nPts ]
ofx ( i ) = pt1 (i ,1) - pt0 (i ,1)
ofy ( i ) = pt1 (i ,2) - pt0 (i ,2)
end
// A COMPLETER ( com2 )
dx = mediane ( ofx )
dy = mediane ( ofy )
dist0 = zeros ( nPts )
// A COMPLETER ( com3 )
for i = [1: nPts ]
for j = [ i +1 , nPts ]
temp0 = (( pt0 (i ,1) - pt0 (j ,1) ) **2 + ( pt0 (i ,2) - pt0 (j ,2) ) ^2) ^0.5
temp1 = (( pt1 (i ,1) - pt1 (j ,1) ) **2 + ( pt1 (i ,2) - pt1 (j ,2) ) ^2) ^0.5
dist0 ( i ) = temp1 / temp0
end
end
shift = mediane ( dist0 )
// A COMPLETER ( com4 )
s0 = 0.5 * ( shift - 1) * bb0 (3)
s1 = 0.5 * ( shift - 1) * bb0 (4)
// A COMPLETER ( com5 )
x1 = bb0 (1) - s0 + dx
y1 = bb0 (2) - s1 + dy
x2 = bb0 (3) + s0 + dx
y2 = bb0 (4) + s1 + dy
w = x2 - x1
h = y2 - y1
// A COMPLETER ( com6 )
bb1 = [ int ( x1 ) , int ( y1 ) , int ( w ) , int ( h ) ]
endfunction