chap5.tex 9.77 KB
Newer Older
nanored's avatar
nanored committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
\chapter{Détection et description de zones d'intérêt}

\myminitoc

\paragraph{Motivations}
Pour calculer les panoramas et les matrices fondamentales, nous avons eu besoin de points d'intérêts à matcher entre des paires d'images. Pointer les points à la main prend beaucoup de temps et n'est pas non plus une méthode très précise. C'est pourquoi on aimerait bien avoir des techniques pour trouver automatiquement des points saillant dans une image. Cela va amener d'autres thématiques comme la description de ces points saillants pour ensuite chercher des points similaires dans d'autres images. Ou encore la vérification de la consistance géométrique pour des objets rigides ou déformables.

Une des applications est de pouvoir retrouver du contenu (comme un monument) dans une base de données d'images. Les difficultés résident dans les changement de points de vu, de luminosité, de réflexion sur des surfaces réfléchissantes, de paramètres de caméra, de saison ou encore d'occlusion ...

\sect{Filtres d'images}

\paragraph{Rappels}
Les slides contiennent des rappels sur les produits de convolutions et la FFT. En particulier le fait que tout opérateur linéaire et stationnaire peut être exprimé comme un produit de convolution. Puis petite revu des filtres classiques. Je vais juste donner ici ce qu'est la corrélation :
$$ (f \otimes g)(x) = \int_{-\infty}^{+\infty} f(u) g(x+u) du = \int_{-\infty}^{+\infty} f(u-x)g(u) du $$
Il faut faire attention au fait que l'on perd la commutativité avec la corrélation bien que la linéarité, l'associativité et l'invariance par translation soit conservé.
\begin{center}
	\begin{tikzpicture}
		\node[left] at (-0.2, 2.2) {Convolution};
		\draw[orange, thick] (1.6, 2) -- (1.6, 2.24);
		\fill[orange, opacity=0.7] (1.05, 0.56) -- (1.05, 0.76) -- (1.25, 0.96) -- (1.25, 0.56);
		\draw[greenTikz, thick] (2, 2) -- (2, 2.32);
		\fill[greenTikz, opacity=0.7] (1.8, -0.14) -- (2.2, 0.26) -- (2.2, -0.14);
		\draw[purple, thick] (2.4, 2) -- (2.4, 2.08);
		\fill[purple, opacity=0.7] (2.75, 0.56) -- (2.95, 0.76) -- (2.95, 0.56);
		
		
		\draw[blue, ultra thick] (0, 4) -- node[above] {$f$} (1.6, 4) -- (1.6, 4.8) -- (2.4, 4.8) -- (2.4, 4) -- (4, 4);
		\draw[red, ultra thick] (0, 3) -- node[above] {$g$} (1.6, 3) -- (1.6, 3.8) -- (2.4, 3) -- (4, 3);
		%\draw[ultra thick] (0, 2) -- node[above] {$f * g$} (1.2, 2);
		\draw[ultra thick, smooth, domain=0:0.8, variable=\x] (0, 2) -- node[above] {$f * g$} (1.2, 2) -- plot ({1.2+\x}, {2+\x*(0.8 - 0.5*\x)}) -- plot ({2+\x}, {2.32-\x*(0.8 - 0.5*\x))}) -- (4, 2);
		
		\foreach \i in {0, ..., 4} {
			\pgfmathsetmacro{\x}{0.75 * \i};
			\pgfmathsetmacro{\xb}{0.95 * \i};
			\pgfmathsetmacro{\xc}{0.4*\i + 1.2};
			\pgfmathsetmacro{\y}{(abs(\i - 2)-2.2)*0.7 + 1.4};
			\draw[blue, thick] ({\x-0.2}, {\y}) -- ({\x+0.3}, {\y}) -- ({\x+0.3}, {\y+0.4}) -- ({\x+0.7}, {\y+0.4}) -- ({\x+0.7}, {\y}) -- ({\x+1.2}, {\y});
			\draw[red, thick] ({\x-0.2}, {\y}) -- ({\xb-0.1}, {\y}) -- ({\xb+0.3}, {\y+0.4}) -- ({\xb+0.3}, {\y}) -- ({\x+1.2}, {\y});
			\draw[gray, thick, ->] ({\xc}, {max(0.34, \y+0.08)}) -- ({\xc}, {1.92});
		}
	\end{tikzpicture} \qquad
	\begin{tikzpicture}
		\node[right] at (4.2, 2.2) {Corrélation \; };
		\draw[orange, thick] (1.6, 2) -- (1.6, 2.08);
		\fill[orange, opacity=0.7] (1.05, 0.56) -- (1.05, 0.76) -- (1.25, 0.56);
		\draw[greenTikz, thick] (2, 2) -- (2, 2.32);
		\fill[greenTikz, opacity=0.7] (1.8, -0.14) -- (1.8, 0.26) -- (2.2, -0.14);
		\draw[purple, thick] (2.4, 2) -- (2.4, 2.24);
		\fill[purple, opacity=0.7] (2.75, 0.56) -- (2.75, 0.96) -- (2.95, 0.76) -- (2.95, 0.56);
		
		
		\draw[blue, ultra thick] (0, 4) -- node[above] {$f$} (1.6, 4) -- (1.6, 4.8) -- (2.4, 4.8) -- (2.4, 4) -- (4, 4);
		\draw[red, ultra thick] (0, 3) -- node[above] {$g$} (1.6, 3) -- (1.6, 3.8) -- (2.4, 3) -- (4, 3);
		%\draw[ultra thick] (0, 2) -- node[above] {$f * g$} (1.2, 2);
		\draw[ultra thick, smooth, domain=0:0.8, variable=\x] (0, 2) -- node[above] {$f \otimes g$} (1.2, 2) -- plot ({1.2+\x}, {2+0.5*\x*\x)}) -- plot ({2+\x}, {2.32-0.5*\x*\x))}) -- (4, 2);
		
		\foreach \i in {0, ..., 4} {
			\pgfmathsetmacro{\x}{0.75 * \i};
			\pgfmathsetmacro{\xb}{0.95 * \i};
			\pgfmathsetmacro{\xc}{0.4*\i + 1.2};
			\pgfmathsetmacro{\y}{(abs(\i - 2)-2.2)*0.7 + 1.4};
			\draw[blue, thick] ({\x-0.2}, {\y}) -- ({\x+0.3}, {\y}) -- ({\x+0.3}, {\y+0.4}) -- ({\x+0.7}, {\y+0.4}) -- ({\x+0.7}, {\y}) -- ({\x+1.2}, {\y});
			\draw[red, thick] ({\x-0.2}, {\y}) -- ({\xb-0.1}, {\y}) -- ({\xb-0.1}, {\y+0.4}) -- ({\xb+0.3}, {\y}) -- ({\x+1.2}, {\y});
			\draw[gray, thick, ->] ({\xc}, {max(0.34, \y+0.08)}) -- ({\xc}, {1.92});
		}
	\end{tikzpicture}
\end{center}

\paragraph{Gradient}
Lorsqu'une image est bruité, le gradient est élevé à peu près partout, il est donc difficile de trouver les arrêtes. Pour remédier à cela, il suffit d'appliquer une filtre de lissage comme un filtre gaussien afin de faire disparaître le bruit pour se retrouver avec un signal lisse dont le gradient est élevé uniquement sur les arrêtes de l'image. On peut factoriser ces deux opération de lissage puis de gradient en une seule grâce à la formule :
$$ \dfrac{d}{dx} (f * g) = f * \dfrac{d}{dx} g $$
Par exemple dans le cas d'un filtrage gaussien, on peut calculer explicitement la dérivée de la gaussienne pour n'avoir qu'une seule opération à faire.

\sect{Détecteur de Harris \textit{(Harris corner)}}

Les coins d'une image sont les jonctions entre plusieurs arrêtes. C'est à dire les points au niveau desquels le gradient est fort dans toutes les directions. Les coins forment des points facilement repérables en plus d'être invariant aux translations, rotations, ... Le détecteur de Harris propose alors de trouver ces points là. On considère une image $I$ en niveaux de gris. On s'intéresse dans un premier temps à la distance "$L_2$" muni d'une matrice de poids $w$ entre un patch centré en $(0, 0)$ et un autre centré en $(x, y)$. On note $S$ cette distance :
$$ S_w(x, y) = \sum_u \sum_v w(u, v) \left( I(x+u, y+v) - I(u, v) \right)^2 $$
Pour simplifier cette expression, on développe $I$ au premier ordre :
$$ I(u+x, v+y) \approx I(u, v) + I_x(u, v) x + I_y(u, v) y $$
Ce qui donne :
$$ S_w(x, y) \approx \sum_u \sum_v w(u, v) \left( I_x(u, v) x + I_y(u, v) y \right)^2 = \pmat{x & y} \sum_u \sum_v w(u, v) \pmat{I_x^2 & I_x I_y \\ I_x I_y & I_y^2}(u, v) \pmat{x \\ y} $$
Le fait que le point en aux coordonnées $(0, 0)$ soit un coin se traduit par le fait que les patchs voisins dans toutes les directions sont différents. C'est à dire que $S_w$ soit grand dans toutes les directions. Or $S_w$ est décrite par la matrice suivante :
$$ M_w = \sum_u \sum_v w(u, v) \pmat{I_x^2 & I_x I_y \\ I_x I_y & I_y^2}(u, v) $$
Cette matrice étant symétrique, on peut l'orthodiagonalisé pour obtenir les valeurs propres $\lambda_1$ et $\lambda_2$. Finalement notre nouvelle caractérisation pour que $(0, 0)$ soit un coin est que ces deux valeurs propres soient grandes. Pour quantifier le fait qu'elles soient toutes deux grandes sans que l'une soit vraiment plus grande que l'autre, Harris et Stephens ont introduit la valeur :
$$ R_w = \lambda_1 \lambda_2 - \kappa (\lambda_1 + \lambda_2)^2 = \det(M_w) - \kappa \, \trace(M_w)^2 $$
$\kappa < 1/4$ et généralement on choisi $\kappa \in [0.04, 0.06]$. Ici on a fait le travail pour le point (0, 0) mais de manière générale pour le point $(i, j)$ il suffit de prendre :
nanored's avatar
nanored committed
87
$$ M_w(i, j) = \left[ w * \pmat{I_x^2 & I_x I_y \\ I_x I_y & I_y^2} \right] (i, j) $$
nanored's avatar
nanored committed
88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
On prend souvent une gaussienne pour $w$. Enfin une fois qu'on a le score $R_w(i, j)$ pour tous les pixels $(i, j)$, on ne garde plus que ceux qui ont un score supérieur à un certain seuil et qui sont des maximas locaux dans leur voisinage de 8 pixels.

\subs{Maximalité}

En réalité, garder les maxima locaux sur des voisinages de 9 pixels n'est pas très robuste et donne des distributions de points assez inégales.

\paragraph{NMS}
Une solution consiste à vérifier la maximalité dans un plus grand voisinage. Par exemple, dans une boule de rayon $r$. Pour ne pas supprimer trop de points lorsque $r$ est grand on peut rajouter une constante $c$ proche de 1 et inférieur à 1 (par exemple $c = 0.9$) et ne garder que les points $x_p$ qui vérifient :
$$ \forall q, \; \| x_p - x_q \| \leqslant r \, \Rightarrow \, c R_w(x_q) \leqslant R_w(x_p) $$
On a toujours le problème de la distribution inégale, mais on obtient un algo plus robuste bien qu'il faille choisir une valeur $r$.

\paragraph{ANMS}
Dans cette solution on calcule un rayon $r$ pour tous les points et on trie ensuite les points par leur rayon.
\begin{algorithm}
	\caption{ANMS}
	\KwIn{Réponse de Harris $R_w$ sur un ensemble $DetectedPoints$}
	$ProcessedPoints \gets \emptyset$ \\
	\ForEach{point $p \in DetectedPoints$ par réponse $R_w$ décroissante} {
		$\displaystyle r_p \gets \inf_{q \in ProcessedPoints \atop R_w(x_p) \; < \;  c R_w(x_q)} \| x_p - x_q \|$ \\
		Ajouter $p$ à $ProcessedPoints$
	}
	Retourner les $n$ points avec le plus grand rayon $r$
\end{algorithm}

\subs{Comparaison}

Les matrices $M_w(x_p)$ définisse des régions elliptiques autour des points par :
$$ \left\{ x_p + x \mid x^\trans M_w(x_p) x \leqslant 2 \right\} = x_p + \mu_{M_w(x_p)}$$
Pour normaliser ces régions d'intérêts afin de pouvoir faire des comparaisons entre des images qui ont différent point de vues, on peut alors appliquer la transformation: 
$$ x' = M_w^{1/2} x $$
Sinon si on sait qu'entre nos deux images il y a une homographie $H$ (i.e. $I = H(I')$), alors on peut faire une approximation affine de $H$ que l'on note $\hat{H}$. Et la distance entre un point d'intérêt de matrice $M$ dans la première image et un point d'intérêt de matrice $M'$ dans la seconde peut être la distance de Jaccard suivante :
$$ 1 - \dfrac{\left| \mu_M \cap \left( \hat{H}^\trans \mu_{M'} \hat{H} \right) \right|}{\left| \mu_M \cup \left( \hat{H}^\trans \mu_{M'} \hat{H} \right) \right|} $$