Brevet FR2831304A1 — publié le 20030425

caractère pour lequel la comparaison présente une erreur minimum. D=ECION D I UN OTIF DANS UNE IGE NUI! ÉRIQUE La présente demande concerne de facon générale le trai tement d' image numérique. Plus particulièrement, la présente demande concerne la détection, dans une image numérique, dun motif prédéterminé quelconque. Un procédé connu d'une telle détection est décrit ci après en relation avec les figures 1A et 1B. La figure 1A illustre schématiquement un motif 1 dont on souhaite déterminer la présence éventuelle dans une image numérique. La figure 1B illustre une image numérique 2 dans laquelle on recherche le motif 1 de la figure 1A. On suppose, dans cet exemple, que limage 2 comporte bien le motif 1 et que l' image 2 a des dimensions plus importantes que celles du motif 1. Pour détecter la présence du motif 1 dans l' image 2, on utilise une image ou fenêtre de référence 3 contenant uniquement le motif 1. La détection est effectuce en balayant l' image 2 avec une fenêtre courante 4 de mêmes dimensions que la fenêtre de référence 3 et en comparant les contenus des deux fenêtres 3 et 4. Une telle comparaison consiste à évaluer le degré de corréla tion entre la fenêtre de référence 3 et la fenêtre courante 4. Pour ce faire, on utilise le plus souvent la distance euclidienne pixel par pixel que l'on cumule sur les fenêtres courante et de référence. Plus particulièrement, on calcule pour chaque pixel de la fenêtre courante le carré dune distance EDi j définie par la relation suivante: ED2i j =(Pi jRi j)2, o Pi j est la valeur de niveau de gris du pixel courant de la fenêtre courante 4, et o Ri j est la valeur de niveau de gris du pixcl de la fenêtre de référence de mêmes coordonnces i,j dans la fenêtre de référence 3. Puis, on somme les carrés des distances EDi j sur les dimensions verticale M (i étant ccmpris entre 1 et M) et horizon- tale N (j étant compris entre 1 et N) de la fenêtre courante, pour en daduire la distance euclidienne ED d'une fenêtre par rapport à l'autre. Cela revient à appliquer la formule: I M N ED= | ED2i j ii=lj=1 Pour permettre la localisation de mêmes motifs de différentes tailles, la somme ED peut être normalisée. On utilise alors, par exemple, l'énergie des fenêtres courante et de réfé rence. Par énergie dune fenêtre courante ou de référence, on entend la somme des carrés des niveaux de gris de tous les pixels de la fenêtre considérée. Pour localiser le motif 1, on calcule la distance enclidienne ED pour toutes les positions possibles de la fenêtre courante dans l' image. Le motif 1 se trouve alors à l' emplacement correspondant à la distance ED minimale. Un inconvénient de ce procédé réside dans le grand nombre de calculs à effectuer. En effet, en supposant que A est le nombre de lignes de l' image 2, et B le nombre de colonnes de 1iimage 2, et en supposant que M est le nombre de lignes de la fenêtre de référence 3 et N son nombre de colonnes, le nombre total de calculs est égal au nombre total de pixels de l' image de référence 3, c'est-à-dire le produit MN, par le nombre de posi tions spatiales possibles pour la fenêtre courante 4, soit M*N* (A-M) * (B-N). Un autre inconvénient de ce procédé réaide dans sa grande sensibilité aux conditions de luminosité lors de l'acqui- sition de l' image traitée ou de la fenêtre de référence. En effet, comme cela a été exposé précédemment, la recherche de corrélation est basée sur une différence de niveaux de gris. Une variation dans les conditions d' acquisition d' image s à traiter peut modifier localement les résultats en provoquant de fausses détections ou de faux rejets. La présente invention vise à proposer un procédé de lo détection dun motif dans une image numérique qui soit plus simple (moins de calculs et moins de mémoire) à mettre en oeuvre que les procédés connus. La présente invention vise également à proposer un tel procédé qui soit moins sensible aux conditions de luminosité (luminance) de l' image traitée et du motif à détecter. Pour atteindre ces objets et d'autres, la présente invention prévoit un procédé de détection d'un motif dans une image numérique par comparaison successive du contenu de fenêtres courantes de l' image par rapport au contenu d'au moins une fenêtre de référence représentative du motif, la fenêtre de référence contenant des valeurs de variance ou d'écart type de sous-blocs de pixcls du motif et les fenêtres courantes contenant des valeurs de variance ou d'écart type de sous-blocs de pixels de l' image, les sous-blocs étant de même taille dans les fenêtres courantes et de référence. Selon un mode de réalisation de la présente invention, le procédé comprend les étapes suivantes: subdiviser l' image et le motif en sous- blocs de mémes dimensions; former une fenêtre de rétérence contenant les variances ou écarts types des niveaux de gris des pixels de chaque sous bloc du motif; et comparer successivement les valeurs de la fenêtre de référence à des valeurs dau moins une fenêtre courante, de même taille que la fenêtre de référence, et contenant les variances ou écarts types des niveaux de gris de pixels de sous-blocs de l' image. Selon un mode de réalisation de la présente invention, les valeurs contenues dans les fenêtres courantes sont calculées au fur et à mesure d'un balayage de l' image. Selon un mode de réalisation de la présente invention, les valeurs des fenêtres courantes sont toutes calculées avant d'effectuer les comparaisons. Selon un mode de réalisation de la présente invention, les étapes de subdivision, de formation et de comparaison sont effectuées pour plusieurs tailles de sous-blocs. La présente invention prévoit également un système de détection d'un motif dans une image numérique, comprenant des moyens pour la mise en _ uvre du procédé selon l'un quelconque des modes de réalisation de la présente invention. Ces objets, caractéristiques et avantages, ainsi que dautres de la présente invention seront exposés en détail dans la description suivante de modes de réalisation particuliers faite à titre non-limitatif en relation avec les figures jointes parmi lesquelles: les figures 1A et 1B illustrent schématiquement un procédé connu de détection dun motif dans une image numérique; les figures 2A et 2B illustrent schématiquement une étape d'un mode de réalisation d'un procédé de détection d'un motif dans une image numérique selon la présente invention; les figures 3A et 3B illustrent une étape ultérieure du mode de réalisation des figures 2A et 2B; et la figure 4 illustre une étape ultérieure du mode de réalisation des figures 3A et 3B. Par souci de clarté, les mêmes éléments sont désignés par les mêmes références aux différentes figures. Un mode de réalisation d'un procédé de détection d'un motif dans une image numérique selon la présente invention sera détaillé ci-après en relation avec les figures 2 à 4. s cherche d6LecLer un nctif non represents (par example, simi laire au mcLif de la figure 1A) content dans One matrice Carrie de six pixals de ct illusLre en tigure 2A. Ea tigure 2B illustre, sous la torme d'une atrice de pixels comportant quinze colonnes eL douze lignes, une image numrique 20 dans laquelle on cherche d6Lecter la prAsence du motit de la tigure 2A. Comme 1'illusLrenL les figures 2A et 2S, le procAd selon 1' _ en subdi isanL la matrice 10 et 11 image 20 en des sous-blocs de mmes dimensions. titre d'exemple non limitatit, on considAre ici que chaque sous-bloc est un carrd de trois pixels de cat6. Bien entendu, il peut subsister un prdblme de bonds si 1' image ne contient pas un nombre entier de sousblocs de mmes dimensions. On peut alors, par axemple et au choix, ne pas tenir compte de pixels de bond de part et d'autre de 11 image en recentrant les sous-blocs, traiter le reste comme un sous-bloc de taille plus taible, ou igocrer le bond. La matrice 10 de la tigure 2A est donc subdivise en quatre sous-blocs de neut pixals chacun. Pour les besoins de la description, on rAtArence ces quatre sous-blocs de gauche a droite et de haut en bas 11, 12, 13 et 14. On illustre la spara tion entre des sous-blocs voisins par des Lraits pleins. La sparation entre les pixals 1'intArieur de chaque sous-bloc est illustrde en traits pointillAs. De fagon similaire, 11 image 20 de la tigure 2B est subdivise en vingt sous-blocs de neut pixels chacun. n figures 3A et 3B, les vingt sousblocs scot reprdsents. outetois, seuls les cinq de la premiAre ligne et le dernier de la derniAre ligne scot rAtArencAs 201, 202, 203, 204, 205 et 220. Ensuite, on caleule pour chaque sous-bloc 11, 12, 13, 14 de la matrice 10, la variance ou 1'6cart type (racine carrde de la variance) des neut pixals quil coporte. Le choix entre variance et écart type dépend, par exemple, de la mémoire allouée au stockage. La variance repré sente de s données plus importantes mai s économi se le calcul dune racine carrée. Pour simplifier, on fera par la suite réfé rence à la variance, mais toute la description qui suit st applique également à l'écart type. La variance V est donnée par la relation: M.N V = N M (Pk-P), o k-1 Pk représente le niveau de gris du pixel k du sous-bloc contenant N*M pixels, et o P représente la moyenne du sous-bloc en termes de niveau de gris, soit: M.N P =-Pk N-Mk 1 On forme alors une image de référence 30, illustrée en figure 3A, constituée dautant de pixels que la matrice 10 comporte de sous-blocs. Dans l'exemple considéré, l' image de référence 30 comporte donc quatre pixcls 11', 12', 13', 14'. La valeur de chaque pixel de limage de référence 30 est la variance précédemment calculée du sous-bloc correspondant de la matrice 10. Selon un premier mode de réalisation de la présente invention, on forme de façon similaire une image réduite 40, illustrce en figure 3B, constituée d'autant de pixels, ici vingt, que de sous-blocs dans limage numérique à traiter 20. Chacun des vingt pixels 201', 202', 203', 204', 205', 220t de 1timage réduite 40 a pour valeur la variance du sous-bloc correspondant de ltimage numérique initiale 20. Comme 1'illustre la figure 4, la détection du motif dans l' image numérique 20 consiste alors à balayer l' image réduite 40 avec une fenêtre courante 31 de mêmes dimensions que l' image de référence 30 et à comparer les valeurs de pixel de la fenêtre courante 31 à celles de la fenêtre de référence 30. Cette comparaison est effectuce en calculant la distance euclidienne. Les valeurs comparées sont toutefois des valeurs de variance. En pratique, mais cela ne change rien au principe de l' invention, on tient préférentiellement compte de l'énergie des fenêtres courante et de référence dans les valeurs de variance. Selon un deuxième mode de réalisat ion, on subdivi se en sous-blocs de mémes dimensions seulement la matrice 10 comportant le motif à rechercher. La matrice 10 est donc seule convertie de façon à former une image de référence 30. On balaye alors l' image numérique à traiter 20 avec une fenêtre ayant la dimension de la matrice 10. Cette fenêtre de balayage est subdivisée en un méme nombre de sous-blocs que l' image de référence 30 compte de pixcls (c'est-à-dire de sous-blocs de la matrice 10), soit dans l'exemple précédent 4. On calcule, pour chaque fenêtre de balayage successive de l' image 20, les variances associées à chacun des sousblocs la composant et on compare les résultats au contenu de l' image de référence 30. La différence par rapport au premier mode de réalisation est que les calculs de variances sont effectués au fur et à mesure du balayage de l' image 20. Le cas échéant, les valeurs sont toutefois mémorisces temporairement pour être réutilisées pour la ou les lignes suivantes. Un avantage de la présente invention est de réduire la complexité, c'està-dire le nombre de calculs primaires ou nombre de boucles par cycle à effectuer pour pouvoir discriminer le motif dans l' image numérique. Ainsi, par rapport au procédé connu décrit précédemment, en considérant des sous-blocs à neuf pixels comme dans 1'exemple décrit précédemment, le nombre de calculs est réduit de Px9 soit 81 fois. Un autre avantage de la présente invention est qu'en utilisant la variance on devient résistant au niveau de lumi nosité. En effet, si la luminosité varie de façon uniforme d'une image à l'autre, cette variation est sans effet sur la variance. Ceci ne serait pas le cas si, au lieu de la variance, on utili- sait les distances euclidiennes des valeurs des pixcls. En effet, si on compare un sous-bloc donné dont huit des neuf valeurs de pixcls sont égales à 100 alors que la neuvième valeur est égale à , à un sous-bloc dans lequel huit valeurs de pixels sont égales à 120 et une valeur à 140, une comparaison en distances euclidienne fera apparaître une différence de 60 sur la fenêtre, alors qu'une comparaison en termes de variance démontrera une identité entre les deux fenêtres. Le choix entre les deux modes de réalisation dépend de l 'application et notamment si on souhaite privilagier une réduc- tion du nombre de calculs ou de la mémoire requise. Le deuxième mode de réalisation présente l'avantage de nécessiter moins de mémoire. De plus, il permet une interruption de la recherche, donc des calculs, dès que le motif est trouvé. Le facteur de réduction maximal que l'on peut mettre en oeuvre est lié à l'échelle inférieure admissible appliquée au motif recherché. Cette échelle inférieure définit le nombre maximal de calculs. On notera toutefois qu'il faudra touj ours au moins deux pixels pour pouvoir effectuer un calcul de variance. Par conséquent, les sous-blocs présenteront une dimension mini- male contenant au moins deux pixcls. Une simple réduction par de tels sous-blocs à deux pixals présente toutefois déjà une réduc tion dun facteur quatre du nombre de calculs. Par rapport aux méthodes classiques qui exploitent les différences entre les niveaux de gris pixels à pixcls, ltinven tion exploite la texture du motif et un gradient non-directif des niveaux de gris. I1 conviendra de ne pas utiliser de sous-blocs trop grands. En effet, audelà dune certaine dimension, qui peut dépendre du motif et de l' image considérée, bien que le temps de calcul soit considérablement réduit, la variance sera calculée à l'intérieur de chaque sous-bloc sur un trop grand nombre de points présentant des écarts importants et on perdra de la préci sion. La limite de réduction de l' image dépend, entre autres, des détails caractéristiques du motif. Le procédé de détection de l' invention peut être appliqué, par exemple, à la localisation exacte dun visage dans une image numérique dans laquelle ce visage a été prélocalisé grossièrement, par exemple, à partir d'une détection d'une couleur de peau. De préférence, un procédé selon l' invention est mis en oeuvre successivement pour plusieurs tailles du motif recherché. Le cas échéant, ces différentes tailles correspondent à différentes réductions et conduisent alors à des fenêtres courante et de référence différentes, limage (40) restant la même. De préférence, on effectue un contrôle en mettant en oeuvre un que l conque de s procédés connus de corrélat ion pour chaque lo taille du motif dorigine en appliquant ce procédé, niveau de gris à niveau de gris, aux emplacements précis o le procédé de détection de l' invention suggère la présence du motif recherché pour cette taille. Dans ce cas, on applique alors une normalisation des coefficients de corrélation respectifs par rapport à la taille de la fenêtre de référence contenant le motif. Bien entendu, la présente invention est susceptible de diverses variantes et modifications qui apparaîtront à l'homme de l'art. En particulier, la présente invention nest pas limitée aux exemples numériques exposés précédemment. La présente inven- tion s' applique à la recherche, dans tout ensemble de données numériques de toute dimension A*B, d'un motif d'une dimension N*M, M étant un nombre de pixals alignés selon une première direction, par exemple verticale, inférieur au nombre homologue A de l' ensemble et N étant un nombre de pixcls alignés selon une seconde direction, par exemple horizontale, inférieur au nombre homologue B de 1' ensemble traité. De plus, comme cela a été indiqué précédemment, les dimensions et nombres de pixels des sous-blocs peuvent être modifiés de toute façon approprice en fonction de l 'application. De même, le sens du balayage d'une image numérique par une image de référence 31 niest indiqué en figure 4 qu'à titre indicatif. Toutefois, les positions des valeurs dans les images réduites (courante ou de référence) doivent correspondre aux positions respecL1ves des sousblocs doot elles expriment la variance ou 1'6carL Lype. En outre, la mise en oeuvre du procAdA de Reinvention par des mcyens materiels et/ou logiciels est la porL6e de 1'bcmme du mealier parLir des indications foncLiconelles dcoD@es Ci -PASSES. REVENDICATIONS 1. Procédé de détection dun motif (10) dans une image numérique (20) par comparaison successive du contenu de fenêtres courantes (31) de l' image par rapport au contenu d'au moins une fenêtre de référence (30) représentative du motif, carac térisé en ce que la fenêtre de référence contient des valeurs de variance ou d'écart type de sous-blocs (11', 12', 13', 14') de pixcls du motif et les fenêtres courantes contiennent des valeurs de variance ou décart type de sous-blocs (201', 202i, 203i, 204', 205t, 220) de pixels de 1' image, les sous blocs étant de même taille dans les fenêtres courantes et de référence. 2. Procédé de détection selon la revendication 1, carac- térisé en ce qu'il comprend les étapes suivantes: subdiviser l' image (20) et le motif (10) en sous-blocs de mémes dimensions; former une fenêtre de référence (30) contenant les variances ou écarts types des niveaux de gris des pixcls de chaque sous-bloc du motif; et comparer successivement les valeurs de la fenêtre de référence à des valeurs dau moins une fenêtre courante (31), de même taille que la fenêtre de référence, et contenant les variances ou écarts types des niveaux de gris de pixels de sous- blocs de l' image. 3. Procédé selon la revendication 2, caractérisé en ce que les valeurs contenues dans les fenêtres courantes sont calculées au fur et à mesure dun balayage de limage (20). 4. Procédé selon la revendication 2, caractérisé en ce que les valeurs des fenêtres courantes (31) sont toutes calculées avant d'effectuer les comparaisons. 5. Procèdé selon l'une quelconque des revendications 2 à 4, caractérisé en ce que les étapes de subdivision, de formation et de comparaison sont effectuées pour plusieurs tailles de sous blocs. 6. Systems de detection d'un Motif dans une Image num6- rique, caractAris en ce gu'il comprend des moyens pour la mise en oeuvre du proceeds Melon dune quelconque des revendications 1