計測白削制御学会東北支部第233回研究集会（2006．12．18）
資料番号233−4

AnImprovedTechniquefbrLVQ−BasedVideoObjectExtraction
スリヤ スンペノナノ、リアディ モハマド‡，伊藤康一†，青木孝文†

SuryaSumpeno†，HariadiMochamad‡，KoichiIto†，TakahlmiAoki††東北大学大学院情報科学研究科‡スラバヤ工科大学，インドネシア†GraduateSchoolofInformationSciences，TbhokuUniversity，Japan‡DepartmentofElectricalEngineering，SepuluhNovemberInstituteofTechnology（ITS）7Surabaya60111，Indonesia
キーワード：Objectex七raction，1earningvectorquantization：videoprocessing
連絡先：東北大学大学陳情報科学研究札 〒980−8579仙台市青葉区荒巻字青葉6−6−05
e−mail：Surya＠aoki．ecei．tohoku．ac．jp

1．Introduction

概要

Thispaperpresentsasemi−autOmaticalgorithm

Today，multimediausers arenolonger sati5fied

forvideoobjectextraction．inwhichasemanticob− tobejustpassiveobserversofvisualpresentation．
JeCtOfinterestisde丘nedinadvanCeinakeyh・ame

They want mOre eXPeriences byinterac七ingwith

PrOVided by human・For ordinaryvideo frames．

the content ofmultimedia datathey areviewlng．

thespecifiedvideoobjectistrackedandsegmented

Thevideostandardsde丘nedbyMPEG−4andMPEG−

automatical1yusingLearningVectorQuantization

7provide standardized technology for represent〜（LVQ）．This paperalso presents a technique for

1ng and man1pulating videodata，tO address thisimprovlngeXtraCtionperformanceoftheproposedneedl）．MPEG−40ffersobject−basedrepresenta−

algorithm and reducing computation time．Ex−

tionandcompressionofvideo，thus enablingvar−

perimentalevaluationuslngMPEG standard七est

iouscontent−basedfunctionalitiesfornewtypesof

Videosequencesdemonstratesthattheproposedal−

COntent−basedapplications，WhileMPEG−7provides

gorithmisabletoextractthevideoobjec七withlow

uswithastructuredmeta−datadescriptionforse−

errOr．

mantical1yrichmediacontent．alongwithsupport
for multimedia databaseindexing．ObjectNbased
Video processinglS required tofu11y make use oftheseadvanCedfunctionalities．Furthermore，Object−basedtechnologylSalsoimportantforcomputervi−ー1−Sionapplicationsincludinggestureunderstanding、
image recognition・augmented reality．etc．How−
ever．extracting the shapeinformation ofseman−ticobjectsfromvideosequencesisaverydifBculttask・Since thisinfbrmationis not explicitly pro−videdwithinthe video data．
−−−−−一一一一−−−一一−−−一一−−−−−・■トResultMany video object extraction algorithms have．二．・ロ

beenproposedovertheyearstoovercomethisdi凪−Cultv．Thesealgorithmsaregeneral1yclassifiedinto
twotypesi・e・・autOmaticexlraction（e・g‥2））andsemi−autOm。ticextraclion（e．g．．3，4））．Automatic
Objectextractionisusuallybasedonspecialcharac−

Fig．1Illustrationofthepracticalapplicationof
PrOPOSedalgorithm uslng keyframe provided byteristicsofthesceneoronspecificknowledge（i．e．．a human．
prioriinformation）suchascolors・teXtureSandmo−
tions．However．itisverydi氏culttoautomatical1y
extractasemanticallymeaningfulobject．sincethe

Objectmayhavemultiplecolors．texturesandmo−

ti。nS5）．Asasatrad。−。仔betweena。t。maticseg−

rangeOfvideosequences．
Inthispaper，Wealsopresentthattheextraction
Perfbrmanceoftheproposedalgorithmisimprovedby trackingthe semantic object uslngOnly code−
bookvectorsde丘ned aroundtheobject．Byselec，mentation and manualsegmentation，manySemi−

automaticobjectextractionmethodsthatincorpo−

tivelyuslngCOdebookvectors，Weareabletoreduce
COmPutationtime．Experimentalevaluationuslng

rateinteractionofuserhavebeenproposed・

MPEGstandardtestvideosequencesdemonstrates

Ouralgorithm forvideo object extraction be−longs to semi−autOmatic approach and applicableforgenericvideosequences6｝7，8†9）10）・Thetrack

slgniBcantextractionperformanceoftheimproved
algorithmcomparedwi七hourpreviousone・mechanismisbasedonLVQ（LearningVectorQuan−tization）11）．whichprovidesoptimalclassdecision
for distinguishing between the object ofinterest

2．LVQ−BasedVideoObjectEx−

traction System

andthebackground．WeuseLVQcodebookvectors

Thissection describes avideo object ex七raction

tomaintaintheclassofeachreg10nfortrackingthe

algorithmusingLearningVectorQuantization（i〃Q）・semanticobject．Eachpixelofavideoh・ameisrep− OurapproachrequlreSa

key

frameinwhichtheresentedbya5−dimensional（5−D）featurevectorin−

semanticobjectofinterestismanual1yde丘nedby

tegratingspatialandcolorfeatures・Spatialfea七ure

theuser．Inthekeyframe．eachpixelisrepresented

refers to pⅨelpositionin2−D coordinates．whilebya5−Dfeaturevectorwithaspecificclasslabelcolor feature is represented by YUV color space（object orbackground）・LVQisusedto approx−

components，Wechoosethiscombinationofcolor

imate七heobject boundary，WheretheLVQ code−

andspatialfeaturesbecausetheyaregenericlow−

bookvectorsaretrainedbythe5−Dfeaturevectors

1evelfeaturesthat areeasilyapplicableto awide−2−

Fig．3 Codebookvectorinitialization：（a）code−
bookvectors usedin theprevious algorithm，（b）
codebookvectorsusedintheproposedalgorithm．

ingdataforsupervisedlearningtoupdatetheLVQ
codebook vectors for segmenting the next frame．
hencepropagatingthesemanticinformation．This

processisrepeateduntilthelastframe．
Inordertoreducecomputationtime．ins七eadof
uslngal1the pⅨels ofthevideo frame・WePreVi−

OuSlyemployedarectangularwindowthatencloses

theobjectofi。tereStbyasmallmargin6）．How−
ever，theobjectplXelissometimesmisclassi丘edas

lbackground，Sincetheobjectofinterestcannotbe
Fig・2 Flowchartoftheproposedsystem．

represented as a rectangularwindow・Inthis pa−

Per．WeuSe areglOnfittingthe object ofinterest
Ofthekeyframe．Inthenextframe，theLVQcode−

bookvectorsareusedtoclassifytheplXelsintoob−
jec七class orbackgroundclassinordertoidentify

theobjectofinterestthuspropagatingthesemantic
information．Thecla5Sificdpixelsarethenusedto

asshowninFig・3・WherethereglOnhas asmal1

margln・ThisreglOnisgeneratedfromtheextrac−

tionresult ofthepreviousframewhichisapplied
themorphological丘1ter（dilation）tohaveamar−
gln．Wecanreducethenumberofcodebookvec−

updatetheLVQcodebookvectorsforsegmenting
Subsequentframes．Thisprocessis repeateduntil

tors．reducethecomputationtimeandimprovethe
extractionperformanceofthealgorithm．

theendofthevideosequence．

Describedbeloware七hes七epsofthe且owchartin

ThesystemflowchartisshowninFig・2・The

Fig．2．

LVQcodebookvectorsaretrainedinthekeyframe

A．Manuallydefinetheobject ofinterest

to approximatethe object shape．For the subse−

The semantic objectis manual1y definedwith

quentframes，the objec七is segmented automati−

user assistancein a particular key frame．EachCal1y・Foreachframe．theLVQ codebookvectors

PlXelofthekeyframeismanual1yclassifiedasei−

Obtainedinitspreviousframeareusedtoclassify

therこ−object or background ■．Thismanualseg−

thepIXelsofthecurren七丘ameintoobjectorback−mentationprovidestheinitialtrainlngdataforthe

ground・Theclassifiedpixelsarethenusedastrain−ー3−

LVQcodebookvectorsinStepD．

Color similarities between the background andtheobject maysometimesresultinsegmentation

B．NormaHze fbature vectors

EaChpixelofthekeyframeisrepresentedbya

noiseinthe form ofsmall，SCattered disjoint re−

5−Dfeaturevectorx＝Li5，亘LKi），Kh，Ki）），Where glOnS・Thisis because the projection of a5−D
pixelcoordinates（p，q）andYUVcolorcomponents Ⅵ〕rOnOireglOn OntO2−Dimage planeis not nec−
（y・u．V）areintegrated七ogethertoformasinglefea−

essarilycontinuous．Toreducethisnoise，Weintro−

turevectorafternormalizationprocesstoprevent

duceapost−PrOCeSSlngStepuSlngmedianfiltcrlng

dominationbyanyOnefeature6）．TheparameL

forremovlngthe smal1reglOnS．Thus．weobtain

terKisusedtoadjustthebalancebetweenplXelthe segmented object.

COOrdinatesandYUVcolorcomponents・

Ⅰ．Endoftemporalsegmen七？

Thealgorithmterminatesiftheendofthetem−

C．InitializeLVQ codebookvectors

Initializationofcodebookvectorsisdonebyran−POralsegmen七isreached．Otherwise，thesegmenT

domly chooslng N pixels丘・Om the keyframe astationresultofStepGisusedtoupdatetheLVQ

codebook vectors，Each codebook vectoris as−

COdebookvectorsforclassifyingthenextframe（re−SlgnedthemaJOrityclasslabelofpixelswithinits

peath・OmStePSDtoH）・VoronoireglOn・

D．TrainINQ codebookvectors

3．ExperimentsandDiscussion

TtainlngOfcodebookvectorsisperformedtolearn
Inourexperiments．weevaluateourproposedal−

theshapeOfthesegmentedobject，Thecodebook

gorithmusingthefollowlngMPEGstandardtestv。。t。rSaretrain。d。SingOLVQlalgorithmll，6）
Weuse20．000totaltrainingsteps and七heinitial

Video sequences：Claire．Horse Ridin9and7bble

乃mnis．Theobjec七Ofinteres七ismanual1yde且ned

1earningra七ecki（0）isO・4foral1codebookvectors

inthe丘rsl，frame、andthentheproposedalgorithm
mトisusedtoautomatical1yextracttheobjectofinter−

E．Get the next frame

est，The number ofcodebookvectors depends on

ThenextframeinthetemporalsegmentisIoaded．

thesizeoftheobjecttobeextracted・F．Normalize feature vectors

TheextractionaccuracylSeValuatedbycompar−

Thefeaturevectorsoftheloadedvideoframeare

1ngtheextractionresultofourproposedalgorithm

normalized．

withthatofmanualsegmenta七ion（groundtruth）・

G．Pixel−WiseclassificationbyVQ

Wemanual1yextractedal1framesofeachvideose−

PixelTWise classification ofthevideoframeinto

Object class or background classis done to cre−atethesegmentationresult・TheVQ−basedclas−

quencethatwasusedinourexperiments・Theex−
tractionerrorforeachh・ameisglVenbythefollow−
ingformula＝sificationiscarriedoutuslngthecodebookvectors

MO＋AB

trainedinthepreviousframe．Eachpixelislabeled

errOr ＝OB×100％（1）

objectorbackgrounddependingontheclassofits
where MO（Missing Object）is number ofpixels

nearest codebook vector．

ofrrlisclassifiedobjectasbackground．AB（AddedH．Removalofsegmentationnoiseー4−

︻辞︼男β︻hOヒ叫︻威︼3q∝JOヒ山

50

0

100

700

150

750

800

850900

Frame Nu皿ber

FrameNuJnber

Fig．4 Frame−by−frameerrorratefor Claireseq

Fig．6 FrameTby−frameerrorrateforHorseRid−quenCe・

m9SequenCe・Figures4．5and6showtheframe−by−frameerror

rate for each sequence．The proposed algorithm
exhibitslowererrorratethanthat oftheprevious︻辞︼む︺遥h2h凹

algorithm，Tablelshowsthe meanerror rate of
all七heframesforeachvideosequence．Figures7，8and9showsomeimagesofextractedvideoobject
alongwiththeorlglnalimages．
Table2shows七he averagenumberofcodebook
150

200

250

VeCtOrSforpreviousalgorithmandtheproposedalT300
350 400
FrameNumber

gorithm．Thenumberofcodebookvectorsusedin

the proposedalgorithmis muchless thanthat of

Fig．5 Frame−by−frameerrorratefor7bble了七乃nisthepreviousalgorithm．Table3showsthecompu−

SequenCe・

tationtimeofthepreviousalgorithmandthepro−
Background）is number ofpixels ofmisclassiBed

POSedalgorithm．Inthecasesof ClaireandHorsebackgroundasobject．andOBisgroundtruthob−

Riding．the computationtimeoftheproposedalL

ject，s12）・Theextractionqualityisdirectlydepen−

gorithmis much faster thanthat ofthe previous

dentonthevalueoftheparam。t。rK6）．Inthis

algorithm．

PaPer，WeemPloythebestvalueofK determined

Asisobservedintheaboveexperiments．thepro−

emplrically・Asforthepreviousalgorithm．K＝3．7

POSedalgorithmisusefu1forextractingthevideo

forCJαかe、∬＝3・6for月■0γ5e月豆d豆乃g、and〟＝0．7

Objectcomparedwiththepreviousalgorithm．

払rTbble Tbnnis・reSPeCtively．Asfortheproposed
algorithm．〟＝3．2for CZα盲re，∬＝2．7forガ0γ5e

Ridin9，andK＝1・2for7bble7bmis．respectively．

−5−

T＝125

T＝167

＿且＿＿且

Fig・7 0bjectextractionresultsfor Clairesequence‥（a）originalimages，（b）extractionresultsofthepreviousalgorithmand（c）extractionresultsoftheproposedalgorithm．

T＝145

T＝206

T＝268

T＝329

［竺］「「

Fig・8 0bjectextractionresultsfor Tbble乃乃nissequence：（a）originalimages．（b）extractionresultsofthepreviousalgorithmand（c）extractionresultsoftheproposedalgorithm．

ー6一T＝798

T＝896

T＝847

円
Fig．9 0bjectextractionresultsforHorseRidin9SequenCe：（a）originalimages・（b）extractionresultsof
thepreviousalgorithmand（c）extractionresultsoftheproposedalgorithm・

Table3 Computationtime・

Tablel Performance evaluation for video se−
quenCeS・Sequence PreviousAlgorithm ProposedAlgorithm
tsecノframe］
5．49
C友正作
1．94
mb〜e Te71m由ガ0γ5e動dれg
4．10

Sequence PreviousAlgorithm ProposedAlgorithm
MeanError〔％］
Me乱nError【％］CJ血豆re0．60
0．61払わge T eγ1れ由
32．60
7．81
ガ0γ5e月iding
3．12
2．53

［secノ什ame】

2．76
1．88
1．54

Selectingthecodebookvectorsaroundtheobjectof
Table2 Averagenumberofcodebookvectors・Sequence Previous Proposed ReductionRate
Algori七hm Algorithm
578
Cヱαか・e1450
7bわヱe 71（≡m凡慮5 332
120
ガロγ5e属官dれg 952
290

interest．Wehavedemonstratedthattheproposed
algorithm canarChive consistent extrac七ionofan

ObjectofinterestL【％］

403630参考文献

4． Conclusion

1）H・Kosch，DistributedMultimediaDatabaseTech−
nologies supported by MPEG−7and MPEG−21：Thispaperpresentavideoobjectextractional−
gorithmusingLearriingVectorQuantization（LVQ）・

CRC Press．2003．

2）H・Xu・A・A・YounisL and M・R・Kabuka，−iAuto−maticmovingobject extraction forcontent−based

Eachpixelofavideoframeisrepresentedbya5−

applications， ■IEEETrans．0nCircuitsSyst．Video
Technol‥VOl．14．no．6＝PP，796−812．June2004．

Dfeaturevectorcombiningbothspatialandcolor

3）S．SunLD．R・Haynor，andY・Kim・ SemiautomaticVideo object segmentation using vsnakes． IEEE

information．Theobjectofinterestismanual1yde−

finedbyauserinthekeyframes．Forframesbe−

tweenthe keyframeS，LVQ codebookvectors areusedtoclassifythepⅨelsintoobjectorbackground・Trans．on Circuits Syst，Video Technol．，Ⅴ01．13L
n0．1．pp．75T82．Jan．2003．
4）C・Toklu・A・M・Tekalp，andA・TanjuErdeL■こSemi−
automatic vide0Objectsegmentationinthepres−enceofocclusion： IEEETrans．on Circuits Syst，

Video Technol．，VOl．10，nO．4，pP．624−629．June
2000．

Theobjectextractionperformanceisimprovedby−7−5）A・C・Bovik，TheHandBookoflmageandVideo
Processing，AcademicPress Limitedコ1st edition．
1998．

6）M・Hariadi・H．C，Loy，and T．Aoki， Semi−
automaticvideo object segmentation using工〃QWith color and spatialfeatures． IEICE Trans．
OnInf．SysthVOl．E88−D，nO．7，PP．1553−1560July2005．

7）M．Hariadi，H．C．Loy．andT．Aoki，；エLVQ−based

videoobjectsegmentationthroughcornbinationof
SPatialand color features． Proc．of TENCON，
VOl．A．pp．211−214．Nov．2004．
8）M・Hariadi・H．C・LoyコandT．Aoki，一iIntegrating
SpatialandcolorfeaturesforLVQ−basedvideoob−
jectsegmentation， Proc．ofITC−CSCC，pP．7F3P−
38−1−7F3P−38−4．July2004．
9）M・HariadiL A・HaradaL T・Aoki・andT・Higuchi・‖An LVQ−based human motion segmentation，t｝
Proc．ofAPCCAS2002，VOl．ⅠⅠ．pp．171−176，Oct．
2002．
10）M・Hariadi：A・Harada：T・Aoki、andT・Higuchi，Pixel−Wise human motion segmentation using
learningvectorquantization，Proc・Of7thInter−nationalConferenceonControlっAutomation＝andVision，PP．1439−1444：Dec・20021

11）T・Kohonen，Self−Organizing Maps3rd edition：
Springer−Verlag，2001・12）P．Villegas，Ⅹ・Marichal；and A・Salcedo・ Obp

jectiveevaluationofsegmentationmasksinvideo
sequences． WIAMIS99workshop，BerlinL Mary
1999．pp85−88．May2006．

ー8−