Geometric modeling and computer vision

GeometricModelingandComputerVisionPAULJ.BESL,MEMBER,IEEEInvitedPaperComputervisionsystemscannotusegeometricmodelsforrec-ognitlonunlesstheabilitytoperformgeometricmatchingbetweenimagedatadescriptionsandgeometricworldmodelinformationisprovided.Thissurveyexaminesgeometricmatchingalgorithmsandgeometricrepresentationsforpointsets,curves,surfaces,vol-umes,andtheirspace-timetrajectories.Severalmatchingprob-lemshavebeensolvedinrecentyears,speculativesolutionsexistforotherproblems,andstillothershaveyettobesolved.I.INTRODUCTIONThewell-establishedscientificandengineeringdisci-plinesofgeometricmodelingandcomputervisionbothoriginatedduringthe1960sascomputersbecamemorepowerfulandeasiertoprogramthantheirpredecessorsofthepreviousdecade.Whereasgeometricmodelinghasbeenprimarilyconcernedwithmechanicaldesign,finite-elementanalysis,numericalcontrol(NC)machining,andvisualizationviacomputergraphics,computervisionhasattemptedbothtounderstandbiologicalvisionsystemsfromacomputationalpointofviewandtobuildusefulauto-matedvisualperceptionsystemsconsistingofcomputers,software,imagingsensors,andotherperipheraldevices.Asignificantportionofcomputervisionresearchhascon-centratedonthedifficultsignalprocessingaspectsofvisualperception,butdespitethesuccessesinthisarea,anauto-matedvisionsystemcannotadequatelyrelateitsunder-standingofimagesofascenetoourhumanunderstandingofthesamesceneunlessitpossessessimilarrelevantknowledgeaboutworld.Inparticular,avisionsystemcan-notrecognizeorreasonaboutgeometricentitieswithoutsometypeofinternalrepresentationofthoseentities.Verylittleisknownabouthowbiologicalvisionsystemsactuallystore,retrieve,andreasonaboutgeometricenti-ties,yetpeopleareabletodealwithmanygeometricprob-lemsquicklyandaccurately.Althoughmathematicalmodelsofpoints,curves,surfaces,volumesandtheirspace-timetrajectoriesareprobablynotusedinternallybybio-logicalvisionsystems,thealternativesforcomputervisionsystemsarefew.Moreover,ifavisionsystemisasubsystemofalargercomputerintegratedmanufacturing(CIM)sys-ManuscriptreceivedNovember30,1987;revisedFebruary29,TheauthoriswiththeComputerScienceDepartment,GeneralIEEELogNumber8822795.1988.MotorsResearchLaboratories,Warren,MI48090,USA.tem,itshouldbeabletocommunicatewithotherauto-mationsubsystemsusingstandardized,mathematical,geo-metricdataformats.Ourbasicpremiseisthatthesolutionstomanyvisualperceptionproblemsrequire,orwouldatleastbenefitfrom,athoroughgeometricunderstandingofimagedataintermsofcommongeometricrepresentations.Therearemyriadopportunitiesforinteractionbetweengeometricmodelingandcomputervision.Anyoff-linegeo-metricmodelingapplicationcouldusegeometricmodelscreatedautomaticallybyacomputervisionsystemthatiscapableofsensing3-Dgeometry.Dynamicgeometricmod-elingapplications,suchasreal-timerobotpathplanning,couldalsoemploygeometricsensoryfeedbackaboutenvi-ronmentgeometryfromareal-timecomputervisionsys-tem.Incontrast,computervisioncanusestaticordynamicgeometricmodelstorepresentworldknowledgetopermittherecognitionofinstancesofknowngeometryinsensordata.Thecentralthemeofthispaperwillbegeometricmatchingforgeneralpurposeobjectrecognitionandwillencompassgeometricrepresentationissues.Low-levelpro-cessingalgorithmstoextractrelevantgeometryfromimagedatawillnotbepresented,andotherhigh-levelprocessesbasedonextractedgeometry,suchaspathplanning,willalsonotbeconsidered.Inimageunderstanding,geometricmatchingisacriticalhigh-levelinterfacebetweengeometricmodelingandcom-putervisionthathasnotreceivedageneralunifyingtreat-mentineitherdiscipline’stextbooksorsurveypapers[6],VI,P61,U81,[27l,WI,WI,[W,[391,WI,[631,b41,[671,[7Ol,[W,[741,[W,[W,B41,[861,P21,WI,WI,[113l,V191,[1271,Thispaperattemptstoprovideaunifyingpresentationandisstructuredasfollows:Computervisionandgeometricmodelingarebrieflyintroducedinbroad,generaltermstoexplainwhygeometricmatchingisneeded,whyitisakeyprocessincomputervision,andwhygeometricmodelinghasnotbeenconcernedwiththisproblem.Generalgeo-metricrepresentationprinciplesareintroducednextintermsofcommongeometricformsandgeometricprimitivecompositionmethodsfollowedbyageneraldefinitionofthegeometricmatchingproblemfacing“model-based”computervisionsystems.Subsequentsectionsinvestigategeometricmatchingissuesinincreasingspatialdimensionsfrompointstocurvestosurfacestovolumes.Individualgeometricprimitiverepresentationsfromthegeometric[126],[128],[132],[1351,[142],[1431,[1471-[1491,[1551,[1791.0018-9219/88/0800-0936$01.0001988IEEE936PROCEEDINGSOFTHEIEEE,VOL.76,NO.8,AUGUST1988modelingliteratureareincluded,andanyspecialmatchingconsiderationsaretreatedforeachdimensionandrepre-sentationintheappropriatesection.Othermiscellaneousshaperepresentationsfromthevisionliteratureandtex-tureandfractalrepresentationsarealsodiscussed.Con-clusionsandunsolvedproblemsaresummarizedinthefinalsection.II.COMPUTERVISIONThegeneralstructureofalmostanycomputervisionsys-temcanbediscussedinthecontextofthesetsandmap-pingsshowninFig.1.TherealworldissensedbyoneorFig.1.Computervisionsystemstructure.moresensors(video,range,thermal,sonar,etc.)tocreate,ingeneral