Traitement de l’image et du signalPartie TI
Emanuel Aldea <[email protected]>http://hebergement.u-psud.fr/emi/453
Master Electronique, energie electrique, automatique 1ere annee
Necessite de l’invariance en TI
Les contours◮ traitement relativement peu couteux
◮ detection robuste de courbes parametriques (Hough)
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (2/41)
Necessite de l’invariance en TI
Les contours◮ traitement relativement peu couteux
◮ detection robuste de courbes parametriques (Hough)
◮ applications variees dans des environnements specifiques :◮ detection de la route, des panneaux, du texte◮ imagerie medicale et satellitaire◮ inspection par vision industrielle
Image aerienne Detection de voies Vision industrielle
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (2/41)
Necessite de l’invariance en TI
Les contours◮ traitement relativement peu couteux
◮ detection robuste de courbes parametriques (Hough)
◮ applications variees dans des environnements specifiques :◮ detection de la route, des panneaux, du texte◮ imagerie medicale et satellitaire◮ inspection par vision industrielle
✦ taches rapides et specialisees
✦ invariants aux variations d’intensite
✪ sensibles aux autres transformations geometriques
✪ probleme pour la reconnaissance de formes
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (2/41)
Motivation - images panoramiques
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (3/41)
Motivation - images panoramiques
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (4/41)
Motivation - images panoramiques
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (5/41)
Le probleme
◮ translation
◮ Euclidienne (translation + rotation)
◮ similarite (tr. + rot. + echelle)
◮ affine (rot. + echelle + shear + translation)
◮ projective
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (6/41)
Necessite de l’invariance en TI
Objectif
◮ identifier des structures qui sont invariantes par rapport aux rotations,changements d’echelle, etc.
◮ ces structures sont appelees couramment points d’interet ou coins
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (7/41)
Necessite de l’invariance en TI
Objectif
◮ identifier des structures qui sont invariantes par rapport aux rotations,changements d’echelle, etc.
◮ ces structures sont appelees couramment points d’interet ou coins
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (7/41)
Necessite de l’invariance en TI
Objectif
◮ identifier des structures qui sont invariantes par rapport aux rotations,changements d’echelle, etc.
◮ ces structures sont appelees couramment points d’interet ou coins
Comment faire pour :
◮ les identifier de maniere non supervisee ?
◮ les associer de maniere robuste ?
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (7/41)
Detecteurs de coins : les bases
DefinitionCoin : un endroit de l’image qui presente une forte variation d’intensite en deuxdirections differentes.
•
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (8/41)
Detecteurs de coins : les bases
DefinitionCoin : un endroit de l’image qui presente une forte variation d’intensite en deuxdirections differentes.
•
Toujours besoin de calculer les gradients locaux, mais
◮ pas suffisant de faire comme auparavant (dans le repere image) !
•
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (8/41)
Detecteurs de coins : les bases
DefinitionStrategie : le contenu d’un patch centre dans le coin devrait varier dans toutes lesdirections
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (9/41)
Detecteurs de coins : les bases
DefinitionStrategie : le contenu d’un patch centre dans le coin devrait varier dans toutes lesdirections
Comportement :
◮ regions homogenes : pas de changement
◮ contours : pas de changement le long du contour
◮ coins : changement important dans toutes les directions
◮ qualite du pixel : le plus petit changement
◮ introduit par Moravec en 1980
◮ pas isotrope : certains contours mal detectes, fausse reponse coin
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (9/41)
Detecteurs de coins : les bases
Changement d’intensite par shift de (∆x ,∆y)
E (x , y ,∆x ,∆y) =∑
x
∑
y
w(x , y)[I (x , y)− I (x +∆x , y +∆y)
]2
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (10/41)
Detecteurs de coins : les bases
Changement d’intensite par shift de (∆x ,∆y)
E (x , y ,∆x ,∆y) =∑
x
∑
y
w(x , y)[I (x , y)︸ ︷︷ ︸
intensite
−I (x +∆x , y +∆y)]2
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (10/41)
Detecteurs de coins : les bases
Changement d’intensite par shift de (∆x ,∆y)
E (x , y ,∆x ,∆y) =∑
x
∑
y
w(x , y)[I (x , y)︸ ︷︷ ︸
intensite
− I (x +∆x , y +∆y)︸ ︷︷ ︸
intensite shiftee
]2
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (10/41)
Detecteurs de coins : les bases
Changement d’intensite par shift de (∆x ,∆y)
E (x , y ,∆x ,∆y) =∑
x
∑
y
w(x , y)︸ ︷︷ ︸
support
[I (x , y)︸ ︷︷ ︸
intensite
− I (x +∆x , y +∆y)︸ ︷︷ ︸
intensite shiftee
]2
Figure – Types de fonction support w(x , y)
E (x , y) large indique potentiellement un coin.
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (10/41)
Detecteurs de coins : les bases
Approximation au premier ordre du dev. en serie Taylor
f (x +∆x , y +∆y) = f (x , y) + fx(x , y)∆x + fy (x , y)∆y
On l’utilise pour reecrire la variation d’intensite par shift :
∑[I (x +∆x , y +∆y)− I (x , y)
]2≈
∑[I (x , y) + ∆xIx(x , y) + ∆yIy (x , y)− I (x , y)
]2
≈∑
∆x2I2x + 2∆x∆yIx Iy +∆y
2I2y
≈∑
[∆x∆y ]
[I 2x Ix IyIx Iy I 2y
] [∆x
∆y
]
≈ [∆x∆y ]
(∑
[I 2x Ix IyIx Iy I 2y
])[∆x
∆y
]
E(x , y ,∆x ,∆y) ≈ [∆x∆y ]
(∑
w(x , y)
[I 2x Ix IyIx Iy I 2y
])[∆x
∆y
]
≈ [∆x∆y ]
[〈I 2x 〉 〈Ix Iy 〉〈Ix Iy 〉 〈I 2y 〉
]
︸ ︷︷ ︸
tenseur de structure
[∆x
∆y
]
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (11/41)
Detecteurs de coins : le tenseur de structure
Proprietes
◮ les vecteurs propres indiquent les direction principales de variation de gradientdans le voisinage du point (voir l’ellipse du changement constant)
◮ ex. : si λ2 > λ1, variation forte en v2 et plus faible en v1
◮ si coin, λ1, λ2 sont larges
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (12/41)
Detecteurs de coins : le tenseur de structure
Proprietes
◮ les vecteurs propres indiquent les direction principales de variation de gradientdans le voisinage du point (voir l’ellipse du changement constant)
◮ ex. : si λ2 > λ1, variation forte en v2 et plus faible en v1
◮ si coin, λ1, λ2 sont larges
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (12/41)
Detecteurs de coins : le tenseur de structure
Proprietes
◮ les vecteurs propres indiquent les direction principales de variation de gradientdans le voisinage du point (voir l’ellipse du changement constant)
◮ ex. : si λ2 > λ1, variation forte en v2 et plus faible en v1
◮ si coin, λ1, λ2 sont larges
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (12/41)
Detecteurs de coins : decision
Decision en fonction des valeurs propres du tenseur
◮ on peut calculer λ1, λ2 explicitement mais trop lourd
◮ methode preferee :
R = det(M)− αtrace2(M) = λ1λ2 − α(λ1 + λ2)2
◮ valeur du parametre α en general 0.04 - 0.06
◮ valeurs propres interessantes = maximum local de R
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (13/41)
Detecteurs de coins : rappel
Etapes de l’algorithme
1. calcul des gradients Ix = ∂
∂xg(σD) ⋆ I , Iy = ∂
∂yg(σD) ⋆ I
2. calcul du tenseur de structure :
M = g(σI ) ⋆
[ ∑I 2x
∑Ix Iy∑
Ix Iy∑
I 2y
]
3. calcul de la fonction de reponse R :
R = det(M)− αtrace2(M)
4. seuillage de R
5. suppression de valeurs non maximales de R
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (14/41)
Detecteurs de coins : exemple
Figure – Paire initiale
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (15/41)
Detecteurs de coins : exemple
Figure – Fonction de reponse R
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (16/41)
Detecteurs de coins : exemple
Figure – Seuillage de RE. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (17/41)
Detecteurs de coins : exemple
Figure – Suppression non maximale de RE. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (18/41)
Detecteurs de coins : exemple
Figure – Resultat detectionE. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (19/41)
Detecteur de Harris
Conclusions✦ detection invariante a la rotation
✦ detection invariante aux changements d’intensite
✪ pas robuste au changement d’echelle
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (20/41)
L’echelle caracteristique
Rappel du cours precedent :
Filtrage Gaussien + Laplace (LoG) - passage en 0
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (21/41)
L’echelle caracteristique
La reponse au Laplacien - maximale si l’echelle du Laplacien correspond a l’echellede la variation dans l’espace image
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (22/41)
L’echelle caracteristique
Si on varie σ, la reponse du Laplacien diminue ; il faut normaliser le resultat parune multiplication avec σ2
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (23/41)
L’echelle caracteristique
Figure – Reponse multi echelle normalisee du Laplacien
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (24/41)
La representation pyramidale
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (25/41)
Approximation du Laplacien
Laplacien :L = σ2(Gxx(x , y , σ) + Gyy (x , y , σ))
Difference de Gaussiennes :
DoG = G (x , y , kσ)− G (x , y , σ)
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (26/41)
Le detecteur SIFT
Scale Invariant Feature Transform◮ tres performant
◮ tres couteux
◮ descripteur integre
1. Construction de l’espace d’echelle
2. Calcul des DoGs
3. Calcul de l’echelle caracteristique
4. Localisation sous-pixel
5. Elimination des reponses des contours
6. Calcul de l’orientation
7. Calcul du descripteur
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (27/41)
La representation pyramidale
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (28/41)
Le detecteur SIFT
1. Construction de l’espace d’echelle
2. Calcul des DoGs
3. Calcul de l’echelle caracteristique
4. Localisation sous-pixel
5. Elimination des reponses des contours
6. Calcul de l’orientation
7. Calcul du descripteur
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (29/41)
Calcul des DoGs
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (30/41)
Le detecteur SIFT
1. Construction de l’espace d’echelle
2. Calcul des DoGs
3. Calcul de l’echelle caracteristique
4. Localisation sous-pixel
5. Elimination des reponses des contours
6. Calcul de l’orientation
7. Calcul du descripteur
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (31/41)
Determination des points extremes
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (32/41)
Le detecteur SIFT
1. Construction de l’espace d’echelle
2. Calcul des DoGs
3. Calcul de l’echelle caracteristique
4. Localisation sous-pixel
5. Elimination des reponses des contours
6. Calcul de l’orientation
7. Calcul du descripteur
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (33/41)
Localisation sous pixel
Interpolation des mesures discretes de D(x , y , σ). Utilisation du dev. Taylor dedeuxieme ordre :
D(x) = D +∂D
∂x
T
x+1
2xT
∂2D
∂x2x
Solution :
x = −
∂2D
∂x2
−1∂D
∂x
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (34/41)
Le detecteur SIFT
1. Construction de l’espace d’echelle
2. Calcul des DoGs
3. Calcul de l’echelle caracteristique
4. Localisation sous-pixel
5. Elimination des reponses des contours
6. Calcul de l’orientation
7. Calcul du descripteur
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (35/41)
Calcul de l’orientation
1. Calcul des gradients locaux a l’echelle caracteristique
2. Calcul de l’histogramme de gradients locaux
3. L’orientation canonique est la direction maximale
4. Chaque coin est caracterise par : localisation, echelle, orientation
5. systeme de coordonnees local pour construire un descripteur
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (36/41)
Le detecteur SIFT
1. Construction de l’espace d’echelle
2. Calcul des DoGs
3. Calcul de l’echelle caracteristique
4. Localisation sous-pixel
5. Elimination des reponses des contours
6. Calcul de l’orientation
7. Calcul du descripteur
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (37/41)
Calcul du descripteur
1. Orientations locales du gradients en 16 regions voisines
2. Systeme de coordonnees relatif au coin
3. 4*4*8 orientations = 128 (dimension descripteur)
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (38/41)
Conclusion SIFT
◮ Invariant echelle
◮ Invariant rotation
◮ Invariant illumination
◮ Invariant perspective
◮ Couteux
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (39/41)
Le detecteur FAST
Features from Accelerated Segment Test
◮ extremement rapide
◮ pas d’operations complexes (convolution, calcul de gradients etc.)
◮ peu robuste
◮ pas de descripteur
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (40/41)
Le detecteur FAST - strategie
E. Aldea (M1-E3A) T. image et signal Chap II : Points d’interet (41/41)