Similarity of cardinal directions

SimilarityofCardinalDirectionsRoopGoyalandMaxEgenhoferin:C.Jensen,M.Schneider,B.Seeger,V.Tsotras(eds.)SeventhInternationalSymposiumonSpatialandTemporalDatabasesLectureNotesinComputerScienceVol.2121,Springer-Verlag,pp.36-55,July2001SimilarityofCardinalDirections*RoopK.Goyal1andMaxJ.Egenhofer21ESRI,380NewYorkStreet,Redlands,CA92373-8100,[e-mail]2NationalCenterforGeographicInformationandAnalysisDepartmentofSpatialInformationScienceandEngineeringDepartmentofComputerScienceBoardmanHall,UniversityofMaine,Orono,ME04469-5711,[e-mail]esssimilaritybetweenspatialscenesintheirroutineactivities,usersofpictorialdatabasesareofteninterestedinretrievingscenesthataresimilartoagivenscene,andrankingthemaccordingtodegreesoftheirmatch.Forexample,atownarchitectwouldliketoqueryadatabaseforthetownsthathavealandscapesimilartothelandscapeofthesiteofaplannedtown.Inthispaper,wedevelopacomputationalmodeltodeterminethedirectionalsimilaritybetweenextendedspatialobjects,whichformsafoundationformeaningfulspatialsimilarityoperators.Themodelisbasedonthedirection-relationmatrix.Wederivehowthesimilarityassessmentoftwodirection-relationmatricescorrespondstodeterminingtheleastcostfortransformingonedirection-relationmatrixintoanother.Usingthetransportationalgorithm,thecostcanbedeterminedefficientlyforpairsofarbitrarydirection-relationmatrices.Thesimilarityvaluesareevaluatedempiricallywithseveraltypesofmovementsthatcreateincreasinglylesssimilardirectionrelations.Thetestsconfirmthecognitiveplausibilityofthesimilaritymodel.1IntroductionSimilarityisanintuitiveandsubjectivejudgment,whichdisplaysnostrictmathematicalmodels(Tversky1977).Intheirroutineactivities,peoplecasuallyassesssimilaritybetweenspatialscenes.Similarityalsomatterswhenusersofspatialdatabaseswanttoretrievespatialscenesthatresembleasketchedconfigurationandwanttoranktheresultsaccordingtodegreesoftheirmatch.Computationalmethodsthatmatchwithusers’intuitiveexpectationsarethefocusofthispaper.*ThisworkwaspartiallysupportedbytheNationalImageryandMappingAgencyundergrantnumberNMA202-97-1-1023.MaxEgenhofer'sresearchisfurthersupportedbytheNationalScienceFoundationundergrantnumbersIRI-9613646,IIS-9970123,andEPS-9983432;bytheNationalImageryandMappingAgencyundergrantNMA201-00-1-2009;bytheNationalInstituteofEnvironmentalHealthSciences,NIH,undergrantnumber1R01ES09816-01,andbyacontractwithLockheedMartinM&DS.SimilarityofCardinalDirectionsRoopGoyalandMaxEgenhoferin:C.Jensen,M.Schneider,B.Seeger,V.Tsotras(eds.)SeventhInternationalSymposiumonSpatialandTemporalDatabasesLectureNotesinComputerScienceVol.2121,Springer-Verlag,pp.36-55,July2001Anumberofmodelsandsystemsforspatialsimilarityretrievalhavebeenalreadydeveloped.Forexample,QuerybyImageContent(Flickneretal.1995)allowsausertoretrieveimagesfromadatabasebasedonthecontentsofimages.Graphicrepresentationsofimagesstoregeometricandvisualattributesofobjectsandspatialrelationsbetweenthem.Thegeometricattributeofanobjectreferstoitsspatialextent,andvisualattributesrefertocolor,shape,andtexture(GonzalezandWoods1992).Geometricandvisualattributeshelpindeterminingthepresenceofanobjectinasceneandspatialrelationsbetweenobjectsdistinguishrelativeplacementsoftheobjectsintheembeddingspace.Combiningobjectsimilarityandspatialrelationsimilarity,onecanmakeaquerysuchas“FindsceneswhereobjectAandBarepresent,BisnorthofA,andAdisjointB.”Nabiletal.(1995)andBrunsandEgenhofer(1996)usespatialrelationsbetweenobjectsfortheassessmentofscenesimilarity.Spatialrelationsarealsousedforsimilarityassessmentinimagedatabases(Chuetal.1994;DelBimboetal.1995;DelBimboandPala1997;Chuetal.1998),multimediadatabases(Al-Khatibetal.1999;YoshitakaandIchikawa1999),andvideodatabases(JiangandElmagarmid1998;Pissinouetal.1998;AslandoganandYu1999).Inordertousespatialrelationsforsimilarityassessment,weneedcognitivelyplausiblemethodstoassesssimilaritybetweenspatialrelations.Cardinaldirectionsplayanimportantroleinthespecificationofspatialconfigurations.Forexample,thequeryscene(Figure 1a)andthethreescenesinthedatabase(Figures 1b-d)containobjectsAandBwhosetopologicalrelationisalwaysdisjoint;therefore,thethreescenesaretopologicallyequivalenttothequeryscene.However,whenconsideringthecardinaldirectionasanadditionalsearchcriterion,onecandeterminethatScene1bisthemostsimilartothequeryscene.Also,whenconsideringdirections,onecandeterminethatScene1cismoresimilartothequeryscenethanScene1d.Aq(a)(b)(c)(d)BqA0B0B1B2A1A2Fig.1:(a)Thequerysceneand(b)-(d)scenes0,1,and2inadatabase.Earliermodelsforspatial-relationsimilarityresortedtominimum-boundingrectangles(Egenhofer1997;PapadiasandDelis1997),representativepoints(GudivadaSimilarityofCardinalDirectionsRoopGoyalandMaxEgenhoferin:C.Jensen,M.Schneider,B.Seeger,V.Tsotras(eds.)SeventhInternationalSymposiumonSpatialandTemporalDatabasesLectureNotesinComputerScienceVol.2121,Springer-Verlag,pp.36-55,July2001andRaghavan1995),orprojectionsalongthecoordinateaxes(Sistlaetal.1995)tomodeldirectionrelations.Thesemethodsarecrudeapproximationsthatoftenle