FR 2623927 A1 19890602 FR 8815356 A 19881124 - 1.- Procédé et dispositif Dour la détection et la localisation d'une Portion d'imaoe L'invention concerne un procédé et un dispositif pour la détection et la localisation d'une portion d'image dans une image d'ensemble à l'aide d'un dispositif de traitement d'image, dans lequel sont traités des signaux de points d'image divisés en lignes et en colonnes issus de convertisseurs opto-électroniques, et qui comprend au moins un filtre. La détection de la position d'une portion d'image donnée dans une image d'ensemble constitue un problème important du traitement d'image. Cette tache désignée coame localisation d'image peut être résolue de différentes manières. Les procédés les plus importants se basent sur la correlation croisée et sur la détermination de grandeurs d'erreur. Pour les deux procédés, la littérature fournit de nombreuses modifications et améliorations. Or, sous certaines conditions, ces procédés peuvent être transformés les uns dans les autres et mènent par conséquent à des résultats semblables. On part ci-après d'abord d'images discrètes qui peuvent être décrites par des pixels. Afin de simplifier, on supposera que les décalages entre les images correspondent également à des pixels (éléments d'image) entiers. Sont données deux images B et R rectangulaires qui sont représentées par leurs valeurs de gris B(i,j) et R(i,j) aux points discrets avec les coordonnées i et J, avec B(i,j) = 0 si i nbi ou j nbj (1) 2 5 R(ij) = si i nri ou j nrj L'image R représente une portion plus petite de l'image B, à la meme échelle. Donc nbi > nri (2) - 2 - nbj > nri Or, on admettra que les valeurs de gris R(i, j) de l'image R se distinguent des valeurs de gris B(i,j) correspondantes de l'image B par une perturbation additive N(l,j). Avec la position de décalage réelle ivt et ivt dans le sens des colonnes et des lignes, on obtient: R(i,j) = B(i+ivt, j+jvt) + N(i+ivt, j+jvt) (3) Une stratégie de localisation optimale fournit le vecteur de décalage Civo,jivo. qui est le plus probable parmi tous les vecteurs de décalage [iV, jv] ackdmissibles. Pour les probabilités conditionnelles p(a/b) vaut donc avec une stratégie optimale: p (ivoJivo]=[ivt,jvtj/ B,R) > p(liv,jv)=tivt,Jivt]/ B,R) 1 5 avec [ivj [ivo,Jvo] (4) A cet effet, il faut déterminer toutes les probabilités conditionnelles p(liv,jv]=civt,Jvt]/ B,R) qui expriment avec quelle probabilité le décalage livJv] coïncide avec le décalage réel [ivt,jvt], en admettant que les images B et R existent. Le théorème de Bayes permet de transformer cette équation: - p (B,R /[ivoivo =[ivtJvt]) * P([ivo,Jvc= tivt,Jvt]) / p(BR) > p (B,R /[ivJv3=[ivtiv) * p([ivjv=[ivtJvtI) / p(B,R) avec[iViv] J [ivoJvol (5) 2 5 Dans le cas o toutes les positions de décalage présentent la même probabilité a priori ou aucune information n'est disponible concernant ces probabilités, et ces dernières sont donc supposées comme étant identiques, il résulte: p(B,R /[ivoJv= [ivt,Jvtl) > p(B,R /[VivJvl=[ivtjvt]) avecCivJv] l[ivo'ivol (6) - 3- En désignant la différence entre l'image R(i-iv,j-jv), décalée de [iv,jvl, et l'image B(i, j) par N- (i,j) tiv,jvl= R(i-iv,i-jv) - B(i,j) (7) on obtient pour les probabilités nécessaires dans l'équation 6: p(B,R / Livjv]=CivtJvt]) = p(N(i,j) = Nd(i,j)Liv,jv]) (8) Le calcul de ces probabilités n'est généralement possible que sous certaines conditions. Dans le cas o les perturbations N-(i,j), définies selon l'équation 7, n'ont pas de correlation locale et présentent une fonction de densité de probabilité de Gauss, il est possible d'indiquer la stratégie de localisation optimale selon l'équation 6 en utilisant l'équation 8. Apres un calcul logarithmique et l'omission de termes identiques des deux cotés de l'inéquation, on obtient: 1 ((N(I,)[ voJvo])) nri ou j nrj R,(i,j)[ivJvj = 1 R(IJ) *R'(1,j)[ivJv] (11) ij ij Or, ces deux équations connues, à savoir la détermination de grandeurs d'erreur selon l'équation 9 et l'équation de correlation 11, fournissent une localisation optimale uniquement dans les conditions rigoureuses indiquées ci-dessus. 4 - Un filtre discret, avec lequel l'image B(i,j) et l'image partielle R(i,j) sont filtrées, permet de modifier la correlation des valeurs de gris des perturbations. Un tel filtre, qui élimine complètement les correlations existantes, est appelé filtre de décorrelation. Or, la détermination des coefficients de filtre n'est possible que si les grandeurs caractéristiques statistiques de la perturbation N.(i,j) sont connues, ce qui n'est pas possible techniquement pour des raisons de causalité. Dans les procédés connus avec des filtres discrets fixes (filtres de prétraitement), l O on s'efforce simplement avec une hypothèse statistique de diminuer les correlations locales des perturbations. Le résultat dépend néanmoins dans une large mesure des images. L'invention a pour but d'indiquer un procédé et un dispositif pour la localisation d'une portion d'image dans une image plus grande (image d'ensemble), permettant d'obtenir une meilleure fréquence de localisation, meme lorsque les perturbations, définies selon l'équation 7, sont en correlation. Conformément à la présente invention, il est propose un procédé pour la détection et la localisation d'une portion d'image dans une image d'ensemble à l'aide d'un dispositif de traitement d'image, dans lequel sont traités des signaux de points d'image divisés en lignes et en colonnes issus de convertisseurs opto-électroniques, ledit dispositif comprenant au moins un filtre, caractérisé en ce que pour le traitement d'image adaptatif préalable, un filtre (fv) 2 5 discret variable est associé à chacune des mémoires d'image (Memo 1, 2) pour - l'image d'ensemble (B(i,j)), - l'image partielle ou portion d'image (R(i,j)), et les deux filtres (fv) sont reliés à un calculateur (C), qui effectue un calcul des coefficients de filtre pour chaque image à partir des grandeurs caractéristiques statistiques des images filtrées ou non filtrées. L'invention propose également un dispositif pour la mise en oeuvre d'un procédé de localisation d'image (partie d'une image - 5 - d'ensemble), dans lequel des signaux de points d'image issus de convertisseurs optoélectroniques sont transformés en données d'image et filtrés, caractérisé en ce que chaque filtre (fv) discret variable est combiné avec un filtre (ff) discret fixe et on choisit entre deux filtres et/ou modes, ou bien est chargé au choix avec au moins deux groupes de coefficients de filtre déterminés de manière différente. Selon un mode de réalisation particulier, non limitatif, du dispositif selon l'invention, est relié au calculateur (C) un étage d'entrée (E) pour la détermination de l'autocorrelation qui - extrait de façon serielle, par lignes (point par point dans les colonnes) ou par colonnes (point par point dans les lignes) , les données d'image pour chaque image à partir de la mémoire (Memo 1, 2) associée, - commande des organes de multiplication (M) pour la multiplication de ces données d'image et - commande, pour la sommation, des organes d'addition (A) dont les sorties sont reliées chacune à un étage de division (D). Quelques-unes ou toutes les fonctions de l'étage d'entrée (E) ci-dessus peuvent aussi etre effectuées dans le calculateur (C). Le procédé et le dispositif selon l'invention permettent aussi d'obtenir une meilleure décorrelation des perturbations dans le cas d'images différentes. Contrairement à des procédés et dispositifs connus, une 2 5 localisation d'image avec une correlation normalisée est effectuée au moyen d'un prétraltement adaptatif, o les coefficients de filtre sont adaptés au contenu de l'image et calculés dans un calculateur. Au calculateur est associé un étage préliminaire pour la détermination approximative de la fonction d'autocorrelation de la perturbation. Pour la détermination de l'autocorrelation ainsi que pour la détermination des coefficients de filtre, on applique un modèle de calcul (algorithme). Le modèle de calcul, appliqué dans l'étage préliminaire E du calculateur C - selon les figures lb et 2 "détermination de Z623927 -6- l'autocorrelation" -, et pour une compréhension générale, la correlation normalisée selon la figure 3 sont présentés ci-apres a titre d'explication: Lorsque, comme il est le plus fréquent, les deux images (image d'ensemble et image partielle) sont générées par des unités d'enregistrement différentes, elles se distinguent en plus par un facteur multiplicatif (positif) dont il est tenu compte ci-après. De plus, il est judicieux de séparer une constante des perturbations additives, de manière à réduire à un minimum l'énergie de la perturbation N(i,j). En utilisant la position de décalage réelle ivt et iJvt, on obtient de manière analogue à l'équation 3: R(l,j) = km * B(i+ivt,j+jvt) + ka + N(i+ ivt,j+jvt) (12) 1 5 km > 0 La substitution B'(i+ivt,j+jvt) = km * B(i+ivt, j+Jvt) + ka (13) permet d'effectuer la localisation essentiellement avec les algorithmes de localisation décrits dans le paragraphe précédent selon l'équation 9 ou 11, si les perturbations N(i,j) présentent une fonction de densité de probabilité de Gauss et sont sans correlation. Dans les équations précédentes, l'image B(i,J) doit être remplacée par une estimation B"(i,j) et l'image R (i,j)[iv,jv] 2 5 par / O si i nri ou j nri RI'-(i,ji)[ivjv] = 26239-27 - 7 - L'expression N'(I1i)tIViJv])2 (R(t-iv,j-Jv) - B"(,j))2 (15) 1,j i,: utilisée dans l'équation 9 constitue une mesure pour l'énergie des parties perturbantes. La mise en équation B"(i,j) = ci * (B'(ij) - c2) (16) permet de déterminer, par différentiation partielle et par mise à zéro subséquente, les constantes c1 et c2 de façon à ce que l'énergie selon l'équation I5 prenne une valeur minimale. Dans ce cas, la sommation ne doit etre effectuée que dans les zones d'image, dans lesquelles l'image R existe. Dans ce modèle, la valeur moyenne linéaire des valeurs de gris n'influence pas la localisation. Il est donc admissible de normaliser préalablement l'image R(i,j) de telle façon que la valeur moyenne linéaire soit égale à zéro. Dans ce cas, les équations sont sensiblement plus simples. Il est possible de trouver une solution d'approche, si les images partielles R"'-(i,j)Civ,jv] définies dans l'équation 10 sont normalisées de la meme manière que l'image R(i,j). La combinaison de deux étages de normalisation successifs convient pour la normalisation du modèle choisi. Pendant la première étape, les éléments Identiques des valeurs de gris des images sont éliminés. Ensuite, les deux images sont multipliées chacune par un 2 5 facteur qui fait que les deux Images présentent la meme énergie. La figure 3 montre le schéma bloc d'une localisation d'image fonctionnant suivant ce principe. Dans ce schéma bloc, on suppose que la détermination des valeurs individuelles de la fonction de correlation ou de la fonction d'erreur se fait par étages successifs. On considère comme décalage ivoivo trouvé celui auquel est associee la plus grande valeur de la fonction de correlation ou la plus petite valeur de la fonction d'erreur. -8- Le procédé connu de correlation normalisée présente jusqu'ici peut etre amélioré par des filtres de prétraitement, ce qui augmente la fréquence de localisation. Or, pour la détermination des coefficients pour un filtre fixe il est désavantageux que les coefficients de filtre ne puissent être optimisés que pour un cas individuel. Dans le cas o les grandeurs caractéristiques statistiques des images se modifient de façon défavorable, l'utilisation d'un filtre de pretraitement peut renore plus mauvaise la probabilité d'erreurs de localisation, c'est-a-dire la précision de localisation. Par conséquent, il est nécessaire pour l'optimisation du filtre d'utiliser un très grand nombre d'images représentatives. La correlation des valeurs de gris entre elles peut être décrite par une fonction d'autocorrelation Ln(i,j) normalisée à deux I 5 dimensions: X(N(iijj) * N(ii.1,jj+j) Ln(iJ) - (17) i(N(iijj) N1(iJj)) il,jj 2 0 Dans ce cas, les perturbations N(i,j) sont sans correlation, si:! / 1 si 1=0 et j=O Ln(i,j) = Dans la description ci-après, on part de la supposition qu'un filtre de prétraitement à deux dimensions avec les grandeurs nfi et nfj dans le sens des colonnes et oes lignes est utilisé. Les coefficients de filtre sont désignés par F(i,j), pour lesquels: F(lj> = O sI I nfi ou j nfj (19) -9- La décorrelation de la perturbation N(i, j) équivaut à une minimisation de l'énergie de perturbation Enf de la perturbation filtrée, pour laquelle: nf ' Ln(l.j) * F(I,J)*F(ii+t,jj+) (20) Âti.:1i,Jj La différentiation partielle et la mise à zéro permettent de déterminer les coefficients de filtre F(i,j) du filtre de prétraitement, un coefficient de filtre devant rester fixe, car pour ce procédé seules les relations entre les coefficients de filtre sont necessalres. De la détermination des coefficients résulte un système d'équation linéaire qui peut etre résolu de manière relativement simple. Pour le calcul d'un filtre de décorrelation il est nécessaire de connaître les grandeurs caractéristiques statistiques de la perturbation N(i,j). Il n'est possible d'indiquer cette perturbation, qui doit etre déterminée selon l'équation 3, que si la localisation correcte a été effectuée. Afin de pouvoir déterminer les grandeurs caractéristiques statistiques, il faut dépouiller un très grand nombre de localisations. L'lnvention concerne notamment un procédé adaptatif pour le prétraitement d'images. Pour cela, des estimations concernant l'autocorrelation des perturbations sont effectuées en fonction du contenu de l'image et de la zone de recherche concernée. - Pour une grande zone de recherche, on suppose que la 2 5 perturbation selon l'équation 3 se compose en grande 'partie de la non Image. Par conséquent, l'autocorrelation de la perturbation cotncidera sensiblement avec l'autocorrelation de l'image. Pour une grande zone de recherche, l'autocorrelation selon la figure lb peut etre déterminée de manière approximative à partir de l'image B(i,j). La détermination de la localisation exacte nécessite une correlation supplémentaire autour du point de localisation le plus probable trouvé préalablement. La supposition sur les perturbations, - 10 - utilisée auparavant, n'étant dans ce cas plus valable, une commutation sur un filtre discret fixe est alors nécessaire, ce qui entraîne une détermination des coefficients de filtre fixes à partir d'une hypothèse statistique sur les perturbations. Ce principe est représenté dans la figure 2. Une autre possibilité consiste à utiliser un seul filtre variable à la place de deux filtres et d'un dispositif de commutation, et dans ce cas on charge et utilise au choix des coefficients de filtre fixes ou adaptatifs (calculés selon l'équation 20). Des exemples de réalisation de l'invention sont illustrés dans les figures 1 à 4, parmi lesquelles la figure la représente une portion cherchée dans une image d'ensemble, la figure lb représente une localisation d'image avec prétraitement adaptatif, la figure 2 représente une localisation d'image avec prétraitement adaptatif commutable, la figure 3 représente un schéma bloc d'une localisation d'image, et la figure 4 représente une détermination des valeurs normalisées de la fonction d'autocorrelation. L'invention concerne notaxmment un prétraltement d'image adaptatif pour la décorrelation partielle. L'utilisation de la décorrelation permet d'obtenir des valeurs 2 5 extremes, délimitées localement de façon très nette, dans la fonction d'erreur ou de correlation. La détermination des valeurs extremes ne peut donc souvent etre effectuée qu'après l'utilisation d'un procédé d'interpolation. Lorsque l'on veut éviter d'utiliser un procédé d'interpolation dispendieux, la prédéfinition d'une fonction d'autocorrelation des images filtrées permet d'adapter la forme des valeurs extrêmes de la fonction d'erreur ou de correlation. Dans ce cas, le calcul des coefficients de filtre devient considérablement plus coûteux. La convolution des coefficients, calculés à partir de l'équation 20, avec une fonction - 11 - modèle, conduisant à la fonction de correlation souhaitée, permet néanmoins d'obtenir ici également une détermination simple des coefficients de filtre définitifs. Pour une réalisation de l'invention permettant une localisation d'image en temps réel vidéo ( réel vidéo. Avec l'utilisation d'un prétraitement, on a optimisé dans cet exemple un filtre avec la grandeur nfi = 1 (valeurs dans le sens des colonnes) nij = 5 (valeurs dans le sens des lignes) i5 Néanmoins, avec le prétraitement adaptatif seuls trois coefficients ont été déterminés suivant l'équation 20. En désignant ces coefficients par F'(i,j), on obtient le système d'équation suivant: Enf = Ln(O,-2) * (F'(1,1)*F'(1,3)) + Ln(O,-1) * (F'(1, 1)*F'(1,2) + F'(1,2)*F'(1,3)) + Ln(O,O) * (F'(1,1)2 + F'(1,2)2+ F'(1,3)2) (21) + Ln(0,1) * (F'(1,1)*F'(1,2) + F'(1,2)*F'(1,3)) + Ln(0,2) * (F'(1,1) *F'(1,3)) L'un des trois coefficients de filtre à déterminer peut être choisi librement, par exemple: 2 5 F(1,1) = 1 Si l'on considère les qualités de symétrie de la fonction d'autocorrelation Ln(i,j) = Ln(i,-j) et sa valeur à la position (0,0) selon l'équation 17 Ln(O,O) = 1, - 12 - on obtient à partir de l'équation 21: Enf = 2 * Ln(0,2) * F'(1,3) + 2 * Ln(0,1) * (F'(1,2) + F'(1,2)*F'(1,3)) + (1 + F'(1,2)2 + F'(1,3)2) Pour la détermination de F'(1,2), il faut différencier partiellement cette équation selon F'(1,2) et la mettre a zéro: 0 = 2 * Ln(0,1) + 2 * Ln(0,1) * F'(1,3) + 2 * F'(1,2) Pour la grandeur F'(1,3), on obtient de la meme manière: 0 = 2 * Ln(0,2) + 2 * Ln(0,1) * F'(1,2) + 2 * F'(1,3) Du système d'équation linéaire il résulte: F'(1,1) = 1 (selon l'hypothèse) F'(1,2) = Ln(0,1) * (Ln(0,2) - 1) / (1 - Ln(0,1)2) F'(1,3) = (Ln(0,1)2 - Ln(0,2)) / (1 - Ln(0,1)2) Pour une détermination plus facile de valeur maximale de correlation, il est possible, si on le désire, d'effectuer en plus une convolution de ce vecteur de résultat avec un vecteur de forme. Dans ce cas, pour les coefficients du filtre utilisé: F(1,1) = F'(1,1) F(1,2) = 2 * F'(1,1) + F'(1,2) F(1,3) = F'(1,1) + 2 * F'(1,2) + F'(1,3) 2 5 F(1,4) = F'(1,2) + 2 * F'(1,3) F(1,5) = F'(1,3) La détermination de ces coefficients, qul doivent etre à nouveau déterminés pour chaque image, ne nécessite que les valeurs de correlation Ln(O,1) et Ln(0,2). Ces dernières peuvent être facilement déterminées en temps reel vidéo, comme le montre le schéma bloc dans la figure 4. Dans ce cas, on suppose que les données d'image sont transmises de manière sérielle par lignes. Une - 13'- commande permet d'obtenir que la sommation ne soit effectuée que sur les points d'une ligne. La commande est comprise dans la figure 4. Dans la figure 4, aussi bien la portion d'image R(i,j) que l'image plus grande ou image résiduelle B(i,j) (portion d'image d'ensemble = image résiduelle) peuvent etre extraites des mémoires d'image partielle T. Les éléments de multiplication sont désignés par M, les organes d'addition par A et les étages de division par D. Les organes d'addition sont commandés par les circuits d'attaque.qủi leurs sont associés. - 14 - Revendications 1. Procédé pour la détection et la localisation d'une portion d'image dans une image d'ensemble à l'aide d'un dispositif de traitement d'lmage, dans lequel sont traités des signaux de points d'image divisés en lignes et en colonnes issus de convertisseurs opto-électroniques, ledit dispositif comprenant au moins un filtre, caractérisé en ce que pour le traitement d'image adaptatif préalable, un filtre (fv) discret variable est associé à chacune des mémoires d'image (Memo 1, 2) pour - l'image d'ensemble (B(i,j)), - l'image partielle ou portion d'image (R(i,j)), et les deux filtres (fv) sont reliés à un calculateur (C), qui effectue un calcul des coefficients de filtre pour chaque image à partir des grandeurs caractéristiques statistiques des images filtrées ou non filtrées. 2. Dispositif pour la mise en oeuvre d'un procédé de localisation d'image (partie d'une image d'ensemble), dans lequel des signaux de points d'image Issus de convertisseurs opto-électroniques sont transformés en données d'image et filtrés, caractérisé en ce que chaque filtre (fv) discret variable est combiné avec un filtre (ff) discret fixe et on choisit entre deux filtres et/ou modes, ou bien est chargé au choix avec au moins deux groupes de coefficients de filtre déterminés de manière différente. 3. Dispositif pour la mise en oeuvre d'un procédé selon larevendication 1 ou 2, caractérisé en ce qu'au calculateur (C) est 2 5 relié un étage d'entrée (E) pour la détermination de l'autocorrelation qui - extrait de façon serielle, par lignes (point par point dans les colonnes) ou par colonnes (point par point dans les lignes), les données d'image pour chaque Image & partir de la mémoire (Memo 1, 2) associée, - commande des organes de multiplication (M) pour la multiplication de ces données d'image et - 15 - - commande, pour la sommation, des organes d'addition (A) dont les sorties sont reliées chacune à un étage de division (D), quelques-unes ou toutes les fonctions de cet étage d'entrée (E) pouvant etre effectuées au choix également dans le calculateur (C).