Upload
jeanette-besse
View
107
Download
0
Embed Size (px)
Citation preview
Cours 10 à 125-6 Éléments symboliques
DécouvertesÉtats de projet5- Extraction des éléments
symboliques5.1 Transformée de Hough5.2 Extraction de segments de droite5.3 Détection des contours5.4 Détection des contours par
poursuite des crêtes et vallées5.5 Contours actifs (ou déformables)6- Représentation des
éléments symboliques
Cours #10-12 - 2 SYS-844Hiver 2005
Découverte(cours 10) Horaud, R,. Monga, O., Vision par
ordinateur: outils fondamentaux, 2e édition, Hermes, 1995. Paradigme de Marr Détection des contours
Filtre de Deriche-Canny Segmentation
Contours Régions
Calibration de caméra Stéréoscopie Vision 3D
Cours #10-12 - 3 SYS-844Hiver 2005
Découverte(cours 11)
B.K.P. Horn
Robot Vision
MIT Press et McGraw-Hill, 1986 École de Marr Contribution majeure: Shape from
Shading - reconstruction 3D à partir de l’ombrage
Cours #10-12 - 4 SYS-844Hiver 2005
Découverte(cours 12) D.A. Forsyth et J. Ponce
Computer Vision: A Modern ApproachPrentice Hall, 2003 Couvre la majorité des divers aspects
des systèmes de vision Couverture uniforme de la vision de
niveau bas, moyen et haut Exemples élaborés Prix élevé: 166$
Chapitre 5 Extraction des éléments symboliques
Un élément symbolique est un événement abstrait qui est localisé sur l’image mais qui requiert une description plus complexe que le pixel.
On fait la transition, dans ce chapitre, de la vision bas-niveau (appelée aussi pré-attentive, centrée sur le pixel) vers la vision de niveau intermédiaire, centrée sur les symboles élémentaires que l’on retrouve par analyse dans l’image.
Cours #10-12 - 6 SYS-844Hiver 2005
Exemples d’éléments symboliques Segments de droite Courbes Contours fermés Régions Texture
Représentation des éléments symboliques Indice unique Attribut de localisation (1 au
minimum) Attributs de description (e.g. rayon
de courbure, pente de la droite, etc)
Cours #10-12 - 7 SYS-844Hiver 2005
5.1 Transformée deHough
But: Former une structure deligne plus complète et pluscompacte à partir d’arêtesreliées entre elles
Cours #10-12 - 8 SYS-844Hiver 2005
Principe: Transformer une ligne d’équation y=mx+b en unpoint dans l’espace de
paramètres m et b. Chaque arête vote pour uncandidat dans l’espace deparamètres.
P
P’L1
L2y
x
b
m
L1
b=−xm+y
1 point 1 ligne1 ligne 1 point(déf. par 2 points) (inters. de 2 lignes)
L2
Cours #10-12 - 9 SYS-844Hiver 2005
Espace de paramètres
Cours #10-12 - 10 SYS-844Hiver 2005
Détection d’arêtes orientées 1 segment orienté 1 point n segments 1 nuage
d’orientations voisines
Cours #10-12 - 11 SYS-844Hiver 2005
Algorithme Quantifier b et m b et m H(m,b) = 0 matrice d’accumulation i,j tel que |A(i,j)| > T
H(m,b) = H(m,b) + 1 m,b tel que b= -mi + j
Max. local dans H(m,b) = segments colinéaires
Variantes Hough pur: 1 point image 1 ligne Arêtes |A| + 1
point orientées
Cours #10-12 - 12 SYS-844Hiver 2005
Exemple: image d'arêtes
02468
10
1 2 3 4 5 6 7 8
i
segment 1segment 2segment 3
1
2
30
1
2
b
0 0,25 0,5 0,75 1 1,25m
Espace de paramètres H(m,b)
b=−mi+j
1: i=2, j =2 b=−2m+2
2: i=4, j =5 b=−4m+5
3: i=7, j =7 b=−7m+7
Cours #10-12 - 13 SYS-844Hiver 2005
Problème de représentation: La valeur de m devient trop importante pour des arêtes presque verticales.
Algorithme modifié Paramètres: r, Algo. Identique, avec H(r,)
Cours #10-12 - 14 SYS-844Hiver 2005
Algorithme de Hough généraliséf(x,a) = 0
(x,a) est le vecteur de paramètres (axes dans l’espace de Hough)
Talon d’achillelocalisation dans l’image est perdue
les 2 sets (\ et \) activent le même maximum Hough. Nous aurons donc besoin de manipuler l’espace de l’image afin de connecter les segments détachés ou encore isoler les segments.
Cours #10-12 - 15 SYS-844Hiver 2005
5.2 Extraction de segments de droite
Algorithme basé sur l’article:
Extracting Straight LinesJ.B. Burns, A. Hanson, E.
Riseman
IEEE Tr. PAMI, Vol. 8(4), Juillet 86, pp. 425-455
But Extraire des lignes droitessignificatives à partir de l’image d’éclairement
Cours #10-12 - 16 SYS-844Hiver 2005
Principe Estimé de l’orientation des gradients
locaux Groupement des orientations
similaires Modélisation de la surface dans le
groupe comme une rampe Ligne: intersection de la rampe et du
plan horizontal de hauteur Imoyen
Cours #10-12 - 17 SYS-844Hiver 2005
Représentation surfacique
Cours #10-12 - 18 SYS-844Hiver 2005
Ligne: intersection de 2 plans
Cours #10-12 - 19 SYS-844Hiver 2005
Algorithme 1: Estimé des orientations locales de gradient
Cours #10-12 - 20 SYS-844Hiver 2005
2: Formation des régions de support d’arêtes de même orientation
Segmentation par partition Orientations réparties en classes Région de support: arêtes connectées
même bin de H()
Cours #10-12 - 21 SYS-844Hiver 2005
• Problème des frontières: histogramme double– Orientations sur 2 histogrammes– Régions de support formées aves les 2 H()– Chaque arête vote pour la région avec la
ligne extraite la plus longue
Cours #10-12 - 22 SYS-844Hiver 2005
• Problème du nombre de partitions
Cours #10-12 - 23 SYS-844Hiver 2005
3: Approximation de la représentation surfacique de l’éclairement par une
surface plane. Pondération par
l’amplitude du gradient Ligne: Intersection entre la surface plane et la surface horizontale dont la hauteur est la valeur moyenne pondérée de l’éclairement
Cours #10-12 - 24 SYS-844Hiver 2005
4: Mesure des attributs de la ligne Longueur Position Orientation Contraste (pente de la rampe) Région de support Paramètres du segment de ligne
5: Filtrage des attributsPermet d’isoler les longues lignes, les lignes dans une certaine orientation, courtes et à faible contraste, etc.
Cours #10-12 - 25 SYS-844Hiver 2005
Filtrage des attributs
Cours #10-12 - 26 SYS-844Hiver 2005
Cours #10-12 - 27 SYS-844Hiver 2005
5.3 Détection des contours
Principe: Un contour est un ensembleordonné de points
connectés
Cours #10-12 - 28 SYS-844Hiver 2005
Algorithme 1: Détection des arêtes locales
Cours #10-12 - 29 SYS-844Hiver 2005
2: Amincissement par suppression des non-maxima (réf. Canny, 3.3.3 et Aphelion ImgEdgesThin) et seuillage
Cours #10-12 - 30 SYS-844Hiver 2005
3: Structuration des arêtes en liste chaînée semence (point de départ): arête avec le
gradient d’amplitude le plus élevé Chaîne agrandie par les extrémités. Le
meilleur candidat est choisi (si existant). Critères de sélection:
• Angle de rotation : • Angle entre l’arête orienté et l’orientation du lien
• Longueur du lien Choix du lien: pointage proportionnel à
somme pondérée de L, et
α <π4
β1 −π2
,β2 −π2
<Seuila
L<Seuilb
Cours #10-12 - 31 SYS-844Hiver 2005
Exemple
Cours #10-12 - 32 SYS-844Hiver 2005
5.4 Détection des contours par poursuite des crêtes et des vallées
Principe: L’image est interprétéecomme une surface dansun espace 3D.éclairement profondeurCrêtes ou vallées désignent des contours.Les crêtes / vallées sontdétectées par dérivée seconde directionnelle
Cours #10-12 - 33 SYS-844Hiver 2005
Algorithme 1: Déterminer les points locaux de
grande courbure négative ou positive
Cours #10-12 - 34 SYS-844Hiver 2005
2: Structuration des contours en liste chaînée semence (point de départ): un point détecté de
grande courbure (négative ou positive) Chaîne agrandie vers les 2 extrémités
Critères de sélection:• Angle de rotation : • Angle entre contour de crête et l’orientation du lien
• Longueur du lien
Choix du lien: pointage proportionnel à somme pondérée de L, et
α <π4
β1 −π2
,β2 −π2
<Seuila
L<Seuilb
Cours #10-12 - 35 SYS-844Hiver 2005
Exemple: Image microscopique d’une plume Représentation surfacique
Cours #10-12 - 36 SYS-844Hiver 2005
Détection des crêtes et des vallées
Cours #10-12 - 37 SYS-844Hiver 2005
Formation des listes chaînées
Cours #10-12 - 38 SYS-844Hiver 2005
Mesure de la courbureLa détection de contours par poursuite des crêtes et des vallées repose sur la détection de la courbure d’une surface tridimensionnelle. C’est une notion très importante en vision 3D auquelle nous nous penchons plus en détail. La notion de courbure sera explorée au laboratoire sur la numérisation 3D.
Cours #10-12 - 39 SYS-844Hiver 2005
Paramétrisation de la courbure 2 paramètres caractérisent une
courbure: K: la courbure gaussienne H: la courbure moyenne
2 mesures locales permettent de calculer K et H:
1 et 2: les courbures principales de la surface, soient les courbures maximales et minimales au point d’intérêt.
K =κ1 ×κ2
H =12κ1 +κ2( )
Cours #10-12 - 40 SYS-844Hiver 2005
Catégories de courbure
K>0 K=0 K<0
H<0
H>0
H=0
Cours #10-12 - 41 SYS-844Hiver 2005
Mesure de la courbure Un maximum (ou minimum) de la dérivée
seconde d’une courbe indique sa courbure et son point le + bas (le + haut)
Courbure locale: Mesure de dérivée seconde en différents points de la surface dans des directions orthogonales
s et s’: 2 directions orthogonales
C1 et C2 : courbures au point (x,y)
C1: courbure dans plan Zos
C2: courbure dans plan Zos’(x,y)
s
s’
Z
C1
C2
Cours #10-12 - 42 SYS-844Hiver 2005
Mesure de dérivée seconde pour localiser la courbure max.
z
C1’
C1’’ max
Cours #10-12 - 43 SYS-844Hiver 2005
Matrice de Hess Mesure locale de la courbure Matrice formée avec les dérivées
secondes selon x, y et xy
H =r s
s t⎡ ⎣ ⎢
⎤ ⎦ ⎥
r =XX=∂2
∂x2 =
1 −2 1
1 −2 1
1 −2 1
⎡
⎣
⎢ ⎢
⎤
⎦
⎥ ⎥
t=YY=∂2
∂y2 =
1 1 1
−2 −2 −2
1 1 1
⎡
⎣
⎢ ⎢
⎤
⎦
⎥ ⎥
s=XY=YX=∂2
∂x∂y=
∂2
∂y∂x=
−1 0 1
0 0 0
1 0 −1
⎡
⎣
⎢ ⎢
⎤
⎦
⎥ ⎥
Cours #10-12 - 44 SYS-844Hiver 2005
Le Hessien donne de l’information sur la courbure locale de surface (pour de faibles inclinaisons)
detH =rt−s2 ≅K
trace H =Laplacien de profondeur = 2×H
trace H =r+t=∂ 2z∂x2 +
∂ 2z∂y2
Cours #10-12 - 45 SYS-844Hiver 2005
Direction de courbure maximum• Valeurs propres calculées à partir du
Hessien• Vecteur propre correspondant à la
valeur propre maximale indique la direction de la crête ou de la vallée
Cours #10-12 - 46 SYS-844Hiver 2005
Algorithme pour trouver max/min de courbure (Aphelion: ImgRidgeValleyEdges)
(x,y) de l’image:• Calculer
• Trouver les valeurs propres i • Trouver le vecteur propre associé au i max.
Le vecteur propre pointe vers la courbure positive ou négative.
H =r s
s t⎡ ⎣ ⎢
⎤ ⎦ ⎥
Cours #10-12 - 47 SYS-844Hiver 2005
5.5 Contours déformables
Les travaux de recherche sur les contours déformables sont relativement récents et sont issus des travaux pionniers de Kass, Witkin et Terzopoulos lors d’une conférence présentée en 1987 à la première conférence internationale sur la vision informatique.
Les contours déformables sont aussi appelés contours actifs et « snake »
Cours #10-12 - 48 SYS-844Hiver 2005
Objectif: Détection des contours fermés d’une image à partir de
quelques points d’arête situés près du contour
Principe: L’image est considérée comme une
image de profondeur z=f(x,y). Représentation surfacique.
Un élastique entoure le contour désiré L’énergie interne de l’élastique est
minimisée
Cours #10-12 - 49 SYS-844Hiver 2005
Illustration: Reconstruction 3D du squeletteIllustration: Reconstruction 3D du squelette
ETS, Polytechnique, LIO-CHUM, LIS3D-Ste Justine, ENSAM-ParisETS, Polytechnique, LIO-CHUM, LIS3D-Ste Justine, ENSAM-Paris
Triangulationstéréoradiographique
Traitement d’images
Modélisation géométrique
++
Cours #10-12 - 50 SYS-844Hiver 2005
Fonctionnelle d’énergieUne fonctionnelle d’énergie est associée à chaque forme de contour. Le contour à détecter correspond à un minimum d’énergie.
ε= α s( )Econt+β s( )Ecurv+γ s( )Eimage( )dscontour C s( )
∫
avec s= longueur d'arc
s=dcdt
dt0
T
∫
avec t= paramètre de la courbe
0<t<T
Cours #10-12 - 51 SYS-844Hiver 2005
Continuité: contrainte de rigidité qui agit sur la longueur du contour.
Lissage ou élasticité: contrainte pour éviter les oscillations du contour.
Arêtes: le contour est attiré par les arêtes de l’image.
ε= α s( )Econt+β s( )Ecurv+γ s( )Eimage( )dscontour C s( )
∫
cas discret: C composé de N points: p1L pN
Econt=dcds
2
Econt≅ pi −pi−1
2
Ecurv= pi−1 −2pi +pi+1
2
Eimage=−∇I
Chapitre 6 Représentation des éléments symboliques
Différents niveaux de représentation sont nécessaires dans un système de vision. Nous avons étudié le premier niveau de représentation, le niveau de l’image (d’éclairement, de niveaux de gris, de profondeur, couleur, etc.) et les divers algorithmes qui nous permettent d’en extraire des primitives.
Ces primitives doivent être ensuite regroupées pour former des caractéristiques plus abstraites qui nous permettront de les identifier. C’est la vision de niveau intermédiaire qui travaille sur des regroupements d’information qui forment des éléments symboliques.
Cours #10-12 - 54 SYS-844Hiver 2005
Objectifs d’un système de vision numérique
Identifier Localiser
Cours #10-12 - 55 SYS-844Hiver 2005
Interpolation
Stéréo
Imagesdroitegauche
Croquis
Esquisse
Esquisse2 1/2 D
multirésolution
Ombrage Ombrage
Détection des arêtes
Description3 D
Segmentation
MouvementTextureCouleur
etc.
si 2 lignes voisinessi lignes longues
alors fermersi - - -si lignes parallèles
Système à basede connaissances
Couleur Couleur
6.1 Vision intermédiaire
bas
intermédiaire
symbolique
Cours #10-12 - 56 SYS-844Hiver 2005
Extraction des segments
Image
Croquis
multirésolution
Détection des arêtes
si 2 lignes voisinessi lignes longues
alors fermersi - - -si lignes parallèles
Segmentation
Description
Système à base
et interpolation
et interprétation
Esquisse
de connaissances
bas
intermédiaire
symbolique
Cours #10-12 - 57 SYS-844Hiver 2005
Niveaux d’abstraction
Chiffres
Hypothèses
Éléments symboliques
STM Contrôle LTM
Mémoire àcourt terme
Mécanismesde contrôled’inférence
Mémoire àlong terme
Siège desconnaissances
Cours #10-12 - 58 SYS-844Hiver 2005
Niveaux de représentation 1: Rétino-centrique
Image Régions, arêtes
2: Éléments symboliques
Regroupement de primitives
• Lignes et courbes• Contours• Frontières
3: Hypothèses
Détermination du contenu symbolique
Cours #10-12 - 59 SYS-844Hiver 2005
Représentations rétino-centriquesImages et dérivées: régions, lignes, contours, surfaces, ...
Hypothèses
Éléments symboliquesReprésentations symboliques d’événements et de caractéristiques;
descriptions des événements dérivés de l’image et des caractéristiques
Multi-résolution
TransformationIconic -> symbol.
extraction
groupementorganisation
fonctionsde contrôle
Cours #10-12 - 60 SYS-844Hiver 2005
Opérations aux divers niveaux Algorithmes de bas niveaux
Extraction des régions, lignes, surfaces ou autres événements significatifs de l’image et leurs caractéristiques
Algorithmes de niveau intermédiaire de regroupement perceptuel
Objets de haut-niveau ou hypothèses sur des parties d’objet bâties du haut vers le bas
Cours #10-12 - 61 SYS-844Hiver 2005
6.2 Base de données intermédiaires
Quantité de données au niveau intermédiaire
Cours #10-12 - 62 SYS-844Hiver 2005
Élément symbolique Événement sur l’image qui est identifiable Les ES doivent pouvoir être localisés sur
l’image et qualifiés (attributs pour les décrire)
Cours #10-12 - 63 SYS-844Hiver 2005
Base de données («tokenset») Attribut de localisation
Au moins 1 est nécessaire Attributs
Descriptions qualitatives ou quantitatives Chaque attribut défini n’a pas à être
calculé tous en même temps
Cours #10-12 - 64 SYS-844Hiver 2005
Attribut de localisation Diverses façons de localiser un ES
Localisation d’une lignegénéralement décrite parun attribut de segment dedroite (coord. des extrémités)
Localisation d’une lignepeut tout aussi bien être décritepar la position des pixels àtravers lesquels la ligne passe
Cours #10-12 - 65 SYS-844Hiver 2005
Les divers types d’attribut de localisation
Cours #10-12 - 66 SYS-844Hiver 2005
Attribut multiple de localisation
Cours #10-12 - 67 SYS-844Hiver 2005
Attributs: Exemples autre que localisation Orientation histogramme
Cours #10-12 - 68 SYS-844Hiver 2005
Types d’attributs Logique - vrai ou faux Entier - nombre entier Flottant - nombre réel Chaîne - chaîne de caractères
ASCII Matrice - matrice ou vecteur
de nombres réels Sous-ensemble d’éléments
symboliques
- ensemble (regroupement) d’éléments
symboliques