Facebook Twitter Google

DIGINPIX: identification d'entités nommées visuelles
dans les images et les vidéos

Pierre Letessier, Nicolas Hervé, Hakim Nabi, Mathieu Derval, Olivier Buisson

Ce travail a été réalisé en collaboration avec Alexis Joly (INRIA, équipe-projet ZENITH)

original

RÉSUMÉ

Ce travail présente un système automatique capable d'identifier des entités nommées visuelles apparaissant dans des images et vidéos, parmi une liste de 25 000 entités, rassemblées à partir de listes Wikipédia et de sites Web plus spécifiques. DigInPix est une application générique conçue pour identifier différents types d'entités. Dans cette première tentative, nous nous intéressons uniquement à l'identification de logo (plus généralement sur les personnes morales). La procédure d'identification repose principalement sur un système efficace de recherche d'image par le contenu (CBIR), qui parcourt une base de données indexée, composée de 600 000 images à l'étiquetage incertain, puisque collectées grâce à un moteur de recherche d'images. DigInPix propose une interface htlml5 responsive, utilisable par n'importe qui, à des fins d'essai.

1 Introduction

La reconnaissance et la désambiguïsation des entités nommées dans les documents textes est un problème bien connu de la communauté TAL et il existe désormais des solutions assez efficaces, telles celles proposées dans le cadre du concours Microsoft Entry Recognition and Disambiguation Challenge [2]. En parallèle, de nombreux travaux ont été réalisés sur la recherche d'images (logos, bâtiments, etc.) [110313], et sur la classification d'images, comme le démontrent de récents résultats sur ImageNet [14, 15]. Il existe par contre très peu de travaux sur l'identification des entités nommées dans les images et les vidéos [11, 9], et ils concernent, pour la plupart, la reconnaissance faciale [6, 4].

Notre proposition consiste en un système automatique capable d'identifier des entités nommées visuelles apparaissant dans des images et des vidéos. Il peut être très compliqué d'identifier visuellement une entité nommée, en particulier quand sa représentation visuelle est très petite (quelques dizaines de pixels). En effet, alors qu'il est possible de représenter une entité nommée textuellement par un petit synset, un synset visuel, quant à lui, doit pouvoir gérer de nombreuses variations (définition, encodage, échelle, rotation, éclairage, etc.). Il est plus difficile d'identifier une entité parmi des milliers que parmi une douzaine, mais ce défi scientifique est bien plus intéressant et réaliste.

2 Approche proposée

2.1 Création de dictionnaires

Nous appelons “dictionnaire” une liste d'entités nommées, regroupées pour leur appartenance à certains concepts de niveau hiérarchique supérieur (par exemple, personnes morales, personnes physiques, peintures, bâtiments, etc.). À chaque entité nous associons un ensemble d'images afin de représenter toute sa diversité visuelle. La manière la plus simple de créer un dictionnaire consiste à importer une base données existante, mais celles-ci sont relativement peu fréquentes et assez incomplètes (en particulier les bases de données collaboratives).

Aussi, la manière la plus courante de créer ce genre de dictionnaire revient à parcourir le Web pour télécharger des images. Pour construire notre propre dictionnaires de personnes morales, nous avons commencé par rassembler une liste de 25 000 entités trouvées dans les listes Wikipédia, classements des plus grandes entreprises, et sites Web spécifiques traitant de clubs sportifs, de voitures, de partis politiques etc.

Pour toutes les entités, nous avons alors utilisé un moteur de recherche d'images bien connu, en entrant les représentations textuelles des entités nommées, de manière à obtenir leurs représentations visuelles. Les résultats du moteur de recherche sont parfois confus, hormis pour les entités les plus connues, et les images téléchargées ne peuvent être considérées que comme étant faiblement étiquetées.

2.2 Identification

Pour ce qui est des vidéos à analyser, nous commençons par extraire quelques images clés à chaque changement significatif du contenu, par exemple nouveau plan, caméra en mouvement, apparition de nouveaux objets, etc. L'intervalle entre deux images clés peut donc facilement varier de 100 ms à 30 ms. Toutes les images clés détectées font alors l'objet d'une demande d'identification dans un système de récupération d'images par contenu, en recherchant dans toutes les images du dictionnaire (c.f. section 2.2.1). Puisque ces images sont toutes associées à l'une des entités nommées du dictionnaire, nous sommes en mesure de décider lesquelles parmi elles sont les plus probables (c.f. section 2.2.2). Lorsqu'il s'agit de photos mises en ligne par des utilisateurs, il nous suffit de passer l'étape d'extraction d'images clés et toutes les photos sont alors traitées comme des images clés.

2.2.1 Recherche d'images par le contenu

Toutes les images sont décrites par des descripteurs SIFT [12], qui sont ensuite compressées en vecteurs binaires de dimensions 128 en suivant la méthode ITQ [5]. L'étape de la recherche est similaire à celle décrite dans [10], c'est-à-dire basée sur une recherche approximative par KNN [7] et une méthode de RANSAC a-contrario pour la vérification de la cohérence géométrique [8]. À l'issue de cette étape, nous disposons d'un ensemble d'images M k similaires à la k ème requête, avec un score de similarité S i k pour chaque i ème image appariée.

2.2.2 Vote

On calcule le score de fiabilité de la e ème entité pour la k ème requête par l'équation suivante :

R e k = i = 1 M e k S i k

où  M e k représente la taille du sous-ensemble d'images associées dans le dictionnaire avec la e ème entité-nommée, et retrouvée avec le système de recherche par le contenu précédemment décrit, pour la k ème requête.

Ce score doit être normalisé entre 0 et 100% afin d'être affiché et compris par les utilisateurs. Il est calculé par :

R ^ e k = tanh max R e k - α β , 0

où  α = 2 et β = 8 0 , fixés tout deux de manière empirique, après essais auprès d'utilisateurs non expérimentés.

Nous n'affichons que les entités présentant un score R ^ e k supérieur à 3%. Ce seuil a été choisi pour favoriser un rappel élevé (préféré par les utilisateurs experts), plutôt qu'une précision elevée (plus adaptée aux utilisateurs non expérimentés).

Lorsqu'il s'agit d'une vidéo, nous conservons un score de fiabilité pour chaque détection (dans l'une des images clés) d'une entité. Mais nous affichons également un score global pour chaque entité détectée dans la v ème vidéo. Ce score global est calculé comme suit :

Ĝ e v = max k K R ^ e k

où K est l'ensemble des images clés de la vidéo v .

Au vu du score global, nous filtrons à nouveau les entités affichées en ne conservant que celles figurant dans le top-25 des scores de fiabilité Ĝ e v , ainsi que celles dont le score est supérieur à 50 %, même si elles ne figurent pas dans le top-25.

2.2.3 Résultats

De manière à évaluer le système, nous avons construit une base de test composées de 2 000 images issues de Flickr, contenant 285 entités nommées différentes. Les 100 demandes utilisées pour trouver ces images sont constituées des noms des entités les plus connues dans le domaines des événement sportifs français (Tour de France, Roland Garros, 24h du Mans, etc.). Bien évidemment, de nombreuses autres entités moins connues que celles recherchées apparaissent dans ces images, ils nous a donc fallut annoter manuellement la vérité terrain. Le graphique de la figure ci-dessous montre la courbe précision/rappel. Nous pouvons constater qu'avec cet ensemble de données de test assez réaliste, nous atteignons une précision de 80 % pour un rappel de 30 %. Nous pouvons aussi remarquer qu'il nous est actuellement impossible d'obtenir plus de 40 % de rappel, probablement en raison du volume d'images mal étiquetées dans le dictionnaire, et en raison de la très petite taille des entités figurant dans les images de test. Ces images ne sont pas très grosses non plus : leur taille moyenne est de 214 Kpx.

Dans le cas d'une charge constante (analyse des 2 000 images de tests), DigInPix peut traiter une image en moins de 2 secondes. En conditions réelles, ce temps peut être légèrement plus long, en raison de la charge serveur. Le temps de traitement peut même atteindre des dizaines de secondes pour les grandes images car la complexité de l'algorithme est quasiment linéaire en fonction du nombre de descripteurs (et donc d'une manière générale de la taille de l'image).

original

3 Démonstrateur

DigInPix possède une interface web html5 (flat-design et responsive). Toutes les actions sont accessibles sur la page unique de cette interface. Il y a deux actions principales à réaliser avec DigInPix : la première se résume à analyser une photo qui nous appartient, la deuxième consiste à parcourir les données analysées et les dictionnaires.

3.1 Analyser une image nous appartenant

Les utilisateurs peuvent charger leur propre image depuis leur disque dur ou depuis l'URL d'une image. À l'issue de la procédure d'identification, l'interface affiche l'image analysée, avec une liste des entités nommées détectées et un score de fiabilité pour chacune. L'image ci-dessous est un exemple d'une image analysée, où DigInPix a identifié six entités nommées, classées par fiabilité. Nous pouvons cliquer sur une entité pour accéder à toutes ses informations, et nous pouvons passer directement aux documents dans lesquels cette entité a été identifiée.

original

3.2 Parcourir les données

Il existe deux catégories de données que l'on peut parcourir dans DigInPix : les données des dictionnaires et les documents analysés. Les utilisateurs peuvent parcourir les entités nommées dans chaque dictionnaire, les classer par nom ou par leur nombre de détections dans l'ensemble des documents analysés, et les filtrer par leur première lettre. Pour chaque entité, DigInPix affiche la liste des images représentatives glanées sur le Web, et utilisées par l'algorithme pour identifier cette entité. Les documents analysés (images ou vidéos) sont répartis en collections cohérentes. Nous pouvons cliquer sur l'une d'entre elles pour voir la liste des entités nommées détectées. Si le document est une vidéo, DigInPix l'affiche dans un player vidéo open-source, enrichi de repaires temporels indiquant les moments où chaque entité a été détectée. Ces moments sont symbolisés par des points sur une ligne, comme le montre l'illustration ci-dessous. De nombreux boutons sont disponibles pour manipuler le player, et le petit engrenage dans le coin inférieur droit permet d'activer ou désactiver les infobulles expliquant leur usage.

original

4 Conclusions

DigInPix est notre première tentative de fournir un accès publique à nos outils d'analyse d'images, et nous pensons qu'il existe une grande marge d'amélioration. L'une des premières améliorations pourrait consister à ajouter des nouveaux dictionnaires comme des bâtiments, lieux, peintures, visages, parmi de nombreux autres. Une autre très bonne amélioration serait de nettoyer les images du dictionnaire mal étiquetées qui sont la cause de la plupart des erreurs d'identification. Pour cela, nous avons l'intention de développer des nouvelles interfaces pour offrir aux utilisateurs un moyen simple de participer et de nous transmettre leurs retours. Enfin, nous pourrions améliorer l'expérience utilisateur en dessinant l'emplacement exacte des entités nommées détectées dans les images et les vidéos, comme le permet notre lecteur vidéo, ainsi que suivre à la trace les entités entre les images clés.



Bibliographie

[1] R. Arandjelovic and A. Zisserman. Three things everyone should know to improve object retrieval. In Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on , pages 2911–2918. IEEE, 2012.

[2] D. Carmel, M.-W. Chang, E. Gabrilovich, B.-J. P. Hsu, and K. Wang. ERD 2014: Entity recognition and disambiguation challenge. SIGIR Forum , 2014.

[3] O. Chum, A. Mikulik, M. Perdoch, and J. Matas. Total recall ii: Query expansion revisited. In Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on , pages 889–896. IEEE, 2011.

[4] L. El Shafey and S. Marcel. Scalable probabilistic models: Applied to face identification in the wild. In European Association for Biometrics-8th European Biometrics Research and Industry Awards , number EPFL-CONF-201763, 2014.

[5] Y. Gong, S. Lazebnik, A. Gordo, and F. Perronnin. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. Pattern Analysis and Machine Intelligence, IEEE Transactions on , 35(12):2916–2929, 2013.

[6] S. C. Hoi, D. Wang, I. Y. Cheng, E. W. Lin, J. Zhu, Y. He, and C. Miao. Fans: Face annotation by searching large-scale web facial images. In Proceedings of the 22Nd International Conference on World Wide Web Companion , WWW ’13 Companion, pages 317–320, Republic and Canton of Geneva, Switzerland, 2013. International World Wide Web Conferences Steering Committee.

[7] A. Joly and O. Buisson. A posteriori multi-probe locality sensitive hashing. In Proceedings of the 16th ACM international conference on Multimedia , pages 209–218. ACM, 2008.

[8] A. Joly and O. Buisson. Logo retrieval with a contrario visual query expansion. In Proceedings of the 17th ACM international conference on Multimedia , pages 581–584. ACM, 2009.

[9] J. Krapac, F. Perronnin, T. Furon, and H. Jégou. Instance classification with prototype selection. In Proceedings of International Conference on Multimedia Retrieval , page 431. ACM, 2014.

[10] P. Letessier, O. Buisson, and A. Joly. Consistent visual words mining with adaptive sampling. In Proceedings of the 1st ACM International Conference on Multimedia Retrieval , page 49. ACM, 2011.

[11] V. Leveau, A. Joly, O. Buisson, P. Letessier, and P. Valduriez. Recognizing thousands of legal entities through instance-based visual classification. In Proceedings of the ACM International Conference on Multimedia , pages 1029–1032. ACM, 2014.

[12] D. G. Lowe. Object recognition from local scale-invariant features. In Computer vision, 1999. The proceedings of the seventh IEEE international conference on , volume 2, pages 1150–1157. Ieee, 1999.

[13] S. Romberg, L. G. Pueyo, R. Lienhart, and R. Van Zwol. Scalable logo recognition in real-world images. In Proceedings of the 1st ACM International Conference on Multimedia Retrieval , page 25. ACM, 2011.

[14] K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556 , 2014.

[15] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going deeper with convolutions. CoRR , abs/1409.4842, 2014.

Remerciements

Nous souhaitons ici remercier les développeurs ayant participé à ce projet, mais dont les noms ne peuvent être cités pour des raisons légales.