Contexte

 
Lorsqu'on  s'intéresse aux problèmes de stabilité numérique et de vitesse d'exécution pour
atteindre des cadences de traitement temps réel, plusieurs aspects, dépendants les uns des
autres doivent être abordés.
 

Aspect qualitatif: F32 ou F64 ?

Les nombres flottants (au sens IEEE-­754) existent en trois précisions. La précision simple – 32
bits, 23 de mantisse, la précision double –64 bits dont 53 de mantisse – et depuis peu (norme
IEEE-­754 2008) en demi précision ou half – 16 bits dont 10 de mantisse. Un axe de recherche
consiste à étudier quelle est la précision nécessaire à chaque étape de calcul d'un algorithme
pour obtenir, au final, un résultat avec la précision nécessaire.  Jusqu'en 2015 le format half
n'existait pas vraiment. Il était certes défini pour le stockage des nombres en mémoire (intel et
nvidia propose des intrinsics dédiés), mais les calculs se faisaient en float, la conversion étant
réalisée à la volée. Ainsi, alors que l'étude de la précision et la stabilité numérique ne concernait
que le HPC (une partie importante étant de savoir quels codes en double pouvaient être passer
en float et quels codes devaient être en précision mixte), l'arrivée du format half intéresse le
monde des systèmes embarqués pour plusieurs raisons [CAMPS 2006][SCAN 2006]. D'un point
de vue précision, un grand nombre de calculs en traitement d'images, en vision par ordinateur et
plus généralement en traitement du signal ne nécessite pas 32 bits. Le fait de passer en demi
précision, permet alors de diviser par deux l'empreinte mémoire d'un code, ce qui peut avoir un
impact important sur les performances [GdR ISIS 2014] d'un code.
 

Aspect quantitatif: SIMD et latence

Le choix du format de calcul a un double impact sur la vitesse de calcul. D'une part, plus le
format est court et plus la latence de calcul diminue. On passe par exemple de 20 à 14 cycles
pour une division, lorsque l'on passe de 64 à 32 bits, sur un processeur Intel Haswell. D'autre
part, plus le format est court et plus le parallélisme SIMD augmente (4 float contre 2 double en
SSE, 8 et 4 en AVX, 16 et 8 en KNC et AVX-­512). Comme certains opérateurs ne sont pas
entièrement pipelinés (cas de la division) on obtient des gains sur-­linéaires. Sur les GPU, il n'y a
pas de parallélisme de type SIMD, c'est donc du stockage (en mémoire privée shared) que
viendra l'accélération.
 

Aspect optimisation, complexité algorithmique et intensité arithmétique

En traitement d'images, certains opérateurs sont décomposables et peuvent même être
reformulés avec une complexité très différente dans certains cas.
Ainsi les filtres (stencils en informatique) bidimensionnels sont construits comme étant
composés de deux filtres monodimensionnels. Ainsi se pose la question de balayer une fois une
image en appliquant une fois un filtre 2D nécessitant N^2 accès mémoire par point ou balayer
deux fois l'image (et augmenter le nombre de défaut de caches) en appliquant deux filtres 1D
nécessitant un total de 2N accès mémoire. Pour certains opérateurs, comme l'opérateur de
moyennage 2D, il est possible d'aller encore plus loin en recourant au calcul de l'image intégrale
(+scan 2D) [Bleloch 1990]. Ainsi, une fois ce pré-­calcul réalisé (nécessitant 3N^2 accès
mémoire), la somme et la moyenne de n'importe quel ensemble de points, et pour n'importe
quelle taille d'ensemble, se fera avec une complexité constante de 4 accès mémoire et 3
opérations arithmétiques. Du point de vue de la stabilité numérique, les filtres séparables ne
posent pas particulièrement de problème, les filtres 2D peuvent avoir des problèmes
d'absorption et les images intégrales des problèmes d'absorption et de cancellation. Ces
problèmes augmentant avec la taille des filtres et la taille des images, il est nécessaire de faire,
soit des compromis vitesse/précision, soit des choix en fonction des dimensions des objets manipulés. Des techniques de réduction des erreurs (par des changements algorithmiques) sont
possibles [ICSP 2000, CDS 2005], souvent au prix d’un surplus de calculs (mais pouvant
s’exécuter sur des mantisses plus petites et donc exploiter le parallélisme SIMD).
 

Aspect Applicatif: estimation du mouvement et stabilisation

Si la majorité des opérateurs de traitements d'images se font en entier ou en virgule fixe, il existe
plusieurs opérateurs en vision nécessitant des flottants. L'un des cas le plus courant est le calcul
du flot optique [HS 1981][Onera2005][ICASSP 2015][ICIP 2015]. C'est un opérateur qui calcul
une carte de vecteurs vitesse pour tout couple d'images, cette carte servant soit à faire de
l'estimation de mouvement, lorsque la caméra est mobile, soit à faire de la stabilisation d'image,
lorsque la caméra est en mouvement. D'un point de vue algorithmique, ces différents opérateurs
sont récursifs et itératifs ce qui les rend sensibles aux approximations et à la propagation
d'erreur.  Ils peuvent même être instable s'ils sont mal paramétrés, ce qui est un problème
majeur pour les drones.
 

Objectif

L'objectif de ce stage est donc d'utiliser des outils existants (Cadna pour la stabilité numérique
[CADNA 2008], MPFR pour la précision des calculs [MPFR 2007] et MPFI pour une validation de
la précision par calcul intervalle [MPFI 2005]) pour étudier la précision et la stabilité
d'algorithmes de calcul de flot optique, en fonction des formats de calcul,  des optimisations
algorithmiques réalisées et des cibles architecturales (GPU Tegra X1 pour l'embarqué,
processeur généraliste SIMD multi-­coeurs).
Contrairement aux filtres non récursif, la présence de plusieurs récursivités au sein de ces
algorithmes a fait qu'il n'existe pas actuellement de formule analytique estimant le nombre de
bits corrects en fonction des paramètres de calculs (format d'entrée, taille des filtres, ...). Il est
pour le moment nécessaire de recourir à des expérimentations (sur des séquences de
références) et de réaliser une exploration de l'espace des paramètres, qui permettront de valider
une étude théorique sur la précision des calculs (borne sur l’erreur de sortie).
 

Bibliographie

[ICIP 2015] Approximation Order of the LAP Optical Flow Algorithm, T. Blu, P. Moulin and C.
Gilliam, IEEE Int. Conf. on Image Processing
[ICASSP 2015] C. Gilliam and T. Blu, Local All-Pass Filters for Optical Flow Estimation, IEEE Int.
Conf. on Acoustics, Speech and Signal Processing
[Eurasip 2014] "Covariance tracking: architecture optimizations for embedded systems" A.
Roméro, L. Lacassagne, M. Gouiffès, A. Hassan Zahraee, Eurasip Journal on Advances in Signal
Processing, 2014
[GdR ISIS 2014] Journée arithmétique pour le traitement du signal et de l'image 2014-­07-­03
Daniel Ménard (IETR) et Thibault Hilaire (LIP6). "Optimisation arithmétique pour des
applications de vision", Lionel Lacassagne (LRI).
[CADNA 2008] « CADNA: a library for estimating round-­off error propagation », F. Jézéquel and
J.-­M. Chesneaux., in Computer Physics Communications, 178(12):933-­955, 2008
[MPFR 2007] « MPFR: A multiple-­precision binary floating-­point library with correct
rounding », L. Fousse, G. Hanrot, V. Lefèvre, P. Pélissier, P. Zimmermann, in ACM Transactions
on Mathematical Software, vol. 33-­2, June 2007
[CAMPS 2006] "Customizing CPU instructions for embedded vision systems", S. Piskorski , L.
Lacassagne, S. Bouaziz, D. Etiemble, IEEE CAMPS Computer Architecture, Machine Perception
and Sensors, 2006, pp. 59-­64
[SCAN 2006] "Efficient floating point interval processing for embedded systems and
applications", S. Piskorski , L. Lacassagne, M. Kieffer, D. Etiemble, International Symposium of
Scientific computing, Computer Arithmetic and Validated Numerics, 2006, pp. 23-­26.
[CDS 2005] « Two efficient structures for 2D digital filter implementation », Z. Zhao, IEE
Proceedings -­ Circuits, Devices and Systems, Volume 152, Issue 6, December 2005, p. 641 – 648
[MPFI 2005] « Motivations for an arbitrary precision interval arithmetic and the MPFI library »,
N. Revol and F. Rouillier, in Reliable Computing, vol. 11, no 4, pp 275-­-290, 2005
[Onera 2005] Dense optical flow estimation by iterative local window registration, Guy Le
Besnerais, Frederic Champagnat, "," in Proceedings of IEEE ICIP05, vol. 1, 2005
[ISCP 2000] « Noise reduction in 2-­D separable-denominator digital filters using error
feedback », T. Hinamoto and M. Nakamoto, 5th Int. Conference on Signal Processing, 2000,
pp547-­550
[Horn-­Schunk 1981], Determinig Optical flow, Artificial Intelligence, vol 17, 185-­203 1981
[Bleloch 1990] Vector Models for Data-­Parallel computing, Guy Bleloch, MIT Press