FR2875622A1 - Procede et dispositif de verification d'entites multimedia - Google Patents

Abstract

Un procédé pour vérifier la correspondance entre une première et une seconde entité multimédia, chaque entité multimédia comprenant une pluralité d'unités d'intérêt. Le procédé comporte les étapes suivantes : mise en correspondance d'informations de contenu local de la première et de la seconde entité multimédia (E33), lesdites informations de contenu local étant associées à des unités d'intérêt, mise en correspondance géométrique d'unités d'intérêt de la première et de la seconde entité multimédia,définition, dans l'une des entités multimédia, d'une zone comportant les unités d'intérêt résultant de la mise en correspondance géométrique, estimation d'au moins un critère de fiabilité à partir du résultat des étapes de mises en correspondance sur la zone définie (E33), comparaison dudit au moins un critère de fiabilité estimé à un seuil prédéterminé (E34), en fonction du résultat de la comparaison, décision sur la correspondance entre la première et la seconde entité multimédia,

Description

1 2875622 5

La présente invention concerne un procédé et un dispositif de vérification d'entités multimédia. Plus particulièrement, la présente invention concerne un procédé et un dispositif de vérification d'entités multimédia adaptés à la vérification des images numériques.

L'invention s'applique dans le domaine de la recherche et de la mise en correspondance d'entités multimédia basée sur leur contenu.

Le réseau Internet représente un immense réservoir d'informations en tous genres. L'image y prend une part de plus en plus grande, et il devient très difficile de contrôler l'usage qui est fait d'une image publiée sur un site Web.

Des dispositifs de vérification d'images ont vu le jour pour essayer de contrôler l'usage de certaines images sur le réseau Internet.

La fonction d'un dispositif de vérification d'images sur le réseau Internet est de déterminer si des images, préalablement enregistrées auprès d'un opérateur d'enregistrement ou auprès de l'opérateur gérant le dispositif de vérification d'images afin de les protéger, sont publiées sur un ou plusieurs sites Web donnés. Ainsi, une application particulière d'un tel dispositif est la recherche sur le réseau Internet d'images dont l'usage est illégal.

Les images préalablement enregistrées sont celles dont l'utilisation veut être contrôlée par les ayants droits. Ces ayants droits sont par exemple, les agences de distribution de photos, les photographes auteurs ou les créateurs des images.

Pour ce faire, les images sont récupérées des sites Web donnés, et chaque image est comparée, selon un dispositif de vérification, aux images préalablement enregistrées.

2 2875622 La performance d'un dispositif de vérification d'images se mesure en termes de compromis entre le taux de fausses alarmes, le taux de non détection et le temps de traitement. En effet, le système doit pouvoir reconnaître une même image, même si celle-ci a subi une modification, mais doit éviter de décider qu'il s'agit d'une même image alors que ce n'est pas le cas.

Le taux de fausses alarmes est égal au pourcentage des images publiées qui sont détectées comme correspondant à une image enregistrée alors que ce n'est pas la même image.

Le taux de non détection correspond au pourcentage des images publiées non détectées par le dispositif de vérification d'images alors que ces images publiées sont les mêmes que des images déjà enregistrées.

Le temps de traitement correspond au temps nécessaire pour traiter les images à vérifier (images provenant par exemple du Web).

Les dispositifs de vérification d'images demandent une optimisation quant à leur complexité, car des contraintes existent sur le temps de traitement et les ressources matérielles disponibles.

En effet, le dispositif de vérification d'image doit être capable de traiter en continu de larges volumes d'images à vérifier dans une durée acceptable par l'utilisateur, ce qui impose une limite supérieure en temps de traitement, avec un coût minimum.

Les dispositifs de vérification d'images connus font généralement appel à une technique de comparaison de la description de l'image publiée sur un site Web avec les descriptions des images protégées. En fonction du résultat de cette comparaison, il est alors décidé si l'image publiée correspond ou non à une image protégée particulière.

Ainsi, on connaît, par l'article intitulé Local grayvalue invariants for image retrieval de C. Schmid et R. Mohr, IEEE Transactions on Pattern Analysis and Machine intelligence, Vol. 19, N 5, pages 530 à 534, 1997, des 30 techniques de description de contenu dites locales .

Ces techniques de description de contenu consistent à extraire par calcul des descripteurs visuels caractérisant l'image. Une pluralité de descripteurs visuels peuvent être calculés et ceux-ci peuvent être de différents 3 2875622 types. Des descripteurs dits globaux et I ou des descripteurs dits locaux peuvent être identifiés.

Selon les techniques de description de contenu local, des points d'intérêt sont détectés dans les images. Ces points d'intérêt peuvent être définis comme des positions p où l'intensité du signal de l'image, aussi bien pour les images en niveau de gris que pour les images en couleur, varie fortement et présente donc des singularités, par exemple, des coins. Un tel dispositif de détection des points d'intérêt est, par exemple, décrit dans le document FR 03.01545.

À chaque point d'intérêt est associé un contenu local de l'image. Ce contenu local comprend un ensemble de valeurs caractéristiques, décrit notamment dans un vecteur v à plusieurs dimensions.

Un exemple de caractérisation de contenu local d'une image en niveau de gris, basée sur des combinaisons d'opérateurs de dérivés de Gaussiennes est décrit dans le document de C. Schmid et R. Mohr cité précédemment.

Le document intitulé Utilisation de la couleur pour l'appariement et l'indexation d'images Rapport de Recherche INRIA n 3269, septembre 1997, de P. Gros et al. et le document intitulé Content-based retrieval using local descriptors: problems and issues from a database perspective , Pattern Analysis and Applications, Vol. 4, pages 108 à 124, 2001, Spinger-Verlag, de L. Amsaleg et P. Gros, décrivent des exemples de caractérisation de contenu local d'une image couleur à trois composantes.

Selon ces exemples, la dimension du vecteur est égale à 23 ou 25 24.

La caractérisation des points d'intérêt à travers la caractérisation de contenu local de l'image présente l'avantage que la mise en correspondance de ces points d'intérêt avec des points d'intérêt d'une seconde image est possible, même si ces images ont été recadrées. Ainsi, la description de contenu local n'est que partiellement altérée lors d'un recadrage d'une image, elle est donc dite robuste .

Un dispositif de vérification exacte par le contenu à l'aide de descripteurs locaux est décrit dans le document de C. Schmid et R. Mohr, et dans le document de L. Amsaleg et P. Gros, cités précédemment.

4 2875622 Un tel dispositif est décrit en référence à la figure 1.

Comme représenté à la figure 1, le dispositif de vérification reçoit en entrée une image publiée IP et comporte une base d'images propriétaires IC. La base d'images propriétaires comprend l'ensemble de descripteurs des images propriétaires enregistrées.

Le mécanisme de vérification comporte une première étape El1 de calcul de descripteurs locaux de l'image publiée IP. Ce calcul peut être réalisé selon les techniques décrites dans le document de P. Gros et al. cité précédemment.

L'étape E11 est suivie d'une étape E12 de sélection qui prévoit de sélectionner un nombre limité d'images propriétaires IC pour l'image publiée IP. Un nombre K d'images propriétaires ICI à ICK est sélectionné. Cette sélection consiste à effectuer une comparaison des descripteurs de l'image publiée IP calculés à l'étape E11 avec les descripteurs des images propriétaires enregistrées IC.

On sélectionne ainsi les K plus proches voisins, c'est-à-dire que l'on recherche les K images parmi les images enregistrées IC qui sont les plus proches de l'image publiée IP.

Le processus de recherche comprend une première étape de mise en correspondance de chacun des descripteurs d'information de contenu local de l'image publiée IP avec l'ensemble des descripteurs d'information de contenu local des images propriétaires IC.

Ensuite, un classement global des images propriétaires les plus proches s'effectue au moyen d'un algorithme de vote majoritaire. Ainsi, les images propriétaires IC sont classées selon le nombre de descripteurs de contenu local qui sont mis en correspondance avec les descripteurs de contenu local de l'image publiée IP.

Le nombre de descripteurs mis en correspondance pour chaque image est appelé score .

Les K images les plus proches correspondent donc aux K scores les plus élevés.

La mise en correspondance de chaque descripteur de l'image publiée IP avec les descripteurs des images propriétaires IC s'effectue au moyen de calcul de distances de l'information de contenu local autour des 2875622 points d'intérêt modélisés sous la forme de vecteur v. Ainsi, la distance entre les vecteurs de description est une distance Euclidienne ou de Mahalanobis.

Afin d'affiner la correspondance entre les points d'intérêt, une variante consiste à prendre également en compte des contraintes géométriques, tel que décrit dans le document de C. Schmid et R. Mohr cité précédemment.

Cette variante présente l'avantage d'accroître la précision de correspondance mais au prix d'une complexité accrue.

Différentes stratégies sont possibles pour le calcul des scores. Il est possible, par exemple, pour chaque vecteur présentant une information de contenu local de l'image publiée, d'incrémenter le score de chaque image propriétaire dont au moins un vecteur de l'image publiée se situe à une distance inférieure à un certain seuil.

Il est également possible d'incrémenter seulement le score des images propriétaires dont l'un des vecteurs représentant l'information de contenu local est l'un des plus proches du vecteur de contenu local de l'image publiée. Ainsi, seuls les scores des images propriétaires ayant des vecteurs les plus proches sont incrémentés.

À l'issue de l'étape E12, une liste de K images propriétaires ICI à ICK sont sélectionnées, chacune de ces images ayant un score Score(IP;).

Le processus de vérification d'images, selon l'art antérieur, comprend ensuite une étape de décision E13.

Cette étape de décision E13 consiste, pour chacune des K images propriétaires de la liste précédemment sélectionnée, à comparer la valeur du score Score(IP;), i allant de 1 à K, à un seuil S. En fonction du résultat de cette comparaison, le processus de décision détermine si l'image publiée IP correspond à une image propriétaire sélectionnée ICk (k = 1 à K) correspondante.

En effet, si l'image publiée IP correspond à l'image propriétaire ICk, alors la valeur du score Score(lP;) est supérieure à une valeur déterminée S. La valeur du seuil S est choisie de telle sorte à fournir une bonne performance en nombre de détections par rapport aux fausses alarmes mesurées expérimentalement.

6 2875622 L'inconvénient d'un tel dispositif de vérification réside dans l'étape de décision. En effet, le seuil S de décision dépend implicitement de la base des images propriétaires IC.

L'inconvénient d'un tel seuil réside dans le fait qu'une bonne valeur de seuil S pour un ensemble d'images propriétaires de type donné et ayant un contenu donné, n'est plus une bonne valeur pour un ensemble d'images propriétaires ayant un contenu différent. C'est aussi le cas lorsque le nombre d'images propriétaires varie.

En effet, les scores Score(IP;) étant obtenus par un algorithme de 10 vote, sont relatifs au nombre et à la nature des images propriétaires.

Ainsi, dans le cas où le contenu de l'ensemble des images propriétaires varie de façon dynamique, le seuil S est inadapté.

Dans les systèmes de vérification d'images où les clients du système peuvent ajouter et supprimer des images à tout moment, le contenu de l'ensemble des images propriétaires, ainsi que le nombre de ces images sont amenés à varier constamment.

Dans ce cas, la valeur du seuil S n'a pas de signification en soi. II est donc impossible de relier le paramétrage de la décision avec la performance mesurée en termes de compromis entre bonne détection et fausses alarmes.

Ainsi, ce système de vérification n'est pas apte à fournir une information fiable à l'opérateur ou aux clients de ce système.

L'application de ces techniques de vérification pose donc un problème compte tenu du manque de fiabilité de cette vérification lorsque l'ensemble des images propriétaires est amené à varier.

La présente invention vise à remédier à au moins un des inconvénients précités en proposant un procédé de vérification basé sur une étape de décision non liée à un seuil S dépendant du nombre et du contenu de l'ensemble des images propriétaires.

Ainsi, la présente invention concerne un procédé de vérification d'entités multimédia dans lequel un bon niveau de performance est garanti sous la contrainte d'un temps de traitement limité, indépendamment de l'ensemble des images propriétaires.

A cette fin, la présente invention vise à fournir un procédé de vérification de la correspondance entre une première entité multimédia et une 7 2875622 seconde entité multimédia, chaque entité multimédia comprenant une pluralité d'unités d'intérêt. Le procédé comporte les étapes suivantes: - mise en correspondance d'informations de contenu local de la première entité multimédia avec des informations de contenu local de la seconde entité multimédia, lesdites informations de contenu local étant associées à des unités d'intérêt, - mise en correspondance géométrique d'unités d'intérêt de la première entité multimédia avec des unités d'intérêt de la seconde entité multimédia, - définition, dans l'une des entités multimédia, d'une zone comportant les unités d'intérêt résultant de l'étape de mise en correspondance géométrique, - estimation d'au moins un critère de fiabilité à partir du résultat des étapes de mise en correspondance d'informations de contenu local et de mise en correspondance géométrique sur la zone définie, - comparaison dudit au moins un critère de fiabilité estimé à un seuil prédéterminé, - en fonction du résultat de la comparaison, décision sur la correspondance entre la première entité multimédia et la seconde entité multimédia.

Le principe du procédé de vérification d'entités multimédia selon l'invention repose sur l'élaboration de deux types de mise en correspondance, puis la définition d'une zone comportant les unités d'intérêt mises en correspondances géométriquement.

L'utilisation de techniques adaptées à chacune des étapes, permet d'établir un ensemble de résultats de mise en correspondance qui permet ensuite d'estimer un critère de fiabilité. Ce critère étant donc défini par rapport aux étapes de mise en correspondance effectuées entre les deux entités multimédia, il permet d'obtenir une valeur de critère au plus juste quant à la similarité, et donc permet d'obtenir une bonne performance en termes de nombre de détection de correspondances et de fausses alarmes.

Selon une caractéristique, à chaque entité multimédia est associé au moins un descripteur déterminé préalablement à l'étape de mise en correspondance, ledit au moins un descripteur associé à au moins une unité d'intérêt de l'entité multimédia comprenant au moins une information de contenu local et au moins une information de position, ledit au moins un 8 2875622 descripteur étant utilisé lors des étapes de mise en correspondance d'informations de contenu local et de mise en correspondance géométrique.

A chaque entité multimédia, on associe au moins un descripteur qui est utilisé pour l'ensemble des étapes du procédé de vérification, sans nécessiter ainsi, le calcul de nouveaux descripteurs en cours de traitement.

Les étapes de mises en correspondance sont effectuées sur la base des mêmes descripteurs.

Selon une autre caractéristique, l'étape de mise en correspondance d'informations de contenu local de la première entité multimédia avec des informations de contenu local de la seconde entité multimédia, comporte les sous étapes suivantes: - pour chaque information de contenu local de la première entité multimédia, sélection, parmi les informations de contenu local de la seconde entité multimédia, des informations sensiblement proches de l'information de contenu local concernée, définissant ainsi un premier ensemble de correspondances dont chacune forme un couple entre l'information de contenu local concernée de la première entité et l'une des informations sensiblement proches de la seconde entité, - pour chaque information de contenu local de la seconde entité multimédia, sélection parmi les informations de contenu local de la première entité multimédia, des informations sensiblement proches de l'information de contenu local concernée, définissant ainsi un second ensemble de correspondances dont chacune forme un couple entre l'information de contenu local concernée de la seconde entité et l'une des informations sensiblement proches de la première entité, - détermination de l'intersection du premier et du second ensemble de correspondances.

En effet, selon cette étape du procédé de vérification, la mise en correspondance des unités d'intérêt multimédia est réalisée sur les informations de contenu local présentant l'avantage que la mise en correspondance est possible même si les images ont été recadrées, la mise en correspondance d'informations de contenu local étant robuste.

Selon une caractéristique dépendante de la caractéristique précédente, la sélection d'un ensemble de correspondances pour une 9 2875622 information de contenu local concernée d'une entité multimédia comporte les étapes suivantes: - calcul des distances entre ladite information de contenu local concernée et chacune des informations de contenu local de l'autre entité multimédia, - détermination des distances inférieures à un seuil prédéterminé, définissant ainsi l'ensemble de correspondances concerné.

En effet, selon ces étapes, on définit les unités d'intérêt qui semblent similaires d'après les informations de contenu local associées.

Selon un premier aspect, le calcul des distances fait intervenir une distance Euclidienne.

Selon un second aspect, le calcul des distances fait intervenir une distance de Mahalanobis.

Selon une caractéristique, l'étape de mise en correspondance géométrique comporte les étapes suivantes: - détermination d'une éventuelle transformation géométrique nécessaire pour obtenir la première entité multimédia à partir de la seconde entité multimédia, - détermination d'un ensemble d'unités d'intérêt de la première et de la seconde entité pour lesquelles la transformation géométrique permet de faire correspondre une unité d'intérêt de la première entité multimédia et une unité d'intérêt de la seconde entité multimédia.

En effet, afin d'améliorer la détection de la correspondance de deux entités multimédia, selon le procédé, on détermine la transformation géométrique des unités d'intérêt des entités multimédia afin d'identifier l'ensemble des unités d'intérêt des entités multimédia qui sont en vraie correspondance géométriquement selon la transformation géométrique déterminée.

De cette transformation géométrique, il est ensuite possible de déduire les unités d'intérêt en correspondance.

Plus particulièrement, l'étape de détermination d'une éventuelle transformation géométrique comprend une estimation de la cohérence géométrique entre les informations de position associées aux informations de contenu local mises en correspondance.

2875622 Selon une caractéristique, la zone correspond à l'une des entités multimédia.

En effet, selon un cas particulier, la zone de correspondance comprend l'entité multimédia dans son intégralité.

Selon une autre caractéristique, la zone comporte des unités d'intérêt n'ayant pas été mis en correspondance lors des étapes de mises en correspondance.

En effet, la zone définie suite à l'étape de mise en correspondance géométrique, peut également contenir des unités d'intérêt non mises en correspondance à partir de leurs informations de contenu ou à partir de leur position géométrique.

Selon une caractéristique, le résultat des étapes de mise en correspondance d'informations de contenu local et de mise en correspondance géométrique sur les unités d'intérêt présentes dans la zone comprend: - le nombre d'unités d'intérêt présentes dans ladite zone, - le nombre d'unités d'intérêt résultant de l'étape de mise en correspondance d'informations de contenu local, et qui sont présentes dans la zone et le nombre d'unités d'intérêt résultant de l'étape de mise en correspondance géométrique et pour lesquelles la distance entre la position correspondant à une information de contenu local de la première entité multimédia et la position correspondant à une information de contenu local de la seconde entité multimédia est inférieure à un seuil prédéterminé.

Cette caractéristique consiste à déterminer le résultat des étapes de mise en correspondance des informations de contenu local et de mise en correspondance géométrique, restreintes à la zone de correspondance sélectionnée. Ce résultat sera ensuite utilisé pour le calcul du critère de décision.

Selon une caractéristique, le résultat des étapes de mise en 30 correspondance est en outre fonction de la surface de la zone.

Selon une autre caractéristique, le résultat des étapes de mise en correspondance est en outre fonction de la transformation géométrique.

Selon une caractéristique, la seconde entité multimédia fait partie d'un ensemble de secondes entités multimédia.

11 2875622 Ainsi, le procédé de vérification selon l'invention consiste à vérifier qu'une première entité multimédia correspond ou non à une seconde entité multimédia parmi une multitude de secondes entités.

Selon une caractéristique, dépendante de la caractéristique précédente, préalablement à l'étape de mise en correspondance d'information de contenu local, le procédé comprend une étape de sélection, parmi l'ensemble de secondes entités multimédia, d'une pluralité de secondes entités multimédia proches de ladite première entité multimédia, en effectuant une recherche sur le contenu des dites première et secondes entités multimédia de l'ensemble des secondes entités multimédia, les étapes de mise en correspondance, d'estimation, de comparaison et de décision étant appliquées sur ladite pluralité de secondes entités multimédia sélectionnées.

Cette étape de sélection permet de réaliser la vérification de la correspondance d'entités multimédia sur les secondes entités multimédia sélectionnées, qui sont donc, en nombre réduit par rapport à toutes les secondes entités de l'ensemble de secondes entités, ce nombre étant de préférence fixe.

Selon une caractéristique dépendante des caractéristiques précédentes, l'estimation du critère de fiabilité est effectuée à partir du rapport entre une probabilité que la première entité multimédia ne corresponde pas à l'une des secondes entités multimédia et une probabilité que la première entité multimédia corresponde à l'une des secondes entités multimédia, ces deux probabilités étant fonction du résultat des étapes de mise en correspondance.

Ainsi est exprimé le compromis entre une bonne détection et les fausses alarmes.

La présente invention a également pour objectif de fournir un dispositif de vérification de la correspondance entre une première entité multimédia et une seconde entité multimédia qui remédie aux inconvénients mentionnés ci-dessus de la technique antérieure.

Le dispositif de vérification d'entités multimédia selon l'invention pour déterminer si une première entité multimédia correspond à une seconde entité multimédia, chaque entité multimédia comprenant une pluralité d'unités d'intérêt, est caractérisé en ce qu'il comporte: 12 2875622 des moyens de mise en correspondance d'informations de contenu local de la première entité multimédia avec des informations de contenu local de la seconde entité multimédia, lesdites informations de contenu local étant associées à des unités d'intérêt, - des moyens de mise en correspondance géométrique d'unités d'intérêt de la première entité multimédia avec des unités d'intérêt de la seconde entité multimédia, des moyens de définition, dans l'une des entités multimédia, d'une zone comportant les unités d'intérêt mises en correspondance géométrique, des moyens d'estimation d'au moins un critère de fiabilité à partir du résultat de la mise en correspondance d'informations de contenu local et de la mise en correspondance géométrique sur la zone définie, - des moyens de comparaison dudit au moins un critère de fiabilité estimé à un seuil prédéterminé, - des moyens de décision sur la correspondance entre la première entité multimédia et la seconde entité multimédia, en fonction du résultat de la comparaison.

Ce dispositif présente les mêmes avantages que le procédé de vérification brièvement décrit ci-dessus.

Selon d'autres aspects, l'invention concerne aussi des dispositifs de traitement d'information aptes à fonctionner en tant que dispositifs de vérification d'entités multimédia tels que décrits brièvement ci-dessus, un système de télécommunications, un dispositif de stockage d'entités multimédia, des supports d'information lisibles par un système informatique ainsi que des programmes d'ordinateur pour une mise en oeuvre des procédés de l'invention décrits brièvement ci-dessus.

D'autres caractéristiques et avantages de la présente invention apparaîtront plus clairement à la lecture de la description qui va suivre faite en référence aux dessins annexés, sur lesquels: la figure 1 montre une vue d'un dispositif de vérification d'images selon l'état de la technique; la figure 2 montre une vue globale d'un dispositif de vérification d'images selon l'invention; 13 2875622 la figure 3 est un organigramme fonctionnel montrant de manière globale un procédé de vérification d'images numériques; la figure 4 est un organigramme fonctionnel du processus de mise en correspondance d'une image publiée avec une image propriétaire selon 5 l'invention; la figure 5 est un organigramme fonctionnel du processus de la mise en correspondance des informations de contenu local de deux images selon l'invention; la figure 6 présente deux scénarii illustrant le recadrage d'une 10 image et la photocomposition; la figure 7 présente de manière schématique la mise en correspondance résultant de l'invention; la figure 8 représente de manière schématique un appareil dans lequel est mise en oeuvre l'invention.

En référence à la figure 2, le dispositif de vérification d'images 1 reçoit en entrée des entités multimédia de référence à protéger qui sont fournies par des clients 2 et des entités multimédia courantes qui sont publiées par exemple sur des sites Web 3.

Les entités multimédia de référence peuvent être par exemple, de la vidéo et des images IC qui sont fournies par des clients propriétaires de ces entités. Les entités multimédia courantes sont du même type que les entités multimédia de référence cependant il s'agit d'entités publiées qui doivent faire l'objet d'une vérification déterminant s'il s'agit ou non d'entités propriétaires protégées.

Selon la figure 2, le dispositif 1 compare des images publiées IP avec des images propriétaires IC en vue de déterminer s'il s'agit d'images propriétaires protégées.

Dans cette forme de réalisation, les images IC et IP sont transmises au dispositif 1 à travers un réseau de communication 4, par exemple, le réseau Internet. Dans d'autres formes de réalisation, les images IC et IP peuvent être chargées dans le dispositif 1 à partir, par exemple, d'une disquette ou d'un CD-ROM.

Le dispositif de vérification d'images 1 délivre en sortie une information d'alarme AL lorsqu'une image publiée IP présente un niveau de 14 2875622similarités élevé avec une image propriétaire 1C enregistrée dans le dispositif 1. La détection d'un niveau de similarités élevé pour une image publiée IP indique une probabilité élevée pour que les images IP et IC soient les mêmes.

Les principaux processus de traitement réalisés dans le dispositif de vérification d'images 1 sont représentés à la figure 2. Ces processus de traitement comprennent notamment un processus d'enregistrement d'images propriétaires 10, un processus de collecte d'images publiées 11, et un processus de vérification d'images 12.

En référence à la figure 3, est décrit le procédé selon l'invention de vérification de la correspondance entre une première image publiée IP et une image propriétaire IC faisant partie des images propriétaires enregistrées.

La figure 3 représente l'algorithme correspondant à des étapes du procédé selon l'invention, cet algorithme comportant différentes instructions ou portions de code logiciel qui, lorsqu'elles sont exécutées, permettent de mettre en oeuvre le procédé.

L'algorithme comporte une première étape E31 de détermination d'un ou de plusieurs descripteurs locaux {d_IP} associé à au moins une unité d'intérêt d'une première image publiée IP, une unité d'intérêt étant, par exemple, un point d'intérêt. Cette étape consiste à extraire par calcul, des descripteurs d_IP caractérisant l'image publiée IP.

Ainsi, conformément à l'invention, une pluralité de N;p descripteurs d IP peuvent être calculés, et ceux-ci peuvent être de différents types. Des descripteurs dits locaux sont, par exemple, utilisés dans cette forme de réalisation.

Par exemple, un descripteur local d'une unité d'intérêt de l'image, telle qu'un point d'intérêt d de l'image est constitué de deux informations indissociables: une information de position p du point d'intérêt, avec, par exemple, p = x+i.y en notation complexe, où x et y sont les coordonnées cartésiennes du point d'intérêt dans le repère de l'image, et une information de contenu local autour du point d'intérêt, information qui est organisée sous la forme d'un vecteur v et est associée à l'information de position p. 2875622 Ainsi, une image publiée IP est décrite selon N1p descripteurs locaux que l'on notera {d_IPi} i=1...Nip = {pi, vi} i= 1...NipÉ II en est de même pour la description des images propriétaires. Une image propriétaire IC est décrite selon Nic descripteurs locaux que l'on notera {d_IC1} i= 1...Nic = {pi, NA} i= 1... Nic.

Ces descripteurs ainsi déterminés sont ensuite utilisés lors des étapes de sélection et de décision, sans nécessiter de nouveau calcul de descripteurs.

L'étape E32 fait suite à l'étape E31 et consiste à effectuer une recherche dans la base des descripteurs propriétaires 30, des descripteurs les plus proches des descripteurs de l'image publiée. Cette étape de sélection peut s'effectuer de manière similaire à l'étape E12 de la figure 1.

Ensuite, des descripteurs d_IC de secondes images qui sont les plus proches des descripteurs d_IP, sont extraits de l'ensemble des descripteurs de l'ensemble de secondes images représenté dans la figure 2 par la base des images propriétaires 30. Les descripteurs d_IC extraits sont ceux correspondant aux images propriétaires sélectionnées ICk (k= 1 à K).

Le processus de sélection emploie des techniques de recherche basées sur le contenu des images afin de sélectionner les K images propriétaires ICI à ICK les plus proches d'une image publiée IP en cours de traitement. La proximité de deux images IP et IC doit ici être comprise au sens de la similarité visuelle entre celles-ci.

Pour cela, par exemple, une mise en correspondance de chacun des vecteurs contenant de l'information de contenu local de l'image publiée 25 avec ceux des images de la base propriétaire est effectuée.

Le nombre de vecteurs mis en correspondance entre deux images est appelé "score".

Les images propriétaires sélectionnées sont ensuite triées au moyen d'un algorithme de vote majoritaire. Ainsi, les images sont classées selon le nombre de leurs vecteurs qui sont mis en correspondance avec les vecteurs de l'image publiée.

Les K images les plus proches correspondent aux K scores les plus élevés.

16 2875622 La mise en correspondance de descripteurs de l'image publiée avec des descripteurs de la base des images propriétaires s'effectue au moyen de calculs de distance entre les vecteurs de descriptions en utilisant, par exemple, une distance Euclidienne ou une distance de Mahalanobis.

L'étape E32 est suivie de l'étape E33 qui prévoit de mettre en correspondance l'ensemble des descripteurs {d_IP} de l'image publiée avec chacun des descripteurs {d_IC} des images sélectionnées ICk à l'étape E32.

La mise en correspondance de l'étape E33 est réalisée sur les descripteurs calculés à l'étape E31, sans nécessiter une caractérisation supplémentaire et donc le calcul de nouveaux descripteurs.

Cette mise en correspondance est une correspondance des descripteurs d'une image publiée avec des descripteurs d'une image de la base des images propriétaires. Elle est donc indépendante des autres images de la base des images propriétaires.

Cette mise en correspondance est suivie du calcul d'une mesure, notée Cl, qui représente une estimation d'un critère de fiabilité de la mise en correspondance effectuée.

Plus précisément, la valeur de Cl est calculée en fonction d'un critère de décision Bayésien. Ce critère de décision se définit comme le rapport entre: d'une part, la probabilité que la première image ne corresponde pas à l'une des secondes images étant donné le résultat des étapes de mise en correspondance, c'est-à-dire la probabilité que les images ne se correspondent pas (hypothèse Hl) étant donné la réalisation de la mise en correspondance et, - d'autre part, la probabilité que la première image corresponde à l'une des secondes images étant donné le résultat des étapes de mise en correspondance, c'est-à-dire la probabilité que les images se correspondent (hypothèse HO) étant donné la réalisation de la mise en correspondance.

Ainsi, la valeur Cl se détermine par le rapport entre les pourcentages de chances entre les deux hypothèses.

La correspondance entre images selon l'invention inclut les cas où l'image publiée est, en tout ou en partie, la même image que l'image 17 2875622 propriétaire enregistrée, ou représente la même scène qu'une image propriétaire enregistrée.

Une mise en oeuvre selon l'invention de l'étape E33 est représentée à la figure 4 et sera détaillée ultérieurement.

L'étape E33 de la figure 3 est suivie de l'étape E34 au cours de laquelle on compare la valeur de Cl obtenue à l'étape E33 à une valeur de seuil prédéterminée, notée Sci(P) en vue de décider de la correspondance entre la première image, c'est-à-dire l'image publiée et une seconde image c'est-à-dire une image propriétaire en fonction du résultat de la comparaison.

Cette valeur de seuil dépend d'un contexte P défini comme le rapport des probabilités a priori que l'image publiée ne corresponde pas ou corresponde à une image propriétaire enregistrée.

Ainsi, selon l'invention, il est possible d'adapter le seuil en fonction de ce rapport de probabilités.

Pour une valeur de Sc1(P) donnée et une valeur de Cl calculée, le résultat de l'étape E34 permet de décider si l'image propriétaire IC correspond à l'image publiée IP ou non.

La valeur du seuil Sci(P) permet de fixer le niveau de fiabilité de la mise en correspondance.

Par exemple, si la valeur Cl est inférieur à Sci(P), alors l'image propriétaire IC est jugée correspondre à l'image publiée IP, la fiabilité de cette décision a comme valeur au moins Sc1(P).

Comme indiqué plus haut à l'étape E33, la figure 4 illustre l'ensemble des étapes de la mise en correspondance de descripteurs Id IP,Np ={P,v}14 n de l'image publiée avec des descripteurs d'une image propriétaire sélectionnée IC et le calcul de la mesure Cl, ces étapes devant être appliquées pour chacune des K images propriétaires sélectionnées.

Le processus de mise en correspondance débute par une étape 30 E41 de construction de la liste des points en correspondance.

Ainsi, la première étape E41 prévoit d'établir une liste L = t(d_IP,d_IC)} de correspondances des descripteurs de l'image 10 15 20 18 2875622 publiée d_IP avec des descripteurs d'une image propriétaire d_IC dont un mode de réalisation est décrit ci-après.

L'étape E41 met en correspondance des informations de contenu local, vlp, au sein de descripteurs d'une image publiée et des informations de contenu local, au sein de descripteurs, d'une image propriétaire enregistrée.

Le détail de cette étape d'établissement d'une liste de correspondances est fourni par la description qui suit, faite en référence à la figure 5 qui illustre un algorithme complétant celui de la figure 4. Cependant, d'autres modes de réalisation peuvent être envisagés.

L'algorithme de la figure 5 comporte une première étape E51 qui consiste à rechercher, pour chaque vecteur contenant de l'information de contenu local de l'image publiée l'ensemble PPV(v1p) des correspondances du vecteur vlp avec ses V plus proches voisins parmi les vecteurs vic contenant de l'information de contenu local de l'image propriétaire.

Parmi les techniques de recherche basée sur le contenu d'images et notamment de recherche basée sur la similarité visuelle, il est possible d'utiliser des techniques connues qui, à partir, des descripteurs locaux, déterminent une mesure de distance.

Ainsi, cette recherche peut s'opérer, par exemple, en déterminant, pour chaque information de contenu local de l'image publiée IP identifié par un vecteur vlp, l'ensemble des distances entre vlp et chaque information de contenu local de l'image propriétaire IC identifiée par un vecteur Cette distance peut être déterminée, par exemple, en utilisant une distance Euclidienne ou une distance de Mahalanobis.

Les éléments mis en correspondance dans la liste des plus proches voisins PPV(v1p) sont les informations de contenu local de l'image propriétaire v, c correspondant à l'information de contenu local de l'image publiée vlp dont les distances déterminées sont les plus faibles. Un nombre déterminé V d'éléments en correspondance est sélectionné.

Une distance de Mahalanobis entre les informations de contenu local est, par exemple, utilisée.

En outre, une contrainte peut également être ajoutée sur la valeur maximale de cette distance de Mahalanobis.

Ainsi, seuls les vecteurs ayant une distance de Mahalanobis inférieure à une valeur seuil Dm, sont susceptibles d'être en correspondance.

Dans ce cas, à chaque information de contenu vip d'une image publiée, est associé au plus un nombre V d'éléments en correspondance.

Selon un cas particulier, le nombre V d'éléments en correspondance est choisi égal à 1.

A l'étape E52, indépendamment de mais de façon similaire à l'étape E51, on recherche, pour chaque information de contenu local v,c d'une image propriétaire, l'ensemble PPV(v,c) des correspondances entre vic et ses V plus proches voisins parmi les vecteurs Enfin, à l'étape E53, on réalise l'intersection entre les deux ensembles de correspondances PPV(vip) et PPV(v1c) définis respectivement aux étapes E51 et E52. Ainsi, seules les correspondances présentes dans les deux ensembles sont considérées et énumérées dans la liste résultante L. Ainsi, à l'issue de l'étape E53 de la figure 5, on dispose d'une liste L = t(d_IP de Nc éléments mis en correspondance. Cette liste comprend un ensemble de couples, ayant comme premier élément, un descripteur de l'image publiée IP et en second élément, un descripteur de l'image propriétaire IC.

Il est ainsi mis fin à l'algorithme de construction de la liste de points en correspondance, élaborée selon une mise en correspondance des informations de contenu local de la figure 5.

De retour à la figure 4, l'étape E41, de construction de la liste de points en correspondance, est suivie de l'étape E42 qui est une étape d'estimation d'une correspondance géométrique globale, ayant pour but d'effectuer une mise en correspondance géométrique des unités d'intérêt des images.

En effet, l'étape E42 consiste à mesurer la cohérence géométrique des unités en correspondance de la liste L obtenue à l'étape E41.

Pour ce faire, on suppose qu'il existe une transformation géométrique T reliant les positions des correspondances entre descripteurs d'une image propriétaire et d'une image publiée de la liste L. L'étape E42 vise ainsi à estimer cette transformation.

2875622 Le choix du type de transformation T à considérer doit être dicté par le type de transformations géométriques que l'image propriétaire a pu subir pour conduire à l'image publiée.

Ce choix doit également être en cohérence avec la robustesse du détecteur de points d'intérêt et des informations de contenu local v vis-à-vis des transformations géométriques.

En effet, la transformation est estimée sur des correspondances établies préalablement sur la base des vecteurs de description de contenu local v.

On considère en particulier, par exemple, le groupe des transformations T de type similitude plane. En effet, la plupart des transformations effectuées sur une image numérique appartiennent à ce groupe.

Ce groupe inclut, par exemple, les translations issues principalement d'un recadrage, les mises à l'échelle et les rotations.

Les descripteurs locaux décrits dans l'article intitulé Utilisation de la couleur pour l'appariement et l'indexation d'images Rapport de Recherche INRIA n 3269, septembre 1997, de P. Gros et al., sont robustes à ce type de transformation.

Mathématiquement, une similitude plane T transforme une position pic dans l'image propriétaire IC en une position pIp dans l'image publiée IP selon la relation suivante, en notation complexe: p = T(plc) S(piceie + t) où: s est une valeur réelle représentant le facteur de changement d'échelle, O est une valeur réelle représentant l'angle de rotation (en radian), et t = t,, + i ty, est une valeur complexe représentant la translation (t,, ty) en coordonnées cartésiennes.

Afin de réaliser l'estimation de la transformation à quatre paramètres (s, 0, tX, ty), cette transformation doit être étudiée sur au moins deux couples de correspondances distinctes de la liste L. 21 2875622 Il est à noter que, numériquement, le modèle de similitude plane permet de prendre également en compte de légères variations d'angle de vue, théoriquement modélisées par des transformations homographiques voire affines.

II convient de noter que l'on peut également considérer les transformations affines et les transformations homographiques. L'estimation de la transformation géométrique est alors basée respectivement sur 6 paramètres et 8 paramètres. Le nombre d'éléments distincts de la liste L à considérer pour l'estimation de la transformation T doit être alors respectivement de 3 et de 4 éléments. Les calculs des points d'intérêt et des vecteurs de description locale doivent en outre être robustes à ce type de transformation.

Il est à noter que la liste L peut comporter de nombreuses fausses correspondances vis-à-vis du modèle géométrique, c'est-à-dire des correspondances identifiées qui ne sont pas de véritables correspondances. En effet, ces correspondances étant uniquement effectuées sur des informations de contenu local, des correspondances peuvent être identifiées sans que les informations de position associées correspondent entre elles.

ll est donc préférable d'utiliser une méthode d'estimation robuste qui permet d'éliminer l'influence des fausses correspondances (appelées outliers en Anglais).

Parmi les techniques d'estimation, il est possible d'utiliser, par exemple, les méthodes dites par échantillonnage consensuel ( sampling consensus en Anglais). En effet, elles sont particulièrement bien adaptées à ce type d'estimation car elles permettent de s'abstraire des fausses correspondances.

Ces méthodes dites par échantillonnage consensuel fonctionnent principalement selon le schéma suivant.

Dans une première étape, on choisit un sous-ensemble de correspondances nécessaires au calcul de la transformation géométrique T, puis la transformation T est déterminée.

Le sous-ensemble comprend, par exemple, deux correspondances pour la similitude.

Dans une seconde étape, à partir de la transformation ainsi déterminée, cette dernière est appliquée aux autres correspondances, puis les 22 2875622 correspondances (pn),pIc) pour lesquelles la transformation déterminée se vérifie sont comptées.

Cette vérification s'effectue en utilisant un critère de distance entre la position transformée et la position effective, i.e. T(prc) .E, où désigne le module (distance Euclidienne) et s est un seuil fixé à l'avance. Ces vraies correspondances sont dénommées inliers par opposition à outliers .

Les première et seconde étapes précédemment décrites sont réitérées pour d'autres sous-ensembles possibles.

Enfin, la transformation T, calculée à la première étape, pour laquelle le nombre de vraies correspondances obtenues à la seconde étape est maximum, est sélectionnée.

Concernant le choix des sous ensembles nécessaires au calcul de la transformation T (première étape), les méthodes connues d'estimation par échantillonnage consensuel procèdent, par exemple, par des tirages aléatoires successifs.

Ces méthodes d'estimation par échantillonnage consensuel sont aussi appelées RANSAC ( RANdom SAmple Consensus ). Pour de plus amples informations concernant ces méthodes, le lecteur est renvoyé notamment à la référence suivante: l'article intitulé Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography , de M. A. Fishler et R. C. Bolles, Communication ACM, Vol 24, No 6, pp 381-395, 1981.

Ce choix aléatoire est souvent utilisé en raison du fait qu'il est 25 souvent complexe de considérer toutes les combinaisons de choix possibles si le nombre N, d'éléments de la liste L de départ est important.

En effet, pour le cas du calcul d'une similitude plane pour laquelle, par exemple deux éléments de la liste sont nécessaires, il existe NC(Nc -1) 2 choix possibles.

Néanmoins, l'étape E41 précédant cette estimation, permet de minimiser la valeur de Ne. Ce nombre d'éléments est d'ailleurs rendu plus 23 2875622 faible lorsqu'une contrainte supplémentaire de distance maximale sur la distance entre vecteurs v est appliquée.

L'ensemble des choix possibles étant donc limité, il est alors possible de tous les considérer et donc la probabilité d'une bonne estimation de la transformation T est maximisée.

Dans le cas où l'on obtient plusieurs valeurs identiques du nombre maximal de vraies correspondances pour différentes estimations de la transformation T, on sélectionne, par exemple, la transformation T qui minimise la grandeur constituée par la somme des carrés des distances Ip. T(pic des éléments en vraie correspondance.

L'étape E42 d'estimation robuste d'une correspondance géométrique T globale est suivie de l'étape E43 de sélection d'une région.

En effet, l'étape E43 consiste, à partir de la liste L et de la transformation robuste T estimée à l'étape précédente, à définir une zone spatiale R des images où chacune des images semble se correspondre.

II est possible, en effet, que les images ne se correspondent qu'en partie. On peut en particulier considérer les deux scenarii possibles illustrés à la figure 6.

Le premier scénario (A) représente un cas où l'image publiée est une version recadrée de l'image propriétaire. Dans ce cas, l'ensemble du contenu de l'image publiée est contenu dans le contenu de l'image propriétaire.

Le second scénario (B) représente un cas où l'image publiée est une photocomposition dont une partie du contenu contient une partie du contenu de l'image propriétaire.

Ainsi, une définition de la zone R va être établie afin de mesurer la cohérence des correspondances entre les deux images, où il y a une vraie correspondance. Cette cohérence tient compte des deux scenarii possibles.

La zone R est, par exemple, définie comme une zone rectangulaire sélectionnée dans l'image propriétaire.

En effet, une définition rectangulaire de la zone R correspond au mode de sélection couramment utilisé dans les éditeurs d'images.

Ce choix n'est cependant pas limitatif et la zone R de correspondance sélectionnée peut être de forme non rectangulaire.

24 2875622 De plus, la zone R à considérer doit être la zone ayant le plus de chances d'être effectivement une zone de correspondance. Pour ce faire, les résultats de l'estimation robuste sont utilisés. La zone R est définie comme la zone dont le périmètre est défini par les unités d'intérêt en vraie correspondance, c'est-à-dire mises en correspondance lors de l'étape de mise en correspondance géométrique. Cette définition de la zone est illustrée à la figure 7.

L'étape de décision sera alors effectuée à partir de cette zone sélectionnée qui peut être une zone réduite de l'image. Ceci permet, en effet, de prendre en compte que les images peuvent se correspondre qu'en partie.

L'étape E43 est suivie de l'étape E44 qui consiste à déterminer le résultat des étapes de mise en correspondance, résultat restreint à la zone de correspondance sélectionnée. Ce résultat, en sus de la zone R et de la transformation T, sera ensuite utilisé pour le calcul du critère de décision.

On considère en particulier les trois composantes suivantes du résultat: la première composante du résultat considérée est le nombre nq d'unités d'intérêt pq de l'image publiée IP qui se projettent dans la zone R de l'image propriétaire, c'est-à-dire vérifiant T _ pje R - la seconde composante du résultat considérée est le nombre nd'unités, parmi les nq unités d'intérêt précédentes, dont les informations de contenu local v de la description locale sont en correspondance avec des unités d'intérêt de l'image propriétaire; ainsi, on identifie le nombre d'unités d'intérêt appartenant à la liste L élaborée lors de la mise en correspondance des informations de contenu local, qui appartiennent à la zone R définie; enfin, la troisième composante du résultat considérée est le nombre ni des unités d'intérêt en vrai correspondance parmi les n, unités d'intérêt précédemment déterminées; ces unités d'intérêt sont déterminées en fonction de la transformation robuste estimée à l'étape E42, c'est-à-dire en 30 fonction de leur mise en correspondance géométrique.

Un exemple de résultat d'observations est illustré à la figure 7.

2875622 En effet, selon la figure 7, la zone R sélectionnée dans l'image publiée comporte l'ensemble des unités d'intérêt résultant de la mise en correspondance géométrique.

La première composante de résultat, nq, comptabilisant le nombre d'unités d'intérêt présentes dans la zone R, a la valeur 7.

La seconde composante de résultat, ne, comptabilisant les informations de contenu local en correspondance avec des unités d'intérêt de l'image propriétaire, a la valeur 6. En effet, parmi les 7 unités d'intérêt de la zone, seules 6 unités d'intérêt ont été mises en correspondance lors de l'étape de mise en correspondance des informations de contenu local.

La troisième composante de résultat, n, , comptabilisant les unités d'intérêt mises en correspondance lors de l'étape de mise en correspondance géométrique, a la valeur 5. En effet, sur les 6 unités d'intérêt mises en correspondance à l'étape de mise en correspondance des informations de contenu local, seules 5 unités d'intérêt ont ensuite été mises en correspondance lors de l'étape de mise en correspondance géométrique.

De retour à la figure 4, l'étape E44 est suivie de l'étape E45 qui est une étape de calcul du critère de décision.

Par exemple, cette étape prévoit de déterminer le critère de 20 décision, selon un critère de décision Bayésienne entre deux hypothèses contraires.

La première hypothèse Ho est que l'image publiée correspond à l'image propriétaire.

La seconde hypothèse HI est que l'image publiée ne correspond 25 pas à l'image propriétaire.

La notion de correspondance inclut les scenarii de recadrage et de photocomposition pour des contenus d'images identiques ou qui représentent la même scène tel qu'illustré à la figure 6.

Mathématiquement, le critère de décision se définit de la façon 30 suivante: P(H, lobs) _ P(obs l H1) P(HI) P(Ho lobs) P(obs l Ho) X P(Ho 26 2875622 Il s'agit du rapport entre la probabilité de ne pas avoir une correspondance et la probabilité d'avoir une correspondance, ces deux probabilités conditionnelles étant fonction du résultat des étapes de mise en correspondance, notés obs, et qui sont issus du procédé selon l'invention comme décrit dans les étapes précédentes.

La décision consiste donc à estimer ce rapport, puis à comparer le rapport ainsi estimé à un seuil prédéterminé S. Si le rapport obtenu est inférieur au seuil S, avec S très inférieur à 1, alors il peut être considéré qu'il y a correspondance.

On peut exprimer la fiabilité de la décision par le rapport suivant: il y a b plus de chances de ne pas se tromper dans la décision.

Ce rapport de fiabilité sur la décision est une information qui peut être fournie en tant que spécification à l'utilisateur ou au client du système.

On estime le critère en utilisant l'expression de droite de la formule exposée ci-dessus: il s'agit de l'approche Bayésienne suivant laquelle on manipule les probabilités des observations conditionnellement aux hypothèses.

Ainsi, l'expression fait intervenir le rapport de deux probabilités a priori, noté P = P(H1)/P(Ho). Ce rapport mesure le rapport entre les chances a priori d'avoir l'une et l'autre des hypothèses.

Ce rapport peut varier en fonction du contexte et dépendre d'un a priori sur l'image publiée en question.

En particulier, la valeur du rapport est plus faible lorsque l'origine de l'image publiée, par exemple, le site Web d'une agence photo, est reliée à l'origine de l'image propriétaire qui est, par exemple, le photographe travaillant pour la dite agence photo.

Il est ainsi possible de rendre la décision adaptative en fonction du contexte en faisant varier la valeur de P. La comparaison du critère de décision avec le seuil s'écrit alors: P(obsJH,) S < P(obs Ho) P En pratique, on effectue les calculs en logarithme et, le critère de décision est comparé au seuil de la façon suivante: 27 2875622 P(obs H] Cl = Log10 P(obslH0) < Loglo S Log10 P Il s'agit de l'expression du critère tel que décrit précédemment à l'étape E34 de la figure 3. Les valeurs de ô et de P qui définissent la valeur du seuil Sci(P) peuvent être fixées a priori ou adaptées en fonction du contexte.

Par exemple, pour ô =10-4 et P =104 on obtient un seuil Sci(P)= -8.

L'étape E44 est suivie de l'étape E45 qui a pour fonction d'estimer la valeur de Cl telle que définie par l'expression précédente.

Etant donnés le résultat des étapes de mise en correspondance constitués par, outre la transformation T et la région R obtenues, les valeurs de 10 n4, ne et n. obtenues à l'étape E44, on calcule Cl de la façon suivante:Cl = C1, n + Cln nc Avec: ll Clnnq =ne xQ1 +(nq ne)xQ2 et Cln, = (ni 2) x Log10 P. H1 + (n, - ni) x Log10 1- PiH1 Pi Ho -PiHO/ avec A(s) PtH1 = A(R) et _ n A(s) PZHO = Q3 + Q4 X A(R) ou: - Q1, Q2 sont des constantes dépendantes des performances du détecteur de points d'intérêts utilisé, de la nature du vecteur de description locale et du seuillage sur la distance de Mahalanobis utilisés à l'étape E41. Par exemple, pour le détecteur de points d'intérêt décrit dans le document FR 03.01545, et pour le vecteur de description locale à 23 dimensions décrit dans le document intitulé Utilisation de la couleur pour l'appariement et l'indexation d'images Rapport de Recherche INRIA n 3269, septembre 1997, de P. Gros et al. et pour une valeur de seuil Dm égale à 50, alors on choisit les valeurs Q1 -0.253 et Q2 = 0.397.

28 2875622 - Q3, Q4 sont des constantes dépendantes des performances du détecteur de points d'intérêts utilisé. Pour le même détecteur que précédemment, on peut choisir les valeurs Q3 = 0.6 et Q4 = 0.4.

- A(s) est une constante en fonction de la valeur du seuils en distance utilisé pour la détermination des correspondances géométriques. La valeur de A(s) représente l'aire d'un disque de rayon s. Pour une valeur de s choisie égale à 1.5 pixel, A(s) est égal à une surface équivalente de 9 pixels.

- A(R) représente l'aire (dans la même unité que la valeur de A(s) i.e. en nombre de pixels) de la zone R de correspondance sélectionnée mesurée (projetée) dans l'image publiée.

Selon un autre mode de réalisation, on peut introduire des termes de pénalisation a priori, ClT et C1R, relatifs respectivement à la valeur de la transformation géométrique T estimée et à la région R obtenue dans l'expression de Cl. Le critère général s'écrit alors: Cl = C1 n + C1,,,, + Cl,. + C1R Une valeur non nulle de C17. , dépendante des caractéristiques de la transformation T estimé, permet de tenir compte du fait que les transformations géométriques ne sont pas a priori équiprobables selon les deux hypothèses. Ainsi, par exemple, selon l'hypothèse Ho, une rotation d'angle 8 nul est plus probable qu'une rotation de 90 degrés, elle-même plus probable qu'une rotation d'angle non multiple de 90 degrés. Les facteurs de mise à l'échelle s sont par ailleurs bornés a priori en fonction de la taille de l'image propriétaire d'origine.

Une valeur non nulle de C1R, fonction de la géométrie de la région R sélectionnée, permet de tenir que certains recadrage sont moins probables que d'autres. Notamment les régions R de formes très allongées sont moins probables sous l'hypothèse HO.

Comme montré à la figure 8, un dispositif de vérification d'entités multimédia adapté à une mise en oeuvre du procédé selon l'invention est de préférence construit autour d'un micro-ordinateur 80 auquel sont associés différents périphériques.

29 2875622 De manière classique, le micro-ordinateur 80 comporte une unité centrale (CPU) 800, une mémoire non volatile telle qu'une ROM 801, une mémoire vive RAM 802, des moyens d'interface homme-machine tels qu'un écran 803 et un clavier 804, des moyens de stockage d'information tels qu'un disque dur 805 et un lecteur 806, et différentes interfaces de périphérique 807. Le terme interface doit ici être interprété de manière étendue et est utilisé pour désigner différentes cartes et circuits d'adaptation tels qu'une carte graphique, une carte audio, une interface de communication et autres. Un bus de communication interne (non représenté) est compris également dans le micro-ordinateur 80 et constitue un moyen de communication, non exclusif, qui permet à l'unité centrale 800 de communiquer avec les différents éléments fonctionnels du dispositif selon l'invention.

Le micro-ordinateur 80 est de préférence relié à une caméra numérique 808, à travers une carte graphique (non représenté) faisant partie des interfaces 807. Selon une variante, il peut également être prévu un scanner (non représenté) ou tout autre moyen d'acquisition ou de stockage d'image fournissant des informations à traiter selon le procédé de l'invention.

Le dispositif selon l'invention est connecté à un réseau de communication 809, tel que le réseau Internet, qui est apte à transmettre des données numériques à traiter ou inversement à transmettre des données traitées par le dispositif.

Le lecteur 806 est prévu pour recevoir un disque 810. Le disque 810 peut par exemple être une disquette, un CD-ROM, ou un DVD-ROM. Le disque 810 peut contenir des données traitées selon l'invention, de même que le disque dur 805, ainsi qu'un programme mettant en oeuvre le procédé de vérification d'entités multimédia selon l'invention qui, une fois lu par le micro-ordinateur 80, est stocké dans le disque dur 805.

De manière plus générale, les moyens de stockage d'information peuvent comprendre un moyen lisible par un ordinateur ou par un 2875622 microprocesseur, intégré ou non au dispositif selon l'invention, éventuellement amovible, qui mémorise le programme mettant en oeuvre le procédé selon l'invention.

Selon une variante, le programme de mise en oeuvre du procédé 5 selon l'invention peut être stocké dans la mémoire morte 801.

Selon encore une autre variante, le programme peut être reçu par l'intermédiaire du réseau de communication 809 pour être stocké de manière analogue à celle décrite précédemment.

Claims (4)

1. 31 2875622 REVENDICATIONS

   1. Procédé de vérification de la correspondance entre une première entité multimédia et une seconde entité multimédia, chaque entité multimédia comprenant une pluralité d'unités d'intérêt, caractérisé en ce qu'il comporte les étapes suivantes: - mise en correspondance d'informations de contenu local de la première entité multimédia avec des informations de contenu local de la seconde entité multimédia, lesdites informations de contenu local étant associées à des unités d'intérêt, - mise en correspondance géométrique d'unités d'intérêt de la première entité multimédia avec des unités d'intérêt de la seconde entité multimédia, définition, dans l'une des entités multimédia, d'une zone comportant les unités d'intérêt résultant de l'étape de mise en correspondance géométrique, - estimation d'au moins un critère de fiabilité à partir du résultat des étapes de mise en correspondance d'informations de contenu local et de mise en correspondance géométrique sur la zone définie, comparaison dudit au moins un critère de fiabilité estimé à un seuil prédéterminé, - en fonction du résultat de la comparaison, décision sur la correspondance entre la première entité multimédia et la seconde entité multimédia.

   2. Procédé selon la revendication 1, caractérisé en ce que à chaque entité multimédia est associé au moins un descripteur déterminé préalablement à l'étape de mise en correspondance, ledit au moins un descripteur associé à au moins une unité d'intérêt de l'entité multimédia comprenant au moins une information de contenu local et au moins une information de position, , ledit au moins un descripteur étant utilisé lors des étapes de mise en correspondance d'informations de contenu local et de mise en correspondance géométrique.

   3. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que l'étape de mise en correspondance 32 2875622 d'informations de contenu local de la première entité multimédia avec des informations de contenu local de la seconde entité multimédia, comporte les sous étapes suivantes: - pour chaque information de contenu local de la première entité multimédia, sélection, parmi les informations de contenu local de la seconde entité multimédia, des informations sensiblement proches de l'information de contenu local concernée, définissant ainsi un premier ensemble de correspondances dont chacune forme un couple entre l'information de contenu local concernée de la première entité et l'une des informations sensiblement proches de la seconde entité, - pour chaque information de contenu local de la seconde entité multimédia, sélection parmi les informations de contenu local de la première entité multimédia, des informations sensiblement proches de l'information de contenu local concernée, définissant ainsi un second ensemble de correspondances dont chacune forme un couple entre l'information de contenu local concernée de la seconde entité et l'une des informations sensiblement proches de la première entité, - détermination de l'intersection du premier et du second ensemble de correspondances.

   4. Procédé selon la revendication 3, caractérisé en ce que la sélection d'un ensemble de correspondances pour une information de contenu local concernée d'une entité multimédia comporte les étapes suivantes: - calcul des distances entre ladite information de contenu local concernée et chacune des informations de contenu local de l'autre entité multimédia, détermination des distances inférieures à un seuil prédéterminé, définissant ainsi l'ensemble de correspondances concerné.

   5. Procédé selon la revendication 4, caractérisé en ce que le 30 calcul des distances fait intervenir une distance Euclidienne.

   6. Procédé selon la revendication 4, caractérisé en ce que le calcul des distances fait intervenir une distance de Mahalanobis.
2. 33 2875622 7. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que l'étape de mise en correspondance géométrique comporte les étapes suivantes: - détermination d'une éventuelle transformation géométrique nécessaire pour obtenir la première entité multimédia à partir de la seconde entité multimédia, détermination d'un ensemble d'unités d'intérêt de la première et de la seconde entité pour lesquelles la transformation géométrique permet de faire correspondre une unité d'intérêt de la première entité multimédia et une unité d'intérêt de la seconde entité multimédia.

   8. Procédé selon les revendications 2 et 7, caractérisé en ce que l'étape de détermination d'une éventuelle transformation géométrique comprend une estimation de la cohérence géométrique entre les informations de position associées aux informations de contenu local mises en correspondance.

   9. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que la zone correspond à l'une des entités multimédia.

   10. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que la zone comporte des unités d'intérêt n'ayant pas été mises en correspondance lors des étapes de mises en 25 correspondance.

   11. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le résultat des étapes de mise en correspondance d'informations de contenu local et de mise en correspondance géométrique sur les unités d'intérêt présentes dans la zone comprend: - le nombre d'unités d'intérêt présentes dans ladite zone, - le nombre d'unités d'intérêt résultant de l'étape de mise en correspondance d'informations de contenu local, et qui sont présentes dans la zone et 34 2875622 - le nombre d'unités d'intérêt résultant de l'étape de mise en correspondance géométrique et pour lesquelles la distance entre la position correspondant à une information de contenu local de la première entité multimédia et la position correspondant à une information de contenu local de la seconde entité multimédia est inférieure à un seuil prédéterminé.

   12. Procédé selon la revendication 11, caractérisé en ce que le résultat des étapes de mise en correspondance est en outre fonction de la surface de la zone.

   13. Procédé selon les revendications 7 et 11, caractérisé en ce que le résultat des étapes de mise en correspondance est en outre fonction de la transformation géométrique.

   14. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que la seconde entité multimédia fait partie d'un ensemble de secondes entités multimédia.

   15. Procédé selon la revendication 14, caractérisé en ce que préalablement à l'étape de mise en correspondance d'informations de contenu local, le procédé comprend une étape de sélection, parmi l'ensemble de secondes entités multimédia, d'une pluralité de secondes entités multimédia proches de ladite première entité multimédia, en effectuant une recherche sur le contenu des dites première et secondes entités multimédia de l'ensemble des secondes entités multimédia, les étapes de mise en correspondance, d'estimation, de comparaison et de décision étant appliquées sur ladite pluralité de secondes entités multimédia sélectionnées.

   16. Procédé selon les revendications 11 et 14, caractérisé en ce que l'estimation du critère de fiabilité est effectué à partir du rapport entre une probabilité que la première entité multimédia ne corresponde pas à l'une des secondes entités multimédia et une probabilité que la première entité multimédia corresponde à l'une des secondes entités multimédia, ces deux probabilités étant fonction du résultat des étapes de mise en correspondance.
3. 2875622 17. Dispositif de vérification de la correspondance entre une première entité multimédia et une seconde entité multimédia, chaque entité multimédia comprenant une pluralité d'unités d'intérêt, caractérisé en ce qu'il comporte: - des moyens de mise en correspondance d'informations de contenu local de la première entité multimédia avec des informations de contenu local de la seconde entité multimédia, lesdites informations de contenu local étant associées à des unités d'intérêt, - des moyens de mise en correspondance géométrique d'unités d'intérêt de la première entité multimédia avec des unités d'intérêt de la seconde entité multimédia, des moyens de définition, dans l'une des entités multimédia, d'une zone comportant les unités d'intérêt des mises en correspondance géométrique, des moyens d'estimation d'au moins un critère de fiabilité à partir du résultat de la mise en correspondance d'informations de contenu local et de la mise en correspondance géométrique sur la zone définie, - des moyens de comparaison dudit au moins un critère de fiabilité estimé à un seuil prédéterminé, - des moyens de décision sur la correspondance entre la première entité multimédia et la seconde entité multimédia, en fonction du résultat de la comparaison.

   18. Dispositif selon la revendication 17, caractérisé en ce que à chaque entité multimédia est associé au moins un descripteur déterminé préalablement à la mise en correspondance, ledit au moins un descripteur comprenant au moins une information de contenu local et au moins une information de position associées à au moins une unité d'intérêt de l'entité multimédia, ledit au moins un descripteur étant utilisé lors de la mise en correspondance d'informations de contenu local et de la mise en correspondance géométrique.

   19. Dispositif selon la revendication 17 ou 18, caractérisé en ce que les moyens de mise en correspondance d'informations de contenu local de 36 2875622 la première entité multimédia avec des informations de contenu local de la seconde entité multimédia, comportent: - des moyens de sélection pour chaque information de contenu local de la première entité multimédia, parmi les informations de contenu local de la seconde entité multimédia, des informations sensiblement proches de l'information de contenu local concernée, définissant ainsi un premier ensemble de correspondances dont chacune forme un couple entre l'information de contenu local concernée de la première entité et l'une des informations sensiblement proches de la seconde entité, - des moyens de sélection pour chaque information de contenu local de la seconde entité multimédia, parmi les informations de contenu local de la première entité multimédia, des informations sensiblement proches de l'information de contenu local concernée, définissant ainsi un second ensemble de correspondances dont chacune forme un couple entre l'information de contenu local concernée de la seconde entité et l'une des informations sensiblement proches de la première entité, - des moyens de détermination de l'intersection du premier et du second ensemble de correspondances.

   20. Dispositif selon la revendication 19, caractérisé en ce que les moyens de sélection d'un ensemble de correspondances pour une information de contenu local concernée d'une entité multimédia comportent: - des moyens de calcul des distances entre ladite information de contenu local concernée et chacune des informations de contenu local de l'autre entité 25 multimédia, - des moyens de détermination des distances inférieures à un seuil prédéterminé, définissant ainsi l'ensemble de correspondances concerné.

   21. Dispositif selon la revendication 20, caractérisé en ce que les 30 moyens de calcul des distances font intervenir une distance Euclidienne.

   22. Dispositif selon la revendication 20, caractérisé en ce que les moyens de calcul des distances font intervenir une distance Mahalanobis.
4. 37 2875622 23. Dispositif selon l'une quelconque des revendications 17 à 22, caractérisé en ce que les moyens de mise en correspondance géométrique comportent: - des moyens de détermination d'une éventuelle transformation géométrique nécessaire pour obtenir la première entité multimédia à partir de la seconde entité multimédia, - des moyens de détermination d'un ensemble d'unités d'intérêt de la première et de la seconde entité pour lesquelles la transformation géométrique permet de faire correspondre une unité d'intérêt de la première entité multimédia et une unité d'intérêt de la seconde entité multimédia.

   24. Dispositif selon les revendications 18 et 23, caractérisé en ce que les moyens de détermination d'une éventuelle transformation géométrique comprennent des moyens d'estimation de la cohérence géométrique entre les informations de position associées aux informations de contenu local mises en correspondance.

   25. Dispositif selon l'une quelconque des revendications 17 à 24, caractérisé en ce que la zone correspond à l'une des entités multimédia.

   26. Dispositif selon l'une quelconque des revendications 17 à 25, caractérisé en ce que la zone comporte des unités d'intérêt n'ayant pas été mises en correspondance lors des mises en correspondance.

   27. Dispositif selon l'une quelconque des revendications 17 à 26, caractérisé en ce que les moyens de mise en correspondance d'informations de contenu local et les moyens de mise en correspondance géométrique sur les unités d'intérêt présentes dans la zone sont aptes à générer le résultat suivant: - le nombre d'unités d'intérêt présentes dans ladite zone définie, - le nombre d'unités d'intérêt résultant de la mise en correspondance d'informations de contenu local, et qui sont présentes dans la zone définie et - le nombre d'unités d'intérêt résultant de la mise en correspondance géométrique et pour lesquelles la distance entre la position 38 2875622 correspondant à une information de contenu local de la première entité multimédia et la position correspondant à une information de contenu local de la seconde entité multimédia est inférieure à un seuil prédéterminé.

   28. Dispositif selon la revendication 27, caractérisé en ce que le résultat de mise en correspondance est en outre fonction de la surface de la zone.

   29. Dispositif selon la revendication 23 et la revendication 27 ou 10 28, caractérisé en ce que le résultat de mise en correspondance est en outre fonction de la transformation géométrique.

   30. Dispositif selon l'une quelconque des revendications 17 à 29, caractérisé en ce que la seconde entité multimédia fait partie d'un ensemble de secondes entités multimédia.

   31. Dispositif selon la revendication 30, caractérisé en ce que le dispositif comprend des moyens de sélection parmi l'ensemble de secondes entités multimédia, d'une pluralité de secondes entités multimédia proches de ladite première entité multimédia, à partir d'une recherche sur le contenu des dites première et secondes entités multimédia de l'ensemble des secondes entités multimédia, les moyens de mise en correspondance, d'estimation, de comparaison et de décision étant appliquées sur ladite pluralité de secondes entités multimédia sélectionnées.

   32. Dispositif selon les revendications 27 et 30, caractérisé en ce que les moyens d'estimation du critère de fiabilité sont adaptés à utiliser le rapport entre une probabilité que la première entité multimédia ne corresponde pas à l'une des secondes entités multimédia et la probabilité que la première entité multimédia corresponde à l'une des secondes entités multimédia, ces deux probabilités étant fonction du résultat de mise en correspondance.

   33. Dispositif de traitement d'information apte à fonctionner en tant que dispositif de vérification de la correspondance entre une première entité 2875622 39 multimédia et une seconde entité multimédia, caractérisé en ce qu'il comprend des moyens adaptés à la mise en oeuvre du procédé de vérification selon l'une quelconque des revendications 1 à 16.

   34. Système de télécommunications comprenant une pluralité de dispositifs terminaux reliés à travers un réseau de télécommunications, caractérisé en ce qu'il comprend au moins un dispositif terminal équipé d'un dispositif de vérification de la correspondance entre une première entité multimédia et une seconde entité multimédia selon l'une quelconque des

   revendications 17 à 32.

   35. Dispositif de stockage d'entités multimédia, caractérisé en ce qu'il comprend au moins un dispositif de vérification selon l'une quelconque des revendications 17 à 32.

   36. Support d'informations lisible par un système informatique, éventuellement totalement ou partiellement amovible, notamment CD-ROM ou support magnétique, tel un disque dur ou une disquette, ou support transmissible tel un signal électrique ou optique, ce support d'informations comprenant des instructions d'un programme d'ordinateur permettant la mise en oeuvre du procédé de vérification selon l'une quelconque des revendications 1 à 16, lorsque ce programme est chargé et exécuté par un système informatique.

   37. Programme d'ordinateur stocké sur un support d'informations, ledit programme contenant des instructions permettant la mise en oeuvre du procédé de vérification selon l'une quelconque des revendications 1 à 16, lorsque ce programme est chargé et exécuté par un système informatique.