3. Analyse et estimation du mouvement dans la vidéo

Mouvement Apparent

CERIMES ©

MPEG7 test set

Projection du mouvement rigide 3D dans le plan-image

Z

Yfyy

Z

Xfxx

0

0Hypothèse : le mouvement observé dans le plan image via changements de luminance correspond à la projection idéale du mouvement 3D des objets de la scène

Mouvement réel/mouvement apparent

a) Insuffisance du gradient spatial

MR - oui

MA - non

b) Changements d’illumination extérieure

MR - non

MA - oui

Détection du mouvement(1)

• Modèle des scènes : la caméra statique, les objets en mouvement

• Méthodes « d’ordre 0 »

Détection du mouvement(2)

• I(x,y,t) - fonction d’intensité lumineuse

• Instants de temps : t, t-dt• (1)La difference temporelle absolue

• Détection :• Si alors le

pixel (x,y) est en mouvement

• Inconvénients : difficultés d’apprentissage du seuil, présence du bruit. (Jain, 79)

),,(),,(,, dttyxItyxItyxFD

SeuiltyxFD ,,

Détection du mouvement(3)

• (2) Prise en compte du bruit et de variations de luminance:

-Pour chaque pixel (x,y) apprentissage pendant de

- - -Pour le couple d’ imagescalcul de- Détection d’un « pixel en mouvement »

si

(Haritaoglu’98)

t ),,(min),(

00 ,...tyxIyxm

tttt

),,(),(00 ,...

tyxIMaxyxMtttt

),,(),,,( dttyxItyxI

tyxFDtyxDyx

,,max),,(),(

),,(),,(),(

),,(),,(),(

tyxDtyxIyxM

outyxDtyxIyxm

• (3) Détection par test des hypothèses statistiques

• Approche par max de vraisemblance.

• Considérons 2 fenêtres centrées sur le pixel (x,y)

Détection du mouvement (4)

(x,y) (x,y)

t t+dt

A1 A2

Détection du mouvement (5)

• Hypothèses:

• H0 : les distributions de la luminance des deux fenêtres possèdent les mêmes caractéristiques statistiques en t et t+dt

• H1 : les distributions sont différentes.

• Modèle de luminance :

2,0),( NyxI

Modèle constant : (A) I(x,y)N(µ,)

H0: pour tout point (x,y) dans A1 et A2 I(x,y)N(µ0,) H1: pour tout point (x,y) dans A1 I(x,y)N(µ1,),

pour tout pixel (x,y) dans A2 I(x,y)N(µ2,),

Détection du mouvement(6)

• Les fonctions de vraisemblance associées

2

20

21,20

2

,exp

2

1

AA

AAAyAx

yxIHL

2

21

1,21

2

,exp

2

1

AA

AAyAx

yxIHL

2

22

2,2 2

,exp

2

1

AA

AAyAx

yxI

Détection du mouvement (7)

0

1

0

1)(ln

H

H

HL

HLR

1 2

21

22

21

20

2 ),(),(

),(

2

1

A AAAAA

AAAA

yxIyxI

yxI

R

RR minmaxˆ

02,1

Test au maximum de vraisemblance :

Rapport logarithmique de vraisemblances

Détection du mouvement(8)

• Pour simplifier

• (méthode de P. Bouthemy et F. Lalande).

0

1

21 ˆˆ2

H

H

nR

),,(,,),,( tyxIdttyxIdttyxFD

0

1

),,(2

1

H

H

dttyxFDn A

Détection à la base de modélisation stochastique

des valeurs de pixels. • Considérons (x0, y0) – un pixel

dans le plan image. • Considérons les valeurs de l’image

I(x0,y0,t). A chaque instant de temps t

- « l’histoire d’un pixel » est connue- - réalisations de la

variable aléatoire X associée à un pixel.

• « processus pixel » :

tiiyxIXXX t 1:,,,...,, 0021

tiX i 1,

Grimson et Stauffer, 1998,2000

• Si on considère une scène idéalement stationnaire, et le bruit Gaussien indépendant, alors

• Néanmoins, les scènes stationnaires naturelles sont caractérisées par changement de luminance, occultations

• En supposant l’indépendance des composantes R,V,B

ttt

Tttt

Tttt

X

XXXP

,,

exp2

1~ 1

2/1

titit

K

ktit XXP

,,1

, ,,

TBVRX ),,(

I2, ltk

• Initialisation : • - sélection du paramètre K =3 ou 5 • -initialisation des gaussiennes et des

poids, algorithme EM, K moyennes, Isodata,..

Mise à jour(1) Pour chaque nouvelle valeur

tester « la correspondance » à une des gaussienne du mélange :

(2) Dans le cas positif :

- «taux d’apprentissage »

Dans le cas négatif : la distribution de poids le plus faible est remplacée par une nouvelle distribution

tX

RVBlX lktlktlt 3,..,15,2 ,,,,,,

0,1,)1( *,*,,1,, tkktktktktk MMM

ttktk X 1,, )1(

,)1(,,

1,2

,2

****

tktT

tkttktk XX

** ,kktX

AX tlkttk ,,','

,

Détection

• Détection : • - trier les gaussiennes selon les valeurs

• Sélectionner B meilleures

• Si parmi les B gaussiennes on ne trouve pas cas positif (k*), alors un pixel d’objet a été détecté.

2/ kkw

TBb

k k

b

1minarg

Exemple

Estimation du mouvement Hypothèse d’invariance de luminance

x

y

Une séquence vidéoen l’absence de bruit:

I(x, y, t) = I(x+dx, y+dy, t+Δt)

d=(dx, dy)T, la projection du déplacement réel 3D dans le plan image.

I(x,y,t) - fonction d’intensité lumineuse

Le champ vectoriel D(x,y)= {(dx, dy)T }

est appelé le champ dense de déplacement

0),,(,,),,( tyxIttdyydxxIdyxDFD

I(x, y , t)t

Flot optique

T

t

y

t

xtyx

,,,

Le vecteur de vitesse au point (x,y) correspond à dt près au vecteur de déplacement

Le champ vectoriel (x,y) est appelé le flot optique ou encore champ de vitesse

t

Idt

y

Idy

x

IdxtyxIdttdyydxxI

),,(,,

Par l ’hypothèse d’invariance de luminance

0

t

I

dt

dy

y

I

dt

dx

x

I

tyx IvIuI OFE/ECMA

Le problème d ’estimation du FO est mal posé.

ECMA (I)

Tdtdydtdxw /,/

Comme alors

tIwI u v

ECMA sous forme vectorielle

L’estimation du mouvement est un problème mal posé. Seul le flot optique normal est observablew

Sous forme vectorielle

Décomposons ,

www

w

tIwwI

est parallèle au gradient local :   flot optique normal  

w

est orthogonale

Une autre vue

t

Iv

y

Iu

x

I

Si u,v sont supposées indépendantes, alors une seule équation pour deux inconnues –

(1) Problème d’unicité de la solution – “problème d’ouverture”

(2) Problème du bruit d’acquisition

(3) Problème d’occultation

ECMA (II)

(1) Illustration du « problème d’ouverture »

Zone découverte : pas de correspondance des pixels avec l’image précédente

flot optique normal

flot optique réel

(3) Illustration du « problème d’occultation »

ECMA (III)

Méthodes d’estimation du mouvement

(x+dx, y+dy)

(x, y)

(dx, dy)

DFD(x, y, d) = I(x, y, t) - I(x+dx, y+dy, t+Δt)

On cherche d=d(θβ) (β modèle du mouvement 2D, θ ses paramètres) tel que DFD(x, y, d) soit minimum.

- Méthodes basées sur l ’ECMA (différentielles)

- Méthodes basées sur la minimisation directe de la DFD ou d ’une mesure basée DFD

- Méthode directes/méthodes paramétriques

Estimation du mouvement dans les algorithmes normalisés (I)

Approche : mise en correspondance (basée bloc)

Critères à optimiser :

MAD= avec

BpFd

ttdpItpI

),(),(min Tyxp ),(

MSE = 2),(),()(

1min ttdpItpI

BCard BpFd

Fenêtre F Bloc B

I(t)I(t-dt)

Estimation par bloc

Objectif : obtenir le champ de déplacement épars

Le FO est supposé constant à l’intérieur d’un bloc

Le critère à minimiser :

Bp

dttdpItpI

),(),(min ou 2),(),(min dttdpItpI

BpFd

It-dt It

FB

Méthode de recherche exhaustive

Estimation « au pixel près »

BpFd

dttdpItpIArgd

),(),(minˆ

It-dt It

L’inconvénient majeur : coût opératoire

Limitations : les dimensions trop faibles de la fenêtre de recherche ne permettent pas d’estimer correctement le vecteur de déplacement

FB

Méthodes de recherche accélérée

Estimation « au pixel près »

1. Recherche à 3 pas,

2. Recherche logarithmique,

3. Recherche « une à la fois »

4. Recherche à 4 pas

……. – méthodes sous-optimales :

Fortes conséquences sur la possibilité d’interprétation du flot optique par bloc;

Recherche à trois pas (Koga’81)

Principe : l’affinage du pas de recherche

1. Pas=4. Evaluer MAD aux pixels « 0 » et « 1 »

Si min(MAD) =MAD(0) – alors bloc stationnaire

Sinon

2. Pas=Pas/2. Evaluer MAD aux pixels « 2 »

3. Pas=Pas/2. Evaluer MAD aux pixels « 3 »

Fenêtre de recherche + 7 pels

0

1

2

1

1

1 1

1

1

1

2 2 2

23

22 2

33

33 3 3

3

Recherche à trois pas (Koga’81)

Le vecteur de déplacement optimal

Modifications :

- Comparaison de min(MAD) avec un seuil T

- Si min(MAD)<T alors arrêt

- Sinon recherche autour de la position courante avec le pas/2 (recherche « logarithmique »).

0

1

2

1

1

1 1

1

1

1

2 2 2

23

22 2

33

33 3 3

3

Recherche en croix (Ghanbari’90)

Le pas de recherche est réduit si

- l’optimum se trouve au centre de la croix ou

- sur le bord de la fenêtre de recherche

0 21

1

1

1

2

254

3

3

3

4

55

Recherche en diamant (Zhu, Ma, MPEG4 VS)

première recherche

si l’optimum se trouve au centre de la croix

sur le bord de la fenêtre de recherche

Estimation du mouvement dans les algorithmes normalisés (II)

Méthode d ’estimation : recherche exhaustive

Précision d ’estimation :

- « au pixel près »

- « au demi-pixel près »

Estimation au pixel près : Z dydxdydxd T ,,),(

Estimation au demi pixel près :

Approches multi-résolution multi-échelle

tt II 0 )( 1lt

lt IgI

1) Construction des pyramides Gaussiennes pour

1, tt II

2) Estimation des paramètres de mouvement en commençant par le niveau le plus élevé

L

3) Propagation

l yxl yx dd ,1, -le facteur de sous-échantillonnage

2

22

2 2exp

21),(

lklkg

Estimation du mouvement dans les algorithmes normalisés (III)

Problèmes spécifiques à la méthode:

- mauvaise approximation des mouvements complexes;

- lissage du champ de déplacement au travers des contours d’occultation;

- « effet de bloc » et coût important de codage de l’erreur dans des schémas du codage avec la compensation du mouvement.