OPERATIONS GEOMETRIQUES 2D

1

Les opérations géométriques ont pour but de modifier la position des informations contenues dans l'image sans modifier le niveau de gris. Ces opérations peuvent s'appliquer à la totalité des points d'une image (les pixels), un objet particulier de l'image, voire à certains points spécifiques (recalage de points caractéristiques).

Fig 1 - Recalage géométrique d'une image

Ces opérations présentent un intérêt dans de nombreuses applications: - correction des distorsions géométriques liées au matériel optique. La distorsion la plus fréquente est celle introduite par l'objectif lui-même (effet de "tonneau" ou de "barillet"). - correction de la perspective d'une scène 3D projetée sur un capteur 2D. Pour envisager des mesures précises des objets présents dans la scène, il peut être utile de restituer une image corrigée par une opération géométrique adaptée. - compensation du mouvement de la caméra pour un système embarqué pour ramener l'image dans un repère de représentation fixe. - mise en correspondance d'images prises dans des conditions différentes (prises de vue satellitaires, radiographie, tomographie). Si l'objectif est de comparer l'évolution des images entre deux vues prises à des intervalles très éloignés (un an par exemple). Les conditions ne seront jamais les mêmes; la première étape sera donc un recalage géométrique de la nouvelle vue sur la première prise comme référence, pour une stricte mise en correspondance des deux vues. L'objet de cette présentation des opérations géométriques est de donner des outils de base 2D.La même approche est souvent utilisée en robotique mobile lorsque la caméra est embarquée sur le robot. Notion d'opération géométrique Les opérations géométriques de base sont la translation, la rotation, l'homothétie ou la symétrie. Pour chacune de ces opérations, on peut considérer que l'opération est une transformation de coordonnées. Soient X =  x , y  les coordonnées. anciennes coordonnées et X ' =  x ' , y '  les nouvelles

Une opération géométrique  est une correspondance fonctionnelle entre les anciennes et les nouvelles coordonnées :  x ' , y '  =  x , y  L'opération  peut présenter des propriétés spécifiques telles que: - la linéarité par rapport à  x , y  ou la loi affine - l'inversibilité (possibilité de retrouver  x , y  à partir de  x ' , y '  )

P. BONNET

Cours de Traitement d'Image

USTL

OPERATIONS GEOMETRIQUES 2D

2

Opérations géométriques élémentaires Les opérations de base permettent de réaliser des transformations géométriques simples. Elles visibles lorsqu'elles affectent une structure spécifique (élément carré, maillage) Les principales opérations ont les formes suivantes(remarquer que leur expression est une fonction affine des variables x et y):
Translation

{
{

x' = x Tx y' = y  T y

Rotation autour de l'origine

x ' = cos  x − sin  y y ' = sin  x  cos  y

Homothétie/ changement d'échelle/dilatation

{

x ' = Sx x y' = S y y

Notes: S x = −1,S y = −1  donne une symétrie centrale par rapport à l'origine, S x = −1, S y = 1  une symétrie .axiale par rapport à Ox et S x = 1, S y = −1  une symétrie axiale par rapport à Oy Relèvement /cisaillement vertical

{

x' = x y' =  x  y

Cisaillement double /transvection

{

x' = x  y y' =  x  y

 Le point O a la propriété d'être invariant (O' est confondu avec O).  Une droite reste une droite dans la transformation affine. Cette propriété permet de mettre en évidence l'opération affine par un ensemble de droite dans l'espace d'origine et celui d'arrivée.  L'opération affine n'est pas une transformation conforme (les angles ne sont pas conservés).

P. BONNET

Cours de Traitement d'Image

USTL

OPERATIONS GEOMETRIQUES 2D

3

Calcul homogène Les matrices homogènes permettent de décrire toutes les opérations géométriques affine par rapport aux variables x et y .Le principe est d'introduire une troisième dimension fictive pour prendre en compte la translation. La forme générale d'une transformation géométrique affine en matrice homogène est :

 
Translation Rotation d'angle 

a b Tx x x' y' = c d T y y 1 0 0 1 1

 
Cisaillement Vertical Cisaillement

Cette représentation est utile pour comprendre la décomposition d'une opération géométrique. Par contre, il sera inutile de programmer une transformation homogène sous forme matricielle (la dernière ligne de calcul étant vérifiée systématiquement, le calcul effectif se réduit au calcul des lignes x' et y' !). Cette représentation permet de décrire les opérations de base:
Homothétie de rapport S x , S y 

T

R cos  −sin  0 sin  cos  0 0 0 1

S

Cy 1 0 0  1 0 0 0 1

C 1  0  1 0 0 0 1

  
1 0 Tx 0 1 Ty 0 0 1

 

Sx 0 0 0 Sy 0 0 0 1

    

Le calcul homogène définit une algèbre de calcul pour les opérations géométriques: 1 0 0 - élément neutre 0 1 0 (matrice identité) 0 0 1 - inverse d'une opération géométrique: l'opération inverse d'une opération géométrique est caractérisée par la matrice homogène inverse de l'opération directe. Exemple de la rotation:

 



cos  −sin  0 sin  cos  0 0 0 1
−1

 
−1

cos − −sin− 0 = sin − cos − 0 soit une rotation d'angle − 0 0 1



Exemple de l'homothétie:



Sx 0 0 0 Sy 0 0 0 1

 

1 /S x 0 0 = 0 1 /S y 0 soit une homothétie de rapport inverse. 0 0 1



- cascade d'opération: la cascade d'opération successives se traduit par un simple produit matriciel (attention, l'ordre des opérations successives intervient comme dans le produit matriciel).

P. BONNET

Cours de Traitement d'Image

USTL

OPERATIONS GEOMETRIQUES 2D

4

Exemple: cascade d'une translation T x1 , T y1  suivie d'une translation T x2 , T y2  1 0 T x2 1 0 T x1 1 0 T x1T x2 T 1 o T 2 = 0 1 T y2 . 0 1 T y1 = 0 1 T y1T y2 0 0 1 0 0 1 0 0 1

   



soit la somme des vecteurs de translation

Cette algèbre de calcul permet de combiner une suite de plusieurs opération qui seront réalisées en une seule application sur l'image. Exemple: Rotation  suivie d'une Translation T x , T y  cos  −sin  T x 1 0 T x cos  −sin  0 R o T = 0 1 T y . sin  cos  0 = sin  cos  T y 0 0 1 0 0 1 0 0 1 Bien remarquer le caractère non-commutatif des deux opérations: cos  −sin  T x cos −T y sin  cos  −sin  0 1 0 T x1 T o R = sin  cos  0 . 0 1 T y1 = sin  cos  T x sin T y cos  0 0 1 0 0 1 0 0 1

 


 








Dans cette deuxième écriture (translation puis rotation), on remarque que la rotation a été appliquée à la translation, d'où le nouveau vecteur de translation de l'opération globale. Centre quelconque Les opérations de base définies précédemment ont pour centre l'origine du repère (point O). De façon générale, le centre C x ,C y  peut être choisi de manière arbitraire. L'opération se décompose en trois temps: - translation du centre sur l'origine (le vecteur de translation est l'inverse des coordonnées du centre de l'opération) - exécution de l'opération demandée (rotation, cisaillement...) - translation de l'origine vers le centre de l'opération (translation inverse)

Fig 2 - Etape de la rotation de centre quelconque P. BONNET Cours de Traitement d'Image USTL

OPERATIONS GEOMETRIQUES 2D

5

L'écriture en matrice homogène montre les étapes:

 
Théorème

1 0 −T x cos  −sin  0 1 0 T x x' y ' = 0 1 −T y sin  cos  0 0 1 T y 1 0 0 1 0 0 1 0 0 1



  

x T x = −C x y avec T y = −C y 1

Ou encore : X ' = T −1 . R . T  X Selon les règles matricielles, il est évident que la deuxième translation n'annule pas la première (produit matriciel non commutatif).

Cette algèbre permet d'affirmer le théorème suivant : Toute opération géométrique affine par rapport aux paramètres  x , y  est décomposable en une suite d'opérations élémentaires de type translation, rotation, cisaillement et homothétie (cette décomposition n'est pas unique). Cette propriété est très utile pour analyser la déformation d'une image et ainsi mettre en évidence les fonctionnalités de base (rotation, homothétie...) L'opération affine étant définie par les 6 paramètres a , b , c , d , T x , T y  , il suffit de connaître 3 points de l'espace transformé pour définir complètement les paramètres. Opérations non-linéaires Les opérations non-linéaires sont caractérisées par des fonctions de calcul de  x ' , y '  =  x , y non-linéaires, comme par exemple des termes polynomiaux xy , x 2 ou y 2 .  transformation bilinéaire dite "perspective" Un terme dit bilinéaire est un terme de la forme xy . L'opération géométrique induite est une forme particulière de perspective (utilisée dans de nombreux logiciels de retouche photo)

{

x' = x y ' =  xy  y

{

x' = x y ' =  xy  y   x

Fig 3 - Transformations bilinéaires de perspective

On remarque que la deuxième perspective est la cascade d'un cisaillement et d'une perspective simple

{
.
P. BONNET

x ' = x   y   xy y ' = y   x   xy

Fig 4 – Perspective complète sans translation

Cours de Traitement d'Image

USTL

OPERATIONS GEOMETRIQUES 2D

6

 transformation bilinéaire générale L'expression de la transformation bilinéaire générale est : La transformation géométrique est la suivante :
Influence des coefficients: - a 1 et a 6 définissent le rapport homothétique - a 2 et a 5 définissent le relèvement et l'inclinaison - a 3 et a 7 définissent la perspective - a 4 et a 8 définissent la translation générale (nulle sur cet exemple). Fig 5 - Transformation bilinéaire complète

{

x ' = a 1 x  a 2 y  a3 xy  a 4 y ' = a5 x  a 6 y  a 7 xy  a 8

On remarque que les 8 paramètres scalaires de la transformation peuvent être fixés par les 4 points de contrôle O',A',B',C' (deux coordonnées par point soit 8 équations pour 8 coefficients). Attention : l'inverse d'une transformation bilinéaire (correction d'une perspective par exemple) n'est pas une transformation bilinéaire !
 transformation non-linéaire

Dans le cas le plus général, la transformation géométrique peut utiliser des termes polynomiaux en x , y 2 , x 3 , y 3 voire des termes du genre sin  x ou sin  y .
2

Exemple d'une distorsion géométrique Les objectifs de prise de vue induisent fréquemment des distorsions à caractère isotrope depuis l'axe optique, comme celle introduite par un objectif grand angle. Ces distorsions sont liées à la distance  =  x 2  y 2 entre le point de l'image et l'axe optique. La correction de cette aberration géométrique utilise la transformation inverse de la distorsion.

Fig 6 - Modèle de la distorsion en barillet - exemple de modèle de la distorsion en barillet:   =  3 x  = x  d'où ⇒  x =  x 2 soit

{

x ' = x   x 2 y ' = y   y 2

{

x ' = x   x 3  x y 2  y ' = y   x 2 y  y 3
Cours de Traitement d'Image USTL

P. BONNET

OPERATIONS GEOMETRIQUES 2D

7

L'opération fait bien appel à des expressions polynomiales en  x , y  .

Fig 7 - Distorsion géométrique en barillet et coussinet d'une grille

Pour corriger une distorsion en barillet, une correction en coussinet de coefficient  adapté permet d'approcher la fonction inverse de la distorsion en coussinet. Correction géométrique d'une image Les opérations non-linéaires permettent de corriger de nombreuses situation de déformation géométrique d'une image. Pour définir les coefficients, il faut fixer un certain nombre de points de contrôles . Les points de contrôle sont des points caractéristiques de l'image source pour lesquels la position dans l'image redressée est connue. Soit C(x,y) un point de contrôle dont l'image est C'(x',y') dans l'image distordue (en supposant que la correction est le passage des coordonnées (x',y') vers (x,y)). Chaque point de contrôle fournit deux équations:

{

x C =  x  xC ' , yC '  yC =  y  xC ' , yC ' 

Pour déterminer les paramètres d'une correction géométrique, le nombre de points de contrôle indépendants doit être égal à la moitié du nombre de paramètres à déterminer (si le nombre de paramètres est impairs, il suffit d'ignorer l'une des équations). Attention: en raison des symétries éventuelles, certains points sont dépendants (par exemple, les 4 sommets de la distorsion en barillet sont symétriques et donneraient 4 systèmes d'équations dépendantes). De même, les points invariants d'une transformation géométrique ne peuvent pas servir de point de contrôle. La correction est déterminée par la résolution du système d'équations. Si la position imposée par les points de contrôles est impossible à obtenir par la transformation géométrique utilisée, on pourra adopter une solution optimale au sens des moindres-carrés.  Exemple de la perspective complète :

{

x = a1 x '  a2 y '  a3 x ' y ' y = a4 y '  a5 x '  a6 x ' y '

Fig 8 – Correction d'une perspective par une transformation bilinéaire (valable pour une faible perspective)

Les points de contrôle peuvent être les 3 sommets du quadrilatère (A'B'C')
P. BONNET Cours de Traitement d'Image USTL

OPERATIONS GEOMETRIQUES 2D

8

Pour ces points de contrôle, le résultat de la correction géométrique  est connu :

{

x A = x  x A ' , y A '  y A =  y  x A' , y A' 

{

xB = x  x B ' , y B '  yB =  y  xB' , yB ' 

{

xC =  x  xC ' , y C '  yC =  y  xC ' , yC ' 

On dispose de 6 équations pour 6 inconnues dans la description de la transformation. Il suffit donc de résoudre le système d'équations pour obtenir les 6 coefficients. L'écriture matricielle permet de résoudre très facilement le système :

  xA yA xB = yB xC yC

xA ' 0 xB ' 0 xC ' 0

y A' 0 y B' 0 yC ' 0

x A' yA' 0 x B' yB' 0 xC ' yC ' 0

0 x A' 0 xB ' 0 xC '

0 yA ' 0 yB ' 0 yC '

0 a1 x A ' y A' a 2 0 . a3 x B ' y B' a 4 0 a5 xC ' yC ' a6

 

soit X = H 

La solution est :  = H −1 . X L'ajout de points de contrôle supplémentaires permet d'améliorer la précision de détermination des coefficients de la correction géométrique.

Fig 9- Recalage géométrique d'une image

Pour chaque point supplémentaire, le vecteur X augmente de 2 lignes ainsi que la matrice H qui devient rectangulaire. Le système comporte donc plus d'équations que d'inconnues. Sa résolution pourra faire appel à la méthode des moindres-carrés qui minimise le critère quadratique J =  X − H  X − H T (voir cours M1 ASE de Modélisation/Identification)  La solution optimale est :  =  H T H −1 H T X

P. BONNET

Cours de Traitement d'Image

USTL

OPERATIONS GEOMETRIQUES 2D

9

Correction exacte d'une perspective Lorsque des objets plans se projettent sur un capteur, les images observées depuis différents points de vue (droit ou oblique) sont liées par une transformation projective appelée Homographie de la T T forme : P ' = H P avec P et P' points en correspondance de coordonnées  x , y , z  et  x ' , y ' , z '  (la dimension z' est fixée à 1pour l'image plane) L'Homographie H est caractérisée par une matrice homogène 3x3 . Cette transformation induit un facteur d'échelle et ne comporte que 8 coefficients indépendants ( h 33=1 ) Pour rectifier une image, il faut déterminer les 8 coefficients de la transformation H qui amène les points de l'image source plane à une position de référence. Les points sont liées par : x' = h 11 x  h12 y  h13 h 31 x  h32 y  h33 et y' = h21 x  h22 y  h 23 h 31 x  h32 y  h 33

Avec 4 points P(x,y) de l'image source assignés à des positions P'(x',y') de référence, on dispose de 8 équations avec 8 inconnues. Le système se met sous la forme suivante : x ' h31 x  h32 y  h33  = h 11 x  h12 y  h 13 y ' h31 x  h32 y  h33  = h 21 x  h 22 y  h23 Avec 4 points de contrôle , on obtient le système suivant :



x0 x0 x0 x0 0 0 0 0

y0 y0 y0 y0 0 0 0 0

1 1 1 1 0 0 0 0

0 0 0 0 x0 x0 x0 x0

0 0 0 0 y0 y0 y0 y0

0 0 0 0 1 1 1 1

−x 0 x ' 0 −x 1 x ' 1 −x 2 x ' 2 −x 3 x ' 3 −x 0 y ' 0 −x1 y ' 1 −x 2 y ' 2 −x3 y ' 3

− y0 x ' 0 h11 x '0 −y 1 x ' 1 h12 x '1 − y2 x ' 2 h13 x '2 −y 3 x ' 3 h x '3 × 21 = − y0 y ' 0 h22 y'0 − y1 y ' 1 h23 y'1 −y 2 y ' 2 h31 y'2 − y3 y ' 3 h32 y'3

   
USTL

La résolution de ce système linéaire permet de déterminer la matrice homographique de redressement de la perspective.

fig 10 Correction de la perspective par la transformation homographique (d'après L; Jagannathan)

P. BONNET

Cours de Traitement d'Image

OPERATIONS GEOMETRIQUES 2D

10

Interpolation des niveaux de gris La mise en oeuvre des opérations géométriques sur les images discrètes demande une algorithmique spécifique. En effet, l'idée de "construire" la nouvelle image à partir du balayage de l'original ne permet pas d'obtenir une image correcte. En effet, la transformation des coordonnées d'origines discrètes (donc entières) peut donner des valeurs non-entières dans le résultat du calcul  x A' , y A '  =  x A , y A  La position d'un tel point est donc hors de la maille d'échantillonnage (fig 10).

fig 10 - Transformation géométrique d'une image discrète

La solution d'affecter le résultat au pixel le plus proche par exemple ne résout pas le problème de la construction de l'image résultat; certains pixels seraient affectés de deux valeurs différentes, d'autres d'aucune valeur. La méthode est de balayer les points de l'image résultat, dont les coordonnées sont dans la maille d'échantillonnage du résultat et à rechercher le niveau de gris équivalent du point source (fig 11). A noter que la maille d'échantillonnage du résultat pourra être différente de celle de l'image d'origine dans le cas d'un ré-échantillonnage (resampling en maille carrée, rectangulaire, hexagonale...)

fig 11 - Algorithme de construction de l'image transformée

L'opération géométrique permettant de repasser des nouvelles coordonnées aux anciennes −1 est l'inverse de l'opération directe de la forme  x A , y A =   x A ' , y A'  soit :

{

x A = −1  x A ' , y A '  x −1 y A =  y  xA ' , yA' 

Pour les opérations linéaires, il suffit de prendre la matrice inverse de l'opération. Les opérations bilinéaires sont inversibles aussi . Dans le cas général, la transformation inverse, si elle n'existe pas, pourra être approchée par un développement polynomial si nécessaire.
P. BONNET Cours de Traitement d'Image USTL

OPERATIONS GEOMETRIQUES 2D

11

Plusieurs méthodes sont proposées pour interpoler la valeur du niveau de gris de A.  Interpolation du plus proche voisin C'est l'algorithme le plus simple, rapide à calculer. La fonction mise en oeuvre est celle de l'arrondi (round, floor ou ceil ). L'algorithme est donc (indiçage des images et bornes à modifier selon le langage) : for x = 1 à Xmax for y = 1 à Ymax x1 = round ( phi1_x ( x , y )) x1 = round ( phi1_y ( x , y )) if (x1>=1 & y1>=1 & x1