Brevet FR2667711A1 — publié le 19920410

Procédé de reconnaissance d'objets dans des images et son application au suivi d'objets dans des séquences d'images. L'invention se rapporte au domaine du traitement de l'image et a plus particulièrement pour objet un procédé, de reconnaissance de formes dans des images et son application au suivi d'objets dans des séquences d'images. Les procédés actuellement connus pour effectuer la recon- naissance d'objets dans les images utilisent des méthodes par corrélation binaire ou multiniveaux dans le domaine spatial ou dans un domaine transformé, ou des méthodes de comparaison utilisant des descripteurs de formes. La reconnaissance d'objets dans une image repose d'une manière générale, sur la recherche de motifs dans l'image les plus ressemblants à des modèles connus. Le modèle de reconnaissance d'un objet peut prendre différentes formes mais caractérise toujours une représentation précise des caractéristiques de l'objet à reconnaître Il peut s'agir d'une matrice de points, d'une collection d'éléments géométriques, d'un ensemble de contours ou bien encore d'une décomposition dans un domaine particulier (Transformée de Fourier, Transformée de Hadamard, ondelettes, etc) Ces méthodes sont pour la plupart très coûteuses en temps de calcul lorsque l'on souhaite que leur soient attachées une grande sûreté et une grande robustesse. L'invention a pour objet un procédé, et le dispositif correspondant de reconnaissance de formes dans lequel la fiabilité et la robustesse des résultats sont obtenues sans que le coût en temps de calcul soit trop grand Pour cela le procédé utilise, pour cette reconnaissance, une décomposition en valeurs singulières de l'image ou "S V D", pour "l Singular Value Decomposition" selon la terminologie anglo-saxonne. La décomposition en valeurs singulières d'un objet représenté par une matrice de points caractérise cet objet par sa "signature sur un espace de projection défini par deux projecteurs Cette signature constituée des valeurs singulières de la matrice objet définit le modèle de reconnaissance Un objet est alors défini par trois matrices notées U, V et S: La matrice S est une matrice diagonale ordonnée L'ensemble des valeurs de la diagonale correspond à la signature de l'objet. Les matrices U et V sont les matrices de projection. Un objet est "reconnu" si sa signature après projection est proche de la signature recherchée En effet il existe une relation quasi univoque entre la signature et la zone à laquelle elle correspond. Suivant l'invention, la reconnaissance est effectuée suivant un procédé itératif sur les valeurs propres: La première étape du procédé consiste à effectuer un premier tri de toutes les zones possibles en n'utilisant qu'une première valeur propre. A la iême étape, un tri sera effectué parmi les zones sélectionnées à l'étape précédente sur un nombre plus grand de valeurs propres. Le procédé consiste donc à effectuer un tri grossier sur un grand nombre de zones dans un premier temps, puis un tri de plus en plus fin sur un nombre de plus en plus restreint de zones Les calculs effectués à chaque étape sont réutilisés à l'étape suivante. Un premier objet de l'invention est un procédé de reconnaissance d'objets dans des images comportant une phase d'apprentissage au cours de laquelle la zone objet à reconnaître sélectionnée dans une image d'apprentissage est modélisée, et une phase de reconnaissance au cours de laquelle la zone modélisée est comparée à des zones image de même taille prises dans les images à traiter, caractérisé en ce qu'il utilise, pour la caractérisation des zones d'images modèles d'objets à reconnaître ou des zones d'images à traiter, une décomposition des matrices des valeurs de luminance en valeurs singulières selon un produit matriciel de matrices de projection et d'une matrice diagonale ordonnée, cette dernière constituant une signature caractéristique de la zone considérée, et en ce que pour la phase de reconnaissance, des écarts entre la signature de la zone modèle et les signatures de zones de l'image considérée sont calculés et des zones d'image sont sélectionnées à partir des moindres écarts selon un procédé itératif tel que dans une première étape seul le premier coefficient des matrices signature ordonnées est considéré pour le calcul des écarts mais pour toutes les zones d'image possibles, puis dans une seconde étape les P 2 premiers coefficients des matrices signature, p 2 supérieur à 1, sont considérés pour un ensemble réduit de N zones d'image sélectionnées à l'étape précédente comme présentant les moindres écarts, dans une ième étape, un nombre P, supérieur à P 1 ' de coefficients des matrices est considéré pour un ensemble réduit de ni zones d'image sélectionnées à l'étape (i-1) car présentant les écarts les plus faibles, i variant de 3 à k-1, dans une kième et dernière étape, tous les coefficients des matrices signatures de zones d'image sélectionnées à l'avant dernière étape sont considérées pour sélectionner la zone d'image présentant l'écart de signature le plus faible avec la zone modèle. Un deuxième objet de l'invention est l'application du procédé au suivi d'objets dans des séquences d'images. L'invention sera mieux comprise et d'autres caractéristi- ques apparaîtront à l'aide de la description qui suit, en réfé- rence aux figures annexées: Les figures 1 et 2 illustrent respectivement une image dans laquelle est sélectionnée une zone comportant un objet à reconnaître, et une seconde image dans laquelle cet objet doit être retrouvé; La figure 3 est un schéma explicatif; La figure 4 illustre le procédé de reconnaissance sui- vant l'invention. La transformation en valeurs singulières (S V D) présente un intérêt en traitement de l'image pour des applications de compression, de filtrage et de reconnaissance de formes. Comme indiqué succinctement ci-dessus la transformation par décomposition en valeurs singulières consiste à décomposer une image (ou partie d'image) dont les valeurs de luminance des points forment une matrice A de taille (m, n) rectangulaire ou carrée, en produit matriciel défini par: lAl = lUl lSl lVlt, o IV It est la matrice transposée de I V, et o la matrice S est une matrice diagonale ordonnée telle que lSl = diag(s 1,s 2,s 3,s 4, sp) avec p=min(m,n). Ces éléments diagonaux S 1 sp sont les valeurs singulières de la matrice A et sont des réels positifs (racines carrées positives des valeurs propres) classés par ordre décroissant s 1 > S 2 > S 3 > > S Les matrices lUl et lVl de tailles respectives (m, p) et (p, n) regroupent dans leurs colonnes les vecteurs singuliers gauches (U) et droites (V) de A Les colonnes ui de lUl sont les vecteurs propres de lAl lAlt alors que les colonnes vi de t lVI sont les vecteurs propres de lAlt lAl. lUl = lu 1, u 2 u p; u est un vecteur colonne de taille m p i lVl = lv 1, v 2 vnl; vi est un vecteur colonne de taille p. Ces matrices ont les particularités suivantes lUltlUl = lVl lVlt = I p o I est la matrice identité de dimension (p,p). P La matrice diagonale lSl est telle que:. lSl = diag (s,, S 2 ' S 3, st, p) avec S 1 > S 2 sr > O; S r+ 1 = O r S r+ 1 " P o r est le rang de la matrice A Les vecteurs propres et les valeurs singulières sont définis par les relations suivantes A v = s u. i 1 il At u = s v. 1 1 1 La transformation par décomposition en valeurs singulières peut donc être représentée sous la forme suivante A = '= (si ui vi t) Plusieurs méthodes ont été développées pour déterminer les matrices lUl, lVl, lSl. La décomposition en valeurs singulières est calculée en appliquant l'algorithme de GOLUB/REINSCH relatif à la méthode de GOLUB/KAHAN classique dans les traitements de matrice. Cette méthode consiste dans un premier temps à transfor- mer la matrice lAl en matrice bidiagonale par la méthode HOU- SEHOLDER, puis à partir de cette forme bidiagonale à calculer les valeurs singulières Cette méthode est efficace, rapide et convergente Cependant, elle est difficilement adaptable au calcul multiprocesseurs. Un autre type de méthode dite"the SVD power algorithm" est couramment développé Cette méthode utilise un procédé itératif: su = lAl v et sv= lAlt u si k est le rang d'itération précédent u(k+ l)=lAlv(k)/I I lAlv(k) I I v(k+l)=lAlU(k+l)+l)/l lAltu(k+l) 1 1 Le procédé itératif se poursuit jusqu'au moment o i Iu(k+l) u(k) 1 1 est inférieur à une valeur fixée La première valeur singulière vaut alors s 1 = I lAlt u(k+ 1) l. Les vecteurs u 1 et v sont donnés respectivement par les vecteurs uk+l et vk+ issus respectivement de la dernière itération. Pour obtenir le couple de vecteurs suivant (u 2, v 2), le procédé est réitéré en considérant non plus la matrice A mais la matrice A' définie par: lAl' = lAl S 1 u 1 vit Ce type d'algorithme peut présenter des problèmes de convergence et de stabilité Il est cependant bien adapté à des applications n'utilisant que les premières valeurs singulières. Enfin, une autre catégorie d'algorithme est basée sur la méthode de HESTENES/NASH dite: "One side transformation" qui permet de rechercher les valeurs singulières d'une matrice en appliquant des séquences de rotations planes sur les colonnes ou les lignes Cette méthode ne permet qu'une décomposition complète de l'image et est particulièrement adaptée aux matrices de faible taille. Le temps de calcul nécessaire pour effectuer cette décomposition, quelle que soit la méthode adoptée, ne représente qu'une infime partie du temps calcul qui sera utilisé pour la reconnaissance du motif dans une image De plus, l'apprentissage n'est pas soumis aux contraintes de durée imposées lors de la reconnaissance. Le choix de la méthode de décomposition n'est donc pas critique et l'une ou l'autre des méthodes décrites ci-dessus peut être utilisée, l'optimisation étant surtout indispensable au niveau du procédé de reconnaissance proprement dit. L'algorithme de calcul des différentes matrices dépend du type de calculateur qui sera utilisé pour calculer la décomposition en valeurs singulières (parallèle, série) et n'est pas décrit en détails dans la présente description car à la portée de l'homme du métier. En utilisant une telle décomposition, l'énergie de l'image est concentrée sur les premiers coefficients (sl S 2) Les derniers coefficients ( S p ' S p) correspondent aux détails et au bruit contenus dans l'image. Cette propriété est utilisée pour des applications à la reconnaissance de formes dans l'image La reconnaissance est obtenue en considérant l'ensemble l S l comme étant la signature du modèle à reconnaître La reconnaissance de formes est alors obtenue en deux phases: La première phase consiste à effectuer un apprentissage sur le modèle à reconnaître défini par une matrice rectangulaire (ou carrée) des valeurs de luminance entourant au mieux l'objet à caractériser L'apprentissage consiste à calculer les trois matrices lUl, lVI, lSl définissant ce modèle de manière unique et complète. La deuxième phase consiste à rechercher dans une image à traiter la partie d'image correspondant au mieux au modèle. Cette phase de recherche est menée en cherchant à reconnaître l'objet A dans l'image M par l'intermédiaire de sa signature lSl Pour cela, les signatures lS Icl de chacune des zones d'image Mîc qui composent l'image M sont calculées pour ensuite être comparées à la signature S de l'objet à reconnaître. Une zone image Mlc telle qu'illustrée par la figure 3 est une matrice A' de taille (m, n) égale à celle de la matrice objet A, extraite de l'image à la position ( 1, c) La signature correspondante l 5 lc l est calculée de la même manière que celle de la matrice A. La comparaison entre les deux signatures lS I et lSlcl qui doit permettre d'apprécier la ressemblance s'effectue en calculant l'écart, ou la "distance", qui sépare les deux matrices lSl et lSlc 1 Cet écart est égal à e=IS-S 2 = S 2 i làp aveci Slci = diag(s'1 '2 Z* S * s) 2 ''p Cet écart e mesure la "similitude" de signatures du modèle et de la zone image examinée. La recherche du motif dans l'image pourrait théoriquement être effectuée en considérant toutes les zones de taille m x n de l'image par glissement et en calculant pour chacune de ces zones une signature et l'écart entre cette signature et la signature de l'objet La position du motif est alors la position de la zone image à partir de laquelle a été calculé le plus faible écart e. Cette recherche effectuée sur l'image entière en prenant en compte toutes les valeurs propres est une opération peu réa- liste du fait du nombre de calculs à mettre en oeuvre, et cette solution ne permettrait pas de résoudre le problème qui est l'optimisation temps de calcul/sûreté et robustesse du procédé. Il est donc prévu dans le procédé selon l'invention de limiter le nombre de calculs Une première possibilité serait de limiter le nombre de valeurs propres Ceci est une opération délicate car le nombre de valeurs propres à conserver dépend des caractéristiques des objets à trier: si deux objets sont proches, il est nécessaire de considérer un grand nombre de valeurs propres pour les différencier, alors que si ils sont très différents, un nombre limité de valeurs propres suffit. Pour limiter le nombre de calculs, une méthode itérative dite "top down" a été utilisée Cette méthode consiste à 2-0 sélectionner à chaque étape un ensemble de zones d'image candidat, suivant une résolution croissante et sur un champ de recherche de taille décroissante: La première étape sélectionne un nombre N 1 de zones suivant les valeurs décroissantes de l'écart de e calculées à partir d'une seule valeur propre, pour toutes les zones de l'image. L'écart pour chaque zone est calculé de la manière suivante: e = (s 1)2 o'1 k 1,m lU(k,1) r 1, m A'(k,r)*V(r,1)l Les N 1 positions des zones conduisant aux écarts les plus faibles sont conservées et seront utilisées à l'étape suivante. La deuxième étape trie parmi ces N 1 zones d'image un nombre N 2 de zones d'image suivant les valeurs décroissantes des écarts calculés en considérant P 2 valeurs propres. L'écart s'écrit: e = L (si s'i)2 = 1 à P 2 os i' = lU (k,i) A'(kr)lc V(ri) A la ième étape, ni zones d'image sont retenues, toujours suivant un critère de tri suivant les valeurs de d'écarts décroissantes, parmi les N 1 zones candidates retenues à l'étape précédente, 1-1, l'écart étant calculé suivant Pl valeurs propres. La dernière étape de sélection permet de sélectionner la zone d'image conduisant à l'écart minimal à partir de toutes les valeurs propres des matrices correspondant aux zones retenues à l'étape précédente Les nombres de zones et de valeurs propres retenues pour les calculs dans les différentes étapes sont donc tels que:. n 1 > N 2 > N 3 > > 1 (nombre de zones-image) 1 o Pt représente le nombre total de valeurs propres. Une étape finale consiste à effectuer une comparaison entre la signature de la zone objet et la signature de la zone d'image retenue dans la dernière étape du procédé itératif, la zone d'image retenue ne conduisant à la reconnaissance de l'objet que si les signatures sont suffisamment proches, l'écart correspondant étant par exemple inférieur à un seuil fixe prédéterminé. Dans un mode de réalisation, un nombre de 10 itérations a été utilisé (quelle que soit la taille de l'objet d'apprentissage). Deux contraintes ont été introduites: 1 Pour les 5 premières itérations, le nombre de valeurs propres utilisé correspond au rang de l'itération (lère itéra- tion, 1 valeur propre; 2 ième itération, 2 valeurs propres; ; 5 ième itération, 5 valeurs propres) La taille de l'objet à rechercher est supposée être supérieure à 10 x 10 pixels. 2 A la dernière étape, toutes les valeurs propres sont considérées. La première itération consiste donc en une sélection grossière et rapide des zones d'image susceptibles de satisfaire aux caractéristiques de la zone objet utilisée pour l'apprentissage, et les itérations successives permettent une sélection de plus en plus fine des zones d'image possibles, jusqu'à la dernière étape o une seule zone est sélectionnée. Pour chaque itération de rang supérieur à 5, le nombre de valeurs propres prises en compte a été calculé suivant la formule: pi = Ent la * (exp (k*li) 1) 1 o Ent signifie partie entière de l'expression entre crochets, et a = 25/(pt 100) et k = 1/5 * log(pt/5-1) o pt correspond au nombre maximal de valeurs propres avec les contraintes précédentes P 5 = 5 et p 10 = pt. Des perfectionnements sont utiles, notamment si l'objet à reconnaître a subi, du modèle à l'image traitée, une variation de luminance uniforme L'objet à rechercher dans l'image peut en effet avoir subi une variation de luminance due à un éclairement différent (imagerie visible) ou à une modification de tempéra- ture (imagerie infrarouge). Dans ce cas, le procédé tel que défini précédemment ne permet pas de retrouver l'objet dans l'image Il est alors nécessaire d'introduire le perfectionnement suivant: Une zone d'image A est considérée comme étant constituée de deux composantes: une composante d'information Ai représentée par une matrice de taille m x N une composante de variation de luminance: AL également représentée par une matrice de taille m x n Ces deux matrices sont telles que: A = Ai + AL et AL = k x II o II est une matrice de dimension N x m constituée de 1 et o le coefficient k représente la différence de luminance moyenne entre la zone d'image candidate et la zone objet d'apprentissage. L'enchaînement des phases du procédé de reconnaissance est identique à celui décrit précédemment, à la modification près suivante: La contribution de la variation de luminance est retirée à la matrice S' pour donner une matrice réduite SR' = S' k Ut * II * V o les coefficients de la matrice diagonale SR' sont tels que sr' = s' k corr (i,j) Le coefficient k doit être calculé pour chaque sousimage à la première itération et être conservé pour les itérations suivantes La valeur corr (i, j) est telle que corr(ij) =L u 1 v D r, k ukvr avec k = 1,m et r = 1,n. Les éléments de cette matrice doivent être complétés pour chaque nouvelle itération. L'écart e pour chaque sous-image s'écrit alors e =(s sri), avec i variant entre 1 et P Pour une variation uniforme de luminance et un nombre faible de cas de saturation (ceci exclut le cas d'une saturation trop importante et les réponses non linéaires des capteurs), le procédé a été mis en oeuvre en introduisant un décalage (offset) sur les valeurs de luminance de 100 (ce qui introduit une saturation de l'ordre de 2 % dans l'image). La sensibilité du procédé a été vérifiée en additionnant aux valeurs de luminance un bruit gaussien: l'écart augmente en fonction de l'augmentation de la valeur de bruit ( 4 valeurs propres ont été utilisées). L'influence de la rotation de l'objet dans l'image a également été analysée L'écart calculé évolue en fonction de la rotation de la sousimage: On observe une augmentation de l'écart en fonction de l'angle de rotation, mais l'écart reste faible pour des angles de rotation de 10 et 20 degrés successivement sur la détection d'un objet La reconnaissance n'est plus correcte pour un angle supérieur ou égal à 30 degrés. L'ensemble des valeurs propres représente une bonne si- gnature de l'objet et permet une reconnaissance sûre et robuste de celui-ci. Pour la mise en oeuvre du procédé, un algorithme optimi- sant le temps de calcul a donc été défini La reconnaissance est effectuée en plusieurs étapes Chaque étape correspond à une résolution L'initialisation est faite à une résolution grossière (sur les premiers valeurs propres) La dernière étape permet de sélectionner l'objet suivant une résolution fine (toutes les valeurs propres sont considérées) Pour cela, en résumé: la première étape de la procédure consiste à effectuer un premier tri des zones d'image sur la première valeur propre; à la ième étape, un tri est effectué sur les zones d'image sélectionnées à l'étape précédente sur un nombre plus grand de valeurs propres; à la dernière étape une seule zone d'image est retenue en considérant pour les zones d'image de l'étape précédente l'ensemble des valeurs propres. Ce procédé est utilisable par exemple dans une application au suivi et à l'identification, dans une suite d'images fixe, la signature de l'objet poursuivi devant être rafraîchie régulièrement pour tenir compte des modifications de formes dues à l'observation sous des angles différents et des masquages souvent observés dans ce type d'applications. La mise en oeuvre de ce procédé est évidemment effectuée par des moyens de traitement et de calculs informatiques convenablement programmés qui, à partir des valeurs de luminance des pixels des images, permettent de sélectionner dans une image de référence une zone image correspondant à l'objet à détecter, de traiter cette zone objet pour en déterminer la signature au sens défini ci-dessus, puis de traiter les images dans lesquelles l'objet est recherché, selon le procédé itératif décrit ci-dessus. REVENDICATIONS 1 Procédé de reconnaissance d'objets dans des images comportant une phase d'apprentissage au cours de laquelle la zone objet à reconnaître sélectionnée dans une image d'apprentissage est modélisée, et une phase de reconnaissance au cours de laquelle la zone modélisée est comparée à des zones image de même taille prises dans les images à traiter, caractérisé en ce qu'il utilise, pour la caractérisation des zones d'images modèle d'objet à reconnaître ou zones d'images à traiter, une décomposition des matrices des valeurs de luminance en valeurs singulières selon un produit matriciel de matrices de projection et d'une matrice diagonale ordonnée, cette dernière constituant une signature caractéristique de la zone considérée, et en ce que pour la phase de reconnaissance, des écarts entre la signature de la zone modèle et les signatures de la zones de l'image considérée sont calculés et des zones d'image sont sélectionnées à partir des moindres écarts selon un procédé itératif tel que dans une première étape seul le premier coefficient des matrices signature ordonnées est considéré pour le calcul des écarts mais pour toutes les zones d'image possibles, puis dans une seconde étape les P 2 premiers coefficients des matrices signature, P 2 supérieur à 1, sont considérés pour un ensemble réduit de N 1 zones d'image sélectionnées à l'étape précédente comme présentant les moindres écarts, dans une ième étape, un nombre pi supérieur à Pl 1 ' de coefficients des matrices est considéré pour un ensemble réduit de ni zones d'image sélectionnées à l'étape ( 1-1) car présentant les écarts les plus faibles, i variant de 3 à k-1, dans une kième et dernière étape, tous les coefficients des matrices signatures de zones d'image sélectionnées à l'avant dernière étape sont considérées pour sélectionner la zone d'image présentant l'écart de signature le plus faible avec la zone modèle. 2 Procédé selon la revendication 1, caractérisé en ce que (s 1, si, sp) étant les coefficients de la matrice signature ordonnée de la zone modèle et (s') IL p étant les coefficients de la matrice signature ordonnée d'une zone d'image à analyser, l'écart calculé à la première étape est (s S 11)2 et à une étape ultérieure j, l'écart calculé est égal à (S S i = 1 à pj o j est le rang de l'étape du procédé itératif et p, le nombre de valeurs propres utilisées à cette étape. 3 Procédé selon la revendication 1, caractérisé en ce que la phase de reconnaissance est suivie d'une étape finale de comparaison entre les signatures selon laquelle l'objet de la zone modèle n'est reconnu dans la sous-image sélectionnée à l'issue de la phase de reconnaissance que si sa signature est proche de la signature de la zone modèle, l'écart entre leurs signatures respectives étant inférieur à un seuil prédéterminé. 4 Procédé selon l'une des revendications 1 et 2, caractérisé en ce que le procédé itératif est tel que pour les premières étapes, le nombre de coefficients des matrices signature utilisés pour les calculs d'écarts est égal au rang de l'itération et en ce que pour les étapes suivantes, le nombre de coefficients est déterminé pour augmenter progressivement jusqu'à la valeur finale Pt, o pt est le nombre maximal de coefficients des matrices signature. 5 Procédé selon l'une des revendications précédentes, caractérisé en ce que, lorsque l'objet à traiter subit des variations de luminance, la matrice signature de la sous-image analysée est préalablement traitée pour en extraire la variation de luminance, de façon que les signatures de la zone modèle de l'objet et de la sous-image analysée soient comparables.