Object Recognition Using Vision and Touch

1. INTRODUCTION

Robotic systems are being designed and built to perform com­ plex tasks such as object recognition, gruping, parts manipulation, inspection and measurement. In the cue of objcct recognition, many systems have been designed that have tried to exploit a aingle sensing modality [1,2,3,4,5,6). Singlesensor systema are neccs­ sarily limited in their power. The p;pproach described here to over­ come the inherent Iimitation· ot a aingle sensing modality is to integrate multiple sensing modalitica (passive stereo vision and active tactile sensing) for object recognition. The advantages ot multiple sensory systems in a tuk like this an: many. Multiple sen­ sor systems supply redundant and complementary kinds of data that can be integrated to create a more coberent underatanding of a scene. The inclusion of multiple sensing systems is becoming more apparent u researeb continues in distributed systems and parallel approaches to problern aolving. The redundancy and support for a hypotbesis tbat comes trom more than one sensing subsystem is important in establishing confidence meuures during a recognition process, )1st u the disagreemcnt betwecn two sensora will inhibit a bypotbesis and point to pouible sensing or reasoning error. The complementary nature of thcse acnsors allows more powertut matehing primitives to bc used. The primitives tbat an: the out­ come of sensing with tbese complementary sensora an: three dimensional in nature, providing stronger invariant& and a more natural way to recognizc objccts wbich an: also three dimensional in nature [7).

Most object · recognition systema are model b11ed discrimina­ tion systems that attempt to find evidence eonsistent with a hypothesized model and for wbich there is no eontradictory evi­ dence (4] . Systems that eontain large amounts of information about objcct structure and relationships potentially reduce the number of false recognitiona. However, the model primitives must be computable from the sensed data. More complex objcct modela an: being built (8) but they an: of limited power unless the sensing systems can uncover the structural primitives and rclationships thcy contain. The approach used bere allowa complex and rieb modela ot objects that extends the kinds of generie objccts that can be recognized by the system. This is due to the rieb nature of the sur­ face and feature primitives the scnsora compute. Sudaces an: tbe actual parts of an objcct that we sec; the primitive computed is exactly this. Holes and cavitics an: important visual and tactile features; thcse an: also computed by integrating toucb and vision. Further, the system dcscn"bed here is viewpoint independent. The problems caused by visual occlusion an: overcome by the ability to use active touch sensing in visually occluded areas.

The domain that the system works in is one of common kitchen items; pots, pans, cups, dishes, utensils and tbe like. This is a rieb domain and in fact containa objecta rcprcsentative of many other domains as weil. The objccts are planar u weil u volumetric, contain holes and have concave and convex surtaccs. They an: also decomposable into separate components that have functional semantic meaning; bandies are distinct geometric parts that an: used for gruping, a cup's centrat cavity is used to hold Iiquida, a spout allows one to pour a liquid, a Iid covers a cavity. By buing the models of thcse objccts on gcometry and topology the system is extensible beyond this domain. The objccts are modcled in a hierarchical manner which allows the matehing process to proceed at different Ievels with support or inhibition from higher or lower Ievels of modcl matching.

Figure 1 is an overview of the system. The vision system con­ sists of a pair of stereo mounted CCD camer11. They are mounted on a 4 DOF camera frame (X, Y, pan, tilt) under computer control. l'ue tactile system eonsists of a one fingered tactile sensor attached to the wrist of a PUMA S60 robot. The control module is the overall supervisor of the system. It is responsible for guiding and directing the vision and tactile sensing modulcs. lt also eommuni­ cates witb the modcl data biiC during the recognition cycle u it tries to interpret the scene. It is able to use both low Ievel reason­ ing about sensory data and high Ievel reasoning about objcct struc­ ture to accomplish this tuk. 8oth kinds of reuoning an: needed and the system's ability to toggle between the two kinds of reason­ ing makcs it powerful. The high Ievel reasoning allows us to use the objcct model u a guide for further active aensing which is accomplished by the low levelsensing modules.

The recognition cycle consists of initial low Ievel sensing which Iimits the number of object models consistent with the sensed data. The low Ievel sensing elements provide data for local aurface and featurc matcbes whieb an: constrained by rclational cri­ teria embeddcd in the models. The system is able to eliminate models that Iack the structure uneavered by the low Ievel sensing elements. The system then invokes an objcet model that is globally eonsistent with the aensed data and proceeds to verify this model by further active sensing. Verification is done at different Ievels (component, featurc, surtace, patch) and aceording to different confidence mea.~ures at each Ievel. The remaining sections of thia paper are a detailed explanation of the various parts of the ayatem.

2. STRUCTURE OF THE OBJECT MODELS

Objects are modeled as collections of surfaces, features anc' relations, organized into four distinct hierarehic Ievels. A hierarehic model allows us to do matehing o;1 many different Ievels, allowing support or inhibition for a match from lower and higher Ievels. It also allows us to nicely separate the low Ievel or bottom up kinds of sensing from the top down or knowledge driven aens­ ing.

Tbc four Ievels of the model are the object Ievel, the component/fcature Ievel, the surface Ievel, and the patch Ievel. Figure 2 is a partial description of the model of a eoffee mug. Tbc details of the model are described below.

2.1. OBJECT LEVEL

Tbc top Ievel of the hierarchy is composed of a Iist of all tbjcct nodes in the data base. An object node corresponds to an ;nstance of a single rigid object. Associated with this node is a Iist containing a bounding box description of the object and a Iist of all the componcnts (subparts) and features of this object which make up the next Ievel of the hierarchy. For gross shape classification, 1 bounding box volumetric description of the object is included. Tbc bounding box is a reetangular parallelepiped whose size is deter­ mincd by the maximum extents of the object in the X, Y and Z directions of the modcl coordinatc syatem. A c:omplexity attribute is also includcd for each object which is a measure of the number of featurcs and components that comprise an object.

2.2. COMPONENT/FEATURE LEVEL

The secend Ievel of the model is the component/feature Ievel. Each object consists of a numbcr of component (subpart) nodes that are the result of a functional and geome:ric decomposition of an object. The components of a cof!ee mug are the body of thc mug, the bottom of the mug, and the handle. A teapot consista of a body, bottom, spout, handle and Iid. They are the major Subdivi­ sions of an object, ablc to be recognizcd both geometrically and functionally. Each c:omponent also has an attribute Iist consisf..ng of its bounding box, surface area, and priority. The priority field is an aid for recognition in which the components are ordered as to thcir likelihood of being scnaed. High priorities are assigned !arge com­ ponents or isolated c:omponents in space that pro~de (handles, spouts) . The protruding parts may show up as outbers from the vision analysis. Obscured components, such as a t'of!ee mug bot­ tom when in a normal poae, are assigned lower priorities. Tbc priority is uscd to aid the matehing probabilistic.ally. H the object is in a regular pose, then certain parts of the ob)Cct are more prom­ inent which can aid the matehing process. Each eomponent nodc contains a !ist of one or more surfaccs th1t make up this functional component and that constitute the next Ievel of the hierarehy.

Features are entities that are useful in the reeognition process. Tbc features modeled are holes and cavities. These features are important in discrimination taska for humans and are able to. bc sensed by the low Ievel sensing. Holes are modeled as ~ght cylinders with a defined axis, centroid and regular ~s aectton. Each hole nodc contains the hole's axis vector, centroid vector, and a boundary curve that contains the cross section. This curve also encloses a two dimensional area ( a "slice" through the hole) . Tbc hole node contains the inertial axes of this 2D slice c:omputed from its central moments. By defining holea in this manner, we are treating them as a negative volumetric entity, which .has implica­ tions in matching. Volumetrie elements have an ob)Ccl centcred coordinate system that contains an invariant set of orthogonal ues (inertial axes) . By discovering such entities and co~puting thcse axes Iransformations between model and world coordmates can bc effc;ted which is a requirement of viewpoint independent matching.

Cavities are features that are similar to holes but are not com­ pletely surrounded by surfacea. Cavities may only bc entered from one direction white holes can bc entered from either end along their axis. An example is the weil of the coffec mug where the liquid is pourcd. These features arc modeled aa containing an u:ia vector, a depth, a bottom point and a boundary curve. Tbc boun· dary curve is closed as in 1 hole, allowing for 1 computation of inertial axes for the cavity opening.

2.3. SURFACE LEVEL

Tbc surface Ievel consists of surface nodes that embody the constituent surfaces of 1 c:omponcnt of the object. Tbc objects arc modeled u collcctions of surfaces. Tbc sensing elementa th1t arc used are vision and touch both of which sense surface information. Each surface contains attributes such as bounding box, aurface area, a flag indicating whether the surface is closed or not and 1 symbolie description of the surfacc such · planar, cylindrical or curved. Tbc surfaces arc decompoacd aa:ording to continuity constraints. Each surface is a smooth entity containing no surfacc disc:ontinuities. Tbc surfacea contain 1 Iist of the actual bicubic surface patches that comprise this surfacc.

2.4. PATCH LEVEL

Each surface is 1 smooth cntity representcd by a grid of bicu­ bic spline surfaccs that retain C2 continuity on the compositc aur­ face (9]. Each patch contains its parametric description as weil as an attribute Iist for the patch. Patch attributes includc, surface area, mean normal vector (10), symbolic form (planar, cylindrical, curved) and bounding box. Patchea constitute the lowcst local matehing Ievel in the syatem. Tbc patches themaelves arc represented in matrix form IS a matrix of cocficients for a Coona' patch.

2.5. RELATION AL CONSTRAINTS

lt is not enough to model an object as a collection of geometric attributes. One of the more powerful approachca to reeognition is the ability to model relationshipa bctween object c:omponents and to successfully sense thcm. Tbc relational con­ straints bctween geomctric entitiea place atrong bounds on potential matches. The matehing process is in many ways a seareh for con­ sistencv betwecn the senaed data and the model data. Relational consist~ncy enforces a firm criteri1 th1t allows incorrect matches to bc rejected. This is especially true when the relational criteri1 ia based on thrce dimensional entities which cxist in the phyaical acene as oppo:;ed to two dimensional projective relationahips which vary with vicwpoint.

In lteeping with the hierarchical nature of the model, relation­ shipa exist on many Ievels of the modcl. The first Ievel at which relational information is included is the component Ievel. Each component contains 1 Iist of adjacent components, where adjacency is simple physical adjacency betwecn components. Tbc features (holes and cavities) also contain a Iist of the componentl that comprise their cross sectional boundary curvcs. Thus, 1 surface sensed near a hole will bc related to it from tow Ievel aensing, and in a seareh for model consistency, this relationship should also hold in the model. At the surface Ievel, again each surfacc c:ontaina 1 Iist of physically adjacent surfacea th1t can bc used to constrain sur­ face matching. Tbc patch relations are implicit in the structure of the composite surface patch deeomposition being used. Each patch is part of an ordered !arger grid of k.nots th1t contains relational adjacency automatically. Thus, each patchcs ncighbors are directly available from an inspection of the composite aurfaccs deftning k.not grid.

3. LOW LEVEL SENSING

Tbc sensing modalities the syatem uses arc stereo visio~ ~d tactile sensing. There are tradeoffs in speed, accuracy and noiSC m using each of these sensors. The limitations of the low Ievelsensors will constrain the accuracy of our recognition process.

The sensory data received from the two sensors needs to be integrated. In designing rulea for integrating data from these two sensors, there are a few general Observations. Vision is global, has high bandwidth, and is noisy. Touch is a low bandwidth, local, sequential process with better noise properlies than vision. Vision gives a sometimes confusing view of an object due to the coupling of geometry, surface reftectance and lighting. Touch is better able to measure directly the propertiea of objects that are desired: their shape and surface properties. It also retains more degrecs of tree­ dom in sensing objccts than a static camera which is limited by its viewpoint.

The most important difference between these sensors though is the active, controlled nature of touch versus the passive nature of visual sensing. To use touch it needs to be guided and supplied with high Ievel knowledge about its task. Blind groping with a finger is an ineffi::ient and :;low way to recognize an objcct.

3.1. VISION SENSING

The objcct to be sensed is placed on a known support surface in an arbitrary position and orientation. It is assumed to be a single rigid objcct. The cameras have previously been ealibrated with the world coordinate system of the robot arm. The stereo algorithm first uses a Marr-Hildreth operator on the images and then matches zero crossings with a stereo mateher developed by Smitley [11). The output of this is a sparse set of 3D points that form closed con­ tour regions.

These closed contour regions can be analyzed from a connec­ tivity standpoint to form a region adjacency graph. This graph establishes constraints on local surface matches. Figure 2 (upper left) contains the closed contour region analysis that results after the edge finding and stereo matehing processes. Stereo cannot ~ vide information about the interiors of these regions, and the tactile systemwill provide this information.

3.2. TACTILE SENSING

The tactile sensor being used is a rigid finger like device that is made up of 133 pressure sensitive sites. The sites are covered by a conductive elastomer that senses pressure al each site with an eight bit gray scale. The geometry of the finger also allows limited amounts of surface normal information. The sensor is mounted on the wrist of the PUMA 560 robot and is continuously monitared by a microprocessor that is capable of Ihresholding and erdering the tactile responses at each of the sites. The arm is controlled by VAL-ll programs that receive feedback from the tactile sensor's microprocessor. The arm can be commanded to move in an arbi­ trary path until the sensor reports an over Ihreshold contact or con­ tacts. These contact points, along with their normals are then reported back to the control module.

3.2.1. SURFACE TRACING ALGORITBMS

Algorithms have been developed to have the tactile system do surface tracing. Given a starting and ending point on a surface, the sensor traces along the surface reporting its contact positions and normals as it moves along. There are many potential paths between these two points on thc surfacc of thc object. The movement cyclc of the sensor begins with contact at thc starfing point on the sur­ face. The surface orientation can be determined by the location of the contact point on the sensor. Thc arm then moves then sensor a small distance off the surface in the direction of the surface normal. At this point a movement vector is calculated that is the weightcd average of the vector to thc ending point of the trace and the vec­ tor formed from previous contact points on the surface. The sen­ sor is then moved a small distance along this vector, monitaring contact continuously. U contact occurs, the cycle repeats until thc ending point is reached. U no contact occurs, then contact with the surface is re-established by moving in the surface normal direction towards the surfacc. This allowa the sensor to mak.e progress towards the goal and to stay in contact with a smoothly changing surface. Using the straight line vector to the goal alone will cause cycles and no progress towards the end point of the trace.

3.2.2. BOLE TRACING

Holes are a useful recogniticn feature that are diffi:Uit to find using machine vision alone. A hole explorer algorithm has been developed to find and quantify a hole with the tactilc sensor. Holes are modeled as cylindrical, negative vclume elements with an arbi­ trary cross section. They have an a:1is ( the cyEndrical axis) from which they can be entered and a centroid which is defined on the cross sectional slice of the hole.

The hole tracing algorithm starts with the tactile sensor proh­ ing the region to determine if it is in fact a hole. U the tip does not come in con tact with a surface, then the region is determined to be a hole. The arm is then moved in conjunction with tactile fcedback araund the contour of the hole, reporling the contact points of the hole's cross section.

4. INTEGRATION OF SENSORY DATA

The stereo matehing from vi.sion yields a sparse set of 3D points that form closed contours. The interior surfaces of these contours cannot be determined from vision alone. To find out the nature of thcse closed contour regions, the tactile sensor is used to explore and quantify the interior of these regions. Each region has a contour of 3D points obtained from stereo vision. A least squares plane can be fit to these points and the tactile sensor aligned normal to this plane, forming an approach angle for the sensor. The sensor then moves towards the plane, seeking to establish contact with a surface. U contact occurs, then the surface interpolation process deseribed below proceeds. U no contact is found within a distance Ihreshold of the least squares plane, a hole is hypothesized and a trace of the hole's contour as described abo-"-e is begun. If surface contact is made aftcr the distance threshold, then a cavity has been discovered, and its cross section is traced similarly to the hole.

The surface interpolation process assumes that the region inside the 3D contour discovered by vision is curvature continuous. U the region was not curvature continuous, then a zero crossing would have been seen inside the closed contour region [12). Determining the true nature of thesc surfaces is the heart of thc integration process. These contours can be analyzed and points of high curvature chosen as knot points for a bicubic spline interpola­ tion process described in (13). Once these knct points are chosen, the tactile system is actively guided in tracing the inferior of the closed contour region using the surface tracing algorithms described earlier. The knots create 4 boundary curves that comprise the closed contour region. Each surface is traced from the midpoint of a boundary curve to the midpoint of the boundary curve opposite. These surface traces are then combined with the contour data to create a composite bicubic spline surface which preserves the smooth nature of the surface and interpolates the sensed data points. This interpolation can be done to arbitrary precision by tracing each surface at Iiner and finer resolutions. Typically, one set of traces across the surface is suffi::ient to obtain a reasonable interpolation of the surface. These surface patches are powerful primitives. They are described by a set of parametric equations that allow easy and effi::ient calculation of surface areas, normals and curvature properlies of the patches which are useful for matching.

The integration of sensory data shows its complementary nature . Visual data can be used to guide active tactile sensing for determination of a visual regions properties. Furlher, this visual region can be extended into a three dimensional surface by thc addition of small amounts of actively guided touch sensing.

S. MODEL INVOCATION

The recognition process begins with the low Ievel vision modulcs in a bottom up f::uhion. These modules create a Iist of closcd contour regions and a region adjacency graph. This is input to thc tactilc system which will eilher interpolate a surface patch or determine that the region is a hole or cavity. This low Ievel sensins defines the primitives that are sent to the higher Ievel matchins sys­ tem to try to instantiate a model consistent with this sensory data.

5.1. LOCAL MATCHING

Local matehing is controlled by a set of rules that drive the process. Thc mies establish local surface matches for a s~nsed sur­ face patch by finding surfaces in the model surface Iist that satisfy ail the constr;;i nts below:

• The arca of the sensed surface patch must be less than or equal to thc model surface area.
• Thc bounding box of the sensed surface patch must be con­ tained within the bounding box of the model surface.
• If the senscd surface patch is planar, the modcl surface must be planar.
• If thc scnscd surface patch is cylindrical, the model surfaoe must bc cylindrical and the diffcrence of the radü of the cylindcrs must be small.
• If the scnscd surface patch is curved, the model surface must bc curvcd.

Thcre is also a set of local matehing rulcs for fcaturcs :

• If thc fcature is a hole or cavity, thc diameter of the cross scction must be within a Ihreshold & of the model diameter.
• U the feature is a cavity, its depth must be within a Ihreshold of the model cavity depth.

If the local surfacel fcature matehing is also relationally con­ sistent, then the model is considered feasible. All local surface/ fcaturc matches must be consistent with !he model rela­ tions. If a relationship exists in the scene between two matched surfaces that are not adjacent in the model, the local surfaoe matches are rcjccted. If a fcature is found, its related surfaces must also be consistcnt. By applying these relational constraints to the local matches, incorrect matches are rejected.

S.l. CHOOSING A MODEL

Once the low Ievel initial sensing has bcen done, a model must be choscn to drive the recognition process to the next stage. There are three possible outcomes of the initial sensing and local matehing proccss:

• No modcl is consistent with the data.
• One model is consistent with the data.
• More than one model is consistent with the data.

The first case reflects a possibility of sensory error. The most effective stratcgy here is to redo the sensing or change the view point to retlcct new sensory input. The second case is a desirable state of affairs; this one model is then a candidate for further verification scnsing. The third case points to the need for further discrimination among the models. Typically, the local matehing process with its geometric and relational constraints will prune the number of consistent interpretations to a small number of modela (two or thrcc). The ambiguity between modcls can be resolved at the next Ievel of sensing. In this case, one of the two or three models left will be chosen as the invoked model to be veriflecl. Choosing this model will rely on the object p:iorities discussed above and thc model complexity measure. Each consistent model has a matehing measure computed based upon the normalized pro­ bability of thc model components and features matched and the complcxity of the object's structure.

where M is the matehing probability measure, PI: is the priority o! each of the matched components and N is the total number o! component/ features !or this object.

The choice is weightecl in favor of complexity of the objects, and with equal complexity, on finding higher probability matches. The sensory subsystems are more likely to sense the high priority components and features. This is then reflected in the choice of model that is invoked. An incorrect choice will be found durins verification, at which time this model is rejected and the remaining ones are again chosen by this rule.

6. VERIFICA TION

Once a model has been chosen, the recognition process becomes a verification process, trying to substantiate the hypothesis that the chosen model is the object to be recognized. Veriflcation proceeds initially on a component/feature Ievel. Some of the componentlfeatures of this model have been partially verified by the local surface/ feature matching. Partial verification means that a component, possibly made up of a number of surfaces, has had at least one of these surfaces matchecl at the lower surface Ievel. Any component/ fcature that has not been partially verifled is then put on a Iist for verification. An important aspect of this verification is using the model to drive the recognition process. To reflect the model in the imaged scene, a transformation matrix relating model coordinates to imaged world coordinates is neeessary. The calcula­ tion of this m atrix will llllow accurate scene prediction for featurea and componcnts.

6.1. SCENE TO MODEL TRANSFORMATION

The Iransformation between model and scene consists of three translat ional parameters and three rotational parameters. This Iransformation can be computed from matched featurea or surf'lCes. Holes have an axis vector and inertial axes of their cross section in the model. ! f hole is matched, these axes ean be used to alip the model with the sensecl hole, thus satisfying the rotational com­ ponent of the transformation. The centroid of the hole can then be translated to the sensed centroid to calculate the translational parameters. Similarly, cavities are modeled as having an uis and bottom point. These can be used in the same manner as the hole axis and ccntroid to compute the Iransformation matrix.

Sc:nsed surface data can also be use<l to calculate the Iransfor­ mation matrix. The approach is to match points on sensed surfaees with model surface points. Candidates for these matehing points are points of maximum or minimum curvature or <ot surface border vertices. By using several match points a least square fit of the Iransformation matrix can be calculated (10) . Planar surfaees ean also be used to define part of the Iransformation by aligning sensed surface normals with model normals. Once this matrix is calcu­ lated, it can be usecl to verify that the initial set of local matches of surfaces and fcatures is consistent with the calculated Iransforma­ tion matrix. If they are not, the system retums to the loeal match· ing Ievel and determines a new relationally consistent set of matches, recalculating the Iransformation matrix. If there is only one relationally consistent set of local matches, then those local matches that are inconsistent with the Iransformation are rejected and the others accepted.

6.l. VERIFICA TION SENSING

The verification of the object model takes place at many Iev­ els. The top Ievel is at the component/ feature Ievel. Veriflcation at this Ievel is done by requiring every component to be at leat partially verified or an ooclusion eomputed trom the transformation matrix whieh accounts for its inability to bc sensed. In verifying a component, the surfaces that comprise that eomponent must bc sensed. This is done by examining the patehes that comprise each surface. The center point of each pateh (ealculated as the parametric center from the parametrie patch equations) is transformed by the matrix and projected into the eamera space. U these projected points lie inside a elosed contour region that ha bcen locally matched, they are occluded. U they lie outside a closed contour region or inside an unmatehed region, then they ean bc sensed by integrating vision and toueh a describcd earlier. U the points are determined to be occluded, then they must bc sensed by the tactile system alone. This is done by actively guiding the tactile sensor to these points and sensing the surf;:ce normal at this point, which should be consistent with the transformcd mean nor­ mal for the patch. By verifying pateh center points and normals, partial verifieation of a component is aceomplished.

Holes are verified by applying the Iransformation matrix to the hole axis and centroid and actively using the tactile systcm to verify the holes existence and cross sectional curve. Cavities simi­ larly are verified by applying the transformation to the cavities uis and bottom point and again using the active tactile system to sense the eavity.

Some components will not bc able to be sensed due to su~ port surface occlusion. An example of this is the coffce mug where the bottom eomponent of the mug eannot bc sensed since it is on the support surface. The applieation of the computed transforma­ tion matrix to this surface will reveal that the surface is coincident with the support surface.

6.3. CONFIDENCE MEASURES

Verifieation ean bc a time consuming and lengthy process as it involves many Ievels of sensing. Once the eomponent/feature Ievel is verified, a further verifieation can proceed at the surface Ievel and finally at the patch Ievel. Rather than continue sensing all parts of the object, a confldence measure for each Ievel is established. In the Iimit, by scnsing all modeled aurfacea and featurea and patches, verifleation will be complete. However, it will not bc physically possible to vclify all of these parts of the model due to ooclusion and inherent limitations in the sensors themsclves. Therefore, a measure nceds to be established that eomputes thc confldence of thc match. One can then predeterminc what confldcnce mcasurea are nccessary for acceptance or rejection of a model.

Thc models used are hierarchic in nature. Confldence mca­ ures can be set up at each Ievel of the model allowing acceptance or rejection based on different requirements for each Ievel. At the component/feature Ievel, a measure of confldence is the fraction of total eomponent/features partially matehed. We ean extend this idea of a partial mateh at each Ievel by including threshold criteria for accepting a partial match. A partial match at the eomponent Ievel means that some fraction of the surface's that comprise that component are matched. A partial match at the surface Ievel means that some fraetion of the patches that comprise a surface are matched. By specifying V 1 , a verification fraction at each Ievel i of the model, hierarchieal acceptance criteria will determine the amount of sensing to bc done. These vcrifleation criteria ean bc global or uscd on a per object basis, implying different amounts of active sensing for different hypotheaes.

One advantage to this approach isthat partial matehing ean bc earried out. Since the matehing is local with global constraints, par­ tial matches can be made and reported even though a global match is rejected. A further extension would be to articulated parts, where loeal transformations between components and aurfacea would have to bc 8ccounted for in the global constraints.

7. CONCLUSION

The system describcd is eurrently bcing tcsted. The experi­ mental hardware systems, model data base and surface and feature matehing routines are built. Work is presen:!y rontinuing on the higher Ievel rcasoning modules. As the numbcr of objects in the database grows, more sophisticated access mec!r::nisms for indexing into the models will bc needed.

8. ACKNOWLEDGEMENTS

This work wa supported in part by the following grants: ARO DAA6-29-84-k-0061, AFOSR 82-NM-299, NSF MCS-1:219196CER, NSF MCS 82-07294, AVRO DAAB07-84-K-F077, and NIH 1-ROI-HL-29985-01.

Rtferences

1. Nevatia, R. and Binford, '":"., "Description and recoguition of curved objccts," Artifi:illllntelligence, vol. 8, pp. 77-98, 1977.
2. Brooks, Rodney, "Symbolic reasoning among 3-D modcls and 2-D imagcs," Artifi:UJllnte!ligence, vol. 17, pp. 285-349, 1981.
3. Shapiro, Linda, Moriarty, J.D., Haralick, R., and Mulgaonkar, P., "Matching ·three dimensional models," Proc. of IEEE confe~na on panem ~cognlrion and Image proauing, pp. 534541, Dallas, TX, August 1981.
4. Fisher, R.B., "Using surfaces and object models to recognize partially obscured objects," Proc. /JCA/ 83, pp. 989-995, Karlsruhc, August 1983.
5. Grimson, W.E.L. and Lozano-Perez, Tomas, "Model based recogniti rJn and localization from sparse three dimensional sensory data," A J. memo 7 38, MIT Al Labaratory, Cam­ bridge, MA, August 1983.
6. Tomita, Fumiaki and Kanade, Talteo, "A 3D vision system: Generating and matehing shape descriptions in range images," IEEE conference on Artifi:IIJI/nte!ligence AppUctJtioru, pp. 186-191, Denver, CO, Deeember 5-7, 1984.
7. Binford, T., "Survey of model based image analysis," lnt. Jeumal of Robotic! Reuarch, vol. 1, no. 1, pp. 18-64, Spring 1982.
8. Shapiro, Linda and Haralick, Robcrt, "A hierarchical rela­ tional modcl for automated inspection tasks," Proc. IJt Inter­ national C onference on R obotic! R euarr:h, pp. 70-77, Atlanta, GA, March 13-15, 1984.
9. Faux, I.D. and Pratt, MJ., Compurational geometry for de!lgn and manufacture, John Wiley, New York, 1979.
10. Potmesil, Michael, "Generating three dimensional surface modcls of solid objects from multiple projections," IPL techn­ ical report 033, Image Processing Laboratory, RPI, Rensse­ laer, NY, Octobcr 1982.
11. Smitley, David and Bajesy, Ruzena, "Stereo Processing of Aerial Images," International Confe~na on Panern Recognlrion , Montrcal, August 1984.
12. Grimson, W.E.L., From Images to surfaces: A computational Jtudy of the human early visual rystem, MIT Press, Cambridge, MA, 1981.
13. Allen, Pctcr, "Surface descriptions from vision and toueh," Proc. 1st I ntemtJtional C onference on R obotic! Research, pp. 394-397, Atlanta, March 1984.