View
4
Download
0
Category
Preview:
Citation preview
IUP M2-ICM
Université Paul Sabatier Toulouse
Métrologie et reconnaissance des formes
Frédéric Lerasle Année 2008-09
Sommaire
- Généralités -• Démarche générique en TI :
• mise en œuvre et acquisition des images
• prétraitement les images
• segmentation des régions pertinentes dans l’image
• extraction des caractéristiques ou descripteurs de ces régions – éventuellement prétraiter ces données
• interprétation : (1) classer pour associer des symboles, (2) vérifier la conformité (mesures, présence,…)
Sommaire
• Métrologie 3D (3h)
• Métrologie 2D (1h)
• Reconnaissance des formes (3h)
• Exercices (1h)
Métrologie 3D
1
• Modèle mince
• Modèle sténopé
- Rappels -
• approximation du modèle épais i.e plans principaux confondus
• appelé « pin-hole » car tous les rayons passent par le centre optique
• un seul rayon conservé
• projection perspective :
⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
=
=
=
fzZYfy
ZXfx
.
.
Métrologie 3D
2
- Modélisation de la caméra -
• la projection perspective ⇒ relation point espace 3D / point image 2D• la transformation repère caméra / repère image -unité : le pixel
• But : relation mathématique entre coordonnées 3D (monde) / 2D (image)• Modèle sténopé
• Deux transformations :
Métrologie 3D
3
- Modélisation de la caméra -• Projection perspective - en coordonnées homogènes* :
• Transformation caméra/image - exprimée en pixel :
• Paramètres intrinsèques - estimés par calibrage
• Paramètres extrinsèques - transformation mire/caméra -estimés par calibrage
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
⎟⎟⎟
⎠
⎞
⎜⎜⎜
⎝
⎛=
⎟⎟⎟
⎠
⎞
⎜⎜⎜
⎝
⎛
1
.0100000000
'.'
c
c
c
ZYX
ff
sys
sx
⎩⎨⎧
+=+=
0v
0
'.k '.
vyvuxku u
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
⎟⎟⎟
⎠
⎞
⎜⎜⎜
⎝
⎛=
⎟⎟⎟
⎠
⎞
⎜⎜⎜
⎝
⎛
==
1
.01000000
.
.
:. ,.
0
0
vu
c
c
c
v
u
vu
ZYX
vu
svsus
fkfkAvec
αα
αα
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
⎟⎟⎠
⎞⎜⎜⎝
⎛=
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
1
.10
1m
m
m
c
c
c
ZYX
TRZYX
Métrologie 3D
4
- Modélisation de la caméra -• Transformation mire/image - matrice M de projection perspective (taille 3x4)
⇒ 12 paramètres à estimer• Principe du calibrage
⎪⎪⎩
⎪⎪⎨
⎧
++++++
=
++++++
=
⎟⎟⎟
⎠
⎞
⎜⎜⎜
⎝
⎛=
34333231
24232221
34333231
14131211
34333231
24232221
14131211
...
...
...
...
:
mZmYmXmmZmYmXm
v
mZmYmXmmZmYmXm
uquetel
mmmmmmmmmmmm
M
iii
iiii
iii
iiii
• utilisation d ’une mire parfaitement modélisée• appariements 2D/3D :• résolution du système :
• solution au sens des moindres carrés :
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
=
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜
⎝
⎛
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
−−−−−−
M
M
M
M
34
34
33
32
31
33
23
22
21
14
13
12
11
.
..
...10000
...00001mvmu
mmmmmmmmmmm
ZvYvXvZYXZuYuXuZYX
i
i
iiiiiiiii
iiiiiiiii
ntt
nn uKKKXuXK 21
11211112 ..).(. −× =⇒=
( ) niiiiii ZYXvu ,...,1,,,, =
Métrologie 3D
5
- Modélisation de la caméra -• « Camera calibration toolbox » de Matlab :
Métrologie 3D
6
- Stéréovision -• Etalonnage :
• Problème des droites non sécantes…
• étalonnage indépendant de chacune des caméras• détermination du positionnement relatif entre caméras (choix arbitraire d ’une vue commune)
• mise en correspondance et triangulation
'
'
'02
'
'02'
2'2
'2
'
0101111
1,,. ,.
1,, ,.
⎟⎟⎠
⎞⎜⎜⎝
⎛ −−==
⎟⎟⎠
⎞⎜⎜⎝
⎛ −−==
vu
vu
vvuuRvavecvMO
vvuuvavecvMO
ααλ
ααλ
rr
rr
R,t1O
2O
M
1. −= gdgd MMM
Métrologie 3D
7
- Stéréovision -• Principe : analyse de plusieurs images prises simultanément sous des angles différents• Etapes :
• Appariements - types de primitives
1) étalonnage hors-ligne du système2) appariements de primitives images gauche/droite3) reconstruction 3D
• régions - taille non conservée – segmentation• segments ⇒ reconstruction de segments 3D – scènes structurées – similarité de longueur, orientation,…• pixels - tous les pixels ou pixels spécifiques -information pauvre - occultations
image gauche image droite
Métrologie 3D
8
- Stéréovision -• Appariements de pixels :
• scores paramétriques :
• scores non paramétriques – exemple : CensusTransform
[ ][ ]
[ ] [ ]
v)(u,en niveau v)I(u, ,),( avec apparié ),(
),(),(
),(),(),(
),().,(),(
)],(),([),(
222111
, ,
2'22
'211
'22
'
,11
21
22'
1121
22'
1121
TT
yx yx
yx
M
Mx
M
My
M
Mx
M
My
vupvup
IyvxuIIyvxuI
IyvxuIIyvxuIppZNCC
yvxuIyvxuIppCC
yvxuIyvxuIppSSD
==
−−−−−−
−−−−−−=
−−−−=
−−−−−=
∑ ∑
∑
∑ ∑
∑ ∑+
−=
+
−=
+
−=
+
−=
238
957
24100111000
10101100
10010100 CT=3
Métrologie 3D
9
- Stéréovision -• Contrainte épipolaire :• droite issue de l’intersection de avec le plan image droit - applicable aux points ou segments
• rectification des images pour stéréo dense – lignes épipolaires confondues avec les lignes image -matérielle ou logicielle
),,( 121 pOO
M
2C1C
n n
Axe optique Axe optique
1m 2m
2C1C
n n1m 2m
W
x
yz x
y
z
Ol Or
P
pl
P1
P2
prpr1
pr2
Métrologie 3D
10
- Stéréovision -• Stratégie en stéréovision dense
• application sur les lignes épipolaires – appariements bidirectionnels
• contraintes unicité et ordre
• étude de la courbe de corrélation
Métrologie 3D
11
- Stéréovision -• Quelques illustrations
Images de profondeur et reconstruction 3D : papier -haut - et circuit imprimé – bas -
Métrologie 3D
12
- Lumière structurée -• Couplage caméra+laser :
• laser source peu divergente et structurée
• attention à la sécurité oculaire
• différents motifs projetés
• applications: profilométrie, métrologie 3D, contrôle de surfaces peu contrastées
Profilométrie
Mesures de profondeur
Métrologie 3D
13
- Lumière structurée -• Principe pour un point lumineux :
• Stéréovision active :
• projection d ’un point lumineux - balayage de la scène - calibrage du faisceau - précision excellente
• projection d ’une matrice de points lumineux -calibrage - identifier les points dans l’image - vitesse d ’acquisition
) .(cot.
bz)y ( fvuuanf
x−
=θ
Z
x
X
Métrologie 2D
1
• Descripteurs de contours, de régions(spatiales, forme, texture, topologiques,…)
• Descripteurs spatiaux :
• boîte englobante (« bounding box ») - dimensions
• aire :
• centre de gravité :
• périmètre P(R) : nombre de pixels de la région ayant un voisin en dehors de celle-ci
• diamètre, diamètre géodésique, …
• direction par intercepts : 0°,45°,90°,135°
• périmètre de Crofton :
• diamètre de Feret : plus grande distance des points de contours de la région à T
∑∑∑∑−
=
−
=
−
=
−
=
==1
0
1
0
1
0
1
0),(.
)(1 ,),(.
)(1 L
y
C
x
L
y
C
xyxfy
RAyyxfx
RAx
∑∑−
=
−
=
=1
1
1
1
),()(L
y
C
x
yxfRA
∫=
=π
α
αα2
0
).,()( dRDRP
)( tanint int )(
).(),(
α
α
α
α
dligneslestercepfrontièresspodenombreXN
dxXNXD ∫=
)(αFD
- Descripteurs de régions -
Métrologie 2D
2
• Caractéristiques de forme (1) :• compacité :
• élongation :
• circularité de Heywood :
• moments :
• moments d’inertie :
• dispersion autour du CdG ( ), dissymétrie de la distribution ( ), son caractère pointu ( )
• moments de Hu invariants aux rotations, échelles, translations !
• orientation : valeur propre max de la matrice d’inertie
))(.4/()( 2 RARPFc π=
))(..2/()( RARPFcH π=
2)(/))(.4(1)( RPRARE π−=
∑∑−
=
−
=
=1
0
1
0),(..
L
y
C
x
qppq yxfyxm
),(.).()(1
0
1
0yxfyyxx q
L
y
pC
xpq ∑∑
−
=
−
=
−−=μ
0220 ,μμ0330 ,μμ 0440 ,μμ
....4)()2(
)1(211
20220
0220
μμμ
μμ
+−=
+=
M
M
44,2tan
21,
0220
11
0211
1120 πϕπμμ
μϕμμμμ
≤≤−⎥⎦
⎤⎢⎣
⎡−
=⎥⎦
⎤⎢⎣
⎡= ArcM
- Descripteurs de régions -
Métrologie 2D
- Descripteurs de régions -• Descripteurs de forme (2) :
• courbure
• descripteurs de Fourier :
3
définition :
mise en œuvre : calcul de la distance entre le centre de la corde et la courbe
exemple :
principe : un contour de coordonnées (x,y) noté sous forme complexe – les contours d’une région assimilés à une séquence de nombres complexes
0
00
limPP
C PPαα −
= →
10,.2exp).()(
1,...,0),(.)()(1
0
−≤≤⎟⎠⎞
⎜⎝⎛ −=
−=+=
∑−
=
NkN
nkjnuka
NnnyjnxnuN
n
π
547.0=cσ
206.1=cσ
Métrologie 2D
4
• Descripteurs de texture :• Caractéristiques de texture (1) : • matrices de co-occurrence :
yx
yxyx
yxyx
yx
LLdimensiondeoccurencecodematriceladetscoefficienp
LLLLnmlkCarddjipjnmIilkId
LLLLnmlkCarddjipjetindgdeetegéométriqu
relationuneparreliésyxetyxresp
pixelsdeuxSoientLLdimensiondeISoit
×−
======
×××∈=°
====
×××∈=°
×
]jn)I(m, i,l)I(k, d),n-l-d,m-(kor -d)n-ld,m-(k
/)()()),(),,[(()45,,,(]),(,),(,n-l0/m-k
/)()()),(),,[(()0,,,(: resp. )direction d, (distance
),( ),( .
.
2211
θ
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
=
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
=
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
=
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
=
°°
°°
0100142002210014
,
0200201301210312
0200222202400206
,
2100160100420124
45135
900
PP
PP
Matrices symétriques !
- Descripteurs de régions -
principe :
exemple :
Métrologie 2D
5
- Descripteurs de régions -• Caractéristiques de texture (2) :
• Caractéristiques topologiques
∑°°=
=135,...,0θ
θPP
⎪⎭
⎪⎬⎫
⎪⎩
⎪⎨⎧
= ∑∑=−
−
= nji
N
n Rjipnf
g ),(1
0
22
• matrices de co-occurrence :
• nombre de trous (H)
• nombre de composantes connexes (C)
• nombre d’Euler : E=C-H
• nombre de branches du squelette
pour invariance aux rotations :
14 attributs déduits de ces matrices, par exemple pour le contraste :
classifier une texture = calculer la distance de ses descripteurs à ceux de textures apprises
Métrologie 2D
• Un constat : positionnement souvent imprécis ⇒ problème pour vérification de présence et métrologie
• Positionnement par l’objet entier
• Positionnement par contour(s)
• principe : recalage par le CdG de l’objet segmenté
• (-) : CdG souvent instable… de part les conditions de capture
• principe : recalage par un contour spécifique
• (-) : sensibilité, qualité du contour
6
- Positionnement -
Métrologie 2D
• Orientation
7
- Positionnement -
• calcul de l’axe principal
• signature distance versus angle
principe basée sur la matrice d’inertie(-) : cas des objets symétriques ou circulaires,
temps de calcul
définition : distance contour-CdG pour chaque direction
mise en œuvre : calcul du décalage maximisant le recouvrement des signatures des objets référence et courant
Reconnaissance et classification
• Notions d’individu et de variables :
• Distance euclidienne entre individus
• Distance de Mahalanobis
• Distance et matrice de covariance totale T
1
- Notions de bases -
• définition :
• (-) : échelle des composantes, dispersion des composantes
• définition :
•(+) : distance assurant une grande cohésion du nuage
• (-) : connaissance a priori des classes, besoin de beaucoup d’individus
[ ] jiPii Cclasseladexxx N,1,iet j'
1 KK ==
[ ] ( ) ( )jiji
P
kjkikji xxxxxxxxd −−=−=∑
=
.),( '2
1
2
[ ] [ ][ ]
[ ][ ])()()()(1
),(
1,1
1'2
lxlxkxkxN
w
wavecW
xxWxxxxd
jiCx
jij
kl
PlPkklj
jijjiji
ji
−−=
=
−−=
∑∈
≤≤≤≤
−
[ ][ ])()(.)()(11
lxlxkxkxN
t i
N
ii
Tkl
T
−−= ∑=
Reconnaissance et classification
2
- Prétraitement des données -• Analyse en composante principale (ACP) :
• but : réduction de la dimension de l’espace
• basé sur la matrice de covariance totale T
• principe : calcul de l’axe u séparant au mieux les données dans l’espace i.e. donnant la variance totale maximale – base orthonormée
• démarche pratique : extraire les n vecteurs propres de la matrice T correspondant aux n premières valeurs propres car proportionnelles au pouvoir discriminant de chaque axe
• choix du nombre d’axes ?
0 ].[ =Ι− uT λ
initialespaceldeensionPP
ii
n
ii
' dim ,1
1
1 ≈
∑
∑
=
=
λ
λ
Reconnaissance et classification
3
- Prétraitement des données -• Analyse Factorielle discriminante (AFD) :
• but : réduction de la dimension de l’espace des données mais en mode supervisé
• basé sur la matrice de covariance intra-classes :
• basé sur matrice interclasses B :
• principe : calcul de l’axe qui regroupe au mieux chaque classe et sépare au mieux les différentes classes
[ ]
[ ][ ]∑∑= ∈
−−=
≤≤
=
Q
jjiji
CxTlk
j
jlk
lxlxkxkxN
w
QjCclasseladanskparamètre
dumoyennevaleurkxavecwW
ji1,
,
)()(.)()(1
)1(
)(
[ ] [ ][ ]∑=
−−==Q
jjjj
Tlklk lxlxkxkxN
NbavecbB
1,, )()(.)()(.1
uuBW ...1 λ=−
Reconnaissance et classification
4
- Mode supervisé -• But : classifier une forme X parmi une classe représentées par leurs individus
• Classes représentées par des prototypes0)()()(
.. )()(
)(),...( 1
lk
11
=−=
∈>
− −
XdXdXdparCetCclasseslesséparerei
CXalorsXdXdsiquetelles
XdXddécisiondefonctionsQdéfinir
lkkl
klk
Q
• classement de X à partir du prototype le plus proche en distance euclidienne :
•(+) : compacité de la modélisation
•(-) : pondération des caractéristiques…
• (-) : dispersion des formes d'apprentissage
Qjjj xXdXd ≤≤= 1),()(
{ }QjjC
,...,1=
{ }ji Cxix ∈
Reconnaissance et classification
5
- Mode supervisé -• Classes représentées par tous les individus
• analyse du voisinage de la forme à classer i.e. des k plus proches voisins (k-PPV)
• règle de décision :
• (+) : tient compte de la dispersion des classes
• (-) : mémorisation de toutes les formes d'apprentissage
• (-) : calcul d'un grand nombre de distance pour connaître les k-PPV
• (-) : choix de k ? Problème des bords ?
{ } { }
∑ ∑= =
≤≤≤≤
∈<
−∈∈
k
im
k
iii
n
imkii
CXalorsXxdXxdsi
CetCclasselapourXdePPVklesxetCx
1 1
'
m
nki1'
1
),(),(
: C
Reconnaissance et classification
6
- Mode supervisé -• Application de classification par k-PPV : reconnaissance de situation
Images stéréo et reconstruction 3D
Boîtes pour le comptage des points 3D
Reconnaissance et classification
• Classes représentées par plusieurs prototypes
7
- Mode supervisé -
• approximation de la distribution de chaque classe par un ensemble de cercles, hypersphères,…représentés par un prototype
• (+) : limitation du nombre de formes à stocker…
• règle de décision/rejet :
• (-) : règle de rejet binaire ⇒ ajout de fonctions de probabilité décroissant suivant la distance au prototype
modèle « Restricted Coulomb Energy »modèle « Radial Basis Function »
jj RXxd ≤),(
Reconnaissance et classification
8
- Mode supervisé -• Classification bayésienne
• lois de probabilité de chaque classe connues
• décision bayésienne :
( )
)()( ,...,1 ),()./()(
/ )/(
i XdXdsiCdansclasséeXQiCpCXpXd
CclasseladeprioriaéprobabilitCpCXXlleconditioneéprobabilitCXp
ji
iii
ii
ii
>==
∈
( ) ⎥⎦⎤
⎢⎣⎡ −−−= − ).(.
21exp.
)2(
1)/( 1'
21
2iii
i
Pi xXWxXW
CXpπ
Reconnaissance et classification
9
- Mode supervisé -• Exemples de classification bayésienne
Image originale et image labellisée
Classe Objet Numéro d’objet Valeur de l’attribut0 fond 0 -11 clou 1 0.932 Vis à tête 2 0.33 pointe 5 1.924 bruit 13 0.0
Numéro d’objet Valeur de l’attribut3 1.0112 1.41
Moment invariant d'ordre 2
Résultat de laclassification
Objet malclassé
Choix desprototypes
Reconnaissance et classification
- Mode supervisé -• « Template matching »
• une approche non ascendante…
• but : détecter la présence d’une forme a priori
• utilisation de scores de similarité
• (+) : pas de segmentation préalable de l’image
• (-) : temps de calcul, robustesse au facteur d’échelle
• optimisation des calculs : recherche hiérarchique, sous échantillonnage, troncature des calculs
• exemple :
10
Reconnaissance et classification
11
- Mode supervisé -• Application : inspection de qualitéd’impression
• but : vérifier la lisibilité des caractères sur une jauge à carburant
• démarche classique : différence entre image de référence puis tests, requiert un positionnement très précis…
recalage grossier à partir du trou et corrélation sur « template matching »
recalage fin de chaque région par corrélation sur « template matching »
différence d’images – segmentation régionsfiltrage du bruit à partir de caractéristiques
telles que aire, ratio, contraste,…
Reconnaissance et classification
• Réseau de neurones (1)
12
- Mode supervisé -
• perceptron multicouches : trois couches interconnectées de neurones
• neurone élémentaire : somme pondérée des entrées et une fonction d’activation en sortie
)(∑ −=k
jkkjaj owfa θ
Reconnaissance et classification
• Réseaux de neurones (2)
13
- Mode supervisé -
• seuil d’activation du neurone
• fonction d’activation dérivable – exemples :
• apprentissage des poids par rétro-propagation de l’erreur
jθ
kjw
Reconnaissance et classification
14
- Mode supervisé -• Application : OCR sur circuit imprimé (1)
• but : vérification de présence
• utilisation de filtres polarisants
• démarche classique (1) :ajustement en position du circuit, 2 solutions :
positionnement de ROIs et segmentation par seuillage
par détection des arêtes verticales puis horizontales du circuit
par détection des deux triangles (« templatematching ») puis recherche en relatif des autres caractères
Reconnaissance et classification
15
- Mode supervisé -• Application : OCR sur circuit imprimé (2)
• démarche classique (2) :
extraction des rectangles englobant les régions segmentées et des imagettes associées
ré-échantillonnage et normalisation de contraste
classification par réseau de neurones
Reconnaissance et classification
16
- Mode supervisé -• Application : Reconnaissance de code-barres
• but : identifier les codes de films 100, 200 et 400 ASA à 15Hz
• dispositif : caméra asynchrone, « shutter » très court (1ms), éclairage stroboscopique pendant 1μs
• démarche classique :
recalage en position par une arête verticale –pas de variation horizontale
positionnement d’une ROIré-échantillonnage sur une résolution de
10x20 pixels pour limiter l’information traitéeclassification par réseau de neurones
Reconnaissance et classification
• Algorithme des centres mobiles ou « K-mean » (1)
17
- Mode non supervisé -
• aucun a priori sur la répartition des individus en classes
• algorithme : fixer le nombre de classes désirées Qchoisir aléatoirement Q individus représentant
les CdGs des classesréaffecter chaque individu à la classe
dont le CdG est le plus prochecalculer les CdGs des classes ainsi créées. Si
changement dans répartition, revenir en
ix qC
Reconnaissance et classification
• Algorithme des centres mobiles (2)
18
- Mode non supervisé -
• (-) : sensibilité aux conditions initiales et aux « outliers », Q fixé a priori, nombre important d’individus, « clusters » circulaires
• exemple pour deux classes, 4 individus et 2 attributs :
Reconnaissance et classification
• Classification hiérarchique ascendante
19
- Mode non supervisé -
• but : minimiser la variance intra-classe
• basée classiquement sur la distance euclidienne
• algorithme :
• (-) : masse de calcul si ajout d’un individu, résultat lié à la distance utilisée
calculer les distances entre paires d’individusregrouper les deux individus les plus proches
dans une même classecalculer les CdG des groupes
calcul de la distance entre toutes les classesfusion des deux classes les plus proches si <
seuilretour en sinon fin
21
22113
..NN
rNrNr++
=
Reconnaissance et classification
• Qualité
• Ingénierie
20
- Choix d’une méthode -
• précision : erreur minimale, taux minimal de faux positifs et/ou faux négatifs
• lisibilité : résultats interprétables
• rapidité de la construction du modèle (« off-line », de la prise de décision (« on line »)
• autres : besoins en apprentissage, ressources CPU et mémoire,…
• « Usability » : facilité d’emploi
• « embedability » : facilité d’introduction dans un système global
• flexibilité : adaptation facile au changement de spécifications
• passage à l’échelle : gros volume de données
Bibliographie
- Quelques livres… -• Industrial Image Processing, C.Demant, B.Streicher-Abel et P.Waszkewitz, chez SPRINGER
• Analyse d’images : filtrage et segmentation, J.P.Cocquerez et S.Philipp
• Traitement et analyse des images numériques, S.Brès, J.M.Jolion, F.Lebourgeois, chez Hermès
• Les systèmes de vision, J.M.Jolion, chez Hermès
Recommended