Auto et intercorrélation, recherche de ressemblance dans les signaux : application à l’identification d’images floutées
Signature : | Mis en ligne le : 27/01/2013
Catégorie(s) :
  • GNU/Linux Magazine
  • Commentez
    Article publié dans :
    Achetez
    Linux Magazine 139 :
    Version Papier
    Version PDF
    Page 1/8
    Page suivante »

    La disponibilité d’une masse croissante de données via Internet permet à chacun d’appréhender des problèmes qui restaient confinés jusque récemment à un cercle restreint d’utilisateurs suffisamment chanceux pour accéder à ces données. Ainsi, seule la compétence de traitement limite aujourd’hui la capacité de toute personne à extraire un maximum d’informations de ces données.

    1. Introduction

    Par exemple, une équipe anglaise a ainsi identifié au moyen d’un accès gratuit aux images satellites de résolution médiocres (preview [1]l’accès aux previews des satellites dont les images sont commercialisées en pleine résolution par DigitalGlobe est disponible à http://browse.digitalglobe.com/imagefinder/main.jsp ) la localisation de toutes les colonies de manchots en Antarctique, tâche impossible à réaliser (ou financer) par un mode d’observation dédié à cet objectif [2]P.T. Fretwell & P.N. Trathan, Penguins from space: faecal stains reveal the location of emperor penguin colonies, Global Ecol. Biogeogr. 18, 543-552 (2009). Une des approches les plus intuitives est la recherche de l’occurrence (ou absence) d’une information dans cette masse de données. Pour appliquer plus précisément ce concept aux images, il s’agit de rechercher l’occurrence d’un motif. Nous proposons donc ici une présentation d’un outil classique de recherche de ressemblances entre motifs : la corrélation. Concrètement, après une brève introduction théorique, nous appliquerons ce concept aux images (rechercher l’occurrence d’un motif) et étude dans des séquences temporelles d’images de déplacement de motifs (champ de déplacements), qui serviront de mise en place des outils en vue du cœur du sujet, la recherche de zones floutées dans les images. Enfin, nous conclurons sur un cas particulier où l’utilisateur choisit le signal sonde qui va servir à détecter une cible, et montrerons comment un choix judicieux des propriétés statistiques permet de maximiser les chances d’identifier l’écho et sa localisation.

    L’ensemble des expérimentations de traitement statistique du signal se fera au moyen de GNU/Octave (www.gnu.org/software/octave) [3]J.-M Friedt, Affichage et traitement de données au moyen de logiciels libres, GNU/Linux Magazine France 111 (Déc. 2008), un port open source de l’outil propriétaire Matlab de Mathworks totalement fonctionnel depuis l’implémentation de la majorité des toolbox, et notamment signal processing toolbox dans le cas qui nous intéressera ici. L’objectif de cette étude, au-delà d’acquérir quelques connaissances utiles pour extraire toute l’information de la masse de données accessibles sur le Web, est d’être conscient des risques associés à ces données, notamment par une analyse systématique de la statistique du signal. Par exemple, il est bien connu qu’une analyse du flux de données fournit une information en cryptographie sans nécessairement permettre l’identification de l’information elle-même : il est peu judicieux de ne crypter par PGP que les messages à vocation de secret, messages qui ressortiront trivialement lors d’une analyse de flux [4]D. Kahn, The codebreakers – the story of secret writing, The MacMillan Company (1973). Une extrapolation audacieuse qui conclura notre étude est que de la même façon, il est peu judicieux de manuellement modifier les propriétés statistiques (flouter), les zones considérées comme sensibles sur les images aériennes, la signature associée à cette opération étant identifiable.

    2. L’intercorrélation : quelques notions de base

    Le concept que nous proposons de mettre en œuvre au cours de cet exposé est l’intercorrélation entre deux signaux. Ce concept vise à extraire le " taux de ressemblance " entre deux signaux unidimensionnels (signaux temporels, par exemple) ou bidimensionnels (images). La définition mathématique de ce concept, que nous nous efforcerons d’intuiter par la suite, est que l’intercorrélation entre deux signaux, supposés unidimensionnels dans un premier temps, de moyenne nulle, s(t) et s′(t) est :



    Le lecteur qui ne désire pas entrer en détail dans la compréhension de cette formule – et par là esquiver toute chance de comprendre le sens du concept – pourra se contenter d’expérimenter avec les fonctions xcorr() et xcorr2() (pour la version 2D applicable en imagerie) de GNU/Octave. La philosophie de l’intercorrélation est de rechercher le retard (ou translation t) qui permet de maximiser la ressemblance entre s et s′. En effet, ce n’est que pour un retard t qui maximise la ressemblance que la somme s’effectue de façon cohérente avec des produits si et s'i−t tous positifs (de l’ordre de si2). Dans le cas contraire, le produit des valeurs de si se fait avec un signal s′ de valeur moyenne nulle qui a toutes les chances de fournir un résultat proche de 0. Ainsi, nous allons rechercher t qui maximise la somme des éléments du produit s(i)xs′(i-t) lorsque le retard t permet à s de ressembler au mieux à s′ décalé de t.



    Figure 1 : Deux signaux qui pourraient s’apparenter à une impulsion de RADAR, au milieu le signal émis, et en haut le signal récupéré après un certain temps de vol et réflexion sur une cible statique. En bas, l’intercorrélation entre le signal émis et le signal reçu n’est non nul que lorsque le signal reçu ressemble au signal émis. Le maximum d’intercorrélation, par exemple identifié ici comme maximum de l’enveloppe de l’intercorrélation (valeur absolue puis filtre passe-bas) indique le retard (ou temps de vol) entre impulsion émise et reçue.

    On notera la forte ressemblance entre la définition de la corrélation xcorr(s,s′)(t) et la convolution définie par :



    Dans ce cas, le produit dans l’intégrale se fait en balayant s selon un axe du temps i croissant, tandis que le second signal s′ est décalé d’un retard t mais balaie le temps à l’envers (-i). Cette opération reflète l’application du filtre défini par s′ au signal s. Cette digression est nécessaire pour entrer dans les détails pratiques de la mise en œuvre de l’intercorrélation : par souci d’efficacité, il nous faut impérativement passer par le domaine spectral (transformée de Fourier). En effet, une relation fondamentale [5]F. Roddier, Distributions and transformation de Fourier, Edisciences International, Paris (1978) [chapitre 11] pour la mise en place d’un calcul d’intercorrélation est le fait que la transformée de Fourier (TF) de la convolution de deux signaux est le produit des transformées de Fourier de chaque signal :

    TF(conv(s,s′))=TF(s′)× TF(s)

    Cette affirmation, apparemment anodine, permet de passer d’un nombre de multiplications de l’ordre de N2 (avec N le nombre d’éléments du vecteur à analyser) vers N.ln N grâce à l’algorithme de transformée rapide de Fourier (Fast Fourier Transform – FFT) [6]un point de vue historique sur les performances d’un ordinateur nécessaires à ces calcluls : Y. Granclaude & J.Y. Ranchin, Corrélation et convolution par transformées entières, actes du Septième colloque sur le traitement du signal et ses applications (Nice, 1979), disponible à http://documents.irevues.inist.fr/bitstream/handle/2042/10373/AR66.pdf. Une subtilité subsiste : nous nous proposons de travailler sur la corrélation, alors que nous énonçons un théorème sur la convolution. On aura remarqué, par rapport à la définition de la corrélation, l’inversion du signe sur le terme de la variable d’intégration : dans un cas, la variable glisse le long de l’axe du temps (s′(i-t)), dans l’autre cas, elle glisse dans le sens opposé (s′(t-i)). Le passage de la convolution à la corrélation va donc soit s’obtenir par inversion de l’axe du temps dans le domaine temporel (rotation de 180° du motif s′) [7]une autre excellente illustration des concepts présentés dans le premier chapitre de ce document : http://www.mathworks.com/help/toolbox/images/f21-17064.html, soit dans le domaine spectral en prenant le complexe conjugué de la transformée de Fourier. On pourra se convaincre que cette dernière opération inverse la direction du temps en considérant que le complexe conjugué de exp(i× ω t) est exp(-i× ω t) (avec t le temps, ω une pulsation et i2=-1).

    Appliquons ces concepts quelque peu abstraits en l’état au cas particulier de la recherche de l’occurrence d’une lettre dans un texte. Si la corrélation est un estimateur capable d’identifier le taux de ressemblance entre deux motifs, alors en prenant un texte (Fig. 2, en haut à gauche) dont on extrait une lettre (Fig. 2, en haut à droite), nous devons être capables de retrouver la position de toutes les occurrences de ces lettres dans le texte. Au-delà des points déjà mentionnés sur le retournement de l’axe des temps de s′, le dernier point fondamental à ne pas oublier est que s et s′ doivent être de moyenne nulle : on prendra soin de toujours retrancher la valeur moyenne de s et s′ avant tout calcul (fonction mean() dans GNU/Octave). Afin d’illustrer les deux modes de calcul cités auparavant, nous pouvons dans un premier temps appliquer la convolution en deux dimensions (fonction conv2() de GNU/Octave) :

    Vous souhaitez commenter cet article ?
    Brèves Flux RSS
    Édito : GNU/Linux Magazine Hors-Série N°72
    Édito : Linux Pratique N°84
    Édito : MISC N°74
    Édito : GNU/Linux Magazine N°173
    Édito : MISC Hors-Série N°9
    Communication RSS Com. RSS Presse
    HACKITO ERGO SUM
    GNU/Linux Magazine, partenaire du SymfonyLive Paris
    Opensilicium, partenaire de RTS EMBEDDED
    Linux Pratique et Linux Essentiel, Partenaire de l’Open World Forum
    Gnu/Linux Magazine, Partenaire des JDEV 2013
    Rechercher un article dans notre base documentaire :
    En kiosque Flux RSS

    Le tout nouveau GNU/Linux Magazine HS est disponible dès maintenant chez votre marchand de journaux et sur notre site marchand.

    Découvrez le sommaire de ce numéro et un aperçu de ce magazine...

    Lire la suite...

    Le tout nouveau Linux Pratique est disponible dès maintenant chez votre marchand de journaux et sur notre site marchand.

    Découvrez le sommaire de ce numéro et un aperçu de ce magazine...

    Lire la suite...

    Le tout nouveau Misc est disponible dès maintenant chez votre marchand de journaux et sur notre site marchand.

    Découvrez le sommaire de ce numéro et un aperçu de ce magazine...

    Lire la suite...

    Le tout nouveau GNU/Linux Magazine est disponible dès maintenant chez votre marchand de journaux et sur notre site marchand.

    Découvrez le sommaire de ce numéro et un aperçu de ce magazine...

    Lire la suite...

    Le tout nouveau Open Silicium est disponible dès maintenant chez votre marchand de journaux et sur notre site marchand.

    Découvrez le sommaire de ce numéro et un aperçu de ce magazine...

    Lire la suite...