Filtrage Mean Shift - INSA Lyongrenier/wp... · Mean Shift et la théorie de l’estimation pdf,...

Filtrage Mean Shift

Théorie, application,

implémentation

Thomas Grenier

T. Grenier 2

Plan

I. Du filtrage Gaussien au filtrage Mean Shift

via la diffusion anisotrope et le filtrage bilatéral

II. Mean Shift et la théorie de l’estimation

pdf, espace des caractéristiques, noyaux, échelles

III. Applications

filtrage, segmentation, vidéo, à priori

IV. Solutions d’implémentations

I - Du filtrage Gaussien

au filtrage Mean Shift

T. Grenier 4

Introduction

Sens de « filtrage »?

(restauration)

De-noising :

Filtering :

Pour la suite filtrage:

première étape d’un traitement,

(ie. deuxième étape : segmentation, recalage, …)

T. Grenier 5

Filtrage Moyenneur

Convolution par une fenêtre de coefficients

égaux (filtrage linéaire, passe bas):

1D : [1 1 1], [1 1 1 1 1 1 1], …

2D:

3D

111

111

111

111

111

111

111

111

111

… Avec normalisation par la somme des coefficients

T. Grenier 6

Filtrage Moyenneur

original Image bruitée 45

Moyenneur

3x3

Moyenneur

11x11

Profils :

T. Grenier 7

Filtrage Gaussien

Convolution par une fenêtre dont les coefficients

sont fonctions de

-5 -4 -3 -2 -1 0 1 2 3 4 5

0.00

0.02

0.04

0.06

0.08

0.10

0.12

0.14

0.16

0.18

xHxxH12/2/1

2

1exp.)2()( Td

gK

1D 2D

Gaussienne généralisée

T. Grenier 8

Filtrage Gaussien

original 45

Profils :

Filtr. Gauss.

3x3

Filtr. Gauss.

11x11

Image bruitée

T. Grenier 9

Filtrage Gaussien vs. Moyenneur

FFT pour 11 coefficients (puis zéro padding)

Gaussien

Moyenneur

0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0

0.0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1.0

T. Grenier 10

Filtrage Gaussien & Moyenneur

Problème de la localisation des contours…

Problème des transitions rapides

(hautes fréquences)

Transformer les filtres en passe bande ?

Détermination de la bande passante?

Amplification du bruit ?

Utilisation localisée du passe bande ?

T. Grenier 11

Filtrage gaussien et PDE*

Equation de diffusion (isotrope) de la chaleur

*Equations aux Dérivées Partielles

2

2 ),(.

),(

x

txTD

t

txT

Solution analytique (fonction de Green)

0000 ).,().(),( dxtxxGxftxT

tD

xx

etD

txxG ..4

)(

0

20

...4

1),(

avec

Convolutions successives

par un filtre Gaussien !

1D

T. Grenier 12

Filtrage gaussien et PDE

t = 0

t = 1

t = 8

t = 20

t = 60

Diffusion en fonction du temps

T. Grenier 13

Filtrage anisotrope

Idée : modifier l’équation de diffusion isotrope…

- Équation de diffusion isotrope

I).(),I(

cdiv

t

tx

RR sI : image

x = (x1, x2, …, xs)T : position spatiale

t : paramètre artificiel de temps

I( x, t) : valeur de I à la position x à l’instant t

c : constante (scalaire) de diffusion

s : nombre de dimensions spatiales

T. Grenier 14

Filtrage anisotrope

… en une équation anisotrope

I)).,(g(),I(

tdiv

t

tx

x

Rôle de la fonction g(x,t) ?

Pondérer l’amplitude du gradient en I(x,t)

Norme du gradient

),I( tx

comment pondérer ?

n Dimensions

I(x,t)

T. Grenier 15

Filtrage anisotrope

Equation de diffusion de Perona-Malik (1990)

I)).I(g(),I(

div

t

tx

uug ,0)(

|| I|| : amplitude du gradient

g(|| I ||) : fonction d’arrêt aux « bords »

0,

²

²1

1)(

steCK

K

uug

g( u ) : fonction de pondération,

T. Grenier 16

Filtrage anisotrope

Formulation discrète de Perona-Malik

xp

px,px,

x

xx

I)I(II 1 gtt

,III, t

xppx,xp approximation du gradient :

x Voisinage de x

Coefficient de diffusion Stabilité ...

T. Grenier 17

Filtrage anisotrope

t = 1

t = 3

t = 5

t = 20

t = 100

Diffusion Anisotrope,

fonction du nombre d’itérations

t = 0

T. Grenier 18

Filtrage anisotrope

Influence de la fonction de pondération g(x)

Exemple: seuil de filtrage pour le gradient (t =100)

Seuil=60 Seuil=70 Seuil=80 Seuil=255

g(x)

Seuil

xp

px,px,

x

xx

I)I(II 1 gtt

T. Grenier 19

Filtrage anisotrope

original Filtr. Moyen.

3x3

Filtr. Gauss.

3x3

Filtr. Anisotrope

(t=100)

T. Grenier 20

Filtrage anisotrope

Temps ?

Démo VTK+Python: import vtk

# Create the image

reader = vtk.vtkBMPReader()

reader.SetFileName("../Data/Original_2D_Noise45.bmp")

diffusion = vtk.vtkImageAnisotropicDiffusion2D()

diffusion.SetInput(reader.GetOutput() )

diffusion.SetDiffusionFactor(0.1)

diffusion.SetDiffusionThreshold(80.0)

diffusion.SetNumberOfIterations(100)

ia = vtk.vtkImageActor()

ia.SetInput(diffusion.GetOutput())

writer = vtk.vtkBMPWriter()

writer.SetInput(diffusion.GetOutput() )

writer.SetFileName("Output.bmp")

writer.Write()

Vtk4, python2.4

T. Grenier 21

Filtrage anisotrope

Autre forme discrète (Barash 2002)

1

1

1

1

,

,

1

1

1

1

,

1

)(w

)(w.)(I

)(I

i j

ji

t

ji

t

i j

ji

t

t

x

xx

x

),( 21 xxx

),( 21, jxixji x

2

2

(d ( ))

2.w ( )

t

Dt e

x

x

)(I)(d xxtt

Avec :

Image à

l’itération t

-3 -2 -1 0 1 2 3 0.0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1.0

1D

2D

5,0D

T. Grenier 22

Filtrage anisotrope

Bilan:

Permet un filtrage adaptatif Dépendant de la norme du gradient

Introduction d’une notion de distance

Filtrage de données scalaires (niveaux de gris)

Problème du choix des paramètres Nombre d’itérations

Fonction de pondération (et seuil)

Coefficient de diffusion (problème de stabilité)

…

T. Grenier 23

Filtrage bilatéral

Filtrer des données couleurs ?

Filtrage bilatéral (Tomasi 1998)

h

hi

h

hj

ji

t

ji

th

hi

h

hj

ji

t

t

),(w

),(w.)(

)(

,

,,

1

xx

xxxI

xI

TBGR

t III )(),(),()( xxxxI

².2

)()(exp.

².2exp),(w

22

R

tt

S

t

yIxIyxyx

Avec:

Domaine spatial Domaine des amplitudes

T. Grenier 24

Filtrage bilatéral

Bilan:

Permet un filtrage adaptatif Dépendant de l’éloignement spatial des points

Dépendant de l’écart entre les amplitudes des points

Filtrage de données vectorielles (RBG, …)

Problème du choix des paramètres Nombre d’itérations

2 fonctions de pondération (et seuil)

… voisinage, …

T. Grenier 25

Filtrage Mean Shift

On continue de généraliser la forme itérative:

h

hi

h

hj

t

ji

t

ji

h

hi

h

hj

ji

t

g

g

),(

),(.

,

,,

1

xx

xxx

x

dRx

d = s+r, domaine joint : s : spatial,

r : « range » (valeur)

t

r

t

st

x

xx

),(',

'

'

', 21

3

2

1

2

1

3

2

1

2

1

jxixIr

r

r

r

jx

ix

r

r

r

x

x

iii,j

xxExemple en 2D avec

3 composantes couleurs:

T. Grenier 26

Filtrage Mean Shift

On continue de généraliser la forme itérative:

h

hi

h

hj

t

ji

t

ji

h

hi

h

hj

ji

t

g

g

)(

)(.

,

,,

1

xx

xxx

x

t

r

t

st

x

xx

(Fukunaga 1975

Comaniciu 1999)

Processus itératif convergent !!

Toutes les coordonnées évoluent !!

2 seuils à régler: hs, hr

Calculs longs (plus longs que les précédents)

)().()(22

rrss ggg xxx g(x)

Seuils hs et hr

T. Grenier 27

Filtrage Mean Shift

Résultats hs=10, hr=70 hs=3, hr=70 hs=5, hr=70

T. Grenier 28

Tests, image originale

T. Grenier 29

Tests Diffusion anisotrope

200 it.

Seuil Gradient 30

200 it. Seuil Gradient 10

T. Grenier 30

Tests Mean Shift

hs = 10, hr=30

hs = 5, hr=10

II – Mean Shift et

la théorie de l’estimation

T. Grenier 32

Définitions et notions préliminaires

Espace des caractéristiques

Estimation non paramétrique de densité de

probabilité par noyau

Paramètres d’échelle

T. Grenier 33

Espace des caractéristiques

Représenter les caractéristiques des

données (images) dans un même espace

Exemple : image couleur (caractéristique couleur)

Image couleur

Espace des couleurs (RVB)

b

v

r

ix

R

V B

Définition et notions

T. Grenier 34

Espace des caractéristiques

Généralisation et notations

« c » caractéristiques

Chaque caractéristique xj (j=1..c) appartient à

L’espace des caractéristiques est un espace euclidien

Un vecteur de l’espace des caractéristiques est noté

Chaque donnée d’entrée permet d’obtenir un vecteur

dans l’espace des caractéristiques

TT

c

T

j

TTxxxxx ,,,,, 21

cdddd RRRR 21

[Schölkopf '99]

jdR

cdddd 21

ix

i

i

i

ii

p1=s

p2

p3

pc

ix

Définition et notions

T. Grenier 35

Espace des caractéristiques

Concentration de l’information

dans l’espace des caractéristiques =

information significative

Estimation de densité dans

l’espace des caractéristiques ?

Définition et notions

T. Grenier 36

Estimation de densité

Histogramme : une technique d’estimation de densité Fixer le nombre de classes largeur des intervalles de valeurs

Compter le nombre de points tombant dans chaque intervalle

Espace des caractéristiques (2D) Histogramme (20x20 classes)

0

2

4

6

8

10

12

14

Z

02

46

810

1214

1618

20

X0

2

4

6

8

10

12

14

16

18

20

Y

0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0 5.5

0

20

40

60

80

100

120

²

20x20 classes

Définition et notions

T. Grenier 37

Estimation de densité

Histogramme : une technique d’estimation de densité Fixer le nombre de classes largeur des intervalles de valeurs

Compter le nombre de points tombant dans chaque intervalle

Espace des caractéristiques (2D) Histogramme (5x5 classes)

0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0 5.5

0

20

40

60

80

100

120

5x5 classes

0

10

20

30

40

50

60

Z

0.00.5

1.01.5

2.02.5

3.03.5

4.04.5

5.0

X0.0

0.5

1.0

1.5

2.0

2.5

3.0

3.5

4.0

4.5

5.0

Y

Définition et notions

T. Grenier 38

Estimation non paramétrique

de densité par noyau Estimateur de « Parzen »

KH(x) : noyau

Fonction de Rd dans R

H : matrice de paramètres d’échelle

matrice carrée (dxd), symétrique et définie positive

(souvent diagonale)

n

i

iKn

f1

)(1

;ˆ xxHx H

1)( xxH dK

[Parzen ‘62][Cacoullos ’66]

1D

0 10 20 30 40 50 60 70 80 90 100

0.000

0.005

0.010

0.015

0.020

0.025

g a u ssK H

x

f̂

ix

0 10 20 30 40 50 60 70 80 90 100

0.00

0.05

0.10

0.15

0.20

0.25

0.30

0.35

0.40

0.45

0.50

H n : nombre de points xi

Définition et notions

T. Grenier 39

0 10 20 30 40 50 60 70 80 90 100

0.000

0.005

0.010

0.015

0.020

0.025

0.030

0.035

Estimateur adaptatif

: noyau

Fonction de Rd dans R

Hi=H(xi): matrices de paramètres d’échelle (adaptatifs)

matrices carrées (dxd), symétriques et définies positives

(souvent diagonales)

1)( xxH dKi

[Abramson ‘82]

1D

g a u ssiK H

Hi

x

f̂

ix

n

i

ii iK

nf

1

)(1

;ˆ xxHx H

0 10 20 30 40 50 60 70 80 90 100

0.00

0.05

0.10

0.15

0.20

0.25

0.30

0.35

0.40

0.45

0.50

n : nombre de points xi

)(xH iK

Estimation non paramétrique

de densité par noyau

Définition et notions

T. Grenier 40

Estimation

non paramétrique de densité par noyau

Illustration 2D

0

2

4

6

8

10

12

14

16

18

Z

0 1 2 3 4 5 6 7X

0

20

40

60

80

100

120

Y0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0 5.5

0

20

40

60

80

100

120

2

2

20

05,0H

Espace des caractéristiques (2D)

Estimation de densité (Parzen)

Hx;f̂-10 -5 0 5 10

-10

-8

-6

-4

-2

0

2

4

6

8

10

)(xH gaussK = H

Définition et notions

T. Grenier 41

0 1 2 3 4 5 6 7

0

20

40

60

80

100

120

0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0 5.5 6.0

40

50

60

70

80

90

100

110

0 1 2 3 4 5 6

40

50

60

70

80

90

100

110

120

Paramètres d’échelle

2

2

10

01,0H

2

2

200

02H

2

2

20

05,0H

)(xH gaussKIso-contours des estimations (avec )

Analyse

fine

Analyse

grossière

Augmentation des

paramètres d’échelle

Définition et notions

T. Grenier 42

Paramètres d’échelle

Scale-space

representation

1;G x

2;G x

; kG x

Laplacian of

Gaussian (LOG)

f x

1( ; )LOG x

2( ; )LOG x

( ; )kLOG x

2

1;G x

2

2;G x

2 ; kG x

Caractéristiques pertinentes:

(x,σ) maximisant L

2

2

22

26

2;

2

xx

LOG x e

2D LOG filter

with scale σ

1.., :

, ;

kx f

L x LOG x f x

x

y

σ

3D scale-space

representation

[Lindeberg 1999]

T. Grenier 43

Paramètres d’échelle

Scale-space

representation

1;G x

2;G x

; kG x

Laplacian of

Gaussian (LOG)

f x

1( ; )LOG x

2( ; )LOG x

( ; )kLOG x

2

1;G x

2

2;G x

2 ; kG x

[Lindeberg 1999]

250 strongest responses

(Large circle = large scale)

Maximize

Yaron Ukrainitz & Bernard Sarel

T. Grenier 44

Intérêts pour les traitements

Traitement Données Espace des

caractéristiques

Paramètres d’échelle (adaptatifs)

H (ou Hi)

Filtrage

Segmentation

Choix de

K et H ?

KH

[Witkin ‘83]

[Guigues ‘03]

Définition et notions

T. Grenier 45

Choix des paramètres

d’échelle et du noyau Noyau et échelle optimaux

Calcul de l’Erreur Quadratique Moyenne Intégrée (EQMI)

EQMI asymptotique (n très grand) et approximations relations et hypothèses de convergence entre H et n

hypothèses sur K

approximations de Taylor

Solution:

xxHxHx dffEfEQMI .)();(ˆ);(ˆ2

dRdKKR xx).²()(

)4/(1

222

2 )().(.

)(.

d

opt

dfKn

KRdh

xx

dépend de f dépend de K

IΗ .2h

Ajouter une hypothèse sur f

dR

T dKK xxxxI )(.).(2

Définition et notions

T. Grenier 46

Noyau et échelle optimaux

Hypothèse : f gaussienne Noyau optimal = noyau d’Epanechnikov

Pas d’hypothèse sur la densité f Solution dans le cas 1D

4

111 )2).(4.(..8 dd

de dnvh Echelle optimale:

Méthode du plug in [Sheather ‘91]

5/1

2

2 )''().(.

)(

fRKn

KRhopt

Estimations successives

(estimation non paramétrique

par noyau)

vd : volume hyper

sphère unité

nonsi

sidvK

TT

de

0

1)1).(2.(.2

1

)(1 xxxx

x

Choix d’un noyau K

-2.0 -1.5 -1.0 -0.5 0.0 0.5 1.0 1.5 2.0

0.0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1.0

eK

Définition et notions

T. Grenier 47

Paramètres d’échelle

Généralisation à l’espace des caractéristiques

K ?

Paramètres

DonnéesDonnées

Coordonnées

spatiales

cH

H

H

H

H

0

03

2

1

Caractéristiques

ci

i

i

i

i

,

3,

2,

1,

x

x

x

x

x

i

i

i

2H

3H

cH

1H

i=1..n

d

i Rx

i=1..n

ii

p1=s

p2

p3

pc

1R1,

d

i x

2R2,

d

i x

3R3,

d

i x

cd

ci R, x

Définition et notions

T. Grenier 48

Noyau et paramètres d’échelle

Noyau et échelle

Profil k du noyau sphérique K

Forme générale de K pour l’espace des

caractéristiques

produit de noyaux sphériques

1)( dRdK xx)()( 2/12/1

xHHxH

KK

)(.)( , xxxT

dk kCK

c

j

jj

T

jjdk

c

j

j kCKjj

1

1

,

2/1

1

..)( xHxHxH

Constante de normalisation

i

i

i

2H

2

3h

cH

sH

ii

p1=s

p2

p3

pc

s

si R, x

R3, ix

cd

ci R, x

2R2,

d

i x

R)( uk

Définition et notions

T. Grenier 49

Définition et notions : Bilan

• Représentation des données d’entrée dans l’espace

des caractéristiques (nuage de points)

• Définition de l’estimation de densité par noyau dans

l’espace des caractéristiques:

• Cette estimation dépend des paramètres d’échelle H

et du noyau K : étude du choix optimal

(au sens du critère de l’EQMI)

Hx;f̂

Mise en œuvre en

filtrage et segmentation d’images

T. Grenier 50

Principe Mean Shift

État de l’art

Historique

Application

Fonctionnement

Lien avec l’estimation non paramétrique

Principe de convergence

Illustrations

T. Grenier 51

Présentation du mean shift

Définition:

estimateur non paramétrique du gradient

de la densité de probabilité

Premières références

inventé par Fukunaga (reconnaissance de forme)

généralisation du formalisme par Cheng

application au filtrage et à la segmentation

d’image

[Fukunaga ‘75]

[Cheng ‘95]

[Comaniciu ‘97] [Comaniciu ‘99]

Principe Mean Shift

T. Grenier 52

Présentation du mean shift

Etat de l’art (surtout applications)

Filtrage et segmentation d’image Images couleurs [Comaniciu ‘99]

Imagerie SAR [Cellier ’05]

Suivi d’objet sur séquence vidéo Suivi de joueur [Jaffre ‘03]

Suivi mouvement cardiaque en imagerie échographique [Zhou ‘05]

Maillage Segmentation [Yamauchi ‘05]

Mean shift géodésique [Shamir ‘04]

Grande variété d’applications : exploitation de l’espace des caractéristiques

[Comaniciu ‘99]

1 15

23 30

[Zhou ‘05]

Principe Mean Shift

T. Grenier 53

Principe : recherche des modes

Mode = maximum d’une densité de probabilité

Un mode caractérise une densité de probabilité

Une région est caractérisée par une densité de probabilité (plusieurs régions plusieurs modes)

Trouver à quel mode appartient une donnée trouver à quelle région appartient la donnée

f

modes

0)(ˆ

xf

2x1x

3x

I

y

x

ix

xI

f̂

1

ˆxf

x1,I

2

ˆxf

x2,I x3,I

Principe Mean Shift

T. Grenier 54

Principe: recherche des modes

Estimations locales,

basées sur un échantillon aléatoire

Principe Mean Shift

0 10 20 30 40 50 60 70 80 90 100 0.0000

0.0002

0.0004

0.0006

0.0008

0.0010

0.0012

0.0014

0.0016

0.0018

0.0020

Image Estimations de la pdf

T. Grenier 55

Principe : recherche des modes

Gradient de l’estimation

n

i

iKn

xfxf1

)(1

)(ˆ)(ˆ xxH

.

.).(),,(

2

2

,dk

dgkkN

j

j

ijij xxxx HH

: distance de Mahalanobis (au carré)

de la caractéristique j

Solution

simple

(littérature)

Solution

générale

(proposition)

?0)(ˆ

xf

n

i

i

i

n

i

i

dg

dg

1

2

1

2

,,

.,,

Hxx

xHxx

x

n

i

jij

n

i

jijij

j

kN

kN

1

,

1

,,

),,(

).,,(

H

H

xx

xxx

x

jijj

T

jijd ,

1

,

2 . xxHxx

ukug ')(

avec:

c

j

ji dkk1

2 .)( xxH

j=1..c

Principe Mean Shift

T. Grenier 56

Principe : recherche des modes

Calcul itératif des racines du gradient

n

i

i

t

i

n

i

i

t

t

dg

dg

1

][

1

][

]1[

,,²

.,,²

Hxx

xHxx

x

n

i

ji

t

j

n

i

jiji

t

jt

j

kN

kN

1

,

][

1

,,

][

]1[

),,(

).,,(

H

H

xx

xxx

x

x[0]=x Solution

simple

(littérature)

Solution

générale

?0)(ˆ

xf

Remarque: toutes les caractéristiques

de x évoluent

b

g

r

y

x

t ][x

'

'

'

'

'

]1[

b

g

r

y

x

tx

amplitude

spatial

Pour chaque caractéristique j

j=1..c

Principe Mean Shift

T. Grenier 57

Procédures mean shift

Deux procédures pour le calcul itératif :

blurring

nonblurring

(convergence montrée par les auteurs pour les deux procédures)

Procédure nonblurring de Comaniciu

{xi} i=1..n : ensemble des données d’entrée (dans Rd)

{yi} i=1..m : ensemble de points de Rd

Pour chaque yi

yi y [0]

Calculer :

[Cheng ‘95]

[Fukunaga ‘75]

exploité par Comaniciu [Comaniciu ‘99]

jusqu’à convergence

mode]1[

i

tyy

n

i

i

t

i

n

i

i

t

t

dg

dg

1

][

1

][

]1[

,,²

.,,²

Hxy

xHxy

y

][]1[ ttyy

Principe Mean Shift

T. Grenier 58

Procédure mean shift nonblurring

Illustration

I

y

x

y

'

'

'mode

I

y

x

y

Recherche du mode

spatial x et y

Noyaux gaussiens,

paramètres d’échelle optimaux

'

'mode

y

xsy

'mode

Iyr

r

s

y

yy

mode

sysy

-20 0 20 40 60 80 100

0.0e+000

5.0e-006

1.0e-005

1.5e-005

2.0e-005

2.5e-005

I

mode

ry

ry

niveaux de gris I

Principe Mean Shift

T. Grenier 59

Procédure mean Shift nonblurring Principe Mean Shift

T. Grenier 60

Procédure mean Shift nonblurring Principe Mean Shift

T. Grenier 61

Procédure mean Shift nonblurring Principe Mean Shift

T. Grenier 62

Procédures mean shift

Deux procédures pour le calcul itératif :

blurring

nonblurring

(convergence montrée par les auteurs pour les deux procédures)

Procédure blurring de Fukunaga

{xi} i=1..n : ensemble des données d’entrée (dans Rd)

Jusqu’à convergence

Calculer les x[t+1] à partir des x[t]

[Cheng ‘95]

[Fukunaga ‘75]

exploité par Comaniciu [Comaniciu ‘99]

n

i

t

i

t

t

i

n

i

t

i

t

t

dg

dg

1

][][

][

1

][][

]1[

,,²

.,,²

Hxx

xHxx

x

it

i

t

i ,][]1[xx

Principe Mean Shift

plus dur…

La position des xi évolue

T. Grenier 63

Procédure mean Shift blurring

xi[0]

xi[1] xi

[2] xi[3]

xi[4] xi

[5] xi[conv]

Principe Mean Shift

III – Applications du Mean Shift

Filtrage

Segmentation

Suivi vidéo

A priori

T. Grenier 65

Application du mean shift

Grande variété d’application:

Utilisation de l’espace des caractéristiques

Filtrage et segmentation d’image

Images couleurs [Comaniciu ‘99]

Imagerie SAR [Cellier ’05]

Suivi d’objet sur séquence vidéo

Suivi de joueur [Jaffre ‘03]

Suivi mouvement cardiaque en

imagerie échographique [Zhou ‘05]

Maillage

Segmentation [Yamauchi ‘05]

Mean shift géodésique [Shamir ‘04]

[Comaniciu ‘99]

1 15

23 30

[Zhou ‘05]

T. Grenier 66

Algorithmes de filtrage mean shift

Filtrage : associer à chaque xi son mode ximode

on notera {zi} : l’ensemble des points filtrés

Deux algorithmes

Variante : paramètres d’échelle adaptatifs [Comaniciu ‘01][Grenier ‘05]

I

y

x

ix

Filtrage Libre (MSL)

'

'

'mode

I

y

x

ii xz

I’

Filtrage Contraint (MSC)

'I

y

x

iz

I’

T. Grenier 67

Filtrage MS image synthétisée

hs=10, hr=70

Mean Shift

Original

His

togra

mm

es

Filtrage Mean Shift Contraint

T. Grenier 68

Filtrage MS image synthétisée

hs=10, hr=70

Mean Shift Libre

Mean Shift

Contraint

Original

3D 3D

Mean Shift

T. Grenier 69

Filtrage MS image RGB (Léna)

MSC

hs=10, hr=30

T. Grenier 70

Filtrage MS image RGB

MSL

hs=10, hr=30

5 Dimensions

T. Grenier 71

Filtrage de …

Maillage

[Yamauchi 2005]

Octaèdre bruité:

T. Grenier 72

Segmentation Mean Shift ?

Pas de segmentation Mean Shift

mais des segmentations basées sur des

prétraitements « Mean Shift »

prétraitements : filtrage, estimation de paramètres…

Exemples de processus de segmentation:

Filtrage croissance de région (multidimensionnelle)

Estimation de paramètres (i.e. d’un modèle

géométrique) mise en correspondance du modèle

T. Grenier 73

Segmentation après filtrage Mean shift

Problème : segmenter les données dans

l’espace des caractéristiques

Seuillage

Méthodes de Clustering

Croissance de région [Comaniciu 99]

…

Reste à définir la croissance de région pour

l’espace des caractéristiques…

T. Grenier 74

Croissance de Région

Présentation / rappel

Introduite par Zucker

Principe

désignation de germes initiaux

agglomération des points situés à la périphérie de cette région

respectant les conditions d’agglomération

[Zucker ’76]

points candidats : nouveau point germes initiaux

R[t] R[t+1]

T. Grenier 75

Croissance de région multidimensionnelle

Comment généraliser le principe de voisinage ?

Définition d’un voisinage:

outils pour la distance: noyaux et échelles

Matrices de paramètres d’échelle Adaptatives ou non

K : produit de noyaux K(.) fonction de n’importe quelle variable

cH

H

H

0

01

c

j

jjKK

1

)( xx HH

yxxy ,);( dXVy y

T. Grenier 76

Croissance de région

Algorithme

Choisir un germe dans l’espace des caractéristiques

À partir de ce germe regrouper itérativement les points

respectant les critères d’homogénéité

Quand on ne peut plus ajouter de nouveaux points:

choisir un nouveau germe parmi les points non regroupés

dans une région et définir une nouvelle région.

Répéter tant qu’il reste des points non affectés à une

région

(supprimer les régions de faibles effectifs)

T. Grenier 77

Exemple de croissance de Région

Logiciel EDISON

Original

Image filtrée (MS*) Segmentation Frontières

T. Grenier 78

Croissance de région

initiale

2̂

A

y

x

iz

caractéristiques

spatiales

caractéristiques

des amplitudes

x

y

K : Epanechnikov

Hs = 102.I et Hr = 702.I : permettent d’obtenir un échantillon représentatif

Hs

Hr

A Ω

2̂

A Ω

2̂

T. Grenier 79

Croissance de région

1ière itération

initiale

A Ω

2̂

A Ω

2̂

A Ω

2̂

A Ω

2̂

spatial

amplitudes

Filtrage

Mean Shift

T. Grenier 80

Segmentation de …

Maillages

Vaisseaux

[Yamauchi 2005]

[Tek 2001]

T. Grenier 81

Ajout d’a priori ?

Transformation de l’a priori dans un espace

Hough, pdf, échelle, polynôme, …

Définition d’une métrique adaptée à l’espace

considéré

ML, Battacharya,

Utilisation des Mean shift pour la recherche des

maximum dans l’espace

Adaptation de l’échelle

Modification de l’a priori

T. Grenier 82

Mean Shift Adaptatif avec a priori

Image filtréeConnaissance à

priori

Image

Largeur de la réponseimpulsionnelle

Filtrage Mean Shift

Adaptatif en

Amplitude et en

Spatial (MSA A+S)

T. Grenier 83

Mean Shift Adaptatif avec a priori

À priori : carte d’échelle

ri

si

ih ,

,

0

0HH

)(xK

Filtrage Mean Shift

Adaptatif en Amplitude et

en Spatial (MSA A+S)

Filtrage Mean Shift

Adaptatif en Amplitude et

en Spatial (MSA A+S)

i

i

p1=s

p2=r

i

ii

p1=s

p2=r

si,H if x~

rih ,

0h

ri

si

ix ,

,xx

Échelle optimale

(plug in)

Moyenne géométrique

des xi,r

Estimation

pilote

Matrices d’échelles

adaptatives

DonnéesDonnées

Réponse

impulsionnelle

Réponse

impulsionnelle

i

s

i

r

i

s

i

r

Méthode de filtrage

adaptative (MSA A+S)

iz

Données

d’entréeDonnées

filtrées

A priori sur le

système

d’acquisition

A priori sur le

système

d’acquisition

[Grenier 05]

T. Grenier 84

Mean Shift Adaptatif avec a priori

Donnée originale MS classique MS avec a priori

seuillage seuillage seuillage

his

togra

mm

e

T. Grenier 85

Tracking

Modification du formalisme Mean Shift:

recherche d’un motif dans une image

[Dorin Comaniciu, 2003]

T. Grenier 86

Tracking

Modification du formalisme Mean Shift:

recherche d’un motif dans une image avec Mean Shift

Adaptatif et un a priori « multi-model » [Georgescu 2004]

T. Grenier 87

Encore un exemple

[Zhou 2005]

IV – Solutions d’implémentations

T. Grenier 89

Problème

Ce qu’il faut (au minimum) implémenter

.

.).(),,(

2

2

,dk

dgkkN

j

j

ijij xxxx HH

: distance de Mahalanobis (au carré)

de la caractéristique j

Solution

simple

(littérature)

Solution

générale

jijj

T

jijd ,

1

,

2 . xxHxx

ukug ')(

avec:

c

j

ji dkk1

2 .)( xxH

ou

n

i

i

t

i

n

i

i

t

t

dg

dg

1

][

1

][

]1[

,,²

.,,²

Hxx

xHxx

x

n

i

ji

t

j

n

i

jiji

t

jt

j

kN

kN

1

,

][

1

,,

][

]1[

),,(

).,,(

H

H

xx

xxx

x

T. Grenier 90

Problème

Cout algorithmique théorique Temps de référence :

T = Calcul de Somme pondérée

Calcul de x[t+1] en O(n)

Pour un pixel : t=0…tconv

Ex. Filtrage Mean Shift nonblurring

Pour une image de p pixels

FiltrageMeanShift =

n

i

i

t

i

n

i

i

t

t

dg

dg

1

][

1

][

]1[

,,²

.,,²

Hxx

xHxx

x

convtnpO ..

T. Grenier 91

Exo, filtrage Mean Shift blurring

On dispose d’une image en niveaux de gris de

n x n pixels.

Chaque pixel est représenté par un vecteur 3D

(position spatiale, amplitude) dans la matrice E:

E(x1,x2) = (x1,x2,I)T , avec I le niveau de gris du pixel

(x1,x2 )

Ecrire le programme permettant de filtrer l’image

E en utilisant la procédure Mean Shift blurring

avec noyau gaussien, hs, hr,

T. Grenier 92

Problème

Rappels pour calcul (solution classique, non générale)

n

i

i

t

i

n

i

i

t

t

dg

dg

1

][

1

][

]1[

,,²

.,,²

Hxx

xHxx

x

iT

id xxHxx 12 .

ukug ')(

Distance de Mahalanobis (au carré):

)()( 2/12/1xHHxH

KK

)(.)( , xxxT

dk kCK

Dérivée du profil:

Ex. pour Epanechnikov:

sinon0

11)(

usiuge

nonsi

sidvK

TT

de

0

1)1).(2.(.2

1

)(1 xxxx

x

T. Grenier 93

Dans la pratique

Noyau : Epanechnikov sans prise en compte des dérivées des autres dimensions

Noyau sphérique

g() = fonction porte (seuillage)

Matrice d’échelle diagonale hs, hr

Utilisation de l’algorithme nonblurring Pas de modification des données servant à l’estimation

(les xi sont constants)

Estimation sur les points du voisinage

Faible nombre d’itérations tC

Pas de recherche de la convergence exacte

Filtrage de quelques points de l’image

n

i

i

t

i

n

i

i

t

t

dg

dg

1

][

1

][

]1[

,,²

.,,²

Hxx

xHxx

x

convC tt

sshn 12

Tessellate the space

with windows Run the procedure in parallel

Filtrage de quelques points

The blue data points were traversed by the windows towards the mode

Filtrage de quelques points

T. Grenier 96

Dans la pratique

Implémentation de versions approchées mais

efficaces…

Temps réel pour tracking (vidéo, séquence US)

Qq secondes pour filtrage d’image 256²