• Accueil
  • À propos
  • Accrom\(\alpha\)th en PDF
  • Commanditaires
  • Contact
  • Contributions des lecteurs
  • Sites amis

Logo

L’imagerie numérique

Par Jean Meunier
Volume 9.2 - été-automne 2014

Pour réaliser leurs travaux1 les frères Chudnovsky ont fait appel à diverses méthodes issues du domaine de l’imagerie numérique. Ces différentes méthodes renvoient à trois grandes étapes: (1) identifier des points caractéristiques, (2) faire l’appariement de ces points entre les différentes photos de la tapisserie, et (3) effectuer une transformation géométrique de chaque photo pour aligner les points caractéristiques et reconstituer la tapisserie complète.

Identifier des points caractéristiques

imagerie0En traitement d’images on a recours fréquemment à l’extraction de points caractéristiques (ou points d’intérêt) pour diverses applications comme la détection du mouvement, le recalage d’images, l’assemblage de photos, la production d’un panorama, la reconnaissance d’objets, etc. Il s’agit de points bien définis et stables dans l’image. Par exemple, on peut chercher à détecter des « coins » en cherchant dans l’image les points où il y a un changement brusque dans la direction des contours des objets comme pour les quatre coins d’un objet rectangulaire. Cette approche permet d’obtenir automatiquement un ensemble de points caractéristiques sur chaque photo. La figure ci-contre donne un exemple2 de points caractéristiques (en vert) obtenus avec le détecteur SURF (Speeded Up Robust Features3) qui est populaire aujourd’hui en imagerie numérique.

Apparier des points correspondants

Lors de la prise des photos de la tapisserie, on a pris soin de s’assurer que celles-ci se recouvraient suffisamment pour pouvoir les aligner plus tard. Cette zone de recouvrement est relativement importante (de l’ordre de 50 %) et permet de trouver les points caractéristiques communs de photos de tapisserie qu’on souhaite aligner. Pour cela, on analyse une petite région (appelée voisinage) autour de chaque point caractéristique et on fait l’appariement des points qui possèdent un voisinage similaire. Pour mesurer la similarité entre deux voisinages a et b on peut par exemple calculer la somme des différences (en valeur absolue) de couleur de chaque pixel:

\[\sum_i \sum_j |a_{ij}-b_{ij}|,\]

où i et j représentent la position (ligne, colonne) du pixel dans le voisinage. Cette mesure sera petite si la similarité est grande. Cependant cela peut poser problème si l’illumination varie entre la prise de deux régions identiques photos puisque apparaîtront alors différentes en intensité dans ce cas. On peut alors miser sur une mesure plus robuste: l’intercorrélation, Corr.

On la définit comme suit:

\[Corr(a,b) = \frac{Cov(a,b)}{\sqrt{Cov(a,a)\cdot Cov(b,b) }}, \]

où

\[Cov(a,b)= \underset{i}{\sum} \underset{j}{\sum} (a_{ij}-\bar{a}) \cdot (b_{ij}-\bar{b})\]

est appelée covariance. \(\bar{a}\) et \(\bar{b}\) sont les moyennes respectives des \((a_{ij}\) et \((b_{ij}.\)

Elle atteint une valeur maximale de 1 lorsque les voisinages a et b sont identiques à une constante multiplicative ou additive près.

Prenons un exemple simplifié où seule l’intensité (ou luminance) du pixel est utilisée4. Considérons des voisinages de 3 × 3 pixels (ils sont plus grands en pratique) pour a et b. Ces voisinages sont identiques sauf les valeurs d’intensité de chaque pixel: celles de b valent la moitié de celles de a (comme cela pourrait être le cas avec un changement d’éclairage par exemple).

imagerie4

La somme des valeurs absolues des différences nous donne évidemment une différence importante, égale à (180-90) × 5 = 450. Par contre, pour l’inter-corrélation, on a:

\(\bar{a} = 100\) et \(\bar{b} = 50,\) puis

imagerie5

On a donc une corrélation maximale comme souhaitée car les deux voisinages sont identiques sauf pour l’illumination. En pratique, l’inter-corrélation ne sera pas égale à 1 mais plutôt proche de 1 pour les régions suffisamment similaires qui seront mises en correspondance. Pour des voisinages plus grands et de nombreux points caractéristiques à comparer, cette procédure peut être coûteuse en temps de calcul. De plus, pour tenir compte des déformations de la tapisserie d’une photo à la suivante, les frères Chudnovsky ont proposé de comparer chaque voisinage a à une transformation affine de b (rotation,translation,mise à l’échelle). L’utilisation d’un superordinateur parallèle s’est avérée très utile ici, car les différents processeurs ont pu se partager la tâche en travaillant chacun sur une partie de la tapisserie.

imagerie1

imagerie2

Les images ci-haut illustrent cette étape où chaque point caractéristique d’une image et le point correspondant dans l’autre image sont identifiés par un numéro (en rouge). La méthode utilisée ici est différente (SURF) mais le principe demeure le même.

Transformer pour réunir

L’exemple du panorama
Lorsqu’on souhaite produire un panorama avec plusieurs photographies, on a recours à un assemblage qui consiste à combiner plusieurs photos se recouvrant partiellement. Cependant il faut en général appliquer une transformation géométrique (projection perspective) aux images afin de bien les aligner lors de la construction du panorama. Cette transformation peut être obtenue automatiquement en cherchant à aligner le mieux possible les points caractéristiques des deux photos dans leur zone de chevauchement.

montagnes

La figure ci-haut illustre ce principe. La seconde photo a été transformée par projection perspective pour obtenir une superposition adéquate des points caractéristiques et placée sous la première photo pour mieux voir la ligne de démarcation entre les deux images. Cette ligne peut être éliminée en effectuant un fondu approprié entre les deux images.

Pour un panorama classique le type de transformation est connu (projection perspective); par contre pour la tapisserie, la transformation peut être beaucoup plus complexe et une simple transformation (perspective ou autre) ne suffit pas. Les frères Chudnovsky ont sans doute eu recours à une autre technique bien connue en infographie qu’on appelle le warping.

imagerie6Le warping
Le warping consiste à transformer de façon naturelle, graduelle et fluide une image initiale en une image finale différente en alignant deux ensembles de points caractéristiques tout en permettant des transformations complexes et réalistes. Pour cela on utilise souvent la triangulation de Delaunay qui consiste en un ensemble de triangles couvrant une image de façon optimale et dont les sommets sont les points caractéristiques. Les images ci-contre illustrent les principes sous-tendant cette technique. Dans cet exemple5, la triangulation permet d’effectuer le warping de l’image du haut vers l’image du milieu. Un résultat intermédiaire est donné en bas en effectuant un fondu des couleurs entre les deux images; on parle alors de morphing entre les deux images. Chaque triangle de l’image de gauche a un triangle correspondant dans l’image du centre afin de calculer les transformations nécessaires. Dans la reconstitution de la tapisserie, on utilise cette méthodologie pour aligner les photographies entre elles dans leurs régions de chevauchement.

On utilise donc l’emplacement des points caractéristiques obtenus précédemment pour construire une triangulation de Delaunay dans la zone de chevauchement des photo- graphies. Ensuite, connaissant le déplacement des points caractéristiques entre deux photos (puisque l’appariement des points est connu), il ne reste qu’à interpoler le déplacement des autres pixels à l’intérieur de chaque triangle à l’aide d’une simple transformation linéaire. La transformation complexe des photos est donc réduite à un ensemble de transformations beaucoup plus simples (linéaires) pour chacun des triangles.

La figure suivante illustre ce principe à l’aide d’un exemple simplifié. Le triangle rouge doit subir une transformation afin de le superposer sur le triangle bleu comme pour les paires de triangles utilisés dans le warping. On connaît la position des 3 points caractéristiques (sommets) pour les deux triangles mais qu’en est-il du point (2, 2) situé à l’intérieur du triangle rouge (point vert)? Où ce point se retrouvera-t-il dans le triangle bleu?

imagerie7

Pour répondre à cette question on doit d’abord trouver la transformation affine (linéaire) entre les deux triangles, c’est-à-dire une transformation dont la formulation est la suivante:

\[x’ = ax + by + c \\ y’ = dx + ey + f\]

où (x, y) est la position initiale des pixels dans le triangle rouge et (x’,y’) la position finale des pixels dans le triangle bleu. Afin de déterminer les paramètres a, b, c, d, e et f de cette transformation, il suffit de miser sur le déplacement connu des 3 sommets de ces deux triangles afin d’obtenir un petit système d’équations en remplaçant dans la transformation affine précédente les valeurs (x, y) et (x’, y’) connues des sommets.

Ainsi, la transformation de A(1, 1) vers A’(3, 3) nous donne:

\[a ×1+b ×1+c = 3 \\d×1+e×1+f =3\]

Celle de B(1,5) vers B’(4, 8):

\[a×1+b×5+c =4 \\d×1+e×5+f =8 \]

Et celle de C(4, 1) vers C’(8, 4):

\[a×4+b×1+c =8 \\d×4+e×1+f =4\]

Ce système linéaire de 6 équations à 6 inconnues est en fait constitué de deux petits systèmes indépendants de 3 équations à 3 inconnues (a, b, c, d’une part; et d, e, f, d’autre part). Il se résout aisément pour donner:

\[a=\frac{5}{3}, b=\frac{1}{4}, c=\frac{13}{12}, \\ d=\frac{1}{3}, e=\frac{5}{4}, f=\frac{17}{12}.\]

On peut maintenant répondre à la question: que devient le point (2, 2) du triangle rouge? En substituant dans la transformation affine la valeur des paramètres et la position (x, y) = (2, 2) on obtient

\[x’=\frac{5}{3}x+\frac{1}{4}y+\frac{13}{12}≈ 4,92, \\ x’=\frac{1}{3}x+\frac{5}{4}y+\frac{17}{12}≈ 4,58.\]

C’est ce principe qui permet d’interpoler le déplacement de tous les pixels à l’intérieur de chaque triangle couvrant la zone de chevauchement de la tapisserie et de pouvoir les recaler (aligner). Notons que les coordonnées finales (x’,y’)= (4,92; 4,58) ne sont pas des entiers ; il faudra donc recourir à une autre forme d’interpolation pour distribuer la couleur du pixel (2,2) sur les pixels voisins de coordonnées entières dans l’image finale. Au besoin il restera aussi à faire un ajuste- ment de l’intensité de certains pixels pour tenir compte de changements d’illumination entre la prise de deux photos en utilisant par exemple les changements observés au niveau des points caractéristiques et en interpolant ces valeurs à l’intérieur de chaque triangle.

PDF

  1. Voir dans ce numéro La quête de la licorne, p. 14-15. ↩
  2. Exemple adapté de http://www.wolfram. com/services/education/seminars/s51.html ↩
  3. Voir http://fr.wikipedia.org/wiki/Speeded_ Up_Robust_Features ↩
  4. Une image couleur aurait 3 composantes R, V et B. Voir « Les images sur la toile un défi de taille », Accromath 7.2, 2012 ↩
  5. Exemple adapté de http://www.mukimuki.fr/flashblo/labs/warping/MorphApp.html ↩
  • ● Version PDF
Partagez
  • tweet

Tags: Applications des mathématiques

Articles récents

  • Le paradoxe de Saint-Pétersbourg

    Michel Adès, Jean-François Plante et Serge Provost
  • Huit dames et un échiquier

    Alexis Langlois-Rémillard
  • Le système de notation Elo

    Christian Genest et Julien Fageot

Sur le même sujet

  • Le paradoxe de Saint-Pétersbourg

    Michel Adès, Jean-François Plante et Serge Provost
  • Huit dames et un échiquier

    Alexis Langlois-Rémillard
  • Le système de notation Elo

    Christian Genest et Julien Fageot

Volumes

  • Volume 17.1 – hiver-printemps 2022
  • Journée internationale des mathématiques: Accromath multilingue
  • Volume 16.2 – été-automne 2021
  • Volume 16.1 – hiver-printemps 2021
  • Volume 15.2 – été-automne 2020
  • Thème spécial: Les mathématiques sont partout
  • Volume 15.1 – hiver-printemps 2020
  • Volume 14.2 – été-automne 2019
  • Volume 14.1 – hiver-printemps 2019
  • Volume 13.2 – été-automne 2018
  • Volume 13.1 – hiver-printemps 2018
  • Volume 12.2 – été-automne 2017
  • Volume 12.1 – hiver-printemps 2017
  • Volume 11.2 – été-automne 2016
  • Volume 11.1 – hiver-printemps 2016
  • Volume 10.2 – été-automne 2015
  • Volume 10.1 – hiver-printemps 2015
  • Volume 9.2 – été-automne 2014
  • Volume 9.1 – hiver-printemps 2014
  • Volume 8.2 – été-automne 2013
  • Volume 8.1 – hiver-printemps 2013
  • Volume 7.2 – été-automne 2012
  • Volume 7.1 – hiver-printemps 2012
  • Volume 6.2 – été-automne 2011
  • Volume 6.1 – hiver-printemps 2011
  • Volume 5.2 – été-automne 2010
  • Volume 5.1 – hiver-printemps 2010
  • Volume 4.2 – été-automne 2009
  • Volume 4.1 – hiver-printemps 2009
  • Volume 3.2 – été-automne 2008
  • Volume 3.1 – hiver-printemps 2008
  • Volume 2.2 – été-automne 2007
  • Volume 2.1 – hiver-printemps 2007
  • Volume 1 – été-automne 2006
  • Article vedette

    Auteurs

    • Michel Adès
    • Antoine Allard
    • Jean Aubin
    • Marie Beaulieu
    • Rosalie Bélanger-Rioux
    • Claude Bélisle
    • Marc Bergeron
    • Pierre Bernier
    • André Boileau
    • Véronique Boutet
    • Pietro-Luciano Buono
    • Massimo Caccia
    • Jérôme Camiré-Bernier
    • France Caron
    • Philippe Carphin
    • Kévin Cazelles
    • Laurent Charlin
    • Pierre Chastenay
    • Noémie Chenail
    • Jocelyn Dagenais
    • Marie-France Dallaire
    • Jean-Lou de Carufel
    • Jean-Marie De Koninck
    • Lambert De Monte
    • Jean-Paul Delahaye
    • Marc-André Desautels
    • Florin Diacu
    • Jimmy Dillies
    • Nicolas Doyon
    • Philippe Drobinski
    • Hugo Drouin-Vaillancourt
    • Louis J. Dubé
    • Thierry Duchesne
    • Stéphane Durand
    • Thomas Erneux
    • Philippe Etchécopar
    • Julien Fageot
    • Charles Fleurent
    • Jérôme Fortier
    • Marlène Frigon
    • Jean-François Gagnon
    • André Garon
    • Christian Genest
    • Denis Gilbert
    • Jonathan Godin
    • Frédéric Gourdeau
    • Samuel Goyette
    • Jean Guérin
    • Hervé Guillard
    • Abba B. Gumel
    • James A. Hanley
    • Alain Hertz
    • Bernard R. Hodgson
    • Isabelle Jalliffier-Verne
    • Guillaume Jouvet
    • Tomasz Kaczynski
    • Patrick Labelle
    • Marc Laforest
    • Nadia Lafrenière
    • Josiane Lajoie
    • Alexis Langlois-Rémillard
    • Simon-Olivier Laperrière
    • René Laprise
    • Steffen Lauritzen
    • Denis Lavigne
    • Adrien Lessard
    • Jean Meunier
    • Normand Mousseau
    • Johanna G. Nešlehová
    • Pierre-André Noël
    • Dmitry Novikov
    • Ostap Okhrin
    • Laurent Pelletier
    • Jean-François Plante
    • Serge Provost
    • Annie Claude Prud'Homme
    • Benoît Rittaud
    • Louis-Paul Rivest
    • Serge Robert
    • André Ross
    • Christiane Rousseau
    • Guillaume Roy-Fortin
    • Yvan Saint-Aubin
    • Maria Vittoria Salvetti
    • Vasilisa Shramchenko
    • Robert Smith?
    • Shophika Vaithyanathasarma
    • William Verreault
    • Redouane Zazoun

Sujets

Algèbre Applications Applications des mathématiques Changements climatiques Climat Construction des mathématiques COVID-19 Cristallographie cryptographie GPS Gravité Géométrie Histoire des mathématiques Imagerie Infini Informatique Informatique théorique Jeux mathématiques Logique mathématique Lumière Mathématiques de la planète Terre Mathématiques et architecture mathématiques et art Mathématiques et arts Mathématiques et astronomie Mathématiques et biologie Mathématiques et développement durable Mathématiques et littérature Mathématiques et musique Mathématiques et médecine Mathématiques et physique Mathématiques et transport Modélisation Nombres Portrait d'un mathématicien Portrait d'un physicien Probabilités Probabilités et statistique Racines Rubrique des Paradoxes Section problèmes Théorie des groupes Topologie Éditorial Épidémiologie

© 2022 Accromath