--- title: INFO911 (4b) Filtrage spatial - convolution discrète 1D et 2D type: slide slideOptions: transition: slide progress: true slideNumber: true --- # Filtrage spatial - convolution discrète 1D et 2D ## (Traitement et Analyse d'Image 4b) > [name=Jacques-Olivier Lachaud][time=Novembre 2020][color=#907bf7] > (Les images peuvent être soumises à des droits d'auteur. Elles sont utilisées ici exclusivement dans un but pédagogique) ###### tags: `info911` Retour à [INFO911 (Main) Traitement et analyse d'image](https://codimd.math.cnrs.fr/s/UE_B59gMy) --- # Convolution continue et discrète On définit les ==fonctions discrètes== $f,g: \mathbb{Z} \rightarrow \mathbb{R}$ | convolution continue $f \ast g(x)$ | convolution discrète $f \ast g[i]$ | | ---------------------------------- | -------- | | $f \ast g(x) := \int_{-\infty}^{\infty} f(t)g(x-t) dt$ | $f \ast g[i] := \sum_{l=-\infty}^{\infty} f[l]g[i-l]$ | Mêmes propriétés de **bilinéarité**, **associativité**, **commutativité** ==impulsion discrète identité== $\delta_0[0] = 1$, et $\forall i \neq 0, \delta_0[i] = 0$ :::danger Quand on code, attention aux bords ! Il faut **étendre** nos fonctions/images vers les deux infinis. On met souvent des zéros, ou on fait un miroir sur la fonction. ::: --- ## Exercices 1. Vérifiez que si, $\delta_a[a] = 1$, et $\forall i \neq a, \delta_a[i] = 0$, alors $\delta_a \ast f = \tau_a( f )$ (son translaté de $a$) 2. Soit $h[-1]=1/4$, $h[0]=1/2$, $h[1]=1/4$ et $h[i]=0$ sinon. Que vaut $h \ast f[i]$ ? 3. Soit $h[-1]=1$, $h[0]=-1$, et $h[i]=0$ sinon. Que vaut $h \ast f[i]$ ? 4. Coder le calcul de la convolution de deux fonctions discrètes `f` et `g`, définis comme des `vector<double>`, où le 0 de `f` est en `z_f` et le zero de `g` en `z_g`. ```cpp= std::vector<double> convolution(const std::vector<double>& f, const std::vector<double>& g, int z_f, int z_g ) // fonctions étendues par des zéros ``` --- ## Masques de convolutions (discrètes) Les filtres de convolutions spatiaux sont souvent de taille limitée (pourquoi ?) On les représente plutôt avec un masque avec leur valeur et en pointant le zéro. Dirac $\delta_0$ $\begin{array}{|c|c|c|} \hline 0 & \fbox{1 } & 0\\ \hline\end{array}$ Moyenneur $\begin{array}{|c|c|c|} \hline 1/4 & \fbox{1/2 } & 1/4\\ \hline\end{array}$ Différentiel centré $\begin{array}{|c|c|c|} \hline 1/2 & \fbox{0 } & -1/2\\ \hline\end{array}$ Différentiel avant $\begin{array}{|c|c|c|} \hline 1 & \fbox{-1 } & 0\\ \hline\end{array}$ Différentiel arrière $\begin{array}{|c|c|c|} \hline 0 & \fbox{1 } & -1\\ \hline\end{array}$ Laplacien $\begin{array}{|c|c|c|} \hline 1 & \fbox{-2 } & 1\\ \hline\end{array}$ Exercice: Que vaut la convolution des différentiels avant et arrière ? --- # Convolution continue et discrète 2D ==continu== $I,J:\mathbb{R}^2 \rightarrow \mathbb{R}$ ou ==discret== $I,J: \mathbb{Z}^2 \rightarrow \mathbb{R}$ | convolution continue $I \ast J(x,y)$ | |:-----------------------------------------------------------------------------------------:| | $I \ast J(x,y) := \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} I(t,u)J(x-t,y-u) dt du$ | | convolution discrète $I \ast J[i,j]$ | |:--------:| | $I \ast J[i,j] := \sum_{l=-\infty}^{\infty} \sum_{m=-\infty}^{\infty} I[l,m]J[i-l,j-m]$ | :::danger Quand on code, attention aux bords aussi ! Il faut **étendre** nos images. ::: --- ## Convolution continue et discrète 2D Mêmes propriétés de **bilinéarité**, **associativité**, **commutativité** ==impulsion discrète identité== $\delta_{(0,0)}[0,0] = 1$, et $\forall i,j, (i,j) \neq (0,0), \delta_{(0,0)}[i,j] = 0$ ==impulsion translation== (a,b) $\delta_{(a,b)}[a,b] = 1$, et $\forall i,j, (i,j) \neq (a,b), \delta_{(a,b)}[i,j] = 0$ on note souvent $\mathrm{Id}$ l'impulsion identité $\delta_{(0,0)}$ --- ## Masques de convolution 2D Filtre spatial souvent petit, représenté par un masque Moyenneur $M:=\begin{array}{|c|c|c|} \hline 1/16 & 2/16 & 1/16 \\ \hline 2/16 & \fbox{4/16 } & 2/16 \\ \hline 1/16 & 2/16 & 1/16 \\ \hline\end{array}$, somme = 1 | image $I$ | $I \ast M$ | $I \ast M \ast M \ast \ldots \ast M$ | | -------- | -------- | -------- | |  |  |  | --- ## Masques différentiels 2D $S_x:=\begin{array}{|c|c|c|} \hline 1/4 & 0 & -1/4 \\ \hline 2/4 & \fbox{0 } & -2/4 \\ \hline 1/4 & 0 & -1/4 \\ \hline\end{array}$ $S_y:=\begin{array}{|c|c|c|} \hline -1/4 & -1/2 & -1/4 \\ \hline 0 & \fbox{0 } & 0 \\ \hline 1/4 & 1/2 & 1/4 \\ \hline\end{array}$ | $S_x$ Filtre différentiel en x (Sobel) | $S_y$ Filtre différentiel en y (Sobel) | | -------- | -------- | |  |  | --- ## Masques séparables Un masque $K$ est ==séparable== ssi $K=H \ast V$, avec $H$ "horizontal" et $V$ vertical $M:=\begin{array}{|c|c|c|} \hline 1/16 & 2/16 & 1/16 \\ \hline 2/16 & \fbox{4/16 } & 2/16 \\ \hline 1/16 & 2/16 & 1/16 \\ \hline\end{array}=\begin{array}{|c|c|c|} \hline 1/4 & \fbox{2/4 } & 1/4 \\ \hline \end{array} \ast \begin{array}{|c|} \hline 1/4 \\ \hline \fbox{2/4 } \\ \hline 1/4 \\ \hline\end{array}$ :::success Il est plus rapide de calculer $M$ sous sa forme $H \ast V$ ::: --- ## Exercices: - Si $M$ est un masque $K \times L$ et un $M'$ un masque $K' \times L'$, quelle est la taille du masque $M \ast M'$ ? - Si $I$ image de taille $N \times N$ et $M$ masque $K \times K$, quelle est la complexité de $I \ast M$ ? - Si $M$ est séparable en $M=H \ast V$, quelle est alors la complexité de $(I \ast H) \ast V$ ? - Est-ce la même complexité que $I \ast (H \ast V)$ ? - séparer les filtres $S_x:=\begin{array}{|c|c|c|} \hline 1/4 & 0 & -1/4 \\ \hline 2/4 & \fbox{0 } & -2/4 \\ \hline 1/4 & 0 & -1/4 \\ \hline\end{array}$ $S_y:=\begin{array}{|c|c|c|} \hline -1/4 & -1/2 & -1/4 \\ \hline 0 & \fbox{0 } & 0 \\ \hline 1/4 & 1/2 & 1/4 \\ \hline\end{array}$ --- ## Masques Laplaciens Masque ==Laplacien== $L:=\begin{array}{|c|c|c|} \hline 0 & 1 & 0 \\ \hline 1 & -4 & 1 \\ \hline 0 & 1 & 0 \\ \hline\end{array}$, zéros=contours | Laplacien $L$ | Autre forme $S_x \ast S_x + S_y \ast S_y$ | |:--------:|:--------:| |  |  | --- ## Application au rehaussement de contraste Image + $\alpha$ Contours = Image plus contrastée On prend les masques $R_\alpha = \mathrm{Id} - \alpha L$ ou $R'_\alpha = \mathrm{Id} - \alpha (Sxx+Syy)$ | | | | | -------- | -------- | -------- | | Input image $I$ | $I \ast R_1$ | $I \ast R'_1$ | --- ## Exercices 1. Séparer le masque laplacien $L$ 2. Calculer $S_x \ast S_x + S_y \ast S_y$ 3. Que fait un masque $K_n = \underbrace{(M \ast M \ast \ldots \ast M)}_{n~ fois} \ast L$ ? 4. Comment calculer $I \ast K_n$ efficacement ? 5. Le gradient de $I$ est l'image vectorielle 2D $G=(S_x,S_y)$. Sa norme représente la force des contours de l'image, $||G||=\sqrt{S_x^2 +S_y^2}$. Est-ce qu'on peut le calculer par convolution ? --- ## Conclusion Cadre théorique puissant (plus encore avec le lien avec le filtrage fréquentiel) Représentation uniforme des traitements bas-niveau Mise en oeuvre facile en électronique et informatique Mais trop **restrictif** => d'autres filtres sont nécessaires `video-filter`