D (cid:2)nition dune force dattraction aux LPE pour la segmentation par
contours actifs
Annabelle GOUZE, C dric DE ROOVER, Beno(cid:238)t MACQ
Laboratoire T l communications, Universit catholique de Louvain
Place du Levant 2, 1348 Louvain la Neuve, Belgique
[email protected], [email protected], [email protected]
R sum (cid:150) Dans cet article, nous traitons du problAme de la segmentation vid o. Nous proposons une nouvelle m thode qui combine les contours
actifs et une pr -segmentation par les LPE (lignes de partage des eaux). Les m thodes LPE traitent ef(cid:2)cacement les images couleurs par une
sursegmentation en r gions de couleurs homogAnes. Dautre part, les contours actifs permettent dobtenir des r sultats r guliers. Lalgorithme
de segmentation propos se compose de deux tapes. Dans un premier temps, les contours actifs voluent sous un critAre permettant de d tecter
un object en mouvement dans une s quence vid o (cid:224) cam ra (cid:2)xe. Une incertitude sur le mouvement peut induire une impr cision sur la position
du contour (cid:2)nal ainsi que des art facts. Aussi, nous af(cid:2)nons les r sultats en introduisant une force dattraction aux LPE. La m thode propos e
am liore la segmentation en augmentant la pr cision et la r gularit des r sultats retourn s par les contours actifs bas s mouvement et les LPE.
Abstract (cid:150) In this paper we address the problem of video segmentation. We propose a new method which combines an active contour and
a watershed presegmentation. On the one hand, watershed methods are very ef(cid:2)cient to provide an oversegmentation of homogeneous color
regions. On the other hand, active contours methods are ef(cid:2)cient to obtain a smooth segmentation. The proposed segmentation algorithm is
performed in two steps. We (cid:2)rst apply an active contour method to segment moving objects in video for static camera. The incertitude on the
motion induces artifacts on the resulting contours. Then, the propagation is driven by the distance to the watershed boundaries to re(cid:2)ne the
results. The proposed method provides (cid:2)ner and smoother results than moving object segmentation by active contours and than watersheds.
1
Introduction
La segmentation dimages et de s quences vid o vise (cid:224) par-
titionner les donn es en diff rentes zones dint rRt a(cid:2)n de per-
mettre linterpr tation et lanalyse dimage. La segmentation
peut servir (cid:224) d limiter de maniAre pr cise les objets de larriAre-
plan pour Rtre utilis s par des applications telle que la post-
production. Cette derniAre n cessite une segmentation (cid:2)ne a(cid:2)n
de d limiter avec pr cision le plan objet de larriAre-plan et ne
requiAre pas une volution temps-r el. Plusieurs techniques ont
t d velopp es aux cours de ces derniAres d cennies, notam-
ment les m thodes par contours actifs et par LPE (lignes de
partages des eaux). La segmentation par contours actifs permet
de d limiter les contours dun ou plusieurs objets s mantiques.
Les contours actifs se r vAlent ef(cid:2)cace pour le suivi dobjets
en mouvement, cependant la m thode souffre dun manque de
pr cision sur la position du contour d (cid:224) un trop faible mou-
vement et (cid:224) la dif(cid:2)cult destimer larriAre plan. Dautre part,
les m thodes de segmentation LPE retournent une image sur-
segment e. Un algorithme de fusion peut Rtre employ en vue
de restreindre le nombre de r gions. La segmentation obte-
nue souffre, n anmoins, dun manque de r gularit . De r cents
travaux ont combin les snakes et les LPE. Nguyen [11] et
Park [13] ont d crit comment repr senter une segmentation
LPE comme un problAme de minimisation d nergie. Nguyen
opAre une segmentation LPE en plusieurs r gions et r gularise
le r sultat en introduisant une quation d nergie bas e sur les
distances topologiques au centre de gravit des r gions.
Larticle aborde le problAme autrement et d crit comment ex-
ploiter de maniAre ef(cid:2)cace la pr -segmentation LPE dans un
algorithme de contours actifs. En effet, nous pr sentons un nou-
veau critAre d nergie bas sur la distance aux lignes LPE. La
d rivation de cette nergie d termine une force dattraction vers
les bords des lignes LPE les plus proches et permet dobte-
nir une courbe r guliAre. Notre algorithme se d compose en
deux tapes. Dans un premier temps, nous traquons les objets
en mouvement avec un simple critAre mouvement bas r gion.
Et dans un second temps, nous appliquons la nouvelle force
dattraction aux LPE a(cid:2)n daf(cid:2)ner les r sultats de la segmenta-
tion. Cette volution s quentielle permet de conduire la courbe
sans Rtre ralenti ou stopp par les lignes LPE ind sirables.
Cet article introduit en section 2 les m thodes de segmentation
par LPE et par contours actifs. La section 3 d crit la m thode
originale combinant les segmentations par contours actifs et par
LPE. En(cid:2)n, la section 4 montre des r sultats trAs concluants.
2
Introduction (cid:224) la segmentation
2.1 LPE : lignes de partage des eaux
Toute image en niveaux de gris, telle quune image de gra-
dient couleur, peut Rtre consid r e comme une surface topo-
graphique, contenant des monts, des plateaux et des vall es.
La transformation morphologique par LPE a pour but de di-
viser cette surface topographique en diff rents bassins s par s
par des lignes de partage des eaux [10]. Ces LPE partitionnent
limage en diff rentes r gions homogAnes. Le d savantage ma-
jeur des algorithmes LPE est leur haute sensibilit au bruit,
il en r sulte une sur-segmentation due (cid:224) un grand nombre de
LPE. Cette sur-segmentation peut Rtre r solue soit en fusion-
nant les r gions, soit en limitant directement le nombre de r -
gions cr es par lutilisation de marqueurs. A(cid:2)n de faciliter le
Advertisement
processus de fusion, Salembier a r organis les r gions sur-
segment es dans un arbre de partition binaire [15]. Malgr le
processus de fusion, des points faibles subsistent. Les contours
ne sont pas r guliers et le suivi temporel des r gions demeure
non trivial.
o est une fonction d rivable de la distance g om trique u :
u(X; ref ) =
minY 2 ref jX Y j
minY 2 ref jX Y j
0
si X est (cid:224) ext rieur de ref
si X est (cid:224) lint rieur de ref
(4)
X est un point de et Y les coordonn es dun point du contour
de r f rence ref . En utilisant la m thode de d rivation de Gas-
taud qui suppose pour d river lint grale que ( ) est param -
tr e par p dans [0; 1], et ainsi que u et d sont des fonctions
continues en p, le critAre est alors exprim comme suit :
2.2 Contours actifs
La segmentation par contours actifs consiste (cid:224) d former un
contour initial et (cid:224) le faire voluer vers les bords dun ou plu-
sieurs objets (cid:224) segmenter. L volution est conduite par une force
(une quation aux d riv es partielles) manant de la minimisa-
tion dune fonctionnelle d nergie [18, 2, 8, 12]. LEDP fait
voluer le contour vers un minimum (local) d nergie assimil
aux bords de lobjet. A lorigine, les snakes [9] ou les contours
actifs g od siques [1] sont calcul s gr(cid:226)ce (cid:224) la minimisation
dune int grale dont les caract ristiques d pendaient des contours.
Par la suite, de nouvelles fonctionnelles d nergie combinant
des int grales de contours et des int grales de r gions sont ap-
parues. Elles furent introduites par [3] et [14], et d velopp s
par plusieurs auteurs [18, 2, 8, 12, 17].
3 Contours actifs contraints par les LPE
Dans cette section, nous proposons un critAre bas sur la seg-
mentation LPE, ensuite nous introduisons le sch ma de seg-
mentation par contour actif. Lid e est de segmenter s quentiel-
lement les objets en mouvement en deux tapes compl men-
taires. La premiAre tape permet de cibler les objets en mou-
vement et la seconde consiste (cid:224) af(cid:2)ner le premier r sultat de
segmentation en attirant les contours vers les bord des r gions
de couleurs homogAnes d limit es par les LPE. Cela suppose
que la d tection des objets retourne un contour proche des LPE
correspondant (cid:224) la meilleure solution.
3.1 D (cid:2)nition de la force dattraction aux LPE
Consid rons une carte de sur-segmentation d (cid:2)nie par les
LPE, notre but est dattirer le contour actif vers la ligne LPE
la plus proche. Pour ce faire, nous introduisons un critAre qui
contraint la distance du contour aux bords des r gions LPE. Le
critAre, JW , est exprim comme suit :
JW ( ) =
Z ( )
d2(X; W )
dp
(5)
@X
@p
LhypothAse de continuit signi(cid:2)e que nous ne coupons pas le
squelette des r gions LPE. Cette hypothAse nous permet dob-
tenir lEDP, ensuite nous g n raliserons en tendant la force
d volution aux cas singuliers. Notons toutefois que cette tape
de segmentation est r alis e en vue daf(cid:2)ner un premier pas,
les chances de couper le squelette sont fortement r duites. Le
gradient en chaque point de la carte de distance est donn par
NW = rd = X Y
jX Y j . Notons que d = juj et que
X Y
si X est (cid:224) lext rieur de ref
jX Y j
X Y
si X est (cid:224) lint rieur de ref
jX Y j
ru =
Advertisement
(
(6)
En d (cid:2)nissant par N la normale unitaire interne (cid:224) , nous ob-
tenons < rd; N > d =< ru; N > u. La d riv e de (5)
sobtient alors en exploitant les r sultats de [6] :
D
dp
@X
@p
J 0
W ( ) =
Z
0
1
<
@X
@
;
2 < NW; N > d "d2
N >
(7)
o " est la courbure du contour. A partir d riv e, nous obtenons
l quation d volution suivante :
@ W
@
=
2 < NW; N > d + "d2
N = FW N
(8)
D
Nous g n ralisons cette quation d volution aux points sin-
guliers. En d = 0, le point d volution X appartient aux LPE
et NW nest pas d (cid:2)ni. N anmoins, les LPE sont atteintes et
la force dattraction doit Rtre nulle. Aussi nous d (cid:2)nissons la
force d volution FW en d = 0 par FW = 0. Si il existe plus
dune valeur Ymin pour un X donn , le point X est alors un
point singulier. Dans ce cas, X se situe sur le squelette de la
r gion et NW nest pas d (cid:2)ni de maniAre unique. Le choix de
< NW; N > d pend de limpl mentation et de la discr tisa-
tion. Num riquement, nous calculons NW par un gradient cen-
tr pour viter de privil gier une mauvaise direction. Comme
partout, la courbe volue dans la direction de N , mais la force
et le sens de propagation sont surtout in(cid:3)uenc s par " (puis-
quil est facteur de d2 et que d est grand sur le squelette).
JW ( ) =
Z ( )
d2( ( ); W )ds
3.2 Segmentation en deux tapes
(1)
o W est un ensemble de courbes correspondantes aux LPE,
d est une distance g om trique des points d volution (cid:224) W . d
peut Rtre calcul par les algorithmes de carte de distance [4].
La d (cid:2)nition de d pour X 2 ( ) est :
d(X; W ) = minY 2W jX Y j = jX Yminj :
(2)
Dans [6], Gastaud a aussi d (cid:2)ni une nergie bas e sur la dis-
tance sign e (cid:224) un simple contour de r f rence :
3.2.1 Premier pas : segmentation par contours actifs par
d tection dobjets en mouvement
La premiAre tape met en oeuvre la d tection des objets en
mouvement pour un simple critAre d (cid:2)ni dans [7] par :
JM ( ) =
obj dxdy+
back jIn Bnj dxdy+
ds
Z Z:obj ( )
Z Z:back( )
Z ( )
(9)
o obj, back et sont des constantes positives. Bn repr -
Advertisement
sente lestimation du fond et In la trame courante. L quation
d volution est d (cid:2)nie par :
JC( ) =
Z
(u( ; ref ))ds
(3)
@ M
@
= (obj back jIn Bnj + ") N
(10)
Cette tape conduit le contour actif prAs des bords de lobjet (cid:224)
segmenter. Cependant, la pr cision peut Rtre am liorer en af(cid:2)-
nant le r sultat par une seconde volution.
3.2.2 Second pas : Segmentation par contours actifs conduits
par une force dattraction aux LPE
Pr -segmentation par LPE
La technique dimmersion introduite dans [16] retourne une
premiAre partition de limage en r gions de couleurs homo-
gAnes. Le nombre de r gions est ensuite r duit par le processus
de fusion pr sent en [5]. Ce processus est bas sur un critAre
spatio-temporel. Aussi les LPE ne correspondent pas aux lignes
de plus fort gradient couleur de limage. Les LPE introduites
dans notre algorithme correspondent aux bornes non-lisses des
r gions de la partition.
5 Conclusion
Dans cet article, nous avons pr sent une nouvelle m thode
de segmentation vid o combinant les m thodes par contours
actifs et par LPE. Lalgorithme propos est r alis s quentiel-
lement en deux tapes. La premiAre exploite un critAre de mou-
vement. La seconde attire le contours vers la ligne de partage
des eaux la plus proche. Ces lignes s parent les r gions de cou-
leurs homogAnes. La partie originale des pr sents travaux est la
d (cid:2)nition dun critAre d nergie bas sur les LPE. Les r sultats
obtenus sont performants. Il est toutefois (cid:224) noter que la d tec-
tion de mouvement doit Rtre suf(cid:2)samment bonne pour que les
LPE globalement les plus proches correspondent (cid:224) la meilleure
solution. Cet approche est applicable pour la d tection dobjet
en mouvement pour une cam ra statique. Une alternative pour
des travaux ult rieurs est d tendre la m thode aux s quences
(cid:224) cam ra mobile en changeant le premier critAre.
Application des contours actifs
6 Remerciement
Le second pas consiste (cid:224) attirer le contour vers les LPE, et (cid:224)
contraindre la r gularit du contour. Aussi, nous d (cid:2)nissons un
critAre combinant l nergie des distances aux LPE (introduit en
3.1) et un terme constant. Ce dernier a pour r(cid:244)le de r gulariser
le contour (cid:2)nal en contraignant la longueur du contour actif.
L nergie est exprim e comme suit :
Les auteurs remercient A. Herbulot, E. Debreuve et le Prof
Barlaud pour leur aide dans la r (cid:3)exion th orique et la r gion
wallonne pour la r alisation de ce projet.
R f rences
[1] V. Caselles, R. Kimmel et G. Sapiro, Geodesic active contours, IJCV, vol
JW ( ) =
Z ( )
D
W d2( ( ); W ) +
ds
(11)
22, n 1, p 61-79, 1997.
o W et sont deux constantes positives. L quation (8) et
la d riv e de (11) retournent l quation d volution :
@ W
@
=
W
2 < NW; N > d + "d2
+ "
N:
(12)
D
Le premier terme attire le contour vers les LPE et le second
le lisse. Dans le cas o le contour actif coupe le squelette des
r gions LPE, le problAme est trait comme voqu dans 3.1.
Le terme de r gularit et la rigidit de la courbe permettent
de ramener les points de part et dautre du squelette. Notons
Advertisement
toutefois, que lalgorithme est appliqu aux r sultats (cid:2)nals de
la premiAre tape de segmentation, aussi le contour est proche
des LPE. Le risque de couper le squelette est ainsi r duit.
4 R sultats :
Les performances de la m thode propos e sont ici valu es
sur la s quence Akiyo pour obj = 0:9, back = 1:2, = 6,
W = 0:2 et = 1:5 et la s quence Mother (Fig. 2) for
obj = 1:5, back = 1:2, = 9, W = 0:2 et = 2:25. Les
(cid:2)gures 1 (a), (b) et (c) pr sentent des r sultats interm diaire et
(cid:2)nal retourn s par le premier pas de lalgorithme. Nous obser-
vons quelques disparit s entre le contours et le bord de lobjet.
La (cid:2)gure 1 (d) pr sente limage sur-segment e par les LPE, (cid:224)
partir de laquelle la carte de distance est calcul e. Les (cid:2)gures 1
(e) et (f) montrent la propagation et les r sultats retourn s par
le second pas. Nous constatons une nette am lioration des r -
sultats de la premiAre segmentation tant du point de vue de la
(cid:2)nesse que de la r gularit .
[2] Chan, T. et Vese, L., Active contours without edges, IEEE Trans. on Im.
Process., vol 10, n 2, p 266-277, 2001.
[3] L. Cohen, E. Bardinet et N. Ayache, Surface reconstruction using active
contour models, SPIE Conf. on Geom. Meth. in Comput. Vis., 1993.
[4] O. Cuisenaire et B. Macq, Fast Euclidean distance transformations by
propagation using multiple neighbourhoods, Computer vision and Image
understanding, Comput. vis. and Im. understanding, vol 76, n 2, p 163-
172, 1999.
[5] C. De Roover, M. Gabbouj et B. Macq, An accurate semiautomatic seg-
mentation scheme based on watershed and change detection mask, Proc.
of SPIE, Im. and Video Comm. and Process., vol. 5685, jan, 2005.
[6] M. Gastaud, M. Barlaud et G. Aubert, Combining Shape Prior and Sta-
tistical Features For Active Contour Segmentation, IEEE TCSVT spec.
sess. on Audio and Video Anal. for Interact. Multim. Services, mai, 2004.
[7] S. Jehan-Besson, M. Barlaud, G. Aubert, A 3-Step Algorithm using
Region-Based Active Contours for Video Objects Detection, EURASIP
JASP, 2002.
[8] S. Jehan-Besson, M. Barlaud et G. Aubert, DREAM2S : Deformable Re-
gions driven by an Eulerian Accurate Minimization Method for image
and video segmentation, Int. Journ. of Comput. Vis., vol 53, n 1, 2003.
[9] Kass, M., Witkin, A. et Terzopoulos, D., Snakes : Active contour mo-
dels,IJCV ; vol 1, p 321-332, 1988.
[10] F. Meyer et S. Beucher, Morphological segmentation, Journal of Visual
Comm. and Image Rep., vol 1, n 1, p.21-46, 1990.
[11] H.T. Nguyen, M. Worring et R. van den Boomgaard, Watersnakes :
energy-driven watershed segmentation, IEEE Trans. on Pat. Anal. and
Mach. Intell., vol 25, n3, p. 300-342,2003.
[12] N. Paragios et R. Deriche, Geodesic Active Regions and Level Set Me-
thods for Supervised Texture Segmentation,Int. Journ. of Comput. Vis.,
vol 46, n 3, 2002.
[13] J. Park et J.M. Keller, Snakes on the Watershed, IEEE Trans. On Pat.
Anal. and Mach. Intell.,vol. 23, n 10, p. 1201-1205, 2001.
[14] R. Ronfard, Region-based strategies for active contour models, Int.
Journ. of Comput. Vis., vol 13, n 2, p 229-251, 1994.
[15] P. Salembier et L. Garrido, Binary Partition Tree as an Ef(cid:2)cient Repre-
sentation for Image Processing,Segmentation, and Information Retrieval,
IEEE Trans. on Im. Process., vol 9, n 4, 2000.
(a) Contour initial
(b) Pas 1 : r sultat interm diaire
(c) Pas 1 : Segmentation (cid:2)nale,
contour initial du 2Ame pas
(d) Pas 2 : pr -segmentation LPE
(donn es)
(e) Pas 2 : r sultat interm diaire
(f) Pas 2 : segmentation (cid:2)nale
FIG. 1 (cid:150) Segmentation en deux phases (Akiyo) : (b) propagation et (c) r sultat de la segmentation dobjets en mouvement (pas 1) ;
(e) propagation et (f) r sultat de la segmentation par attraction aux LPE (pas 2)
(a) Pas 1 : r sultat
(b) Pas 2 : Pr -segmentation LPE
(c) Pas 2 : segmentation (cid:2)nale
FIG. 2 (cid:150) Segmentation de Mother : (a) segmentation par d tection dobjet en mouvement, (b) LPE servant (cid:224) calculer la carte de
distance, (c) R sultat aprAs les 2 tapes de segmentation.
[16] L. Vincent et P. Soille, Watersheds in Digital Spaces : An Ef(cid:2)cient Algo-
rithm Based on Immersion Simulations, IEEE Trans. on Pat. Anal. and
Mach. Intell., vol 13, n 6, 1991.
[17] A. Yezzi, A. Tsai et A. Willsky, A statistical approach to snakes for bi-
modal and trimodal imagery, IEEE ICIP, Kobe, 1999.
[18] S Zhu et A. Yuille, Region competition : unifying snakes, region growing,
and Bayes/MDL for multiband image segmentation, PAMI, vol 18, p 884-
900, sept. 1996.