Transformations linéaires

GIF-4105/7105 Photographie Algorithmique, Hiver 2017

Jean-François Lalonde
Merci à D. Hoiem, A. Efros et S. Seitz
Cette semaine

• Aujourd’hui:
• Transformations linéaires globales

• Calculer la transformation à partir d’images

• Appliquer une transformation à une image

• Morphage
Transformations d’image
• filtrage: modifier l'image du signal
g(x) = T (f (x))
f f
T

x x
• transformations: modifier le domaine du signal

g(x) = f (T (x))
f f
T

x x
Transformations d’image
• filtrage: modifier l’image du signal
g(x) = T (f (x))

• transformations: modifier le domaine du signal

g(x) = f (T (x))

T
Transformations globales (paramétriques)
• Transformation T modifie les coordonnées:

p = (x, y) p0 = (x0 , y 0 )
p0 = T (p)
• Qu’est-ce que “globale” veut dire?
• La même chose pour chaque point

• Peut être représentée par un faible nombre de paramètres

(paramétrique)

• Pour les transformations linéaires, on peut représenter la

transformation par une matrice: 0 
0 x x
p = Mp =M
y0 y
Transformations globales (paramétriques)

translation rotation aspect

affine perspective cylindrique

Mise à l’échelle
• Multiplier chaque coordonnée par un scalaire

• Uniforme: le même scalaire pour chaque

coordonnées (ici: x et y)

×2
Mise à l’échelle
• Non-uniforme: différent scalaire par coordonnée

X × 2,
Y × 0.5
Mise à l’échelle

0
• Opération: x = ax
0
y = ay

  
x0 a 0 x
• Matrice: 0 =
y 0 b y

matrice S
Rotation 2D
0 0
(x , y )

0
x = x cos ✓ y sin ✓
(x, y)
0
y = x sin ✓ + y cos ✓

✓
Rotation 2D
0 0
(x , y ) Coordonnées polaires
x = r cos (φ)
y = r sin (φ)
x’ = r cos (φ + θ)
y’ = r sin (φ + θ)
(x, y)
Identité trigonométrique
x’ = r cos(φ) cos(θ) – r sin(φ) sin(θ)
y’ = r sin(φ) cos(θ) + r cos(φ) sin(θ)

Substitution
✓ x’ = x cos(θ) - y sin(θ)
y’ = x sin(θ) + y cos(θ)
Rotation 2D
• Forme matricielle:
  
x0 cos ✓ sin ✓ x
=
y0 sin ✓ cos ✓ y

R
• Même si sin(θ) et cos(θ) sont des fonctions non-linéaires
en θ,
• x’ et y’ sont des combinaisons linéaires de x et y

• Quelle est la transformation inverse?

• Rotation par –θ

• Pour les matrices de rotation:

1
R = RT
Matrices 2x2
• Quelles transformations peuvent être représentées
par des matrices 2x2?

Identité?
0   
x =x x0 1 0 x
=
y =y0 y0 0 1 y

Facteur d’échelle autour de (0,0)?

0  0
 
x = sx x x sx 0 x
=
0
y = sy y y0 0 xy y
Matrices 2x2
• Quelles transformations peuvent être représentées
par des matrices 2x2?

Réflexion en x?
0
  
x = x x0 1 0 x
=
0
y =y y0 0 1 y

Réflexion par rapport à l’origine?

0  0
 
x = x x 1 0 x
=
y0 = y y0 0 1 y
Matrices 2x2
• Quelles transformations peuvent être représentées
par des matrices 2x2?

Rotation?
  
x0 = x cos ✓ y sin ✓ x0 cos ✓ sin ✓ x
=
y 0 = x sin ✓ + y cos ✓ y0 sin ✓ cos ✓ y

Étirement (shear)?

0  0
 
x = x + kx y x 1 kx x
=
0
y = y + ky x y0 ky 1 y
Matrices 2x2
• Quelles transformations peuvent être représentées
par des matrices 2x2?

Translation?
0
x = x + tx
0 NON!
y = y + ty

Seulement les fonctions linéaires en x et y

peuvent être représentées par des matrices 2x2
Transformations linéaires
• Toutes les transformations
linéaires sont des combinaisons
de:  0
 
x a b x
=
• échelle, rotation, étirement, réflexion y0 c d y

• Propriétés
• Origine ne change pas

• Sont préservés:
• Lignes, lignes parallèles, ratios

• Composition est aussi une

transformation linéaire
    
x0 a b e f i j x
=
y0 c d g h k l y
Translations?
• Comment pouvons-nous représenter les
translations sous forme matricielle?

x 0 = x + tx
0
y = y + ty
Coordonnées homogènes
• Représente des coordonnées 2-D avec un vecteur
à 3 éléments
2 3
 Coordonnées homogènes
x
x 4 y 5
y
1

2 3
x 
4 y 5
Point 2D x/w
w
y/w
Coordonnées homogènes
• Propriétés:
2 3 2 3
• Invariance au facteur d’échelle x x
4 y 5 = k4 y 5
• (x, y, 0) représente un point à l’infini w w
• (0, 0, 0) n’est pas permis

Invariance à l’échelle
y

2 (2,1,1) ou (4,2,2) ou (6,3,3)

1

2 x
1
Translations?
• Comment pouvons-nous représenter les
translations sous forme matricielle?
0
x = x + tx
0
y = y + ty

• En utilisant une troisième colonne!

2 0
3 2 32 3
x 1 0 tx x
4 y0 5 = 4 0 1 ty 5 4 y 5
1 0 0 1 1
Exemple de translation
2 3 2 32 3
x0 1 0 tx x
4 y0 5 = 4 0 1 ty 5 4 y 5
1 0 0 1 1

tx = 2
ty = 1
 Transformations 2D en matrices 3x3
2 0
3 2 32 3 2 0
3 2 32 3
x 1 0 tx x x sx 0 0 x
4 y 0 5 = 4 0 1 ty 5 4 y 5 4 y0 5 = 4 0 sy 0 54 y 5
1 0 0 1 1 1 0 0 1 1
Translation Échelle

2 3 2 32 3 2 3 2 32 3
x0 cos ✓ sin ✓ 0 x x0 1 kx 0 x
4 y 0 5 = 4 sin ✓ cos ✓ 0 5 4 y 5 4 y 0 5 = 4 ky 1 0 54 y 5
1 0 0 1 1 1 0 0 1 1
Rotation Étirement
 Composition
• Les transformations peuvent être composées en
multipliant les matrices

2 3 2 32 32 32 3
x0 1 0 tx cos ✓ sin ✓ 0 sx 0 0 x
4 y0 5 = 4 0 1 ty 5 4 sin ✓ cos ✓ 0 54 0 xy 0 54 y 5
w0 0 0 1 0 0 1 0 0 1 w

Est-ce que l’ordre est important?

Démonstration
transformations.m
Transformations affines
• Transformées affines sont des combinaisons de:
• Transformées linéaires; et
2 0
3 2 32 3
• Translations x a b c x
4 y0 5 = 4 d e f 54 y 5
• Propriétés 1 0 0 1 1

• L’origine n’est pas nécessairement préservée

• Sont préservées: les lignes, lignes parallèles, ratios

• Composition est aussi une transformée affine

Transformations projectives
• Transformées affines sont des combinaisons de:
• Transformées affines; et
2 0
3 2 32 3
• Projections x a b c x
4 y0 5 = 4 d e f 54 y 5
• Propriétés 1 g h i 1
• L’origine n’est pas nécessairement préservée

• Sont préservées: les lignes, lignes parallèles, ratios

• Composition est aussi une transformée affine

• Définies jusqu’à un facteur d’échelle (8 DDL)

Transformations en 2D

Composition et inverse font aussi parties du groupe

Estimer les transformations

?
T(x,y)
y y’
x x’
f(x,y) g(x’,y’)

• Admettons que nous connaissons deux images (f et g).

Comment faire pour estimer leur transformation?

• Demandons à un utilisateur de nous donner des

correspondences
• Combien en avons-nous besoin?
Translation

?
T(x,y)
y y’
x x’

• Combien de degrés de liberté (DDL)?

• Combien de correspondences?
Rigide (translation + rotation)

?
T(x,y)
y y’
x x’

• Combien de degrés de liberté (DDL)?

• Combien de correspondences?
Affine

?
T(x,y)
y y’
x x’

• Combien de degrés de liberté (DDL)?

• Combien de correspondences?
Projective

?
T(x,y)
y y’
x x’

• Combien de degrés de liberté (DDL)?

• Combien de correspondences?
Questions
• Supposons que nous avons deux triangles:
• ABC et A’B’C’

• Quelle est la transformation qui passe de ABC vers A’B’C’?

• Comment pouvons-nous estimer ses paramètres?

B B’

T C’
A C A’
Source Destination
Estimation de paramètres

y2

y = ax + b

y1

x1 x2
Démonstration
lls.m
 Estimation de paramètres

(xB , yB ) (x0B , yB
0
)

T
(x0C , yC
0
)
(xA , yA ) (xC , yC ) (x0A , yA
0
)

Source Destination
2 3
a b c
T =4 d e f 5
0 0 1
Déformation d’image

T(x,y)
y y’
x x’
f(x,y) g(x’,y’)

• Étant données une image f et une transformation T,

comment calculer l’image déformée g?
Idée 1: transformée directe

T(x,y)
y y’
x x’
f(x,y) g(x’,y’)

• Pour chaque pixel dans f

• Calculer sa nouvelle position, et “copier-coller” sa
couleur
Idée 1: transformée directe
Quel est le problème avec cette approche?

T(x,y)
y y’
x x’
f(x,y) g(x’,y’)

Q: Qu’est-ce qu’on fait si un pixel arrive “entre” deux pixels?

R: distribuer sa couleur sur les pixels avoisinants

(comme si on “aplatissait” la couleur)
Idée 2: transformée inverse

T-1(x,y)
y y’
x x’
f(x,y) g(x’,y’)

• Pour chaque pixel dans g

• Calculer d’où il vient grâce à l’inverse de T

Idée 2: transformée inverse

T-1(x,y)
y y’
x x’
f(x,y) g(x’,y’)

Q: qu’est-ce qu’on fait si un pixel provient “d’entre deux pixels”?

R: Interpolation!
plus proche voisin, bi-linéaire, bi-cubique, etc.
interp2 dans Matlab
Interpolation bilinéaire

[Link]
Déformation directe vs inverse

• Laquelle est la meilleure?

• Habituellement, c’est la transformée inverse

• Garantit qu’on ne génère pas de trou

• Cependant, il faut que notre transformation puisse être

inversée!