Model-Based Recognition in Robot Vision

Model-BasedRecognitioninRobotVisionROLANDT.CHINElectricalandComputerEngineeringDepartment,UniversityofWisconsin,Madison,Wisconsin53706CHARLESR.DYERComputerSciencesDepartment,UniversityofWisconsin,Madison,Wisconsin53706Thispaperpresentsacomparativestudyandsurveyofmodel-basedobject-recognitionalgorithmsforrobotvision.Thegoalofthesealgorithmsistorecognizetheidentity,position,andorientationofrandomlyorientedindustrialparts.Inoneformthisiscommonlyreferredtoasthe“bin-picking”problem,inwhichthepartstoberecognizedarepresentedinajumbledbin.Thepaperisorganizedaccordingto2-D,2&D,and3-Dobjectrepresentations,whichareusedasthebasisfortherecognitionalgorithms.Threecentralissuescommontoeachcategory,namely,featureextraction,modeling,andmatching,areexaminedindetail.Anevaluationandcomparisonofexistingindustrialpart-recognitionsystemsandalgorithmsisgiven,providinginsightsforprogresstowardfuturerobotvisionsystems.CategoriesandSubjectDescriptors:1.2.9[ArtificialIntelligence]:Robotics-sensors;1.2.10[ArtificialIntelligence]:VisionandSceneUnderstanding-modelingandrecoveryofphysicalattributes;1.4.6[ImageProcessing]:Segmentation;1.4.7[ImageProcessing]:FeatureMeasurement-inuariants;sizeandshape;texture;1.4.8[ImageProcessing]:SceneAnalysis;1.5.4[PatternRecognition]:Applications-computervisionGeneralTerms:AlgorithmsAdditionalKeyWordsandPhrases:Binpicking,computervision,2-D,2&D,and3-Drepresentations,featureextraction,industrialpartrecognition,matching,model-basedimageunderstanding,modeling,robotvisionINTRODUCTIONmationdoexist,theircapabilitiesarestillResearchanddevelopmentincomputervisionhasincreaseddramaticallyoverthelastthirtyyears.Applicationareasthathavebeenextensivelystudiedincludechar-acterrecognition,medicaldiagnosis,targetdetection,andremotesensing.Recently,machinevisionforautomatingthemanu-facturingprocesshasreceivedconsiderableattentionwiththegrowinginterestinro-botics.Althoughsomecommercialvisionsystemsforroboticsandindustrialauto-veryprimitive.Onereasonforthisslowprogressisthatmanymanufacturingtasksrequiresophisticatedvisualinterpretation,yetdemandlowcostandhighspeed,accu-racy,andflexibility.Thefollowingdeline-atessomeoftheserequirements:lSpeed.Theprocessingspeedofacquiringandanalyzinganimagemustbecompa-rabletothespeedofexecutionofthespecifictask.Often,this“real-time”rateislessthanfractionsofasecondperpart.Permissiontocopywithoutfeeallorpartofthismaterialisgrantedprovidedthatthecopiesarenotmadeordistributedfordirectcommercialadvantage,theACMcopyrightnoticeandthetitleofthepublicationanditsdateappear,andnoticeisgiventhatcopyingisbypermissionoftheAssociationforComputingMachinery.Tocopyotherwise,ortorepublish,requiresafeeand/orspecificpermission.01986ACM0360-0300/86/0300-0067$00.75ComputingSurveys,Vol.18,No.1,March198668lR.T.ChinandC.R.DyerCONTENTSINTRODUCTION1.MODEL-BASEDOBJECTRECOGNITION2.MODELS,FEATURES,ANDMATCHING3.2-DIMAGEREPRESENTATIONS3.1ExamplesofGlobalFeatureMethods3.2ExamplesofStructuralFeatureMethods3.3ExamplesofRelationalGraphMethods3.4ComparisonoftheThreeMethodsfor2-DObjectRepresentation4.2%-DSURFACEREPRESENTATIONS4.1Example1:ARelationalSurfacePatchModel4.2Example2:ARelationalSurfaceBoundaryModel4.3OtherStudies5.3-DOBJECTREPRESENTATIONS5.1Example1:ASurfacePatchGraphModel5.2Example2:HierarchicalGeneralizedCylinders5.3Example3:MultiviewFeatureVectors5.4Example4:MultiviewSurfaceOrientationFeatures5.5OtherStudies6.RELATEDSURVEYSI.SUMMARYACKNOWLEDGMENTSREFERENCESlAccuracy.Therecognitionrateofobjectsinthesceneandtheaccuracyindeter-miningparts’locationsandorientationsmustbehigh.Althoughtherearein-stanceswhereengineeringsolutionscanbeappliedtoimproveaccuracy(e.g.,bycontrollinglightingandpositionaluncer-tainty),thesesolutionsmaynotbereal-isticintermsoftheactualenvironmentinwhichthesetasksmustbeperformed.lFlexibility.Thevisionsystemmustbeflexibleenoughtoaccommodatevaria-tionsinthephysicaldimensionsofmul-tiplecopiesofagivenpart,aswellasuncertaintiesinpartplacementduetoindividualworkstationconfigurations.Furthermore,manyrobotvisiontasksaredistinguishedbytheirperformanceindirtyanduncontrolledenvironments.Tobefullyeffective,futurerobotvisionsystemsmustbeabletohandlecomplexindustrialparts.Thisincludesrecognizingvarioustypesofpartsanddeterminingtheirpositionandorientationinindustrialenvironments.Inaddition,visionsystemsmustbeabletoextractandlocatesalientfeaturesofpartsinordertoestablishspa-tialreferencesforassemblyandhandlingoperationsandbeabletoverifythesuccessoftheseoperations.Theperformancerequirementsindicatedabovearenottheonlyfactorsdistinguish-ingrobotvisionfromotherapplicationareasandgeneralcomputervisionresearch.Thenatureofthedomainofobjectsmustalsoberecognized.Mostindustrialparts-recognitionsystemsaremodel-basedsystemsinwhichrecognitioninvolvesmatchingtheinputimagewithasetofpredefinedmodelsofparts.Thegoalofsuchsystemsistoprecompileadescriptionofeachofaknownsetofindustrialparts,thentousetheseobjectmodelstorecognizeinanimageeachinstanceofanobjectandtospecifyitspositionandorientationrel-ativetotheviewer.Inanindustrialenvi-ronm