XFV

eXtremely Fast Vision

Responsable

Période

septembre 2009 - décembre 2012

Axes

Accélération matérielle du traitement de l'information

Ce projet HESS-SO (Isys) traite de la détection d'objets, connus à priori, dans une image. Il s'agit de « Pattern Matching ».

Ce projet a pour but de retrouver un ou plusieurs objets identiques, de taille et d’orientation différente, dans un flux d’images vidéo défilant à grande vitesse.

Plusieurs instituts ont participé à ce projet : iAi (institut d’Automatisation) et Reds (Reconfigurable embedded digital systems) de l’HEIG-VD et iSi (institut Systèmes industriels) de l’HEVS.

Chacune de ces équipes s’est concentrée sur un ou plusieurs types d’algorithme bien définis, dont principalement les algorithmes CIRATEFI et la corrélation multi-échelles / multi-rotations.

Ces algorithmes ont été implantés sur différentes plateformes (DSP, GPU, FPGA) et les performances obtenues ont été mises en concurrence et comparées.

Cet article présente le travail effectué sur une plateforme à base de FPGA (Field Programmable Gate Array).

Différentes architectures ont été étudiées afin de déterminer la meilleure solution pour une implantation sur une telle plateforme. Le candidat idéal est la détection de motifs spécifiques sur un flux vidéo acquis par une caméra HD (Haute-Définition). L’algorithme de «coefficients de corrélation» a été choisi, et adapté pour être insensible à l’échelle et l’orientation du motif à détecter.

Le matériel utilisé : Une caméra Toshiba DVI HD de 1280 x 1024 pixels @ 60 images/sec, une carte de développement à base d’Altera Stratix IV GX 230, une carte Bitec d’entrée/sortie HSMC-DVI et un écran TV full HD.

L’algorithme déployé : « coefficient de corrélation multi échelles / multi rotations ». Ce type d’algorithme est défini par l’équation ci-dessous:
Algorithme_XFV
Il s’agit de déplacer un pattern « T », représentant l’objet à détecter, sur chaque pixel de l’image « I » afin de déterminer l’emplacement exact de l’objet. A chaque pixel, l’algorithme de corrélation ci-dessus est appliqué. La valeur du résultat normalisée, entre -1 et +1, indique la probabilité de détection de l’objet.

La valeur limite est choisie de manière à trouver, dans l’image à traiter, tous les objets et uniquement ces objets recherchés. Des erreurs de détection peuvent survenir et sont soit un « faux négatif » (objet manqué) ou « faux positif » (objet en trop).

La technologie des FPGA : Les FPGA ont l’avantage de traiter une très grande quantité d’information en parallélisant de multiples calculs « simples » à des fréquences de l’ordre de 400MHz pour les circuits de dernière génération, telles les Stratix V ou Virtex 7. Ces circuits offrent une grande quantité de cellules de calcul (LUT) et un réseau d’interconnections très complexe.

Le flux de données : Dans le cas d’un flux vidéo HD (1280 x 1024 px @ 60img/s), la quantité d’information reçue à la seconde représente 2Gbits. L’FPGA du kit de développement utilisé est connectée par un bus 24bits (3 bytes RGB) au circuit DVI externe. Cela représente donc un flux de données à 80 MHz. Une telle fréquence ne pose pas de problème particulier pour une Stratix IV. Par contre, la taille d’une image est d'environ 32Mb et nécessite 2 fois plus de mémoire que la quantité disponible dans l'FPGA utilisée dans ce projet. L'astuce décrite ci-dessous a donc été mise en oeuvre afin que l'algorithme de corrélation puisse être appliqué à chaque nouvelle image en un instant donnée T, sans pour autant disposer entièrement de cette dernière en mémoire dans l'FPGA.

Implantation et résultats : la corrélation de coefficients fonctionne effectivement sur principe de base du déplacement d’une matrice n x n sur chaque pixel d’une image complète. Or, comme mentionné ci-dessus, il n’est pas possible de stocker l’entier de cette image. Afin de minimiser la quantité d’information nécessaire, ce n’est pas la matrice qui se déplace sur l’image, mais ce sont les pixels, arrivant en série du lien DVI, qui sont « déplacés » à chaque coup d’horloge « sous » la matrice. Ceci nécessite de ne sauver que la quantité de lignes correspondante à la taille de la matrice, soit n lignes. Le cas considéré, une image de 800 x 600 px et une matrice de 25 x 25 px représente un peu plus de 150kbits, soit moins de 2% de la mémoire disponible.

Dans le cadre de la corrélation de coefficients, l’algorithme est donc réévalué à chaque nouveau pixel et un maximum est calculé. Si ce dernier est supérieur à la limite définie, les nouvelles coordonnées du pixel sont sauvées. A la fin de l’image, les positions ainsi obtenues sont mises en évidence par incrustation d’une marque aux coordonnées déterminées (carrés verts). Le délai de calcul, dû au pipeline des 25 lignes, n’est que de 700ns. L’utilisation des LUT est de 45%, les BlocRam de 15% et les Blocs DSP de 80% pour une image de 800 x 600 px.

Enfin, afin de garantir une implantation rapide et stable pour chaque nouvel algorithme, le design est composé de blocs « SoPC » de type QSys (Altera). Tout le contrôle du flux vidéo reste inchangé et seul le bloc de l’algorithme nécessite d’être adapté en fonction des nouvelles spécifications. Les paramètres de configuration de l’algorithme (les valeurs d’une matrice par exemple) sont modifiés dynamiquement par le biais d’une application Windows communiquant avec le Softcore Nios II (Altera) implanté dans le design SoPC. Le flux des pixels au travers de l’algorithme est représenté ci-dessous. Ce bloc diagramme décrit précisément l'architecture implantée dans l'FPGA.
Design_bloc_XFV

Au vu des résultats obtenus il est tout à fait aisé d’envisager des applications industrielles performantes sur des plateformes à base de logiques programmables.