VPOA: Detection et localisation

Lien de la note Hackmd

Introduction

Qu’est-ce que la vision ?

• Percevoir le monde
  • Compose d’objets
  • Structure en 3D
  • Efficacement interprete par l’Homme
• Receuil d’information
  • Ensemble de points
  • Information sur la lumiere
  • Quantite et contenu spectral
• Representation du monde reel
  • Les objets n’existent pas sur la retine
  • Processus visuel d’interpretation

Vision humaine

• Extremement complexe
• Active de nombreuses zones du cerveau
• Possede des capacites nombreuses et variees

Vision par ordinateur

• Bio inspiree ou non
• Production d’un modele algorithmique fonctionnellement similaire aux capacites du cerveau humain
• Reprosudit seulement un sous-ensemble de capacites

Quelques termes

Traitement d’images:

• manipulation dont l’entree et la sortie sont des images
• Aide l’humain ou la machine a examiner des images

Analyse d’images: analyse ou l’entree est une image mais la sortie est une information

TODO

Processus d’integration dans un systeme

Objectifs de la seance

• Trouver/extraire dans l’image des informations pertinentes pour TODO

Detection Deep-learning

On a entraine le modele a detecter des voitures mais ca ne reconnais que l’avant des camions

Detection et tracking

Geometrie projective

Coordonnees homogenes

Systeme de coordonnees pour la geometrie projective

Passer des coordonnees cartesiennes aux coordonnees homogenes:

\[\begin{bmatrix} x\\ y \end{bmatrix} \Rightarrow \begin{bmatrix} x\\ y\\ 1 \end{bmatrix}\]

Passer des coordonnees homogenes aux coordonnees cartesiennes:

\[\begin{bmatrix} u\\ v\\ w \end{bmatrix}= \begin{bmatrix} u / w\\ v / w\\ 1 \end{bmatrix} \Rightarrow \begin{bmatrix} u / w\\ v /w \end{bmatrix} = \begin{bmatrix} x\\ y \end{bmatrix}\]

Propriete homogene: $\bar x\sim\lambda \bar x, \forall \lambda\in\mathbb R, \lambda \neq =0$

Point a l’infini:

\[\bar x_{inf} = \begin{bmatrix}x \\ y \\0 \end{bmatrix}\]

Modele du plan projectif

Le plan projectif $P^2$ represente l’espace 3D sur un plan

Intrepretation geometrique de l’homographie

Homographies

Estimation d’homographie

Estimation par Direct Linear Transform

• Necessite au moins 4 points pour obtenir une solution exacte (2 equations par point et 8 inconnues)
• Etant donne $n\ge 4$, correspondances de points 2D, determiner $H$ tel que $\bar x_i’=H\bar x_i$

Algorithme:

• Pour chaque correspondance $\bar x_i\leftrightarrow \bar x_i’$ pour claculer $A_i$
• Assembler les matrices $A_i$ en une matrice $9\times 9$: $A$
• Calculer le SVD de $A$: $U\Sigma V$
• Solution pour $h$: derniere colonne de $V$
• Determiner $H$ a partir de $h$

Homographie et plan 3D

Le passage de n’importe quel plan vers n’importe quel autre plan (y compris le plan image) est une homographie

Extraction de caracteristiques locales

Representation d’une image

$I(x, y)$: valeur d’un pixel

• Dans $\mathbb R$ en monochrome
• Dans $\mathbb R^3$ en couleurs

Variations

• De luminosite globale: $I(x,y)\to I(x,y)+\alpha$
• De contraste: $I(x,y)\to\lambda I(x,y)$
• Par translation

Comparaison de points

Trouver le point le plus similaire

Stereo-vision: on suppose que les points similaires sont sur la meme ligne

Comment trouver des points facilement identifiables ?

Gradients Contours Etc

Kernel

Aussi appele noyau ou masque ou matrice de convolution

• Permet d’appliquer une operation a l’image
• Convolution:

Gradient

Va nous permettre d’obtenir une caracteristique de variabilite autour d’un point

En 1D:

En 2D: Filtre de Sobel

Laplacien

Detection de contours

Detection de coins

Zones ou le gradient varie dans plusieurs directions

Detecteur de Harris:

Changement d’echelle

Comment reconnaitre un point apres un changement d’echelle ?

Avec des descripteurs !

Descripteur

• Moyen de decrire une zone locale de l’image
• Les “features” sont associees a des points localement distincts dans l’image
• Les descripteurs sont la signature de ces points

Differences de Gaussiennes

Detection de blobs par differences de Gaussiennes:

On soustrait l’image floutee a l’image normale

Invariance par changement d’echelle pour les differences de Gaussiennes:

Descripteur SIFT

Scale Invariant Feature Transform

Detection de blobs par la methode des differences de gaussienne

Rotation

Comment reconnaitre un point apres une rotation ?

Descripteur SIFT

Histogramme d’orientations du gradient

• Decoupage en $4\times 4$ fenetres
• Histogramme sur 8 directions

Resume:

• Identification/Matching des keypoints

Autres descripteurs

• MSER (Maximally Stabel Extremal Regions)
• SURF (Speeded Up Robust Features)
• ORB (Oriented FAST and Rotated BRIEF)
  • SIFT et SURF sont brevetes
  • OpenCV a invente ORB comme alternative open-source et gratuite
• BRIEF
• FAST
• KAZE
• etc

Extraction de caracteristiques locales

Comment valoriser l’information ?

• Reconaissance/detection d’objets
• Estimation de la pose/localisation
  • De la projection d’objets 3D sur le plan Image
  • D’objets 3D dans le monde
  • De la camera dans le monde
• Estimation du mouvement

Reconaissance d’objets

Objectifs:

• Detection d’instances d’objets par points d’interet
  • Transformee de Hough
  • RANSAC
• Detection de categories d’objets
  • Sac de mots visuels

Transformee de Hough

A l’origine, detection de lignes droites:

• Chaque point votre pour “toutes” les lignes qui passent par lui
• Les votes sont accumules
• Un maximum local corresponds a des lignes candidates

Possible probleme: trouver le maximum vrai

• Mean shift
• Gaussian convolution
• …

Transformee de Hough generalisee

• Contour/forme arbitraire
  • Choix d’un point de reference our le contour (e.g. le centre)
  • Pour chaque point du contour, se rappeler de sa position par rapport au point de reference
  • Calcul de l’angle

RANSAC

Cas de lignes

• Choix aleatoire de droites
• Vote base sur le nombre de points proches de la ligne
• todo

Amelioration

• Elimination de outliers par RANSAC
• Amelioration de l’estimation de RANSAC TODO

Comparaison

Reconnaissance d’objets 3D

Base sur la detection de features

• 3 features minimum sont necessaires pour la reconnaissance

Reconnaissance d’objet 3D base sur la detection d’un modele 3D connu

Mots visuels

Principe: extraction de features locales a partir d’un certain nombre d’images

• Cartographie des descripteurs vers de mots visuels qui quantifient l’espace des features
• Le centre des clusters definissent les prototypes de mots

• Determination de quel mot doit etre assigne a chaque nouvelle region de l’image en trouvant le centre du cluster le plus proche

Exemple

Chaque groupe de patch correspond a un meme mot visuel

• Resumer une image entiere a partir de sa distribution de presence de mots
• Analogue a un sac de mots souvent utilise pour les documents de texte

Creation d’un vocabulaire visuel:

• Repertorier un ensemble de mots visuels (~ dictionnaire)
• Differentes strategies
  • Apprentissage supervise
  • Deep learning
  • etc

Strategies d’echantillonnage:

Arbre de vocabulaire:

• Remplissage:

Probleme:

• certains mots visuels sont discriminants
• D’autres apparaissent dans de nombreuses images

Calcul d’un poids pour chaque mot visuel

• Le poid correspond a la quantite d’info esperee
• Normalisation des histogrammes en fonction de ce poids

Estimation du mouvement

Objectifs

• Detection/ Estimation du mouvement dans la scene
  • Du au mouvement de la cmaera
  • Mouvement des objets
• Perception du mouvement apparent
  • Champs des vecteurs de deplacement
  • Flux optique

Flux optique

Difficultes de l’estimation du flux optique

• Ambiguites

• Premiere image: deplacement de drone, champ de vecteurs = deplacement des pixels
• Si on aune voiture qui se rapproche de nous, on peut segementer la voiture du reste de l’image a partir de champs de vecteurs

Interpretation du flux:

Vitesse:

• La camera se deplace a une vitesse $(X’, Y’, Z’)$ par rapport a la scene
• Si on derive les equations de perspective on a donc:

Interpretation du flux

Translation pure selon $X$ (ou $Y$)

Translation pure selon $Z$:

Cas general:

• Donne la direction du deplacement
• Mouvement $(X’, Y’, Z’)$
• Soit $[X_0, Y_0, Z_0]^T$ un point de la scene, apres un temps $t$, il est projete sur l’image au point $[u_t, v_t]^t$ avec:

Temps avant collision:

• Mesure de la taille d’‘un element $\lambda = f\frac{\Lambda}{z}$

Bundle adjustment

• Nous avons pour l’instant uniquement utilise des paires d’image pour obtenir une information de profondeur
• Dans le cas general, il est possible d’utiliser $N\gt 2$ images/cameras

Le Bundle (block) adjustment ou ajustement de faisceaux en bloc, est une methode de resolution au sens des moindres carres les coordonnees 3D des points et aligner les images

Plusieurs images sont corrigees “en bloc”

Principe:

• Demarrer avec une approximation initiale
• Projeter les points 3D sur les plans images des cameras
• Comparaison avec la mesure
• Ajustement pour minimiser l’erreur

Le BA est une approche non-lineaire de resolution par moindres carres:

• $\bar x_{ij} + \hat e_{x_{ij}} = \lambda_{ij}P_{ij}\bar X_i$
• Avec $\hat e_{x_{ij}}$ l’erreur de mesure du point $\bar X_i$
• $i l’indice du point, $j$ l’indice de la camera

Elimination du facteur d’echelle:

• $\bar x_{ij} + \hat e_{x_{ij}} = \frac{P_{1:2{ij}}\bar X_i}{P{3_{ij}}\bar X_i}$
• Resolution par SVD

Odometrie Visuelle

Estimation du mouvement de la camera par rapport au monde

Necessaire a de nombreuses applications

• Pas de GPS
  • Genre sur Mars
• IMU et/ou odometrie des roues insuffisants
  • On va mettre des encodeurs sur les roues et lire de combien s’est deplace la roue

Odometrie:

• Estimation du mouvement base sur le modele cinematique
• Extansion a la vision

Triangulation

• Permet de connaitre la position 3D d’un point

Principe:

• Trouver des correspondances de points entre 2 images successives: utilisation de descripteurs
• Si le monde est statique et les points bien apparies alors on peut estimer la transformation $(R,t)$ a partir des parametres extrinseque
• Probleme de minimisation de l’erreur de reprojection
  • Necessite d’une bonne calibration

Peu robuste aux rotations pures

• On compense ave l’IMU et l’odometrie des roues

Pseudo code:

Capturer l'image I_k
Calculer les correspondannce entre I_k-1 et I_k
Calcul de la matrice essentielle E et que p^TEp' = 0
Decomposition de E en R_k et t_k par SVD
Calcul du modele 3D (coordonnees des points de correspondance)
Redimensionnement de t_k pour prendre en compte l'echelle
    Attention ! p^TEp' = 0 <=> lambda p^TEp'=0
k = k + 1

SLAM

Simultaneous Localization and Mapping

• Si une carte est fournie, possibilite de se localiser dans cette carte uniquement
• Si une position est fournie, possibilite de creer une carte de l’environnement
• Le SLAM est l’estimation conjointe d’une carte de l’environnement et de la position de la camera dans cette carte
• Necessaire des qu’un robot doit explorer un environnement totalement ou partiellement inconnu
• Amelioration de l’odometrie visuelle
• On sauvegarde les coordonnees des points 3D extraits et de leurs caracteristiques locales
• Creation d’une carte de features 3D

3 categories principales de methodes pour l’estimation de l’etat:

• Extended Kalman Filter
• Particle Filter
• Least Squares => Graph-based SLAM

Graph-based SLAM

• Utilisation d’un graphe pour representer les variables et les relations entre ces variables
• Pose Graph: contient uniquement les positions
• Factor Graph: contient des facteurs reliant les differentes variables

Pose Graph:

• Chaque noeud represente une pose
• Les liaisons entre ces noeuds contiennent leur relation spatiale
• L’optimisation essaye de trouver la position optimale d’un noeud qui minimise l’erreur introduite dans les liaisons

Quels sont les avantages ?

• Meilleure estimation des coordonnees 3D des points/features
• Fermeture de boucles (Loop-closure)
• Plus robuste face aux rotations pures