Points d'intérêt

Cours

Comment décrire les points d'intérêt ?

• Descripteur de type patch (liste des intensités) autour du point d'intérêt. Mais un patch n'est pas robuste à la rotation, au changement d'échelle, d'illumination ou de point de vue, sauf si on l'impose :
• Rotation : tourner le patch dans l'axe d'orientation principale
• Échelle : trouver la bonne échelle grâce à la pyramide LoG et ramener le patch à une taille normalisée
• Illumination : normaliser le patch
• Point de vue : considérer que le patch a subi une transformation affine, trouver les orientations et transformer le patch

Descripteur à base d'histogrammes

Calculer l'histogramme des orientations des gradients d'intensités. Le pic de l'histogramme donne l'orientation principale. Ramener le patch vers l'orientation principale, compensation de l'orientation.

Appariement de points

On a les points d'intérêt et les descripteurs associés : comment les apparier ? Nous pouvons utiliser la méthode d'appariement des points. Soit un descripteur $f_1$ dans $I_1$, trouver le meilleur correspondant $f_2 \in I_2$.

• Définir la distance $d(f_1, f_2)$
• Tester tous les $f \in I_2$ (ou dans un voisinage) et sélectionner celui qui minimise $d$, en imposant éventuellement $d(f_1,f_2) \leq S$, $S$ un seuil.

Cependant, une bonne distance peut donner un mauvais appariement. Une autre approche (test du ratio de Lowe) consiste à :

• calculer $r = \dfrac{d(f_1,f_2)}{d(f_1, f_2')}$ où $f_2'$ est le second plus proche
• des valeurs de $r$ proches de 1 signifient des appariements ambigus, donc à rejeter ; on ne conserve que les appariements dont le ratio est faible (par exemple $r < 0{,}8$)

Estimation d'homographie avec RANSAC

Soit $p_2 \propto H p_1$ (égalité à un facteur près, en coordonnées homogènes), avec $H$ la matrice de transformation projective (homographie) : $p_1 = \begin{pmatrix} x_1 \\ y_1 \\ 1 \end{pmatrix} \; p_2 = \begin{pmatrix} x_2 \\ y_2 \\ 1 \end{pmatrix} \; H= \begin{pmatrix} H_1 & H_2 & H_3 \\ H_4 & H_5 & H_6 \\ H_7 & H_8 & H_9 \end{pmatrix}$

Utiliser RANSAC : choisir un nombre d'itérations $k$ ; tant que $k > 0$ :

• sélectionner aléatoirement 4 paires de points appariés (le minimum pour déterminer les 8 degrés de liberté de $H$)
• calculer la matrice de transformation $H_{curr}$ entre ces points
• construire l'ensemble des inliers, tels que $SSD(p_2, H_{curr}p_1) \leq S$
• si cet ensemble est plus grand que ceux obtenus précédemment, poser $H=H_{curr}$ et stocker les inliers
• décrémenter $k$

L'homographie ayant le plus d'inliers est la solution du problème ; elle est généralement réestimée à partir de tous ses inliers.

La transformée de Hough

• Soit $p = (x,y)$ : différentes droites $(y=mx + b)$ peuvent passer par $p$, ce qui équivaut à différents couples $(m,b)$. En pratique, on utilise la paramétrisation $(\rho, \theta)$, qui évite les pentes infinies.
• La transformée de Hough permet de trouver les droites qui passent par le plus grand nombre de points possible.

L'algorithme de Hough est le suivant : initialiser l'accumulateur $H$ à zéro, puis :

• pour tout point de contour $p = (x,y)$ dans $I$
  • pour tout $\theta \in [\theta_{min}, \theta_{max}]$, calculer $\rho = x.\cos(\theta) + y.\sin(\theta)$ et $H(\rho, \theta) = H(\rho, \theta) + 1$
• Trouver les $(\rho, \theta)$ où $H(\rho, \theta)$ est un maximum local
• La ligne détectée est donnée par $\rho = x.\cos(\theta) + y.\sin(\theta)$

Détecteur de Harris

On mesure la variation d'intensité provoquée par un petit déplacement $(u,v)$ d'une fenêtre $P$ : $E(u,v) = \sum \limits_{x,y \in P} w(x,y)(I(x+u,y+v) - I(x,y))^2 \approx \sum \limits_{x,y \in P} w(x,y)(u.I_x + v.I_y)^2 = \begin{pmatrix} u & v \end{pmatrix} M \begin{pmatrix} u \\ v \end{pmatrix}$ avec $M = \sum \limits_{x,y \in P} w(x,y) \begin{pmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{pmatrix}$

$M$ est symétrique, donc diagonalisable dans une base orthonormée de vecteurs propres :

$M = \sum w \begin{pmatrix} I^2_x & I_x I_y \\ I_x I_y & I^2_y \end{pmatrix} = \begin{pmatrix} A & B \\ B & C \end{pmatrix} \rightarrow \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix}$

• Les valeurs propres $\lambda_1$ et $\lambda_2$ donnent l'amplitude des variations d'intensité principales
• Les vecteurs propres donnent les directions de ces variations principales
• Coefficient $R$ de Harris $R = \lambda_1\lambda_2 - k(\lambda_1 + \lambda_2)^2 = \det(M) - k(\operatorname{trace}(M))^2$, avec $k \in [0{,}04 ; 0{,}15]$
• Interprétation de $R$ :
  • $R$ grand et positif (deux valeurs propres grandes) : au voisinage d'un coin
  • $R < 0$ (une valeur propre grande, l'autre petite) : au voisinage d'un contour
  • $|R|$ petit (deux valeurs propres petites) : dans une zone homogène
• Harris est robuste à la rotation, mais pas au changement d'échelle

Mise en pratique

panorama <ims-name-1> <ims-name-2>

Écrire le programme panorama.cpp

• ce programme permet de charger deux images données en paramètre <ims-name-1> et <ims-name-2>
• les images sources sont en couleur mais la plupart des traitements se font en niveaux de gris
• le programme permet de réaliser un panorama à partir des 2 images sources
• le programme affiche les étapes intermédiaires
• les étapes sont les suivantes :
  • détecter les points d'intérêt avec les descripteurs SURF, afficher les descripteurs
  • appariement des points d'intérêts, via une méthode "brute force" et déterminer les bons appariements, par exemple via un seuillage. Afficher les appariements
  • estimer l'homographie $H$ via RANSAC, afficher l'image déformée via l'estimation
  • construire et afficher le panorama final
• regarder la documentation d'OpenCV sur le module features2d
• certaines classes et fonctions peuvent être utiles
• il peut être nécessaire d'inclure des éléments du module nonfree d'OpenCV (SURF est breveté et se trouve dans xfeatures2d)

hough-lines <ims-name> <th-mag>

Écrire le programme hough-lines.cpp

• ce programme permet de charger une image donnée en paramètre <ims-name>
• l'image est considérée en niveaux de gris (représentant les contours d'une image)
• le programme permet de mettre en œuvre la transformée de Hough
• le paramètre <th-mag> permet de seuiller les valeurs de l'image en entrée et de ne pas considérer tous les pixels comme étant des pixels de contour dans le calcul de la transformée
• le programme affiche les étapes intermédiaires : l'accumulateur de Hough, les lignes détectées, l'image finale
• afin de ne pas considérer toutes les lignes détectées, on pourra trouver un moyen de seuiller l'accumulateur de Hough afin d'obtenir les maxima locaux de l'accumulateur