Détection de texte dans des images vidéo: apprentissage de dictionnaires ou extraction de caractéristiques

PROJET FIN D’ETUDES - PROJECTE FINAL DE CARRERA Détection de texte dans des images vidéo: apprentissage de dictionnaires ou extraction de caractéristiques. Auteur: Tuteurs: Jordi CASTILLO QUER Corinne MAILHES Jean-Yves TOURNERET ESCOLA TECNICA SUPERIOR D’ENGINYERIA DE TELECOMUNICACIONS DE BARCELONA - ECOLE NATIONALE SUPERIEURE D’ELECTRONIQUE, D’ELECTROTECHNIQUE, D’INFORMATIQUE, D’HYDROLYQUE ET DES TELECOMMUNICATIONS Remerciements Je voudrais remercier tout d’abord mes tuteurs Jean-Yves Tourneret et Corinne Mailhes pour m’avoir offert la possibilité de faire ce Projet Fin d’Etudes à Toulouse, qui a sans doute a amélioré tantôt mes aptitudes techniques comme humaines, mais surtout qui a signifié le point culminant de mes études comme Ingénieur en Télécommunications. Je voudrais remercier aussi Grégoire Denis et le reste de l’équipe ELLIPSE de l’IRIT, composé par Cristophe Jouffrais et Marc Macé pour sa gentillesse et son implication dans mon travail. Je remercie aussi mes camarades du bureau F204 et de TéSA pour la bonne humeur et la bonne ambiance de travail. Je remercie spécialement mes deux colocataires Joan et Victor, avec lesquels j’ai partagé sans doute un des moments les plus spéciaux de ma vie jusqu’à présent. Je remercie aussi tous les étudiants Erasmus que j’ai rencontré cette année, sans lesquels sans doute, j’aurais pu finir ce projet avant. Impossible d’oublier mes camarades de l’ETSETB avec lesquels j’ai parcouru mes études universitaires. Finalment, reservo aquestes darreres línies per a la meva família, especialment pel meu pare i la meva mare, pel seu sacrifici econòmic però també per la seva paciència i el seu suport moral, pels valors transmesos i pel seu amor, que m’han facilitat el recorregut d’aquest llarg i tortuós camí que ha suposat la meva educació i formació. Sense vosaltres hagués estat impossible. Gràcies de tot cor. Aquest projecte va dedicat, tot i que segurament no l’entengueu, als meus millors amics, i a vosaltres, pare i mare. i Sommaire Sommaire i Liste des figures iii 1. Introduction ..........................................................................................................................1 1.1. Contexte du projet .......................................................................................................1 1.2. Objectifs........................................................................................................................2 1.3. Résumé..........................................................................................................................2 2. Détection par discrimination de dictionnaires .................................................................. 3 2.1. Qu’est-ce qu’un dictionnaire? .....................................................................................3 2.1.1. Définition .........................................................................................................3 2.1.2. Estimation par dictionnaires.............................................................................. 3 2.1.3. Dictionnaires comme outil de discrimination....................................................3 2.2. Une solution au problème: l’algorithme K-SVD ........................................................4 2.2.1. Étape de codification parcimonieuse: algo OMP...............................................4 2.2.2. Étape de mise à jour du dictionnaire..................................................................5 2.2.3. Considérations sur l’algorithme: initialisation et convergence..........................6 2.2.4. Processus de construction des dictionnaires...................................................... 7 2.2.5. Exemples de dictionnaires................................................................................. 9 2.3. Processus d’analyse des images..................................................................................11 2.3.1. Prétraitement: détection de contours................................................................11 2.3.2. Analyse en patchs............................................................................................ 11 2.3.3. Étape de discrimination....................................................................................12 2.3.4. Considérations sur le temps de calcul..............................................................12 2.4. Résultats par discrimination par dictionnaires ..........................................................13 2.4.1. Images synthétiques.........................................................................................13 2.4.1.1. Dictionnaires 16x16 ............................................................................14 2.4.1.2. Dictionnaires 32x32..............................................................................14 2.4.1.3. Premières conclusions et alternatives................................................... 15 2.4.2. Images IRIT..................................................................................................... 15 ii 2.4.2.1. Dictionnaires 16x16..............................................................................17 2.4.2.2. Dictionnaires 32x32..............................................................................19 2.4.3. Conclusions......................................................................................................21 2.5. Conclusions de la méthode......................................................................................... 21 3. Détection avec l’algorithme Maximal Stable Extremal Regions (MSER)......................22 3.1. Caractéristiques principales de MSER........................................................................22 3.2. Paramètres MSER.......................................................................................................22 3.2.1. Stabilité d’une région extrémale......................................................................22 3.2.2. Considération sur l’image de sortie MSER..................................................... 23 3.2.3. Paramètre Delta ............................................................................................ 23 3.2.4. Paramètre MaxVariation.................................................................................. 25 3.2.5. Paramètre MinDiversity................................................................................... 28 3.2.6. Autres paramètres: MaxArea,MinArea,DarkOnBright et BrightOnDark......29 3.3. Pré-traitement: amélioration localisée du contraste....................................................30 3.4. Premier post-traitement: discrimination morphologique des objets...........................31 3.4.1. Fonction d’étiquetage des régions et extraction des propriétés....................... 31 3.4.2. Bounding Box d’un objet et proportion............................................................31 3.4.3. Densité d’un objet............................................................................................32 3.4.4. Nombre d’Euler d’un objet..............................................................................33 3.5. Résultats......................................................................................................................33 3.5.1. Premières images............................................................................................. 33 3.5.2. Deuxième banque d’images.............................................................................35 3.6. Deuxièmes post-traitements........................................................................................36 3.6.1. Regroupement d’objets par proximité............................................................. 36 3.6.2. Recherche de lignes......................................................................................... 38 3.6.3. Possible utilisation d’OCR (Optical Character Recognition)..........................39 3.7. Conclusions de la méthode......................................................................................... 40 4. Conclusions sur le projet et travail futur .........................................................................41 Annexe: Extraits vidéo des résultats MSER..........................................................................42 Références et bibliographie.....................................................................................................44 iii Liste des figures Figure 1.1 Cadre rouge ayant reconnu un visage et image simulant la vision prosthétique avec 6x10 phosphènes .................................................................................1 Figure 2.1. Schéma simplifié de la détection de caractères.....................................................4 Figure 2.2. Description de l’algorithme OMP utilisé..............................................................5 Figure 2.3. Description de l’algorithme K-SVD utilisé...........................................................6 Figure 2.4. Exemples d’images d’apprentissage pour les lettres et les fonds......................... 7 Figure 2.5. Contours d’images d’apprentissage de dictionnaires...........................................8 Figure 2.7. Extrait d’un dictionnaire de lettres (32x32) x 2048..............................................9 Figure 2.8. Extrait d’un dictionnaire de fonds (32x32) x 2048............................................... 9 Figure 2.9. Dictionnaire de lettres (16x16) x 512..................................................................10 Figure 2.10. Dictionnaire de fonds (16x16) x 512.................................................................10 Figure 2.11. Images avec filtrage Canny avec seuil 0.01, seuil 0.1 et seuil 0.7.................... 11 Figure 2.12 Patchs approximés et leur erreur quadratique associée....................................12 Figure 2.13. Image d’essai et ses contours pour la détection de texte..................................13 Figure 2.14. Résultat après analyse 16x16 avec T=15 et T=150..........................................14 Figure 2.15. Résultat après analyse 32x32 avec T=15 et T=150..........................................14 Figure 2.16. Quelques images prises d’intérieurs.................................................................15 Figure 2.17. Exemple de nouvelle image d’analyse.............................................................. 16 Figure 2.18. Dictionnaire 16x16 de lettres et de fonds .........................................................17 Figure 2.19. Résultat de la discrimination avec dictionnaires 16x16................................... 18 Figure 2.20. Zoom des atomes du dictionnaire 32x32 de lettres et de fonds.........................19 Figure 2.21. Contours d’images à analyser et leurs résultats avec T=50.............................20 Figure 3.1 Image binarisée seuillée avec un pas de 10%......................................................23 Figure 3.2. Image synthétique 250x350 pour l’analyse de paramètres.................................24 Figure 3.3. Carrés détectés par MSER avec =62 et =63..................................................24 Figure 3.4. Carrés détectés avec =63 et MaxVar=35.........................................................25 Figure 3.5. Test du paramètre MaxVariation.........................................................................26 iv Figure 3.6. Nouvelles sorties avec =63 et MaxVar=100000...............................................27 Figure 3.7.Zoom de l’image testée. Sorties avec =63, MaxVariation=500 et MinDiversity=0.1 et Mindiversity=1......................................................................28 Figure 3.8.Images en sortie avec différents [DarkOnBright BrightOnDark] ...................... 29 Figure 3.9. Sorties de l’algorithme MSER sans pré-traitement puis avec pré-traitement .. 30 Figure 3.10. Histogramme de la proportion des lettres..........................................................32 Figure 3.11. Histogramme des densités des lettres................................................................32 Figure 3.12. Images avant et après premier post-traitement ................................................34 Figure 3.13. Images avant et après premier post-traitement.................................................35 Figure 3.14. Description de l’algorithme d’unification d’objets...........................................37 Figure 3.15. Exemples de regroupements..............................................................................37 Figure 3.16. Description de l’algorithme détection et séparation par lignes....................... 38 Figure 3.17. Exemples avant et après la recherche de lignes................................................39 1 1. Introduction 1.1. Contexte du projet L’ingénierie au service de la santé est un domaine où le traitement du signal et de l’image ont une place très importante afin de rendre les données les plus informatives possibles pour l’interprétation médicale, ou aussi pour l’accessibilité des personnes comme la lecture automatique de caractères par exemple. Des études récentes montrent qu’une personne non voyante pourrait arriver à distinguer un point lumineux, appellé phosphène, grâce à la stimulation du cortex visuel à l’aide de neuro-prothèses. Avec l’implantation de plusieurs prothèses, on pourrait arriver à avoir une image de quelques dizaines de phosphènes, appelée “vision prosthétique”. Ce sera en jouant avec l’activation ou pas des phosphènes que l’on pourra avoir des applications intéressantes. Plus précisément, l’équipe ELIPSE de l’IRIT (Institut de Recherche en Informatique de Toulouse) dans le cadre de la thèse de G. Denis[1], travaille dans le cadre de la vision prosthétique pour la localisation d’objets et de visages, application très utile pour les personnes non-voyantes. Dû au manque de patients non voyants équipés de neuro-prothèses pouvant tester ces applications, l’équipe a développé un système qui simule la vision prosthétique et qui peut donc être testée avec des personnes voyantes. La localisation d’objets d’intérêt consisterait à faire clignoter un des phosphènes représentés par des pixels, indiquant la direction vers laquelle la personne devrait se déplacer. Pour cela, une caméra enregistrerait la scène et le résultat du traitement sur cette image serait envoyé vers les neuro-prothèses. Figure 1.1 Cadre rouge ayant reconnu un visage (gauche) et image simulant la vision prosthétique avec 6x10 phosphènes (droite). 8 Pour ceci, il existe différents détecteurs de contours tels que Prewitt,Sobel,Roberts ou Canny. Nous avons choisi le détecteur de Canny pour ses bonnes propriétés connues. Pour tout détecteur de contours on doit fixer un seuil de sensibilité. Même si pour les images d’apprentissage des lettres ce n’est pas significatif, car elles sont bien contrastées, on construit différents dictionnaires pour différentes valeurs du seuil plutôt pour les images de fonds. Les valeurs prises ont été 0.04,0.06,0.08,0.1,0.12 dans la fonction edge de Matlab. Figure 2.5. Contours d’images d’apprentissage de dictionnaires D’autre part, on ne travaillera pas avec l’image entière mais on découpera chaque image en patchs (morceaux) carrés. En plus, vu que notre algorithme travaille avec des données 1D, on devra passer celles-ci de taille NxN à N²x1 comme l’illustre la figure 2.6. Figure 2.6. Schéma illustratif de la préparation des données pour l’apprentissage 9 2.2.5. Exemples de dictionnaires Dans les figures qui suivent, on a différents dictionnaires obtenus avec K-SVD pour des patchs de 16x16 et de 32x32: Figure 2.7. Extrait d’un dictionnaire de lettres (32x32) x 2048 Figure 2.8. Extrait d’un dictionnaire de fonds (32x32) x 2048. 10 Figure 2.9. Dictionnaire de lettres (16x16) x 512. Figure 2.10. Dictionnaire de fonds (16x16) x 512. En observant ces dictionnaires, à ce point là les différences entre les deux types de dictionnaires sont encourageantes quant à la possible capacité de discrimination. 11 2.3. Processus d’analyse des images 2.3.1. Prétraitement: détection de contours Comme pour l’apprentissage des dictionnaires, on doit réaliser un pré-traitement en transformant l’image à analyser en échelle de gris, puis réaliser une détection de contours. Le même détecteur Canny que celui pour l’apprentissage des dictionnaires est utilisé. Même si pour les lettres, bien contrastées avec le fond, le choix d’un seuil pour le détecteur de contours n’est pas significatif pour qu’elles apparaissent, pour le fond ce n’est pas la même chose. En effet, plus le seuil est élevé moins de contours on détectera, en arrivant même à faire disparaître des lettres, mais aussi, plus le seuil est bas, plus le détecteur est sensible aux contours et donc beaucoup plus de contours apparaissent, ce qui rend difficile la détection. Figure 2.11. Images avec filtrage Canny avec seuil 0.01(à gauche), seuil 0.1(au milieu) et seuil 0.7(à droite). 2.3.2. Analyse en patchs La méthode proposée découpe l’image en patchs adjacents de la même taille que ceux du dictionnaire bien évidemment. Même si on ne l’a pas implémenté, on pourrait paralléliser l’exécution de l’analyse pour une meilleure performance temporelle vu qu’on a affaire à une application en temps réel. Il s’agirait en tout cas de quelque chose à voir après la validation de la méthode. On va donc se déplacer du haut vers le bas et de gauche à droite en voyant quel dictionnaire a le moins de mal à reconstruire le patch analysé. 12 2.3.3. Étape de discrimination Pour chaque patch, on devra réaliser deux opérations: la reconstruction avec le dictionnaire de lettres et celle avec celui de fonds. Pour ceci on va utiliser la fonction OMP décrite auparavant. Figure 2.12 Patchs approximés et leur erreur quadratique associée Dans l’exemple de la figure 2.12, on considèrera le patch analysé comme du texte vu que son erreur de reconstruction est plus petite en prenant le dictionnaire de lettres. Tous les patchs considérés comme du fond sont mis en noir. Ainsi l’image résultante sera une image binaire qui n’aura que les patchs de lettres et les fausses détections, prêtes à être enlevées avec des opérateurs morphologiques par exemple. 2.3.4. Considérations sur le temps de calcul Dans les premières expériences, on a eu un grand problème relatif au temps de calcul. En effet, en n’utilisant que des fonctions Matlab, l’apprentissage d’un dictionnaire prenait entre 2h et 3h. Ceci ne pose pas de problème, car une fois obtenu, on ne doit pas le recalculer pour l’analyse des images. Par contre, pour une image de taille 640x320 le temps d’analyse associé à tous les appels de la fonction OMP pouvait atteindre 300s, valeur totalement inadmissible pour une application en temps réel. Approximation avec DLETTRES Approximation avec DFONDS ε=49 ε=55 Patch à analyser 32x32 13 C’est pourquoi, dans les dernières expériences, on a utilisé le code C++ de ces fonctions, et on est passé à une dizaine de minutes pour l’apprentissage d’un dictionnaire et à moins de 2s pour l’analyse d’une image, valeur encore améliorable en parallélisant le code. 2.4. Résultats par discrimination par dictionnaires 2.4.1. Images synthétiques Dans un premier temps, on n’a pas disposé d’images de situations réelles du projet et donc on a décidé de faire les essais tout d’abord sur une image synthétique comme celle de la figure 2.13. Avec cette image, on simplifie d’abord le problème en ayant des lettres de différentes tailles et bien contrastées avec le fond le plus simple dans une moitié de l’image, et dans l’autre du fond. Figure 2.13. Image d’essai et ses contours pour la détection de texte. Pour les résultats qui suivent, les dictionnaires utilisés sont ceux des figures 2.7, 2.8, 2.9, 2.10. 14 2.4.1.1. Dictionnaires 16x16 Figure 2.14. Résultat après analyse 16x16 avec T=15(à gauche) et T=150(à droite). Avec les dictionnaires constitués d’atomes de taille 16x16, pratiquement toute l’image a été considérée comme du texte. En effet, avec cette taille si petite, les patchs sont facilement aproximés par le dictionnaire de lettres, qui lui est constitué d’atomes avec des lignes. C’est le cas par exemple des zones de fond, qui “de loin” présentent des formes compliquées mais qui “de près” sont formés de quelques lignes, et sont donc mieux aproximés comme des lettres. D’autre part, le nombre Tde coefficients non nuls utilisés n’apporte aucune amélioration dans notre analyse. 2.4.1.2. Dictionnaires 32x32 Figure 2.15. Résultat après analyse 32x32 avec T=15(à gauche) et T=150(à droite). 15 Si on construit des dictionnaires d’atomes de taille 32x32, dans ce cas, l’élimination des patchs de fond s’améliore mais reste encore insuffisante pour traiter cette image afin de ne garder que les caractères. 2.4.1.3. Premières conclusions et alternatives Après cette première phase expérimentale, on a essayé de chercher différentes alternatives pour améliorer le rendement de l’algorithme. Parmi elles, on a eu tout d’abord l’idée d’utiliser seulement le dictionnaire de lettres, et de discriminer en fonction de la valeur de l’erreur de reconstruction. Mais cette valeur dépend directement de la parcimonie Tde l’approximation et du type de patch. Une combinaison d’analyse 32x32 et 16x16 a été proposée, mais à nouveau, les paramètres dépendent des caractéristiques de l’image et de la parcimonie des reconstructions. On a conclu dans un premier temps qu’il fallait “aider” l’algorithme en utilisant des images plus proches des conditions de l’application, ou en tout cas, restreindre les conditions des images à un contexte donné, comme par exemple, des intérieurs de bâtiments. 2.4.2. Images IRIT Afin de mieux personnaliser et restreindre le dictionnaire de fonds, on a modifié la formation de ces dictionnaires en choisissant des images d’apprentissage contenant des couloirs, des bureaux, entre autres (voir figure 2.16). De cette façon on espère mieux caractériser ce dictionnaire. Figure 2.16. Quelques images prises d’intérieurs. 16 D’autre part, on n’a plus affaire a des images d’essais synthétiques, et donc la résolution de l’image joue un rôle important car on a l’influence du flou en plus de l’illumination de la scène qui gênent la séparation de caractères au moment de faire la détection de contours, notamment pour les lettres petites (voir figure 2.17). Figure 2.17. Exemple de nouvelle image d’analyse. 17 2.4.2.1. Dictionnaires 16x16 Dans un premier temps, sur cette banque d’images ciblées, représentant des couloirs de l’IRIT pour l’apprentissage du dictionnaire de fonds, on décide de travailler sur des patchs 16x16. Toutefois, avant d’appliquer l’algorithme de discrimination, on prévoit déjà qu’on ne pourra pas avoir de bons résultats avec cette taille car les deux dictionnaires sont très ressemblants (voir figure 2.18). Figure 2.18. Dictionnaires 16x16 de lettres (en haut) et de fonds (en bas). En effet les résultats ne sont pas du tout satisfaisants comme l’illustre la figure 2.19 et donc la taille 16x16 est définitivement mise de côté. 24 Figure 3.2. Image synthétique 250x350 pour l’analyse de paramètres. Les chiffres sous chacun des carrés correspondent à leurs niveaux de gris (ils ne sont pas présents dans l’analyse). A partir de l’image de la figure 3.2, on va voir l’influence du paramètre , considérant qu’une région ne va pas être détectée si son aire varie. On appellera Rl’aire extrémale avant seuillage et R  l’aire après seuillage. Au départ, les 6 carrés gris ont chacun une aire de R=50x50=2500. Sur la figure 3.3.a on observe que le paramètre =62 est en sorte que l’aire des carrés ne change pas, et donc pour toutes les régions: R=R. De cette façon on détecte tous les carrés comme des régions extrémales stables. Par contre, sur la figure 3.3.b avec =63 on observe que le carré avec un niveau de 192 n’est pas détecté vu qu'il s’est fondu avec la couleur blanche du fond, qui lui a aussi un niveau de 255-=192. La nouvelle aire de ce carré serait donc celle de toute l’image (région extrémale du niveau 192) et pas celle de l’image sauf les 5 carrés détectés. Figure 3.3. Carrés détectés (en blanc) par MSER avec a)=62 et b)=63. 25 A ce point là, si notre objectif était de détecter du texte noir sur du fond blanc, on choisirait >192, mais en pratique, les lettres possèdent des valeurs de niveau de gris différents qui peuvent dépendre aussi de phénomènes extérieurs tels que l’illumination. On devra donc prendre une valeur plus basse qui peut inclure des fausses alarmes. 3.2.4. Paramètre MaxVariation On définit tout d’abord la valeur absolue de la variation entre Ret R  notée Vde la façon suivante: R RR V  (3.1) Le paramètre MaxVariation indique la valeur maximale de la variation qu’une région peut atteindre pour être détectée. C’est ainsi que toute région avec V<MaxVariation sera détectée et acceptée. Figure 3.4. Carrés détectés avec =63 et MaxVar=35. De cette façon, comme on peut voir dans la figure 3.4, avec =63 le carré en bas à droite devrait disparaître comme dans le cas de la figure 3.3. En effet, tous les autres carrés ont V=0 sauf lui qui a V=34, et donc tous respectent les deux paramètres et MaxVar=35. En fait, la figure 3.3. Précédente correspond à fixer MaxVar=1 pour modéliser “ne pas être détectée si son aire varie”. Voici le calcul pour V=34: 34 2500 2500250350      R RR V (3.2) L’intérêt pour nous de ce paramètre sera de détecter du texte qui à cause de conditions d’éclairement, ses niveaux de gris et ceux du fond ne sont pas assez contrastés. En effet si on met une grande valeur pour MaxVariation, tous ces caractères, même s’ils étaient engloutis par une autre zone (leur fond par exemple), auraient une valeur Vqui resterait inférieure à MaxVar. 26 Figure 3.5. Test du paramètre MaxVariation. a) Image testée. b) Détail de la zone des lettres avec détection de contours Canny. c) Résultat avec =63 et MaxVar=35. d) Résultat avec =63 et MaxVar=500. Dans la figure 3.5, les résultats sont très satisfaisants rien qu’en regardant un possible résultat avec un détecteur de contours (figure 3.5.b), qui lui possède beaucoup d’éléments supplémentaires à filtrer. Dans l’image de la figure 3.5.c on a le résultat espéré vu qu’avec ce et un MaxVar bas, les lettres sont englouties par le seuillage. Par contre, avec une grande valeur de MaxVar, la relation entre les aires reste au-dessous et donc on détecte la grande majorité des lettres même si on introduit plus de fausses alarmes. Avec MaxVar=500 les résultats sont déjà satisfaisants, mais on peut augmenter considérablement cette valeur. En fait, plus une lettre est petite, ou plus elle a un niveau de gris proche de son fond, un MaxVar=100000 par exemple les détecte bien. Le seul problème est qu’une grande quantité d’objets peuvent apparaître. Ces objets devront être filtrés un à un, ajoutant un temps de calcul considérable. Tous ces effets sont observables dans la figure 3.6 où l’on a des détections que l’on avait pas avec MaxVar=500. 27 Figure 3.6. a) et d) Images testées. b) et e) Sorties avec =63 et MaxVar=500. c) et f) Nouvelles sorties avec =63 et MaxVar=100000. 28 3.2.5. Paramètre MinDiversity Dans certaines conditions, certaines régions peuvent être entourées par d’autres. C’est à ce moment que le paramètre MinDiversity intervient. Le mot ‘diversité’ fait référence au nombre de régions qui peuvent être contenues dans une région, que l’on appellera sous-régions. Si la variation relative des aires entre deux régions extrémales est au-dessous de ce paramètre, seulement la région la plus stable est prise en compte. De ce fait, plus MinDiversity est bas plus de sous-régions on aura et inversement. Dans la figure 3.7 on observe ce comportement, où chaque couleur (sauf le noir) représente une région détectée. Figure 3.7. a) Zoom de l’image testée. Sorties avec =63, MaxVariation=500 et b) MinDiversity=0.1 et c) Mindiversity=1. Ce paramètre n’est pas intéressant vu que les objets ont de toute façon la même taille. De toute façon, quand on a beaucoup de sous-régions, il est vrai que les lettres semblent toutes avoir la même sous-région à ses bords. Ceci a mené à essayer d’éliminer ces sous-régions aux bords des lettres afin de mieux les séparer entre elles. Mais d’après les expériences, l’identification de la sous-région idéale à éliminer n’est pas automatisable, et donc certains caractères peuvent disparaître complètement. C’est pour cela qu’on garde la valeur par défaut MinDiversity=0.2 . 29 3.2.6. Autres paramètres: MaxArea,MinArea,DarkOnBright et BrightOnDark Les paramètres MaxArea et MinArea bornent l’aire des régions extrémales trouvées, même pour les sous-régions. Ceci constitue donc un premier outil discriminant car on peut enlever des objets de taille trop grande ou trop petite en fonction de la taille de lettre que l’on vise à détecter. Ces deux paramètres ne sont pas des aires absolues mais des aires relatives à l’aire de l’image et donc sont plus petites que un. Les paramètres DarkOnBright et BrightOnDark spécifient si on veut détecter du “noir sur du blanc“ ou vice-versa. Dans toutes les expériences précédentes on a mis DarkOnBright=1 et BrightOnDark=0. Si on active BrightOnDark, le même code va être exécuté, mais avec l’image inverse en entrée. D’après les expériences, si on veut combiner les deux approches, il est préférable de ne pas le faire en même temps surtout pour des lettres ayant des trous. On aurait alors des régions claires détectées dans des régions foncées et vice-versa, comme illustre la figure 3.8. Ceci peut provoquer des problèmes au niveau du post-traitement. Il vaut donc mieux de lancer deux fois l’algorithme et de lancer deux discriminations, si le temps de calcul satisfait les contraintes temporelles de l’application. Figure 3.8. a) Image en entrée. Images en sortie avec [DarkOnBright BrightOnDark] étant b) [1 0], c) [0 1] et d) [1 1]. 30 3.3. Pré-traitement: amélioration localisée du contraste Une fois qu’on a trouvé de bons paramètres qui maximisent le nombre de détections et minimisent le nombre de fausses alarmes, on veut essayer de mieux séparer les caractères pour qu’on ne détecte pas trop de caractères collés, surtout pour les petites tailles ou à cause du flou. Les améliorations d’histogramme, n’apportent pas de progrès significatifs. En revanche, l’utilisation du filtre 2D ‘unsharp’ de Matlab nous offre de bons résultats. Il s’agit d’améliorer le contraste exclusivement des zones avec des hauts gradients comme les contours des objets. De cette façon certaines lettres deviennent déjà “à l’oeil” susceptibles d’être bien séparées en sortie de MSER. De plus, ce pré-filtrage n’apporte pas de différences pour les lettres qui seraient déjà bien séparées. Dans la figure 3.9, on a quelques résultats sans, et avec ce pré-traitement. Figure 3.9. Sorties de l’algorithme MSER a) et b) sans pré-traitement puis c) et d) avec pré-traitement respectivement. 31 Le filtre utilise l’information du gradient, et donc comme n’importe quel détecteur de contours il a besoin d’un seuil. Dans notre cas, pour la fonction de Matlab on utilise un seuil de 0.1, qui est très sensible aux contours. 3.4. Premier post-traitement: discrimination morphologique des objets A ce point là, dans la plupart des images on trouve des fausses alarmes que l’on doit éliminer. Notre premier post-traitement va tenir compte des caractéristiques discriminantes de la forme des lettres face aux objets du fond. 3.4.1. Fonction d’étiquetage des régions et extraction des propriétés Vu que notre image est désormais une image binaire, pour identifier les différents objets il suffit d’utiliser un algorithme de détection ou étiquetage de régions. Vu que l’on a travaillé avec MATLAB, on utilise la fonction CC=bwconncomp(imageBW). Une fois que les régions sont identifiées, on utilise à nouveau une fonction Matlab propriétés=regionprops(CC,propriétés_désirées). Avec celle-ci, on a pour chaque objet les propriétés que l’on a indiqué, parmi lesquelles on peut choisir l’aire, la solidité, la concavité, etc. Pour avoir une statistique de ces valeurs, on a utilisé les fonctions précédentes sur les images d’apprentissage des dictionnaires de lettres dont on disposait, avec des inclinaisons différentes pour simuler les possibles scénarios réels. 3.4.2. Bounding Box d’un objet et proportion La Bounding Box fait référence dans le cas 2D au plus petit cadre rectangulaire, avec ses côtés parallèles aux bords de l’image, qui peut entourer un objet. Ceci est un paramètre très discriminant vu que les lettres n’ont pas une Bounding Box aléatoire, mais par contre, intuitivement il est facile de voir que celles-ci auront, sauf pour des caractères comme le ‘i’, le ‘l’ ou le ‘f’, une proportion hauteur sur largeur proche de 1. Plus précisément, dans la figure 3.10, on observe que les proportions des lettres sont majoritairement dans l’intervalle [0.5;3]. Mais on a constaté que la majorité des valeurs au-dessous de 1 sont issues de lettres collées dans les images observées, et donc on a pris finalement comme intervalle [0.88;3]. 32 Figure 3.10. Histogramme de la proportion des lettres. Il faut ajouter que l’on a rejeté les Bounding Boxes ayant une aire inférieure à 35 car on comprend qu’il s’agirait d’objets trop petits. 3.4.3. Densité d’un objet Cette propriété est définie par la relation entre l’aire de l’objet sur l’aire de sa Bounding Box. En effet dans la statistique de la figure 3.11 on observe que les valeurs sont concentrées dans l’intervalle [0.25;0.83]U[1] , qui va être donc utilisé dans notre fonction de discrimination. Figure 3.11. Histogramme des densités des lettres. Les densités égales à 1 sont souvent associées aux lettres ‘i’ et ‘l’, mais dans des intérieurs elles correspondent aussi à des contours de portes ou d’objets rectangulaires qui sont très présents. C’est pour cela qu’on a décidé finalement d’accepter des densités dans l’intervalle [0.25;0.83]. Ces caractères pourraient être détectés une fois qu’on aurait une bonne image ne contenant que du texte. 33 3.4.4. Nombre d’Euler d’un objet Ce paramètre est utilisé pour trouver le nombre de trous d’un objet suivant la forme E=1-nombre_de_trous. Dans notre discrimination, les objets possédant plus de 2 trous ne seront pas considérés comme des lettres. On prendra donc E>-2. 3.5. Résultats Même si la qualité des résultats a évolué au cours du temps avec l’optimisation des paramètres de l’algoritme MSER, les résultats suivants sont ceux avec les meilleures valeurs: Taille des images: 480 x 640  : 63 MaxVar: 500 MinDiversity: 0.2 MaxArea: 0.000013021 ( 2² / (640x480) ) MinArea: 0.00094076 ( 17² / (640x480) ) BrightOnDark: 0 DarkOnBright: 1 3.5.1. Premières images Dans un premier temps, les images fournies par l’équipe IRIT avaient une forte complexité. En effet l’illumination de la scène n’est pas bonne, et la grande majorité des textes sont trop petits. Dans la figure 3.12 on observe quelques résultats. 40 3.7. Conclusions de la méthode L’utilisation de cet algorithme MSER, basé sur la stabilité des régions comme outil discriminant, résulte avoir de très bons résultats. Son temps de calcul inférieur à 1s le fait complètement exploitable dans l’application de l’équipe IRIT, ce temps pouvant être encore réduit. Comme tout algorithme de traitement d’image, le manque ou l’excès d’illumination de la scène influence en grande mesure l’algorithme, comme le témoignaient les premières images utilisées. Il faudrait donc rentrer dans le domaine de l’acquisition de l’image et voir quels mécanismes pourraient combattre ces phénomènes. Cette méthode, évite aussi l’utilisation d’autres fonctions et algorithmes qui aparaissent dans l’article de H. Chen[6] dont cette deuxième partie de ce PFE s’inspire, ce qui fait gagner du temps de calcul. 41 4. Conclusions sur le projet et travail futur L’objectif de ce Projet de Fin d’Etudes était le développement d’un algorithme de détection de zones de texte dans des images en mouvement. Dans un premier temps, ce projet était orienté vers l’article de Zhao[2] et la méthode qui y était proposée. L’étude exhaustive que nous avons menée nous permet de douter de l’efficacité de la méthode de Zhao dans notre application. Ainsi, la méthode simplifiée d’apprentissage par K-SVD de dictionnaires indépendants ne permet pas de résoudre le problème posé. C’est pourquoi nous nous sommes intéressés dans un deuxième temps à l’algorithme MSER[6] qui fonctionne de façon satisfaisante avec les paramètres proposés. Ce dernier algorithme, permet d’obtenir un coût de calcul petit, qui se situe au-dessous d’une seconde. De toutes les façons, on n’a pas un algorithme robuste à 100%, et donc, il sera nécessaire de passer par une étape expérimentale pour voir si ses fonctionnalités sont suffisantes dans l’objectif de la détection de texte en temps réel. Ce rapport peut servir alors comme référence pour les modifications qui pourraient être menées. Ce projet ouvre les portes à deux nouvelles phases: la phase d’approximation vers le texte une fois détecté et celle de sa lecture. Sans doute, l’algorithme MSER utilisé ici sera un outil à tenir en compte conjointement avec des outils comme le tracking, entre d’autres. Des problèmes comme le développement d’une interface avec l’utilisateur et d’un système de notifications s’imposent aussi comme possibles travaux futurs. 42 Annexe: Extraits vidéos des résultats MSER Dans les banques d’images qui suivent, chaque couleur représente un groupe détecté différent. Les paramètres utilisés sont ceux de la section 3.5. 43 44 Références et bibliographie [1] Grégoire Denis et Al. “Human faces detection and localization with simulated prosthetic vision”. CHI 2013 Extended Abstracts, April 27-May 2, 2013, Paris, France. [2] Ming Zhao et Al. “Text detection in images using sparse representation”, Image and vision computing, IVC 2010. [3] M. Aharon et Al., “The K-SVD: An algorithm for designing of overcomplete dictionaries for sparse representation,” IEEE Trans. Signal Processing [4] http://spams-devel.gforge.inria.fr/ (toolbox K-SVD) [5] D.Nister et Al., "Linear Time Maximally Stable Extremal Regions", ECCV, 2008. [6] Huizhong Chen et Al. “ Robust text detection in natural images with edge-enhanced maximally stable extremal regions” dans Proc.IEEE Int. Conf. Image Processing, Bruxelles, Sept. 2011 [7] http://www.vlfeat.org/ (toolbox MSER) [8] J. Mairal et Al., “Discriminative learned dictionaries for local image analysis”, InCVPR, 2008.