Caliban Project - Recherche de composantes

Introduction :

S’il est une question qui revient souvent au sujet de Caliban ces temps ci, c’est bien celle concernant le fonctionnement de son système visuel. De fait, afin de satisfaire les esprits les plus curieux, nous avons décidé de divulguer la méthode utilisée pour isoler les composantes d’une image. Notez que les procédures de recherche de mouvement et de reconnaissance de formes feront l'objet de pages indépendantes. Les acquis de ces 3 systèmes étant synthétisés et mis corrélés dans la partie "traitement visuel général". Ces 3 processus, une fois rapprochés, permettent d'aboutir à la définition et l'analyse de l'environnement suffisement précise et pertinente pour être exploitée par un système cognitif .

Ainsi, la recherche de composantes visuelles n'étant pas à proprement parler un processus cognitif mais un système d'acquisition d'image, nous avons estimés que ces explications ont plus leur place dans la rubrique "Corps" que "Cognition".

Pour des raisons de praticité rédactionnelle, les images utilisées pour cette démonstration ne proviennent pas du système de Caliban mais sont des images retravaillées à l’aide de sous programmes ayant concourus à l’élaboration du système principale. La raison à cela est bien simple ! En effet, lors de l’élaboration de ce processus, les images étaient travaillées en mode « visuel » afin que le développeur puisse suivre aisément la progression du traitement afin d’y apporter les corrections nécessaires. Une fois le processus parfaitement au point, celui-ci à été adapté pour fonctionner uniquement en mémoire. En effet, l’adressage des pixel est très gourmant en temps CPU de sorte qu’implémenter tel quel le processus dans Caliban aurait empêché tout traitement en temps réel. Ainsi, l’adressage des pixels a été avantageusement remplacé par une lecture exploitant la méthode Scanline (beaucoup plus rapide mais plus complexe d’utilisation) chargeant directement en mémoire une version « numérique » de l’image. Comprenez "numérique" le fait que l’image n’est plus un fichier « visible » mais un tableau dynamique dans lequel des « chiffres » représentent les différentes couleurs (matrice RGB pour les connaisseurs). Or le traitement de tableaux dynamiques, couplé à une méthode de lecture Scanline procure des temps de réponses tout à fait satisfaisant pour du traitement en temps réel sur des images jusqu’à 1280*1024.

De fait, vouloir tirer des exemples de ces matrices est pour ainsi dire impossible. C’est donc pour cette raison que les images de cette démonstration sont issues des programmes originaux (de recherche ?!) et non des processus optimisés pour Caliban.

L’essentiel est que l’algorithme dans son ensemble soit saisi. Le reste n’est qu’affaire de programmeur et une infinité de moyen de mise en œuvre peuvent s’appliquer dessus (système, langage, procédures…etc.).

Afin de rendre notre exposé plus ludique, nous avons décidé de faire un petit clin d’œil au projet Robot-Cub qui a toute notre admiration et dont les objectifs se rapprochent de ceux du projet Caliban, aux ressources disponible pret. Nous allons donc décrire le fonctionnement du système visuel de Caliban via la photo de Cub ci-dessous :

Cette photo, que nous avons scandaleusement copiée sur le site http://www.robotcub.org/ , a été légèrement modifiée afin de correspondre aux images acquises par Caliban tant en terme de taille que de luminosité ou encore définition. Il est donc temps de rentrer dans le vif du sujet…

La recherche de contour

A chaque fois qu’une image est émise par une des webcams de Caliban, un procédure se lance afin de convertir ladite image en chiffre. En effet, chaque nuance de couleur se traduit (informatiquement) par les trois composantes que sont le Rouge, le Vert et le Bleu (RGB pour red-green-blue) ; Chacune de ces composantes peut prendre une valeur comprise entre 0 et 255, 0 étant l’absence de la composante et 255 la saturation de cette dernière. Ainsi, il est possible, à partir d’un tel système de « coder » 256*256*256 couleurs différentes soit plus de 16 millions de teintes. La seule chose est que travailler sur un tel niveau de définition ne présente pas grand intérêt car il est justement trop précis et les amplitudes de variation de couleur d’un pixel à l’autre, dans leur ensemble, peu significatives. Or il se trouve que les webcam de Caliban perçoivent particulièrement bien la composante Rouge à luminosité normale (les détails sont plus marqué qu’avec les autres composantes). En conséquence, ce qui est à l’origine un « défaut » des caméras (les images semblent plus rouge qu’en réalité) devient ici un avantage. En effet, pourquoi s’embarrasser des autres composantes alors que la seule rouge nous permet d’avoir une approximation correcte de l’image originale. Pour résumer, nous pouvons considérer que l’image originale est transformée en noir&rouge. Notez qu’une multitudes de procédures disponibles sur Internet (et ce dans tous les langages) permettent de décomposer une image en matrice RGB. considéront ll'exemple d'une image de forme carré constituée de 9 pixels. Cela pourrait correspondre à ceci :

Pixels de couleur de l’image originale / Pixels de composante rouge

En fait nous venons d'effectuer la conversion d’un bitmap (image a code couleur unique) en une matrice RGB dont seul le code rouge a été gardé. Dans cet exemple, on peut très bien imaginer que le marron de l’image d’origine soit des cheveux et le jaune un magnifique soleil. En composante rouge, cela ne signifie plus grand-chose mais l’information du changement de teinte reste bien présente tout en passant d'un système de définition en base 16 000 000 à seulement 256 (de 0 a 255 il y a bien 256 valeurs)... Un sacré gain :) Bien que cette image soit parlante, en réalité, ce qui est stockée en mémoire n’est pas un pixel rouge mais un chiffre décrivant exactement la saturation de la couleur rouge. il est donc plus exact de représenter la chose comme suit :

Vous voyez donc que nous avons à présent un beau tableau dynamique contenant plein de chiffres (représentant le poids de la couleur rouge sur l’image initiale) et sur lequel nous allons pouvoir faire tourner des super procédures de tueur. Inutile de préciser que les temps de réponses sont incomparables…

Avant de continuer, précisons juste que dans la réalité, ce tableau est beaucoup plus grand. Si l’image est en 1024*768, alors il aura 1024 colonnes et 768 lignes. Ca coule de source ;) Passons à la suite... Une fois ce tableau chargé, chaque case, de façon récursive, va être pointée et comparée aux 8 cases qui l’entourent. Prenons la cas de la case centrale de notre mini matrice de démonstration. Nous allons tenter de calculer une moyenne de variation des teinte entre son voisinage et ellle. Pour cela, le taux de variation va être calculée de la façon suivante :

(ABS(254-250)+ ABS(254-116) +ABS(254-145) +ABS(254-132) +ABS(254-7) +ABS(254-244) +ABS(254-15) +ABS(254-252) ) / 8

Soit :

(4+138+109+122+247+10+239+2)/8 = 109 (où ABS désigne la valeur absolue)

Ainsi dans notre exemple, pour le pixel central, le taux moyen de variation est 109 grade sur 256. Imaginez à présent que nous répétions l’opération à l'identique pour toutes las cases du tableau, puis que nous additionnions tous les résultats pour, in fino, le diviser par le nombre de cases du tableau ; Nous obtenons, en procédant de la sorte le taux de variation général de l’image entière.

Partons du principe que le taux de variation moyen de l’image exemple est 85 (car le pixel central de notre exemple est sur une ligne de contraste et n'est donc pas forcément représentatif de l’image). C'est a ce moment qu'une autre procédure entre en action et scanne à nouveau le tableau… Si l’écart entre une case est celles qui l’entourent (même méthode d’analyse que pour obtenir la moyenne) est supérieur à la moyenne de l'image, alors le pixel est noté comme étant un point de rupture. Or, dans le cas du pixel central de notre exemple, 109>85 donc la case centrale de notre tableau est bien un pixel de rupture. Au final, nous obtenons un tableau de la forme :

Où 1 signifie qu’une point de rupture a été trouvé et 0 non… mais en réalité nous trichons un peu car dans un tel tableau, nous ne pouvons travailler que sur le pixel central ! L’internaute admettra que d’autres cases entourent chaque case de bordure de l'exemple et ayant chacune le « poids » que celle qu’elle borde. Au final, pour l’image de notre robot Cub, et si nous traduisons sous forme d’image les 0 en blanc et les 1 en bleu, cela donne :

Précisons toutefois que pour Caliban, ces procédures seules ne sont pas suffisantes pour isoler les contour d'un objet… En effet, Caliban est capable de savoir si sont système visuel renvoit trop ou pas assez de contour… Comment ? Et bien, vous verrez en dessous qu’il est capable d’isoler les composantes de l’image (telle la tête du petit Robot-Cub). Or l’efficacité du procédé décrit plus bas dépend directement de la finesse et de la pertinence des contours. Un seuil moyen trop élevé et les contours ne seront pas suffisamment marqués (image très blanche) pour isoler les primaires (composantes de l'image) et, de la même façon un seuil trop faible fournira lui aussi peu de primaires (image très bleu). Ainsi donc, Caliban travaille en pourcentage de la valeur moyenne de taux de variation de l'image. dés lors, si peu de composantes de l’image sont détectée et que cette dernière est majoritairement bleue, Caliban augmente le pourcentage appliqué a la moyenne : nous avions dit (dans notre exemple) que le taux moyen est de 85 grade... Dans ce cas, Caliban prendra 105 % de la moyenne soit 89 grades et, si cela n’est pas suffisant, 110 % et ainsi de suite… Dans le cas contraire, (si trop de blanc est détecté et pas assez de primaires renvoyées), alors il prendra 95 %, 90 %... etc de la valeur moyenne. Il ajuste donc sa vision en fonction des acquisitions précédentes ; c’est un peu comme quand vous plissez les yeux parce que vous voyez flou ;)

Recherche des composantes de l’image (Primaires de l’image)

Arrvivé à ce stade du traitement de ll'image, nous avons donc un magnifique tableau, rempli de pleinde 0 et de 1 décrivant les « cassures » de tonalité de l’image et donc par la même, les contours d’un objet ou d’une partie d’un objet. Reste a trouver un moyen d’isoler chacun des ces « objets » des autres et du reste du décort.

Et bien la méthode est très simple et est connue de tous pour la simple et bonne raison que tout le monde à utilisé un jour ou l’autre la fonction « floodfill »… mais qu’est ce donc que ce terme barbare ? Allez, vous appelez cela le « remplissage » sous Paintbrush, vous savez, le petit pot de peinture !!! Pour ceux qui ignore de quoi il sagit, cette fonction permet de remplir toutes les cases d’une même couleur et se "touchant" avec une autre couleur… Et figurez vous que seulement avec cela, on obtient des merveilles :)

En fait, il convient de scanner à nouveau notre tableau, case à case, à la recherche de 0, puis dés que la procédure en rencontre un, le remplace par 2 et effectue un floodfill dessus afin que toutes les cases concomitantes et étant marqué de 0 soient remplacées elles aussi par 2. Ainsi, toutes les cases qui, à la suite du pointage d’un 0 particulier, on été remplacées par un 2 appartiennent, de facto, à un même objet et/ou entité délimitée par des contours (valant 1 et donc n’étant pas remplacé par 2 durant le floodfill). Plutôt qu’un long discours, un bref exemple est bien plus parlant. Pointons le pixel immédiatement en haut a gauche de la photo de Cub. Si nous admettons que 0 = blanc, 1= bleu et 2=rouge, cela donne :

Alors oui, le résultat ne décrit pas grand-chose mais cette « composante » ou « primaire » de l’image est malgré tout isolé et stockée en mémoire un bref instant avant qu'un certain nombre de filtres ne le mette de coté (ces filtres sont expliqué plus bas); Mais ce n’est pas elle qui nous intéresse et vous allez voir pourquoi ; Continuons notre lecture du tableau vers la droite jusqu’au prochain 0 rencontré ; cela donne :

Et hop ! un autre petit bout sans intérêt qui sera stocké en mémoire mais ce n’est pas grave… On continu :) plusieurs floodfill plus tard nous en arrivons là :

Notre programme , dans sa lancée, s’apprête a effectuer un floodfill sur le pixel au centre du cercle noir. En effet, le programme lit les pixel de la gauche vers la droite et de haut en bas. une fois le floodfill effectué, cela donne :

Ce que nous allons expliquer ci-dessous est valable pour chaque composante de l’image a quelques exception prêt . ne sont pas traitées celles qui répondent au critères suivant :

- taille trop petite (inférieure à 60 pixel de large par 60 de haut car ne comportant pas assez de détails pour la reconnaissance de forme se déroulant ultèrieurement) : par exemple la seconde composante trouvé dans notre exemple

- Celle trop grande (>50% de la taille de l’image initiale) car le bruit de fond pollue la définition de cette dernière

- Celles étant en contact direct avec la bordure de l’écran car jugées incomplètes. par exemple : la première composante trouvé dans notre exemple.

Vous noterez donc que l’immense majorité des primaires détectée jusqu'à présent n’ont pas été analysée pour l’une des raisons citées plus haut. Nous avons décidé de ces régles de filtrage suites à l'expèrience acquise lorsque Caliban exploitait la première topique Freudienne. Leur analyse ralentie les temps de réponse et n'apporte aucune réelle valeur ajouté à l'anaalyse globale de l'image.

Bref, revenons au dernier floodfill en date ! Nous voyons qu'il a "colorié" la tête de Cub. Or, il est assez aisé de « détourner » un floodfill de son usage initial pour récupérer les bornes minimale et maximales du remplissage ; Autrement dit les X minimum et maximum de même que les Y (jusqu’où le floodfill s’est étendu). Il est important de noter qu’en informatique, les X augmentent de la gauche vers la droite et de haut en bas. Ainsi, en connaissant ces coordonnées nous pouvons « encadrer »la zone remplie ; dans le cas, présent, cela donne :

A ce stade du traitement, la primaire est isolée par les processus interne de Caliban comme si l’on découpait un bout de l’image. Un nouveau tableau dynamique (de la taille de la primaire) est donc initialisé puis rempli avec les données de la zone ciblée. Nous avons donc :

Une fois le primaire isolé, il est absolument de la nettoyer. Pour cela, Il convient de faire un nouveau floodfill sur le pixel qui a été à l’origine de l’isolation de la primaire. Remplaçons ainsi la valeur 2 (rouge) par la valeur 3 (vert). Nous avons :

Quel intérêt de faire ceci ? cela se voit à l’œil :) En effet, du rouge, résiduel de l’entourage de la primaire mais ne lui appartenant pas apparait. Pour le faire disparaitre il suffit de remplacer tout ce qui n’est pas 1 (bleu) ou 3 (Vert) par 0 (blanc = absence de données) ; nous avons :

Et voila comment obtenir une magnifique tête du Robot Cub vue par Caliban avec en vert (3), les données correspondant au remplissage de la primaire et en bleu (1) les arrêtes de la primaire. Répétez l’opération tant que du blanc (0) persiste sur l’image initiale et vous obtiendrez toutes les primaires…positives !!!

Oui, je dis bien positive... Car nous avons procédé jusqu'à présent par élimination du blanc. mais on peut trés bien procéder par élimination du bleu sur l'image contourée initiale. Or cela s'avère être un excellent complément au processus décrit ci dessus car, curieusement, c'est lui qui assure la cohésion entre les primaires positive. Procéder en élimination de Bleu débouche généralement sur d'autres primaires, plus vastes, que nous désignons sous le nom de primaires négatives. Juste pour l'exemple, éliminons le bleu de l'image originale, nous avons, au bout de qquelques floodfill :

Bon, ce n’est pas de veine car dans cet exemple, l’écran d’ordinateur n’est pas bien détaché du visage de Cub mais, en pratique, le système de pondération de la moyenne des variation de l'image de Caliban corrige très vite cela. Vous remarquerez cependant que, d’une façon générale, c’est bien Cub, dans sa totalité qui ressort. Cub est donc une primaire géante (le filtre de filtrage des grande primaires n'est pas appliqué sur les négatives) que l’on peut analyser exactement comme la tête vue plus haut (avec le même algo mais en remplaçant les 1 par des 0 et les 0 par des 1).

Mais ce qui est encore plus intéressant ici est qu’il faut garder à l’esprit que toutes les primaires (positives et négatives) se trouvent dans un référentiel (l'image) et donc que l’on connait les coordonnées de chacunes d'elles. Ainsi, il apparait que la primaire « tête » analysée plus haut a des coordonnées appartenant en totalité à la primaire Cub isolée ici. La probabilité que la tête soit une composante de Cub est donc très élevée. Des liens hiérarchiques peuvent donc être établis, a priori, qui seront vérifiés soit par la comparaison stéréoscopique soit par l'apprentissage; Mais là, nous entrons dans l’analyse et la reconnaissance de forme qui fera prochainement l’objet d’une autre page de ce site.

En espérant avoir pu vous éclairer sur la méthode de fonctionnement du système visuel de Caliban, il ne me reste plus qu’a vous inviter a venir intervenir sur le forum si tel ou tel point vous semble obscur. Cela nous permettra d'améliorer le présent exposé ;)

_______________________________________________________________________________________________________________

PS 1 :Nous avons bien conscience que ce processus est trés simple et peut être largement amélioré. Cependant nos ressources humaines et matérielles ne nous le permettent pas. mais peut être qu'un jour, pour CBN-002 (qui commence à se concrétiser dans nos esprits), nous mettrons en place diverses améliorations

PS 2 : Il va de soit que dans Caliban, les processus ne s'enchainent pas exactement comme décrit ci dessus. Il serait dommageable de scanner à maintes reprises un tableau quand on peut mutualiser les traitements. Ainsi, à titre d'exemple, le calcul du taux moyen de variation se fait en même temps que l'alimentation du tableau a partir des procédure Scanline.

PS 3 : Nous tenons à informer l'internaute de la franchise de notre exposé. En effet, il existe une infinité de traitements d'images et nous n'en connaissons pour ainsi dire aucun. dés lors, il est possible que tout ou ppartie de la présente méthodologie existe déjà voir, pire, soit la propriété intellectuelle de quelqu'un. Nous tenons donc à préciser que nous avons élaboré ce processus de façon entièrement autonome en fonction de nos expériences et résultats. Nous avons peut être réinventé la poudre mais au moins, en ayant procédé de la sorte, maitrisons parfaitement son déroulement.