Brevet FR2845186A1 — publié le 20040402

L'invention concerne un procédé et dispositif de mesure de similarité entre images. Le domaine d'application est celui du calcul de la similarité entre 5 images. Cette similarité peut être utilisée dans le cadre de la recherche d'images par similarité. Elle peut également être utilisée pour estimer des groupes d'images proches selon le critère de similarité utilisé. Il s'agit par exemple de la construction de résumés vidéo. Celle-ci consiste en une recherche d'images similaires dans une base constituée d'images d'une 10 séquence vidéo. Le but est de réduire le nombre de ces images en ne conservant qu'un représentant pour un groupe d'images décrétées ressemblantes Il s'agit également de l'indexation consistant à sélectionner des images index à partir de leur similarité à d'autres images ou tout simplement de la recherche d'images spécifiques dans la séquence vidéo, à 15 partir d'images requête. De nombreuses études s'intéressent à la mesure de similarité entre images à partir d'attributs affectés aux images. Un certain nombre d'entre eux sont maintenant définis dans la norme MPEG-7. L'invention s'intéresse 20 en particulier aux attributs dits structurels. Par exemple, dans la dernière version de la norme, un attribut de type contour est défini. Il est extrait localement de blocs d'images à partir de filtres de Gabor. Les attributs connus de l'art antérieur ou proposés dans la norme MPEG-7 et les algorithmes de traitement de ces attributs pour la mesure de similarité, ne permettent cependant pas, pour certains types de séquences, de détecter des images similaires de façon satisfaisante, dans la mesure o ils ne prennent pas en compte, soit l'image dans sa globalité, soit les détails dans l'image. Dans une optique de regroupement d'images extraites d'une 30 vidéo, la mesure de similarité doit pouvoir traduire le fait que plusieurs images correspondent à une même scène, caractérisée par une unité de lieu. Une information caractérisant uniquement les détails de l'image ne suffit pas à remplir cette tâche. D'un autre coté une information caractérisant l'image uniquement dans sa globalité peut s'avérer inadaptée dans le cas de 35 modification partielle du décor de la scène, par exemple par modification du fond de la scène. L'invention a pour but de pallier les inconvénients précités. Elle a pour objet un procédé de mesure de similarité entre images, caractérisé en ce qu'il effectue, pour chaque image, les étapes suivantes: - segmentation de l'image - classification des segments en fonction de leur orientation pour donner des classes, - calcul d'un histogramme du nombre de segments en fonction de 10 la classe, - calcul d'un histogramme du nombre de pixels appartenant aux segments d'une même classe en fonction de la classe, comparaison des histogrammes de chaque image pour donner une mesure de similarité. Selon une mise en oeuvre particulière, le procédé est caractérisé en ce qu'il calcule également un histogramme correspondant à la distribution des segments autour du centre de gravité de chaque classe. Selon une réalisation particulière, pour calculer cet histogramme, il effectue un calcul de l'écart-type des distances des milieux des segments 20 d'une classe au centre de gravité de la classe considérée. Selon une mise en oeuvre particulière, la comparaison des histogrammes consiste en une soustraction des ordonnées, classe par classe et en une somme, sur l'ensemble des classes, des valeurs obtenues pour chaque classe. Selon une mise en oeuvre particulière, les histogrammes sont codés selon la norme MPEG-7. L'invention concerne également un procédé de regroupement (clustering) d'images d'une base de données, caractérisé en ce que le regroupement est effectué en fonction des mesures de similarité selon le 30 procédé décrit précédemment pour donner des groupes (clusters) d'images. L'invention concerne également un procédé de création de résumés vidéo, caractérisé en ce qu'il sélectionne au moins une des images d'au moins un groupe calculé selon le procédé précédent. L'invention concerne également un procédé d'indexation vidéo, 35 caractérisé en ce qu'il sélectionne au moins une des images d'au moins un groupe calculé selon le procédé précédent, comme image d'indexation. L'invention concerne également un dispositif de mesure de similarité entre images, caractérisé en ce qu'il comporte un circuit de traitement et de calcul d'histogrammes recevant des données numériques définissant ces images pour effectuer, pour chacune d'elle, les opérations suivantes: segmentation de l'image - classification des segments en fonction de leur orientation pour donner des classes, - calcul d'un histogramme du nombre de segments en fonction de 10 la classe, - calcul d'un histogramme du nombre de pixels appartenant aux segments d'une même classe en fonction de la classe, - comparaison des histogrammes de chaque image pour donner une mesure de similarité. L'invention a pour principal avantage de mettre en oeuvre des algorithmes performants pour caractériser une image et mesurer la similarité entre images à partir de ces algorithmes, grâce à l'utilisation conjointe d'attributs basés orientation de contours permettant de caractériser le 20 nombre de segments, leur taille ainsi que leur distribution en fonction de l'orientation. La description globale de l'image est obtenue à partir des histogrammes des orientations des segments dans l'image, donc sans tenir compte de la position de ces segments dans l'image, et la description locale 25 est obtenue à partir d'une mesure de centres de gravité de classes de segments, qui correspond aux positions relatives des différents segments d'une même classe. L'utilisation de tels attributs structurels permet de caractériser l'image à la fois de façon locale et de façon globale, améliorant ainsi l'efficacité dans 30 la recherche de similarité des images. En effet, les dimensions des objets similaires peuvent être très différentes d'une image à une autre, d'un plan de la séquence à un autre. D'autres particularités et avantages de l'invention apparaîtront 35 clairement dans la description suivante donnée à titre d'exemple non limitatif, et faite en regard des figures annexées qui représentent: - la figure 1, un organigramme du procédé selon l'invention, - la figure 2, un procédé d'approximation polygonale, - la figure 3, un exemple de recherche de similarité. Le procédé réalise une segmentation de l'image. L'approche " objet " n'existe cependant pas ici. Il s'agit de déterminer des segments dans l'image qui sont des approximations des contours réels dans l'image, par exemple à partir de mesures de gradients, sans se soucier du fait qu'ils appartiennent ou non à un objet particulier dans l'image. 10 La figure 1 représente un organigramme définissant les principales étapes du procédé de calcul d'histogrammes d'attributs caractérisant une image. Une première phase qui est un prétraitement de l'image consiste en 15 une détection de contours dans l'image pour obtenir une carte de contours et en une segmentation de ces contours pour obtenir une carte de segments. La deuxième phase réalise un calcul des attributs pour la détection de similarité. Une image à traiter est transmise à une première étape référencée 1 sur l'organigramme de la figure 1. Cette étape du procédé réalise un calcul de gradients dans l'image. Un filtre de détection de gradients est appliqué à l'image pour donner en chaque point une mesure de gradient. Une carte de gradients verticaux et une carte de gradients horizontaux sont ainsi 25 calculées. La norme des gradients obtenue à partir de ces cartes, racine carrée de la somme des carrés des valeurs de gradient horizontal et vertical attribuées à un pixel, est aussi exploitée. L'étape 2 réalise une sélection des pixels à partir des valeurs de gradient calculées à l'étape précédente, comparées à des seuils. Cette 30 sélection est affinée par celle des points de plus fort contraste dans une fenêtre de voisinage donnée. Le but est de supprimer des contours épais en sélectionnant, dans le voisinage d'un pixel, les pixels ayant les plus forts gradients, en considérant les valeurs des gradients horizontaux et verticaux. Il s'agit également de favoriser les pixels voisins d'un pixel déjà sélectionné 35 comme un contour. Les points contours isolés sont éliminés. Nous obtenons, à ce stade, une carte binaire de contours, chaque pixel de l'image est étiqueté comme contour ou non. Un test de connectivité est effectué sur la carte binaire de contours afin de rassembler les pixels voisins, pour ainsi constituer des lignes de 5 contours. Pour ce faire, un processus d'étiquetage en composantes connexes est mis en oeuvre à l'étape suivante 3. Deux pixels sont déclarés connexes s'il existe un chemin ininterrompu de pixels contours reliant ces deux pixels. On " chaîne " ainsi des pixels contours de manière à obtenir une ligne de continuité. Les pixels 10 connexes sont étiquetés, chaque pixel touchant un autre pixel étant marqué de la même étiquette. On obtient, pour chaque étiquette, une liste de composantes connexes, cette liste étant les coordonnées des différents pixels d'une ligne de continuité relative à une étiquette. Pour chaîner chaque contour d'une extrémité à l'autre, il est 15 nécessaire d'éliminer les points multiples, c'est à dire les jonctions de lignes de contours. Un algorithme teste la présence de jonctions et les élimine. Cette étape est réalisée en effectuant un suivi de contours sur chaque composante connexe identifiée. Le parcours des pixels appartenant à une composante connexe donnée se fait de proche en proche. Une combinaison 20 de filtres permet de savoir si le pixel courant correspond à une jonction entre le contour principal et un contour secondaire. Un pixel ayant été catégorisé comme jonction est éliminé de la carte des pixels contour, détachant ainsi le contour secondaire du contour principal. Le contour secondaire est replacé dans la liste des composantes connexes à parcourir. Le suivi de contours se 25 poursuit alors le long du contour principal. A ce stade, nous disposons d'une carte de lignes de continuité non rectilignes. L'étape suivante 4 du processus de prétraitement est une approximation polygonale de ces contours chaînés afin d'approcher chaque 30 ligne de contour par un ensemble de segments connectés. La figure 2 représente un procédé d'approximation polygonale d'un contour chaîné. Pour un contour donné référencé 11, on recherche le point e3 donnant la distance maximale entre les points du contour et le segment formé par les extrémités de ce contour el et e2. Si cette distance est 35 supérieure à un seuil, le contour est approché par deux segments [el,e3] et [e3,e2]. Le processus est réitéré jusqu'à ce que les distances du point au segment soient inférieures au seuil fixé. A l'issue de cette étape, on dispose, pour une image, d'une carte de segments constituée d'un ensemble de segments dont il est alors possible 5 de calculer l'orientation. Un exemple de carte de segments est représenté en haut à droite de la figure 3. La deuxième phase consiste en un calcul et une exploitation des attributs relatifs à cette carte de segment. L'étape 5 calcule, pour chaque segment de la carte de segments, l'angle entre sa direction et l'horizontale. L'angle obtenu, compris entre 0 et 180 degrés, est alors quantifié pour obtenir un nombre réduit de catégories ou classes d'angles. Par exemple, les angles obtenus sont répertoriés dans 36 classes, le pas de quantification étant de 5 degrés ou, en d'autres termes, 15 une classe correspond à une largeur de 5 degrés. Des histogrammes relatifs à trois attributs sont maintenant calculés lors de l'étape 6, exploitant l'information d'orientation de segment obtenue précédemment. - un histogramme du nombre de segments en fonction de 20 l'orientation. Les différentes classes sont représentées en abscisse et les occurrences en ordonnées. - un histogramme du nombre total de pixels appartenant à des segments de même orientation en fonction de l'orientation de ceux-ci. Les ordonnées correspondent à la somme des longueurs des segments de la classe, pour une classe donnée. - un histogramme correspondant à la distribution des segments autour du centre de gravité de chaque classe, par calcul de l'écart-type des distances des milieux des segments au centre de gravité. Le centre de gravité G, de la classe C, est obtenu par calcul du barycentre des milieux M(s) des segments s,. Le poids associé à chaque milieu est égal au nombre de pixel n(s) composant le segment: Zn(sj)* M(sj) G sj eci En(sj) Sj ECi Les ordonnées H(fi) correspondent à l'écarttype des distances euclidiennes d(GiM(sj)) entre le barycentre ou centre de gravité de la classe Ci considérée et le centre de chaque segment de la classe: card(Ci)* d(GiM(sj))2 -(d(iM(sj)))2 H(i) = |SjECi sj Ci 1H() = card(Ci) * card(Ci) o card est la fonction cardinale retournant le nombre de segments de la classe considérée. La distribution est mise sous forme d'histogramme, c'est à dire de vecteurs de valeurs, permettant ainsi son exploitation dans le cadre de la norme MPEG7 qui définit le codage de tels histogrammes. Afin de plus facilement combiner les informations, les histogrammes sont normalisés, par exemple à partir des valeurs maximales trouvées. Les trois histogrammes des attributs caractérisant l'image sont exploités pour les mesures de similarité, étape 7. Trois histogrammes sont calculés pour une première image qui est par exemple une image requête et trois autres histogrammes pour une deuxième image qui est une image dans une base de données. La mesure de similarité entre les deux images I, et I2, c'est à dire le calcul de la distance entre ces images peut alors s'effectuer par simple soustraction des 25 ordonnées, classe par classe, pour chaque type d'histogramme Hk de taille mk k HT k (i)-Hk (i) A {r.k kx i ukkll,rl2)= mk Un indicateur de similarité S(I1I2) est par exemple la somme des valeurs obtenues par ces soustractions, pour l'ensemble des histogrammes: jdk(HlkH k) S(Il 12) = k=1,2,3 La mesure de similarité peut être améliorée en comparant la classe également à des classes voisines de l'histogramme de l'autre image, avec un facteur de pondération. La comparaison d'histogrammes utilise par exemple une métrique de type cross quadratique permettant de s'affranchir des 10 faibles variations d'orientation globale entre deux images successives, par exemple lors d'une rotation faible de la caméra. Un exemple de recherche d'images similaires est donné à la figure 3, montrant, en haut à gauche, l'image considérée, sa carte de contours et de 15 segments associée, ainsi que les images reconnues comme les plus ressemblantes dans une base de 150 images issues de deux séquences différentes. La principale caractéristique de ces histogrammes est donc de 20 fournir une description à la fois globale et locale des images. Il est ainsi possible, grâce à la description globale, de différencier des images globalement structurées, par exemple des images de villes caractérisées pas des orientations de segments horizontaux et verticaux, d'images de campagnes caractérisées par des orientations de segments plus aléatoires. 25 Mais il est également possible, grâce à la description locale, de différencier des images localement structurées, une partie de l'image est par exemple consacrée à un bâtiment, une autre à un bois, d'images moins structurées, par exemple une maison au milieu de la forêt. Le calcul des segments, dans la description précédente, est effectué sur les valeurs de luminance de l'image. Il est bien sr tout aussi envisageable d'effectuer un tel calcul pour chacune des composantes couleur de l'image. Si les calculs demandent plus de capacité de traitement, en revanche la réalisation d'histogrammes par couleur permet d'améliorer l'efficacité du procédé. Trois histogrammes sont ici exploités pour caractériser l'image. Il est bien sr possible de n'exploiter que l'un d'entre eux ou une combinaison de 5 deux d'entre eux pour calculer la similarité d'images, sans sortir du domaine de l'invention. Les orientations des segments exploitées peuvent être les angles formés avec d'autres droites de référence que l'horizontale. Les dimensions 10 des classes peuvent être inférieures ou supérieures à 5 degrés, selon la puissance ou temps de calcul disponible ou la qualité de mesure souhaitée. REVENDICATIONS 1 Procédé de mesure de similarité entre images, caractérisé en ce qu'il effectue, pour chaque image, les étapes suivantes: - segmentation de l'image (1, 2, 3, 4), - classification des segments en fonction de leur orientation pour 10 donner des classes (5), - calcul d'un histogramme du nombre de segments en fonction de la classe (6), - calcul d'un histogramme du nombre de pixels appartenant aux segments d'une même classe en fonction de la classe (6), - comparaison des histogrammes de chaque image pour donner une mesure de similarité (7). 2 Procédé selon la revendication 1, caractérisé en ce qu'il calcule également un histogramme (6) correspondant à la distribution des segments 20 autour du centre de gravité de chaque classe. 3 Procédé selon la revendication 2, caractérisé en ce que, pour calculer l'histogramme, il effectue un calcul de l'écart-type des distances des milieux des segments d'une classe au centre de gravité de la classe 25 considérée. 4 Procédé selon la revendication 1, caractérisé en ce que la comparaison des histogrammes consiste en une soustraction des ordonnées, classe par classe et en une somme, sur l'ensemble des classes, 30 des valeurs obtenues pour chaque classe. Procédé selon la revendication 1, caractérisé en ce que les histogrammes sont codés selon la norme MPEG-7. 6 Procédé de regroupement (clustering) d'images d'une base de données, caractérisé en ce que le regroupement est effectué en fonction des mesures de similarité selon le procédé de la revendication 1 pour donner des groupes (clusters) d'images. 7 Procédé de création de résumés vidéo, caractérisé en ce qu'il 5 sélectionne au moins une des images d'au moins un groupe calculé selon le procédé de la revendication 6. 8 Procédé d'indexation vidéo, caractérisé en ce qu'il sélectionne au moins une des images d'au moins un groupe calculé selon le procédé de 10 la revendication 6, comme image d'indexation. 9 Dispositif de mesure de similarité entre images, caractérisé en ce qu'il comporte un circuit de traitement et de calcul d'histogrammes recevant des données numériques définissant ces images pour effectuer, 15 pour chacune d'elle, les opérations suivantes: - segmentation de l'image (1, 2, 3, 4), - classification des segments en fonction de leur orientation pour donner des classes (5), - calcul d'un histogramme du nombre de segments en fonction de 20 la classe (6), - calcul d'un histogramme du nombre de pixels appartenant aux segments d'une même classe en fonction de la classe (6), - comparaison des histogrammes de chaque image pour donner une mesure de similarité (7).