Différence de trames

La différence de trames

Un flux vidéo entrelacé est une succession d'images composée de deux trames:

• une trame paire, composée des lignes paires de l'image
• une trame impaire, composée des lignes impaires.

Le flux vidéo commence par sortir la première trame (paire), puis la deuxième (impaire). Ces deux trames forment l'image qui est affichée sur l'écran de la télévision. Mais il ne faut surtout pas croire que ces deux trames appartiennent à la même image !!! Elles sont décalées dans le temps.

Par exemple, pour un flux vidéo PAL à 25 images/secondes, il vaut mieux parler de 50 trames/seconde : chaque trame est photographiée tous les 1/50 de seconde. Une conséquence de ceci, est que pour une scène en mouvement, les objets qui bougent se sont déplacés d'une trame à l'autre.

Ceci est illustré sur l'image suivante, extraite d'une vidéo capturée par notre caméra.  On a décomposé l'image en ses deux trames. Mon bras, en mouvement, n'a pas la même position sur les deux trames (regardez juste sous le bras).

Pour la petite histoire, la reconstruction d'une image à partir de deux trames consécutives n'est donc pas si facile que ça... Cette opération est appelée désentrelacement (deinterlace) dans le monde de la vidéo, et la meilleure façon de le faire consiste à estimer les déplacements des objets dans les trames et à re-créer leur position dans les lignes manquantes.

Pour nous, l'entrelacement est bien pratique : si une balise clignote à la fréquence image, elle sera donc présente sur une trame, et absente sur la suivante. Il nous suffit donc de comparer pixel à pixel deux trames successives : en soustrayant de chaque pixel sa valeur dans la trame précédente, on obtient comme image résultante seulement ce qui a changé. C'est-à-dire la balise.

Conséquence sympathique : un projecteur, même extrêmement fort, ne nous brouillera pas s'il est constant (s'il ne clignote pas).

Conséquence moins sympathique : ça ne marche pas...

Les problèmes commencent

Les problèmes commencent !

Tout ceci est bien beau, mais on a oublié un détail important: on compare deux trames successives. Or deux trames successives ne représentent pas exactement la même chose : elle sont décalées non seulement dans le temps, mais aussi dans l'espace (d'un pixel en vertical) ! Cela peut sembler négligeable, mais c'est en fait
beaucoup.

Prenons un cercle blanc fixe sur fond noir :

 

D'après ce qu'on a dit plus haut, il devrait être éliminé lors de la différence de trame.

Examinons de plus près, en zoomant sur une partie du cercle. Pour plus de clarté, on a représenté en rouge les lignes impaires, en vert les lignes paires.

 

	Trame impaire du zoom
Zoom sur une partie du cercle	Trame paire du zoom

 

Superposons les deux trames, et faisons la différence pixel à pixel (les pixels résultant sont blancs si la différence n'est pas nulle, noirs sinon).

 

Superposition des trames Bien que faisant partie de la même image, étant décalées d'un pixel vertical, elles ne se superposent pas exactement...	Résultat de la différence de trames On détecte un objet alors qu'on ne devrait rien voir !!!

 

Ce phénomène se produit aux frontières d'objets. Et plus la frontière en question est horizontale, plus le nombre de faux pixels est grand.

On pourrait penser les éliminer par un filtrage adéquat (vertical sur un pixel), mais cela ne marcherait pas pour des objets en forme de peigne (du genre un peigne vertical). Il faut donc revoir à la base notre principe de différence de trame...

On recommence

On recommence...

L'effet indésirable vu ci-dessus vient du fait qu'on compare deux scène décalées physiquement (d'un pixel en vertical), donc qui n'ont rien à voir. Il faudrait comparer deux vues physiquement semblables, qui ne différent que dans le temps. Autrement dit, on va devoir faire non pas de la différence de trames, mais de la différence d'images.

Le problème est que la fréquence des images est deux fois plus faible que celle des trames. On pourrait faire clignoter la balise deux fois plus lentement, soit à 15Hz, mais :

• ça fait mal aux yeux, les caméras de télévision risquent de ne pas aimer, les spectateurs non plus
• ça double le temps d'acquisition de la position de la balise, qui est déjà long (cf. plus loin)...
• ça nécessite de stocker deux fois plus de pixels, et :
  • nos cartes sont limitées en RAM vidéo (rappel : on n'a pas de PC embarqué et autres PC104, nos cartes on les fait nous même, avec des vraies contraintes de systèmes embarqués...)
  • bon d'accord, on a quand même assez de RAM vidéo, mais bon, si il y a une solution meilleure, pourquoi gâcher ?
  • et puis, on aimerait bien garder la RAM vidéo externe pour d'autres traitements. Si on peut se contenter de la RAM interne au FPGA c'est mieux.
  • OK, on pourrait ne stocker et travailler que sur une trame sur deux. Mouais, reste quand même le clignotement à 15 Hz désagréable...

Pour travailler sur des images en gardant la même fréquence des balises et sans avoir à stocker des images entières, le seul moyen est d'augmenter la fréquence image. Par chance, la caméra OV7620 dispose d'un mode d'acquisition à 60 images/seconde : le QVGA à 60 images/seconde.

Dans ce mode-là, la caméra ne sort qu'un pixel sur deux en horizontal (ce qui divise la résolution horizontale par deux, mais ça ne pose pas de problème en pratique), et seulement les trames impaires (mais à une fréquence de 60Hz). Bingo, c'est exactement ce qu'on veut !

Principe de la détection

On récapitule le principe...

On récapitule: une balise émet à 30Hz. On la filme à 60 trames par seconde (en QVGA). On prend deux trames successives, on les "soustrait" l'une de l'autre. Ce qui a changé, c'est probablement la balise.

Il y a quand même un problème : le "probablement"... Parce que d'autres choses que la balise peuvent changer entre les trames :

• le robot adverse peut passer dans le champ de la caméra (si si, il y en a qui bougent !!!)
• on peut avoir dans le champ des spectateurs, un arbitre, un objet qui roule
• on peut se choper un flash
• et en plus, il y a des projecteurs. Heureusement, ils fonctionnent sur le secteur (50Hz), et le filament reste allumé même entre les alternances. Pour la caméra, ils sont globalement constamment allumés (c'est aussi un peu pour ça qu'on fonctionne à 60Hz, et non 50Hz)
• par contre il y a aussi de néons (dans les salles d'homologation et dans nos locaux). Eux, par contre, ne sont pas du tout constants. La caméra les voit très clairement clignotants...

En d'autres termes, on ne peut pas se contenter seulement de regarder ce qui a changé entre deux trames successives.

Par chance, les changements de la balise ont une bonne propriété : ils restent à la même place plusieurs trames de suite, pour peu qu'on regarde la balise assez longtemps. Ce qui n'est pas le cas des autres objets (à un détail près qu'on réglera plus tard) qui clignoteront sur deux trames, peut-être trois, mais pas beaucoup plus. On peut donc modifier notre algorithme : un point changeant appartiendra à la balise s'il change régulièrement sur plusieurs trames de suite. Le "plusieurs" reste encore à définir... Pour nous, ce sera un seuil réglable, qu'on essayera de prévoir et qu'on affinera lors des tests.

Ce système permet d'éliminer la plupart des objets mobiles. Par contre il n'élimine pas les néons, qui clignotent assez longuement. Pour éliminer les néons, on tire partie du fait que la caméra filme à 60Hz alors qu'ils clignotent à 50Hz (oui, le 60Hz, ce n'est pas un hasard...). A cause des fréquences différentes, le néon ne sera vu clignotant que par intermittence. C'est cette rupture de clignotement qui va nous permettre de dire que ce qu'on voit n'est pas la balise mais un néon. En d'autres termes :

• si ça clignote pas, c'est un objet immobile,
• si ça clignote presque pas, c'est un objet mobile,
• si ça s'arrête de clignoter de temps en temps c'est un néon,
• si ça clignote en permanence, c'est la balise.

Ah mais oui mais non : la caméra a son propre quartz (27MHz). Celui des balises aussi. Les quartz ont des tolérances non nulle, et leurs fréquences ont la sale manie de changer en fonction de la température... La balise va donc clignoter à une fréquence légèrement différente de la fréquence trame de la caméra. Et comme pour les néons, mais moins souvent,leur clignotement s'arrêtera par intermittence. Il va donc falloir définir précisément le seuil : suffisamment haut pour ne pas prendre des néons pour des balises, suffisamment bas pour ne pas prendre la balise pour un néon.

Pour rendre la discrimination néon / balise plus fiable, on peut aussi modifier un peu l'algorithme : on attribue à chaque point un coefficient de confiance (plus il est grand, plus il y a de chance pour qu'il appartienne à une balise). Si on voit le point clignoter, on incrémente ce coefficient. Si on le voit s'arrêter, on le décrémente. Comme les néons s'arrêtent plus souvent de clignoter que les balises, il faudra décrémenter plus fort que ce qu'on incrémentera.

Ce qui nous donne cet algorithme :

1. si le point clignote : indice[point] += a1;
2. s'il s'arrête de clignoter, indice[point] -= a2;
3. si indice[point] > seuil_confiance, alors il appartient à la balise

Reste à définir a1, a2 et seuil_confiance. On partira de valeurs théoriques qu'on affinera par la pratique.

Deux trames consécutives : la balise est clairement identifiable, la lampe à sa gauche sera ignorée

Enfin dernier point, il va falloir traiter avec les particularités (défauts) de la caméra. C'est l'objet de la prochaine section (et c'est là qu'on voit pourquoi on a pris une OV7620 et pas autre chose).

Problème des caméras

Problèmes des caméras et solutions

Filtrage

Les caméras CMOS, comme toutes les caméras, ont des problèmes de bruit. Il y a plusieurs sources de bruit possibles (cf google pour la liste complète), qui se manifestent différemment :

• un même pixel peut avoir une valeur légèrement différente sur deux trames consécutives
• des pixels peuvent prendre aléatoirement des valeurs complètement fausses
• ....

Le mécanisme de coefficient de confiance se charge du deuxième cas. Il reste le premier à régler. De plus, pour séparer plus facilement deux balises, on peut en prendre une verte et une rouge (ou comme nous, une jaune avec un point vert au centre en opposition de phase). Une étape de filtrage de l'image reçue (avant traitement) est donc bienvenue :

• première possibilité, filtrage effectué au vol : on ne garde que les pixels dont l'intensité est supérieure à un certain seuil. Ce filtrage pose un problème pour les objets faiblement illuminées, qui tombent pile à la limite. A cause du bruit, ils peuvent être vus au dessus du seuil lors d'une trame, et en dessous à la suivante, simulant un clignotement. Par contre, il est plus simple à implémenter que le deuxième (ci-dessous), et nécessite moins de RAM. C'est celui que nous avons choisi, les effets négatifs étant en pratique inexistants.
• deuxième possibilité, filtrage effectué aussi au vol : pour savoir si un point clignote au pas, il faut qu'il ait changé "beaucoup" (deuxième seuil). On garde donc en mémoire la valeur du pixel en question à la trame précédente, et pour le définir comme clignotant il faut qu'il ait varié de plus qu'un certain seuil en valeur absolue. Inconvénient : nécessite de garder la trame précédente en mémoire...
• troisième possibilité, filtrage effectué par la caméra : comme la balise crache bien, on ne garde que les éléments les plus puissants. Autrement dit, on règle le gain au minimum (0). Ainsi on ne garde que les projecteurs, les flashs, les lampes, et les balises.

La caméra dispose de plusieurs moyens de régler l'intensité reçue : des registres de gain (0x01, 0x02, 0x03, 0x0C, 0x0D, ...) et un registre de contrôle d'exposition (0x10). Le fonctionnement des registres de gain est évident, celui d'exposition l'est moins. Il va falloir entrer dans le fonctionnement des caméras CMOS (en plus, ça expliquera beaucoup de problèmes de certaines équipes).

Exposition glissante

Le principe de fonctionnement des caméras peut être résumé ainsi : chaque pixel de la matrice photo-sensible est pré-chargé. Puis il est exposé à la lumière pendant un temps fixe (appelé temps d'exposition, généralement exprimé en fraction de secondes ou en lignes). Au bout de ce temps, l'exposition est terminée (voir après comment), et les pixels sont transmis à l'extérieur.

Il existe deux principaux moyens pour faire en sorte que les pixels soient tous exposés le même temps :

• les obturateurs mécaniques ou synchrones (généralement mécaniques)
• les obturateurs glissants, électroniques (rolling shutter).

La plupart des caméras CMOS bas prix sont équipées d'obturateurs glissants. Leur principe est simple : imaginons que le temps d'exposition soit de 10 lignes [dans la suite, on part du principe qu'on lit toutes les lignes les unes après les autres (progressif), alors qu'en mode entrelacé on ne lit en fait qu'une ligne sur deux (les impaires puis les paires)] : chaque ligne, avant d'être lue, est remise à zéro (pré-chargée) 10 lignes auparavant. 10 lignes après (soit le temps d'exposition) elle est lue et transmise à l'extérieur. Autrement dit :

• pendant qu'on lit la ligne 34, on expose les lignes 35 à 44, et la ligne 45 est remise à zéro,
• une ligne plus tard, on lit la ligne 35, on expose 36 à 45, et la ligne 46 est remise à zéro,
• une ligne plus tard, on lit la ligne 36, on expose 37 à 46, et la ligne 47 est remise à zéro,
• etc...

On a donc une fenêtre glissante d'exposition qui parcourt l'image. Chaque ligne entrant dans la fenêtre est remise à zéro, et lue lorsqu'elle en sort.

Le temps d'exposition (délai entre la remise à zéro et la lecture) peut varier entre 1 ligne et 1 image. Ce mécanisme a comme avantage de ne pas nécessiter de pièce mécanique en mouvement (obturateurs mécaniques), et une architecture des pixels photo-sensibles simple (3 transistors contre 4 pour les obturateurs électroniques synchrones). Leur inconvénient est que chaque ligne fournit une information décalée dans le temps : une barre verticale se déplaçant horizontalement sera vue de biais (car le bas de l'objet sera vu plus tard que le haut).

Ce mécanisme d'exposition a une importance pour nous : rappelons-nous que les fréquences caméra et balise sont légèrement décalées. Autrement dit, l'instant où la balise change d'état (s'allume ou s'éteint) se décale lentement dans l'image. Imaginons que la balise soit vue d'assez loin pour qu'elle entre entièrement dans la fenêtre d'exposition.

• Si la frontière est au milieu de la fenêtre d'exposition, la balise sera vue à moitié allumée et à moitié éteinte, soit une intensité de 50% sur une trame, 50% sur la trame suivante.
• Si la frontière est au tiers de la fenêtre d'exposition, la balise sera vue avec une intensité de 33% (et 66% sur la trame suivante).
• Si la frontière est au dixième de la fenêtre d'exposition, la balise sera vue avec une intensité de 10% (90% sur la trame suivante).

Autrement dit, au fur et à mesure du décalage de la frontière, la balise va être vue allumée, puis lentement décroissante, puis éteinte, puis lentement croissante. Plus la fenêtre d'exposition sera grande, plus le temps de transition (de allumée à éteinte) sera grand. Et pendant ce temps de transition, la balise est vue allumée sur plusieurs trames successives, mettant notre algorithme par terre...

Cette vidéo illustre bien ce phénomène : on a filmé une balise avec différents temps d'exposition, et on a capturé le flux vidéo en séparant les images paires et impaires. On voit bien que plus l'exposition dure longtemps, plus la balise clignote de façon molle... Il nous faut absolument une balise qui clignote franchement, soit un temps d'exposition le plus faible possible. On prendra donc le minimum : 1 ligne (0x00 dans le registre 0x10, en ayant désactivé le contrôle automatique d'exposition bien sûr). Sur la vidéo, la balise devient presque invisible car les gains sont en plus mis au minimum (0x00 dans 0x00, 0x01, 0x02 et 0x06).

Au passage : une durée d'exposition faible assombrit la scène. C'est pour cela que la balise dispose de LED haute-luminosité !..

Résultats

Expérimentation et résultats

Voici quelques vidéos  de la détection de balise avec l'algorithme numéro 1 :

You are missing some Flash content that should appear here! Perhaps your browser cannot display it, or maybe it did not initialise correctly.	Exposition longue. Pour contrebalancer l'effet décrit plus haut, on est obligé de mettre un coefficient de seuil de confiance très haut. D'où le lag (retard) à la détection.
You are missing some Flash content that should appear here! Perhaps your browser cannot display it, or maybe it did not initialise correctly.	Exposition de 8 lignes, a1 = 1, a2 = 2, seuil = 8 trames. Ni le néon ni la lampes ne sont détectés. On note quand même un retard à perdre les zones. a2 est donc un peu faible
You are missing some Flash content that should appear here! Perhaps your browser cannot display it, or maybe it did not initialise correctly.	Ici on a regroupé les deux images en une. Les coefficients sont corrects, la balise est bien détectée, le reste non. Le léger lag est normal (par construction).
You are missing some Flash content that should appear here! Perhaps your browser cannot display it, or maybe it did not initialise correctly.	Exposition 2 lignes. Coefficient a1 et a2 minimum. La balise est détectée rapidement.
You are missing some Flash content that should appear here! Perhaps your browser cannot display it, or maybe it did not initialise correctly.	Exposition longue, coefficient a1 et a2 mal réglés !
You are missing some Flash content that should appear here! Perhaps your browser cannot display it, or maybe it did not initialise correctly.	Exposition plus courte, mais a2 est mal réglé, le seuil de confiance aussi (on détecte trop de choses)

  Il ne reste plus qu'à implémenter tout ça dans un FPGA (ça fera l'objet d'un prochain tutorial) et à trianguler !..

Fichier attaché	Taille
demo_balises1.avi	1.63 Mo
demo_balises2.avi	1.77 Mo
demo_balises3.avi	1.24 Mo
demo_balises4.avi	796 Ko
demo_balises5.avi	681 Ko
demo_balises6.avi	613 Ko

Résumé

On résume tout ?

Deux possibilités d'algorithmes, selon le filtrage qu'on souhaite effectuer. Pour chaque algorithme, l'indice de confiance sera pris sur 6 bits.

Algorithme 1 (avec seuillage absolu)

1. La caméra est réglée (en I2C) à un gain faible, temps d'exposition minimum, mode QVGA, 60 images/seconde (trames impaires seulement)
2. pour chaque pixel :
   1. s'il est supérieur à un seuil, on le déclare allumé, sinon on le déclare éteint
   2. on stocke sa valeur quelque part ("allumé" ou "éteint", donc sur 1 bit)
   3. on compare cette valeur à celle de la trame précédente (XOR)
      1. si le point clignote : indice[pixel] += a1;
      2. s'il s'arrête de clignoter, indice[pixel] -= a2;
      3. si indice[pixel] > seuil_confiance, alors le pixel appartient à la balise et on le stocke quelque part

Cet algorithme nécessite de stocker pour chaque pixel son indice de confiance (6 bits), sa valeur (allumé ou éteint, sur 1 bit), et s'il appartient à la balise ou non, soit 8 bits/pixel.

Algorithme 2 (avec seuillage différentiel)

1. La caméra est réglée (en I2C) à un gain faible, temps d'exposition minimum, mode QVGA, 60 images/seconde (trames impaires seulement)
2. pour chaque pixel :
   1. on stocke ce pixel
   2. on le compare à sa valeur à la trame précédente. Si la valeur absolue de la comparaison est plus grande qu'un seuil, le pixel a clignoté.
      1. s'il a clignoté : indice[pixel] += a1;
      2. s'il n'a pas clignoté, indice[pixel] -= a2;
      3. si indice[pixel] > seuil_confiance, alors le pixel appartient à la balise et on le stocke quelque part

Cet algorithme nécessite de stocker pour chaque pixel son indice de confiance (6 bits), son intensité (5 bits significatifs), et s'il appartient à la balise ou non (1 bit), soit 12 bits / pixel.

Il ne reste plus qu'à les implémenter dans le FPGA (Stratix d'Altera). On présente ici le deuxième algorithme, le premier est laissé en exercice au lecteur :)