ELECINF344/381

Partie interactive du site pédagogique ELECINF344/ELECINF381 de Télécom ParisTech (occurrence 2011).

Catégories

Copterix: some reflexions about Kanade

After having spent hours focusing on our PID into the Télécom ParisTech’s dancing room, we joined Télécom Robotic’s room in order to work on our implementation of Lucas and Kanade algorithm, because of a giant chessboard in green and red, perfect for image processing. We fixed Copterix in the air using some strings, and started test, with or without threshold, and it wasn’t really efficient…
We thought a moment about using ‘unfisheye’ opencv’s algorithm (see joined photo to understand why we wanted to use it), but it took 0.6 seconds per frame on our Gumstix…

Fisheye

What our camera actually sees: we can observe a 'fisheye' effect

Then we stopped and decided we should decide exactly how, even if it worked, Lucas and Kanade would help us to correct Copterix’s drift.
As we have 10 frames per second when processing the algorithm, it will be really difficult to determine in real time if we actually corrected the drift whenever we would want to correct it, and that is why we imagined the following algorithm:

  1. wait for Copterix to be horizontal (pitch and yaw < epsilon)
  2. take a reference picture and search the good features to track on it (quite heavy operation)
  3. while Copterix is horizontal (pitch and yaw < epsilon)
  4. ____take a picture, compare it with reference
  5. ____if not horizontal (pitch and yaw >= epsilon)
  6. ______wait for Copterix to be horizontal (pitch and yaw < epsilon)
  7. ______go to 3.
  8. ____if drift is big enough (move size > threshold)
  9. ______go to 12.
  10. ____if we don’t find enough features to track
  11. ______go to 1.
  12. ask PID to incline Copterix toward the good direction (we have to decide an angle)
  13. wait a chosen time (we have to be over-precise on this data)
  14. ask PID to set Copterix horizontal
  15. go to 1.

The real difficulty of this algorithm is that it infers we do own a powerful and precise PID, able to remain horizontal most of the time, and to follow an order in the better and faster possible way, which is of course not true.

That is why we are now considering the fact that we may not have time to have a excellent PID AND implement such a precise algorithm; we will talk about it tomorrow with our teachers.

IRL : firsts tests with the real laser

Real laser

Today we replaced the oscilloscope by the real laser. As expected, it does not exactly work the same way, but our first test with « The Riddle » is not so bad. You can see it on the video below, it is little as we do not have a lot of space in the classroom. You can see that the image is blinking, this is partly due to our code, but also partly due to the camera sync, and the « real » result is cleaner than what can be seen here.

FPGA design

The new design suggested by our teachers has been implemented, except for the FIFO which for the moment does not use the internal RAMs This will normally be done tomorrow. The FIFO, as it is now sometimes, leads to some bugs that we do not really understand yet. We will also investigate those issues tomorrow. Nevertheless, we have a functional design, the one we used tonight to make the video.

Tweet to ILDA

Concerning the way we will display tweets, Sam suggested us to make a smooth horizontal scrolling. Our first idea was to generate a big ILDA image containing the whole tweet on one line, and to clip it at display time, just before sending it to the laser. It seems that is was not the best way to act. So, we are now trying to generate an ILDA animation corresponding to the scrolling with a Python script. We are on our way and we have yet disclosed a few points of intersert to change in our design to make it work soon.

Web interface

The library we mentionned last time (libmicrohttpd) seems to fit quite well with our needs. It is not a complete Web server, but it is enough to make the card serve a static HTML page and a little REST API to get tweets and validate them. The authentication is for the moment very basic it consists in a « secret » token as segment of the URI. It is not very secure, but it is not our priority at the very moment.

MB Led : PSSC pour ces trois prochaines semaines

Suite à la demande d’Alexis et Samuel, nous ajoutons des garants pour nos prochaines étapes:

- Contrôle de la matrice de LED.                                                      => 15 avril (Benjamin)
- Élection de leader sur un ensemble de bloc.                                    => 15 avril (Guillaume)
- Affichage d’une image sur un ensemble de bloc.                              => 18 avril (Benjamin)
- Lecture de données sur la SD Card.                                               => 18 avril (Cédric)
- Détection de la rotation d’un bloc (gauche, droite, demi-tour)            => 20 avril (Guillaume)
- Mise à jour du firmware via IrDA fonctionnelle                                => 24 avril (Cédric)
- Possibilité de jouer au morpion sur 3×3 blocs                                 => 26 avril (Benjamin)

[CASPER] Beagleboard, pilotes et pwm

Voici un petit compte rendu de ce que Thomas et moi-même avons réalisé hier et aujourd’hui.

 

Bootstrap

Partant de ce que Thomas avait réalisé précédemment, nous avons automatisé l’installation de la carte SD pour la beagleboard. En effet, celle-ci doit contenir dans une première partition FAT les fichiers du noyau nécessaires au démarrage, et sur une deuxième partition du format de notre choix la racine du système de fichiers.

Afin de pouvoir choisir plus finement quel noyau et quel paquets nous souhaitons installer sur notre beagleboard, et pour pouvoir la placer rapidement dans une configuration « prête à utiliser » lors d’une éventuelle réinitialisation, nous avons choisi de ne pas utiliser les images de rootfs proposées sur internet par la communauté de développeurs beagleboard.

Nous avons donc construit notre propre image rootfs à l’aide de l’outil debootstrap couplé à l’émulateur qemu, ce qui permet de créer sur un ordinateur portable classique une distribution pour une architecture arm, par exemple. Nous avons inclus de nombreux paquets tels que la bibliothèque opencv qui nous sert pour le traitement de l’image, et SVOX pico, qui nous sert pour la synthèse vocale.

Nous avons ensuite configuré la distribution afin d’obtenir une console sur le port série et paramétré la distribution afin de la rendre directement utilisable.

Ces étapes ont été totalement automatisées dans un script, ce qui nous permettrait éventuellement de regénérer tout ceci très rapidement, tout en faisant évoluer nos paramètres.

Nous avons ensuite généré les fichiers de boot à partir du noyau de sorte qu’il supporte le système de fichiers nilfs2¹ (Le garbage collector du nilfs2 sera lancé automatiquement, dès lors que les paquets nilfs-tools et nilfs2-tools sont installés sur le système. Il faut donc les ajouter dans le script debootstrap_init.sh).

 

Le système de fichiers nilfs2 offre en résumé deux avantages : sa structure garantit l’intégrité des fichiers écrits ce qui évite la corruption de la carte en cas de coupure de courant ou de plantage et il offre d’excellentes performances sur la carte SD en comparaison avec l’ext2 par exemple.

Cela est certainement dû à sa structure circulaire, et à son mode de fonctionnement avec garbage collector. En effet, les fichiers supprimés ne sont pas effacés immédiatement, ce qui aurait pour effet de ralentir les opérations. Ces effacements ne sont réalisés que beaucoup plus tard, à la fin d’un compte à rebours ou lorsque les segments propres sont en nombre insuffisant. Ainsi, l’écriture est rapide puisque sans effacement, et l’effacement est retardé ce qui à nouveau permet de gagner beaucoup en vitesse de fonctionnement. (L’installation de paquets logiciels est aussi rapide que sur un ordinateur moderne avec nilfs2, ce qui était loin d’être le cas avec ext2 puisqu’en fonction des dépendances, il fallait entre 15 et 60 min)

 

Ensuite, un autre script que nous avons réalisé automatise la génération d’une archive tarball rootfs.

Une version adaptée du script setup_sdcard.sh (http://github.com/RobertCNelson/omap-image-builder/blob/master/tools/setup_sdcard.sh) nous permet ensuite, là encore de manière automatisée, de formater la carte mémoire et de créer les partitions, de générer les fichiers uImage et uBoot, et enfin de copier les fichiers de boot et d’extraire le tarball rootfs sur les partitions correspondantes.

Nous avons de plus écrit une notice détaillant l’utilisation de ces scripts en vue de générer rapidement une installation pleinement fonctionnelle et incluant tous les paquets logiciels nécessaires sur la carte SD.

 

¹ Merci PHH pour les conseils !

 

 

Pilotes et PWM

Thomas continue de se pencher sur la question des pilotes. Il a réalisé un helloworld que nous ne pouvions malheureusement tester sur la beagleboard, du fait que celle-ci était immobilisée par les opérations de préparation de la carte SD. Maintenant que celle-ci est prête, nous allons pouvoir tester la compilation et l’installation dynamique de ce module de communication helloworld dans le noyau.

Étant donné que la beagleboard n’était pas prête, et outre sa participation à la création de la nouvelle distribution au travers de son expérience précédente avec la première installation que nous avions réalisée avec le script setup_sdcard.sh, Thomas a continué de se documenter sur la réalisation de pilotes et sur l’utilisation des modules PWM sur la beagleboard.

[CASPER] Reconnaissance faciale

Nous avons implémenté la détection et la reconnaissance de visages à l’aide de la bibliothèque OpenCV. Celle-ci utilise l’algorithme de Viola-Jones pour la détection et l’algorithme des eigenfaces dont nous avons déjà parlé dans ce billet pour la reconnaissance.

Nous allons donc ici expliquer uniquement l’algorithme de Viola-Jones.

Algorithme de Viola-Jones

Cet algorithme est un algorithme de boosting, c’est-à-dire qu’il classifie une zone de l’image comme visage ou non-visage à partir de plusieurs classifieurs faibles (c’est-à-dire ayant un taux de bonne classification légèrement meilleur qu’un classifieur aléatoire). Ces classifieurs faibles, inspirés des ondelettes de Haar, consistent à sommer des pixels sur certaines zones (rectangulaires) de l’image et à les soustraire sur d’autres (on trouve ainsi par exemple un classifieur faible dont le but est de détecter des yeux en sommant sur les yeux et en soustrayant entre). Afin de réduire le coût computationnel de ces sommations, Viola & Jones ont introduit les « images intégrales » : celles-ci consistent à recueillir dans chaque pixel la somme des pixels du rectangle qu’il délimite avec le pixel origine. Les classifieurs faibles sont ensuite agrégés à l’aide de l’algorithme AdaBoost.

Afin d’accélérer le traitement, l’algorithme de Viola-Jones utilise plusieurs classifieurs « forts » en cascade, et les agrège par unanimité : dès qu’un classifieur classifie une zone de l’image comme non-visage, le traitement de cette zone s’arrête et celle-ci est classifiée comme non-visage.

Un des problèmes que soulève cette méthode est que les classifieurs faibles (et donc les classifieurs forts) sont définis pour une taille de visage donnée. Or en pratique les visages susceptibles d’apparaître sur une image ont une taille quelconque. Le traitement est donc réalisé de manière pyramidale.

Un deuxième problème est l’agrégation des résultats. En effet, en faisant glisser une fenêtre de détection sur l’image, le même visage est susceptible d’être détecté plusieurs fois, pour des décalages de quelques pixels de la fenêtre. Afin de palier ce problème, l’algorithme regroupe les fenêtres se chevauchant de plus d’une certaine proportion, et en retourne une fenêtre « moyenne ».

Une des principales limitations de cet algorithme est qu’il n’est pas invariant pas rotation, ce qui impliquera de faire un prétraitement pour redresser l’image de la caméra selon la position de notre robot avant de lancer l’algorithme.

Viola-Jones et OpenCV

Plusieurs bases de classifieurs sont fournies par défaut avec OpenCV, notamment pour détecter des visages de face ou de profil. Deux bases détectent les visages de face, les bases « haarcascade_frontalface_default.xml » et « haarcascade_frontalface_alt.xml ». Nous utilisons la deuxième, car la détection est plus rapide (de l’ordre de 50%).

Nous utilisons plusieurs paramétrages fournis par OpenCV, notamment le fait de s’arrêter dès qu’un visage a été détecté, et de commencer par rechercher les visages les plus grands.

Ceci permet d’avoir des temps de détection acceptables (de l’ordre de 50ms sur un PC portable vieux de deux ans à base d’Athlon X2) quand un visage est présent dans l’image, mais beaucoup plus longs si aucun visage n’est présent (de l’ordre de la seconde). Nous pouvons donc envisager d’arrêter la recherche dès que celle-ci dépasse la centaine de millisecondes. Nous attendons cependant le portage sur beagleboard pour évaluer les temps de calcul en conditions réelles. Il existe de plus un projet d’optimisation d’OpenCV utilisant le DSP présent dans l’OMAP de la beagleboard, qu’il sera intéressant de tester.

Algorithme complet

L’algorithme complet de détection et reconnaissance donne des résultats intéressants sur PC portable, la prochaine étape étant de les tester sur beagleboard. Nous rencontrons de même un problème de latence sur OpenCV : l’algorithme se comporte en effet comme s’il existait un buffer de quatre images qui introduit un retard sur les images traitées, le problème étant d’autant plus perceptible en cas d’absence de visage lorsque le traitement de chaque image prend une seconde… Nous n’avons cependant pas encore mené de recherches approfondies sur ce problème.

MB Led: Depuis la soutenance intermédiaire…

Notre dernier article datant de mardi dernier. Je vais faire un résumé de mes avancées des derniers jours:

Mercredi et jeudi:

J’ai terminé de coder les fonctions de communications avec le driver de LED. J’ai désormais un exécutable censé afficher une image décrite pour l’instant en dur (pixels écrit un par un à la main dans un tableau). Je ne peux pas avancer plus de ce côté sans nos blocs, une fois ceux-là soudés,  je pourrais passer au debugage

Voici comment fonctionne cet affichage dans les grandes lignes:

Initialisation:

  1. On initialise la communication SPI: messages de 16 bit, fréquence d’envoi de 18MHz, LSB transmis en premier.
  2. On initialise le DMA.
  3. On initialise l’horloge qui servira de référence pour le PWM du driver.
  4. On configure les différentes luminosités pour les trois groupes de couleur (rouge, vert et  bleu)
  5. On configure la fréquence de l’interruption qui rafraichira l’affichage de l’image. Cette fréquence n’est pas définitive, elle dépendra de la puissance des LED qui influe sur la persistance rétinienne. Plus cette puissance sera grande plus on pourra réduire la fréquence de rafraîchissement. Cette fréquence ne peut donc être réglée qu’empiriquement. Pour l’instant 80KHz en se basant sur le code des GLiP.

Routine d’affichage:

Les 8 lignes sont affichées les unes après les autres. Une seule ligne est allumée à un instant donné.

L’affichage d’une ligne se fait de la façon suivante:

  1. On récupère la ligne dans l’image courante.
  2. On extrait, des pixels de cette ligne, les valeurs des 24 LED.
  3. Ces valeurs sont pour l’instant sur 4 bit, une fonction est chargée « d’étirer » ces valeurs sur 12 bits pour correspondre aux attentes du driver. C’est cette fonction qu’il faudra modifier lorsque nous déciderons d’élargir le champ de couleur disponible (pour l’instant on garde le format GLiP).
  4. On construit finalement, sous forme de 18 messages de 16 bit, le vecteur de 288 bit attendu par le driver pour piloter ses 24 sorties (24*12bit).
  5. Ces 18 messages sont envoyés en SPI par accès direct à la mémoire au driver de LED qui va afficher la ligne courante.

Vendredi et samedi:

Depuis vendredi je réfléchi à une façon de faire des mises à jour de firmware via l’IrDA. En effet si nous avons 36 blocs, dès qu’il s’agira de flasher une nouvelle version de notre code, cela s’avérera être une opération fastidieuse. Petit calcul: 30 secondes (au moins) pour flasher un bloc et 36 blocs. Soit un peu moins de 20 minutes à chaque fois!

Une organisation possible de la mémoire flash, pour la mise en place d’un système de mise à jour que je détaille plus bas, serait la suivante:



Les premières instructions du bloc Flash programmer font « sauter » en _firmware_begin.

Puis, le firmware pourrait être mis à jour de la façon suivante:

  1. Notre firmware courant s’exécute normalement sur un bloc B : affichage d’animations, jeux, etc…
  2. Nous souhaitons faire une mise à jour du firmware depuis la carte microSD d’un bloc A par exemple.
  3. En se reposant sur notre système de transmission de donné par IrDA que je ne détaille pas ici, le bloc A va d’abord envoyer une commande indiquant l’arrivé d’une mise à jour (broadcastée ou non)
  4. Un des blocs, B, recevant cette commande décide de l’accepter ou non.
  5. Si il accepte il va placer les différentes parties du firmware  envoyé par le bloc A (là encore en se reposant sur notre système de transmission IrDA gérant les problèmes de communication, les paquets corrompus, perdus etc.) en flash à partir de l’adresse _new_firmware_begin à la bonne position: _new_firmware_begin + (taille d’un paquet * position du paquet).
  6. Lorsque tous les paquets ont été reçu correctement (on peut redemander une confirmation à ce moment-là), le programme saute à l’adresse  dans le bloc Flash programmer de début de traitement de la copie.
  7. Le nouveau firmware est alors entièrement copié à la place de l’ancien.
  8. Une fois la copie terminée on retourne à l’adresse _firmware_beginn.

La mise à jour est terminée!

Je m’intéresse maintenant à l’implémentation de ce système de mise à jour ainsi qu’au fonctionnement du debugage via le port série prévu pour ça.

Référence :

Pour le flashage « in-application » : AN2557

 

Copterix : Topo sur Lucas and Kanade

L’algorithme de Lucas et Kanade

Principe

Nous disposons de deux images en niveau de gris, A et B, espacées dans le temps de δt.
Nous cherchons à déterminer les vecteurs déplacement de certains points d’intérêt, que nous pouvons par exemple soit choisir arbitrairement, soit trouver grâce à un filtre de Sobel (détection de contours), soit finalement rechercher d’une manière plus lourde mais qui donne des résultats plus efficaces que nous aborderons dans la dernière partie. Bien entendu, un grand nombre de points d’intérêt permettrait d’avoir une meilleure estimation de la vitesse globale de l’image, mais une quantité plus faible de points d’intérêt demanderait moins de ressources système et de temps de calcul : un compromis est donc nécessaire pour les systèmes embarqués.
Nous nous donnons pour cela une fenêtre de recherche pour chaque point d’intérêt trouvé de taille 2*ωx+1 par 2*ωy+1 (en nombre de pixels). Une fois encore, une plus grande fenêtre permettrait de trouver une plus grande amplitude du mouvement, mais demanderait plus d’itérations (ce problème est en grande partie pallié par la forme pyramidale, que nous aborderons par la suite).
Il ne reste plus qu’à trouver le déplacement qui minimise l’erreur :


Développements

Nous commençons donc par calculer la dérivée de l’erreur par rapport au déplacement :

pour ensuite lui appliquer un développement de Taylor à l’ordre 1 autour du déplacement [0, 0] (valide si nous estimons que le déplacement est petit , ce que nous allons admettre) :

À partir d’ici, nous pouvons arrêter les calculs pour faire quelques considérations.
Tout d’abord, l’expression A(x, y) – B(x, y) fait penser à la dérivée de l’image dans le temps au point (x, y), que nous noterons dI(x, y).
Ensuite, les dérivées partielles de B en x et en y ressemblent à un gradient. Nous pouvons de plus considérer que la fenêtre étant grande en comparaison du vecteur mouvement, la dérivée de l’image dans la fenêtre sur l’image B sera la même que sur l’image A. Nous avons donc le gradient suivant :

pour tout (x, y) appartenant à la fenêtre :
Avec ces notations, nous obtenons :

Enfin, une légère transformation nous permet d’obtenir :

Si nous nous donnons :
et

nous pouvons réécrire l’équation précédente sous la forme :

Or, ne l’oublions pas, le but de cette démarche étant d’annuler la dérivée de l’erreur afin de la minimiser, nous avons


G est inversible si le gradient de A est défini, c’est-à-dire si la fenêtre se trouve dans l’image et que nous disposons d’un contraste suffisamment élevé dans la fenêtre (se référer à la dernière partie pour un choix correct des bons pixels à suivre).

Nous avons ici le moyen de calculer le vecteur déplacement ‘le plus cohérent’ qui permet de passer de l’image A à l’image B dans la fenêtre donnée.

Itérations sur k pour affiner la recherche

Le calcul précédent représente un unique passage de l’algorithme. Nous pouvons affiner le résultat en effectuant plusieurs passages, jusqu’à ce que, par exemple, la norme du déplacement soit inférieure à une valeur que nous pouvons choisir.
Pour un indice d’itération k, si nous avons un résultat , nous transformons B ainsi :


pour calculer :

Nous voyons ici l’intérêt de calculer le gradient sur A et non sur B car ainsi nous n’avons qu’à calculer b à chaque itération.
Nous obtenons le déplacement final suivant :

Du problème des déplacements de plus grande amplitude : la mise en pyramide

Nous avons vu dans la première partie que la fenêtre ne suffisait pas à obtenir un compromis satisfaisant entre vitesse de calcul et détection des grands mouvements.
Une solution à ce problème est l’utilisation de pyramides.

Nous nous donnons m niveaux de pyramide (souvent égal à 3) et nous appliquons l’algorithme entier à chaque niveau de Lm à 0.
À chaque niveau de la pyramide, nous construisons une image de résolution 2^L fois inférieure à l’image originale.
Nous gardons la fenêtre de la même taille et transformons les coordonnées des pixels à suivre pour rester cohérent avec la nouvelle résolution.
Pour obtenir le déplacement final, il ne reste plus qu’à sommer tous les déplacements trouvés mis à l’échelle :

Voici une petite illustration du procédé :

Certains pixels sont plus faciles à suivre que d’autres

Nous pouvons déterminer les meilleurs pixels à suivre en nous basant sur l’utilisation que nous souhaitons en faire.
Ici, ce sera le calcul de l’inverse de G qui sera déterminant, il nous faut donc un déterminant non nul pour chaque pixel de la fenêtre, ou bien, pour rester plus mathématique, une valeur propre minimale maximale.
Nous pouvons donc procéder de la manière suivante :

  1. Calculer G et sa valeur propre minimale λ pour chaque pixel de l’image A
  2. Retenir la plus grande valeur λ sur toute l’image (et s’arranger pour éviter que son pixel soit trop au bord pour faciliter les problèmes de fenêtrage)
  3. Garder les pixels qui ont un λ supérieur à un certain pourcentage de ce maximum (5 ou 10 % par exemple)
  4. Parmi les pixels sélectionnés, choisir ceux dont λ est le maximum dans leur voisinage 3×3
  5. Ne garder que les pixels qui ont une distance suffisante (5 ou 10 pixels par exemple)
  6. Enfin, supprimer les pixels de λ minimal pour respecter un seuil maximal de nombre de pixels à suivre que nous nous serons fixés

Cette procédure est un petit peu lourde, d’autant plus qu’il faudrait théoriquement la répéter à chaque nouveau couple d’images à traiter, c’est pourquoi nous pouvons garder les pixels suivis d’une image à l’autre sur par exemple 10 itérations avant de les rechercher à nouveau.

Conclusion

Nous avons vu la version de l’algorithme de Lucas et Kanade implémentée en openCV. Cet algorithme se révèle facile à comprendre et à implémenter, et est personnalisable à souhait pour s’adapter aux besoins exigeants des systèmes embarqués.

Source

Pyramidal Implementation of the Lucas Kanade Feature Tracker