ELECINF344/381

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

Catégories

[Casper] Face tracking

We now have our face tracking algorithm running on BeagleBoard. Since a tracking only based on face detection was to slow and not very intuitive (you always have to look the camera), we decided to use a blob tracking algorithm, which we initialize with the face detection algorithm.

First, Casper looks for a face. When it finds one, it learns the associated color histogram. After what it tracks the histogram (with the OpenCV Camshift function), for a few tens of frames. If it does not find a face again during the blob tracking, it stops at the end of the frames. Otherwise, it keeps tracking the « blob » face.

We adopt a multithread program : a thread looks for a face every second, and a thread is responsible for blob tracking when a face is found. The first thread is used to set a counter which is decremented by the second thread.

 

RoseWheel now detects obstacles.

Yesterday we finished to implement the drivers for both the distance sensors: the infrared and the ultrasonic one. They actually work better than expected as their detection cones are a little thinner than expected.

At last, Rosewheel will come with 2 infrared sensors and 1 ultrasonic sensor. The infrared sensors will be used to detect falls and ravines whereas the ultrasonic sensor will be used to detect obstacles.

It’s not possible to link the sensors to the mainboard with a wire longer than 15cm, we will not be able to place them on the top of the handlebars to detect ravines as we previously thought. But, given the fact that the detection cone of the infrared sensor is really thinner than expected we finally conclude that we will have a sufficient range to detect ravines with sensors place on the chassis basis.

Indeed, we need a range of detection long enough as even if it could sound a bit counter-intuitive, to stop, Rosewheel needs to accelerate so that it could place back its center of gravity upright the wheels axis and then stop.

For the obstacles detection, we will use the ultrasonic sensor placed right in the middle of the chassis, with a slight upward inclination so that it doesn’t take the floor as an obstacle. As the range of detection is up to 4 meters, it will generate errors with long distance obstacles that aren’t actually on RoseWheel’s path. Thus, we have to handle only the detection of obstacles that are closer than 4 meters. We haven’t yet defined this range but we will have a clearer idea during the tests.

To be continued.

 

MB Led: Synchronization, algorithm reliability and improving IrDA transmission

Since yesterday, Guillaume worked on algorithm reliability, improving its performance and solving some problems such as information sharing (number of blocks in network, position…). Some loop-back which were over-charging the network have been deleted. He worked with Benjamin to improve the algorithm but some problems remain unsolved… In late afternoon, the algorithm was working rather well : in a 9 blocks network, blocks detected the good number of blocks, their position, the leader ID, the positions of the others in many cases. But sometimes, one block loses his IrDA connection so he has to start again the algorithm. When dividing a network in 2 networks, the blocks graph (developped with Benjamin) gives the blocks good informations.

Benjamin worked on improving the snake game, now it has a tail and if you cut it (meaning you disconnect blocks before the tail leaves) you lose. Some apples have shown their faces on the screen, but we must handle turn detection before evolving furthermore. He also worked with Guillaume on the implementation of a blocks graph in order to react faster when a block leaves the network. In fact, if a member leaves, blocks are able to calculate that every members of the branch also left. At last he tested synchronisation implemented by Guillaume displaying an animation on MB Leds, it is pretty quick and all blocks flash at once.

I have first worked on improving some aspect of IrDA like variable waiting time before a resend and size of packets in order to improve the  payload . I have continued  to implement firmware transmission and have begun testing it. Transmission seems a bit slow and tomorrow I will look for a way to improve its speed.

[Casper] Flash, Screen and Pictures…

We’ve been working these last few days on the PCB, to display pictures and to save and load them from flash.

First, we developped a set of functions to erase, write and read the flash memory, using a SPI protocol. After testing it with text strings we displayed on the screen, we tried with pictures. However, the STM32 RAM is not big enough to handle a whole picture : we have at most 20kbytes RAM, and one picture takes 25kbytes (132*132 pixels of 12 bits, 4 for each RGB channel). So we read the flash per 256 bytes blocks that we send to the LCD screen, until transfer completion. Similarly, we write flash per 256 bytes blocks when receiving a picture from the UART connection.

In order to have a simple protocol for writing pictures, we do not allow two pictures to share a same memory sector (smallest erasable area). Since each sector is 4 kbytes wide, we use 7 sectors for each picture : that’s about 3 kbytes too large. However, this allows to store 146 pictures in the flash, which should be enough for our project. We did not work yet on the possibility of storing smaller pictures which could be used to refresh a small screen area. It may be useful for animations.

Finally, we use the screen configuration options to rotate pictures by 90, 180 or 270 degrees, changing the way the screen controller reads the RAM.

Moreover, we wrote a small program which uses OpenCV library (which is already used on the beagleboard for face detection and recognition) and converts a picture (jpeg, png, bmp,…) in a 132*132 12 bits picture and saves it in a file that can be sent to the PCB by UART.

[Casper] OpenCV et Beagleboard

Aujourd’hui j’ai porté les algorithmes de détection et reconnaissance faciale sur Beagleboard, sans trop de soucis. Comme nous n’avons pas encore reçu la webcam, je me suis contenté de les tester sur des images jpeg. Les temps de traitement sont deux fois plus longs sur Beagleboard que sur mon PC, et nous allons donc certainement jouer sur la taille des images pour avoir un temps de traitement convenable.

Je me suis également penché sur le projet d’optimisation d’OpenCV utilisant le DSP de la beagleboard, mais un benchmark disponible sur le site du projet montre que le gain en performances est plus que relatif. Le seul intérêt pourrait être de décharger le processeur de certains traitements. Nous reviendrons donc vers ce projet uniquement si le besoin s’en fait réellement sentir…

Nous avons de plus reçu notre carte aujourd’hui et nous commençons donc sa prise en main.

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