Discussion:Algorithme de remplissage par diffusion

Auteur de l'algorithme du flood fill

Je m'appelle Fred RINGUET, je suis Français, j'habite près d'Angers, et je suis ingénieur télécom. Je suis l'inventeur de l'algorithme de remplissage par diffusion connu sous le nom de Scanline fill. J'avais trente ans quand j'ai créé cet algorithme en 1986 dans une toute petite SSII de six personnes qui s'appelait SDI (Solutions et Développements Informatique) et qui était située à Bourg-la-Reine dans le 92. On m'avait demandé de réaliser un logiciel de DAO sur PC pour saisir en les dessinant les points de collage d'une table de collage industrielle. J'étais stagiaire, non payé car avec l'ANPE, et sans contrat signé avec l'entreprise. Pour cette raison, je faisais ce que je voulais, en y passant tout le temps que je voulais y passer. C'est ainsi que quand j'ai commencé la "routine paint" pour peindre une surface, j'ai voulu réussir à peindre une surface quelque soit la forme de son contour. Je passais des journées entières à tester la fonction paint. Je réfléchissais tout le temps au problème que je voulais résoudre, le jour, la nuit et le week-end, sans pression de personne, totalement libre. Je voulais absolument peindre une surface quelque soit sa forme et son contour. Cela dura un peu plus d'un mois jusqu'à ce que tout à coup vers la mi-septembre 1986, je vis sous mes yeux l'écran se remplir selon l'algorithme du "Scanline fill" que l'on connaît (lignes horizontales peintes dans une seule direction avec une fonction récursive utilisant une pile de points remplis avec une toupie de neuf points, en partant de n'importe quel point de germe pris dans la surface à peindre). Aussitôt, j'appelai tous les personnes présentes pour venir voir. Elles furent toutes émerveillées de voir la manière dont toutes les zones de la surface se remplissaient les unes après les autres selon un ordre étrange ! Il s'agissait de l'algorithme appelé "Scanline fill" sur la version anglaise de cet article et présenté dans l'article en anglais comme une optimisation de l'algorithme de base du Flood fill.

Côté anglo-saxon, il est fait état d'un algorithme précurseur du Scanline fill s'appelant le Seed fill, créé par un américain. Mais cet ancêtre du Scanline fill fut publié dans le livre Graphics Gems pour la première fois en 1987, soit après septembre 1986, date de la découverte du Scanline fill par moi-même. Autrement dit, mon algorithme ancêtre est né après moi... C'est plusieurs années plus tard,qu'un australien publia la version actuelle connue du Scanline fill. Cette filiation du Seed fill au Flood fill puis au Scanline fill a pour effet de créer un processus logique dans l'histoire de son invention. Mais ce n'est pas ainsi que fut inventé le Scanline fill. Il fut inventé from scratch, directement, sans un algorithme ancêtre, et par moi-même.

On peut remarquer que le Scanline fill possède, en plus de la propriété de peindre une surface quelconque, la propriété de reconnaître le contour quelconque de la surface. Pour obtenir le contour, il suffit de masquer tous les pixels qui ont été peints par l'algorithme. C'est la pile de l'algorithme qui fournit ce contour. Autrement dit, le Scanline fill permet de faire de la reconnaissance de forme, ce qui est au moins aussi intéressant que le remplissage. Il en découle une multitude d'applications industrielles. Si la bordure de la surface n'est pas la couleur d'un pixel mais une teneur en minerai, alors on peut développer une méthode de recherche minière sans creuser au hasard. En imagerie, on peut faire de la reconnaissance d'écriture ou de la reconnaissance des notes d'une partition musicale. Toujours en imagerie, on peut aussi utiliser cet algorithme pour guider la prise de vue d'un satellite. En robotique, on peut lancer un robot à l'intérieur d'une surface à scanner. Le robot va scanner toute la surface, mémoriser tout le contour de la surface et revenir tout seul au point de départ sur la fin du balayage sans localisation annexe ! Cette exploration vers l'inconnu avec retour au point de départ et mémorisation de l'inconnu est tout à fait remarquable.

Il y a un enjeu financier certain lié à toutes ces applications industrielles. Cette algorithme est une pépite. On peut remarquer que le Seed fill a été publié en 1987 dans le livre Graphics Gems en étant noyé au milieu de dizaines d'algorithmes...

Combien de temps s'est il écoulé entre septembre 1986 et la date des premières exploitations industrielles de l'algorithme ? Quel fut le premier satellite à l'embarquer ? Un satellite américain ou bien un satellite français ? Au bout de combien de temps après 1986 ? Combien est-ce que cela a rapporté d'argent et à qui ? Au bout de combien de temps les militaires ont mis la main dessus et lesquels en premier ?

En 1990, on m'a promené pour un entretien au CNES aux Halles à Paris. En 1992, j'ai rencontré un anglo-saxon qui venait de la SHELL. En 1993, j'ai rencontré quelqu'un qui avait travaillé dans les sous-marins militaires français. En 1995, j'ai rencontré quelqu'un qui m'a récité le CV d'un de mes employeurs.

Ce que je sais, c'est que la République n'aime pas tousser.

Fred Ringuet

Utilisateur wikipedia : FredBRinguet --FredBRinguet (discuter) 14 juillet 2015 à 19:40 (CEST)

--Spécial:Contributions/FredBRinguet (discuter) 8 avril 2015 à 19:01 (CEST)

Transféré depuis ma page de discussion. Le fait pour un article d'être orphelin signifie qu'aucun autre article n'y fait référence (moins de 3 pour être exact). Si personne ne créé de lien vers cet article, il n'y a aucune raison que ce fait change...