N Découvertes n Présentation des équipes et des projets n 3- Extraction des primitives u 3.1 Caractéristiques 3D et 2D u 3.2 Arêtes u 3.3 Gradient et arêtes

DécouvertesPrésentation des équipes et des

projets

3- Extraction des primitives3.1 Caractéristiques 3D et 2D3.2 Arêtes3.3 Gradient et arêtes orientées Gradient - moyenneur

Amincissement des arêtes Canny-Deriche Arêtes orientées

Cours 7-8 3- Extraction des

primitives

Cours #7-8 - 2SYS-844Hiver 2005

3- Extraction des primitives (suite) … 3.4 Modèles paramétriques 3.5 Passages par zéro de la dérivée

seconde 3.6 Détection multirésolution


Forum


Découvertecours 7

Haralick & Shapiro, Computer and Robot Vision, Volume 1 et 2, Addison-Wesley,1992 et 1993. Traitement complet de la vision par ordinateur Approche mathématique Texture Appendice vol. 1: ellipse Knowledge-based vision


Découvertecours 8

T. Lindberg, Scale-Space Theory in Computer Vision, Kluwer Academic,1994. Aspects théoriques de la représentation

multirésolution Plusieurs approches originales et intéressantes

Henri Maître, Le traitement des images, Hermes, 2003 Collectif d’auteurs reconnus dans leur domaine Vue d’ensemble du traitement d’images

Traitement Restauration

Champs de Markov Ondelettes Contours actifs Texture Vision

Chapitre 3 Extraction des primitives

L’extraction des primitives est le premier traitement réalisé sur l’image filtrée et conditionnée. Nous allons d’abord nous intéresser aux arêtes, ces variations brusques de l’éclairement lumineux. Puis, nous nous intéresserons aux regroupements de ces arêtes à plus grande échelle, pour former des lignes, des contours, des courbes, etc.


3.1 Caractéristiques 3D et 2D

Ce qui permet de différencier un objet 3D: Contour (forme du contour) Changement d’orientation de surface Marques sur la surface (texture)

En résumé, les discontinuitésDu processus de formation des images:

E∝ L

∇E∝ ∇L

E =π4df

⎡

⎣ ⎢ ⎤

⎦ ⎥

2

cos4α ⋅L

EI =df

⎛ ⎝ ⎜ ⎞

⎠ ⎟

2

cos4αEo4

cosθi


Sortes de discontinuités


3.2 Arêtes

Attributs 3D arêtes 2D Orientation de surface Variation de profondeur Ombrage Réflectance de surface

Bruit de mesure arêtes 2D


Limitations de la détection des arêtes Les arêtes 2D n’indiquent pas le

type d’attribut 3D Certaines caractéristiques 3D

perceptuelles ne sont pas traduites en arêtes


Objectifs de la détection d’arêtes Extraction des arêtes significatives Regroupement en lignes, courbes

et contours


Catégories d’arêtes

Échelon Rampe Barre

Crête Point (eg spot

lumineux)


Détection d’arêtes dans le bruit


Algorithme général d’extraction des primitives Calcul des variations d’éclairement Détection des arêtes (seuillage) Amincissement Regroupement



Calcul des variations d’éclairement Gradient (dérivée première) Passage par zéro (dérivée seconde)

I

∇I

∇2I

Caractéristique de scène (variation de la normale à lasurface) et sa traduction sur l’image d’illuminance I. Lavariation d’illuminance peut être détectée soit comme unmaximum de la dérivée première de l’image, ou soit com-me un passage par zéro de la dérivée seconde.


3.3 Méthodes basées sur le gradient


3.3.1 Gradient d’une image

v ∇ I x,y( )= Δx x,y( ),Δy x,y( )( )

avec Δx=∂∂xI x,y( )

et Δy=∂∂yI x,y( )

v ∇ I = vecteur avec

une amplitude s= Δ2x+Δ2y

une orientation θ=tan−1 ΔyΔx

⎛ ⎝

⎞ ⎠

Approximation: ∂∂x

⇒ Différence selon x


Interprétation géométrique du gradient


3.3.2 Masques 1x2

-1 1

-1

1

∂∂x

=Δx

∂∂y

=Δy

∇I x,y( )≅Δx OU Δy


Formation de x et y


Approximation de l’amplitude du gradient


dérivation accentue le bruit


Combinaison différentiation - filtre moyenneur




3.3.3 Masque moyenneur-différentiateur Masques de base:

Sobel Prewitt


Quelques masques supplémentaires


Effets de la grosseur des zones de moyennage Utilisation de deux masques orthogonaux


Effets de l’augmentation de la zone de moyennage


Pondération uniforme, non-uniforme et sans pondération


Effets sur les coins

Masque de 11x11 avecpondération uniforme


Détection d’arêtesmasque de 11x11


Vecteurs gradients: arrondissement du coin


Effets sur une image plus complexe


Masque de 7x7


Résumé: effets de la largeur de masque


Grandeur optimale: 3x3 Moyennage le long de l’arête et

différentiation à travers l’arête Si l’arête est orientée différemment

de 0o ou 90o, celle-ci sera filtrée, d’où une amplitude plus petite du gradient

Solution: masque de Sobel orienté selon plusieurs directions

• Filtrage raisonnable• Détection symétrique



3.3.4 Détecteur de Canny Principe détection optimale

d’arêtes bruitées Critères

Bonne détection• Minimiser prob. de faux positifs• Minimiser prob. de ne pas détecter une

vraie arête Bonne localisation Contrainte de réponse unique

• Minimiser le nombre de maxima locaux autour de la vraie arête

Opérateur optimalFiltre RIF complexe, approximé par: dérivée première de gaussienne


Algorithme Filtrer l’image par une gaussienne

Dérivée première de l’image filtrée

Amplitude et direction du gradient

Maximum local dans la direction du gradient

• Algorithme: amincissement des arêtes

Seuillage avec hystérésisG x,y( ) >τh ⇒ arête gardée

G x,y( ) <τl ⇒ arête rejetée

τl ≤G x,y( )≤τh ⇒ gardée si dans direction

des gradients voisins


Variante Canny-Deriche Filtre optimal de Canny:

Forme complexe, approximée par une dérivée de gaussienne(20% de perte de performance)

RIF de largeur 2M• largeur varie en fct de la fréq. coupure

Filtre optimal de Deriche Filtre récursif RII

• Largeur fixe• Forme 1D• Forme 2D,

séparable

Performances supérieures Valeurs typiques:

€

h(x) = ce−α x sinωx

€

X(m,n) =−ce−α m sinωm[ ] k(α sinω n + ω cosω n )e−α n

[ ]

α 2 + ω2

Y (m,n) =k(α sinω m + ω cosω m )e−α m

[ ] −ce−α n sinωn[ ]

α 2 + ω2

€

α =1,6

ω = 0,01

Comparaison filtres Deriche vs Canny

Extension du filtre de Deriche en 2D


Amincissement des arêtes Principe: Opérateur large

réponse multiple


Analyse locale pour supprimer les arêtes redondantes


Analyse locale

Modèle en toit de l’arête

Appariement avec le modèle en toit:

• rejet des 2 arêtes enlignées (évite la compétition)

• rejet des orientations différentes (possibilité de jonction)

• rejet des directions (signe) différentes (pas modèle en toit)


Algorithme 1- Fenêtre de sélection:

ne sont pas considérés: 1 arêtes alignées 2 arêtes d’orientation différente 3 arêtes de même orientation

mais de direction (signe) opposée

2- Suppression des non-maximaux

3- Seuillage (en option)

1

1

2

3

3

( ) ( ) ( )mnEjiEjiE mn ,, si 0,restant

, <∀=


exemple


3.3.5 Détection d’arêtes orientées Principe: Détection d’arêtes selon

plusieurs directionsSortie maximale:

détecteur i indique l’orientation et l’amplitude de l’arête

Opérateur:NO

O

SO S SE

E

NEN


Masques Sobel

S=maxnMn

n:0L 7

θ=45o ×indexmaxMn{ }




Prewitt 1 et 2 Kirsch Frei & Chen


Nevatia-Babu


3.4 Modèles paramétriques Principe:

Image traitée comme une surface I(x,y) Z(x,y)

Apparier une surface paramétrique approximant I(x,y) dans un voisinage

Gradients calculés sur la surface paramétrique


Surfaces paramétriques Constante Plane (la plus commune) ax+by+c Quadratique Cubique

Appariement: Moindres carrés

Z i, j( )−I i, j( )( )2

i, j( )∈N∑


Appariement à une surface plane Équation d’un plan: I(i,j)=ai+bj+c I(i,j)=c pour les surfaces horizontales a et b grands aux arêtes a et b approximent le gradient dans les

directions i et j respectivement


Appariement par moindre carrés

Z i, j( )=ai+bj+c

erreur=Z i, j( )−I i, j( )



Équations d’appariement par moindre carrés

Z i, j( )=ai+bj+c

2 3

41

j j+1

i

i-1

ε2 = ai+bj+c( )−I i, j( )[ ]2

+ a i−1( )+bj+c( )−I i−1, j( )[ ]2

+ a i−1( )+b j+1( )+c( )−I i−1, j+1( )[ ]2

+ ai+b j+1( )+c( )−I i, j+1( )[ ]2

1

2

3

4


∂ε∂a

=i ai+bj+c( )−I i, j( )[ ]

+ i−1( ) a i−1( )+bj+c( )−I i−1, j( )[ ]

+ i−1( ) a i−1( )+b j+1( )+c( )−I i−1, j+1( )[ ]

+i ai+b j+1( )+c( )−I i, j+1( )[ ]=0

∂ε∂b

=L =0

∂ε∂c

=L =0

a: pente du plan dans direction i

b: pente du plan dans direction j

c: interception de z


( ) ( ) ( ) ( ){ }2

1,,1,1,1 ++−+−+−=

jiIjiIjiIjiIa

( ) ( ) ( ) ( ){ }2

,1,1,11, jiIjiIjiIjiIb

−+−+−++=

-1 1

1-1

j j+1

i

i-1

1 1

-1-1

j j+1

i

i-1


Variantes Extension à un voisinage 3x3

Surface: quadratique Masque: Prewitt

Modèle « Facet » de HaralickImage: Image idéale + bruit


3.5 Passages par zéro

Méthodes basées sur le passage par zéro de la dérivée seconde de la fonction d’éclairement


3.5.1 Opérateurs de dérivée seconde Principe: Détection du passage

par zéro de la dérivéeseconde


Masques Anisotrope (directionnel)


1 -2 1

1

-2

1

∂ 2I∂x2

∂ 2I∂y2


Isotrope (indépendant de l’orientation)• Laplacien (réf. 2.2.6)

∇2I -4

1

1

11

– Détecteur isotrope du second ordre le plus petit possible

– On doit combiner 2 masques orthogonaux pour obtenir un détecteur isotrope de premier ordre

• Le laplacien est un opérateur très bruyant à cause du calcul de dérivée seconde


3.5.2 Laplacien moyenneur Principe: Calculer le laplacien sur

un masque de plus grande dimension

• effet de moyennage • problèmes d’élargissement de

transition identiques à gradient• condition imposée: poids = 0


Laplacien5x5

Laplacien9x9


Laplacien 9x9 Représentation 3D


Exemples

Interprétation

∇2I =I i+1, j( )+I i−1, j( )+I i, j+1( )+I i, j−1( )

sommation dans une fenêtre1 2 4 4 4 4 4 4 4 3 4 4 4 4 4 4 4 −4I i, j( )

∇2I =I i+1, j( )+I i−1, j( )+I i, j+1( )+I i, j−1( )+I i, j( )−5I i, j( )

∇2I =−5 I i, j( )− Moyenne sur fenêtre{ }

∇2I =−K I i, j( )−F I i, j( )[ ]{ }

avec F: filtre dans le voisinage de NxN


Applications Détection d’arêtes par passage par zéro Rehaussement du contraste (réf. 2.2.6)

Image brouilléeGaussien 3x3

Image rehausséeLaplacien 3x3


3.5.3 Laplacien de gaussienne

appelé aussi: Opérateur de Marr-HildrethDifférence de GaussiennesChapeau mexicain

Principe: Les variations d’éclairement sont détectées à

plusieurs échelles spatiales Il n’existe pas d’opérateur à taille fixe qui est

effectif à toutes ces échelles Détection optimale opérateur de taille

variable avec un filtre gaussien


Algorithme Choix de l’échelle ( (croissant) de

la gaussienne)

Laplacien de l’image filtrée

Détection des passages par zéro

G∗I

∇2 G∗I( )= ∇2G( )∗I

∇2G x,y( )=−1πσ 4

1−x2 +y2( )2σ 2

⎡

⎣ ⎢ ⎤

⎦ ⎥ e

−x2+y2

( )

2σ2

⎡

⎣ ⎢

⎤

⎦ ⎥


Opérateur chapeau mexicain

que l’on peut approximer par une différence de gaussiennes

∇2G x,y( )=−1πσ 4

1−x2 +y2( )2σ 2

⎡

⎣ ⎢ ⎤

⎦ ⎥ e

−x2+y2

( )

2σ2

⎡

⎣ ⎢

⎤

⎦ ⎥

∇2Gσ x,y( )=LoG≅DoGσe,σ i( )

DoG=1

2πσ e

e

− x2+y2( )

2σe2

−1

2πσ i

e

− x2+y2( )

2σ i2

avec σ i

σe

=1,6

W=2 2σ


W=2 2σ

∇2Gσ x,y( )=LoG≅DoGσe,σ i( )

DoG=1

2πσ e

e

− x2+y2( )

2σe2

−1

2πσ i

e

− x2+y2( )

2σ i2

avec σ i

σe

=1,6


Exemples de masques de LoG


Chapeau mexicain (LoG)22



Implantation Aphelion Différence de gaussienne Attention: Le rapport 1,6 n’est pas

calculé automatiquement


Quelques exemples

Mission de Santa Fechapeau mexicain 13x13


Chapeau mexicain 5x5



Chapeau mexicain 13x13 Seuil positif

Seuil négatif Passages par zéro


Chapeau mexicain 17x17 Seuil positif

Passages par zéroSeuil négatif


Extraction à plusieurs résolutions spatiales

Pour des valeurs de suffisamment éloignés, les ZCs ne sont pas reliés sauf:

• Les arêtes 3D de l’objet 3D imagé apparaissent comme des ZCs dans 2 images d’arêtes consécutives ou plus

• Les ZCs coïncidents disparaissent pour un augmentant lorsque:

– 2 arêtes locales ou plus fusionnent par moyennage ou

– 2 phénomènes indépendants produisent des arêtes dans la même région de l’image mais à des échelles spatiales différentes


3.6 Détection multirésolution d’arêtes

Principes: Détection des arêtes à plusieurs

résolutions Les arêtes correspondent à des

caractéristiques 3D qui apparaissent à plus d’une échelle

On débute à basse résolution Moins d’arêtes bruitées Mais aussi moins bien localisées

On projète à haute résolution


Analyse à échelle spatiale continue.Le signal du bas représente un signal temporel dont on v eut étudier le comporte-ment des passages par zéro de la déri vée seconde en fonction de l’échelle d’analy-se, soit la fréquence de coupure du fi ltre passe-bas. Le graphique du haut illustrele comportement des passages par zéro de la déri vée seconde (maximums/mini-mums locaux de la courbe du bas) en fonction de l’échelle spatiale. Le signal est deplus en plus fi ltré à mesure qu’on progresse le long de l’échelle spatiale. Le graphi-que montre qu’il y a de moins en moins de passages par zéro à mesure que la réso-lution spatiale est diminuée. Il n’y a pas de création de nouveaux passages par zérolorsqu’il y a diminution de la résolution.

Amplitude

Temps

Temps


Image d’entrée

Arêtes bien localiséesmais bruyantes (petit σ)

(Illuminance)

Niveau à hauterésolution

Arêtes mallocalisées (grand σ )

Niveau à basserésolution

Représentation multi-résolution des caractéristiques (arêtes) d’une image d’illumi-nance. La représentation à un niveau donné de résolution spatiale s’obtient en filtrantl’image d’illuminance avec un fi ltre passe-bas puis en détectant les caractéristiquesde l’image filtrée.


Algorithmes Bergholm

Échelle continue Changement de pour assurer

qu’une arête ne se déplace pas de plus d’un pixel

Lindeberg Signaux discrets


3.7 Squelettisation

Documents

N Découvertes n Présentation des équipes et des projets n 3- Extraction des primitives u 3.1 Caractéristiques 3D et 2D u 3.2 Arêtes u 3.3 Gradient et arêtes