Integrated spatial and feature image query

IntegratedSpatialandFeatureImageQueryJohnR.SmithShih-FuChangIBMT.J.WatsonResearchCenterDept.ofElectricalEngineering30SawMillRiverRoadColumbiaUniversityHawthorne,NY10532NewYork,[e-mail]@ctr.columbia.eduThispaperwaspresentedinpartatACMMultimedia,19961AbstractWepresentanewsystemforqueryingforimagesbyregionsandtheirspatialandfeatureattributes.Thesystemenablestheusertondtheimagesthatcontainarrangementsofregionssimilartothosediagrammedinaqueryimage.Byindexingtheattributesofregions,suchassizes,locationsandvisualfeatures,awidevarietyofcomplexjointspatialandfeaturequeriesareecientlycomputed.Inordertodemonstratetheutilityofthesystem,wedevelopaprocessfortheextractingcolorregionsfromphotographicimages.Wedemonstratethatintegratedspatialandfeaturequeryingusingcolorregionsim-provesimagesearchcapabilitiesovernon-spatialcontent-basedimageretrievalmethods.21IntroductionThetremendousgrowthinthenumbersandsizesofdigitalimageandvideocollectionsismakingnecessarythedevelopmentoftoolsforindexingthisunconstrainedimagery.Inordertoprovideasystemwithimageandvideosearchcapabilities,content-basedvisualquery(CBVQ)methodsarebeingdevelopedwhichindexthevisualfeaturesoftheimages[1,2,3,4,5]andvideos[6,1].TheobjectivesofCBVQare,intheabsenceofimageunderstanding,toobtainandutilizediscriminantsthatareusefulinconductingsimilarityqueriesforvisualinformation.RecenteortsofCBVQhavefocusedonafewspecicvisualdimensions,suchascolor,texture,shape,motionandspatialinformation.However,withoutintegratingthesevisualdimensions,thecurrentcontent-basedtechniqueshavelimitedcapacitytocharacterizethecontentofthevisualimageryandtosatisfactorilyretrieveimages.Inthispaper,wepresentanewsystem1forqueryingforimagesbyspa-tialandfeatureattributes.Thesystemintegratescontent-basedandspatialquerymethodsinordertoenablesearchingforimagesbyarrangementsofregions.Wedemonstratequeriesonseveraldatabasesofimages,includingsymbolicimages,syntheticcolor-regionimagesandphotographiccolorim-ages[5].Inparticular,wedemonstratethattheintegratedspatialandfeatureapproachimprovesimagequerycapabilitiesovernon-spatial,content-basedmethods.1nitionsTheintegratedspatialandfeature(SaFe)imagequerysystemcombinesCBVQandspatialquerying(SQ).Fig.1summarizestherelationshipofthesequerymethodsandtheirintegrationintheSaFeimagequerysystem.CBIQSQabsSQCBRQrelSQSaFeFigure1:Taxonomyofimagequerymethods:CBIQ=content-basedimagequery,CBRQ=content-basedregionquery,SQ=spatialquery(absoluteandrelative),andSaFe=spatialandfeatureimagequery.1.1.1Content-basedvisualqueryTheobjectiveofcontent-basedvisualquery(CBVQ)istoretrievetheim-agesthataremostsimilartotheuser’squeryimage.CBVQisdierentfromatypicaldatabasequeryinthatitentailsasimilaritysearch.TheprocessofCBVQhasbeeninvestigatedinseveralrecenteorts:IBM’sQBICproject[1],MIT’sPhotobooksystem[3],theChabotimageretrievalsys-tem[4],andVirage’scommercialimageretrievalsystem[2].TheseCBVQsystemshaveneglectedanimportantcriteriaforassessingimagesimilarity:regionandspatialinformationandspatialrelationships.41.1.2SpatialimagequeryInaneortlargelydierentfromCBVQ,researchershavedevelopedtech-niquesforspatialimagequerybasedonthelocationsofobjects[7,8,9,10].Theseapproachescomparesymbolicimagesinwhichtheregionsorobjectshavebeendenedapriori.Spatialimagequerydoesnotincorporatefeaturessuchascolor,texture,shape,andsoforth.Itisdiculttoextendspatialimagequerytoincludefeaturemeasuresoftheobjects[11].Wedistinguishbetweentwotypesofspatialimagequery:relativeandabsolute.Inarelativespatialimagequery,theimagesarematchedbasedupontherelativelocationsofsymbols.Forexample,arelativespatialquerymayaskforimagesinwhichsymbolAistotheleftofsymbolB.Inabsolutespatialimagequery,theimagesarematchedbaseduponxedpositionsintheimages.1.1.3IntegratedspatialandfeatureimagequeryIntheintegratedspatialandfeaturequerysystem,regionsandtheirfeatureandspatialattributesarerstextractedfromtheimages.ThecomparisonoftheimagesthenconsidersthesimilaritiesofthefeatureandspatialattributesoftheregionsasdepictedinFig.2.Theoverallmatchscorebetweenimagesiscomputedbysummingtheweighteddistancesbetweenthebestmatchingregionsintermsofspatiallocations,sizesandfeatures.Therelativespatiallocationsofregionsinthetargetimagesarealsocomparedtothoseinthequeryimagetodeterminetheimagematches.Thespatialandfeatureimagequeryprocess,summarizedinFig.3,iscarriedoutonthequeryandtargetregiontables,depictedinTable1andTable2,respectively.AsdepictedinFig.3,theuserpresentsaqueryimage5BregionextractionQqk{}=ACDBACDtjqkregionextractionqueryimagetargetimagecompareIQITDqk{}tj{},()Ttj{}=CBADABCDspatialcompositionspatialcompositionFigure2:Integratedspatialandfeaturequery.Imagesarecomparedbycomparingthespatialarrangementsofregions.Q=fq0:::qK1g,whichconsistsofKregions.Eachoftheregionsqkhasspatialattributes:(x;y),(w;h)andareaandfeatureattributes:(f)whicharestoredinTable1.IMIDREGIDfxywhareaQq0f0205020801000Qq1f1706550401500Table1:TheREGIONtableforqueryimageQ=fq0;q1g.Tocomputethequery,thesystemcomp