Laboratoire Bordelais de Recherche en Informatique 23/02/2014 3.2.Caractérisation du mouvement et méthodes par comparaison du mouvement 1. Représentation

Laboratoire Bordelais de Recherche en Informatique

11/04/23

3.2.Caractérisation du mouvement et méthodes par comparaison du mouvement 1. Représentation du mouvement dans le plan -

image 2. Modèles du mouvement 3. Méthodes d’estimation

Méthodes directes Méthodes paramétriques Estimation robuste Estimation par bloc

4. Méthodes de la segmentation basées mouvement Méthodes par comparaison du mouvement Méthodes par des mesures de similarité après la

compensation Approches par projections


11/04/23

3.2.1.Représentation du mouvement dans le plan - image

Une séquence vidéo est une image 2D du monde 3D en mouvement

On ne perçoit le mouvement que grâce au changement de la luminance / couleur

Mouvement Apparent


11/04/23

Mouvement réel 2D vs mouvement apparent

Mouvement réel 2D est la projection du mouvement 3D par le système optique de la caméraY

Z

X

YZ

X

à t à t+1

Mouvement apparent _ “flot optique” est observé dans le plan image 2D grâce au changements de la luminance


11/04/23

Mouvement réel 2D vs mouvement apparent (2)

Mouvement apparent est dans le cas général différent du mouvement réel 2D

a)Insuffisance du gradient spatial

MR - oui

MA - non

b)Changements d’illumination extérieure

MR - non

MA - ouiNéanmoins!Hypothèse: Mouvement Apparent=Mouvement reel 2D


11/04/23

Caractérisation locale du mouvement

P

P’

t t+1

d

Tdydxd ,

Vecteur de déplacement élémentaire

Tdtdydtdxw /,/

vecteur vitesse

Premier niveau de caractérisation du mouvement consiste à calculer le flot optique ou “champ de déplacement”

wW dD


11/04/23

3.2.2. Modèles de mouvement

En développant en série de Taylor autour de jusqu’au 1er ordre

Tdydxd ,

gg yx ,

g

g

yy

xx

bb

aa

b

a

dy

dxd

21

21

0

0(9)

xdx

a1 y

dxa

2 x

dyb

1 y

dyb

2

Ici M

Tbbaabaaff 212100 ,,,,, Modèle afffine à 6-paramètres


11/04/23

Modèles affinesExprimant

ItraceMMMMMItraceMM TT 21

21

21

)(21 ddivydy

xdx

batraceM

01

10

21

)(21

ydx

xdy

MM T

drot z

ydy

xdx

hyp

1

ydx

xdy

hyp

2

1221

2112

abab

abab ItraceMMM T

21

=

01

102

21

10

011

21

01

10

21

10

01

21

hyphyprotdivM

Hiérarchie des modèles affines

)(2)(1)()(

)(2)(1)()(

2

1

0

0

gggg

gggg

xxhypyyhypxxrotyydiv

yyhypxxhypyyrotxxdiv

b

a

dy

dx

gy

gx

yyktdy

xxktdx )(

y

x

t

t

dy

dx

111112

111112

ggy

ggx

yykxxtyydy

yyxxktxxdx

g

g

yy

xx

bb

aa

b

a

dy

dx

21

21

0

0

gg

g

g

g

gyyxx

b

a

yy

xx

bb

aa

yy

xx

bb

aa

b

a

dy

dx

5

52

2

43

43

21

21

0

0


11/04/23

3.2.3. Méthodes d’estimation

Objectif : mesurer le mouvement apparent

Applications : indexation vidéo : caractérisation du mouvement de la caméra, suivi des objets

Méthodes :- directes (estimation du flot optique)

- indirectes (parametriques- estimation du modèle global)

Modes : basé-pixel, basé-bloc, basé-région


11/04/23

Estimation du mouvement(1)

Hypothèse principale : conservation de l’intensité lumineuse d’un point le long du trajectoire

n’est jamais nulle à cause du bruit et de changement d’éclairage

0),,(,,),,( tyxIdttdyydxxIdyxDFD

(12)

(x+dx, y+dy)

(x, y)

(dx, dy)

),,( dyxDFD


11/04/23


Critères à minimiser: EQM, MAD

),(

2 )),(,,(1

yxyxdyxDFDEQM min

),(

)),(,,(1

yxyxdyxDFDMAD min

)(min,),(* DEQMArgyxdyxD

Estimation directe

)(min,, *

EQMArgyxd

Estimation paramétrique


11/04/23


Développant dttdyydxxI ,, en série de Taylor

autour de (x,y,t)

t

Idt

y

Idy

x

IdxtyxIdttdyydxxI

),,(,,

et supposant la linéarité de I(x,y,t) on a

Du (12) 0

t

Idt

y

Idy

x

Idx

0

tI

dtdy

yI

dtdx

xI l’équation de contrainte

du mouvement apparent (ECMA)


11/04/23


Tdtdydtdxw /,/Comme alors

tIwI u v

ECMA

Estimation du mouvement est un problème mal posé. Uniquement le flot optique normal est observable

w

Sous forme vectorielle

Décomposons ,

www

w

tIwwI

est parallèle au gradient local

w

est orthogonale


11/04/23


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


11/04/23


(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 »


11/04/23

Méthodes pel-récursives(1)

Méthode de Netravali et Robbins

tdpIdpDFDdd iiiiii ,, )()()()()()1(

Fonctionnelle à minimiser 2,,, tdyxDFDE

avec le gain constant

Méthodes d’optimisation différentielles de premier ordre (descente de gradient)

dEddii

2)()1(

Problème du bruit -> préfiltrage gaussien


11/04/23

Méthodes pel-récursives(2)

Méthode de Walker et Rao

tdpIdpDFD

tdpI

dd iiii

ii

ii ,,

,

)()()()(2)()(

)()1(

Méthode of Cafforio and Rocca

tdpIdpDFD

tdpI

dd iiii

ii

ii ,,

,

)()()()(

22)()(

)()1(

Gain adaptatif en fonction de l’image


11/04/23

Estimation paramètrique(1)

Modèles : affines 1er order ( 4, 6-paramètrs)

Méthodes d’estimation : differentielles de 1er ordre ( déscente de gradient), 2nd ordre ( Gauss-Newton), moindres carrés

Trotdivytxt

,,,

Example:Modèle:

Un modèle globale est supposé dans une zone du plan-image (ex. dans un bloc, dans un région, dans le fond de la scène – mvt. de caméra)

1111

1111

ggy

ggx

yydivxxrottdy

yyrotxxdivtdx


11/04/23

Estimation paramétrique(2)

Fonctionnelle à optimiser :

jRyx

jj

dyxDFDN

MSE),(

2 ))(,,(1

Application de la méthode de Cafforio-Rocca avec le gain adaptatif

)()()1(

2i

j

ij

ij G

N

)(2

)(2

1

),( ,,

...

,,

ij

k

ij

Ryx

i

dyxDFDt

dyxDFDt

G

rot

div

ty

tx

ii tdpI

000

000

000

000

),(

1

22

tytx ,

divtxrotdiv ,,

de même ordre de grandeur que pixels


11/04/23

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 commençant par le niveau le plus élevé

L

3) Propagationl

yxl

yx tt ,1

, -le facteur de sous-échantillonnagell rotdivrotdiv ,, 1

2

22

2 2exp

21),(

lklkg


11/04/23

Estimation robuste (1)

- On suppose le mouvement conforme au modèle paramétrique

On considère - les mesures observées - les mesures conformes au modèle - les résidus

Principe minimiser un critère d’erreur de façon que les valeurs aberrantes de résidus ne

perturbent l’estimation

iY

iyxM ,,

iii yxMYr ,,

ir


11/04/23

Estimation robuste (2) Soit la loi discrète de distribution

d’erreur dépendant du paramètre . La vraisemblance du paramètre est

définie

Le max-vraisemblance est trouvé en

résolvant

Ceci est équivalent à minimiser

P

r

rPPL

PLmaxargˆ

Pr

logargˆ min

Pour toutes les valeurs disponibles de r


11/04/23

est appelé “estimateur” (*)

Supposons que r suit (Estimateur gaussien). (*) est l’estimateur aux moindres carrés

Estimateur de Lorentz


2,0 N

2

2

2,

r

rG

min2 2

2

r

rPr log,

D. Hasler, L. Sbaiaz, S. Susstrunk, M. Vetterli, « Outlier Modeling in Image Matching », IEEE TRans on PAMI, v. 25, n3, march 2003

Estimateur de Geman-McClur

)2

1log(,2

2

r

rL

22

22

/1

/,

r

rrGM


11/04/23

Estimation robuste(4)

yx

iyxMiY,

),(,(minargˆ

Modèle:

yaxaayxv

yaxaayxu

654

321

),(

),(

Taa ),...,( 61

Exemple : Estimateur des moindres carrés médians :

2),(,(minargˆ ii yxMYiMed

-avantage : une grande robustesse

aux erreurs (50%)

- inconvénient : lourdeur de calcul


11/04/23

Minimisation problem is posed as a re-weighted least – square minimisation


i

ii r

rw

)(

i i

yxZi

Zi

ri

ri

wi i

r )),(,(,22

1)( min

i j

iririw

jir

iir 0)(

i

iyxMiYiririwji

irj),(,(),2

21())((

ii rr here


11/04/23


M-estimateurs ),

,),(,((minargˆ

yxiyxMiY

- est opposé de log-vraisemblance des observations conditionnellement au modèle

- sont des fonctions d’influence (des outliers)

'

xx 22 - moindres carrés –l’influence est illimitée

sinon0

si222 CxxCx

- la dérivée d’estimateur de Tuckey


11/04/23

othervise

C

CrifrCrCr

Cr

,6

,24

2

6),(6

24426

othervise

CrifCrrCr

,0

,)(),(

222

Estimateur de Tuckey

La dérivée

résidulerCr ii

i ,,argˆ min



11/04/23


Estimation par de moindres carrés pondérés

i

iyxMiYiririwi

ir ),(,(,221)(

Minimiser le critère revient à calculer les dérivées partielles par rapport à chaque paramètre et les égaler à 0

j

i j

iririw

jir

iir 0)(

On obtient ainsi les coefficients de pondération du moindre-carré

)i

ii r

rw

Méthode d’estimation – itérative en recalculant les poids à chaque itération


11/04/23

Estimation par bloc

Objectif : obtenir le champ de déplacement éparse

Le FO est supposé constant à l’intérieur d’un blocLe critère à minimiser :

Bp

dttdpItpI

),(),(min ou

2),(),(min dttdpItpIBpFd

It-dtIt

B


11/04/23

Méthode de recherche exhaustive

FB

Estimation « au pixel près »

BpFd

dttdpItpIArgd

),(),(minˆ

It-dt It

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

Les estimateurs basés-blocs sont utilisés pour tous les standards du codage vidéo cf. UE « Codage Vidéo »

Documents

Laboratoire Bordelais de Recherche en Informatique 23/02/2014 3.2.Caractérisation du mouvement et méthodes par comparaison du mouvement 1. Représentation