A search engine for 3D models

ASearchEnginefor3DModelsThomasFunkhouser,PatrickMin,MishaKazhdan,JoyceChen,AlexHalderman,DavidDobkinPrincetonUniversityDavidJacobsNECResearchInstituteAbstractAsthenumberof3DmodelsavailableontheWebgrows,thereisanincreasingneedforasearchenginetohelppeoplefindthem.Unfortunately,traditionaltext-basedsearchtechniquesarenotalwayseffectivefor3Ddata.Inthispaper,weinvestigatenewshape-basedsearchmethods.Thekeychallengesaretodevelopquerymethodssimpleenoughfornoviceusersandmatchingalgorithmsrobustenoughtoworkforarbitrarypolygonalmodels.Wepresentaweb-basedsearchenginesystemthatsupportsqueriesbasedon3Dsketches,2Dsketches,3Dmodels,and/ortextkeywords.Fortheshape-basedqueries,wehavedevelopedanewmatchingalgorithmthatusessphericalharmonicstocomputediscriminatingsimilaritymeasureswithoutrequiringrepairofmodeldegeneraciesoralignmentoforientations.Itprovides46–245%betterperformancethanrelatedshapematchingmethodsduringprecision-recallexperiments,anditisfastenoughtoreturnqueryresultsfromarepositoryof20,000modelsinunderasecond.Thenetresultisagrowinginteractiveindexof3DmodelsavailableontheWeb(i.e.,aGooglefor3Dmodels).1IntroductionOverthelastfewdecades,computersciencehasmadeincredibleprogressincomputer-aidedre-trievalandanalysisofmultimediadata.Forexample,supposeyouwanttoobtainanimageofahorseforaPowerpointpresentation.Adecadeago,youcould:1)drawapicture,2)gotoalibraryandcopyapicture,or3)gotoafarmandphotographahorse.Today,youcansimplypickasuitableimagefromthemillionsavailableontheweb.Althoughwebsearchiscommonplacefortext,images,andaudio,theinformationrevolutionfor3Ddataisstillinitsinfancy.However,threerecenttrendsarecombiningtoacceleratetheproliferationof3Dmodels,lead-ingtoatimeinthefuturewhen3Dmodelswillbeasubiquitousasothermultimediadataaretoday:(1)newscannersandinteractivetoolsaremakingconstructionofdetailed3Dmodelspracticalandcosteffective,(2)inexpensivegraphicshardwareisbecomingfaster(at3Moore’sLaw),causinganincreasingdemandfor3Dmodelsfromawiderangeofpeople,and(3)thewebisfacilitatingdistributionof3Dmodels.1Thesedevelopmentsarechangingthewaywethinkabout3Ddata.Foryears,aprimarychal-lengeincomputergraphicshasbeenhowtoconstructinteresting3Dmodels.Inthenearfuture,thekeyquestionwillshiftfrom“howdoweconstructthem?”to“howdowefindthem?”.Forexample,considerapersonwhowantstobuilda3Dvirtualworldrepresentingacityscene.Hewillneed3Dmodelsofcars,streetlamps,stopsigns,etc.Willhebuya3Dmodelingtoolandbuildthemhimself?Or,willheacquirethemfromalargerepositoryof3DmodelsontheWeb?Webelievethatresearchinretrieval,matching,recognition,andclassificationof3Dmodelswillfollowthesametrendsthatcanalreadybeobservedfortext,images,audio,andothermedia.Animportantquestionthenishowpeoplewillsearchfor3Dmodels.Ofcourse,thesimplestapproachistosearchforkeywordsinfilenames,captions,orcontext.However,thisapproachcanfail:(1)whenobjectsarenotannotated(e.g.,“B19745.wrl”),(2)whenobjectsareannotatedwithinspecificorderivativekeywords(e.g.,“yellow.wrl”or“sarah.wrl”),(3)whenallrelatedkeywordsaresocommonthatthequeryresultcontainsafloodofirrelevantmatches(e.g.,searchingfor“faces”–i.e.,humannotpolygonal),(4)whenrelevantkeywordsareunknowntotheuser(e.g.,objectswithmisspelledorforeignlabels),or(5)whenkeywordsofinterestwerenotknownatthetimetheobjectwasannotated.Inthesecasesandothers,wehypothesizethatshape-basedquerieswillbehelpfulforfinding3Dobjects.Forinstance,shapecancombinewithfunctiontodefineclassesofobjects(e.g.,roundcoffeetables).Shapecanalsobeusedtodiscriminatebetweensimilarobjects(e.g.,deskchairsversusloungechairs).Thereareeveninstanceswhereaclassisdefinedentirelybyitsshape(e.g.,thingsthatroll).Intheseinstances,“apictureisworthathousandwords.”Ourworkinvestigatesmethodsforautomaticshape-basedretrievalof3Dmodels.Thechal-lengesaretwo-fold.First,wemustdevelopcomputationalrepresentationsof3Dshape(shapede-scriptors)forwhichindicescanbebuiltandsimilarityqueriescanbeansweredefficiently.Inthispaper,wedescribenovelmethodsforsearching3Ddatabasesusingorientationinvariantsphericalharmonicdescriptors.Second,wemustfinduserinterfaceswithwhichuntraineduserscanspecifyshape-basedqueries.Inthispaper,weinvestigatecombinationsof3Dsketching,2Dsketching,text,andinteractiverefinementbasedonshapesimilarity.Wehaveintegratedthesemethodsintoasearchenginethatprovidesapubliclyavailableindexof3DmodelsontheWeb(Figure1).Thepaperisorganizedasfollows.Thefollowingsectioncontainsareviewofrelatedwork.Section3providesanoverviewofoursystem,whilediscussionofthemainresearchissuesappearsinSections4-7,andimplementationdetailsareprovidedinSection8.Section9presentsexper-imentalresultsofstudiesaimedatevaluatingdifferentqueryandmatchingmethods.Finally,abriefsummaryandconclusionappearsinSection10,followedbyadiscussionoftopicsforfutureworkinSection11.2RelatedWorkDataretrievalandanalysishaverecentlybeenaveryactiveareaofresearch[30,52].Themostobviousexamplesaretextsearchengines(e.g.,Google[22]),whichhavebecomepartofourdailylives.However,content-basedretrievalandclassificationsystemshavealsobeendevelopedforothermultimediadatatypes,includingaudio