Agrégation informatique externe 2021, épreuve 2, option ingénierie informatiqueSujet et rapport du jury

AGREGATION
CONCOURS EXTERNE

INFORMATION AUX CANDIDATS

Ces codes doivent être reportés sur chacune des copies que vous remettrez.

Sommaire

• -Le sujet (pages 1 à 24)
• -Les documents techniques DT1 à DT4 (pages 25 à 32)
• -Les documents réponses DR1 à DR6 (pages 33 à 43)

Inspection de parois rocheuses

pour la sûreté du réseau ferroviaire

Présentation

Ces traitements aboutissent à une représentation 3D relativement fidèle de l'environnement étudié. Les experts ont ainsi accès à des informations précises et facilement exploitables informatiquement.

• -la lasergrammétrie terrestre ;
• -la lasergrammétrie aéroportée ;
• -la photogrammétrie.

Figure n°1 : Scanner-Lidar 2 axes de rotation et le modèle 3D d'une paroi (1 770102 points 3D, résolution en profondeur 2 cm)

Lasergrammétrie aéroportée:

Figure n°2 : Drone RiCOPTER et son scanner-Lidar

Photogrammétrie :

Figure n°3 : Modèle 3D d'une paroi rocheuse par photogrammétrie (30 paires d'images)

Logiciel d'inspection de parois rocheuses :

• -mesure des distances par déplacement de la souris ;
• -visualisation de la carte des profondeurs en 2D et 3D ;
• -extraction des familles de discontinuités ;
• -classification des plans de discontinuités.

Figure n°4 : Cas d'utilisation partiel du logiciel d'inspection de parois rocheuses

Figure n°5 : Principe de l'image solide (avec dab, distance du point 3D)

• -une couche C++ associée à l'interface homme-machine et aux entrées/sorties du type fichier texte et image ;
• -une couche de scripts réalisés dans le langage « R » orienté manipulation de données pour le traitement du nuage de points et des images.

Figure n°6 : Nuage de points 3D projetés dans l'image « IMG_3886.jpg » et console d'exécution des tâches logicielles

• -« img_3886_infosCam.txt » : informations caméra ;
• -« Carriere_ZoneEtude[2cm].asc » : nuage de points 3D.

Figure n°7 : Inspection de parois rocheuses : interaction entre couches logicielles et utilisateur

• -partie 1 : acquisition 3D par scanner-Lidar ;
• -partie 2 : calcul de l'image solide par lasergrammétrie ;
• -partie 3 : solution de photogrammétrie ;
• -partie 4 : analyse des images par segmentation.

Partie 1. Acquisition 3D par scanner-Lidar

Le déplacement horizontal du drone réalise un balayage perpendiculaire au balayage suivant la direction portée par le segment SW (Swath Width : largeur de bande), décrivant ainsi une matrice d'empreintes (« footprints »). Par la suite, l'hypothèse d'une répartition uniforme des empreintes est considérée.

• Q2. Déterminer avec les éléments du croquis ci-avant, l'expression de la largeur de bande SW en fonction de la hauteur H et de l'angle de champ de vision FOV. Déterminer la surface balayée A à vitesse v et à temps de vol ΔT donnés.
• Q3. Exprimer le nombre de lignes N_1 scannées en fonction du temps de vol ΔT et de la fréquence de balayage SR. Exprimer la vitesse angulaire Ω en fonction de la fréquence de balayage SR et de l'angle de champ de vision FOV. Donner l'expression du pas angulaire Δθ (angle décrit par le faisceau durant la période d'un pulse).
• Q4.Exprimer le nombre d'empreintes N_f lors d'un unique balayage. En déduire la densité de points d_p (nombre d'empreintes par m^2 ) et donner les expressions de l'espace inter-empreintes a et de l'espace interligne b dont la répartition est considérée uniforme.

• Q5. En considérant un balayage à fréquence donnée (SR = 200Hz) suivant des lignes parallèles à la hauteur de la paroi, un déplacement horizontal du drone et une distance D = 30m du drone par rapport à la paroi, déterminer l'angle de champ de vision, la fréquence PRR et la vitesse du drone afin d'obtenir une résolution spatiale de 2 cm.

• Q6. Calculer le volume de données en octets pour la campagne de mesures décrite à la question précédente pour un temps de vol ΔT = 20s.

Les calculs précédents ont été implémentés dans le langage Python selon la structure logicielle ci-dessous dans laquelle deux classes collaborent.

• Q7. Compléter le corps des méthodes de la classe CLidar (DR1) décrites ci-dessous :

• Q8. Compléter le corps des méthodes de la classe CDrone (DR1) décrites ci-dessous :

Partie 2. Calcul de l'image solide par lasergrammétrie

• -tous les rayons lumineux passent uniquement par le centre optique (O) sans distorsion ;
• -le plan de l'image non inversée est localisé à la distance focale f par rapport au centre optique représenté par le centre du repère caméra (O).

Figure n°8 : Construction de l'image d'une caméra

• Q
  16. Justifier les expressions exactes des coordonnées du point image données cidessous.
  u = s_x[(L_(cmos))/2 − f((R_(11)(x_p − d_x) + R_(12)(y_p − d_y) + R_(13)(z_p − d_z)))/((R_(31)(x_p − d_x) + R_(32)(y_p − d_y) + R_(33)(z_p − d_z)))]; v = s_y[(H_(cmos))/2 + f((R_(21)(x_p − d_x) + R_(22)(y_p − d_y) + R_(23)(z_p − d_z)))/((R_(31)(x_p − d_x) + R_(32)(y_p − d_y) + R_(33)(z_p − d_z)))]
  L'image solide (figure 5) permet de composer, dans une unique structure de données, les informations colorimétriques de chaque pixel d'une image (R, G, B) avec la distance dab entre un point 3D et le centre optique de la caméra.
  

  Figure n°9 : Distance dab
  Les coordonnées d'un point 3D sont issues de mesure du type scanner-Lidar.
  Le DT3 présente un extrait des fonctions de la bibliothèque Numpy et des fonctions de traitement des fichiers en Python.
  Le DT2 présente le fichier des informations d'un nuage de points ainsi que le fichier des paramètres de la caméra utilisée pour la capture de l'image associée.
• Q17. Sans utiliser la bibliothèque « csv », compléter la fonction read3dPointTextFile du programme Python (DR2) permettant de stocker les coordonnées homogènes des points 3d dans la variable tabNuage et la direction du plan dans la variable tabVecNorm.
• Q18. Compléter les fonctions matRotation et matProjection associées respectivement à la matrice de rotation globale et à la matrice de projection.
• Q19. Déduire du programme principal du DR2, la structure de données permettant de stocker le vecteur (u^′, v^′, w)^T de coordonnées homogènes (u, v, 1)^T et justifier son type et ses dimensions.

In [2]: lpixels_dab[0:10]
Out[2]:
[[1190, 694, 50.86, 0],
    [1191, 695, 50.858, 1],
    [1190, 696, 50.841, 2],
    [1191, 696, 50.822, 3],
    [1191, 693, 50.887, 4],
    [1192, 693, 50.869, 5],
    [1193, 695, 50.852, 6],
    [1193, 695, 50.833, 7],
    [1193, 696, 50.814, 8],
    [1196, 696, 50.813, 9]]

In [4]: lpixels_dab[0:10]
Out[4]:
[[1130, 49, 63.477, 299733],
    [1128, 49, 63.474, 299722],
    [1132, 49, 63.467, 325187],
    [1133, 49, 63.466, 299801],
    [1131, 48, 63.465, 325143],
    [1127, 48, 63.459, 325133],
    [1143, 47, 63.458, 324902],
    [1130, 49, 63.457, 299730],
    [1127, 50, 63.456, 299714],
    [1129, 50, 63.455, 299721]]

• Q22. Justifier ce choix et compléter dans le DR3 le programme du tri rapide (dans sa version récursive) dans le cas d'une liste simple à trier dans l'ordre décroissant.
• Q23. Compléter dans le DR3, la fonction de partition partition_ag dans le cas d'une liste composée des index de pixels, de la distance dab et de l'index de la liste 1_pixels_dab selon les valeurs décroissantes de la distance dab.

• Q24. Donner l'expression de k en fonction de u, v et L et écrire la fonction suppression_doublons(l_pixels_dab,H,L) permettant de retourner une nouvelle liste composée des éléments de l_pixels_dab sans doublon. La complexité en temps devra être au plus en O(n) et la taille de la nouvelle liste devra correspondre au nombre de points 3D. Au préalable du programme Python, un énoncé du principe de l'algorithme devra être rédigé.
• Q25. Compléter le programme principal avec l'appel des fonctions de tri et de suppression des doublons.

• -imSrc : variable permettant de stocker l'image RGB ;
  • -img : variable permettant de stocker l'image solide (figure 5).
• Q26. Préciser la taille et le type des données associées à ces variables en considérant les composantes de couleur de l'image source définies comme des réels simple précision. Ajouter les instructions permettant de remplir la variable img.
• Q27. Conclure sur les performances en déterminant les complexités en temps et en mémoire associées à la création de l'image solide dans le meilleur des cas.

Partie 3. Solution de photogrammétrie

La figure ci-dessous décrit un système stéréoscopique, équivalent à deux prises de vue consécutives depuis un drone. Ce système est composé de deux caméras calibrées (C1 et C2) fixées sur le même support permettant l'acquisition d'une paire d'images stéréo rectifiées (coplanaires).

• Q28. D'après la figure précédente, démontrer l'expression matricielle ci-dessous décrivant les coordonnées du point P.
  [X; Y; Z] = B/d[x_1; y_1; f]
• Q
  29. Déterminer la résolution spatiale ΔX et ΔY conformément aux contraintes matérielles décrites dans le tableau ci-après.

  B	10 m
  Z	30 m
  Résolution d'une caméra	7360 × 4912 pixels
  f	35 mm
  Taille capteur caméra	35.9 mm × 24 mm

• - L(k, j) où j est associé à l'index de colonne d'un pixel de C1 ;
• - R(k, i) où i est associé à l'index de colonne d'un pixel de C2.

• -soient L(j) et R(i), respectivement les chaînes d'entrée et de référence, de taille N et indexées de 0 à N − 1;
• -soit D(i, j) = |L(j) − R(i)|, la différence entre deux pixels mis en correspondance ;
• -le coût minimum g(i, j) pour mettre en correspondance les chaînes L(j) et R(i), est défini comme la somme de D(i, j) avec le minimum des coûts suivants :
• - g(i, j − 1), occlusion de pixel dans l'image de droite, équivalent à un déplacement horizontal (numéroté 1 dans la figure 12 ci-après) vers la cellule g(i, j);
• - g(i − 1, j − 1), correspondance entre pixels équivalent à un déplacement diagonal (numéroté 2 ) vers la cellule g(i, j);
• - g(i − 1, j), occlusion de pixel dans l'image de gauche équivalent à un déplacement vertical (numéroté 3) vers la cellule g(i, j);

• -pour le calcul de la première ligne de g(0, ), etdelapremièrecolonneg(, 0), les valeurs g(− 1, ), etg(, − 1), utilisées lors de l'opération « min » possèdent un coût maximum (v_(max) = 50) pour interdire ces possibilités ;
• -la valeur d'initialisation de g(0, 0) est égale à |D(0, 0)|.

Figure n^∘12 : Mouvements possibles vers la cellule g(i, j)

Algorithme d'appariement de points homologues
L, chaîne d'entrée,
R, chaîne de référence,
g(-1,.) et g(.,-1) possèdent un coût maximal
initialisation de g(0,0)
Pour j allant de 0 à N-1 faire
    Pour i allant de 0 à N-1 faire
        calcule D(i,j)
        evalue g(i,j)= D(i,j) + min(g(i,j-1), g(i-1,j-1), g(i-1,j))
        memorise l'argument choisi argmin(i,j)
    Fin pour
Fin pour

• Q32. Compléter la table des coûts g(i, j) (DR4) associée aux chaînes L et R et tracer en couleur le chemin qui minimise la fonction de coût. Préciser la résolution minimale de correspondance.
• Q33. Compléter le programme Python implémentant l'algorithme ci-dessus (DR4). Le tableau P permettra de stocker le type de déplacements ( 1,2 ou 3 ) vers la cellule g(i, j). Les fonctions amin et argmin de la bibliothèque Numpy (DT3) pourront être utilisées.

In [3]: P
Out[3]:
array([[0., 0., 0., 0., 0., 0.],
    [0., 2., 1., 1., 1., 1.],
    [0., 3., 2., 2., 2., 1.],
    [0., 3., 2., 2., 3., 2.],
    [0., 3., 2., 3., 3., 3.],
    [0., 3., 2., 3., 3., 3.]])

In [2]: d
Out[2]: [(2, 4), (2, 3), (2, 2)]

• Q34. Compléter le programme Python (DR4) permettant, à partir du tableau P, de remplir la structure de données d présentée ci-dessus.
• Q35. Déterminer la complexité en temps et en espace mémoire de l'algorithme d'appariement pour une paire d'images de dimensions égales.

• Q36. Comparer les performances de la technique de stéréoscopie avec la technique par lasergrammétrie en termes de plage de mesure, de résolution, de coût des traitements numériques et d'intégration dans une cible embarquée. Dresser un tableau synthétique comme ci-dessous en ajoutant les critères importants.

Partie 4. Analyse des images par segmentation

• Q41. Représenter l'allure des réponses impulsionnelles d'un DoG et du LoG, pour σ = 1 et k = 2. Évaluer l'influence de k.
• Q42.Définir une fonction masque2D(sigma,p)en Python qui calcule le masque normalisé associé à la fontion G de taille (2p + 1) × (2p + 1).
• Q43. À partir de la décomposition du filtre Gaussien en deux filtres 1D, montrer que le filtre Gaussien est un filtre séparable au sens de la convolution.
• Q44. Estimer le nombre d'opérations N_C pour un pixel pour une convolution 2D classique. Estimer le nombre d'opérations N_S en exploitant la séparabilité du filtre. En déduire le gain (rapport N_C/N_S ).

La fonction DoG est illustrée suivant le schéma ci-dessous :

• Q45. Écrire la fonction DoG en Python et les fonctions dont elle dépend (DR6) qui renvoie l'image de la différence (résultat à la figure 13). La séparabilité du filtre sera utilisée.

Figure n°13 : À gauche, image d'origine, à droite image du DoG(k = √2, σ = 1)

• Q46. En utilisant la fonction précédente L(x, y, σ) écrite en Python, compléter la fonction Python DoGN(Image, N, k, σ, p) du DR6 qui prend en entrée l'image à traiter, le nombre de gaussienne, la valeur de k, la valeur de σ et qui renvoie l'image filtrée constituée des pixels de valeur maximale (points d'intérêt) parmi les N DoG de l'octave 1.

Figure n°14 : Fonction DoGN sur N étages

• Q47. En utilisant la fonction de la question précédente, compléter la fonction de filtrage multirésolution, DoG_MR du DR6, qui reprend la structure du filtre de la figure 15 ciaprès. Cette fonction permettra de réaliser un filtrage multirésolution sur l'image d'entrée, en vue d'extraire les points d'intérêts.

Figure n°15 : Filtre pyramide DoG_MR multirésolution

Figure n°17 : RANSAC appliqué sur un contour linéaire. Comparaison à une régression linéaire

Figure n°18 : Exemple de contours segmentés par RANSAC

• Q48. En considérant, k : le nombre d'itérations (ou tirages), P : la probabilité que l'algorithme sélectionne n points valables sur k itérations, w : la probabilité de tirer un point valable à chaque itération, déterminer la relation lien k à P, w et n.
• Q49.En utilisant la fonction linear_model.RANSACRegressor (bibliothèque Scikitlearn DT3), écrire une fonction en Python qui estime les paramètres d'un segment de contour passé en argument. Les paramètres renvoyés seront les coefficients de la droite ainsi que son orientation 2D. Les paramètres estimés seront stockés dans un fichier « angle.csv ».
• Q
  50. Rappeler brièvement le principe du clustering. La classification des orientations des segments utilise l'algorithme K-means (bibliothèque Scikit-learn DT3). La labellisation est réalisée avec un a priori de 10 degrés en termes de résolution. Ce clustering sera appliqué sur le fichier « angle.csv » et renverra la classe du linéament. Écrire le programme Python associé à ce traitement en utilisant les bibliothèques ci-dessous.

  from sklearn import linear_model,
  datasets from sklearn.cluster import KMeans
  

Figure n°19 : À gauche : nuage de points 3D brut acquis par le Lidar. À droite : nuage de points segmenté par application de la transformée de Hough, une couleur par plan détecté - extraction de 407 plans [Thèse S.Slob 2010].

Q 54. Déterminer les paramètres d'orientation en azimut (θ) et élévation (φ) (voir figure ci-après) du plan P_i.

Figure n°20 : Exemple d'extraction des plans de discontinuité par le traitement des orientations à partir de l'image solide. Les F_i correspondent aux familles de plan de discontinuité, classées selon l'orientation du vecteur normal au plan

Document technique DT1 :

scanner-Lidar

• -la première assure l'émission d'une onde électromagnétique ;
• -la seconde assure la mesure de la durée de propagation (aller-retour) des échos multiples ainsi que la mesure de leur intensité respective.

Extrait Kashani 2015

Balayage :
Un dispositif de balayage du faisceau (miroir polygonal tournant) selon un seul axe de rotation permet d'acquérir plusieurs points (empreintes) situés sur une même ligne.

Caractéristiques du scanner-Lidar Riegl vux-uav :

Fichier de nuage de points :

Document technique DT2 : Extrait des fichiers de données