Cours 10 à 12 5-6 Éléments symboliques n Découvertes n États de projet n 5- Extraction des...

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