CCP Informatique PSI 2015

Thème de l'épreuve Robot Evolap – Suivi d'un instrument chirurgical
Principaux outils utilisés images, pivot de Gauss, tri
Mots clefs méthode de Lucas-Kanade, corrélation croisée, pixel

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 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

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


 CCP Informatique PSI 2015 -- Corrigé Ce corrigé est proposé par Guillaume Batog (Professeur en CPGE) ; il a été relu par Jean-Julien Fleck (Professeur en CPGE) et Julien Dumont (Professeur en CPGE). De nouvelles techniques chirurgicales, dites mini-invasives, permettent d'opérer un patient en faisant passer de longs instruments chirurgicaux et une caméra au travers de fines canules cylindriques traversant la peau. Afin d'aider le chirurgien au cours de l'opération, un robot pilote le déplacement de la caméra pour suivre le mouvement des instruments chirurgicaux. Le sujet propose de réaliser une partie du programme pour ce suivi automatique, fondé sur un traitement mathématique des images extraites du flux vidéo. · Les questions 1 à 6 sont une petite mise en jambe où l'on demande d'écrire de courts programmes qui ne sont pas utiles pour la suite. Les notions abordées sont très variées : expressions booléennes, requêtes SQL, tableaux à 3 dimensions, quantité de mémoire. On se familiarise avec la représentation d'une fenêtre rectangulaire d'une image et le codage en niveaux de gris. · Le coeur de l'algorithme est programmé dans les questions 7 à 13. Étant donné une fenêtre entourant un objet dans l'image I(t) à l'instant t, on souhaite calculer une nouvelle fenêtre entourant ce même objet dans l'image I(t + dt). Pour cela, on extrait des pixels d'intérêt dans I(t). On calcule le déplacement de chacun d'eux dans l'image I(t + dt) à partir des variations d'intensité spatiales et temporelle autour des pixels. Cette phase de modélisation est difficile à comprendre à cause de quelques sous-entendus dans l'énoncé. Toutefois, il est possible de traiter indépendamment chacune des questions si la démarche générale est comprise. · Le calcul des nouveaux pixels d'intérêt dans l'image I(t + dt) est heuristique. Les questions 14 à 19 proposent trois tests pour éliminer les nouveaux pixels qui ne conviennent pas. La dernière question utilise une fonction très générale dont la documentation est donnée en anglais en annexe. Réussir à faire le lien entre les structures manipulées dans le sujet et les spécifications de cette fonction suppose une compréhension en profondeur du sujet et du cours. · Les questions 20 et 21 étudient un code servant à calculer les dimensions d'une nouvelle fenêtre entourant la plupart des pixels d'intérêt dans la nouvelle image I(t + dt). On demande de modifier et commenter ce code pour pouvoir l'utiliser dans le programme principal. Cette épreuve évalue un large panel de compétences du programme d'informatique commune, dont certaines sont difficiles à mettre en oeuvre en temps limité. Elle comporte aussi des applications directes du cours : algorithme de tri, calculs de produits matriciels, méthode du pivot de Gauss. C'est pourquoi elle constitue un excellent support d'entraînement, notamment pour réviser le programme de première année. Indications 2 Il suffit de vérifier que les dimensions sont positives et que les pixels supérieur gauche et inférieur droit de la fenêtre se trouvent bien dans l'image. 6 Utiliser deux boucles for imbriquées pour traiter chacun des pixels de l'image. 7 Les points à extraire ont pour coordonnées (Px + i L, Py + j H) avec L (resp. H) le nombre de pixels pour passer d'une colonne (resp. ligne) des points à extraire à la suivante 8 Écrire les approximations au premier ordre de I(x + dx, y, t) et I(x - dx, y, t). Pour le calcul de Ix, prendre dx = 1. 9 Déterminer entre quelles valeurs se trouvent les abscisses x et les ordonnées y des pixels du patch. Utiliser deux boucles for imbriquées en x et y pour construire la liste patch. 10 La matrice A possède autant de lignes qu'il y a d'équations Ixdx + Iydy = -Itdt, c'est-à-dire une par pixel du patch. Elle possède 2 colonnes correspondant aux variables dx et dy. Attention : le pixel numéro k de la liste patch a pour coordonnées patch[2*k] et patch[2*k+1] (où le premier pixel est numéroté 0). 11 Pour calculer AT A et AT b, programmer des fonctions qui calculent respectivement la transposée et le produit de matrices générales. Résoudre le système 2 × 2 obtenu à l'aide de l'algorithme du pivot de Gauss. Il est inutile de programmer l'algorithme général vu en cours. 12 Pour chaque pixel d'intérêt de pts, appliquer successivement les fonctions des questions 9, 10 et 11 avec un patch de taille 5. On obtient le déplacement (dx, dy) du pixel d'intérêt. 15 Pour un tableau t, la notation t[0 : :2] (resp. t[1 : :2]) consiste à extraire toutes les cases d'indices pairs (resp. impairs) de t. 16 Utiliser n'importe quel algorithme de tri vu en cours. 19 Programmer une fonction qui construit une liste ssimg des valeurs img[x][y] correspondant à un patch d'une image img. Retourner plus précisément la sousimage [ssimg] de taille 1 × 2 , où est la taille du patch. Utiliser ensuite la fonction match_template avec les sous-images correspondant au patch de imgI autour de P et à celui de imgJ autour de Pn, où Pn est la nouvelle position de P. 20 Regarder de plus près la structure de pt0 et pt1. 21 Expliquer ce que calcule chaque morceau de code, sans entrer dans le détail de la façon d'obtenir le résultat. Robot Evolap ­ Suivi d'instrument chirurgical 1 On demande successivement 4 valeurs qu'on renvoie sous forme d'un tableau. def demande_fenetre(): Px = demande_valeur("Valeur Py = demande_valeur("Valeur L = demande_valeur("Valeur H = demande_valeur("Valeur return [Px,Py,L,H] de de de de Px Py L H = = = = ") ") ") ") 2 La fenêtre est définie correctement si et seulement si elle est non vide et ses coins en haut à gauche et en bas à droite se trouvent bien dans l'image. On exprime chacune de ces conditions à l'aide des variables booléennes nonvide, coinHG et coinBD respectivement. On retourne le résultat de la conjonction (and) de ces 3 variables. def verification_fenetre(image_width,image_height,fenetre): [Px,Py,L,H] = fenetre iw,ih = image_width, image_height # quelques raccourcis nonvide = ( L>0 and H>0 ) coinHG = ( Px >=0 and Py >=0 and Px =0 and Py+H>=0 and Px+L0 and H>0 ) coinHGbis = ( Px>=0 and Py>=0 ) coinBDbis = ( Px+L < image_width and Py+H < image_height ) return ( nonvide and coinHGbis and coinBDbis ) En reprenant le nom des variables du corrigé, remarquons que nonvide et coinHGbis impliquent que Px + L > 0 et Py + H > 0 donc il n'est pas nécessaire de réaliser ces tests dans coinBDbis. De même, nonvide et coinBDbis impliquent que Px < iw et Py < ih. 3 Grâce à l'égalité (via ON) des identifiants d'instruments id dans la table INSTRUMENTS et mid dans la table DEFINITIONS, on effectue une jointure (via JOIN) pour mettre en correspondance les enregistrements de ces deux tables pour un même instrument. Dans cette jointure, on sélectionne (via WHERE) les enregistrements correspondant aux pinces puis on extrait (via SELECT) la colonne d'attribut des noms de fichiers images. SELECT filename FROM DEFINITIONS JOIN INSTRUMENTS ON INSTRUMENTS.id = mid WHERE name = "pince"; Puisque l'attribut id apparaît dans les deux tables, on distingue les deux attributs id en les faisant précéder du nom de la table (INSTRUMENTS.id pour celui de la table INSTRUMENTS). 4 Le centre de la fenêtre se situe au milieu de la largeur et de la hauteur d'où def centre(fenetre): [Px,Py,L,H] = fenetre return ( Px+L//2, Py+H//2 ) Si les dimensions L = 2 + 1 et H = 2h + 1 sont impaires, alors le centre de la fenêtre se trouve en position (Px + , Py + h). On obtient et h par quotient d'une division euclidienne par 2, ce que permet l'opérateur // sur les variables de type int. Si l'une des dimensions H ou L est paire, le centre géométrique de la fenêtre ne correspond plus au centre d'un pixel de l'image. Toutefois, il se trouve sur le bord du pixel retourné par la fonction centre. H=4 · · · · · · · · · · · · × · · · · · · · · ×: centre geometrique pixel retourne par centre L=5 L'énoncé n'indique pas clairement si l'on doit renvoyer les coordonnées du centre géométrique, de type float, ou les coordonnées d'un pixel, de type int, comme proposé dans le corrigé. 5 Le tableau possède 3 × m × n = 3 × 800 × 600 = 1 440 000 valeurs. Chaque valeur est un entier compris entre 0 et 255. La représentation binaire d'une valeur possède au plus 8 chiffres 0 ou 1 car 28 = 256 donc on peut la stocker dans un octet. Finalement, Le tableau représentant l'image nécessite 1,44 millions d'octets de mémoire. Rappelons que 1 Ko = 1 024 octets et 1 Mo = 1 024 Ko. Ainsi, 1,44 millions d'octets correspond à environ 1,37 Mo. 6 Après avoir initialisé une image avec des valeurs nulles, deux boucles for imbriquées permettent de traiter successivement chacun des pixels de l'image. def grayscale(imagecolor): [c,l] = imagecolor.shape # récupération des dimensions image = zeros((c,l)) # initialisation de l'image # remplissage des valeurs de l'image, case par case for i in range(c): for j in range(l): # traitement du pixel de coordonnees (i,j) r = imagecolor[0][i][j] g = imagecolor[1][i][j] b = imagecolor[2][i][j] mini = min(min(r,g),b) # version où min et max ne maxi = max(max(r,g),b) # travaillent que sur 2 éléments image[i][j] = (mini+maxi)//2 return image La fonction zeros du module numpy, de spécification rappelée en annexe, n'est pas à connaître. Voici deux façons d'initialiser l'image à la main : image = [0]*m