Exploration logicielle

Algorithmes

Norme de gradient 2D L’opérateur gradient permet d’obtenir à partir d’une image, une information sur les variations de valeur entre les pixels. Dans le cas de l’application de vision robotique étudiée, où seule la norme du gradient est utilisée, le choix de l’opérateur n’est pas définitif. Pour ce document, on optera pour l’opérateur de Sobel (figure 3.1), mais des tests ont été faits avec l’opérateur de Prewitt, et il est envisagé d’utiliser l’opérateur de Deriche. −1 B = −2 −1 1 1 2 −1 −2 −1 A = 1 1 2 G = sqrt( (A*E)² + (B*E)² ) 0 0 0 0 0 0 Figure 3.1 – Opérateur de Sobel – Intensité de gradient de l’opérateur de Sobel. L’image d’intensité de gradient G est calculée à partir de l’image d’entrée E. Le symbole * représente l’opérateur de convolution Les effets de bord sont réduits ici aux pixels du tour de l’image, pour lesquels on ne dispose pas des huit pixels limitrophes. On choisit une méthode simple pour gérer 51 Exploration logicielle Chapitre 3 : Exploration logicielle ces effets de bord : pour le tour de l’image, le résultat de l’opérateur est simplement remplacé par une valeur nulle. 

Pyramide Gaussienne

Une fois que l’intensité du gradient de l’image fournie par la caméra est obtenue, il reste à découper l’information fréquentielle de celle-là en bandes de fréquences. C’est ici qu’intervient la pyramide Gaussienne de Crowley et. al (CRP02). Pour rappel, la décomposition en sous-blocs, présentée en section 1.2.2, est la suivante : – filtrages Gaussiens successifs – sous-échantillonnage à chaque octave (en fréquence spatiale) – soustraction deux à deux des résultats de filtrage pour obtenir les DoG (Différences de Gaussiennes) 

Filtrages Gaussiens

L’algorithme 1 représente le filtrage Gaussien par convolution avec un noyau de coefficients. Les valeurs de σ qui sont utilisées pour la pyramide de l’application de vision sont celles proposées par Crowley et al., soit 1 et √ 2 selon la position du filtre dans la pyramide (figure 1.2). La formule de la fonction Gaussienne est 1 2πσ2 e − x 2+y 2 2σ2 . Dans cette formule, le coefficient 1 2πσ2 permet d’obtenir une surface de valeur 1 sous la courbe Gaussienne. Dans le cas d’une convolution avec un noyau de coefficients, la valeur de ce coefficient n’est théoriquement juste que pour un noyau de coefficients de dimensions infiniment élevées. Dans notre cas, la taille du noyau étant finie, la somme des coefficients n’atteint pas 1, s’ils sont calculés à partir de cette formule. Il faut donc passer par une étape de normalisation des coefficients. On calculera une version temporaire des coefficients du noyau avec la formule e − x 2+y 2 2σ2 , afin de calculer leur somme. Chacun des coefficients temporaires est alors divisé par cette somme, afin que la somme des coefficients définitifs du noyau soit égale à 1. La formule adaptée de la fonction Gaussienne sera alors G(x, y) = 1 xmax P a=xmin ymax P b=ymin e − a2+b2 2σ2 e − x 2+y 2 2σ2 . 

Algorithmes

Entrée : E : image de dimensions H × W G : noyau de coefficients Gaussien de dimensions h × w impaires, centré sur (0,0) (somme des coefficients = 1) Sortie : S : image de dimensions H × W 1 for Y ← 1 to H do 2 for X ← 1 to W do 3 S(X, Y ) = 0 4 for y ← −(h − 1)/2 to (h − 1)/2 do 5 for x ← −(w − 1)/2 to (w − 1)/2 do 6 S(X, Y ) = S(X, Y ) + E(X + x, Y + y) × G(x, y) 7 end 8 end 9 end 10 end Algorithme 1: Filtrage Gaussien par convolution 2D, effets de bords non représentés L’algorithme 1 présente un temps d’exécution relativement long, du fait des nombreuses multiplications effectuées pour chaque pixel de l’image de sortie. Le filtrage Gaussien 2D étant séparable en deux passes de convolution 1D (verticale + horizontale) sans perte de précision, il sera peut-être préférable de choisir cette solution. L’algorithme 2 présente la convolution en 2 passes à 1 dimension : l’image subit d’abord une convolution avec une fenêtre d’un pixel de haut, et large de la dimension du noyau 2D, puis le résultat subit une autre convolution, cette fois avec la même fenêtre disposée verticalement (ces deux passes sont interchangeables). Le nombre de multiplications par pixel de l’image de sortie passe alors d’une complexité en O(n 2 ) à une complexité en O(n). Plus concrètement, une fenêtre de convolution carrée de taille 9 nécessite 81 multiplications (carré de 9 × 9 pixels) dans le cas de l’algorithme 1, alors qu’il n’en nécessite que 18 (deux lignes de 9 pixels) dans le cas de l’algorithme 2, soit moins du quart. On peut donc supposer que cette optimisation permettra d’accélérer fortement l’exécution, et permettra de réduire les ressources arithmétiques utilisées par le déploiement matériel. Cela dit, il reste à voir si cet algorithme peut être déployé en matériel sans trop de compromis sur le comportement temporel, ni sur l’utilisation de la mémoire. L’algorithme en 2 passes sera donc utilisé pour tout déploiement logiciel.