[PDF] Un Algorithme robuste de Segmentation Vidéo pour des

View - Download Un Algorithme robuste de Segmentation Vidéo pour des

Previous PDF

Next PDF

Un Algorithme robuste

de Segmentation Vid

´eo pour des Applications Temps R´eels

M. El Hassani, D. Rivasseau

Philips Semiconductors

Caen, FranceS. Jehan-Besson, M. Revenu

Laboratoire GREYC

Caen, FranceD. Tschumperl

´e, L. Brun

Laboratoire GREYC

Caen , FranceM. Duranton

Recherche Philips

Eindhoven,Pays-Bas

R

´esum´e

Dans ce papier, nous proposons un algorithme de segmen- tation vid ´eo temps r´eel conc¸u pourˆetre stable temporel- lement. Notre algorithme est bas

´e sur une segmentation

spatiale de l'image en r

´egions homog`enes qui sont mises

a jour au fil de la s´equence en utilisant des informations de mouvement. En ce qui concerne la segmentation spa- tiale, nous proposons une m

´ethode ascendante de segmen-

tation bas ´ee sur des fusions successives. Grˆace`a un ordre de fusion sp ´ecifique et`a un seuil adaptatif pour le pr´edicat, la m ´ethode donne de tr`es bons r´esultats sur des images naturelles (m ˆeme pour les r´egions textur´ees) avec peu de param `etres`a r´egler. De mani`ere`a am´eliorer la consis- tance temporelle de la segmentation pour une s

´equence

d'images, nous incorporons une information de mouve- ment via un masque bas

´e sur la d´etection des changements

d'intensit ´es entre deux images. Ce masque est conc¸u en uti- lisant `a la fois les diff´erences d'intensit´es entre image suc- cessives et la segmentation de l'image pr

´ec´edente. Notre

algorithme tourne en temps r

´eel sur un processeur TriMe-

dia pour des s

´equences de format CIF (Common Interme-

diate Format).

Mots clefs

Segmentation bas

´ee r´egions, Fusion de r´egions, Traitement de S ´equences Vid´eo, D´etection du mouvement, Consis- tance temporelle, Impl

´ementation mat´erielle, Temps r´eel.

1 Introduction

La segmentation de vid

´eos en r´egions homog`enes est cru-

ciale pour de nombreuses applications. Parmi elles, on peut citer l'estimation de mouvement bas

´ee r´egions et la conver-

sion du 2D au 3D o `u la segmentation est utilis´ee pour l'es- timation de la profondeur. La tendance actuelle se dirige egalement de plus en plus vers des traitement adapt´es au contenu de l'image (filtrage, rehaussement, compression orient ´ee objet) et donc bas´es sur une segmentation initiale de la vid ´eo. Toutes ces applications n´ecessitent l'obtention d'une segmentation pr

´ecise et stable temporellement. Par

ailleurs, les applications multim

´edia vis´ees n´ecessitent un

algorithme de traitement des s

´equences en temps r´eel.

Les m ´ethodes de segmentation spatiale peuventˆetre di- vis ´ees en deux cat´egories, les m´ethodes bas´ees r´egions et les m

´ethodes bas´ees contour. Dans la premi`ere cat´egorie[1], les transitions entre pixels sont calcul

´ees et les com-

posantes connexes peuvent alors

ˆetre extraites. Le prin-

cipal inconv

´enient de ces approches est que le calcul du

gradient est parfois impr

´ecis et tr`es sensible au bruit. De

plus il est alors difficile de tenir compte de propri

´et´es sta-

tistiques des r ´egions consid´er´ees. La seconde cat´egorie de m ´ethodes (i.e. bas´ees r´egions) est donc plus souvent uti- lis ´ee et c'est dans cette cat´egorie que se situe notre algo- rithme. Nous nous int

´eressons plus particuli`erement ici aux

m ´ethodes ascendantes qui op`erent par fusions successives [2,3, 4, 5]. Dans ces m

´ethodes, deux points importants sont

a consid´erer : l'ordre de fusion et le crit`ere de similarit´e.

Lorsque l'on traite de segmentation vid

´eo, la dimension

temporelle doit ˆetre ajout´ee et la segmentation en r´egions doit ˆetre stable temporellement. De nombreuses approches ont ´et´e test´ees. Quelques auteurs consid`erent le temps comme une dimension suppl

´ementaire et la vid´eo devient

alors un volume 3D [6]. D'autres approches utilisent une information de mouvement comme la d

´etection des chan-

gements d'intensit

´es ou les vecteurs mouvement [7, 8].

Nous n'abordons pas ici le suivi d'objet qui consiste `a suivre un objet au cours du temps (voir par exemple les travaux [9]). Dans ce papier, nous proposons une segmentation spatiale bas ´ee sur la fusion de r´egions. Cette fusion est faite dans un ordre sp ´ecifique qui est fonction de la diff´erence d'in- tensit ´e entre les pixels voisins. Par ailleurs, un crit`ere de si- milarit ´e bas´e sur les diff´erences de moyennes entre r´egions est utilis ´e pour la fusion. La fusion est arrˆet´ee`a l'aide d'un seuil adaptatif justifi

´e par une mod´elisation statistique

de l'image. Nous nous sommes bas

´es sur les travaux de

[2] en proposant une mod

´elisation statistique de l'image

qui conduit `a un seuil plus appropri´e pour la segmenta- tion en temps r

´eel. Notre m´ethode donne une segmentation

tr `es satisfaisante pour des images naturelles (mˆeme pour des images textur

´ees) avec peu de param`etres`a r´egler. De

mani `ere`a am´eliorer la consistance temporelle, nous propo- sons d'ajouter l'information de mouvement. Comme l'esti- mation du mouvement entre deux images est une op

´eration

co ˆuteuse, nous avons choisi de combiner un masque de d ´etection des changements d'illumination avec les infor- mations r ´egions contenues dans la segmentation spatiale de l'image pr ´ec´edente. En faisant des comparaisons au niveau pixelliqueetauniveau r

´egion,onobtientunalgorithmetr`es

1 efficace pour un faible coˆut calcul.

Notre algorithme tourne en temps r

´eel sur des s´equences

de format CIF sur le processeur TriMedia. De plus les r´esultats exp´erimentaux montrent l'applicabilit´e de notre m ´ethode sur des s´equences d'image que ce soit en terme de qualit ´e de la segmentation obtenue ou de stabilit´e tem- porelle.

Ce papier est organis

´e de la mani`ere suivante. L'algo-

rithme de segmentation spatiale est d

´etaill´ee dans la sec-

tion 2. L'introduction d'informations temporelles pour am ´eliorer la consistance est d´etaill´ee en section 3. Enfin dans la section 4, nous d

´eveloppons l'implantation de notre

algorithme. Les r

´esultats exp´erimentaux sont finalement

donn

´es section 5.

2 Segmentation spatiale

Consid

´erons une imageIde largeurWet de hauteurH,

D={1....W} × {1....H}est le domaine de l'image. I(p,n)l'intensit´e du pixel de positionp= (x,y)Tdans l'imagen.

La segmentation d'une image en r

´egions consiste`a trou-

ver une partition pertinente de l'image enmr´egions {S1,S2,..,Sm}. L'algorithme propos´e part du niveau pixellique et proc `ede par fusions successives pour aboutir a la segmentation finale (m´ethode ascendante). Un ordre sp ´ecifique de fusion est utilis´e ainsi qu'un seuil adaptatif pour stopper les fusions. Ces deux

´etapes sont d´etaill´ees

ci-apr `es et nous donnerons ensuite l'algorithme complet de segmentation.

2.1 Ordre de fusion

L'ordre de fusion est bas

´e sur les poids des transitions

comme dans [2, 10]. L'id

´ee est de fusionner d'abord ce qui

est similaire avant de fusionner ce qui est diff

´erent. Une

transitioneest un couple de pixels(p,p?)en 4-connexit´e.

La similarit

´e entre pixels est mesur´ee en calculant la dis- tance entre les intensit

´es des deux pixels. Pour des images

couleur, la similarit

´e est calcul´ee de la mani`ere suivante :

w(p,p?) =?

I?{Y,U,V}(I(p,n)-I(p?,n))2.(1)

Nous avons choisi l'espace couleurY UVqui est le format couleur utilis ´e pour le traitement des vid´eos ce qui nous evite ainsi une conversion. De plus, nous avons trouv´e que l'espace couleurY UVprocure une partition de l'image qui est, subjectivement, de qualit

´e meilleure que celle ob-

tenue avec l'espaceRGB. L'espaceL?a?b?donne des r ´esultats l´eg`erement meilleurs que l'espaceY UV, mais au prix d'une impl

´ementation coˆuteuse [11].

Les transitions sont ensuite tri

´ees dans l'ordre croissant de

leurs poidswet les couples de pixels correspondant sont trait ´es dans cet ordre pour la fusion. En ce qui concerne l'impl ´ementation, l'image est seulement parcourue deux fois pour ce tri. Le premier parcours permet de calculer le nombre de transitions de m

ˆeme poids, nombre qui eststock

´e dans une table. Cette table est ensuite utilis´ee pour allouer la m

´emoire pour ces transitions. Le second permet

de stocker chaque transition dans la partie de la m

´emoire

correspondante.

2.2 Crit`ere de fusion

Etantdonn

ces deux r ´egions doiventˆetre fusionn´ees. En cons´equence, un crit `ere de similarit´e entre r´egions doitˆetre choisi et evalu´e. En comparant la valeur de ce crit`ere`a un seuil, les r ´egions seront fusionn´ees ou non. Le choix du seuil est sou- vent difficile. Dans ce papier, nous utilisons un seuil adap- tatif qui d ´epend de la taille de la r´egion consid´er´ee. L'uti- lisation d'un tel seuil est justifi

´ee par le biais d'in´egalit´es

statistiques comme dans [2]. Nous proposons ici une in- terpr ´etation statistique plus simple de l'image qui nous conduit `a un crit`ere plus adapt´e pour une impl´ementation temps r ´eel. Nous pr´esentons d'abord ici le pr´edicat de fu- sion utilis

´e, puis sa d´emonstration.

Pr ´edicat de fusion.La moyenne des intensit´es de la r ´egionSiest calcul´e de la mani`ere suivante :

Si=1|Si|k=|Si|?

k=1I i(pk) o `uIi(pk)est l'intensit´e duk`emepixel de la r´egionSi. Le pr

´edicat de fusion est alors :

P(S1,S2) =?vraisi(

fauxsinon (2) avecgle niveau maximum deI(g= 255pour les images de composantes en pr

´ecision8bits). LA nota-

tion|Si|repr´esente la taille de la r´egionSi. Le param`etre Qpermet de r´egler la finesse de la segmentation. Dans les exp

´eriences, nous choisissonsQ= 2qui donne de

bons r ´esultats pour le format vid´eo CIF (taille des images

352×288).

Justification statistique du pr

´edicat.Classiquement,

l'imageIest consid´er´ee comme l'observation d'une image parfaiteI?et les pixels sont alors des observa- tions d'un vecteur de variables al

´eatoires (v.a) not´eX=

(X1,..,Xn)T. Le pr´edicat de fusion est bas´e sur l'in´egalit´e de McDiarmid [12] donn

´ee ci-apr`es :

Theorem 2.1(L'in´egalit´e de McDiarmid) SoitX= (X1,X2,...,Xn)une famille denv.a. ind´ependantes avec X kprenant ses valeurs dans un ensembleAkpour chaque k. Supposons que la valeur r´eelle de la fonctionfdefinie sur? xetx?diff`erent seulement sur leursk`emecoordonn´ee. Soit E(f(X))l'esp´erance def(X)alors quelque soitτ≥0, -2τ2/? kc 2 k? (3) Nous nous int´eressons ici`a deux r´egions adjacentesS1et S

2. Dans ce cas, nous consid´erons le vecteur de variables

al

´eatoires suivant :

(X1,...,Xn) =?I?1(p1),...,I?1(p|S1|),I?2(p1),...,I?2(p|S2|)? AvecIi(pj)l'intensit´e duj`emepixel deSicorrespondant`a l'observationdelavariableal

´eatoireI?i(pj).Danscecas,la

taille du vecteur de variables al

´eatoires estn=|S1|+|S2|.

De mani

`ere`a appliquer le th´eor`eme 2.1, nous choisissons comme fonctionf(x) =?

S1-S2?. Pour cette fonction,

nous trouvons que? kc2 k=g2? 1 |S1|+1|S2|?

Par inversion du th

´eor`eme, nous avons avec une probabilit´e

avecQ=1

2?ln(2δ), etE(S)l'esp´erance deS. SiS1et

S

2appartiennent`a la mˆeme r´egion dansI?, l'esp´erance

E?

S1-S2?sera nulle et le pr´edicat suit.

2.3 Algorithme de segmentation

L'algorithme 1 donne le traitement complet pour la segmentation spatiale. L'algorithme de fusion utilise la structure de donn

´ees "UNION-FIND"[13]. La fonction

UNIONfusionne deux r´egions en une seule r´egion et la fonctionFINDpermet d'identifier la r´egion d'appar- tenance d'un pixel.

Algorithm 1La segmentation spatiale

Calcul des poids des transitions et de l'histogramme correspondant Tri par ordre croissant des transitions en fonction de la valeur de leur poidsw. fori:= 1to2|I|do

Lecture de lai`emetransition :(p1,p2);

S

1=FIND(p1);

S

2=FIND(p2);

ifP(S1,S2) =Truethen

UNION(S1,S2)

end if end for

3 Am´elioration de la consistance

temporelle

Laqualit

´ed'unesegmentationvid´eod´epend nonseulement de la bonne s ´eparation entre les r´egions significatives dans l'image, mais aussi de la consistance temporelle de cette s´eparation. En effet, si dans deux images successives, une m ˆeme r´egion est segment´ee diff´eremment, ce qui peutˆetre d ˆu au bruit, ou`a des situations particuli`eres comme l'oc- clusion, la deocclusion, alors les r

´esultats de la segmenta-

tion seront difficilement exploitables dans des applicationscomme l'am

´elioration de l'image ou la conversion 2D/3D.

Quelques auteurs [8] utilisent les vecteurs de mouvements pour am ´eliorer la consistance temporelle de la segmenta- tion vid ´eo. Or l'estimation de mouvement est tr`es coˆuteuse en temps de calcul et n'est pas toujours fiable. Dans ce papier nous utilisons un masque de changement d'inten- sit ´es (CDM) combin´e avec la segmentation spatiale pour am ´eliorer la coh´erence temporelle de la segmentation. LeCDMest calcul´e en utilisant la diff´erence d'in- tensit ´es entre les images et la segmentation de l'image pr ´ec´edente. Premi`erement, on d´etecte les variations d'in- tensit ´e des pixels en utilisant la diff´erence entre deux images cons

´ecutives. Ensuite, nous exploitons la seg-

mentation de l'image pr

´ec´edente afin de classifier les

pixels au niveau r

´egion. Si on consid`ere l'image cou-

ranteI(:,n)et l'image pr´ec´edenteI(:,n-1), La diff ´erence entre les imagesFDest donn´ee parFD(p) = |I(p,n)-I(p,n-1)|. Cette diff´erence est classiquement seuill ´ee pour distinguer les variations d'intensit´e des pixels dues aux objets en mouvement de celles dues au bruit. SoitLLe r´esultat de seuillage de l'imageFD. Un pixel p, avecL(p) = 1est un pixel classifi´ee comme chan- geant, c'est `a dire que pour ce pixel, la variation d'inten- sit ´e entre deux images est sup´erieure`a un seuil. Ensuite on utilise la segmentation pr

´ec´edente pour convertir leCDM

du niveau pixel au niveau r

´egion, ce qui est plus fiable.

Pour chaque r

´egion dans la segmentation pr´ec´edenteSi, on calculeτ(Si), qui repr´esente le ratio des pixels chan- geants dans la r

´egionSi. Nous avonsτ(Si) =Ni,changeant

|Si|, ouNi,changeantest le nombre de pixels changeant dans la r ´egion. Les pixels sont classifi´es par la suite en trois cat

´egories :

CDM(p) =?

1si(τ(Si)> tr2)et(L(p) = 1).

2si(τ(Si)> tr2)et(L(p) = 0).(4)

o `utr2est une constante positive. Plus cette constante est importante, plus la segmentation sera stable mais on risque alors de ne pas segmenter correctement les zones en mou- vement. La valeur du seuiltr2est donc choisie faible afin de ne pas manquer une r

´egion en mouvement. Dans nos

exp ´eriences, nous avons pristr2= 0.01(i.e. on consid`ere qu'une r ´egion a boug´e, si elle contient au moins1%de pixels changeant, sinon elle est consid

´er´ee comme sta-

tique).

Les pixels appartenant

`a une r´egion statique sont´etiquet´es en utilisantCDM(p) = 0. Les deux autres´etiquettes,1,2, concernent les pixels dans les r

´egions qui ont boug´e. Se-

lon la valeur de la diff

´erence entre images, appel´ee iciFD,

Le pixel est qualifi

´e comme´etant changeantCDM(p) =

1ou non changeantCDM(p) = 2. Une telle classi-

fication est alors utilis

´ee pour segmenter l'image cou-

rante. Premi `erement, Les r´egions statiques sont gard´ees telles qu'elles ´etaient segment´es dans l'image pr´ec´edente. Deuxi `emement, on applique un algorithme d'extraction de composantes connexes (CCL)[14] afin d'extraire les com- posantes connexes des pixels ayantCDM(p) = 2. Cette deuxi `eme´etape construit des germes`a partir de la seg- mentation prquotesdbs_dbs29.pdfusesText_35

[PDF] calculer taille image pixel

[PDF] 300 dpi en mo

[PDF] poids d'une image definition

[PDF] photo haute définition c est quoi

[PDF] les fonctions en langage c exercices corrigés

[PDF] les tableaux en c exercices corrigés pdf

[PDF] somme et différence de nombres relatifs 4ème exercices

[PDF] le perimetre d un cercle

[PDF] calcul force verin hydraulique

[PDF] comment calculer l'aire d'une forme géométrique quelconque

[PDF] calcul superficie forme irrégulière

[PDF] calcul surface quadrilatère irrégulier

[PDF] calcul surface polygone irrégulier

[PDF] sécurité incendie habitation 2ème famille

[PDF] porte coupe feu reglementation incendie