Traitement de l'information et modélisation

english version

GPU for Image : GPU-FOLKI

1- Introduction : flot optique

Le flot optique est le champ des déplacements apparents mesurés dans le repère image. Le flot optique résulte des mouvements des objets présents dans la scène, du mouvement propre du capteur, mais peut aussi être impacté par des effets d’illumination.

L’estimation du flot optique nécessite une forme de régularisation spatiale, le mouvement d’un pixel unique, ou même d’une zone peu texturée n’étant en général pas observable (un problème appelé « problème d’ouverture » en vision). Les méthodes d’estimation peuvent être regroupées en deux grandes familles, traditionnellement associées à deux publications du début des années 1980.

• Les méthodes de type Horn et Schunk reposent sur une formulation globale de l’estimation comme la recherche d’un champ de vecteur permettant de superposer deux images (terme de recalage) et satisfaisant à des contraintes de régularité (terme de régularisation spatiale);
• Les méthodes de type Lucas-Kanade utilisent des techniques de recalage paramétrique de fenêtres locales (centrées autour de chaque pixel dans le cas des approches denses).

Les techniques les plus anciennes (Horn et Schunck, par exemple) considèrent uniquement des déplacements faibles (typiquement de l’ordre du pixel) et reposent sur un développement limité au premier ordre du terme de recalage, qui devient linéaire. Depuis les années 90, des techniques itératives et multirésolution, qui relinéarisent plusieurs fois le terme de recalage et utilisent une pyramide d’images, permettent d’estimer des grands déplacements.

2- L’Algorithme FOLKI

FOLKI est un algorithme développé par G. Le Besnerais et F. Champagnat en 2005 [1] pour estimer rapidement un flot optique dense par une technique de recalage de fenêtre de type Lucas-Kanade itératif et multirésolution. Il repose sur un développement limité spécifique du critère de recalage de fenêtre permettant de limiter le nombre d’interpolations d’image par itération. Cette spécificité lui permet d’être beaucoup plus rapide que les autres algorithmes de type Lucas-Kanade itératif, comme ceux dérivés de l’implémentation LK pyramidale de Open CV par exemple, et plus précis comme le montrent les évaluations comparatives de l’université de Middlebury. Un exemple de résultat sur les données de ce site est présenté en figure 1

Figure 1. Résultat de FOLKI sur l’exemple « army » de l’université Middlebury

Une autre caractéristique importante de FOLKI est sa structure hautement parallèle qui profite pleinement des architectures de calcul modernes.

3- Implémentation CUDA

Comme le montre les publications [1,2], une itération de FOLKI implique uniquement des opérations pixels à pixels sans notion de voisinage, des convolutions séparables et des interpolations d’image.

Pour les opérations pixels à pixels, nous utilisons simplement une bijection entre les pixels de l'image et la grille de calcul où chaque thread correspond à un pixel.

L'API Cuda fournit une interpolation bilinéaire native, que nous avons utilisée. Celle-ci utilise des registres spéciaux des GPU, les registres de textures. Ces registres permettent de stocker des données en une à trois dimensions et leur lecture peut se faire avec des indices non entiers, ce qui permet de les utiliser pour faire des interpolations. L'interpolation obtenue n'est pas d'une grande précision car elle consiste à diviser en 256 intervalles le pas de base des données stockées.

En ce qui concerne les convolutions, nous nous sommes basés sur l'exemple de convolution séparable du SDK de Cuda.

4- Performances

L’algorithme FOLKI-GPU permet de calculer une estimation dense et précise du flot optique y compris dans le cas de grands déplacements,  en cela FOLKI diffère d'autres algorithmes rapides qui ne font que détecter du mouvement, le plus souvent uniquement sur des zones de fort gradient. Le temps de traitement dépend de différents facteurs en particulier du rayon de la fenêtre utilisée et du nombre d’itérations effectuées à chaque niveau de résolution. Pour des réglages conduisant à un flot de très bonne qualité un temps de traitement typique est de 32ms/frame pour une vidéo au format full HD (1920x1080), ce qui correspond donc à une cadence plus élevée que la cadence vidéo. Cette performance est à notre connaissance unique pour cette qualité de flot optique. La figure 3 présente le gain en coût de calcul par pixel entre une implémentation C sur CPU (courbe bleue) et la version FOLKI-GPU (courbe rouge). Le gain en temps de calcul est d’un facteur 10 pour les images de dimensions modestes (512x512) mais ce facteur atteint 100 pour les images de grandes dimensions (2048x4096) !

Figure 2. Temps de calcul de FOLKI par pixel en fonction du nombre total de pixels par frame. En bleu : implémentation C sur CPU, en rouge implémentation CUDA FOLKI-GPU.

L'algorithme FOLKI possède deux paramètres principaux :

• le nombre d'itérations
• le rayon de la fenêtre

Nous illustrons sur la figure suivante le comportement de l'algorithme lorsqu'on augmente le nombre d'itérations et lorsque l'on augmente la taille de la fenêtre.

Figure 3. En bleu, l'influence d'une augmentation du nombre d'iterations et en rouge l'influence d'une augmentation du rayon de la fenêtre.

5- Applications

L’algorithme FOLKI et sa version GPU ont déjà été utilisés sur de nombreuses séquences provenant de contextes différents, parmi lesquels la vidéo-surveillance, la vision pour la robotique et la métrologie par imagerie. Ces différentes applications sont illustrées dans les vidéos présentées ci-dessous.

Vidéo 1. Estimation de mouvement de piétons sur une séquence PETS (Dataset 3 du PETS 2007). La norme du flot optique estimé est représentée par un niveau de couleur du rouge vers le blanc, une version sous-échantillonnée du champ de vecteur obtenu est représentée par des flêches rouges pour juger de l’orientation estimée.

Vidéo 2. Estimation d’élévation des structures au sol lors du survol d’une zone rurale par le drone Ressac (ONERA/DCSD). Le niveau de couleur donne la norme du mouvement, celui-ci est lié à la structure 3D de la scène. Les zones les plus proches du drone (cimes des arbres, toits) ont un mouvement apparent plus important que les zones plus lointaines (sol...).

Vidéo 3. Estimation de champ de déplacement par FOLKI-GPU sur des images PIV (Particle Imagery Velocimetry) haute cadence, images issues du site FLUIDS (Package 3, B. Wieneke, LaVision). L’échelle de couleur représente le rotationnel, un sous-échantillonnage du champ de vecteur est aussi représenté à l’aide de flêches.

7- Publications

[1] Guy Le Besnerais and Frédéric Champagnat, “Dense optical flow estimation by iterative local window registration,” in Proceedings of IEEE ICIP’05, vol. 1, pp. I–137–40, Genova, Italy, Sept. 2005.

Mis à jour le - © ONERA 2008 - Crédits et conditions d'utilisation