Soutenance mémoire
Le traitement d’images pour les machines intelligentes
Montée en puissance des intelligences artificielles
«Mon intention n’est pas de vous surprendre ou de vous choquer, mais la manière la plus simple de résumer les choses consiste à dire qu’il existe désormais des machines capables de penser, d’apprendre et de créer. En outre, leur capacité d’accomplir ces choses va rapidement s’accroître jusqu’à ce que, dans un futur proche, le champ des problèmes qu’elles pourront aborder soit coextensif à celui auquel s’applique l’esprit humain.» .
Cette citation (relevée dans [1]) de 1957 d’Herbert Simon (1916-2001), lauréat du prix Turing en 1975 et du prix Nobel d’économie en 1978, prédisait que la machine serait rapidement l’égal de l’humain dans de nombreux domaines et notamment dans celui de la prise de décision qui était une de ses spécialités. Si l’horizon de sa prédiction a été plus lointain que prévu, il n’en est pas moins vrai que les machines occupent aujourd’hui une place centrale dans les domaines économiques, éducatifs et plus généralement dans notre vie de tous les jours :
• la voiture autonome ou «intelligente» existe déjà [2, 3], et sa diffusion pose plus de problèmes au niveau des infrastructures [4], de la législation et des mentalités [5, 6] qu’au niveau des techniques des systèmes embarqués,
• nos poches contiennent des assistants personnels capables de comprendre (partiellement) notre langage, d’anticiper nos demandes et de nous suggérer ce que nous allons manger, avec qui le faire et dans quel lieu [7].
Ces évolutions récentes reposent sur la conjonction de deux phénomènes : les progrès algorithmiques en intelligence artificielle et la massification des données.
Rôle de la vision artificielle
La vision artificielle, comme les autres branches de l’intelligence artificielle, participe à ces progrès en apportant aux machines une information sur leur environnement. Son impact est notable dans des domaines variés tels que :
• le domaine médical, où le diagnostique assisté par ordinateur permet d’aider le praticien par la mise en évidence d’irrégularités dans des résultats d’imagerie [8, 9],
• les applications industrielles, où le but est d’extraire de l’information pour automatiser et accélérer des processus fastidieux pour les humains [10, 11].
• l’accès interactif à la culture, avec la mise à disposition d’une bibliothèque d’Alexandrie numérique rendue possible par la reconnaissance de caractères (O.C.R) que ce soit pour les caractères imprimés [12] ou manuscrits [13] et même pour les œuvres musicales les plus anciennes (O.M.R) [14],
• l’exploration spatiale, où les délais et la variabilité des communications rendent nécessaire l’autonomie décisionnelle des machines d’explorations [15],
• l’interaction homme-machine, où le contrôle par gestes et l’utilisation de capteurs dédiés ont nécessité la création et l’adaptation de nombreux algorithmes de vision [16],
• la biométrie [17] et la sécurité par le biais du suivi de personnes [18, 19] de la détection de mouvements [20, 21] et de l’analyse de scènes [22] sont des domaines en forte expansion, du fait du contexte sécuritaire actuel, qui nécessitent toujours plus de précision et de rapidité,
• la réalité augmentée dont le champ d’application se développe tant du point de vue médical, industriel que ludique [23].
Enjeu de la massification des données
Dans un monde où la communication visuelle tient le premier plan, pouvoir analyser rapidement des images fixes ou des séquences vidéos pour en extraire de l’information est un enjeu important. La quantité d’images générées et stockées numériquement dans le monde croît en effet exponentiellement. Quelques chiffres permettent de prendre conscience de l’ampleur du phénomène :
• une plateforme dédiée à la photographie (Instagram) s’enrichit chaque jour de 70 millions de photographies et dispose déjà d’une base de 40 milliards d’images,
• le réseau social Facebook dispose d’une base supérieure à 240 milliards d’images qui progresse au rythme de 350 millions par jour (chiffres 2013),
• les bases de données scientifiques ne sont pas en reste et ImageNet [24] propose plus de 14 millions d’images classées en 21841 catégories sémantiques (synsets).
Dans le même temps, la taille des images générées progresse avec la résolution des capteurs comme par exemple les caméras de vidéo-surveillance récente qui ont couramment une résolution HD1080 (1920 × 1080) à comparer à la résolution standard 4CIF(704 × 576) et la résolution 7K (7360 × 4128) qui représente le haut de gamme actuel. Le cas des aéroports de Paris (groupe ADP) illustre cette augmentation des données et du besoin de les traiter toujours plus rapidement. En 2001, la fréquentation des aéroports du groupe ADP était de 71 millions de passagers [25] et est passée à 95,4 millions en 2015 [26]. Dans le même temps, du fait de l’augmentation constante des processus visant à garantir la sécurité des passagers, le nombre de caméras de surveillance est passé de 1000 à 9000 unités et le groupe ADP est actuellement en phase de test de systèmes de reconnaissance faciale [27]. L’objectif d’un tel système est d’avertir le plus rapidement possible (de l’ordre de la minute) de la présence d’un individu recherché afin de faire intervenir le personnel de sécurité. D’une manière générale, la vision artificielle doit aujourd’hui traiter toujours plus d’images, de plus grande taille, plus rapidement et au plus près de l’utilisateur final du fait de la diversification des supports et des applications. Les algorithmes de traitement d’images doivent donc être agiles et s’adapter aux architectures modernes, de l’assistant personnel (smartphone, tablette) aux architectures les plus parallèles en passant par l’ordinateur de tout un chacun.
Architectures pour la vision artificielle
Depuis les début de la vision artificielle, plusieurs approches architecturales coexistent. Que l’architecture consomme quelques watts ou plusieurs centaines de watts, la performance réside dans l’exploitation maximale de capacités de calculs et de bande passante mémoire de celle-ci. Le développement d’un algorithme efficace passe donc par la prise en compte des mécanismes spécifiques à chaque architecture, des plus généralistes aux plus spécialisées.
• Les processeurs généralistes (GPP ) qui équipent le ordinateurs de bureau, les stations de travail, les serveurs les plus courants mais aussi les téléphones mobiles et les tablettes, sont très représentés dans la littérature sur les algorithmes de traitement d’images du fait du grand nombre d’outils de conception supportés et du faible coût des plateformes au regard de leurs performances. De plus, chaque progrès dans l’écosystème de ces architectures est directement bénéfique aux algorithmes de traitements d’images. Ainsi, les progrès réalisés sur les compilateurs, les langages, les mécanismes de caches et les jeux d’instructions ont un impact direct sur la simplicité de développement et les performances des algorithmes de traitement d’images. A l’inverse, l’évolution des architectures généralistes vers un modèle comportant toujours plus de cœurs nécessite de repenser les algorithmes pour exploiter au mieux la puissance des nouveaux modèles de processeurs. Enfin, leur polyvalence permet de les utiliser à la fois pour les algorithmes de bas niveau et ceux de plus haut niveau [28]. Pour des algorithmes spécifiques, les architectures dédiés seront plus efficaces mais nécessiterons dans la plupart des cas de transférer in fine les données obtenues vers des architectures généralistes [29].
• Les processeurs graphiques ont été conçu comme des coprocesseurs spécialisés dans le rendu d’images de synthèse. Ils intègrent aujourd’hui plusieurs milliers d’unités de traitements spécialisées organisées pour réaliser de courtes séquences d’instructions identiques sur une grande quantité de données. Les applications nécessitant du calcul régulier avec une intensité arithmétique élevé tels que le filtrage sont très favorablement accélérées sur GPGPU et proposent un gain du point de vue de l’efficacité énergétique. A contrario les algorithmes irréguliers qui nécessitent l’utilisation intensive de structures de contrôle sont inefficaces sur ce type d’architectures. Les algorithmes doivent donc être pensées spécifiquement pour ces architectures [30]. Les GPGPU restent dépendants d’un système hôte utilisant une architecture généraliste et les temps de transfert très significatifs nécessaires au chargement des données dans la mémoire du processeur graphique et à la récupération des résultats doivent être pris en compte pour une comparaison équitable [31].
• Des architectures spécialisées ont été développées pour faire face aux besoins élevés de puissance de calcul, notamment dans le cadre du traitement d’images, afin atteindre des performances temps-réel. Par exemple, des architectures de type maille permettent d’associer à chaque processeur élémentaire un pixel, une ligne ou un bloc selon les paramètres de l’algorithme. Un des avantages de la structure en mailles est que sa structure régulière préserve les relations spatiales des images pixelisées [32]. Un exemple de structure en maille utilisée pour la vision par ordinateur est la Maille Associative d’Orsay [33]. Basée sur une structure asynchrone, elle permet d’atteindre les performances temps réel nécessaires pour traiter des flux vidéos [34]. Les DSP, les architectures Tilera [35], CELL [36], TSAR (TeraScale Architecture) [37–39] sont d’autres exemples d’architectures spécialisées dont le traitement d’images peux tirer parti. La complexité de programmation de ces architectures, relativement aux architectures généralistes, peut-être levée par l’utilisation de langages dédiés [40].
• Les architectures dédiées conçues pour répondre aux spécificités d’un algorithme particulier, sont généralement implémentées sur FPGA [41] afin d’optimiser finement les ressources en choisissant le juste niveau de parallélisme. Les blocs élémentaires ainsi conçus peuvent être chaînés physiquement, si les ressources du FPGA le permettent, ou temporellement dans le cas des architectures reconfigurable dynamiquement telles qu’Ardoise [42] mais généralement au prix d’une perte de spécialisation. Les avantages de ces architectures dédiées sont : la possibilité d’optimiser la consommation énergétique en ajustant les ressources aux besoins de l’algorithme [43], la possibilité d’utiliser ces développements dans des ASIC poussant ainsi plus loin encore l’optimisation énergétique et le couplage fin avec des processeurs dans le cas des PSoC (Programmable System on Chip). Par exemple dans [44] où une détection de points d’intérêts est réalisé dans une section FPGA et exploitée par le processeur bi-cœur Cortex-A9 embarqué du PSoC Zynq. Un des principaux inconvénient du développement dédié sur FPGA est le haut niveau de spécialisation nécessaire des concepteurs, associé au temps de développement particulièrement élevé. La génération automatique de code par le biais de la synthèse haut-niveau (HLS) permet de réduire ce temps de développement, pour les applications compatibles, au prix d’une élévation de la consommation. Cette surconsommation peut-être alors modérée par l’utilisation de transformations au niveau algorithmique .
|
Table des matières
INTRODUCTION
Chapitre Fondamentaux de l’étiquetage en composantes connexes d’images binaires
1.1 Notions de topologie pour l’étiquetage en composantes connexes
1.1.1 Topologie numérique
1.1.2 Pavage
1.1.3 Maillage
1.1.4 Connexité
1.1.5 Sens de parcours de l’image
1.1.6 Voisinage
1.2 De la composante connexe à l’image étiquetée
1.2.1 Composantes connexes
1.2.2 Structures de l’étiquetage en composantes connexes pour les images binaires
1.2.3 Première intuition
1.2.4 Les catégories d’étiquetage en composantes connexes
1.3 Structures de données et manipulations des graphes
1.3.1 Dualité graphe de connexité / matrice d’adjacence
1.3.2 Fermeture transitive
1.3.3 Algorithme de Floyd-Warshall
1.3.4 Forêts enracinées
1.3.5 Représentation par table d’équivalences
1.3.6 Algorithme Union-Find
1.4 Algorithmes pionniers
1.4.1 Rosenfeld & Pfaltz
1.4.2 Haralick & Shapiro
1.4.3 Lumia & Shapiro & Zuniga
1.4.4 Ronse & Devijver
1.5 Contraintes algorithmiques et architecturales
1.5.1 Topologie des algorithmes d’étiquetage en composantes connexes : un mélange de données éparses et denses
1.5.2 Problématique de l’intensité arithmétique
1.5.3 Étiquettes supplémentaires
1.6 Analyse en composantes connexes
1.6.1 Descripteurs d’une composante connexe
1.6.2 Calcul des descripteurs
1.7 Conclusion
Chapitre 2 Etat de l’art des algorithmes séquentiels d’étiquetage en composantes connexes
2.1 Introduction
2.2 Construction d’un jeu de données unifié
2.2.1 Images épreuves
2.2.2 Taille des images
2.2.3 Métriques
2.2.4 Reproductibilité des images aléatoires
2.2.5 Densité
2.2.6 Granularité
2.3 Analyse des caractéristiques du jeu de données
2.3.1 Influence des paramètres du jeu de données sur le nombre d’étiquettes
2.3.2 Cas des images des bases de données SIDBA et SIDBA4
2.4 Améliorations algorithmiques
2.4.1 Arbre de décision
2.4.2 Gestion des équivalences : Suzuki
2.4.3 Compression de chemin
2.4.4 RCM
2.4.5 HCS : un algorithme à machine d’états
2.4.6 HCS2
2.4.7 ARemSP
2.4.8 Grana
2.4.9 LSL : Light Speed Labeling
2.5 Calcul des descripteurs
2.6 Conclusion
Chapitre 3 Performance des algorithmes séquentiels d’étiquetage et d’analyse en composantes connexes
3.1 Introduction
3.2 Constitution d’un ensemble d’algorithmes de référence
3.2.1 Variantes de la famille Rosenfeld
3.2.2 Variantes de la famille HCS2
3.2.3 Variantes de la famille Suzuki
3.2.4 Algorithmes de références pour la suite des expérimentations
3.3 Confrontation des algorithmes de référence au jeu de données
3.3.1 Comportement vis-à-vis de la densité
3.3.2 Comportement vis-à-vis de la granularité
3.3.3 Résultats par rapport aux images de SIDBA
3.3.4 Conclusion sur le comportement général des algorithmes de référence vis-à-vis du jeu de données
3.4 Parts des étapes intermédiaires dans la composition de la performance globale de l’étiquetage en composantes connexes
3.4.1 Résultats pour les images aléatoires
3.4.2 Résultats pour les images de SIDBA
3.4.3 Conclusion pour l’étiquetage en composantes connexes
3.5 Analyse en composantes connexes
3.5.1 Résultats pour les images aléatoires
3.5.2 Résultats pour les images de SIDBA
3.5.3 Conclusion
3.6 Part des étapes intermédiaires dans la composition de la performance globale de l’analyse en composantes connexes
3.6.1 Résultats pour les images aléatoires
3.6.2 Résultats pour les images de SIDBA
3.6.3 Conclusion
3.7 Évolution des performances avec les générations d’architectures
3.8 Conclusion
CONCLUSION
