PROD TYPE: COM PP:1 col fig nil PR2195 DTD VER: ED: PrathibaPAGN: Vidya SCAN: global
12 pages
English

PROD TYPE: COM PP:1 col fig nil PR2195 DTD VER: ED: PrathibaPAGN: Vidya SCAN: global

-

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
12 pages
English
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Niveau: Secondaire, Lycée, Terminale
UN CO RR EC TE D PR OO F PROD. TYPE: COM PP:1-12 (col.fig.: nil) PR2195 DTD VER: 5.0.1 ED: PrathibaPAGN: Vidya -- SCAN: global ARTICLE IN PRESS Pattern Recognition ( ) – 1 Semi-supervised statistical region refinement for color image segmentation3 Richard Nocka,?, Frank Nielsenb aGRIMAAG-Département Scientifique Interfacultaire, Université des Antilles-Guyane, Campus de Schoelcher, BP 7209, 97275 Schoelcher,5 Martinique, France bSony Computer Science Laboratories, Inc., 3-14-13 Higashi Gotanda, Shinagawa-Ku, Tokyo 141-0022, Japan7 Received 9 August 2004 Abstract9 Some authors have recently devised adaptations of spectral grouping algorithms to integrate prior knowledge, as constrained eigenvalues problems. In this paper, we improve and adapt a recent statistical region merging approach to this task, as a non-11 parametric mixture model estimation problem. The approach appears to be attractive both for its theoretical benefits and its experimental results, as slight bias brings dramatic improvements over unbiased approaches on challenging digital pictures.13 2004 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved. Keywords: Image segmentation; Semi-supervised grouping15 1. Introduction Grouping is the discovery of intrinsic clusters in data [1].

  • algorithm

  • regions obtained

  • well-known benchmark

  • single event's

  • grouping

  • segmentation

  • algorithm probabilistic-sorted image11


Sujets

Informations

Publié par
Nombre de lectures 23
Langue English
Poids de l'ouvrage 1 Mo

Exrait

13335373931434547494

1.Introduction
accuratecandidacy,assegmentationshouldcomeupwith
partition(s)fromacandidatesegmentationset
[3]
.
GroupingisthediscoveryofintrinsicclustersindataWiththeadventofmediamakingiteasierandcheaperto
[1]
.Imagesegmentationisaparticularkindofgroupingin
collectandstoredigitalimages,unconstraineddigitalpho-
whichdataconsistsofanimage,andthetaskistoextracttographicimageshaveraisedthischallengeevenfurther
asregionstheobjectsausermayfindconceptuallydistincttowardsbothcomputationalefficiencyandrobustprocess-
fromeachother.Theautomationandoptimizationofthising.Considerforexamplethewell-knownbenchmarkimage
taskfacecomputationalissues
[2]
andanimportantcon-
lena
in
Fig.1
.Userswouldcertainlyconsiderthehatof
ceptualissue:basically,segmentationhasaccessonlytothethegirlasanobjectdifferentfromtheblurredbackground,
descriptionsofpixels(e.g.colorlevels)andtheirspatialre-andmostwouldconsiderhershoulderasdifferentfromher
lationships,whileauseralwaysuseshigherlevelofknowl-face.Nevertheless,duetothedistributionofcolors,itisvir-
edgetoclustertheimageobjects.Withoutsuchasignifi-tuallyimpossibleforsegmentationtechniquesbasedsolely
cantpriorworldknowledge,theaccuracyofgroupingisnotonlow-levelcues,suchasthecolors,tomakeacleansepa-
meanttobeoptimalityorevennear-optimality,butratherrationoftheseregions.Therightimagedisplaystheresult
ofouralgorithm.Theregionsfoundhavewhiteborders.

Thisresultispresentedmoreindepthintheexperimental
Correspondingauthor.Tel.:+596727424;fax:+596727362.
section(Fig.
2
).Noticefromtheresultthesegmentationof
E-mailaddresses:
richard.nock@martinique.univ-ag.fr
(R.Nock),
frank.nielsen@acm.org
(F.Nielsen)
thehat,cleanlyseparatedfromthebackground,andalsothe
URLs:
http://www.univ-ag.fr/

rnock
,
segmentationofthegirl’schin,whichisseparatedfromher
http://www.csl.sony.co.jp/person/nielsen/
.
shoulder.
0031-3203/$30.00

2004PatternRecognitionSociety.PublishedbyElsevierLtd.Allrightsreserved.
doi:10.1016/j.patcog.2004.11.009

911232527292

Abstract
Someauthorshaverecentlydevisedadaptationsofspectralgroupingalgorithmstointegratepriorknowledge,asconstrained
eigenvaluesproblems.Inthispaper,weimproveandadaptarecentstatisticalregionmergingapproachtothistask,asanon-
parametricmixturemodelestimationproblem.Theapproachappearstobeattractivebothforitstheoreticalbenefitsandits
experimentalresults,asslightbiasbringsdramaticimprovementsoverunbiasedapproachesonchallengingdigitalpictures.

2004PatternRecognitionSociety.PublishedbyElsevierLtd.Allrightsreserved.
Keywords:
Imagesegmentation;Semi-supervisedgrouping

9113151

www.elsevier.com/locate/patcog

PatternRecognition()–

Semi-supervisedstatisticalregionrefinementforcolorimage
segmentation
ba∗,RichardNock,FrankNielsen
a
GRIMAAG
-DépartementScientifiqueInterfacultaire,UniversitédesAntilles-Guyane,CampusdeSchoelcher,BP7209,97275Schoelcher,
Martinique,France
b
SonyComputerScienceLaboratories,Inc.,3-14-13HigashiGotanda,Shinagawa-Ku,Tokyo141-0022,Japan
Received9August2004

1357

SERPNIELCITRAlabolg:NACS--aydiV:NGAPabihtarP:DE1.0.5:REVDTD5912RP)lin:.gif.loc(21-1:PPMOC:EPYT.DORP
13579113115

2

RAITPCRL2E1I9N5RPESR.Nock,F.Nielsen/PatternRecognition()–

Fig.1.Image
lena
(left),andoursegmentation(right).Inthesegmentation’sresult,regionsfoundarewhitebordered(seetextfordetails).

Fig.2.Image
lena
(upperleft),anditssegmentationby
SRRB
,withoutbias(w/o),andwithbias(w/,see
Fig.1
).Inthesegmentations’
results,regionsfoundaredelimitedwithwhiteborders.Wehave
m
=
4
,
|
V
1
|=
2
,
|
V
2
|=
2
,
|
V
3
|=
2
,
|
V
4
|=
2.Theupperrighttabledisplays
someofthelargestregionsextractedfromthesegmentation(Reg.#X).Thebottomtableshowshow
lena
’sfaceisbuiltfromthetwo
modelswhosepixels,denotedbyredtrianglesontheupperrightimage,havebeenpointedbytheuser(eachmodel’scolorisrandom);the
numberbelow
×
2000is
SRRB
’siterationnumber.

CommongroupingalgorithmsforimagesegmentationOurapproachtosegmentation,whichgivestheresultsof
useaweightedneighborhoodgraphtoformulatethespa-
Fig.1
,isbasedonasegmentationframeworkpreviously
tialrelationshipsamongpixels
[1–6]
andthenformulatethe
studiedbyYuandShi
[1,7]
:groupingwithbias.Itispar-
segmentationasagraphpartitioningproblem.Anessentialticularlyusefulfordomainsinwhichtheusermayinteract
differencebetweenthesealgorithmsisthelocalityofthewiththesegmentation,byinputtingconstraintstobiasits
groupingprocess.ShiandMalik
[3]
andYuandShi
[1,7]
result:sensormodelsinMRF
[8]
,Human–computerinter-
solveitfromaglobalstandpoint,whereasFelzenszwalbandaction,spatialattentionandothers
[1]
.Groupingwithbias
Huttenlocher
[4]
,Nock
[2]
andNielsenandNock
[5]
make
isbasicallyonestepfurthertowardstheintegrationofthe
greedylocaldecisionstomergetheconnexcomponentsofuserintheloop,comparedtothemethodofgeneralexpec-
inducedsubgraphs.Sincesegmentationisaglobaloptimiza-tationsofagoodsegmentationintegratedinnon-purposive
tionprocess,theformerapproachisaprioriagoodcan-grouping
[9]
;itissolvedbypointingintheimagesomepix-
didatetotackletheproblem,evenwhenitfacescomputa-els(the
bias
)thattheuserfeelbelongtoidentical/different
tionalcomplexityissues
[3]
.However,strongglobalproper-
objects,andthensolvingthesegmentationasaconstrained
tiescanbeobtainedforthelatterapproaches,suchasqual-groupingproblem:pixelswithidenticallabels
must
belong
itativeboundsontheoverallsegmentationerror
[4,2]
,or
tothesameregioninthesegmentation’sresult,whilepixels
evenquantitativebounds
[5]
.
withdifferentlabels
mustnot
belongtothesameregion.The

7191213252729213

135791131517191123252729213335373931434457494153555

RAITPR2195

LCENIRPESR.Nock,F.Nielsen/PatternRecognition()–

solutionfortheglobalapproachofYuandShi
[1,7]
ismath-
ematicallyappealing,butitiscomputationallydemanding,
anditrequiresquiteanextensivebiasforgoodexperimental
resultsonsmallimages.Furthermore,itmakesitdifficultto
handletheconstraintsthatsomepixelsmustnotbelongto
thesameregions;thatiswhythistechniqueismainlyused
fortheparticularbiasedsegmentationprobleminwhichone
wantstosegregatesomeobjectsfromtheirbackground.
Inthispaper,weproposeageneralsolutiontobiased
grouping,basedonalocalapproachtoimagesegmentation
[2,5]
,whichbasicallyconsistsinusingthebiasfortheesti-
mationofnon-parametricmixturemodels.Distribution-free
processingtechniquesareuseful,ifnotnecessary,ingroup-
ing
[10,2]
.However,estimatingclustersindataisalready
farfrombeingtrivialevenwhensignificativedistribution
assumptionsareassumed
[11]
.Thisiswherethebiasisof
hugeinterestwhenitcomestogrouping,asbiasdefines
partiallylabeledregions,withtheconstraintthatdifferent
labelsbelongtodifferentregions.TheapproachofNock
[2]
andNielsenandNock
[5]
isalsoconceptuallyappealing
foranadaptationtobiasedsegmentation,becauseitconsid-
ersthattheobservedimageistheresultofthesamplingof
atheoreticalimage,inwhichregionsarestatisticalregions
characterizedbydistributions.Thereisnodistributionas-
sumptiononthestatisticalpixelsofthistheoreticalimage.
Theonlyassumptionmadeisanhomogeneityproperty,ac-
cordingtowhichtheexpectationofasinglecoloristhe
sameinsideastatisticalregion,anditisdifferentbetween
twoadjacentstatisticalregions.Thesegmentationproblem
isthustheproblemofrecognizingthepartitionofthesta-
tisticalregionsonthebasisoftheobservedimage.Thebi-
asedgroupingproblemturnsouttoallowstatisticalregions
tocontaindifferentstatisticalsub-regions,notnecessarily
connected,eachsatisfyingindependentlythehomogeneity
property,
and
forwhichtheuserfeelstheyallbelongtothe
sameperceptualobject.Thus,ityieldsasignificantgeneral-
izationofthetheoreticalframeworkofNock
[2]
andNielsen
andNock
[5]
.
Ourcontributioninthispaperistwofold.First,itconsists
oftwomodificationsandimprovementstotheunbiasedseg-
mentationalgorithmofNock
[2]
andNielsenandNock
[5]
.
Theiralgorithmcontainstwostages.Informally,itsfirstpart
isaprocedurewhichordersasetofpairsofadjacentpix-
els,accordingtotheincreasingvaluesofsomereal-valued
function
f
.Itssecondpartconsistsofasinglepassonthis
order,inwhichitteststhemergingoftheregionstowhich
thepixelsbelong,usingaso-calledmergingpredicate
P
.
f
and
P
arethecornerstonesoftheapproachofNock
[2]
and
NielsenandNock
[5]
.Weproposeinthispaperabetter
f
,
andanimproved
P
relyingonaslightlymoresophisticated
statisticalanalysis.Oursecondcontributionistheextension
ofthisalgorithmtogroupingwithbias.Ourextensionkeeps
bothfastprocessingandthetheoreticalboundsonthequal-
ityofthesegmentation.Experimentally,theresultsappear
tobeveryfavorablewhencomparingthemtothoseofthe
approachofYuandShi
[1,7]
.Theyalsoappeartoleadto

3

dramaticimprovementsoverunbiasedgrouping,whencom-
paringourmostlyautomatedbiasedgroupingprocesstothe
humansegmentationsobtainedonimagesoftheBerkeley
segmentationdatasetandbenchmarkimages
[12]
.
Section2summarizestheunbiasedapproachofNock
[2]
andNielsenandNock
[5]
,andpresentsourmodificationto
theiralgorithmintheunbiasedsetting.Section3presents
ourextensiontobiasedgroupingandsometheoreticalre-
sults.Section4presentsexperimentalresults,andSection5
concludesthepaper.

2.Groupingexploitingconcentrationphenomena
WerecallherethebasicfactsofthemodelofNock
[2]
andNielsenandNock
[5]
.Throughoutthispaper,“log”is
thebase-2logarithm.Thenotation
|·|
denotesthenumber
ofpixels(cardinality)whenappliedtoaregion
R
,ortothe
observedimage
I
.Eachpixelof
I
containsthreecolorlevels
(
R
,
G
,
B
),eachofthethreebelongingtotheset
{
1
,
2
,...,g
}
.
The
RGB
settingisusedtocastourresultsdirectlyonthe
samesettingasNock
[2]
andNielsenandNock
[5]
;however,
theversatiletechniqueofNock
[2]
andNielsenandNock
[5]
canbetailoredtoothernumericalfeaturedescription
spaces,andhandlesmorecomplexformulationsofthecolor
gamuts,suchasCIE,
L

u

v

,
HSI
,etc.aswellaschannel
samplingrates.
2.1.ThemodelandalgorithmofNock
[2]
andNielsenand
Nock
[5]
Theimage
I
isanobservationofaperfectobject(or“true
region”,orstatisticalregion)scene
I

wedonotknowof,
andwhichwetrytoapproximatethroughtheobservationof
I
.Itis
I

whichcapturestheglobalpropertiesofthescene:
theoretical(orstatistical)pixelsareeachrepresentedbyaset
of
Qdistributions
foreachcolorlevel,fromwhicheachof
theobservedcolorlevelissampled.Thestatisticalregions
of
I

satisfya4-connexityconstraint,andthesimpleho-
mogeneityconstraintthatthe
R
(resp.,
G
,
B
)expectationis
thesameinsideastatisticalregion.Inordertodiscriminate
regions,weassumethatbetweenanytwoadjacentregions
of
I

,atleastoneofthethreeexpectationsisdifferent.It
isimportantthat,apartfromanadditionalindependency,no
moreassumptionsareputon
I

:forinstance,thedistribu-
tionscan
all
bedifferentforallstatisticalpixels,thereby
contrastingwithusualstatisticalmodelsusedinimageseg-
mentation,involvinghypothesesthatcanbequiterestric-
tive
[10]
.
Q
isaparameterwhichquantifiesthecomplexity
ofthescene,thegeneralityofthemodel,andthestatisti-
calhardnessofthetaskaswell.If
Q
issmall,themodel
gainsingenerality(
Q
=
1bringsthemostgeneralmodel),
butsegmentingtheimageismoredifficultfromastatistical
standpoint.Experimentally,
Q
turnsouttobeatunablepa-
rameterwhichcontrolsthecoarsenessofthesegmentation,
evenifonevaluein
[2,5]
(
Q
=
32)appearstobesufficient
toobtainnicesegmentationsforalargebodyofimages.

7559163656

7696713757779718

385878981939597999101301501701

1357911315171911232527292133353739314

4

RAITPR2195

LCENIRPESR.Nock,F.Nielsen/PatternRecognition()–

Fromthismodel,Nock
[2]
andNielsenandNock
[5]
obtainamergingpredicate
P
(R,R

)
basedonconcentration
inequalities,todecidewhethertwoobservedregions
R
and
R

belongtothesamestatisticalregionof
I

,andthushave
tobemerged.Let
R
a
denotetheobservedaverageforcolor
a
inregion
R
of
I
,andlet
R
l
bethesetofregionswith
l
pixels.Let
1

|
R
|

b(R)
=
g
ln
|
R
|
.
(1)
2
Q
|
R
|

Ref.
[2]
pick
|
R
l
|=
(l
+
1
)
g
.Themergingpredicateis
[2]

true
iff

a
∈{
R
,
G
,
B
}
,
|
R

a

R
a
|
P
(R,R

)
=

b(R)
+
b(R

),
(2)
false
otherwise
.
Thedescriptionofthealgorithm
p
robabilistic-
s
orted
i
mage
s
egmentation(
PSIS
)ofNock
[2]
isstraightforward,as
exposedinAlgorithm1.Itbasicallyconsistsinmakinga
preliminarysortingovertheset
S
I
ofthepairsofadjacent
pixelsoftheimage,accordingtotheincreasingvaluesofa
real-valuedfunction
f(p,p

)
.
f(.,.)
takesapairofpixels
p
and
p

asinput,andreturnsthemaximumofthethree
colordifferences(
R
,
G
and
B
)inabsolutevaluebetween
p
and
p

:
f(p,p

)
=
max
|
p

a

p
a
|
.
(3)
a
∈{
R
,
G
,
B
}
In4-connexity,thenumberofsuchpairsis
|
S
I
|=
2
r
I
c
I

r
I

c
I
=
O
(
|
I
|
)
if
I
has
r
I
rowsand
c
I
columns.After
ordering,thealgorithmtraversesthisorderonlyonce,and
testforanypair
(p
i
,p
i
)
themergingofthetworegionsto
whichtheycurrentlybelong,
R(p
i
)
and
R(p
i

)
(here,the
subscript
i
denotestherankofthecoupleintheorder).Such
analgorithmiscalledregion-merging,sinceitgradually
mergesregions,pixelsbeingtakenaselementaryregions.
Algorithm1:
PSIS
(I)
Input
:animage
I
S
I

=
Order
_
increasing
(
S
I
,
f
);
for

i
=
1
to
|
S
I

|
do
if
R(p
i
)
=
R(p
i
)
and
P
(R(p
i
),R(p
i
))
=
true
then

Union
(R(p
i
),R(p
i

))
;
Thisapproachtosegmentationisinterestingfromthealgo-
rithmicstandpoint,becauseitisbothsimpleandfast.The
eigenvalueapproachofShiandMalik
[3]
admitsanaiveso-
lutionwhosetimecomplexityis
O
(
|
I
|
3
)
—impracticaleven
formoderate-sizedimages—.Mathematicaltrickscanscale
downthetimecomplexityattheexpenseofgreaterim-
pleme

ntationefforts,butitstillliessomewhereinbetween
O
(
|
I
||
I
|
)
and
O
(
|
I
|
3
)
.InthecaseofAlgorithm1,the
for...to
complexityis
O
(
|
I
|
)
(linear).Fortunately,theorder
isalsocheapas
radixsort
ingwith
f(.,.)
valuesasthe
keysbringsatimecomplexity
O
(
|
I
|
log
g)
.Since
g
canbe
consideredconstant,wegetanoverallapproximatelinear-

timecomplexityforthewholealgorithmusinganUnion-
Findimplementation
[13]
.
Wenowconcentrateonourmodificationsto
f
andthe
mergingpredicate
P
.
2.2.Animprovedf
NielsenandNock
[5]
haveshownthat
f
shouldtheoret-
icallybeanestimator,asreliableaspossible,ofthelo-
calbetween-pixelgradients.Eq.(3)isthesimplestwayto
computetheseestimators,butthereisanotherchoicewith
whichwehaveobtainedyetbettervisualresults.Itconsists
inextendingconvolutionkernelsclassicallyusedinedge
detectionforpixel-wisegradientestimation.In4-connexity,
neighborpixelsareeitherhorizontalorvertical.Thus,we
onlyneed

ˆ
x
or

ˆ
y
betweenneighborpixels
p
and
p

,for
eachcolorchannel
a
∈{
R
,
G
,
B
}
.Anaturalchoiceisto
extendtheSobelconvolutionfiltertothefollowingkernels:


1001


ˆ
x
:−
2002
,


1001
121
ˆ
y
:

000

.
000−
1

2

1
Forexample,wheneverneighborpixels
p
and
p

arehori-
zontal,

ˆ
x
isusedandthetwopixelsintheconvolutionfil-
terarelocatedinthesecondrow,andthesecondandthird
columns.Onlyforthepixelsforwhichtheestimationswith

ˆ
x
and

ˆ
y
cannotbedone(i.e.thoseoftheimageborder)
dowekeeptheestimationofEq.(3).
2.3.Animprovedmergingpredicate
P
,andassociated
theoreticalresults
Ourfirstresultisbasedonthefollowingtheorem:

Theorem1
(
Theindependentboundeddifferenceinequality,
McDiarmid
[14]
).
Let
X
=
(X
1
,X
2
,...,X
n
)
beafamily
ofindependentr.v.with
X
k
takingvaluesinaset
A
k
for
eachk
.
Supposethatthereal-valuedfunctionhdefinedon
k
A
k
satisfies
|
h(
x
)

h(
x

)
|

c
k
whenevervectors
x
and
x

differonlyinthek-thcoordinate
.
Let

betheexpected
valueofther.v.
h(
X
)
.
Thenforany


0,
Pr
(h(
X
)




)

exp


2

2
(c
k
)
2

.
(4)
kFromthistheorem,weobtainthefollowingresulton
thedeviationofobserveddifferencesbetweenregionsof
I
.
Recallthat
R
a
denotestheobservedaverageofcolor
a
for
region
R
.
Theorem2.
Considerafixedcouple
(R,R

)
ofregionsof
I
.

0
<


1,

a
∈{
R
,
G
,
B
}
theprobabilityisnomore

3454

749415355575

9516365676

96177357779718

{SERPNIELCITRA1

35791131517191123252729213335373931434547494

5

Proof.
Supposeweshiftthevalueoftheoutcomeofone
r.v.amongthe
Q(
|
R
|+|
R

|
)
possibler.v.ofthecouple
(R,R

)
.
|
R
a

R
a
|
issubjecttoavariationofatmost
c
R
=
g/(Q
|
R
|
)
whenthismodificationaffectsregion
R
(among
Q
|
R
|
possibler.v.),andatmost
c
R

=
g/(Q
|
R

|
)
forachange
inside
R

(among
Q
|
R

|
possibler.v.).Weget
k
(c
k
)
2
=
Q(
|
R
|
(c
R
)
2
+|
R

|
(c
R

)
2
)
=
(g
2
/Q)((
1
/
|
R
|
)
+
(
1
/
|
R

|
))
.
Usingthefactthatthedeviationwiththeabsolutevalueisat
mosttwicethatwithout,andusingTheorem1(solvingfor

)bringsourresult.ThisendstheproofofTheorem2.

Fixsome
a
∈{
R
,
G
,
B
}
.Providedwehavesomewayto
evaluatethetheoreticaldeviationof
|
R
a

R
a
|
,acandidate
mergingpredicateisstraightforward.Nock
[2]
andNielsen
andNock
[5]
useaconcentrationinequalityonthedeviation
oftheaveragecolorlevelarounditsexpectationforany
singlearbitraryregion
R
.Thus,theygetforeachregion
R
probabilisticboundsonthedeviationof
|
R
a

E
(R
a
)
|
.When
twoadjacentregions
R
and
R

comefromthesametrue
regionin
I

,wehave
E
(R
a
)
=
E
(R
a
)
;thusthetriangular
inequalitymakesthatthedeviationof
|
R
a

R
a
|
isnomore
thanthesumofdeviationsforeachregion’scoloraroundits
expectation,andwegetthemergingpredicateofNock
[2]
andNielsenandNock
[5]
inEq.(2).However,theuseof
thetriangularinequalityweakenstheconcentrationbound.
Noticethatwhen
R
and
R

comefromthesametrueregion
in
I

,Theorem2directlyyieldsaprobabilisticboundon
thedeviationof
|
R
a

R
a
|
(since
E
(R
a

R
a
)
=
0),without
asimilarweakening.
However,Theorem2isasingleevent’sconcentrationin
whatitconsidersasinglecoupleofregions
(R,R

)
,andone
shouldextendthistothewholeimage,inordertoobtain
aconvenientmergingpredicate.Fortunately,onecaneasily
upperboundtheprobabilitythatsuchalargedeviationoccurs
intheobservedimage
I
,usingtheunionbound.Nock
[2]
remarkthatthisisnomorethantheprobabilitytooccur
inthesetofallregions(whetherpresent
or
absentfrom
I
).Thecardinalofeachsubsetcontainingfixed-sizeregions
canbeupperboundedbyadegree-
O
(g)
polynomial
[2]
,but
ityieldstoaprettylargeupperbound.
Anothercountingargumentispossible,ifweremarkthat
theoccurrenceprobabilityon
I
isalsonomorethanthat
measuredonthesetofcouplesof
I
whosemergingistested,
S
I

(SeeAlgorithm1).Itscardinal,
|
S
I

|
,iscomparatively
small:forasingle-passalgorithm,
|
S
I

|
<
|
I
|
2
,andeven
|
S
I

|=

(
|
I
|
)
in4-connexity.Thus,wegetthefollowingthe-
.meroTheorem3.

0
<


1,
thereisprobabilityatleast
1

(
3
|
S
I

|

)
thatallcouples
(R,R

)
testedshallverify

a

than

that
2111|
(R
a

R

a
)

E
(R
a

R
a
)
|

g
2
Q
|
R
|+|
R

|
ln

.

R.Nock,F.Nielsen/PatternRecognition()–

R
,
G
,
B
}
,
|
(R
a

R

a
)

E
(R
a

R
a
)
|

b(R,R)
,
with
b(R,R

)
=
g
21
Q
|
R
1
|+|
R
1

|
ln

2
.
(5)

b(R,R

)
wouldleadtoaverygoodtheoreticalmerging
predicate
P
insteadofusingthethreshold
b(R)
+
b(R

)
in
Eq.(2),providedwepicka

smallenough.Thispredicate
wouldbemuchbetterthan
[2,5]
fromthetheoreticalstand-
point,butslightlylargerthresholdsarepossiblethatkeep
allthedesirabletheoreticalpropertieswelookfor,andgive
muchbettervisualresults.Ourmergingpredicateusesone
suchthreshold,whichturnsouttobe
O
˜
(b(R,R

))
(thetilde
uponthebig-Ohnotationauthorizestoremoveconstantsand
log-terms).Remarkthatprovidedregions
R
and
R

arenot
empty,
b(R,R

)

b
2
(R)
+
b
2
(R

)<b(R)
+
b(R

)
.This
rightquantityisthatofEq.(2).Thecenterquantityisthe
oneweuseforourmergingpredicate.Noticethatitisin-
deed
O
˜
(b(R,R

))
providedagoodupperboundon
|
R
l
|
is
used.Ourmergingpredicateisthus:

true
iff

a

∈{
R
,
G
,
B
}
,
|
R

a

R
a
|
P
(R,R

)
=

b
2
(R)
+
b
2
(R

),
(6)
false
otherwise
.
Letusnowconcentrateon
|
R
l
|
.Nock
[2]
andNielsenand
Nock
[5]
pick
|
R
l
|=
(l
+
1
)
g
,consideringthataregion
isanunorderedbagofpixels(eachcolorlevelisgiven
0
,
1
,...,l
pixels).Thisboundcountsnumerousduplicates
foreachregion:e.g.atleast
(l
+
1
)
g

l
when
l<g
.Thus,
wefix
|
R
l
|=
(l
+
1
)
min
{
l,g
}
.
Asadvocatedbefore,themergingpredicateinEq.(6)has
provenexperimentallytobemoreinterestingthanthatof
Eq.(2).Letusbrieflyillustrateitstheoreticalinterests,that
encompassthoseofthemergingpredicateofNock
[2]
and
NielsenandNock
[5]
(duetothefactthatitistighter).
Supposethatweareabletomakethemergingtests
through
f
insuchawaythatwhenanytestbetweentwo
(partsof)trueregionsoccurs,thatmeansthatalltestsin-
sideeachofthetwotrueregionshavepreviouslyoccurred.
Letusname
A
thisassumption.Informally,
A
stressesthe
needtomake
f
asaccurateaspossible(andithasmoti-
vatedourstudyofSection2.2).Noticealsothat
A
doesnot
postulate
atall
thatweknowwherethestatisticalregions
of
I

arein
I
.Underassumption
A
,NielsenandNock
[5]
haveshownthatwithhighprobability,theerrorofthe
segmentationislimitedfromboththequalitative
and
the
quantitativestandpoint.Therearebasicallythreekindof
errorsasegmentationalgorithmcansufferwithrespectto
theoptimalsegmentation.First,under-mergingrepresents
thecasewhereoneormoreregionsobtainedarestrictsub-
partsofstatisticalregions.Second,over-mergingrepresents
thecasewheresomeregionsobtainedstrictlycontainmore
thanonestatisticalregion.Third,thereisthe“hybrid”(and
mostprobable)casewheresomeregionsobtainedcontain
morethanonestrictsubpartoftrueregions.Nameforshort
s

(I)
asthesetofregionsoftheidealsegmentationof

15

355575951636567696173757779718385878981939597999

PR2195

SERPNIELCITRA81

6

135791131517191123252

729213335373931434547494

Itshallbeusefulinthissectiontothinkof
I
ascontaining
verticesinsteadofpixels,andthe(4-)connexityasdefining
edges,sothat
I
canberepresentedbyasimplegraph
(V,E)
.
FollowingYuandShi
[1]
,wedefinea
groupingbias
tobe
user-defineddisjointsubsetsof
V
:
{
V
1
,V
2
,...,V
m
}=
V
.
Anyfeasiblesolutiontotheconstrainedgroupingproblem
isapartitionof
V
intoconnexcomponents(thus,apartition
ofthepixelsof
I
intoregions),suchthat
(i)anysuchconnexcomponentintersectsatmostoneele-
mentof
V
,and
(ii)

1

i

m
,anyelementof
V
i
isincludedintooneconnex
component.
Thefirstconditionstatesthatnoregioninthesegmentation
of
I
maycontainelementsfromtwodistinctsubsetsin
V
,
andcondition(ii)statesthateachvertexin
V
belongstoa
region.
Foranyregion
R
of
I
,wedefinea
model
fortheregion
tobeasubsetof
R
,withoutconnexityconstraintsonits
elements,containing
one
vertexofsomeelementof
V
.The
termmodelmakesstatisticalsensebecauseany
V
i

V
with
|
V
i
|
>
1mayrepresentasingleobjectfortheuser,but
composedofdifferentstatisticalregions(“models”)of
I

.
Eachelementof
V
i
canthusrepresentonetheoreticalpixel
ofeachdifferentstatisticalsub-regions,whoseunionmakes

3.Groupingwithbias

I
followingthestatisticalregionsof
I

,and
s(I)
theset
ofregionsinthesegmentationweget.Thenwehavethe
followingqualitativeboundontheerror.
Theorem4.
Withprobability

1


(
|
I
|

)
,
thesegmenta-
tiononIsatisfying
A
isanover-mergingof
I

,
thatis
:

O

s

(I),

R

s(I)
:
O

R
.
Proof.
FromTheorem3,withprobability
>
1

(
3
|
S
I

|

)
(thus
>
1


(
|
I
|

)
in4-connexity),allregions
R
and
R

comingfromthesamestatisticalregionof
I

,
whosemergingis

tested,satisfy

a
∈{
R
,
G
,
B
}
,
|
R
a

R
a
|

b(R,R

)

b
2
(R)
+
b
2
(R

)
(thus,
P
(R,R

)
=
true
).Since
A
holds,thesegmentationobtainedisan
over-mergingof
I

.

Becauseofthechoiceofour
P
,itsatisfiesalsothequan-
titativeboundsofNielsenandNock
[5]
,i.e.wecanshow
thatwithhighprobability,theover-segmentationofTheo-
rem4shallnothopefullyresultinatoolargeerror.Werefer
thereadertoNielsenandNock
[5]
fortheexplicitvaluesof
thiserrorbound,notneededhere.Inthesequel,weshallre-
fertoourmodifiedversionof
PSIS
as
SRRB
,whichstands
for
S
tatistical
R
egion
R
efinement(with
B
ias).Wehavecho-
sentouserefinementbetterthanmerging,becauseitshall
beclearfromtheexperimentsthatthebiasmayhelptoim-
proveboththemergingandthesplittingofregions,even
when
SRRB
formallybelongstoregionmergingalgorithms.

R.Nock,F.Nielsen/PatternRecognition()–

theobjectperceivedbytheuser.Forexample,thehatof
lena
in
Fig.1
visuallycontainstwopartsbelongingtothe
sameconceptualobject(abandeauandthehatitself).There
isasignificantgradientbetweenthesetwopartsofthehat.
So,onemayimaginetocreatesome
V
i

V
bypointing
twopixels,oneonthetopofthehat,andonesomewhere
onthebandeau(oronthebrighthat’sborderwhosecoloris
similartothebandeau).Thisindicatesthatthesetwoparts
withdifferentcolorsdefinetwomodelsthatbelongtothe
sameobject,andshouldthusbeconsideredasasingleregion
inthesegmentation’sresult(Noticethatthisisindeedthe
casefromourbiasedsegmentation’sresultin
Fig.1
.)
Groupingwithbiashasanotheradvantage,sinceitnatu-
rallyhandlesocclusions,astheusermayspecifythattwo
(ormore)modelsnotconnectedrepresentthesameregion.
Thiscouldbethecasein
Fig.1
for
lena
’shairforexample.
Anyregion
R
definedbysome
V
i

V
isapartition
ofmodels,eachrepresentedbyoneelementof
V
i
.We
nameregionswithoutverticesfrom
V
as“model-free”.
Therearethereforetwotypesofregionsinoursegmenta-
tion:thosemodel-free,andthosebeingapartitionofsub-
regions,eachdefinedbytheelementsofonesubsetin
V
.
Ourregionmergingalgorithmkeepsthisasaninvariant:
thus,mergingamodel-freeregionandamodel-basedre-
gionresultsinthemergingofthefirstregionintoone
modelofthesecond.Themodificationoftheapproach
inRefs.
[2,5]
consistsinfirstmakingeach
V
i
definedby
theuser,andthen,throughthetraversingof
S
I

,replacing
themergingstage(the
if
conditioninthe
for...to
ofAlgo-
rithm1)bythefollowingnew
if
condition(

(p,p

)

S

):
Iif
If
R(p)
and
R(p

)
aremodel-free,thenwecompute
P
(R(p),R(p

))
asinAlgorithm1,andeventually
mergethem;
elseif
bothcontainmodels,thenwedonotmergethem;
Indeed,inthatcase,eitherthemodelsaredefinedby
verticesofdifferentsubsetsin
V
(andweobviously
donothavetomergethem),ortheyaredefinedby
verticesofthesamesubsetof
V
.However,inthat
case,theyhavebeendefinedbytheusedasdifferent
sub-regionsofthesameobject,sowekeepthesesub-
regionsdistinctuntiltheendofthealgorithm.
else
considerwithoutlossofgeneralitythat
R(p)
con-
tainsmodelsand
R(p

)
doesnot.Wefirstcompute
P
(M(p),R(p

))
,with
M
themodelof
R(p)
adjacent
to
R(p

)
(noticethat
p

M(p)
):
if
itreturns
true
,thenamergeisdone:wefold
R(p

)
into
M(p)
;thus,
M(p)
grows(andnot
theothermodelsof
R(p)
),asafterthismerging
itintegrates
R(p

)
.
else
wesearchforthebestmatchingmodel
M(p)
of
R(p)
w.r.t.
R(p

)
(theoneminimizing
max
a

R
,
G
,
B
|
M(p)
a

R(p

)
a
|
),andeventu-
allyfold
R(p

)
into
M(p)
iff
P
(M(p),R(p

))
returns
true
.

153555759516365676961737577797

PR2195

PR2195
ARTICLEINPRE
S
R.Nock,F.Nielsen/PatternRecognition()–
7
1Attheendofthealgorithm,allmodelsofeach
V
i
aremergedTheresultof
SRRB
withbiasdisplaysaverygoodseg-
altogetherinthesegmentation’soutput.mentationoftheimage.Thegirl’shatandhershoulder,two47
3Thetheoreticalpropertiesenjoyedbythisextensiontoverydifficultregionstosegment,arealmostperfectlyseg-
groupingwithbiasarethesameastheunbiasedapproachmented.Thequalityofthesegmentationistobeevaluated49
5giveninSection2,providedwemaketheassumptionthatinthelightofthebiasgiven.Theuserhasspecifiedonly
alltheverticesofthesubsetsin
V
comefromdifferenteightpixelsforthewholeimage.Obviously,thesepixels51
7statisticalregionsof
I

.Recallthatthisissoundwiththefacthavenotbeenchosenatrandom.
thattheaimofbiasispreciselytomakeitpossiblefortheTwosimple“rulesofthumb”appeartobeenoughfora53
9observertointegrateinthesameperceptualobjectdifferentlimitedprocessingofmostoftheimages,whileobtaining
statistical(true)regionsof
I

.Forexample,wehave:thesignificantimprovementsoverunbiasedsegmentation55
observedin
lena
,andoverimagesaswellsuchasthose
11
T

heorem5.
Supposethattheverticesof
V
comefrom
of
Fig.3
.
57
m
|
V
i
|
differentstatisticalregionsof
I

.
Then
,
withprob-
Thefirstandmostimportantisa
gradientrule
:thesub-
1=i13
ability

1


(
|
I
|

)
,
thesegmentationonIsatisfying
A
is
regionsofsmoothestgradientsbetweentwoperceptually59
anover-mergingof
I

.distinctregionsaregoodplacesforspecifyingmodels.This
preventstheordertomergedistinctperceptualsub-regions61
15Quantitativeboundsonthearealsopossible,followingintheearlystepsof
SRRB
,duringwhichthestatisticalac-
NielsenandNock
[5]
.
curacyofthemergingpredicateisthesmallest.Inimage63
lena
,thetworedtrianglesdefiningherfaceareapproxi-
matelylocatedinsmoothgradientpartsbetweenthefaceand65
4.Experiments
thehat,andbetweenthefaceandtheshoulderrespectively.
Thesecondisa
sizerule
:duringthemergingsteps,no67
Wehaverun
SRRB
onabenchmarkofdigitalpicturesoftwomodelsmixaltogetherintoasinglemodel,evenwhen
19variouscontentsanddifficultylevels,totestitsabilitytoim-theybelongtothesameregion.Furthermore,themergingof69
provethesegmentationqualityovertheunbiasedapproach,amodel-freeregionintoamodelofanotherregiondoesnot
21whileusingabiasasslightaspossible.Whilelookingatthenecessarilyimplythattheyareconnected,asconnexityis71
experimentsperformedon
Figs.2–7
,thereadermaykeep
ensuredonlywiththeregioncontainingthemodel.Thus,if
23inmindthatimagesaresegmentedastheyare,i.e.withouttheuserspecifiesverysmallmodelsinperceptuallydistinct73
anypreprocessing,andwiththesamevaluefortheparam-regions,thismayyieldasignificantover-mergingforthe
25eters,followingNock
[2]
andNielsenandNock
[5]
:
regionstowhichsuchmodelbelongs.Forexample,ifwehad75
putaredtrianglein
lena
’srighteye,herhairwouldhave
Q
=
32
,
(7)beenmergedwithherface.Suchamistakedoesnotreally77
representarealadditionalinteractionburden,asputtinga

=
1
.
(8)singledifferentadditionalmodelinthehairwouldsolvethe79
273
|
I
|
2
problem.However,thissimpleruleofleavingmodel-free
toosmallregionsmaysaveasignificantnumberofmodels,81
Thus,thequalityoftheresultsmaybeattributedonlytoandthusreducetheinteractiontimefortheuser.
29
SRRB
,andnottoanycontent-specifictuningorpreprocess-Forrelatively“easier”pictures,suchasthoseof
Fig.3
,
83
ingoptimization.sparseandsimplechoicesyielddramaticimprovements
overunbiasedgrouping:thestairsandthetowerof85
31
4.1.
SRRB
’smodelchoicerules,andfirstexperiments
castle-1
arealmostperfectlysegmented,andthecastle
of
castle-2
isalmostperfectlyextractedasawhole87
Fig.2
showsdetailedresultsontheimage
lena
,thathave
(noticethemodelinthedrainpipe,whichpreventsittobe
33beenpreviouslyoutlinedintheintroduction.Wehavechosenmergedwiththebushytree).89
thisimagebecauseitisoneofthemostlyusedbenchmarkInthenextsubsection,wemakefurthercomparisonsof
35inimageprocessing,andithasfeaturesmakingitdifficult
SRRB
withbiasednormalizedcuts(
NCuts
).91
tosegment,suchasitsblurredregions,itsthindifferences
37betweenperceptuallydistinctregions(e.g.herfaceandher
4.2.
SRRB
vs.
NCuts
shoulder),itssinglemajoritytone(reddish),itsstronggra-
39dients(e.g.herhat).Theresultof
SRRB
withbiasdisplaysYuandShi
[1,7]
haveproposedamathematicallyappeal-
93
fourmodel-basedregions.Eachsuchregionisdefinedonlyingextensionoftheoriginalunbiasednormalizedcutsprob-
41bytwomodels.Intheresultof
SRRB
withbias,thesym-lemofShiandMalik
[3]
.Intheoriginalproblem,theimage
95
bolsdenotethepixelsthathavebeenpointedbytheusertoistransformedintoaweightedgraph,andtheobjectiveisto
43defineeachelementof
V
.Differentsymbolsdenotediffer-makeapartitionofthisgraphintoafixednumberofconnex97
entelementsof
V
,andthusdifferentperceptualregionsforcomponents,soastominimizethecutbetweenthecom-
45theuser.ponentsandmaximizeanassociation(within-component)99

1357911

8

RAITPR2195

LCENIRPR.Nock,F.Nielsen/PatternRecognition

=Fig.3.Segmentationresultsonimages
castle-1
(
m
3
,
|
V
1
|
V
1
|=
3
,
|
V
2
|=
1
,
|
V
3
|=
1
,
|
V
4
|=
1
,
|
V
5
|=
2).Conventionsfollow
Fig.2
.

measure.Thesolutionofthisproblem,evenwhencompu-
tationallyintractable
[3]
,canbefairlywellapproximated
bytheeigendecompositionofastochasticmatrix.Theex-
tensionofthistechniquetobiasedgroupinginvolvescon-
strainedeigenvalueproblems.Theseproblemsmakeitdif-
ficulttohandlenon-transitiveconstraints,suchasthecon-
straint“mustnotbelongtothesameregion”,whichbelongs
tothecoreofthebiasedgroupingproblem(seeSection3).
IntheRefs.
[1,7]
,thebiastakestheformoftransitivecon-
straints,suchas“mustbelongtothesameregion”.Inthat
case,nothingisassumedforthepixelswithdifferentla-

|=E(

S52|V,

|)

=–

43|V,

|=3)and
castle-2
(
m

=5,

bels.Inordertomakeafaircomparisonwith
NCuts
,we
havedecidedtostudyaparticularbiasedgroupingprob-
lemwhoseconstraintsfitinthiscategory,andforwhichthe
NCuts
givesomeoftheirbestresults
[7]
:thesegregation
oftheforegroundfromthebackgroundofanimage.This
problemisaddressedon
NCuts
bymakingaframe(10pix-
elswidthinmostofourexperiments)onanimage,andthen
constrainthegroupingtotreatthisframeasasingleregion.
Fig.4
presentssomeresultsthathavebeenobtainedfor
threeanimalpictures,inwhichwewanttosegregatethe
animalfromitsbackground.
Fig.5
presentsadditionalre-

3151719112

135791131

RAITPCRL2E1I9N5RPER.Nock,F.Nielsen/PatternRecognition

S–)(

9

Fig.4.
SRRB
vs.
NCuts
onimages
leopard
(
m
=
2
,
|
V
1
|=
4
,
|
V
2
|=
5),
bat
(
m
=
2
,
|
V
1
|=
2
,
|
V
2
|=
7)and
badger
(
m
=
2
,
|
V
1
|=
10
,
|
V
2
|=
4).
Foreachimage,theresultof
SRRB
withbiasandthelargestregionsfoundby
SRRB
and
NCuts
areshown.Theremainingregionsfollow
theconventionof
Fig.2
.

sultsonananimal,andonaflower.Theresultsdisplaytheflower,while
NCuts
essentiallysucceedonlyinmaking
thatthe
NCuts
performreasonablywell,butfailtomakeanaccuratesegregationoftheinsectfromthebackground.
accuratesegmentationsofregionswithdeeplocalizedcon-This
flower
imageisanexampleofadifficultimagefor
trasts,suchastheheadofthe
badger
,thespeckledcoatgroupingalgorithmsbasedonlyonlow-levelcues:dueto
ofthe
leopard
,orthe
flower
.Becausethesecontraststhedistributionofcolors,itisvirtuallyimpossibletomakea
makeverysmalllocalcutvaluesfor
NCuts
,theytendtosingleregionoutoftheflower,whosecolorsarecontrasted,
beselectedasregionfrontiers,andtransitiveconstraintsdo
while
preventingthebeetobemergedwiththebackground.
notseemtobeenoughforpreventingtheirsplit.ThisisEightmodelspointedareenoughtosolvethisproblemin
clearlyadrawbackthat
SRRB
doesnotsuffer,asitmanages
SRRB
.
veryaccuratesegmentationsofallanimals.EventhebeeSinceourmergingpredicatereliesoncomparingobserved
ofthe
flower
imagereceivesanaccuratesegmentation,averages,makingsegmentationswithoutbiasin
SRRB
faces
whichsegregatestheinsectfromboththebackgroundandtheproblemofundermergingforregionswithstrong

517191123252

01

RAITPCRL2E1I9N5RPESR.Nock,F.Nielsen/PatternRecognition()–

Fig.5.Moreresultsonimages
chamois
(
m
=
3
,
|
V
1
|=
5
,
|
V
2
|=
3
,
|
V
3
|=
3)and
flower
(
m
=
3
,
|
V
1
|=
3
,
|
V
2
|=
3
,
|
V
3
|=
2).Conventions
follow
Fig.4
.

Fig.6.Comparisonof
SRRB
and
NCuts
ontheBSDBimage
woman
(
m
=
2
,
|
V
1
|=
3
,
|
V
2
|=
3).The“human”resultisasegmentation
fromahuman,takenfromtheBSDB(regionsaredisplayedwhitewithblackborders).Otherconventionsfollow
Fig.4
.

  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents