MOUVEMENT

Objectifs : • Présenter les concepts de base, l’importance et les problèmes liés à l’analyse du mouvement ;

• Comprendre les notions de champs de mouvement et de flot optique ainsi que leurs liens;

• Connaître l’équation d’invariance de la luminance;

• Savoir implémenter des méthodes de calcul de flot optique.

•Savoir implémenter des méthodes de tracking et apprendre la technique de filtrage de Kalman.

Introduction

Nous allons à présent nous occuper de l’information visuelle que l’on peut extraire à partir des changements spatio-temporels survenant dans une séquence d’images.

Séquence d’imagesUne séquence d’images est une série de N images, ou frames, acquises à des instants du temps discret tk=t0+kt, où t est un intervalle de temps fixe, et k=0, 1, …, N-1.

Remarque : nécessité d’un “frame grabber” capable de stocker des frames à des taux rapides. (“Frame rate” : t =1/24s et “field rate” : t =1/30s). Il vous appartient de définir le t utile à votre problème et représentatif en terme d’échantillonnage temporel de la réalité des mouvements continus dans votre séquence. Persistence rétienne : 1/12s -> illusion vidéo ?

Hypothèse : MOUVEMENT VARIATION d’INTENSITESi l’on suppose que les conditions d’illumination ne varient pas () et que les surfaces sont lambertiennes(), les changements de luminance dans l’image sont dus à un mouvement relatif entre la caméra et la scène :

• Caméra mouvant devant une scène statique;• Parties de la scène mouvante devant une caméra statique;• Caméra et objets mouvant ensemble.

Importance du mouvement visuel1. Le mouvement apparent d’objets sur le plan image est un

indice visuel important pour comprendre la structure et le mouvement 3D dans une scène :

Structure 3D à partir du mouvement 2D …

Ou forme ….

AnimatedModel

AnimatedPointSet

file:///../../../../../../../../../../../../../../../../../../../../../../../../../users/crip5/lomn/ENSEIGNEMENT/Images/ComputerVision/AnaSeqVid/Publis/armAndBody.avifile:///../../../../../../../../../../../../../../../../../../../../../../../../../users/crip5/lomn/ENSEIGNEMENT/Images/ComputerVision/AnaSeqVid/Publis/NBM.movfile:///../../../../../../../../../../../../../../../../../../../../../../../../../users/crip5/lomn/ENSEIGNEMENT/Images/ComputerVision/AnaSeqVid/Publis/NBM.mov

Importance du mouvement visuel• Les systèmes biologiques utilisent le mouvement visuel

pour inférer des informations sur le monde 3D avec peu de connaissance a priori sur celui-ci

http://nivea.psycho.univ-paris5.fr/FeelingSupplements/BlindSpotFillingInExperiments.htm

https://www.verywellmind.com/why-do-you-have-a-blind-spot-2794880

http://nivea.psycho.univ-paris5.fr/FeelingSupplements/BlindSpotFillingInExperiments.htmhttps://www.verywellmind.com/why-do-you-have-a-blind-spot-2794880

Détection de changement

Qu'est-ce qu'on peut inférer à partir du mouvement ?

Analyse par Flot optique

Tracking

Model-based tracking

Structure From Motion

Time-to-ImpactIl est possible de calculer le temps, , nécessaire à la barre pour atteindre la caméra seulement à partir d’informations images. C’est-à-dire sans connaître la taille réelle de la barre ou sa vélocité dans l’espace 3D.

f

L

l

D0-Vt=D(t)D0=D(0)

V= cste

O

Z

L,V, f et D0 sont inconnus mais on peut écrire : τ=DV

La taille apparente de la barre l(t) à l’instant t sur le plan image s’écrit :

l( t )=f LD

d'où l' ( t )=dl( t )dt

=−f LD2

dDdt

=f LVD2

d'où τ=l( t )l' ( t )

Quelles informations extraire ?

Ce qui se traduit en terme de traitement d’images …

RECONSTRUCTION 3D

Les 2 Problématiques Informatiques

1. Le problème de la mise en correspondances complexe (ou recalage) : Quels éléments d’une trame correspondent à quels éléments de la trame suivante de la séquence ?

On empruntera deux voies possibles :

• Les méthodes différentielles : en sortie, on obtiendra des mesures denses, cad, calculées en chaque pixel image. Elles utilisent des dérivées temporelles du signal et donc

nécessitent des séquences finement échantillonnées.

• Les méthodes de Matching : en sortie, on obtiendra des mesures éparses, cad, calculées seulement en un sous-

ensemble des pixels images -> Filtrage de Kalman

• Motion: N frames

baselinebaseline

timetime

• Stereo: Two or more frames

Différence principale entre Mouvement et Stéréo :

Comme les séquences d’image sont généralement échantillonnées temporellement à des taux élevés, les

différences spatiales (disparités) entre trames consécutives sont, en moyenne, plus petites que celles de paires stéréo

typiques.

Du coup,

• Grâce aux nombreuses trames échantillonées de façon proche disponibles pour l’analyse d’image :

-> les méthodes utilisant des primitives peuvent être plus efficaces grâce aux techniques dites de suivi ou tracking, qui exploitent l’historique du mouvement des primitives pour prédire les disparités dans la trame suivante.

•Grâce aux différences spatio-temporelles généralement petites entre trames consécutives :

-> le problème de correspondance devient le problème de l’estimation du mouvement apparent de motifs lumineux de l’image, que l’on appelle généralement le flot optique.

Un parallèle intéressant :La vision stéréoscopique fait référence à la capacité d’inférer de l’information sur la structure 3D et les distances 3D d’une scène à partir d’au moins deux images optiques prises de points de vue différents

T+xl−xrZ−f

=TZ

d'où Z=f Td

avec d=xr−xl

Le problème de la correspondance

Left RightRecherche exhaustive ?

Algo CORR_MATCHINGINPUT : • Paire stéréo d'images Il et Ir. • Soient pl et pr les pixels dans l'image droite et gauche. 2W+1 la taille en pixels de la matrice de corrélation. R(pl) la région de recherche dans l'image droite associée à pl.• Soit (u,v) une fonction de deux valeurs de pixel.) une fonction de deux v) une fonction de deux valeurs de pixel.aleurs de pixel.

Pour chaque pixel pl=[i,j]T de l'image gauche :• Pour chaque déplacement d=[d1,d2]TR(pl) calculer :

• La disparité de pl est le v) une fonction de deux valeurs de pixel.ecteur qui maximise c(d) sur R(pl) :

OUTPUT : tableau de disparités (disparity map), une pour chaque pixel de Il.

c (d )= ∑k=−W

W

∑k=−W

W

Ψ ( I l( i+k,j+1) ,I r ( i+k−d1 ,j+1−d2 ))

d̄= [ d̄ 1 , d̄ 2 ]T

{c ( d ) }

C ( x,y,d )=∑i,j[ (I 1 ( x+i,y+j)− I1 ( x,y ) )−(I 2 ( x+i+d,y+j)− I 2( x+d,y )) ]

2

√∑i,j (I 1 ( x+i,y+j)−I 1( x,y ))2∗√∑i,j (I 2 ( x+i+d,y+j)− I 2( x+d,y ))

2

Les 2 Problématiques Informatiques

2. Le problème de la reconstruction : Etant donné un certain nombre d’éléments correspondants, et éventuellement la connaissance des paramètres intrinsèques de la caméra, que pouvons-nous dire au sujet des mouvement et structure 3D de la scène observée ?

Différence principale entre Mouvement et Stéréo :

• Contrairement à la stéréo, dans le mouvement, le déplacement relatif 3D entre la caméra d’observation et la scène observée n’est pas nécessairement causé par une

transformation rigide 3D unique.

• La problématique de reconstuction 3D à partir du mouvement est plus délicate que dans le cadre

stéréoscopique car il y a une sensibilité accrue au bruit en raison d’une ligne de base entre trames consécutives du

point de vue stéréo très petite.

Carte de disparité (à droite) contre flot optique (à droite)

Hypothèse forte de ce coursIl y a seulement un mouvement rigide relatif entre la caméra et la scène observée, et les conditions d’illuminations ne changent pas dans le temps.

Remarque : ceci implique que les objets 3D observés ne peuvent bouger avec des mouvements différents. Si cela est vraisemblable dans le cas d’un bâtiment observé par un passant se promenant, cette hypothèse est régulièrement violée :• Matches de foot;• Traffic routier ou urbain;• Objets déformables comme les vêtements ou la danse.

Du coup, si la caméra observe plus d’un objet mobile, ou que simplement vous ne pouvez pas faire l’hypothèse d’une caméra se déplaçant dans un environnement statique, un troisième sous-problème doit être envisagé :

La 3ème problématique informatique3. Le problème de la segmentation :

quelles sont les régions du plan image qui correspondent à différents objets mobiles ?

Matching Problem

Regions of different moving objets : Segmentation

Problem?

Le champ de déplacement d'objets rigides

Objectifs : • Prendre contact avec la théorie et la géométrie du champ de mouvement ou de déplacement (motion field);

• Comparer la représentation des disparités dans le mouvement ou la stéréo;

• Analyser deux cas spéciaux de déplacement rigide;

•[ Introduire la notion de parallaxe de mouvement.]

Champ de mouvement ou de déplacementLe champ de mouvement est un champ de vecteurs 2D représentant les vélocités des points images, induit par le mouvement relatif entre la caméra d'observation et la scène observée.

Remarque 1 : ce champ de vitesse peut être vu comme la projection d'un champ de vitesse 3D sur le plan image.

Remarque 2 : On travaillera dans cette partie dans le repère caméra, supposant la calibration intrinsèque effectuée.

ff

PPVV

ppv) une fonction de deux valeurs de pixel.v) une fonction de deux valeurs de pixel.

ZZ zz

Notations : Soit P=[X,Y,Z]T un point 3D exprimé dans le référentiel caméra. L'image p=[x,y,f]T=[x,y]T de P est donnée par :

p⃗=f P⃗Z

Le mouvement relatif entre P et la caméra est décrit par :

V=−T −ω× P

où T est la composante en translation du mouvement et la vélocité angulaire de la caméra par rapport à la scène.

Remarque : T représente un vecteur vélocité, pour une fois, et pas un vecteur déplacement comme d'habitude. De plus, comme le mouvement est rigide, T et sont les mêmes pour tous les points de l'objet.

Notations : L'équation précédente s'écrit aussi en 3D :

V x=−T x−ω y Z+ωzYV y=−T y−ωz X+ωxZV z=−T z−ωxY+ω y X

Les équations de base du Champ de MouvementLe champ de mouvement v est donné par :

Soit en 2D :

v⃗ =fZ V⃗−V z P⃗

Z2

v x=T z x−T x fZ

−ω y f+ωz y+ω x xyf

−ω y x

2

f

v y=T z y−T y fZ

+ωx f−ωz x−ω y xyf

+ωx y

2

f

Ce champ de mouvement est la somme de deux composantes, l'une uniquement translationnelle vT et l'autre uniquement rotationnelle v :

Soit :

et

v⃗= v⃗ T+ v⃗ω

v xT=T z x−T x fZ

v yT=T z y−T y fZ

vxω=−ω y f+ωz y+

ω x xyf

−ω y x

2

f

v yω=ωx f−ωz x−ω y xyf

+ωx y

2

f

D'où :

• v=[vx,vy,0]T=[vx,vy]T

• La partie du champ de mouvement qui dépend de la vélocité angulaire ne porte pas d'information de profondeur : les valeurs Z et sont découplées.

Remarque : si la mise en correspondance reste un enjeu majeur en stéréo et en mouvement, les déplacements de

points sont représentés par des cartes de disparité pour la stéréo et par des champs de mouvement plus complexe pour

le mouvement.

Carte de disparité stéréo vs. Champ de mouvement

Les déplacements spatiaux de points correspondants entre images d'une paire stéréo (formant la carte de disparité

stéréo) sont finis, et, en principe, non contraints.

Les déplacements spatiaux de points correspondants entre trames consécutives d'une séquence dynamique (formant le

champ de mouvement) sont des approximations discrètes de dérivées temporelles, et doivent donc être relativement faibles.

Le champ de mouvement coïncide avec la carte de disparité stéréo seulement si les différences spatiales et temporelles

entre trames consécutives sont suffisamment faibles.

Le cas particulier de la Translation Pure V=-T.

Le champ de mouvement correspondant possède une structure spatiale particulière.

Comme =0 :v x=

T z x−T x fZ

v y=T z y−T y fZ

On considère le cas particulier où Tz 0. On introduit alors le point p0=[x0,y0]T défini par :

x0=fT xT z

y0=fT yT z

alors vx=( x−x0)T zZ

v y=( y−y 0)T zZ

Le cas particulier de la Translation Pure V=-T.

Le champ est donc radial : les vecteurs irradiant d'une origine commune p0 qui est donc le point de fuite de la direction de

translation.

Donc, • si Tz0 et le point s'éloigne de la caméra. Le champ de

vecteurs pointent vers p0 qui est appelé le focus de contraction.

• si Tz>0, Vz

Le cas particulier de la Translation Pure V=-T.

• si Tz=0,

et tous les vecteurs du champ de mouvement sont parallèles avec

L'objet et la caméra s'éloignent L'objet et la caméra se rapprochent

L'objet et la caméra restent à distance constante

Le cas particulier de la Translation Pure V=-T.

• Si Tz0, le champ de mouvement est radial, et tous les vecteurs pointent vers (ou à partir de) un seul point, p0. Si

Tz=0, le champ de mouvement est parallèle.

• La longueur des vecteurs du champ de mouvement est inversement proportionnel à la profondeur Z; Si Tz0, elle

est aussi proportionnel à la distance entre p et p0;

• p0 est le point de fuite de la direction de translation.

• p0 est aussi le point d'intersection du rayon optique parallèle à la direction de translation avec le plan image.

Le cas particulier du plan mobile

Penser à un environnement construit par l'homme.On suppose que la caméra observe une surface plane, ,

d'équation : n⃗T P⃗=d

où n=[nx,ny,nz]T est le vecteur unité normal à , et d la distance entre l'origine et .Le plan se déplace avec une vitesse translationnelle –T et une vitesse angulaire -, si bien que n et d dépendent du temps. On a : n x x+n y y+n z f

fZ=d

Le cas particulier du plan mobile

En remplaçant Z dans les équations de base du champ de mouvement :

Le champ de mouvement d'une surface plane mobile, à tout instant t, est un polynôme quadratique en les coordonnées (x,y,f) des points images.

Symétrie des coefficients -> ai inchangés si

d'=dn'=T‖T‖T'=‖T‖nω'=ω+n×T /d

En général, le même champ de mouvement peut être produit par deux plans différents avec deux mouvements 3D différents ! -> Indétermination pour le problème inverse !

2 conclusions importantes :

• Puisque le champ de mouvement d'une surface plane est décrite exactement et globalement par un polynôme du second degré, le champ de mouvement de toute surface lisse est approximable par un polynôme de bas ordre même sur de larges régions du plan image. Et donc, en général, des modèles paramétriques très simples permettent une estimation assez précise du champ de mouvement.• Comme les algos recouvrant le mouvement et la structure 3D ne peuvent utiliser des points coplanaires (indétermination), les mesures devront être effectuées en de nombreux différents emplacement du plan image pour minimiser la proba d'examiner des points se trouvant proche d'une surface plane.

Représentation des normes des vecteurs vitesses et du flot optique évalués par appariement à partir d’images en niveaux de gris à gauche, à partir d’images en

couleurs à droite

FishTank.avi

file:///../../../../../../../../../../../../../../../../../../../../../../../../../users/crip5/lomn/ENSEIGNEMENT/Images/ComputerVision/AnaSeqVid/Publis/FishTank.avi

Le plan mobile : propriétés du champ de mouvement

1. Le champ de mouvement d'une surface plane est, à tout instant, un polynôme quadratique en les coordonnées

images.

2. En raison de la symétrie particulière des coefficients polynomiaux, le même champ de mouvement peut être produit par deux surfaces planes différentes avec deux

mouvements 3D distincts.

La parallaxe de mouvement

Le découplage entre les paramètres rotationnels et la profondeur est responsable de la parallaxe de mouvement.

Ce phénomène représente le fait que le champ de mouvement relatif de deux points coïncidant

instantanément ne dépend pas de la composante rotationnelle du mouvement dans l'espace 3D.

Soient deux points P=[X,Y,Z]T et P'=[X',Y',Z']T projetés en deux points images p et p'. Si à un instant t, p et p'

coïncident, on a p=p'=[x,y]T et :

v xω=v' x

ω=−ω y f+ωz y+ω x xyf

−ω y x

2

f

v yω=v' y

ω=ωx f−ωz x−ω y xyf

+ωx y

2

f

D'où :Δvv x=v x

T−v' xT= (T z x−T x f ) (1Z −1Z' )

Δvv y=v yT−v' y

T= (T z y−T y f )(1Z −1Z' )

ff

PPVV

ppv) une fonction de deux valeurs de pixel.v) une fonction de deux valeurs de pixel.

ZZ zz

P'P'V'V'

Z'Z'

V V’

v

p=p’

Le vecteur [vx,vy]T peut être vu comme le champ de mouvement relatif. Tous facteurs égaux par ailleurs, la norme de ce vecteur augmente avec la séparation en profondeurs de P et P'.

On peut écrire : Δvv yΔvv x

=y− y0x− x0

Avec [x0,y0]T les coordonnées images de p0, le point de fuite de la direction de translation.

Donc, pour tous les mouvements rotationnels possibles, le vecteur [vx,vy]T pointe dans la direction de p0.

V V’

v

p=p’

épipole

Δvv . ( p− p0 )=0Comme vω=v'ω ,on a vT . ( p− p0 )=v'T . ( p− p0)Donc v . ( p− p0 ) indépendant de la structure 3D et de la composante translationnelle du mouvement

On écrira:v=( y− y 0 )vx

ω−( x−x0 )v yω

v . ( p− p0 )=constante+v

La parallaxe de mouvement

Le champ de mouvement relatif de deux points instantanément coïncidant :

Ne dépend pas de la composante rotationnelle du mouvement

Pointe vers le (ou à partir du) point p0, le point de fuite de la direction de translation.

L’épipole instantanée

Le point p0, intersection du plan image et de la direction de translation du centre de projection, peut être vu comme l’épipole instantanée entre des paires consécutives de trames de la séquence.

O1 O2T

t1 t2

p0

En conséquence, il est possible de localiser l’épipole p0 sans connaissance a priori sur les paramètres intrinsèques de la caméra (voir notion dépipole en vision stéréo 3D).

Remarque : dans le cas de la stéréo, connaître l’épipole de l’image en coordonnées images n’est pas équivalent à connaître la direction de translation (la ligne de base du système stéréo). La relation entre épipole p0 et direction de translation T est donnée ici dans le repère caméra et pas dans le repère image et contient donc la focale f. Ainsi, en stéréo, la connaissance de l’épipole d’une image ne donne la direction de translation entre les deux caméras que si les paramètres intrinsèques de la caméra sont connus. C'est la même chose dans le cas vidéo.

On a vu comment, on pouvait déduire la forme du champ de déplacement 2D si on connaît le champ de vitesses 3D et les paramètres caméra.

On suppose donc que la connaissance de champ 2D nous donnera des indications sur les mouvements réels 3D et sur les structures 3D présentes dans la scène.

La question qui vient naturellement est : comment estimer ce champ déplacements 2D ?

La notion de flot optique apportera un élément de réponse.

La notion de Flot OptiqueNous allons bientôt essayer de voir comment estimer le champ de mouvement à partir d’une séquence d’images

Pour nous une séquence d’images signifie un ensemble de variations spatio-temporelles de la luminosité d’une image.

Donc, il faut trouver le lien physique entre les variation lumineuses et le champ de mouvement.

1ère Hypothèse de cette partie : de petits mouvementsLa luminosité image est continue et différentiable autant de fois que nécessaire à la fois dans l’espace et dans le temps.

Calcul du flot optique : limites et contraintes (brightness constancy)

() On suppose que l’observation d’une variation d’intensité dans l’image traduit nécessairement l’existence d’un mouvement dans la scène. Cela correspond à une hypothèse d’éclairement constant sur la scène.

() On suppose qu’un mouvement induit un déplacement d’intensité dans l’image. Pour pouvoir utiliser la variation d’intensité dans l’image pour retrouver le mouvement apparent de l’objet dans la scène, on doit donc supposer que la lumière réfléchie par un point de la scène reste constante indépendamment du mouvement relatif scène/caméra. L’hypothèse sous-jacente est que les objets sont à surface lambertienne :

Donc, un mouvement induit un déplacement spatial d’une région d’intensité lumineuse dans l’image sans modification d’intensité dans cette région.

Comment estimer le mouvement d’un pixel entre l’image H et l’image E ?

Donc si ,selon les hypothèse précédentes, cela revient

résoudre le problème de la m.e.c. pixellique :• Étant donné un pixel dans l’image H, chercher des pixels

vosins de la même couleur dans l’image E

C’est ce qu’on appelle le problème du flot optique

E(x,y)

ΔvxΔvt

, ΔvyΔvt⇔

ΔvI ( x,y )Δvt

– Illumination constante :– Des petits mouvements : u=x et v=y valent

moins que 1 pixel : prenons alors le développement en série de Taylor d’ordre 1 de E :

Calcul du flot optique : limites et contraintes (brightness constancy)

E(x,y)

0=E( x+u,y+v )−H ( x,y )

E( x+Δvx,y+Δvy )=E ( x,y )+∂E∂ x Δvx+

∂ E∂ y Δvy+ termes d'ordres supérieurs

E( x+Δvx,y+Δvy )≈E ( x,y )+∂ E∂ x

Δvx+∂E∂ y

Δvy

En combinant les deux équations :

0=E ( x+Δvx,y+Δvy )−H ( x,y )

0≈E ( x,y )+E x Δvx+E y Δvy−H ( x,y ) avec Ex=∂ E∂ x

0≈(E( x,y )−H ( x,y ) )+E x Δvx+E y Δvy0≈ΔvE+E x Δvx+E y Δvy

0≈ΔvE+ ∇⃗ E⋅[ Δvx Δvy ]

0≈ΔvEΔvt +∇⃗ E⋅[ΔvxΔvt ΔvyΔvt ]

A la limite, quand x et y tendent vers 0, cela s’écrit différentiellement :

E t+∇⃗ E⋅[ dxdt dydt ]=0Cela se traduit par l’équation fondamentale suivante décrivant la luminosité image E :

dE ( x,y,t )dt

=0

C’est la traduction sous forme d’équation de l’expérience commune selon laquelle dans la plupart des circonstances, la luminosité apparente d’objets mobiles reste constante.

x et y variant dans le temps :

dE ( x ( t ) ,y ( t ) ,t )dt

=∂ E∂ x

dxdt+ ∂ E∂ y

dydt+ ∂ E∂ t=0

SoitSoit(Frame spatial gradient)(Frame spatial gradient)

(optical flow)(optical flow)

etet (deriv) une fonction de deux valeurs de pixel.ativ) une fonction de deux valeurs de pixel.e across frames)(deriv) une fonction de deux valeurs de pixel.ativ) une fonction de deux valeurs de pixel.e across frames)

Rappels :Dérivée du premier ordre d’une fonction de deux variables f(x,y)

= Vecteur Gradient en P(x,y)

∇ P f ( x,y )=[ ∂ f∂ x∂ f∂ y ]

= Vecteur normal à la courbe de niveau f(x,y) = f(xP,yP)=cste,

Orientation du gradient :

Orientation du contour :

ϕ=Arc tan( ∂ f∂ y / ∂ f∂ x )θ= π2 +ϕ

n⃗

P(x,y)

∇P f ( x,y )

n⃗

L’équation de Conservation de l’Illumination - Brigthness ConstancyEtant donnée la luminosité image E(x,y,t) et le champ de mouvement v, on a :

où Et désigne la dérivée partielle par rapport au temps.

(∇ E )T v+E t=0

Comment estimer le champ de mouvement v à partir de cette équation ?

Sous l’hypothèse de petits mouvements, E et Et sont accessibles par la mesure, donc v n’est pas loin. Qu’en est-il précisément ?

Le problème de l’ouvertureLa composante du champ de mouvement dans la direction orthogonale au gradient spatial de l’image n’est pas contrainte par l’équation de conservation de l’illumination.

(∇ E )T v‖∇ E‖ =−

E t‖∇ E‖=vn

Peut-on estimer le champ de mouvement v total à partir de cette équation ?

Donc, seule la composante normale vn de v dans la direction du gradient spatial peut être estimée à partir de cette équation :

v) une fonction de deux valeurs de pixel.v) une fonction de deux valeurs de pixel.xx

v) une fonction de deux valeurs de pixel.v) une fonction de deux valeurs de pixel.yy

EE

-E-Ett/|/|E|E|

Géometriquement,

Pour pouvoir mesurer E, cela implique qu’on observe de petits mouvements et donc qu’on porte une contrainte sur v dans une petite fenêtre d’analyse.

∂E∂ x →

ΔvEΔvx

Le problème de l’ouverture

The Image Brightness Constancy Assumption The Image Brightness Constancy Assumption only prov) une fonction de deux valeurs de pixel.ides the OF component in the direction only prov) une fonction de deux valeurs de pixel.ides the OF component in the direction of the spatial image gradientof the spatial image gradient

Le parallèle entre l’illustration visuelle précédente et l’équation de conservation de l’illumination n’est pas parfait.

En effet, cette équation relie le gradient image et le champ de mouvement en un même point image, établissant une contrainte sur un support spatial infiniment petit, tandis que la figure précédente fait le lien sur un support petit mais fini.

Donc, une stratégie possible pour résoudre le problème d’ouverture est d’examiner les variations spatio-temporelles de l’illumination sur un voisinage de chaque point

-> Solution manifestement adoptée par le système visuel humain.

Moyenne

Un autre problème se pose …

Validité de l’équation de conservation : flot optiqueA quel point l’estimée de vn à partir de l’équation de conservation est-elle correcte ?

Si on se restreint à une surface lambertienne illuminée par une source lumineuse ponctuelle située à l’infini, on peut écrire l’illumination image sous la forme :

E=ρ I⃗ T . n⃗

SURFACE

SOURCE LUMINEUSE p

P

On

I

En effet, d ( ρ I⃗T . n⃗ )

dt=ρ I⃗ T . d n⃗

dt=ρ I⃗ T .( ω⃗× n⃗ )

Donc (∇ E )T v+E t=ρ I⃗T .( ω⃗× n⃗ )

Par conséquent, la différence v entre la vraie valeur de v’n après modélisation radiométrique et celle estimée grâce à l’équation de conservation vn peut s’écrire :

|Δvv|=ρ |I⃗T .( ω⃗×n⃗ )|‖∇ E‖

Le problème est que la vitesse rotationnelle d’un objet 3D vient contredire l’hypothèse d’illumination constante (un déplacement d’un point dans l’image ne doit pas modifier sa luminosité) :

Validité de l’équation de conservation : flot optiqueEn conséquence, l’équation de conservation de la luminosité fournit la véritable valeur de la composante normale vn du champ de mouvement (v =0 pour tout type de surface) seulement pour :

• Des mouvements purement translationnels;• Tout mouvement rigide pour lequel I et sont parallèles.

De plus Δvv ↑ pour ‖∇ E‖↓Enfin, v est rarement nul, et le mouvement apparent de la luminosité image est presque toujours différent du champ de mouvement. Pour cette raison, et pour éviter toute confusion, on appelle le mouvement apparent un flot optique, et on fait référence aux techniques d’estimation du champ de mouvement à partir de l’équation de conservation de l’illumination comme les techniques de flot optique.

Flot OptiqueLe flot optique est un champ de mouvement satisfaisant la contrainte de conservation de l’illumination :

et pouvant être défini comme le mouvement apparent des motifs lumineux image.

Remarque 1 : le flot optique est différent du champ de déplacement projeté 3D-> 2D mais en est une approximation

Remarque 2 : si les mouvements sont suffisamment petits, on peut estimer la composante normale vn de ce flot optique.

Flot Optique et Champ de MouvementLe flot optique est l’approximation du champ de mouvement calculée à partir d’une séquence d’images temporelle. Sous les hypothèses simplifcatrices suivantes :

• surfaces lambertiennes,

• source lumineuse ponctuelle à l’infini,

l’erreur liée à cette approximation est

•Faible en les points présentant un fort gradient spatial

•Nulle seulement pour les mouvements de translation ou les mouvements rigides telles que la direction de l’illumination est parallèle à la vélocité angulaire.

Estimation du champ de MouvementNous allons maintenant essayer de voir comment estimer le champ de mouvement à partir d’une séquence d’images

Les techniques algorithmiques disponibles peuvent être grossièrement divisés en deux catégories :

– Techniques de mises en correspondance dense dites techniques différentielles :

-> méthodes de calcul du flot optique

– Techniques de mises en correspondances éparses dites techniques de matching :

-> méthodes de tracking

Vrai flot optique

Méthodes qui peuvent s’affranchir de l’hypothèse de

“brigthness constancy car on utilisera des

contraintes géométriques

Nous allons exposer une première méthode utilisant l’estimation locale aux Moindres Carrés des paramètres du flot optique

Techniques Différentielles : calcul du Flot Optique Direct par Moindre Carrés

Hypothèses et contraintes1. L’équation de conservation de la luminosité image

fournit une bonne approximation de la composante normale du champ de mouvement;

• Le champ de mouvement est bien approximé par un vecteur mouvement constant à l’intérieur d’un tout petit patch du plan image. (cf. approximation de champ de mouvement lisse pour des plans mobiles)

Pour tout point pi à l’intérerieur d’un petit patch Q de taille NxN (disons 5x5) on peut écrire :

(∇ E ( p i))T v ( pi )+Et ( pi )=0et ∀ i, v ( p i)=vQd'où ∀ p i∈Q, (∇ E( p i))

T vQ+Et ( pi )=0

Donc à l’ordre 1, (vx,vy) peut être assimilé à un vecteur constant (a5f/d,a8f/d) localement qui dépend du mouvement générique d’un plan mobile

En conséquence, le flot optique peut être estimé sur Q comme le vecteur constant v’ minimisant la fonctionnelle :

Ψ ( v )=∑pi∈Q

[ (∇ E ( pi ))T v+E t( pi )]2

Classiquement, résoudre ce problème de minimisation aux moindres carrés revient à résoudre le système linéaire suivant :

On résoud ainsi le problème de l’ouverture en extrayant le plus d’équations possibles pour un même pixel central à partir d’une fenêtre 5x5 centrée sur ce pixel. Avec les contraintes précédents, on a 25 équations par pixel. Avec [u v]T le vecteur déplacement vQ, on peut écrire :

[ E x( p1 ) E y ( p1 )Ex ( p2 ) E y ( p2 )⋮ ⋮Ex( p25 ) E y( p25) ] [uv ]=−[E t ( p1)E t( p2)⋮

E t ( p25)]

La solution de ce système est donnée par :

Où v est le flot optique (ou estimée du champ de mouvement) au centre du patch Q. En répétant cette procédure pour tous les points images, on obtient un flot optique dense.

v= ( AT A )−1 AT b

Qv

Algorithme CONSTANT_FLOW

INPUT : Une séquence temporelle de n images E1, E2, …, En. Soit Q une région carrée de NxN pixels (disons 5x5)

• Filtrer chaque image de la séquence av) une fonction de deux valeurs de pixel.ec un filtre Gaussien de dév) une fonction de deux valeurs de pixel.iation standard S (disons S = 1,5 pixels) le long de chaque dimension spatiale.• Filtrer chaque image de la séquence le long de la dimension temporelle av) une fonction de deux valeurs de pixel.ec un filtre Gaussien de dév) une fonction de deux valeurs de pixel.iation standard t (disons t = 1,5 frames). Si 2k+1 est la taille du filtre temporel, il faut laisser de côté les k premières et dernières images.• Pour chaque pixel p de chaque image de la séquence :

• Calculer la matrice A et le v) une fonction de deux valeurs de pixel.ecteur b• Calculer le flot optique v) une fonction de deux valeurs de pixel.(p) = (ATA)+ATb

OUTPUT : le flot optique de la séquence d’images

Conclusions sur cette méthode de flot optiqueEn quels pixels l’algorithme précédent éprouve-t-il des difficultés d’estimation ? A chaque fois que ATA est singulière :

AT A=( ∑ E x2 ∑ E x E y

∑ E x E y ∑ E y2 )ATA caractérise la structure des niveaux de gris dans le patch Q. Ses vecteurs propres codent les directions principales des contours et ses valeurs propres la force des ces contours.

La matrice est singulière si au moins une des deux valeurs propres est nulle, ce qui correspond aux 2 cas suivants : 1.Tous les gradients spatiaux dans Q sont nuls

1.Tous les gradients spatiaux dans Q sont parallèles

Dans ce cas 2, le problème de l’ouverture ne peut pas être résolu et la seule possibilité est de retenir la solution de norme minimale v) une fonction de deux valeurs de pixel.(p) = (ATA)+Atb en s’aidant de la pseudo inv) une fonction de deux valeurs de pixel.erse et de la décomposition SVD.

Dans ce cas, on estime le flot normal.

Dernière remarque : l’algorithme précédent donne de bons résultats car la structure spatiale d’un champ de mouvement rigide est bien décrite par un polynôme de bas degré en les coordonnées images. Pour cette raison, l’hypothèse de conservation locale du champ de mouvement sur de petits patches images est raisonnable.

Nous allons exposer une deuxième méthode utilisant la résolution de l’équation différentielle globale de conservation de l’illumination.

Techniques Différentielles : calcul du Flot Optique Itérative par Equa. Dif. : Horn et Shunck

(∇ f )T [uv ]+f t= 0f x u+f y v+f t=0

Soit la fonction 3D f(x,y,t) représentant la valeur du niveau de gris en (x,y) à l’instant t. D’après ce qui précède on a,

Ce qui s’écrit :

C’est une équation linéiare à deux inconnus (u,v) constituant le flot optique car fx, fy et ft sont calculable par des techniques de gradient classiques de l’imagerie 2D

La solution peut se situer n’importe où sur la droite :

v=−f xf yu−

f tf y

d=f t

√ f x2+f y2

Cette valeur de d donne la composante du flot optique dans la direction du gradient d’intensité :

f ( x,y )∇t⃗ p ?

On ajoute une contrainte : le flot optique doit être lisse ou continu :

• On fait donc l’hypothèse que des points voisins sur une surface rigide possèdent des vecteurs déplacement localement approximativement identiques.

Cela revient à minimiser la fonctionnelle d’erreur suivante :

E( x,y )= terme d'attache aux données + contrainte de régularisationE( x,y )=( f xu+f y v+f t )

2+ norme sur [ u,v ]T

E( x,y )=( f xu+f y v+f t )2+λ(‖∇ u( x,y )‖2+‖∇ v ( x,y )‖2 )

E( x,y )=( f xu+f y v+f t )2+λ(ux

2+u y2+vx

2+v y2 )

Le paramètre code la force de la contrainte de lissage imposée.

Technique classique dite de régularisation de problème inverse.

d'où ∂ E2∂ u =( f xu+f y v+f t ) f x+λ( uxx+u yy )=0

∂E2∂ v

=( f xu+f y v+f t ) f y+λ( vxx+v yy )=0

soit

( f x u+f y v+f t ) f x+λ ( Δv2u )=0

( f x u+f y v+f t ) f y+λ ( Δv2 v )=0

or ∂E∂ u=2( f xu+f y v+f t ) f x+2 λ[( ∂∂u ∂u∂ x ) ∂u∂ x +( ∂∂ u ∂u∂ y ) ∂ u∂ y ]=0

Classiquement, en utilisant les masques de convolution linéaire, on peut calculer le laplacien d’une fonction par la formule suivante :

Δv2u=u−umoyen

où umoyen est la moyenne de la composante u du flot optique pris parmi les 4 voisins du pixel. Soit

h=[ 0 −1 0−1 4 −10 −1 0 ]

( f x u+f y v+f t ) f x+λ (u−umoyen )=0( f x u+f y v+f t ) f y+λ (v−vmoyen )=0

On peut ainsi calculer (u,v) de façon itérative avec les équation :

u=umoyen− f xf x umoyen+f y vmoyen+f tλ+f x2+f y2

=umoyen− f xPD

v=vmoyen−f yPD

Algorithme HORN_FLOW

INPUT : Une séquence temporelle de n images f1, f2, …, fn.

1.Filtrer chaque image de la séquence av) une fonction de deux valeurs de pixel.ec un filtre de Dériv) une fonction de deux valeurs de pixel.ation le long de chaque dimension spatiale.• Filtrer chaque image de la séquence le long de la dimension temporelle av) une fonction de deux valeurs de pixel.ec un filtre de Dériv) une fonction de deux valeurs de pixel.ation. 1.Pour chaque pixel p de chaque image de la séquence :

• k=0• Initialise uk et v) une fonction de deux valeurs de pixel.k à zéro

2.Pour chaque pixel p de chaque image de la séquence :• Jusqu’à ce qu’une mesure d’erreur soit satisfaite, faire :

OUTPUT : le flot optique de la séquence d’images

uk=umoyenk−1 − f x

Pk−1

D

v k=vmoyenk−1 − f y

Pk−1

D

Interprétation Intuitive du Schéma Itératif

u

v (fx,fy)

Constraint line

(u,v)

( ū , v̄ )

La nouvelle valeur de (u,v) en un point (x,y) est égale à la moyenne des valeurs voisines moins un ajustement dans la direction du gradient d’intensité

Schunk propose d’ajouter d’autres contraintes géométriques à celle utilisée précédemment . Le niveau de gris en un pixel donne une contrainte, à savoir que le flot optique peut se trouver n’importe où sur la droite déterminée par les dérivées spatiales et temporelles.Si on utilise un pixel avoisinant, la même contrainte appliquée à ce pixel fournit une nouvelle droite de contrainte.Le flot optique est ainsi l’intersection de ces deux droites de contrainte. On ne peut pas privilégier un voisin, on considère donc les 8 contraintes générées par les 8 pixel du voisiange 3x3 en 8 connexité.

w

z

Faisceau de droites de contraintes

Bien sûr, ces droites ne sont pas exactement concourantes, même si leurs points d’intersection se regroupent dans une région étroite. Il s’agit d’estimer le meilleur point d’intersection.

Passons en coordonnées polaires (, ):

d=ρ cos( α−β )

avec d=f t

√ f x2+f y2et α= arctan

f yf x

est la vitesse et la direction du flot optique

2 points 1 et 2 fournissent les 2 équations de flot optique suivante :

d1=ρ cos( α1−β )d2=ρ cos (α 2−β )

AB=d2−d1 cos(α 2−α 1 )sin (α 2−α1 )

De façon similaire, les intersections avec les droites correspondant aux points 3, 4, …, 9 peuvent être calculées.

Ces intersections sont sensés se regrouper autour d’un point central.Si l’on désigne par ce point central, alors le flot optique est donné par :

ρ=√d12+b̂2

β=α1+arctan (b̂d1 )

b̂

Représentation des normes des vecteurs vitesses et du flot optique évalués par appariement à partir d’images en niveaux de gris à gauche, à partir d’images en

couleurs à droite

Estimation du flot optique

Estimation des paramètres d’un modèle de mouvement affine sur des régions carrées [WA94]

Classification par Cmoyennes floues sur les paramètres de mouvement

Représentation des classes dans l’espace de l’image

image initiale image segmentée

{v x( x,y )=a x0+a xx x+a xy y }

image initiale segmentation par classification sur les composantes de la vitesse

Techniques de Matching

Il s’agit d’estimer le champ de déplacement en certains points correspondant à des primitives seulement.

Le résultat est un champ de déplacement épars.

On illustrera deux cas :1. L’analyse frame-à-frame dans le cas de 2 frames

seulement, ce qui revient à trouver les disparités entre deux frames consécutives.

2. Le tracking du déplacement d’une primitive à travers une séquence d’images plus longue, et qui peut améliorer la robustesse du matching frame-à-frame.

Techniques de Matching par autocorrélation

Matching de 2 frames :Tracking avec jetons

Etant donné deux frames capturées à différents instants et m points dans chaque image, le problème de mec revient à mapper un point d’une frame à un point de l’autre frame de sorte que deux points ne se mappent pas en un même point.

Le problème en stéréo est évidemment simplifié puisque les correspondants possibles se trouve le long de la droite épipolaire.

Dans le cas d’objets se déplaçant et de frames prises à intervalle quelconque, les matches possibles peuvent se trouver quasiment n’importe où dans la frame suivante, contrairement à la stéréo où les frames sont séparés dans l’espace et non dans le temps.

Le problème de mec est ainsi extrêmement combinatoire et lourd à traiter de façon brutale. Pour 2 frames et 5 points dans chaque frame, le nombre de mappings possible est 5!=120.Par ailleurs, même si on peut éventuellement construire ces 120 mappings, comment choisir le meilleur ?

Pour réduire la complexité du problème, on utilise des contraintes physiques ou heuristiques.

Smoothness

Rigidity

Techniques différentielles

(See M. Shah book)

La difficulté est de traduire ces heuristiques qualitatives en expressions quantitatives afin de définir des fonctions de coûts. (Techniques d’optimisation de type Programmation Dynamique utilisées en Reconnaissance de Formes structurelles).

Le problème revient alors à déterminer le mapping optimal en fonction de ces fonctions de coût.

L’énumération de toutes les configurations possibles n’est en général pas possible. Il s’agit donc de trouver un bon algorithme d’approximation pour obtenir une solution sub-optimal très proche de la solution optimale.

Tracking avec jetons : Algorithme itératif

S. T. Barnard and W. B. Thompson, "Disparity analysis in images," IEEE Trans. Pattern Anal. Machine Intell., v) une fonction de deux valeurs de pixel.ol. PAMI-2, pp. 333- 340, 1980.

Il s’agit d’un algorithme itératif pour calculer le flot optique pour m jetons.

Ils utilisent une mesure de confiance Pij qui code la

probabilité d’un jeton i du frame f1 à être associée au jeton j

du frame f2 : Pij = P( (i,1)(j,2) )

Pij0=

1c+w ij

La probabilité initiale Pij0 sont calculées en utilisant des

différences de niveaux de gris dans des petites fenêtres

autour des jetons se correspondants :

w ij= ∑dy=−w

dy=w

∑dx=−w

dx=w

( f 1 ( xi+dx,y i+dy )−f 2 ( x j+dx,y j+dy) )2

avec

A chaque itération, on calcule : Pijn=

~Pijn

∑k

~Pikn

Avec :~P ijn=Pij

n−1 ( A+Bqijn−1 )etqijn−1=∑

k∑lPkln−1

Avec k voisin de i et l voisin de j, tels que :

‖( x i ,y i )−( xk ,y k )‖≤Dmaxet‖V ij−V kl‖≤Vmax

où Vij est le flot optique du jeton i s’il est matché avec le jeton j dans l’autre frame

Algorithme ITER_TOKEN

INPUT : Une séquence temporelle de n images f1, … fn av) une fonction de deux valeurs de pixel.ec le même nombre de primitiv) une fonction de deux valeurs de pixel.es ou jetons à apparier dans chaque frame.

Pour chaque paire de frames consécutiv) une fonction de deux valeurs de pixel.es, et pour chaque paire de jetons i et j d’une frame à l’autre, calculer jusqu’à stabilisation

OUTPUT : le flot optique ou la correspondance de mouv) une fonction de deux valeurs de pixel.ement associé à l’ensemble des jetons de frame en frame.

Pij0=

1c+wij

Pijn=~Pijn

∑k

~Pikn

avec ~Pijn=Pij

n−1 (A+Bqijn−1)etq ijn−1=∑

k∑lPkln−1

Illustration de la méthode de Barnard et Thompson avec A=.3, B=3 et Vmax = 2, et Dmax=4

Matching multi-frames : Tracking avec jetons : Algorithme non-itératif déterministe (voir le livre en ligne de M. Shah)Il s’agit de suivre des jetons dans plusieurs frames successives et d’utiliser un mapping initial entre les deux premières frames pour propager cette information et adapter le mappings suivants en fonction de cette information a priori.

Soit une séquence de n frames f1, f2, …, fn.On suppose que les m jetons d’intérêt (détecteur de Harris pour les jonctions par exemple) ont été détectés.

Ainsi, chaque frame fi est réduit à un ensemble de m points.

Xij est le vecteur de coordonnées 2D du ième points dans la jème

frame.

Le but est de trouver une correspondance bi-univoque k entre les points de la frame k et ceux de la frame k+1.

fk fk+1Xik

Xjk

XΦ k ( i )k+1

XΦ k ( j )k+1

Il n’est pas irréaliste de supposer que dans l’espace et sur des intervalles de temps petits, les objets se déplacent sur de petites distances. Et que leur mouvement correspondant est régulier ou uniforme : contrainte (a).La régularité du mouvement implique un changement minime de la vélocité du point. C’est à dire quele point ne peut changer sa direction et sa vitesse de déplacement simultanément : contrainte (b).

Ainsi, les points vont suivre un certain chemin dit “proximal uniform path”. La découverte de ce chemin régulier optimal va utiliser la fonction de coût (“proximal uniformity function”) définie dans ce qui suit.

Soit les matrices des Changements Relatifs de la frame k-1 à k+1 Crkmxm et des Déplacements Relatifs de la frame k à la frame k+1 Drk mxm. On placera en ligne les points de la frame de départ et en colonne les points de la frame d’arrivée.

Ck Dk

Points de la couche k Points de la couche k

Points de la couche k+1

C k [ i,j ]=‖XΦ− ( k− 1)( i )k−1 X i

k−X ik X j

k+1‖

etDk [ i,j ]=‖X i

k X jk+1‖

fk fk+1

Xik X jk+1

fk-1

XΦ −( k− 1) ( i )k−1

Soit les matrices de Changement C et Déplacement D Absolus

Mapping initial

Cr k[ i,j ]=C

k [ i,j ]∑u∑vCk [ u,v ]

et

Drk [ i,j ]=Dk [ i,j ]∑u∑vD k[ u,v ]

Soit

M k [ i,j ]=C r k [ i,j ]+D r k [ i,j ]

Soit Mmxm la matrice résultante :

Cette matrice code la fonction de cout pour une association (i,k) avec (j,k+1) sachant l’association optimale précédente ( -(k-1)(i) , k-1 ) avec (i,k) :

M k [ i,j ]=δ ( X Φ −( k− 1) ( i )k− 1 ,X i

k ,X jk+1 )

En estimant quantitativement les critères de régularisation suivants :

•La vitesse ne change pas beaucoup entre deux frames successives;•La direction ne change pas beaucoup entre deux frames successives;•Le déplacement d’un point entre deux frames successives tend à être petit;

Trajectoire lisse et uniforme :Controle des Changements du vecteur vélocité

Proximal Match

Dans cette formulation, on suppose qu’un premier mapping 1 entre la frame 1 et la frame 2 est disponible. On peut utiliser l’algorithme à jeton itératif précédent, par exemple. Ensuite l’algorithme va prolonger la trajectoire de frame en frame en utilisant ces contraintes de régularités initiales.

Le mapping k est déterminé en fonction des mappings précedents de sorte à minimiser la fonction de coût globale sur toute la trajectoire :

C=∑kδ ( X p

k−1 ,X qk ,X r

k+1 )

Algorithme GREEDY_TOKEN

INPUT :•Une séquence temporelle de n images f1, f2, …, fn. •Un ensemble de m jetons dans chaque frame. •Une correspondance initiale entre les m jetons de la frame 1 et les m jetons de la frame 2 donnée par l’algorithme ITER_TOKEN par exemple.

OUTPUT : les trajectoires de la séquence d’images

•Quand le nombre de jetons varie, on adapte ce cadre algorithmique à la programmation dynamique (cf. reconnaissance de la parole et de l'écrit manuscrit). http://www-i6.informatik.rwth-aachen.de/~dreuw/tracking.html •Ces techniques séparent complètement le processus de segmentation/détection des primitives de leur suivi.

http://www-i6.informatik.rwth-aachen.de/~dreuw/tracking.html

Matching multi-frames : Tracking : Filtrage de Kalman

Définition :Il s’agit de mettre en correspondance des primitives sur une séquence d’images longue en associant des incertitudes..

Il s’agit comme précédemment d’utiliser le travail de mise en correspondance passé pour prédire la mise en correspondance à venir dans l’hypothèse de trajectoires continues.

Pour cela, il existe une cadre théorique bien établi venant des techniques d’optimisation ; le filtre de Kalman.

Dans nos problématiques de vision, un filtre de Kalman est mis en place sous la forme d’un algorithme récursif qui estime la position et l’incertitude d’un point caractéristique mobile dans la frame suivante à partir des frames précédentes. En d’autres termes, on cherche la primitive dans cette frame et la taille de la région autour de la primitive prédite pour être sûre de trouver la dite primitive avec une certaine confiance.

Cadre de modélisation bayésienne

Math

Voir document kalma.HMM.ps

L’estimée résultat est optimal au sens statistique : sur un grand nombre d’expériences, le filtre de Kalman, s’il est bien conçu, serait meilleur, en

moyenne, que les estimées résultats de tout autre filtre de prédiction sous l’hypothèse d’un système linéaire et de bruit blanc gaussien.

Si le bruit est non gaussien, le filtre de Kalman est encore le meilleur filtre linéaire non biaisé.

[P.S. Maybeck, Stochastic Models, Estimation, and Control, Vol I. Academic Press, New York, 1979]

• Un système physique.

• Distinction entre paramètres:–qui modélisent le système;–que l’on peut mesurer.

• Estimer les premiers à partir des seconds.

Principe

oi

Prise en compte des incertitudes

• Les mesures sont imprécises/incertaines• Le modèle est simpliste donc ….

• Dans ce formalisme statistique, on fait une estimation si de l’état courant si à partir des observations oi. • On veut savoir la fiabilité d’une estimation si de l’état courant si.

ce que le filtre de Kalman permet.

•On a accès a: • bruit blanc additif et:

• Evolution du modèle:

• ni bruit blanc additif et :

ηi

ô i=o i+η i

Ri=E [ ηi .ηit ]

Qi=E [ ni .nit ]

s i+ 1=h i( s i)+n i

Les notes de Joella le mois i

Etat de concentration du professeur pour le mois i

Etat de connaissance de Joella le mois i+1

Etat de concentration de Joella pour le mois i

Formalisation: mesure et vecteur d’états

•Filtrage de Kalman: processus itératif d’estimation du vecteur

•Estimation à l’instant i:

• traduit la confiance que l’on a en l’estimation• Si on connaît , statistiquement parlant la meilleure estimation possible de est:

s i

ŝ i associée à Pi=E [( ŝ i− s i) ( ŝ i− s i )t ]

ŝ i

Piŝ i−1

ŝ i / i−1=h i ( ŝ i− 1 )

Formalisation: mesure et vecteur d’états

• du Lien entre les observations et le vecteur d’état:

•Cas linéaire:

f i(o i ,s i )=0

f i :ℜm i×ℜn→ℜ p i

ô i=F i . s i+η i

Formalisation: les équations de mesures,ou de quoi dispose-t-on en pratique ?

• et on a bien:z i=Mi . s i+wiavec

z i=−f i( oi , ŝi / i−1)+∂ f i∂ si( oi , ŝi /i−1 ). ŝi / i−1

M i=∂ f i∂ si(o i , ŝi / i−1 )

w i=∂ f i∂ oi

(o i , ŝi / i−1 ).( ôi−oi )=∂ f i∂ oi

(o i , ŝi / i−1 ).ηi

Formalisation: les équations de mesures

• Dans le cas non-linéaire, on s’y ramène: développement de Taylor à l’ordre 1 de :f i

f i( ô i ,s i )=f i( oi , ŝi /i−1 )+∂ f i∂ x i

.( ôi− x i )+∂ f i∂ s i

.( s i− ŝ i / i−1 )+ . . .

3 étapes, propagation des incertitudes.

•Initialisation:•Prédiction (grâce au modèle système) :

•Calcul du gain de Kalman:

•Mise à jour (grâce aux mesures) :

Un pas du filtre.

ŝ i ŝ i / i−1+K i .( z i−M i . ŝ i / i−1 )Pi ( I−K i .M i ). Pi / i−1

( ŝ 0 ,P 0 )

ŝ i / i−1 hi( ŝi−1)

Pi / i−1∂ hi∂ s i

( ŝ i−1 ). Pi−1 .∂ hi∂ s i

( ŝ i−1 )t +Q i−1

K i P i / i−1 . M it . (M i . P i / i−1. M i

t +W it )−1

L’algorithme

L’algorithme : interprétation

•Compromis entre la contribution de la prédiction et de la mesure:

•On peut réécrire:

•Grande incertitude sur le vecteur d’état donc « grande », « grand » donc innovation favorisée.•Grande incertitude sur la mesure donc « grande » , « petit » , donc prédiction favorisée.

K iW i K i

K i=Pi .M it .W i−1

Pi

)ˆ.(.ˆˆ 1/1/ iiiiiiii sMzKssprédiction inovation

Formalisons dans ce cadre le problème du tracking.Une nouvelle frame de la séquence d’image est acquise et traitée à chaque instant tk=t0+k où k est un entier naturel.

k est suffisament petit pour considérer que le mouvement est linéaire d’une frame à l’autre.

On considère seulement un point primitive, pk=[xk,yk]T, dans la frame acquise à l’instant tk, se déplaçant avec la vélocité vk=[vx,k,vy,k]T.

On décrit le mouvement dans le plan image avec un vecteur d’état sk=[xk,yk,v x,k,v y,k]T.

En supposant un intervalle d’échantillonnage suffisamment petit (et donc une vélocité de la primitive constante entre 2 frames), le modèle système s’écrit dans le cadre du filtre de Kalman :

pk=pk−1+v k−1+ξ k−1v k=vk−1+ζ k−1où ξk−1 et ζ k−1 sont des bruits blancs gaussiens modélisant le bruit du système .

Le modèle du système : ou prédiction du vecteur d’état

En terme de vecteurs d’état xk cela s’écrit :sk=H k−1 sk−1+n k−1

avec H k−1=[1 0 1 00 1 0 10 0 1 00 0 0 1 ] et nk−1=[ξk−1ζ k−1 ]

En terme de mesures, on suppose qu’un extracteur rapide de primitive est disponible et estime zk, la position du point primitive pk pour chaque frame de la séquence. Ainsi le modèle de mesure du filtre de Kalman devient :

zk=[1 0 0 00 1 0 0 ][ pkvk ]+wk =Msk +wkavec w k bruit blanc Gaussien centré modélisant le bruit de mesure

Le modèle de mesures

Remarque : dans le cas linéaire : Rk=Wk, Mk=Fk et zk=

Hypothèses et Positions du problèmeSous les hypothèses du filtre linéaire de Kalman, et étant données les observations bruitées zk, calculer la meilleure estimée de la position de la primitive et de sa vélocité à l’instant tk ainsi que leurs incertitudes associées.

ô k

Algorithme KALMAN_TRAKING

INPUT : L’entrée est formée, à chaque instant tk, des deux matrices de cov) une fonction de deux valeurs de pixel.ariance des bruits du système et de mesure à l’instant tk-1, Qk-1 et Wk-1 respectiv) une fonction de deux valeurs de pixel.ement, plus les deux matrices inv) une fonction de deux valeurs de pixel.ariantes temporellement d’état d’une part, H, et de mesure, M, d’autre part, ainsi enfin que des mesures de position à l’instant tk, zk. Les entrées de P0 sont fixées à de très fortes v) une fonction de deux valeurs de pixel.aleurs arbitraires.

OUTPUT : les estimations optimales des position et v) une fonction de deux valeurs de pixel.élocité à l’instant tk, ,et leurs incertitudes données par les éléments diagonaux de Pk.

ŝk /k−1=H k−1 ŝk−1Pk /k−1=H k−1Pk−1H k−1T+Qk−1

Kk =Pk /k−1M k T(M k Pk /k−1M kT+W k )−1

ŝk= ŝk / k−1+K k ( zk−M kH k−1 ŝk−1 )Pk=( I−K k )Pk / k−1 ( I−K k )

T+K kW k Kk T

ŝk

Prédiction modèle

Gain

MAJ de la prédiction modèle par le biais des

mesures

Le filtre quantifie l’incertitude sur l’estimée de l’état, sous la forme des éléments diagonaux de la matrice de covariance d’état Pk

Cette information permet au détecteur de primitives de dimensionner automatiquement la région de recherche de la primitive dans la frame suivante.

Cette région de recherche est centrée sur la meilleure position estimée et sa largeur est proportionnelle à l’incertitude.

Dans un filtre correctement conçu, la valeur de cette incertitude décroit rapidement avec le temps et la région de recherche se rétrécit d’autant avec le temps.

Dans l’exemple présenté, la taille des croix indique la zone d’incertitude dans laquelle rechercher la primitive dans la frame suivante.

Remarque : la matrice de covariance d’état ne dépend pas des mesures. Donc, si la dépendance temporelle de Hk, Mk, Qk et Rk est connue, Pk peut être calculée off-line et ensuite être approximée par une fonction en escalier. Cette propriété peut être cruciale pour les implémentations temps réel du filtre de Kalman.

Deux problèmes se posent pour l’implémentation de cet algorithme :

Les données manquantesLe filtrage de Kalman repose sur la connaissance suivante :

– Le modèle du système et la matrice de covariance du bruit correspondant Qk

– Le modèle de mesures et la matrice de covariance du bruit correspondant Rk

– L’état initial du système (temps t0), , et la matrice de covariance d’état, P0

Cependant, nombre de données parmi ces dernières sont inconnues. Toutefois, en général, elles sont modélisables de façon simples linéairement. Il faut juste prendre garde à faire en sorte que Q et R soient comparables pour que la prédiction ou l’innovation ne l’emporte pas de façon injustifiée sur l’autre.

L’association des donnéesEn présence de plusieurs primitives images et de multiples mesures, quelle mesure observée doit être associée avec quelle primitive ? Le cas de cibles en désordre et interférant.

ŝ0

Incertitude de Kalman.C’est la région de l’espace d’état qui contient le véritable état avec une probabilité donnée.

Exemple : soit le vecteur d’état 2D ek=[x1,x2]T. Le filtre de Kalman calcule l’estimé d’état optimal, êk, comme le maximum de la densité de probabilité conditionnelle de ek étant donnée la mesure zk. Cette fonction de densité est supposée Gaussienne, si bien que son maximum coïncide avec sa moyenne.Conséquences pratiques :

•La région du plan centrée sur êk qui contient le véritable état avec une probabilité c2 est l’ellipse : •Les axes de cette ellipse sont :•La variable (e-êk)(Pk)-1(e-êk)T a une distribution du Chi-2

Utilisation pratique, pour le tracking :•A t k-1, la prédiction d’état du filtre à tk est ê k/k-1= H k-1 ê k-1 avec la matrice de covariance P k/k-1. On diagonalise P k/k-1 pour obtenir ses vecteurs propres, considère les composantes du vecteur d’état donnant la position [x1,x2]T de la primitive, et on construit une ellipse d’incertitude (centrée en ê k/k-1 avec une probabilité désirée de (1-a)), et on cherche la primitive dans la frame k seulement dans l’ellipse. Une fois que votre détecteur de primitive a mesuré la position de la primitive à tk, on calcule êk et Pk, ce qui vous permet de construire l’ellipse d’incertitude contenant la véritable primitive à tk avec le niveau de probabilité choisi.

(e− êk )( Pk )−1 (e− êk )

T≤c2

±c √ λie i ,i=1,2 , à partir des éléments propres de Pk

Suivi de la trajectoire d’une particule dans le plan

• Le système: mouvement à accélération constante

• Equation de mesures:

• Incertitude: Meyer a montré que

s i [ x i ẋ i ẍ i y i ẏ i ÿ i ]t si+1 [1 Δvt

Δvt2

1 Δvt 01

1 Δvt Δvt2

0 1 Δvt1] . si +ni

z i=[ x i y i ]t z i=[1 0 0 0 0 00 0 0 1 0 0 ] . s i+w i

Qi=[Δvt5

20Δvt 4

8Δvt 3

6Δvt3

6Δvt 3

3Δvt 2

2Δvt3

6Δvt 2

2 Δvt]

Bilan sur la Technique de tracking de Kalman

Remarque : Tout ce qui suit est tiré de la thèse de Auguste Genovesio traitant du tracking de spot fluorescents en imagerie médidale disponible en ligne et d'un chapitre en particulier qui propose un bon bilan des méthodes de tracking ponctuel ou de forme (les références se trouvent dans le document)

Suivi de primitives multi-frames : filtrage particulaire ou la version évolutionnaire avec un peu de Bayes

Encore appelé algorithme CONDENSATION ou filtre bootstrap

Permet de manipuler numériquement des modèles joints.

Repose sur un principe de ré-échantillonnage qui correspond à la sélection dans les algorithmes évolutionnaires (GA)

Suivi de contours multi-frames : Snake ou Contours actifs

Définition :Il s’agit de suivre un contour d'objet légèrement mouvant sur une séquence d’images longue.

•D'abord une méthode de segmentation en image fixe

Suivi de contours multi-frames : Level Set Methods

Définition :Il s’agit de suivre plusieurs contours d'objets dont le nombre varie et légèrement mouvant sur une séquence d’images longue.

• Travaille dans le cadre des equations aux dérivées partielles• D'abord une méthode de segmentation en image fixe

• “Performance of Optical Flow Techniques”, J. Barron et al., IJCV, vol. 12, pp. 43-77, 1994

• “Determining Optical Flow”, Horn et Schunck, AI, vol.17, pp. 185-203, 1981

• “Use of Optimal Estimation Theory, in Particular the Kalman Filtering, in Data Analysis and Signal Processing”, W. Cooper, Review of Scientific Instrumentation, vol. 57, pp. 2862-2869, 1986

Bibliographie

Le temps manquant, je n’ai pas parlé de :

• Détection de changement dans des séquences vidéos (différences d’images sophistiquées) - de plans dans des films

• Du tracking de référence de points de Harris : l'algorithme de Kanade Lucas et Tomassi (KLD) disponible dans beaucoup de bibliothèque en ligne

Diapo 1Diapo 2Diapo 3Diapo 4Diapo 5Diapo 6Diapo 7Diapo 8Diapo 9Diapo 10Diapo 11Diapo 12Diapo 13Diapo 14Diapo 15Diapo 16Diapo 17Diapo 18Diapo 19Diapo 20Diapo 21Diapo 22Diapo 23Diapo 24Diapo 25Diapo 26Diapo 27Diapo 28Diapo 29Diapo 30Diapo 31Diapo 32Diapo 33Diapo 34Diapo 35Diapo 36Diapo 37Diapo 38Diapo 39Diapo 40Diapo 41Diapo 42Diapo 43Diapo 44Diapo 45Diapo 46Diapo 47Diapo 48Diapo 49Diapo 50Diapo 51Diapo 52Diapo 53Diapo 54Diapo 55Diapo 56Diapo 57Diapo 58Diapo 59Diapo 60Diapo 61Diapo 62Diapo 63Diapo 64Diapo 65Diapo 66Diapo 67Diapo 68Diapo 69Diapo 70Diapo 71Diapo 72Diapo 73Diapo 74Diapo 75Diapo 76Diapo 77Diapo 78Diapo 79Diapo 80Diapo 81Diapo 82Diapo 83Diapo 84Diapo 85Diapo 86Diapo 87Diapo 88Diapo 89Diapo 90Diapo 91Diapo 92Diapo 93Diapo 94Diapo 95Diapo 96Diapo 97Diapo 98Diapo 99Diapo 100Diapo 101Diapo 102Diapo 103Diapo 104Diapo 105Diapo 106Diapo 107Diapo 108Diapo 109Diapo 110Diapo 111Diapo 112Diapo 113Diapo 114Diapo 115Diapo 116Diapo 117Diapo 118Diapo 119Diapo 120Diapo 121Diapo 122Diapo 123Diapo 124Diapo 125Diapo 126Diapo 127Diapo 128Diapo 129Diapo 130Diapo 131Diapo 132Diapo 133Diapo 134Diapo 135Diapo 136Diapo 137Diapo 138Diapo 139Diapo 140Diapo 141Diapo 142Diapo 143Diapo 144Diapo 145Diapo 146Diapo 147Diapo 148Diapo 149Diapo 150Diapo 151Diapo 152Diapo 153Diapo 154Diapo 155Diapo 156Diapo 157Diapo 158Diapo 159