关 键 词：

多功能 小型 扫雪 冰车 除冰 其他 部分 设计 开题 12 CAD

资源描述：

多功能小型扫雪除冰车除冰及其他部分的设计含开题及12张CAD图,多功能,小型,扫雪,冰车,除冰,其他,部分,设计,开题,12,CAD

内容简介：

Three-dimensional shape searching: state-of-the-artreview and future trendsNatraj Iyer*, Subramaniam Jayanti, Kuiyang Lou, Yagnanarayanan Kalyanaraman,Karthik RamaniPurdue Research and Education Center for Information Systems in Engineering PRECISE, School of Mechanical Engineering,Purdue University, West Lafayette, IN 47907, USAAbstractThree-dimensional shape searching is a problem of current interest in several different fields. Most techniques have been developed for aparticular domain and reduce a shape into a simpler shape representation. The techniques developed for a particular domain will also findapplications in other domains.We classify and compare various 3D shape searching techniques based on their shape representations. A brief description of eachtechnique is provided followed by a detailed survey of the state-of-the-art. The paper concludes by identifying gaps in current shape searchtechniques and identifies directions for future research.q 2004 Elsevier Ltd. All rights reserved.Keywords: State-of-the-art; 3D; matching; Shape similarity; Shape search; CAD1. IntroductionShape has been studied by philosophers, psychologists,mathematicians, scientists, and engineers. For over acentury, philosophers and psychologists have tried tounderstand the human visual perception (HVS) systemthat recognizes three-dimensional shapes from two-dimen-sional images picked up by the human eye 15. Over thelast four decades, scientists have tried to develop ArtificialIntelligence (AI) techniques to enable computers to performthe same functions as the HVS system 68. However, theaspects of shape that philosophers and psychologists havestudied are not directly applicable to the engineeringdomain. For example, while philosophers primarily focuson mechanisms of shape perception by humans, engineersmake decisions based on shape-related attributes such asmanufacturability and functionality. As Koenderink 9suggests, Things have a shape for you, the person in whoseperception the things exist. Shape depends on the percep-tionthat is, the mode of interaction and the expectation(your theories or models). Section 1.1 defines shapeand 3D shape searching in the context of this paper.1.1. What is shape?The MerriamWebster Dictionary 10 defines the nounshapeasthevisiblemakeupcharacteristicofaparticularitemorkindofitem,aspatialformorcontour,andastandardoruniversallyrecognizedspatialform.Althoughthesedescrip-tions work for what is commonly understood by the wordshape in the English language, they are not sufficient in thecontext of analysis and representation ofshapes.Marr 11 described shape as, . the geometry of anobjects physical surface. Thus, two statues of a horse, castfrom the same mold have the same shape. Kendall 12defined shape as, . all the geometrical information thatremains when location, scale, and rotational effects(Euclidean transformations) are filtered out from an object.However, there is no standard definition of shape. For thepurpose of this paper, we will use Kendalls definition ofshape. Three-dimensional shape searching refers todetermining similarities among 3D shapes from a largedatabase of 3D shapes.0010-4485/$ - see front matter q 2004 Elsevier Ltd. All rights reserved.doi:10.1016/j.cad.2004.07.002Computer-Aided Design 37 (2005) 509530/locate/cad* Corresponding author.1.2. MotivationShape-based retrieval of 3D data has been an area ofresearch in disciplines such as computer vision 13,mechanical engineering 14, artifact searching 15, mol-ecular biology 16, and chemistry 17. All the shapesearching methods reviewed in this paper have beendeveloped and implemented for a specific discipline.However, most of these methods are relevant to CAD andengineeringproblems.The3Dshapesearchingareahassofarbeendominatedbyresearchinvisionandcomputergraphics,where researchers have extensively studied the shapematching problem. However, CAD and engineering appli-cations of 3D shape searching warrant very differentconsiderations than the shape matching problem. Forexample,domainknowledgeaboutmanufacturingprocesses,cost and material selection play a very important role in thesearch process. Inadditiontoshapematching,thereisaneedfor development of advanced engineering applications suchas clustering and automated classification. We hope that thispaper will encourage research in combining shape andproduct informationfor applications in CADandengineering.1.3. Need for shape searching in engineeringAs design personnel within companies retire, newer andoften untrained personnel with little or no knowledge ofcompanies previous design methods are being hired.Previous search methods employing keywords have hadlimited success rates since design personnel are unaware ofprevious contexts, projects, and part or peoples names. Asorganizations become more and more geographicallydistributed, better information systems will be required tolocate and reuse corporate knowledge.A 1994 survey reported that designers spend about 60%of their time searching for the right information 18. In anpaper in Scientific American, Gunn 19 estimates that only20% of the parts initially thought to require new designsactually need them; 40% could be built from an existingdesign and 40% could be created by modifying an existingdesign. More recently, Ullman 20 estimates that morethan 75% of design activity comprises reuse of previousdesign knowledge to address a new design problem.However, physical inventories such as tooling are oftennot located or not reused, resulting in significant losses.Design and associated knowledge reuse is the key toreducing new product development time.Engineering design and manufacturing have progressedextensively from 2D to 3D in the last decade. Advances in3D graphics hardware have contributed to the widespreaduse of 3D models. The use of 3D models is especially highin net-shape manufacturing processes such as injectionmolding and casting, where it is critical to visualize andunderstand the part accurately before building expensivetooling. Approximately 66% of CAD modeling in the moldmaking industry was being done in 3D in 2001. This wasexpected to increase to 80% in 2003 21. As a result, theshapes of products and associated tooling have increasedconsiderably in complexity and number, contributing to a3D model explosion.The simplest form of searching is by keyword infilenames, part numbers, or context attached to the CADmodel. Product Lifecycle Management (PLM) systemsallow part-name based searching of 3D models. However,this method is not robust primarily for the followingreasons: All models will not have a well-defined attacheddesign/manufacturing context. Keywords such as project names or part names may beunknown to the user. The context may be too narrow or too broad to retrieverelevant models. The context changes with time, such as when designersor naming conventions change.A significant amount of knowledge generated during thedesign and manufacturing phases are associated with the 3Dmodel because of the growing interdependence of PLM,MRP and CAD systems. Most of this knowledge isgeometry-related (manufacturing process details) or evengeometry-dependent (analysis results). Therefore, a searchsystem which is capable of retrieving similar 3D modelsbased on their shape will also retrieve related knowledgethat cannot be discovered by other means.This paper summarizes the state-of-the-art in 3D shapesearching and suggests future trends for applicability of thistechnology to engineering. The paper is structured in thefollowing manner. Section 2 introduces basic terminology;Section 3 describes the essential qualities of a shaperepresentation; Section 4 gives an overview of 3D shapesearching techniques. Section 5 delves in detail into state-of-the-art. Finally, Sections 6 and 7 compare the varioustechniques with respect to efficiency and effectiveness anddescribe future trends.2. Similarity metricsBefore proceeding further, it is important to define theterm similar and how similarity can be measured. TheMerriamWebster Dictionary 10 defines the adjectivesimilar as having characteristics in common: strictlycomparable or not differing in shape but only in size orposition. We are more concerned with the latter part ofthe definition. Typically, similarity is measured in termsof a similarity (or dissimilarity) metric (or measure). Indatabase terms, similarity is quantified as a metric.Metrics have been applied in databases to find similardocuments 22, images 23, audio 24, and movies 25.A metric should satisfy the metric axioms 26. Let S be aset of objects. A metric on S is defined as the functionN. Iyer et al. / Computer-Aided Design 37 (2005) 509530510d : S!S/:where u and v are nodes of the graph G, and direpresents thedegree of node i. The graph spectra obtained for differentgraphs in this manner are then compared using variousdistance measures. These measures are intuitive only whenthe objects to be compared have graphs of the same size.However, when the sizes of the graphs are not the same, thespectra have different lengths thereby making a comparisonFig. 2. Illustration of the Spherical Harmonics-based representation of a 3D model.N. Iyer et al. / Computer-Aided Design 37 (2005) 509530515difficult. McWherter and Regli 65 overcame this problemby padding constant values to the smaller of the two graphspectra to make them have the same lengths.4.3.3. Reeb graphsReeb 66 defined a skeleton structure, called the Reebgraph, which is determined using a continuous scalarfunction on an object. Three types of scalar functionshave been used, namely Height function, Curvaturefunction, and Geodesic distance. Geodesic distance hasbeen used in many applications because it providesinvariance against rotation and robustness against noiseand small perturbations. The function is integrated over thewhole body to make it invariant to the starting point and isalso normalized to achieve scale invariance.A Multi-Resolution Reeb Graph (MRG) was developedby Hilaga et al. 67 where a 3D model is divided into anumber of levels based on the value of the scalar function. Anode of the Reeb graph represents a connected componentin a particular region, and adjacent nodes are linked by anedge if the corresponding connected components of theobject contact each other, as shown in Fig. 3. Hence, theMRG has the following properties: (a) It contains parentchild relationships between nodes of adjacent levels; (b) byrepeated partitioning, the MRG converges to the originalReeb graph as defined by Reeb (finer levels approximatethe object exactly); and (c) an MRG of a certain levelimplicitly contains all the information about the coarserlevels. For example, in Fig. 3(c), the node S1contains theinformation about S4and S5and the node S0in Fig. 3(a)contains the information about the nodes S1, S2,and S3asshown in Fig. 3(b). The larger shaded regions in Fig. 3(c)correspond to the children of nodes S1, S2,and S3,respectively.4.3.4. Skeletal graphsSkeletal graph-based techniques compute the skeletonfor a model and convert it into a skeletal graph as its shapedescriptor. The concept of a skeleton was proposed by Blum68. A skeleton in 2D is the medial axis, while in 3D it isthe medial surface. Skeletonization can be performed byvarious methods such as distance transform 69, thinning70, or Voronoi-based methods 71. Additionally, curveskeletonization 72 methods have been proposed to converta 3D model into a medial axis type representation. Theskeletal graph (Fig. 4) stores the various entities obtainedafter skeletonization in a graph data structure. Advantagesof skeletal graph-based methods are that the graphs aretopology preserving and are smaller in size than B-Repgraphs. Hence, they can be used for subgraph isomorphismat a very low computational cost. Additionally, local partattributes can be stored for a more accurate comparison. It isFig. 3. Multi-resolution Reeb graph using a Height function in 2D.Fig. 4. Skeletal Graph based representation of shape.N. Iyer et al. / Computer-Aided Design 37 (2005) 509530516important to note that many engineering shapes are notamenable to skeletonization by thinning.4.4. Histogram-based techniquesHistogram-basedtechniques sample points on the surfaceof the 3D model and extract characteristics from thesampled points. These characteristics are organized in theform of histograms or distributions representing theirfrequency of occurrence. Similarity is determined by acomparison of histograms by means of a distance function.The accuracy and effectiveness of histogram-based tech-niques depend on the number of sampled points. A largernumber of sampled points result in higher accuracy.However, the efficiency is inversely related to the numberof sampled points.4.4.1. Shape histogramsShape histograms evolved from the section codingtechnique developed for retrieving 2D polygons describedin Ref. 73. Shape histograms 74 are based on apartitioning of space in which 3D models reside. Thecomplete space is decomposed into disjoint cells, whichcorrespond to the bins of the histograms. As a preprocessingstep, 3D models are made invariant to translation by movingthe origin tothe centroid. Three techniques are suggested forspace partitioninga shell model, a sector model, and aspiderweb model as a combination of the former two. Fig. 5illustrates these space partitioning techniques.a. Shell model. The space is decomposed into concentricshells around the center point. This representation isindependent of rotation. Any rotation of the 3D modelaround the center point of the model results in the samehistogram.b. Sector model. The space is decomposed into sectors thatemerge from the center point of the model. Thisrepresentation closely matches the section codingtechnique for 2D shapes. Computation of sectorhistograms is a complicated task and it makes use ofvertices of regular polyhedrons and their recursiverefinements on a sphere. Once the points are uniformlydistributed, the Voronoi diagram of the points defines anappropriate decomposition of space.c. Spiderweb model. The spiderweb model represents moredetailed information and has higher dimensionality thanthe above two models. Since the resolution of thedecomposition is a parameter, the number of dimensionscan be tailored for a particular application.4.4.2. Shape distributionsShape distributions represent the shape signature as aprobability distribution sampled from a shape functionmeasuring the geometric properties of a 3D model 75.Selection of the shape function (Fig. 6) is the primary step inthis technique.Fig. 6 illustrates typical geometry-based shape functionsas explained below:A3: Measures the angle among three random points on thesurface of a 3D model.D1: Measures the distance between a fixed point and onerandom point on the surface.D2: Measures the distance between two random points onthe surface.D3: Measures the square root of the area of the triangleamong three random points on the surface.D4: Measures the cube root of the volume of thetetrahedron among four random points on the surface.Fig. 5. Space partitioning techniques for generating shape histograms.Fig. 6. Geometry based shape functions for generating shape distributions.N. Iyer et al. / Computer-Aided Design 37 (2005) 5095305174.5. Product information-based techniquesThe techniques encompassing product information-basedsystems are specifically designed for the domain ofengineering parts. Part designs are described either basedon their manufacturing attributes or on their geometry.While group technology-based representation schemesaddress both these issues, they require the user to describethe shape of the part based on its drawing. On the otherhand, 2D section image-based methods try to eliminate userinput to a large extent by classifying the parts based on their2D image attributes. Image processing techniques alongwith neural networks have been used to compare and clusterparts based on their silhouette images.4.5.1. Group technology (GT)Group technology 76 coding and classification schemesattempt to capture design and manufacturing attributes suchasthemainshapeandsizefeaturesoftheproduct,productionquality, and material. Additionally, the manufacturinginformation may also include a part-machine assignmentmatrix,whichdescribestheprocessplanninginformation.Allthe attributes described above are either a binarynumber or anumericvalue,therebyresultinginastringoffeaturesasseenin Fig. 7. Part similarities are determined based on stringmatchingtechniques.GTcodingschemesprovideasystema-tic way of representing product information. However, GTcodesoftenhavetobegeneratedmanuallyorinteractivelybyanswering a series of questions and applying appropriatecoding rules. This is a slow and inconsistent procedure and ispronetohumanerror.Anextensiveamountofuserinteractionbetweenthedesignerandthesystemhasbeenthemainreasonfor the marginal success in mechanical engineering of thisapproach to similarity-based retrieval of parts.4.5.2. Section image-basedSection image-based techniques rely on the 2D silhouetterepresentation of parts or their sections to determinesimilarity. In this approach, the boundary of the part sectionimage is represented using a binary pixel matrix (binaryimage), while image processing techniques are used tocompare them. In particular, the contour of the silhouettecan be converted into a set of Fourier descriptors, which areaffine-invariant descriptors of the silhouette shape. Thesimilarity between different parts is determined by compar-ing the binary images or their Fourier descriptors throughthe use of a neural network 77. Both GT and sectionimage-based approaches are only suitable for extrudedshapes that have relatively constant cross-sections or shapesthat can be described with only a few features. Theincreasing complexity of engineering designs does notallow descriptions based on such a predefined set ofgeometric features and may also result in ambiguousrepresentations.4.6. 3D object recognition-based techniquesThree-dimensional object recognition techniques havebeen studied extensively by the computer vision commu-nity. Many methods have been developed for 3D objectrecognition. Some of them are based on aspect graphs7880, extended Gaussian images 81, superquadrics82, spin images 83,84, and geometric hashing 85.Extensive reviews of 3D object recognition techniques areavailable in Refs. 45,46,86. We present three methods thathave been used for detecting shape similarity from adatabase of models.4.6.1. Aspect graphThe aspect graph representation 78,79 identifiesregions of the viewing sphere where equivalent views andneighborhood relations on the viewing sphere generate agraphical structure of views. Each node of the aspect graphrepresents a general view or aspect of the 3D object and amaximally connected region on the viewing sphere. Eachlink represents some view even where transitions occurFig. 7. Example of a Group Technology code for a sheet metal component.N. Iyer et al. / Computer-Aided Design 37 (2005) 509530518between two neighboring views, namely, the accidentalviews. Cyr and Kimia 80 use two shape similarity metrics,one based on curve matching and the other based on shockgraph matching, and conclude that the latter is more suitedfor generating aspects and for recognition. The recognitionof an unknown view is done by matching it with storedprototypes for each object and by ordering them accordingto the shape similarity metric (Fig. 8). The resulting matchgives the identity of the object as well as its pose. It may,however, be noted that pose estimation is not as importantfor engineering design similarity problem as it is formachine vision. It is also important to note that aspectgraph-based shape similarity approach has only beenapplied to multi-media databases, but never tested forengineering shapes.4.6.2. Extended gaussian images (EGI)Horn 81 discussed the use of extended Gaussian images(EGI) for object recognition and object attitude determi-nation. Depth maps or needle maps (surface-normaldirection maps) computed for real-world scenes areprocessed to create an orientation histogram for the visiblehalf of the Gaussian sphere in presegmented objects.Because the extended Gaussian image uniquely determinesthe convex polyhedra, this technique appears to be ideal forconvex object recognition without occlusions. Non-convexobjects are handled in general by creating a separateorientation histogram for every view in a discrete set ofviews and matching against this enlarged data structure.Although occlusion is not a common problem inCAD/engineering applications, many engineering parts arenon-convex.4.6.3. Geometric hashingIn this technique, originated by Lamdam and Wolfson85, a 3D object is parsed into basic geometric featuressuch as surface points. From the points set, a set of basispoints are chosen and the coordinates of all the remainingpoints with respect to that basis are calculated and are thenstored in a histogram for each coordinate set. This isrepeated for all basis combinations, and the resultinghistogram is stored in a hash table. This is called geometrichashing. The objects are indexed based on the hashing and,in turn, used for matching with the query model. The binthat receives the highest number of votes for the querymodel indicates the set of models that is similar to the querymodel.5. State-of-the-artMost 3D shape searching methods have a preprocessingstage before conversion into a shape representation. Themost common preprocessing stage is a conversion into acanonical representation, which is invariant to rotation,translation, and scaling. From here on, this is referred to asnormalization.5.1. Global feature-based techniquesThe 3dbase system was developed by Cybenko et al.87. After normalization, a series of feature vectors areextracted, namely, second order moment invariants, spheri-cal-kernel moment invariants, bounding box dimensions,the object centroid, and surface area. The correlation metricis used as the similarity measure.Elad et al. 88 used moments of 3D objects as the featurevector. They suggested that moments up to order 47 areusually sufficient to represent the object. Before computingmoments for objects, a normalization process is performed.The similarity measure is a weighted Euclidean distancebetween feature vectors. The system uses a Support VectorMachine (SVM)-based algorithm to learn from the usersrelevance feedback and adjusts the weights to compensatefor the users similarity notion.Rea et al. 89 used geometric ratios such as compact-ness, crinkliness, the number of facets, surface area tovolume, and the number of holes (using Eulers equation forFig. 8. Multiple 2D views or aspects of a 3D model are extracted and the corresponding aspect graphs are used to match 3D objects.N. Iyer et al. / Computer-Aided Design 37 (2005) 509530519faceted objects). Additional shape signatures such as convexhull compactness and crinkliness were also used inRef. 90. The Euclidean distance measure was used asthe similarity metric. A database of 101 shapes from afamily of similar shapes was generated randomly using theACIS modeler scheme. The search engine results werecompared with the human perception of similarity. Theprototype of the search system can be found at http:/www. Other search systems based on globalfeatures are described in Refs. 9195.Vranic and Saupe 96,97 developed a 3D shapedescriptor based on spherical harmonics. The Fouriertransform on the shape uses spherical harmonic functionsto represent any spherical function. Feature vectors areextracted from the normalized model using sphericalFourier coefficients. These harmonic coefficients can beused to reconstruct an approximation of the underlyingobject at different levels. A nearest neighbor search is usedto find the most similar models. The prototype of the searchsystem can be found at http:/merkur01.inf.uni-konstanz.de/CCCC/. The precision-recall diagrams show that the methodusing spherical harmonics performed better than moments.Related techniques 98 used Extended Gaussian Images asa starting point to generate a spherical harmonic expansion.A harmonic-based representation was developed byKazhdan et al. 99,100. In this method, a model isvoxelized into a 64!64!64 grid and aligned such that itscenter of mass is at the center of the voxel grid, and itsbounding sphere has radius 32. The voxel grid is decom-posed into 32 different functions by restricting the voxelgrid to spheres with radii 132. Each function is decom-posed into 16 spherical harmonic components analogous toa Fourier decomposition into different frequencies. Thus,each model is represented by a 32!16 signature. TheEuclidean distance metric is used to compare twoharmonic representations. Ohbuchi et al. 101 proposed atechnique that uses a rotation invariant Fourier descriptorof depth images for a 3D model. Forty-two depthimages were generated for a 3D model at regular intervalson a unit sphere.5.2. Manufacturing feature recognition-based techniquesRamesh et al. 102 developed a feature recognition-based technique to identify similarities between parts. Thepart domain is limited to parts having planar and cylindricalsurfaces. A maximal cell convex decomposition method isproposed as an approximation to a unique decomposition.Once the decomposition is obtained, the cells are mapped toan editable library of machining features following a seriesof rules, possibly with user interaction. Next, partcharacteristics that capture the spatial and dimensionalrelationships among features are derived. Seven character-istics are defined: feature existence, feature count, featuredirection, feature size, directional distribution, size distri-bution,andrelativeorientation.Featureexistencedetermines the existence of particular features on a part,which in turn determines the variety of operations formachining the part. Feature count is a measure of thenumber of instances of a feature on the part. Featuredirection is a measure of the number of machining setupsrequired for the part. Feature size reflects the number oftools required to machine each feature type on the part.Directional distribution is relevant to the number ofoperations that can be performed in the same setup. Sizedistribution is relevant to the number of operationsperformed by the same tool. Relative orientation is ameasure of the number of setups in general. The similaritymeasure between two parts is the summation of similaritywith respect to each characteristic.Cicirello and Regli 103,104 used a graph-basedapproach to assess the similarity of solid models. Theapproach starts with mapping the solid model to a set ofSTEP AP 224 machining features. Feature extraction iscarried out using the FBMach System developed byAlliedSignal. Then a model dependency graph (MDG) forthe set of features is constructed. The MDG is arepresentation of the design features and interdependenciesof those design features of a CAD model 105. It is adirected acyclic graph where the nodes represent designfeatures, and the edges between nodes represent spatialdependency between features. The direction of the edgesrepresents the order in which the design features wereapplied during the design phase. However, the similaritybetween two models is assessed by computing the size of thelargest common subgraph (LCS) of the correspondingundirected model dependency graphs (UMDG). Since theLCS problem is NP-complete, a heuristic method wasdeveloped to compute the LCS. A variant of iterativeimprovement search (hill-climbing/gradient descent) wasused. Additionally, domain knowledge (holes map to holes,etc.) and auxiliary constraints (vertex degree, size, andlocation) were used to refine and narrow down the searchspace. However, a major limitation is that the MDG for amodel is not unique because features can be constructed indifferent ways and orders 106.The approach developed in Ref. 107 uses a graph-basedapproach to similarity assessment. A design signature is agraph structure where nodes represent various attributes ofthe design, and edges represent various relationshipsbetween attributes. The attributes may be different depend-ing on the problem at hand. The concepts of equivalencehierarchy and classification trees are introduced. Anequivalence relationship between two designs is thesimilarity between two designs with respect to an attribute.An equivalence hierarchy is a set of equivalence relationsthat make progressively more detailed distinctions betweendesigns. A classification tree uses the equivalence hierarchyto construct a tree structure where the similarity betweentwo designs is the depth of their deepest common ancestor.As an example, a prototype system for classifying machinedparts is discussed. The nodes of the design signatureN. Iyer et al. / Computer-Aided Design 37 (2005) 509530520represent machining features, while edges representrelationships between features. The equivalence relation-ship between two designs is graph isomorphism betweentheir design signatures.An approach to search a database of 2 1/2-D componentsis discussed in Ref. 108. Spatial interactions betweenfeatures are represented by a place vocabulary. The placevocabulary consists of a graph where nodes represent shapefeatures, while edges represent feature interactions. Mul-tiple feature interactions are represented by an envisionment(a forest of trees representing all potential interpretations fora component). The information in the place vocabulary andenvisionment is combined into a unique maximal featuresubgraph representation (MFSG) for every model in thedatabase. The MFSG consists only of maximal features thatcannot be subsumed by other features. Similarity betweentwo models is then reduced to matching blocks of themaximal subgraph of the query component to the maximalsubgraph of components in the database. A related approachis found in Ref. 109.5.3. Graph-based techniques5.3.1. B-Rep graph matchingEl-Mehalawi and Miller 110 used the attributed graphmatching approach to compare CAD models of engineeringparts in the STEP format. The models are converted fromthe STEP format to attributed graphs whose nodes containgeometric attributes that represent the surfaces of the STEPmodel. The graph matching process and the experimentalresults are described by El-Mehalawi and Miller 111. Thepaper takes an inexact graph matching approach that avoidsthe combinatorial problems associated with exact matching.Similarity measures are generated using an inexact graphmatching algorithm based on integer programming. How-ever, most of the models tested in the paper have small sizesand moderate complexity. Two parts with surfaces on theorder of 200 were also compared with success. However, thetimes taken for comparisons have not been presented. Whiletopological graph matching based on the original detailedrepresentation is a good approach for similarity determi-nation, it becomes unworkable for large and complicatedmodels.5.3.2. Spectral graph theoryMcWherter et al. 112 made use of a specialized graphstructure called the Model Signature Graph (MSG) con-structed from the B-Rep representation 113. MSGs areessentially attributed graphs with the vertices representingthefacesofthemodelandthevertexattributesdescribingthequalities of the face. These attributes include type of surface(flat, curved, etc.), relative size, topological identifier of thefaces (planar, conical, etc.), underlying geometric represen-tation of the surfaces (type offunction), the surface area, anda set of surface normals or aspects for the face. Similarly,edges between surfaces are described with attributes such astheir topological identifiers, concavity/convexity, geometricrepresentation, and the length of the curve.Peabody et al. 114 also used the frequency histogramsof these attributes in comparing two models. The typehistogram for a given solid model essentially represents thefrequency of the 13 types of surfaces and eight types ofcurves found in the ACIS solid modeler. The MSGessentially is as complex in topology as the original B-Rep structure. Various graph properties extracted fromMSGs, such as vertex and edge counts, maximum,minimum, mean, mode, and standard deviation of vertexdegrees, as well as graph diameter, are also used to comparesimilarities between models. In addition, McWherter et al.115 employed spectral graph theory to describe thetopology of the MSGs. The distance between graph spectrais called Eigen distance. The Type Histogram together withall the graph invariants is referred to as the InvariantTopology Vector (or ITV), which has 33 features. Similarmodels are conjectured to have similar ITVs and, hence, thedistance between ITVs provides an approximate measure ofthe similarity between models. The distance measures arecalculated based on the L2norm. Variable-size graphs aredealt with by truncating the Eigenvalue spectrum orpadding it with a set of constant values (of 0.0, 1.0 or 2.0)in order to maintain a constant size of the Eigenvalue arrayfor all models. However, it is important to note that theadjacency matrix of the MSG represents certain properties,which cannot be completely captured by the Eigenvalues.This method is suitable for complicated graph structures,which are not amenable to graph matching algorithms thatare at best NP-hard.McWherter et al. 116 provided a method for comparingthe substructure of the solid models. The approach consistsof partitioning the MSG into two or more subgraphs byremoving the edges that cross the partitions with the aim ofseparating the highly connected components. Partitioning iscontinued iteratively while also indexing the Eigenvalues ofeach of the components at each stage. This is a step towardsobtaining refined similarity measures that describe a solidmodel in terms of its local properties. However, optimalpartitioning of the graph is again an NP-hard problem.While the similarity metrics used in these papers can becomputationally fast and seem very useful for pruning thesearch space in large databases, the metrics do not seem tobe satisfactory in producing refined similarity measures thatcan finely distinguish 3D models.5.3.3. Reeb graphsHilaga et al. 67 used Multi-resolution Reeb Graphs(MRGs) for representing the topology of 3D shapes as anextension of the original Reeb graphs. Due to the highcomputational costs of calculating the integral of geodesicdistance, they used Dijkstras algorithm to evaluate anapproximate value.For topology comparison, the similarity between nodes isestimated based on the similarity of the node attributes,N. Iyer et al. / Computer-Aided Design 37 (2005) 509530521while a coarse-to-fine strategy is adopted for topologicalcorrespondence comparison. The coarse-to-fine strategy isbelieved to help avoid the combinatorial explosion of thetopology matching. Experiments were performed on 230models where the searching took on an average 12 s for eachmodel,therebyleadingto0.05 spersimilaritymeasurement.Chen and Ouhyoung 117 extended the MRG approachproposed by Hilaga et al. to handle practical parts. Theclaim was that the original MRG-based method neededsome modifications for accurate determination of the searchkey. To achieve this objective, the paper recommendsadequate preprocessing by resampling the original triangu-lated models to split large triangles into smaller trianglesbefore determining the MRGs. A database of 445 modelswas used for testing the system. The search system isimplemented and demonstrated on their website at http:/3/dynamic. The paper reported the averagetime for comparing two models as 0.08 s, compared to the0.05 s reported by Hilaga et al. The extra computation timemay be attributed to the extra costs of preprocessing themodels for better accuracy.Bespalov et al. 118 applied the MRG-based approachfor a large number of engineering parts. They, however,reported that small variations in topology producedsignificantly different similarity between models. TheMRGs were also found to be sensitive to the surfaceconnectivity of the VRML models, thereby producingspurious entities.In summary, the MRG-based approach has the followingadvantages: (a) it works for non-orientable, non-closed, andnon-manifold surfaces; (b) it is position, orientation, andscale independent; (c) it considers local and topologicalsimilarity while comparing the 3D objects; and (d) it adoptsa hierarchical strategy to reduce the search space throughmultiple levels of resolution. Major limitations of an MRG-based approach are the following: (a) it is affected bysurface connectivity; (b) it is more sensitive to geometrythan topology; (c) it is not amenable to sub-graph matching;(d) it does not always represent the skeleton; and (e) itproduces vertices of different density. Chen and Ouhyoung117 concluded that using a hierarchical medial axis-basedmethod would be more useful in overcoming some of theseproblems, while Bespalov et al. 118 recommended usingbetter scalar functions that also take into account thetopology of the object.5.3.4. Skeletal graph-based techniquesSundar et al. 119 presented a skeletal graph-basedmethod using distance transform. The skeletonizationmethod thins the volumes to a desired threshold basedupon a thinness parameter given by the user. A family ofdifferent skeletal voxels is each thinner than its parent. Thethinness parameter for a voxel is the difference in value ofthe distance transform at the voxel and the mean distancetransform values of its 26-neighbors. Once the skeletalvoxels are generated, they are converted into a directedacyclic graph by applying the minimum spanning treealgorithm. A topological signature vector is also stored foreach graph similar to Ref. 112. The graph isomorphismalgorithm is reformulated to find the maximum cardinality,minimum weight matching in a bipartite graph. A recursivedepth-first search is applied in order to preserve thehierarchical structure of the graph. Two measures ofsimilarity are calculatedtopological and local shapesimilarity. Local shape similarity is calculated by matchingthe radial distribution of the distance field values at eachnode in the graph. A database of 100 models was used fortesting both global and local similarities.Iyer et al. 120 and Lou et al. 121 used thinning as theskeletonization method. A 3D model is converted into avoxel model and then into a thinned skeleton. The thinnedskeleton is converted into a skeletal graph through askeleton marching algorithm. The skeletal graph consistsof nodes, edges, and loops. Each edge in the skeletontranslates into an independent geometric entity, while eachloop represents a hole in the 3D model, thereby giving ashape to the model in physical space. Skeletal graphspreserve the geometry and topology of the model and areconsiderably smaller than the B-Rep graphs and insensitiveto minor perturbations in shape. Additionally, featurevectors such as moment invariants, geometry and voxeliza-tion parameters, and graph parameters are stored in thedatabase. The search process consists of feature-vectorsearching as well as skeletal graph-based searching. Adatabase of 150 models was used to test similarities betweenmodels. However, thinning does not yield intuitiveskeletons for many engineering components, especially forshell-like parts. In order to overcome the disadvantages ofthe skeleton-based approach, they also describe a multi-stepsearch approach that uses both global feature vectors and theskeletal graphs in different steps.Kim et al. 122 presented a method for reducing 3Dsolid models into skeleton graphs based on medial axistransform and dilation. Triangulated models of the objectsare initially voxelized with certain resolution, and skeletonsare obtained based on the rank of the voxels in the model.The rank of a voxel is defined as the number of layers ofvoxels surrounding it. For example, in Fig. 9, pixel A has arank of 0, while pixel B has a rank of 1. Hence, the skeletonFig. 9. An illustration of the rank of a voxel during dilation.N. Iyer et al. / Computer-Aided Design 37 (2005) 509530522of this image consists of pixels A and B. These pixels arecalled nodes. For each pixel in the skeleton, k dilations areperformed around a pixel with rank k, starting with thepixels having highest rank K. Dilations are then performedsuccessively for all pixels in the skeleton thereby recon-structing the object. However, care is taken not to dilate anynode pixels of lower rank that are already a part of thedilations of a pixel with higher rank. This method is directlyextended to 3D voxel models. The graph is finally obtainedby the union of nodes for which dilation was performed.Each node now holds information on all the voxels that wereformed during dilation and its own rank. If two nodes havecommon voxels then the voxels are assigned to the nodewith a higher degree while performing the union operation.In order to reduce the size of the graph, a method ispresented to merge nodes based on a threshold rank and sizeof the nodes. Experiments on a few models are presentedshowing a considerable decrease in the size of the graphs.The above method is prone to problems with voxeliza-tion resolution. Different graphs may be produced byvarying the resolution during voxelization. To remedy thisproblem, if the same resolution is applied to all models, thegraphs generated may not reflect the perception of the user.Nagasaka et al. 123 converted a 3D model into a voxelmodel and subsequently converted it into a line skeletonbased on distance transform. A distance measure, DS,denoting the distance of a voxel from the surface, is definedfor all the voxels in the model. The voxels with themaximum DSvalues constitute the skeleton and are definedby three types of geometries, lines, circular rings, andtriangles. These skeletons are linked to each other with orwithout distance for connected and disconnected skeletons,respectively. Each skeleton is associated with a set of nineattributes including the DSdistribution, volume, and linkstrength. The similarities among 36 casting workpieces arecompared based on their skeletons, where each skeleton isrepresented as a tree with 126 leaves. A back-propagation-based neural network is trained using these attributes toclassify the objects into a set of three distinct groups (calledmaster data objects). All the other modelsin the database areclassified into one of these three groups. Although some ofthe models have reasonable similarity estimates, others havesimilarity estimates that are counter-intuitive.5.4. Histogram/distribution-based techniquesAnkerst et al. 74 used shape histograms in searching for3D protein structures. Before the computing of shapehistograms,modelsarenormalizedwithrespecttotranslationand rotation. Then a Principle Axes Transform is performedon the model. The Euclidean distance function neglects anyrelationship between vector components and, hence, aquadraticdistancefunctionisusedinordertodetectsimilarityof histograms. However, this leads to increased dimension-ality. In order to achieve good efficiency, a multi-step queryprocessing paradigm is followed. An index-based filter stepproducesasetofcandidates,andasubsequentrefinementstepperforms the expensive exact evaluation of candidates. Amulti-dimensional index structure is used to minimize thenumber ofaccessed index pages.A similar search technique for mechanical parts usinghistograms was proposed in Ref. 124. As a preprocessingstep, the models are normalized into a canonical form andvoxelized. The 3D space is divided into axis parallelequisized partitions. Each of these partitions is assigned toone or several bins in a histogram depending on the specificsimilarity model. By scaling the number of partitions, thedimensionality of the feature vector is controlled. However,there is a tradeoff between dimensionality and accuracy ofrepresentation.A variation on histogram-based techniques was proposedin Ref. 125, where shapes are matched using 3D shapecontexts. Shape contexts were first proposed for 2D shapesin Ref. 32. A shape is represented as a discrete set of pointssampled from the internal or external contours on the shape.For a point, the relative coordinates of the remaining pointsare computed as a distribution. This histogram is known asthe shape context.Osada et al. 126 used shape distributions for thecomparison of 3D models. The D2 shape function asdescribed in Section 4.4.2 was chosen for computation sinceit was found to be robust and efficient. Additionally, it isinvariant to translation and rotation.Having calculated the distances between random points,the distances are normalized using the mean distance. Theshape distribution is a 1D probability distribution thatmeasures the frequency of occurrence of distances within aspecifiedrangeofdistancevalues.Thedissimilaritybetweentwo3Dmodelsiscalculatedusingvariousdistancemeasuressuch as Minkowski LNnorms. The prototype of their searchengine can be found at /.A similar approach was used in Ref. 127 to comparesolid models of mechanical parts. The D2 shape function75 was used and shape distributions are generated.However, the shape distribution for a part is split intothree separate distributions. The first distribution (IN) iscalculated for all pairs of points where the line connectingthem lies inside the model. The second distribution (OUT)considers pairs of points where the line connecting them liesoutside the model. The third distribution (MIXED) iscalculated for all pairs of points where the line connectingthem passes both inside and outside the model. Thedissimilarity between models is calculated similar toRef. 126.Ohbuchi et al. proposed another variation of thetechnique in Ref. 128.Two 2D histograms Angle-Distance(AD) and Absolute Angle-Distance (AAD) were calculatedbased on the D2 shape function 75. The AD histogram wasconstructed by measuring both the distance between a pairof points and the angle formed by the surfaces on which thepair of points are located. The AD distribution performswell for models that have properly oriented surfaces withN. Iyer et al. / Computer-Aided Design 37 (2005) 509530523a consistent representation. The AAD histogram wascalculated for models that have unoriented or inconsistentlyoriented surfaces. The AAD histogram calculates theabsolute value of the inner product to increase robustness.It was found that the AD and AAD histograms outperformedthe method described in Ref. 126. Ohbuchi et al. 129 alsoproposed a related method that generated AAD histogramsfor an Alpha Shape 130 of a 3D model.5.5. Product information-based techniques5.5.1. Group technologyA system for exchanging of product information betweendesigners and manufacturing service providers over theInternet in a distributed setting was developed by Kalyana-pasupathy et al. 131. As part of this system, a distributedGT code generation system was developed and is claimed tobe useful for comparing similarity between parts.The GT code generation system requires the user toanswer many questions regarding the main attributes of eachpart indexed in the system.Iyer and Nagi 132,133 conducted experiments on arandomly generated database of parts. The objective was todevelop a design decision support system allowing adesigner to assess the manufacturability of a new designand to select optimal partners to contribute to the realizationof the design by evaluating the cost, quality, cycle time, etc.The paper adopted a two-pronged approach to findingsimilar parts using the GT Code. In the first part, the usersubmits a query about the number of attributes that arebased on the GT Code of the part. This specifies the searchintent of the user, in addition to which the user must specifya desired level of similarity. The system returns parts withsimilar attributes, subsequently being input to the nextmodule, which sorts the retrieved parts based on theircritical design information.Hermann et al. 134 developed design similaritymeasures in the context of variant process planning. Theyrequire a user to define the process plan similarity measureand select the process plan attributes. Subsequently, the usermust also define a mapping function between the designattributes and the process plan attributes. The designattributes are the geometric attributes in the GT Code ofthe design. Finally, the user also needs to define the designsimilarity measure between two designs based on theirdesign attributes. This approach makes the followingassumptions: (a) the user can (at least approximately)estimate the process plan for a new design; (b) there is one-to-one mapping from the design and the process plan(excludes alternate plans); and (c) the user must be able tocorrelate between the design attributes and the process planattributes. The implicit assumptions here are that the user isa part of manufacturing and process planning, rather thandesign. Therefore, this approach is not relevant for the earlydesign process where a designer would be expected toperform cost estimation for new designs.5.5.2. Section image-basedBack-propagation-based Artificial Neural Networks(ANNs) were used by Chung and Kusiak 40 for groupingengineeringpartsbasedontheirpartgeometry.Thegeometryofastandardpartisdescribedintermsofavectorrepresentingthebinaryimageoftheenvelope(shape).TheANNtakesthispart geometry expressed as a vector for binary values as theinputandclassifiesitintooneoffivepredefinedclasses.Allthepartsusedinthisstudywerebinarizedintoimagesofstandardsize (12!16 pixels). The network was trained with fivedifferentpartsandtestedwith15partsthatweregeneratedbydistorting these five parts. However, most of the partsconsidered here are prismatic and simple, making theapproach difficult to generalize. It is also difficult to reasonout with neural networks with regards tothe classification.LeeandFischer135usedthegeometryofthepartsaswellastheirprocessroutingdataforgroupingpartsbasedontheirGT Code. Their approach for representing the geometry isbased on the similarity invariant Fourier description of thetwo-dimensionalimageoftheparts.Theprocessroutingdatasuch as machine-part matrix, process times, size of the part,etc.arealsoobtainedforthesamepart,andacompletevectorof all the features (geometry and process data) is used fortraining and testing a Fuzzy ART-based neuralnetwork. TheNeural Network is designed to classify test images to one ofnine different training classes provided while training basedon13inputattributes(fivegeometryandeightmanufacturingprocess features).Smithetal.42alsousedanART-basedneuralnetworktoclassifypartsintogroupsusingtheGTcodingscheme.Pixelsfrom the 2D silhouette images of parts are used as input fortraining the neural network. However, the representationproposed in Ref. 42 is richer than simple silhouettes.Important geometric information such as positions of holesand bend-lines are separated before being fed into the neuralnetwork. In addition to 2D silhouette based representations,3D voxel-based representations were also proposed. How-ever, the process becomes complicated and unmanageableeven for small number of parts in 3D. Therefore, the authorspropose using the coefficients of the geometric equations forthe facets of the 3D model as the parameters to the neuralnetwork.Therefore,eachfacetofthe3Dmodelisrepresentedas a point in 4D space where each dimension represents thecoefficientsofthefacet.Theauthorsreportthatthissystemhasbeen implemented in the Boeing Company as part of theNeural Information Retrieval System (NIRS) for designretrieval.5.6. 3D object recognition-based techniques5.6.1. Aspect graphCyr and Kimia 80 used aspect graphs to assess thesimilarity between 3D models. The object recognitionscheme itself has been used in generating the aspects so asto reduce the indexing of the objects in the database.A shock graph-based shape similarity metric was used.N. Iyer et al. / Computer-Aided Design 37 (2005) 509530524The shock graph-based metric is more sensitive to theview changes in the adjacent views than the curvematching-based metric. Adjacent views are clustered in,thus generating the aspect using a seeded region growingtechnique, which satisfies the local monotonicity andobject specific distinctiveness of the aspect view criteria.After the aspects have been generated, the comparison oftwo 3D models is done by matching the 2D aspect views.The results presented are based on a database of 18objects.5.6.2. Extended gaussian images (EGI)Shum et al. 136 proposed a variant of the EGI. Eachpolyhedral 3D surface object without holes is representedusing the local curvature distribution over a deformedtessellated sphere, similar to the Gaussian sphere. Thetessellated sphere is iteratively deformed to coincide withthe nodes of the sphere and the original data set. Thesimilarity metric is defined as a distance function on thesphere. The distance between two shapes can be computedin time O(n2), where n is the number of nodes. The resultsbased on experiments with nine freeform shapes arepresented using the L2metric. This approach is valid onlyfor shapes with topology genus zero.5.6.3. Geometric hashingLeibowitz et al. 137 used geometric hashing forcomparing protein molecules for multiple structural align-ment and core detection in an ensemble of proteinmolecules. The 3D object consists of the set of data pointspertaining to the atomic coordinates here. It was observedthat the geometric hashing implementation is memoryintensive. Wolfson and Rigoustos 138 described the 3Dimplementation aspects of the geometric hashing algorithm.Gueziec et al. 139 discussed the use of geometric hashingin 3D medical image registration, where the crest lines inimages are the main geometric features used for hashing.6. DiscussionGlobal feature-based methods while being computa-tionally efficient are unable to discriminate amongdissimilar shapes. Manufacturing feature recognition-based methods do not decompose shapes uniquely.Additionally, they may require human intervention.Topological graph-based techniques are intractable forlarge graphs because of the high complexity of graph/subgraphmatchingproblems.Skeletalgraph-basedmethods are not applicable to all kinds of shapes.Histogram-based methods have a tradeoff betweencomputational cost and number of sampled points.Sampling a lower number of points leads to very lowaccuracy. Product information-based techniques are notrobust or require extensive human input. Three-dimen-sional object recognition techniques have been tested forlimited shapes and have high storage/computational costs.In summary, each technique has its own advantages andlimitations. The choice of technique depends on the typeof shape being searched and the level of discriminatingpower required by the application. As an example, if theapplication requires classification of shapes, global objectfeatures could be used. If the application requiresdetection of local dissimilarities among relatively similarshapes, techniques that allow local support such astopologicalgraph-basedorskeletalgraph-basedtechniques can be used. Table 1 summarizes theadvantages and limitations of all the 3D shape searchingmethods described above.All the above techniques have only been implemented ina research setting and have undergone limited testing.Additionally, there are very limited performance criteriaand databases for 3D shape search techniques. Hence, it isdifficult to quantitatively compare or evaluate thesetechniques.A large body of work has been done in the informationretrieval (IR) area to evaluate information retrieval systems140142. System efficiency and search effectiveness aretwo criteria extensively used by IR researchers forquantitative comparison of search techniques.6.1. System efficiencySystem efficiency is composed of representation effi-ciency and database retrieval (comparison) efficiency. Wesummarizethecomputationalandcomparisoncostsforsomeshape-based search techniques in Table 1. For sometechniques such as feature recognition and section image-based techniques, it is difficult to determine algorithmiccomplexity. Nevertheless, for the sake of completeness, wehave presented complexities for those algorithms that havebeen analyzed in literature. It is important to note that this isnot a comprehensive study of algorithmic complexity of alltechniques. Additionally, there are many variations of thesame approach leading to different computational costs. Forsuch approaches, we have used the computational costspresented by the earliest study.6.2. Search effectivenessSearch effectiveness is defined as the ability of a searchtechnique to retrieve a maximum number of relevant shapeswithin a limited number of retrieved shapes. Searcheffectiveness has been used extensively by InformationRetrieval researchers. However, computation of effective-ness requires a substantially large dataset of standarddocuments against which one can perform measurements.The ideal search system would have the maximum possibleeffectiveness, i.e. all relevant models are retrieved and allretrieved models are relevant. However, in practice, this isnotpossiblebecausehigh-levelshapecontentisdescribedbylow-level descriptors in the database, which cannot fullyN. Iyer et al. / Computer-Aided Design 37 (2005) 509530525capture the shape. The terminologies which will be used inassessingsearcheffectivenessaredescribedinTable2143.a. True Positives (TP)the number of relevant resultsretrievedb. False Positives (FP)the number of irrelevant resultsretrievedc. True Negatives (TN)the number of irrelevant resultsnot retrievedd. FalseNegatives (FN)thenumberof relevantresultsnotretrieved.Search effectiveness can be quantified collectively byPrecision/Recall curves 143 or the Receiver-OperatingCharacteristic (ROC) curve 144 of the search system.ROC curves plot specificity at a range of sensitivities. Anexample of a Precision/Recall curve for some 3D shapesearching methods has been described in Ref. 145.7. Future trendsWe believe that the 3D shape searching area is still in itsnascent stages. Some important issues that need to beaddressed are:a. Applications for 3D shape search. 3D shape search lendsitself to a variety of real-world engineering applications.For example, diverse applications have been proposed inliterature such as clustering similar 3D models 114,121, range queries 65, nearest neighbor queries 115,121,146,147 and automated model classification 148.Current research does not consider domain knowledge inengineering in application development. Domain knowl-edge coupled with shape-based techniques will beimperative for widespread use of 3D shape searchsystems. Additionally, to make it easier for industriesto implement such systems, tight integration withCAD/CAM/PLM systems will be necessary.b. Application-driven benchmark databases. Three-dimen-sional shape searching is being applied in diverse areassuch as mechanical engineering, bio-informatics, medi-cal imaging, and computer vision. Applications in theseareas are driven by different requirements and con-straints. A critical need for evaluating various searchtechniques is the development of benchmark databasesfor various application domains. Two such benchmarkdatabases are the Princeton Shape Benchmark (http:/benchmark/) and the NationalDesign Repository (),both of which have datasets for download 149,150. Forapplicability of shape search techniques to engineeringdatabases, comparative studies need to be performedusing standard datasets consisting of real-world engin-eered components. Since users of 3D shape searchsystems are likely to be from different engineeringdepartments, standard datasets must reflect the percep-tion of different users. For example, while a designermight think that two components are similar, amanufacturing engineer might suggest two totallydifferent manufacturing processes for them.c. Improving search effectiveness. Relevance feedbacktechniques reduce the semantic gap between the usersnotion of similarity and the system notion of similarityand improve search effectiveness 88,151153. Simi-larityisasubjectivemeasureanddiffersfromusertouser.The shape representation and corresponding similaritymeasure should be customizable. This can be accom-plished using hierarchical or multi-step search strategies146,147. Effectiveness can also be enhanced bydeveloping interfaces that help the user compose queriesthat accurately represent the users intent or by develop-ing active learning strategies for automatic annotation154. Currently, a large gap exists between engineeringand research in the psychological sciences. Studies doneby cognitive psychologists will be useful in under-standing user intent thereby improving search effective-ness. Forexample,Corney etal. 90 used human inputtooptimize parameters for improving search performance.d. Better shape representations. Shape representationsshould be designed keeping in mind the humanperception of shape/similarity 3,11. Interdisciplinaryresearch with cognitive sciences will help yield bettershape representations.e. Increasing efficiency. System efficiency can be increasedby using parallel or distributed computing methods forcomputer intensive tasks. Depending on the application,it may be more desirable to obtain a quick, information-preserving shape representation than a time-consuming,exact shape representation. However, it is also undesir-able to obtain an oversimplified shape representation.Database efficiency can be increased by the use ofappropriate indexing methods.Three-dimensional shape searching is receiving a lot ofinterest from researchers worldwide. We are optimistic thata feasible shape search system will drive newer applicationsin the future.AcknowledgementsThe initial funding for this project came from the 21stCenturyResearchandTechnologyFundawardfromthestateof Indiana. We acknowledge Professor Karthik RamanisUniversity Faculty Scholar award from Purdue University,which seeded this project. Supplemental support fromTable 2Measures of search effectivenessPrecisionTP/(TPCFP)RecallTP/(TPCFN)SensitivityTP/(TPCFN)SpecificityTN/(TNCFP)N. Iyer et al. / Computer-Aided Design 37 (2005) 509530526thee-EnterpriseCenteratDiscoveryPark,PurdueUniversityis acknowledged. We also recognize the Innovation Realiz-ation Laboratory at Purdue University for supporting NatrajIyer. Finally, we would also like to thank the anonymousreviewersforprovidingvaluablesuggestionstoimprovethispaper.References1 Fechner GT. Elements of psychophysics. Holt, Rinehart andWinston: New York; 1860/1966.2 Gordon IE. Theories of visual perception. England: Wiley; 1989.3 Yantis S. Visual perception: essential readings. Philadelphia, PA:Psychology Press; 2001.4 Wertheimer M. Gestalt theory. Soc Res 1944;11:7899.5 Zusne L. Visual perception of form. New York: Academic Press;1970.6 Attneave F. Some informational aspects of visual perception.Psychol Rev 1954;61:18393.7 Hoffman DD, Richards WA. Parts of recognition. Cognition 1984;18:6596.8 Lowe DG. Three-dimensional object recognition from single two-dimensional images. Artif Intell 1987;31:35595.9 Koenderink JJ. Solid shape. Cambridge, MA: MIT Press; 1990.10 11 Marr D. Vision: a computational investigation into the humanrepresentation and processing of visual information. San Francisco:W.H. Freeman; 1982.12 Kendall DG. The diffusion of shape. Adv Appl Probab 1977;9:42830.13 Pope A. Model-basedobject recognition:a survey of recent research.Technical Report 94-04. Canada: Department of Computer Science,University of British Columbia; 1994.14 Kriegel H-P, Brecheisen S, Kro ger P, Pfeifle M, Schubert M. Usingsets of feature vectors for similarity search on voxelized CADobjects.Proceedingsofthe ACMSIGMODInternationalConferenceon Management of Data (SIGMOD03), San Diego, CA 2003.15 Rowe J, Razdan A, Collins D, Panchanathan S. A 3D digital librarysystem: capture, analysis, query, and display. Proceedings of theFourth International Conference on Digital Libraries (ICADL),Bangalore, India 2001.16 Kastenmu ller G, Kriegel H-P, Seidl T. Similarity Search in 3DProtein Databases. Proceedings of the German Conference onBioinformatics, Ko ln 1998.17 Bruno IJ, Kemp NM, Artymiuk PJ, Willett P. Representation andsearching of carbohydrate structures using graph-theoretic tech-niques. Carbohydrate Res 1997;304:617.18 Leizerowicz W, Lin J, Fox MS. Collaborative design using WWWProceedings of the WET-ICE96, CERC, University of WestVirginia 1996.19 Gunn TG. The mechanization of design and manufacturing. Sci Am1982;247(3):86108.20 Ullman DG. The mechanical design process, 2nd ed. New York:McGraw-Hill; 1997.21 Christman A. Its all about the geometry Moldmaking technologymagazine, May 2001. PA: Communication technologies; 2001.22 BrinS, Page L. The anatomyofa largescale hypertextual websearchengine. Proceedings of the Seventh International World Wide WebConference (WWW7), vol. 30 1998 p. 10717.23 Castelli V, Bergman L. Image databases: search and retrieval ofdigital imagery. New York: Wiley; 2001.24 Foote J. An overview of audio information retrieval. ACMMultimedia Syst 1999;7(1):211.25 Veltkamp RC, Burkhardt H, Kriegel H-P. State-of-the-art in content-based image and video retrieval. Dordrecht: Kluwer AcademicPublishers; 2001.26 Copson ET. Metric spaces. UK: Cambridge University Press; 1968.27 Faloutsos C, Equitz W, Flickner M, Niblack W, Perkovic D,Barber R. Efficient and effective querying by image content. J IntellInf Syst 1994;3:23162.28 Bach JR,FullerC, Gupta A,HampapurA,HorowitzB, HumphreyR,Jain R, Shu C. Virage image search engine: an open framework forimage management Proceedings of the SPIE Storage and Retrievalfor Image and Video Databases, vol. 2670 1996 p. 7687.29 Hu MK. Visual pattern recognition by moment invariants. IRE TransInf Theor 1962;8(2):17987.30 Persoon E, Fu KS. Shape discrimination using Fourier descriptors.IEEE Trans Syst, Man Cybern 1977;7:1709.31 Mokhtarian F, Abbasi S, Kittler J. Efficient and robust retrieval byshapecontentthroughcurvaturescalespace.In:ImageDatabasesandMulti-MediaSearch,ProceedingsoftheFirstInternationalWorkshopIDB-MMS96, Amsterdam, The Netherlands 1996 p. 3542.32 Belongie S, Malik J, Puzicha J. Shape matching and objectrecognition using shape contexts. IEEE Trans Pattern Anal MachIntell 2002;24(4):50922.33 Liu T-L, Geiger D. Approximate tree matching and shape similarity.Proceedings of the Seventh International Conference on ComputerVision 1999 p. 45662.34 Tamura H, Yokoya N. Image database systems: a survey. PatternRecogn 1984;17(1):2943.35 Gudivada VN, Raghavan VV. Content-based image retrievalsystems. Computer 1995;28(9):1822.36 Jain R. Infoscopes: multimedia information systems. In: Furht B,editor. Multimedia systems and techniques. Dordrecht: KluwerAcademic Publishers; 1996. p. 21753.37 Veltkamp RC, Hagedoorn M. State-of-the-art in shape matching. In:Lew M, editor. Principles of visual information retrieval. Berlin:Springer; 2001. p. 87119.38 Veltkamp RC, Tanase M. Content-based image retrieval systems: asurvey. Technical Report UU-CS-2000-34. Netherlands: UtrechtUniversity; 2000.39 Special Issue on Digital Libraries. IEEE Trans Pattern Anal MachIntell. 1996:18(8).40 Chung Y, Kusiak A. Grouping parts with a neural network. SMEJ Manuf Syst 1994;13(4):26275.41 Berchtold S, Kriegel HP. S3: similarity search in CAD databasesystems. Proc SIGMOD97 1997;97:5647.42 Smith S, Escobedo R, Anderson M, Caudell T. A deployedengineering design retrieval system using neural networks. IEEETrans Neural Netw 1997;8(4):84751.43 Loncaric S. A survey of shape analysis techniques. Pattern Recogn1998;31(8):9831001.44 Besl PJ, Jain RC. Three-dimensional object recognition. Artif Intell1985;17(1):75145.45 Alt H, Guibas LJ. Discrete geometric shapes: matching, interpolation,and approximation: a survey. Technical Report B 96-11, EVL-1996-142. Berlin: Institute of Computer Science, Freie Universita t; 1996.46 Arman F, Aggarwal JK. Model-based object recognition in dense-range imagesa review. ACM Comput Surv 1993;25(1):543.47 Marr D, Nishihara HK. Representation and Recognition of theSpatial Organization of Three-dimensional Shapes. Proc R Soc LondB 1978;200(1140):26994.48 Woodham RJ. Stable representation of shape. In: Pylyshyn Z, editor.Computational processes in human vision. New Jersey: Norwood;1987.49 Binford TO. Survey of model-based image analysis systems. IntJ Robot Res 1982;1(1):1864.50 Brady M. Criteria for representations of shape. In: Beck J, Hope B,Rosenfeld A, editors. Human and machine vision. London:Academic Press; 1983. p. 3984.N. Iyer et al. / Computer-Aided Design 37 (2005) 50953052751 Haralick RM, Mackworth AK, Tanimoto SL. Computer visionupdate.In:Barr A,CohenPR,Feigenbaum EA, editors.Handbook ofartificial intelligence. Addison-Wesley; 1989. p. 51982.52 Mokhtarian F, Mackworth AK. A theory of multiscale curvature-based shape representation for planar curves. IEEE Trans PatternAnal Mach Intell 1992;14(8):789805.53 Zhang C, Chen T. Efficient feature extraction for 2D/3D objects inmesh representation IEEE International Conference on ImageProcessing (ICIP 2001), Thessaloniki, Greece 2001.54 Sadjadi FA, Hall EL. Three-dimensional moment invariants. IEEETrans Pattern Anal Mach Intell 1980;2(2):12736.55 Khotanzad A, Hong YH. Invariant image recognition by Zernikemoments. IEEE Trans Pattern Anal Mach Intell 1990;12(5):48997.56 Duda RM, Hart PE. Pattern classification and scene analysis. NewYork: Wiley; 1973.57 /58 Kyprianou L. Shape classification in computer-aided design. PhDdissertation. UK: Cambridge University; 1980.59 Regli WC. A survey of automated feature recognition techniques.Technical Report, SRC-TR92-18. The Institute for SystemsResearch, University of Maryland and Harvard University; 1992.60 Henderson MR, Srinath G, Stage R, Walker K, Regli W. Boundaryrepresentation-based feature identification. In: Shah J, editor.Advances in feature based manufacturing. Amsterdam: ElsevierNorth Holland Publishers; 1993.61 Joshi S, Chang T-C. Graph-based heuristics for recognition ofmachined features from a 3D solid model. Comput-Aided Des 1988;20(2):5866.62 Prabhakar S. An experiment on the use of neural nets in form featurerecognition.MSThesis.Tempe, AZ: Arizona StateUniversity;1990.63 Cvetkovic D, Doob M, Sachs H. Spectra of graphs. New York:Academic Press; 1979.64 Chung FR. Spectral graph theory: American Mathematical Society;1997.65 McWherter D, Regli WC. An approach to indexing databases ofsolid models. Technical Report DU-MCS-01-02. Philadelphia, PA:Drexel University; 2001.66 Reeb G. Sur les Points Singuliers dune Forme de Pfaff Complete-ment Integrable ou dune Fonction Numerique (On the singularpoints of a completely integrable Pfaff form or of a numericalfunction). Comptes Randus Acad Sci Paris 1946;222:8479.67 Hilaga M, Shinagawa Y, Kohmura T, Kunii TL. Topology matchingfor fully automatic similarity estimation of 3D shapes. In:SIGGRAPH.: ACM Press; 2001 p. 20312.68 Blum H. A transformation for extracting new descriptors of shape.In: Dunn E, editor. Models for the perception of speech and visualform, Cambridge, MA, 1967. p. 36280.69 Borgefors G. Distance transformations in arbitrary dimensions.Comput Vis, Graph, Image Process 1984;27:32145.70 Lam L, Lee SW, Suen CY. Thinning methodologies: a comprehen-sive survey. IEEE Trans Pattern Anal Mach Intell 1992;14(9):86985.71 Ogniewicz RL, Kubler O. Hierarchical voronoi skeletons. PatternRecogn 1995;28(3):34359.72 Sanniti di Baja G, SvenssonS. A new shape descriptorfor surfaces in3D images. Pattern Recogn Lett 2002;23(6):70311.73 Berchtold S, Keim DA, Kriegel H-P. Section Coding: Ein Verfahrenzur Ahnlichkeitssuche in CAD-Datenbanken (Section Coding: aTechnique for Similarity Search in CAD Databases) In: Proceedings7 GI-Fachtagung Datenbanksysteme in Bu ro, Technik und Wis-senschaft, Ulm Germany 1997 p. 15271.74 Ankerst M, Kastenmu ller G, Kriegel H-P, Seidl T. 3D shapehistograms for similarity search and classification in spatialdatabases. Lecture Notes in Computer Science, vol. 1651. Berlin:Springer; 1999 p. 20726.75 Osada R, Funkhouser T, Chazelle B, Dobkin D. Shape distributions.ACM Trans Graph 2002;21(4):80732.76 Opitz H. A classification to describe workpieces. Oxford, UK:Pergamon Press; 1970.77 Wasserman PD. Neural computing: theory and practice. Reinhold,NY: Van Nostrand; 1989.78 Koenderink JJ, van Doorn AJ. The singularities of the visualmapping. Biol Cybern 1976;24(1):519.79 Koenderink JJ, van Doorn AJ. The internal representation of solidshape with respect to vision. Biol Cybern 1979;32(4):2116.80 Cyr CM, Kimia BB. 3D object recognition using shape similarity-based aspect graph 3D. In: Proc. Inter. Conf. Comp. Vis. 2001p. 25461.81 Horn BKP. Extended Gaussian images. Proc IEEE 1984;72(12):167186.82 Solina F, Bajcsy R. Recovery of parametric models from rangeimages: the case for superquadrics with global deformations. IEEETrans Pattern Anal Mach Intell 1990;12(2):13147.83 Johnson A, Hebert M. Using spin images for efficient multiple modelrecognition in cluttered 3D scenes. IEEE Trans Pattern Anal MachIntell 1999;21:43349.84 Ruiz-Correa S, Shapiro L, Meila M. A new signature based methodfor efficient 3D object recognition. Proceedings of Computer Visionand Pattern Recognition, SC 2000.85 Lamdam Y, Wolfson HJ. Geometric hashing: a general and efficientmodel based recognition scheme. Proceedings of InternationalConference on Computer Vision, Tampa, FL 1988;23849.86 Campbell R, Flynn P. A survey of free-form object representationand recognition techniques. Comput Vis Image Understand 2001;81(2):166210.87 Cybenko G, Bhasin A, Cohen K. Pattern recognition of 3D CADobjects. Smart Eng Syst Des 1997;1:113.88 Elad M, Tal A, Ar S. Content based retrieval of VRML objectsaniterative and interactive approach. Eurographics Multimedia Work-shop 2001 p. 97108.89 Rea H, Corney J, Clark D, Pritchard J, Breaks M, MacLeod R. Partsourcing in a global market. Proceedings of ICeCE01. Beijing:China Machine Press; 2001.90 Corney J, Rea H, Clark J, Pritchard J, Breaks M, MacLeod R. Coarsefilters for shape matching. IEEE Comput Graph Appl 2002;22(3):6574.91 Paquet E, Robinette KM, Rioux M. Management of three-dimensional and anthropometric databases: Alexandria and Cleopa-tra. J Electron Imaging 2000;9:42131.92 Zhang C, Chen T. An active learning framework for content-basedinformation retrieval. IEEE Trans Multimedia, Spec Issue Multi-media Databases 2002;4(2):2608.93 NovotniM, KleinR. Ageometric approachto 3D objectcomparison.In: Proceedings of the International Conference on Shape Modelingand Applications 2001 p. 16775.94 Ohbuchi R, Otagiri T, Ibato M, Takei T. Shape-similarity search ofthree-dimensional models using parameterized statistics. Proceed-ings of Pacific Graphics, Beijing, China 2002;26574.95 Chakraborty T, Venkataraman S, Sohoni M. A fast 3D shape searchtechnique for 3D CAx/PDM repositories. Proceedings of theInternational Symposium on Product Lifecycle Management,Bangalore, India 2003.96 Vranic D, Saupe D, Richter J. Tools for 3D object retrieval:KarhunenLoeve transform and spherical harmonics. Proceedings ofthe IEEE 2001 Workshop on Multimedia Signal Processing 2001;2001:2938.97 Saupe D, Vranic D. 3D model retrieval with spherical harmonics andmoments. In: Radig B, Florczyk S, editors. Proceedings of theDAGM 2001, Munich, Germany, 2001. p. 3927.98 Tanaka K, Sano M, Mukawa N, Kaneko H. 3D object representationusing spherical harmonic functions. In: Proceedings of the IEEE/RSJInternational Conference on Intelligent Robots and Systems,Yokohama, Japan 1993 p. 1873880.N. Iyer et al. / Computer-Aided Design 37 (2005) 50953052899 Kazhdan M, Funkhouser T. Harmonic 3D shape matchingSIGGRAPH 2002 Technical Sketches 2002 p. 191.100 Kazhdan M, Funkhouser T, Rusinkiewicz S. Rotation invariantspherical harmonic representation of 3D shape descriptors. In:Proceedings of the ACM/Eurographics Symposium on GeometryProcessing 2003 p. 16775.101 Ohbuchi R, Nakazawa M, Takei T. Retrieving 3D shapes based ontheir appearance. Proceedings of the Fifth ACM SIGMM Workshopon Multimedia Information Retrieval (MIR 2003), Berkeley, CA;2003 p. 3946.102 Ramesh M, Yip-Hoi D, Dutta D. Feature based shape similaritymeasurement for mechanical parts. ASME J Comput Inf Sci 2001;1(3):24556.103 Cicirello V, Regli WC. Machining feature-based comparisons ofmechanical parts. ACM International Conference on Shape Model-ing and Applications, Genova, Italy 2001;17685.104 Cicirello V. Intelligent retrieval of solid models. MS Thesis.Philadelphia, PA: Drexel University; 1999.105 Cicirello V, Regli WC. Resolving non-uniqueness in design featurehistories. In: Anderson D, Bronsvoort W, editors. In: Proceedings ofthe Fifth ACM Symposium on Solid Modeling and Applications,New York, NY.106 Cardone A, Gupta SK, Karnik M. A survey of shape similarityassessment algorithms for product design and manufacturingapplications. ASME J Comput Inf Sci Eng 2003;3(2):10918.107 Elinson A, Nau D, Regli WC. Feature-based similarity assessment ofsolid models. In: Proceedings of the Fourth ACM/SIGGRAPHSymposium on Solid Modeling and Applications, Atlanta 1997p. 297310.108 Ascher M, Marefat M, Fasse E. A methodology for automaticretrieval of similarly shaped machinable components. IEEE Int ConfSyst, Man, Cybern 2001;2:28405.109 Sun TL. Shape similarity assessment of polyhedral parts based onboundary models. Int J Prod Res 2000;38(18):465570.110 El-Mehalawi M, Miller R. A database system of mechanicalcomponents based on geometric and topological similarity. Part I:representation. Comput-Aided Des 2003;35:8394.111 El-Mehalawi M, Miller R. A database system of mechanicalcomponents based on geometric and topological similarity. Part II:indexing, retrieval, matching, and similarity assessment. Comput-Aided Des 2003;35:95105.112 McWherterD,PeabodyM,Regli WC,Shoukofandeh A.Solidmodeldatabases: techniques and empirical results. ASME J Comput Inf SciEng 2001;1(4):30010.113 Sun T-L, Su C-J, Mayer RJ, Wysk RA. Shape similarity assessmentof mechanical parts based on solid models. In: Gadh R, editor.ASME Design for Manufacturing Conference, Symposium onComputer Integrated Concurrent Design, , ASME, Boston, MA,September 1721, 1995. p. 95362.114 Peabody M, Regli WC. Clustering techniques for databases of CADmodels. Technical Report DU-MCS-01-0, Philadelphia, PA: Depart-ment of Mathematical and Computer Science, Drexel University;2001.115 McWherter D, Peabody M, Regli WC, Shoukofandeh A. Anapproach to indexing databases of graphs. Technical Report DU-MCS-01-01, Philadelphia, PA: Department of Mathematical andComputer Science, Drexel University; June 2001.116 McWherter D, Peabody M, Regli WC, Shoukofandeh A. Trans-formation invariant shape similarity comparison of solid models.ASME DETC, Computers and Information in Engineering Con-ference, September 912, Pittsburgh, PA 2001.117 Chen D-Y, Ouhyoung M. A 3D Object Retrieval System Based onMulti-Resolution Reeb Graph Proceedings of Computer GraphicsWorkshop, Taiwan, Taiwan, June 2002 p. 16.118 Bespalov D, Regli WC, Shokoufandeh A. Reeb graph-based shaperetrieval for CAD. Proceedings of the ASME DETC 03 ComputersandInformationinEngineering(CIE)Conference,Chicago,IL2003.119 Sundar H, Silver D, Gagvani N, Dickinson S. Skeleton based shapematching and retrieval. In: Proceedings of Shape Modeling andApplica