atWork Editor:TizianaCatarciUniversityofRome BilVideo:AVideoDatabaseManagementSystem MehmetEminDönderler, EdizS¸aykol,ÖzgürUlusoy,and Ug˘urGüdükbayBilkentUniversity, Ankara,Turkey Figure1.BilVideo’ssystemarchitecture. TheBilVideovideodatabasemanagementsystemprovidesintegratedsupportforspatiotemporalandsemanticqueriesforvideo.1Aknowledgebase—consistingofafactbaseandprehensiverulesetimplementedinProlog—handlesspatio-temporalqueries.Thesequeriescontainbinationofconditionsrelatedtodirection,ology,3Drelationships,objectappearance,trajectoryprojection,andsimilaritybasedobjecttrajectories.Therulesintheknowledgebasesignificantlyreducethenumberoffactsrepresentingthespatio-temporalrelationsthatthesystemneedstostore.Afeaturedatabasestoredinanobject-relationaldatabasemanagementsystemhandlessemanticqueries. Torespondtouserqueriescontainingbothspatio-temporalandsemanticconditions,aqueryprocessorinteractswiththeknowledgebaseandobject-relationaldatabaseandintegratestheresultsreturnedfromthesetwoponents. Becauseofspacelimitations,hereweonlydiscusstheWeb-basedvisualqueryinterfaceanditsfact-extractorandvideo-annotatortools.Thesetoolspopulatethesystem’sfactbaseandfeaturedatabasetosupportbothquerytypes. VideoclipsFactextractor Extractedfacts Knowledgebase Users WebclientVisualqueryinterface QueryResults Queryprocessor Rawvideodatabase(filesystem) Videoannotator Featuredatabase Object-relationaldatabasemanagementsystem SystemarchitectureWebuiltBilVideooveraclient–serverarchi- tecture,showninFigure1.UsersessBilVideooverthethroughaJavaclientapplet.The“QueryTypes”sidebardiscussestheformsofuserqueriesthatBilVideo’sarchitecturesupports.Theheartofthesystemisthequeryprocessor,whichrunsinamultithreadedenvironment. Thequerymunicateswithafeaturedatabaseandtheknowledgebase,wherethesystemstoressemanticandfact-basedmetadata,respectively.Thesystemstoresrawvideodataanditsfeaturesinaseparatedatabase.Thefeaturedatabasecontainsvideosemanticpropertiestosupportkeyword-,activity/event-,andcategorybasedqueries.Thevideo-annotatortool,whichwedevelopedasaJavaapplication,generatesandmaintainsthefeatures.Asmentionedpreviously,theknowledgebasesupportsspatio-temporalqueriesandthefactsbaseispopulatedbythefactextractortool,whichisalsoaJavaapplication. Fact-extractortoolThefact-extractionprocessissemiautomatic: usersmanuallyspecifyobjectsinvideoframesbytheirminimumboundingrectangles(MBRs).UsingobjectMBRs,thisprocessputesasetofspatio-temporalrelations(directionalological).Therulesintheknowledgebaseeliminateredundantrelations;therefore,thissetcontainsonlytherelationsthatPrologcan’tderivebyusingtherules.For3Drelations,extractiondoesn’turautomaticallybecausethefact-extractiontoolcan’textract3Dobjectcoordinatesfromvideoframes.Hence,usersmustmanuallyentertheserelationsforeachobjectpairofinterest.Thefact-extractortoolperformsaninteractiveconflictcheckfor3Drelationsandkeepsaframe’s3D-relationsset 66 1070-986X/03/$17.00©2003IEEE PublishedbytheIEEEComputerSociety intactforthenextframe.Thisletsusersapplyanychangesin3Drelationsbyeditingthissetinthenextframe.Thetoolalsoautomaticallyextractsobjecttrajectoriesandobject-appearancerelationsforeachobject.Moreover,usersneednotredrawobjectMBRsforeachframe;instead,theycanresize,move,anddeleteMBRs.Whenexitingthetoolaftersavingthefacts,thesystemstoressomeconfigurationdataintheknowledgebaseifthevideoisn’tyetentirelyprocessed.Thisletsuserscontinueprocessingthesamevideoclipatalatertimefromthepointwheretheoriginalsearchleftoff.Figure2showsaviewofthefactextractortool. BecauseusersmanuallydrawobjectMBRs,thesystemcan’ttolerateerroneousMBRspecifications,although,inmanycases,smallerrorsdon’taffectthesetofputed.Toautomatethisprocess,wedevelopedanobject-extractorutilitymodule,showninFigure3.2Whenweembedthismoduleintothefact-extractortool,userswillbeabletospecifyobjectMBRsbyclickingthemouseonobjects. QueryTypes BilVideo-supportedqueriesmightbeconstructedwithuser-drawnsketches.Acollectionofobjectswithsomeconditionsformsavisualquery.Suchconditionscouldincludeobjecttrajectorieswithsimilarmeasurements,spatio-temporalorderingofobjects,annotations,orevents.Searchesspecifyobjectmotionasanarbitrarytrajectoryandannotationssupportkeyword-basedsearching.Userscanbrowsethevideocollectionbeforeplexandspecificqueries.Atext-basedStructuredQueryLanguagelikelanguageisalsoavailable.1 Reference
1.M.E.Dönderler,Ö.Ulusoy,andU.Güdükbay,“Rule-BasedSpatio-TemporalQueryProcessingforVideoDatabases,”submittedforpublication. Video-annotatortoolThevideo-annotatortool,showninFigure4 (nextpage),extractssemanticdatafromvideoclipsandstoresitinthefeaturedatabase.Thetoolletsusersview,update,anddeletesemanticdataalreadyextractedfromvideoclips.Oursemanticvideohierarchycontainsthreelevels:video,sequence,andscene.Videosconsistofsequences,andsequencescontainscenesthatneednotbeconsecutiveintime.Whenpletethesemanticqueryprocessor,BilVideowillanswervideo,event/activity,andobjectqueriesbyusingthissemanticdatamodel.Videoqueriesretrievevideosbasedondescriptivedata(annotations).Conditionscouldincludetitle,length,producer,productionyear,category,anddirector.Event/activityqueriesretrievevideosbyspecifyingeventsthaturatthesemanticlayersequence(becauseeventsareassociatedwithsequences).However,thisquerytypemightalsoreturnaparticularscene(orscenes)becauseeventsmayhavesubeventsassociatedwithscenes.Objectqueriesretrievevideosbyspecifyingsemanticobjectfeatures.Becausevideosareannotated,videosalientobjectsarealsoassociatedwithsomedescriptivemetadata. Web-baseduserinterfaceBilVideohandlesmultiplerequestsreceived overthethroughagraphicalqueryinter- Figure2.Factextractor. Figure3.Objectextractor.face,developedasaJavaapplet.3Theinterfacehasqueryspecificationwindowsfordifferenttypesofqueries,thatis,spatialandtrajectory.Becausevideohasatimedimension,thesetwotypesofprimitivequeriesbinewithtemporalpredicatestoquerytemporalcontents. January–March2003 67 MultimediaatWork Figure4.Videoannotatortool. Figure5.Spatialqueryspecification. TrajectoryqueryspecificationTrajectoryofasalientobjectisapathofver- ticescorrespondingtotheobject’slocationsindifferentvideokeyframes.Displacementvaluesanddirectionsbetweenconsecutivekeyframes(vertices)definethetrajectoryfactofanobject.Inthetrajectoryqueryspecificationwindow,userscandrawtrajectoriesofobjects,asFigure6shows.Thetrajectoriesdisplayedaredynamic;userscandeleteorinsertanyvertextoatrajectory.Userscanalsochangevertexlocationstoobtainadesiredtrajectory.Object-trajectoryqueriesaresimilaritybased.Therefore,usersspecifyasimilarityvaluebetween0and100,wherethevalue100impliesanexactmatch. SpatialqueryspecificationSpatialcontentofavideokeyframeistherela- tivepositioningofthekeyframe’ssalientobjectswithrespecttoeachother.Thisrelativepositioningconsistsofthreesetsofrelations:directional,ological,and3D.Toqueryakeyframe’sspatialcontent,usersmustspecifytheserelationswithinabination.Obviously,usersshouldconstructbinationwithalogicalconnectorAND;thus,allvideoframe(s)returnedmustcontaintheserelations.Inthespatialqueryspecificationwindow,showninFigure5,userssketchobjectsasrectangles.TheserectanglesrepresentobjectMBRs.Hence,eachobjectisenclosedbyitsMBRduringthedatabasepopulationphase,andthesystemextractsakeyframe’sspatialcontentbasedonobjectMBRs.Similarly,thesystemautomaticallyextractsdirectionalologicalrelationsbetweenobjectsinthequeryspecificationphase.Becauseit’simpossibletoextract3Drelationsfrom2Ddata,thesystemdirectsuserstoselectappropriate3Drelationsforobjectpairs. FinalqueryformulationTheuserinterfacespecifiesspatialandtrajec- toryqueriesindifferentwindows.Eachofthesespecificationsformsasubquery,andthesebineinthefinalqueryformulationwindow,asFigure7shows.Thiswindowcontainsallspecifiedsubqueriesandobject-appearancerelationsforeachobject.Usersbinesubqueriesbylogicaloperators(AND,OR)andtemporalpredicates(before,during,andsoon).ExceptforthelogicaloperatorNOT,alltemporalandlogicaloperatorsarebinary.Iftheusergivesmorethantwosubqueriesasargumentstobinaryoperators,thebinesthemascumulativepairswiththeoperators.Afterapplyingoperatorstosubqueries,anewqueryisaugmentedtothelist,andessiveandbinationsepossible.Thequeryinterfacesendsthefinalquerytothequeryprocessor.Furthermore,theusercansendsubqueriesofthefinalquerytothequeryprocessoratanytime,whichwillprovidepartialresults. ExampleapplicationAnewsarchivesearchsystemcontainsvideo clipsofnewsbroadcastsandcanretrievespecificnewsfragmentsbasedondescriptionsgivenasqueryconditions.Thetraditionalapproachtothistaskrequiressearchingforkeywordsthatdescribethesemanticcontentofthenewsfragments.Forthis,atraditionaldatabasesystemwouldsuffice,becausethesesystemswouldindexnewsfragmentsbysometextualdata.However,traditionaldatabasesystemsdon’tconsiderspatio-temporalrelationsbetweenobjectsandobjecttrajectories.Theyalsodon’tsupportlow-levelvideoqueries(forexample,color,shape,andtexture).Furthermore,thetraditionalapproachmightresultin 68 Figure6.Trajectoryqueryspecification. retrievalsofirrelevantnewsfragments,whilemissingothersthatuserswouldexpect.Keyword-basedsearchingisn’tpowerfulenoughtoformulatewhatusershaveinmindasaquery.Consequently,BilVideowithitssupportofspatio-temporalandsemanticvideoqueriesprovidesamoreusefulsearchmechanism.Toretrievepreciseanswers,userscanalsoquerynewsarchivesbysomespecificapplication-dependentpredicatessupportedbyBilVideo’squerylanguage.Inthefuture,BilVideowillsupportsomelow-levelfeaturesaswell.4 Asabasisforaspatio-temporalqueryexample,weuseafragmentvideoclipcapturedfromnewsbroadcastbyanationalTurkishTVstation(KanalD).Weextractedfactsrepresentingthespatio-temporalrelationsbetweenobjects,object-appearancerelations,andobjecttrajectoriesandinsertedthemintotheknowledgebasepriortosubmittingthequeries.Figure8(nextpage)showsascreencaptureofthespatialrelationsdialogboxofthefact-extractortoolforakeyframeinthisnewsfragment,aftertheframewasprocessed.Queries1through3giveexamplesofdifferenttypesofspatio-temporalqueries. Query1:Retrievethesegmentsfromthesamplenewsclip,whereArafatandPowellappeartogetheralone(nootherobjectofinterestisinthescene),andPowellistotherightofArafat. videokeyframeswhereonlyspecifiedobjectsappear.Thepredicaterightisadirectionalpredicate.Vidisauniquevideoidentifierassignedtothesamplenewsvideoclip. Query2:Retrievethesegmentsfromthesamplenewsclip,whereTurkishPrimeMinisterEcevitandTurkishForeignAffairsMinisterCemappeartogetherclosetoeachother,andEcevitistotherightofandinfrontofCem. Figure7.Finalqueryformulation. selectsegmentfromvidwhereappear_alone(arafat,powell)andright(powell,arafat); Inthisquery,appear_aloneisanexternal(application-dependent)predicate.Itsearchesfor selectsegmentfromvidwhereright(ecevit,cem)andinfrontof(ecevit,cem)andclose(ecevit,cem); Inthisquery,closeisanexternalpredicate.It 69 January–March2003 MultimediaatWork IEEEMultiMedia Figure8.Spatialrelationsforakeyframe. searchesforvideokeyframeswithspecifiedobjectsincloseproximitytoeachother.Here,wesemanticallydefinetheclosenessasfollows:Iftwoobjectsareclose,thentheirMBRsaren’tdisjoint.Thisdefinitionmightchangeforotherapplications.Thesystemcaneasilyadapttosuchchangesthroughexternalpredicatesdefinedintheknowledgebaseordingtoapplication-specificneeds.Thepredicateinfrontofisa3Dpredicate. Query3:Retrievethesegmentsfromthesamplenewsclip,whereapolicevehiclemoveswest,togetherwithanIsraeliflagthatisabovethevehicleandoverlapsit,givenasimilaritythresholdvalueof0.8andanallowedtimegapvalueof1second. selectsegmentfromvidwhere(tr(policevehicle,[[west]])sthreshold0.8tgap1)repeatandoverlap(israeliflag,policevehicle)andabove(israeliflag,policevehicle); Thisquerycontainssimilarity-basedtrajectory,directional,ologicalconditions.TheintervaloperatorANDimpliesthattheintervalsreturnedassegmentshaveallconditionssatisfied,andthatforallvideoframesinsuchsegments,theflagisaboveandoverlapsthepolicevehicle.Thekeywordstgap(timegap)andrepeatindicatethetrajectorycondition.Theseconditionsensurethatthequeryreturnsallclipsegmentssatisfyingthegivenconditions—thatis,thepolicevehiclecanonlyforatmost1secondatatimeduringitsmovementwest. ConclusionsBilVideodoesn’ttargetaspecificapplication, thus,itcansupportanyapplicationwithvideodatasearchingneeds.Moreover,BilVideo’squerylanguageprovidesasimplewaytoextendthesys- tem’squerycapabilities,throughtheuseofexternalpredicates.ThisfeaturemakesBilVideoapplicationindependent,butwecaneasilyfine-tuneittothespecificneedsofdifferentapplications,withoutsacrificingperformance.Userscanaddapplication-dependentrulesand/orfactstotheknowledgebase.ApplicationssuitedforBilVideoincludesporting-eventanalysis,object-movementtracking(medical,biological,astrophysical,andsoon),andvideoarchives. Ourworkonsemanticqueryexecutionandquerybylow-levelpropertiesisongoing.We’restudyingtheoptimizationofuserqueries.SometutorialvideoclipsthatdemonstratethevisualqueryinterfaceandtoolsareavailableonMultiMedia’sWebsiteat/multimedia/mu2003/u1toc.htm.We’recurrentlyworkingontheintegrationoftheWeb-basedqueryinterfaceandthequeryprocessor,soBilVideoisn’tyetavailableonthe.MM Acknowledgment TheScientificandTechnicalResearchCouncilofTurkey(TÜBITAK)supportsthisworkunderprojectcode199E025. References
1.M.E.Dönderler,Ö.Ulusoy,andU.Güdükbay,“ARuleBasedVideoDatabaseSystemArchitecture,”InformationSciences,vol.143,no.1-4,2002,pp.13-45.
2.E.Saykol,
U.Güdükbay,andÖ.Ulusoy,“ASemiautomaticObjectExtractionToolforQueryinginMultimediaDatabases,”Proc.7thWorkshopMultimediaInformationSystems,2001,pp.11-20;http://www.cs.bilkent.edu.tr/~ediz/bilmdg/papers/mis01.pdf.
3.E.Saykol,Web-BasedUserInterfaceforQuerySpecificationinaVideoDatabaseSystem,master’sthesis,Dept.ofComputerEng.,BilkentUniv.,Ankara,Turkey,2001.
4.E.Saykol,
U.Güdükbay,andÖ.Ulusoy,AHistogramBasedApproachforObject-BasedQuery-by-Shapeand-ColorinMulti-MediaDatabases,tech.rep.BU-CE-0201,BilkentUniv.,Ankara,Turkey,2002. ReadersmaycontactU˘gurGüdükbayatBilkentUniv.,Dept.ofComputerEngineering,06533Bilkent,Ankara,Turkey,emailgudukbay@cs.bilkent.edu.tr. ReadersmaycontacteditorTizianaCatarciattheDept.ofInformationSystems,Univ.ofRome“LaSapienza,”ViaSalara113,00198Rome,Italy,emailcatarci@dis.uniroma1.it. 70