A survey of shape similarity assessment algorithms for product design and manufacturing applications
---
paper_title: Shape contexts enable efficient retrieval of similar shapes

paper_content:

In this paper we demonstrate that a recently introduced shape descriptor, the "shape context", can be used to quickly prune a search for similar shapes. Our representation for a shape is a discrete set of n points sampled from its internal and external contours. For each of these points, the shape context is a histogram of the relative positions of the n - 1 remaining points. We present two methods for rapid shape retrieval: one that does comparisons based on a small number of shape contexts and another that uses vector quantization in the space of shape contexts. We verify the discriminative power of these methods with tests on the Columbia (COIL-100) 3D object database and the Snodgrass and Vanderwart line drawings. The shape context-based methods are shown to quickly produce an accurate shortlist of candidates suitable for a more exact matching engine in spite of pose variation and occlusion.
---
paper_title: Shape matching: similarity measures and algorithms

paper_content:

Shape matching is an important ingredient in shape retrieval, recognition and classification, alignment and registration, and approximation and simplification. This paper treats various aspects that are needed to solve shape matching problems: choosing the precise problem, selecting the properties of the similarity measure that are needed for the problem, choosing the specific similarity measure, and constructing the algorithm to compute the similarity. The focus is on methods that lie close to the field of computational geometry.
---
paper_title: A metric for distributions with applications to image databases

paper_content:

We introduce a new distance between two distributions that we call the Earth Mover's Distance (EMD), which reflects the minimal amount of work that must be performed to transform one distribution into the other by moving "distribution mass" around. This is a special case of the transportation problem from linear optimization, for which efficient algorithms are available. The EMD also allows for partial matching. When used to compare distributions that have the same overall mass, the EMD is a true metric, and has easy-to-compute lower bounds. In this paper we focus on applications to image databases, especially color and texture. We use the EMD to exhibit the structure of color-distribution and texture spaces by means of Multi-Dimensional Scaling displays. We also propose a novel approach to the problem of navigating through a collection of color images, which leads to a new paradigm for image database search.
---
paper_title: Automated design of sheet metal punches for bending multiple parts in a single setup

paper_content:

Sheet metal bending is a process in which bends are formed using a combination of a punch and a die. A very large number of mechanical products such as furniture panels, shelves, cabinets, housing for electro-mechanical devices, etc. are created by using the sheet metal bending process. Bending tools need to satisfy the following two criteria: (1) tools should be able to withstand bending forces, and (2) tool shapes should be such that there is no tool-part interference. In this paper, we describe a methodology for automatically designing shapes of bending punches for bending multiple parts in a single setup. We create parametric geometric models of punches. These parametric models describe the family of possible punch shapes. Using the part geometry and parametric punch shape models, we automatically generated constraints on tool parameters that eliminate the possibility of part-tool interference. We use mixed-integer techniques to identify parameters of punch shapes that result in the maximum punch strength. Finally, we perform strength analysis of the designed punch shape using "nite element analysis methods, to verify that the designed punch shape is capable of withstanding the bending forces. 2001 Elsevier Science Ltd. All rights reserved.
---
paper_title: Sheet Metal Bending: Generating Shared Setups

paper_content:

Contemporary process planners for sheet metal bending solve the process planning problem for individual parts. Quite often, many different parts can be produced on shared setups. However, plans generated by current process planning systems fail to exploit this commonality between setups and try to generate optimal setups for individual parts. In this paper, we present an algorithm for multi-part setup planning for sheet metal bending. This algorithm takes a set of parts and operation sequences for these parts, and tries to find a shared setup plan that can work for every part in the set. Setup changes constitute a major portion of the production time in batch production environments. Therefore, multi-part setup planning techniques can be used to significantly cut down the total number of setups and increase the overall through-put.
---
paper_title: Efficient geometry-based similarity search of 3D spatial databases

paper_content:

Searching a database of 3D-volume objects for objects which are similar to a given 3D search object is an important problem which arises in number of database applications — for example, in Medicine and CAD. In this paper, we present a new geometry-based solution to the problem of searching for similar 3D-volume objects. The problem is motivated from a real application in the medical domain where volume similarity is used as a basis for surgery decisions. Our solution for an efficient similarity search on large databases of 3D volume objects is based on a new geometric index structure. The basic idea of our new approach is to use the concept of hierarchical approximations of the 3D objects to speed up the search process. We formally show the correctness of our new approach and introduce two instantiations of our general idea, which are based on cuboid and octree approximations. We finally provide a performance evaluation of our new index structure revealing significant performance improvements over existing approaches.
---
paper_title: Model-based object recognition in dense-range images—a review

paper_content:

The goal in computer vision systems is to analyze data collected from the environment and derive an interpretation to complete a specified task. Vision system tasks may be divided into data acquisition, low-level processing, representation, model construction, and matching subtasks. This paper presents a comprehensive survey of model-based vision systems using dense-range images. A comprehensive survey of the recent publications in each subtask pertaining to dense-range image object recognition is presented.
---
paper_title: Application of affine-invariant fourier descriptors to recognition of 3-d objects

paper_content:

The method of Fourier descriptors is extended to produce a set of normalized coefficients which are invariant under any affine transformation (translation, rotation, scaling, and shearing). The method is based on a parameterized boundary description which is transformed to the Fourier domain and normalized there to eliminate dependencies on the affine transformation and on the starting point. Invariance to affine transforms allows considerable robustness when applied to images of objects which rotate in all three dimensions, as is demonstrated by processing silhouettes of aircraft maneuvering in three-space. >
---
paper_title: An analysis technique for biological shape. I

paper_content:

An analysis technique for biological shape based on the concept of bending energy has been developed. The technique permits the calculation of the amount of energy (work) that would have to be expended to form typical biological shapes out of a linear, thin-shelled medium. In addition the development of this analysis procedure provides several new results concerning image processing including a sampling theorem for simply connected closed contours and a fast algorithm for calculation of the bending energy.
---
paper_title: An efficiently computable metric for comparing polygonal shapes

paper_content:

A method for comparing polygons that is a metric, invariant under translation, rotation, and change of scale, reasonably easy to compute, and intuitive is presented. The method is based on the L/sub 2/ distance between the turning functions of the two polygons. It works for both convex and nonconvex polygons and runs in time O(mn log mn), where m is the number of vertices in one polygon and n is the number of vertices in the other. Some examples showing that the method produces answers that are intuitively reasonable are presented. >
---
paper_title: A Survey of Shape Analysis Techniques

paper_content:

Abstract This paper provides a review of shape analysis methods. Shape analysis methods play an important role in systems for object recognition, matching, registration, and analysis. Research in shape analysis has been motivated, in part, by studies of human visual form perception systems. Several theories of visual form perception are briefly mentioned. Shape analysis methods are classified into several groups. Classification is determined according to the use of shape boundary or interior, and according to the type of result. An overview of the most representative methods is presented.
---
paper_title: Contour shape description based on an arch height function

paper_content:

Abstract A new method to extract contour features is proposed. For any contour C , a function, which we call Arch Height Function (AHF), is defined for each point and its value on C is computed. The set of AHF values is then used as a description of the shape of C . In particular, its local maxima, if they exist, correspond precisely to the cornerpoints of C . Besides, the method is computationally efficient as compared with the existing techniques of the contour feature extraction. The new method provides an effective and reliable tool for contour description, especially for angle detection. Some experimental results that demonstrate the adaptability and reliability of the AHF method are presented.
---
paper_title: Geometric Pattern Matching under Euclidean Motion

paper_content:

Abstract Given two planar sets A and B, we examine the problem of determining the smallest ϵ such that there is a Euclidean motion (rotation and translation) of A that brings each member of A within distance ϵ of some member of B. We establish upper bounds on the combinatorial complexity of this subproblem in model-based computer vision, when the sets A and B contain points, line segments, or (filled-in) polygons. We also show how to use our methods to substantially improve on existing algorithms for finding the minimum Hausdorff distance under Euclidean motion.
---
paper_title: Shock graphs and shape matching

paper_content:

We have been developing a theory for the generic representation of 2-D shape, where structural descriptions are derived from the shocks (singularities) of a curve evolution process, acting on bounding contours. We now apply the theory to the problem of shape matching. The shocks are organized into a directed, acyclic shock graph, and complexity is managed by attending to the most significant (central) shape components first. The space of all such graphs is highly structured and can be characterized by the rules of a shock graph grammar. The grammar permits a reduction of a shockgraph to a unique rooted shock tree. We introduce a novel tree matching algorithm which finds the best set of corresponding nodes between two shock trees in polynomial time. Using a diverse database of shapes, we demonstrate our system's performance under articulation, occlusion, and changes in viewpoint.
---
paper_title: Feature-based similarity assessment of solid models

paper_content:

This paper presents our initial efforts to develop a systematic approach for assessing the similarity of solid models based on how they will be manufactured. The goal of this work is to develop methods that, given a solid model representing the design of a new product, query a product information database (of solid models, associated manufacturing plans, and related attributes) and identify existing designs with manufacturing plans similar to some reasonable plan for the new design—or useful as a starting point for creation of a new plan for the new design. Our approach is based on the automatic generation (from CAD models) of graph structures that contain manufacturing information (in the form of manufacturing features). We are developing ways to measure similarity among these graph structures, so that given the graph structures corresponding to two different designs, we can tell how similar or different they are. The similarity measure will be used as a basis for indexing and retrieving similar designs from databases. An implementation of our approach is discussed. We believe our work is a first step in producing computergeneratable and computer-interpretable similarity assessment techniques that will be useful for applications such as variThis work is supported in part by NSF grants NSF EEC 94-02384, IRI9306580, and DDM-9201779, by ARPA grant DABT63-95-C-0037 and ONR grant DABT63-95-C-0037, and by in-kind contributions from Spatial Technologies and Bentley Systems. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the funders. Current position: Visiting Research Engineer, Engineering Design Research Center, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15213-3980 ant and hybrid variant/generative process planning systems, indexing schemes for large part inventories, access methods for “smart catalogs,” and for performing component searches through product catalogs and on the Internet.
---
paper_title: Retrieval of similarly shaped parts from a CAD database

paper_content:

The increased use of Computer Aided Design (CAD) tools have resulted in the obvious need to efficiently retrieve specific and groups of similar parts from CAD databases for group technology (GT) applications; Current classification and retrieval methods from CAD databases are typically code based. The disadvantage of such a retrieval scheme is application dependency. We propose an application independent scheme and utilize it in retrieving similarly shaped parts on the basis of form-features and the inter-feature relationships. We address the issues of completeness of spatial interactions vocabulary and multiple interpretations for a part.
---
paper_title: Machining feature-based comparisons of mechanical parts

paper_content:

Solid models are the critical data elements in modern computer-aided design (CAD) environments, describing the shape and form of manufactured artifacts. Their growing ubiquity has created new problems in how to effectively manage the many models that are now stored in the digital libraries of large design and manufacturing enterprises. Existing techniques from the engineering literature and from industrial practice, such as group technology, rely on human-supervised encoding and classification, while techniques from the multimedia database and computer graphics/vision communities often ignore the manufacturing attributes most significant in the classification of models. This paper presents our approach to the manufacturing similarly assessment of solid models of mechanical parts based on machining features. Our technical approach is three-fold: (1) perform machining feature extraction to map the solid model to a set of STEP AP 224 machining features; (2) construct a model dependency graph from the set of machining features; and (3) find the nearest neighbors to the query graph using an iterative improvement search across a database of other models. We also present empirical experiments to validate our approach using our testbed, the National Design Repository ( ). The contribution of this research is the first fully automated technique for machining feature-based comparisons of mechanical artifacts. We believe that this work can lead to radical changes in the way in which design data is managed in modern engineering enterprises.
---
paper_title: On 3D shape similarity

paper_content:

This paper addresses the problem of 3D shape similarity between closed surfaces. A curved or polyhedral 3D object of genus zero is represented by a mesh that has nearly uniform distribution with known connectivity among mesh nodes. A shape similarity metric is defined based on the L/sub 2/ distance between the local curvature distributions over the mesh representations of the two objects. For both convex and concave objects, the shape metric can be computed in time O(n/sup 2/), where n is the number of tessellations of the sphere or the number of meshes which approximate the surface. Experiments show that our method produces good shape similarity measurements.
---
paper_title: Identification of Partially Obscured Objects in Two and Three Dimensions by Matching Noisy Characteristic Curves

paper_content:

In this paper we analyze the problem of matching partially obscured, noise-corrupted images of composite scenes in two and three dimensions. We describe efficient methods for smoothing the noisy data and for matching portions of the observed object boundaries (or of characteristic curves lying on bounding surfaces of 3-D objects) to prestored models. We also report initial experiments showing the efficacy of this procedure.
---
paper_title: Computing the minimum Hausdorff distance for point sets under translation

paper_content:

@ 2 . The results for the one-dimensional case are applied to the problem of comparing polygons under general affine transformations, where we extend the recent results of Arkin et al on polygon resemblance under rigid body motion. The two-dimensional case is closely related to the problem of finding an approximate congruence between two points sets under translation in the plane, as considered by Alt et al.
---
paper_title: A unified computational framework for Minkowski operations

paper_content:

Abstract In this paper we present a complete computational theory of Minkowski addition and Minkowski decomposition of boundary-represented objects. The theory can be summarized as a unified algorithm to compute Minkowski operations of 2D and 3D continuous objects. We unify the two Minkowski operations as a single operation by introducing the notion of negative shape; in contrast to that, the shapes of ordinary objects may be considered positive. More interestingly, the concept of negative shape makes possible further unification since exactly the same computational technique works for convex as well as nonconvex objects. This happens because conceptually a convex object can be viewed as a pure object—either completely positive or completely negative, while a nonconvex object is like a mixture of positive and negative ones. To make the unified algorithm conceptually simpler and computationally more efficient, we devise a new representation scheme, called the slope diagram representation, to represent the input polygons and polyhedra. The slope diagram representation also allows us to provide a nice geometric interpretation of negative shape. Finally, we take up various special cases to show how the unified algorithm can be quickly simplified when the input objects are endowed with more structure (such as, the objects are all convex, or, the boundaries of the objects can be expressed as smooth analytic functions, etc.).
---
paper_title: Similarity Measures for Convex Polyhedra Based on Minkowski Addition

paper_content:

Abstract In this paper we introduce and investigate similarity measures for convex polyhedra based on Minkowski addition and inequalities for the mixed volume and volume related to the Brunn–Minkowski theory. All measures considered are invariant under translations; furthermore, some of them are also invariant under subgroups of the affine transformation group. For the case of rotation and scale invariance, we prove that to obtain the measures based on (mixed) volume, it is sufficient to compute certain functionals only for a finite number of critical rotations. The paper presents a theoretical framework for comparing convex shapes and contains a complexity analysis of the solution. Numerical implementations of the proposed approach are not discussed.
---
paper_title: Mathematical morphological operations of boundary-represented geometric objects

paper_content:

The resemblance between the integer number system with multiplication and division and the system of convex objects with Minkowski addition and decomposition is really striking. The resemblance also indicates a computational technique which unifies the two Minkowski operations as a single operation. To view multiplication and division as a single operation, it became necessary to extend the integer number system to the rational number system. The unification of the two Minkowski operations also requires that the ordinary convex object domain must be appended by a notion of inverse objects or negative objects. More interestingly, the concept of negative objects permits further unification. A nonconvex object may be viewed as a mixture of ordinary convex object and negative object, and thereby, makes it possible to adopt exactly the same computational technique for convex as well as nonconvex objects. The unified technique, we show, can be easily understood and implemented if the input polygons and polyhedra are represented by their slope diagram representations.
---
paper_title: Matching 3D models with shape distributions

paper_content:

Measuring the similarity between 3D shapes is a fundamental problem, with applications in computer vision, molecular biology, computer graphics, and a variety of other fields. A challenging aspect of this problem is to find a suitable shape signature that can be constructed and compared quickly, while still discriminating between similar and dissimilar shapes. In this paper, we propose and analyze a method for computing shape signatures for arbitrary (possibly degenerate) 3D polygonal models. The key idea is to represent the signature of an object as a shape distribution sampled from a shape function measuring the global geometric properties of an object. The primary motivation for this approach is to reduce the shape matching problem to the comparison of probability distributions, which is simpler than traditional shape matching methods that require pose registration, feature correspondence or model fitting. We find that the dissimilarities between sampled distributions of simple shape functions (e.g. the distance between two random points on a surface) provide a robust method for discriminating between classes of objects (e.g. cars versus airplanes) in a moderately sized database, despite the presence of arbitrary translations, rotations, scales, reflections, tessellations, simplifications and model degeneracies. They can be evaluated quickly, and thus the proposed method could be applied as a pre-classifier in an object recognition system or in an interactive content-based retrieval application.
---
paper_title: A metric for distributions with applications to image databases

paper_content:

We introduce a new distance between two distributions that we call the Earth Mover's Distance (EMD), which reflects the minimal amount of work that must be performed to transform one distribution into the other by moving "distribution mass" around. This is a special case of the transportation problem from linear optimization, for which efficient algorithms are available. The EMD also allows for partial matching. When used to compare distributions that have the same overall mass, the EMD is a true metric, and has easy-to-compute lower bounds. In this paper we focus on applications to image databases, especially color and texture. We use the EMD to exhibit the structure of color-distribution and texture spaces by means of Multi-Dimensional Scaling displays. We also propose a novel approach to the problem of navigating through a collection of color images, which leads to a new paradigm for image database search.
---
paper_title: Using shape distributions to compare solid models

paper_content:

Our recent work has described how to use feature and topology in-formation to compare 3-D solid models. In this work we describe a new method to compare solid models based on shape distributions. Shape distribution functions are common in the computer graphics and computer vision communities. The typical use of shape dis-tributions is to compare 2-D objects, such as those obtained from imaging devices (cameras and other computer vision equipment). Recent work has applied shape distribution metrics for compari-son of approximate models found in the graphics community, such as polygonal meshes, faceted representation, and Virtual Reality Modeling Language (VRML) models. This paper examines how to adapt these techniques to comparison of 3-D solid models, such as those produced by commercial CAD systems. We provide a brief review of shape matching with distribution functions and present an approach to matching solid models. First, we show how to ex-tend basic distribution-based techniques to handle CAD data that has been exported to VRML format. These extensions address specific geometries that occur in mechanical CAD data. Second, we describe how to use shape distributions to directly interrogate solid models. Lastly, we show how these techniques can be put together to provide a "query by example" interface to a large, het-erogeneous, CAD database: The National Design Repository. One significant contribution of our work is the systematic technique for performing consistent, engineering content-based comparisons of CAD models produced by different CAD systems.
---
paper_title: Pattern classification using neural networks

paper_content:

The author extends a previous review and focuses on feed-forward neural-net classifiers for static patterns with continuous-valued inputs. He provides a taxonomy of neural-net classifiers, examining probabilistic, hyperplane, kernel, and exemplar classifiers. He then discusses back-propagation and decision-tree classifiers; matching classifier complexity to training data; GMDH (generalized method of data handling) networks and high-order nets; K nearest-neighbor classifiers; the feature-map classifier; the learning vector quantizer; hypersphere classifiers; and radial-basis function classifiers. >
---
paper_title: A neural network system for shape-based classification and coding of rotational parts

paper_content:

The classification and coding of parts for group technology applications continue to be labour intensive and time-consuming processes. In this paper a pattern recognition approach utilizing neural networks is presented for the automation of some elements of this critical activity. As an illustrative example, a neural network system is used to generate part geometry-related digits of the Opitz code from bitmaps of part drawings. It is found to generate codes accurately and promises to be a useful tool for the automatic generation of shape-based classes and codes.
---
paper_title: Grouping parts with a neural network

paper_content:

Abstract Recognition of objects is used for identification, classification, verification, and inspection tasks in manufacturing. Neural networks are well suited for this application. In this paper, an application of a back-propagation neural network for the grouping of parts is presented. The back-propagation neural network is provided with binary images describing geometric part shapes, and it generates part families. To decrease the chance of reaching a local optimum and to speed up the computation process, three parameters—bias, momentum, and learning rate—are taken into consideration. The contribution of this paper is in design of a neuro-based system to group parts. The network groups all the training and testing parts into part families with perfect accuracy. Performance of the system has been tested on a benchmark example and then by experimenting with 60 parts.
---
paper_title: Graph-based heuristics for recognition of machined features from a 3D solid model

paper_content:

Abstract The internal representation of the solid modeller provides a description of parts which when used directly is useful for automation of the process planning function. So that the CAD model can be used to provide the information required for manufacturing, techniques to improve machine understanding of the part as required for manufacturing are needed. This paper presents the development of the concept attributed adjacency graph (AAG) for the recognition of machined features from a 3D boundary representation of a solid. Current implementation of the feature recogniser is limited to polyhedral features such as pockets, slots, steps, blind steps, blind slots, and polyhedral holes. Sample results that show the capabilities of the system are presented.
---
paper_title: Database techniques for archival of solid models

paper_content:

This paper presents techniques for managing solid models in modern relational database management systems. Our goal is to enable support for traditional database operations (sorting, distance metrics, range queries, nearest neighbors, etc) on large databases of solid models. As part of this research, we have developed a number of novel storage and retrieval strategies that extend the state-of-the-art in database research as well as change the way in which solid modeling software developers and design and manufacturing enterprises view CAD-centric data management problems. Past research and current commercial systems for engineering information management and Product Data Management (PDM) have predominantly taken annotation and document-based approaches—where the solid modeling data itself is simply stored as a related file to other project documents. Research in CAD and engineering databases has produced great advances, such as representation schemas for STEP-based data elements, however existing technologies stop short of enabling content-based and semantic retrieval of solid modeling data of the types now available for other higher-dimensional media (images, audio and video). Our approach encodes solid model BRep information as a Model Signature Graph. We demonstrate how Model Signature Graphs can be used for topological similarity assessment of solid models and enable clustering for data mining of a large design repositories. We believe this work will begin to bridge the solid modeling and database communities, enabling new paradigms for interrogation of CAD datasets.
---
paper_title: Spectral Graph Theory

paper_content:

Eigenvalues and the Laplacian of a graph Isoperimetric problems Diameters and eigenvalues Paths, flows, and routing Eigenvalues and quasi-randomness Expanders and explicit constructions Eigenvalues of symmetrical graphs Eigenvalues of subgraphs with boundary conditions Harnack inequalities Heat kernels Sobolev inequalities Advanced techniques for random walks on graphs Bibliography Index.
---
paper_title: Level set diagrams of polyhedral objects

paper_content:

Shape descriptors and feature-based representations are of primary interests in the area of solid modeling. They allow us for easier storage, recognition and general treatments of objects. Axial structures such as skeletons are popular shape descriptors which have been widely studied. Most of the studies focus on a particular type of skeleton called the Medial Axis. Medial Axes can be extracted from discrete volumetric data as well as boundary-based representations. In the later case, however, no algorithm is known to perform well and accurately. We propose a new paradigm for constructing one dimensional axial structures associated with a polyhedral object. These structures, called the level set diagrams, are associated with scalar functions defined over the set of vertices of a polyhedron. We study in details the level set diagram associated with the shortest path distance to a source point. This particular association fits nicely into a theoretical framework and presents interesting properties for the purpose of shape description.
---
paper_title: A feature-based approach for smooth surfaces

paper_content:

Feature-based representation has become a topic of interest in shape modeling techniques. Such feature- based techniques are, however, still restricted to polyhedral shapes, and none has been done on smooth sur- faces. This paper presents a new feature-based ap- proach for smooth surfaces. Here, the smooth surfaces are assumed to be 2-dimensional @differentiable manifolds within a theoretical framework. As the shape features, critical points such as peaks, pits, and passes are used. We also use a critical point graph called the R.eeb graph to represent the topological skeletons of a smooth object. Since the critical points have close relations with the entities of B-reps, the framework of thtx B-reps can easily be applied to our approach. In our method, the shape design process begins with specifying the topological skeletons using the Reeb graph. The Reeb graph is edited by pasting the enti- ties called cells that have one-to-one correspondences with the critical points. In addition to the topological skeletons, users also design the geometry of the objects with smooth surfaces by specifying the flow curves that run on the object surface. From these flow curves, the system automatically creates a control network that encloses the object shape. The surfaces are interpolated from the control network by minimizing the allergy function subject to the deformation of the surfaces using variational optimization.
---
paper_title: Topology matching for fully automatic similarity estimation of 3D shapes

paper_content:

There is a growing need to be able to accurately and efficiently search visual data sets, and in particular, 3D shape data sets. This paper proposes a novel technique, called Topology Matching, in which similarity between polyhedral models is quickly, accurately, and automatically calculated by comparing Multiresolutional Reeb Graphs (MRGs). The MRG thus operates well as a search key for 3D shape data sets. In particular, the MRG represents the skeletal and topological structure of a 3D shape at various levels of resolution. The MRG is constructed using a continuous function on the 3D shape, which may preferably be a function of geodesic distance because this function is invariant to translation and rotation and is also robust against changes in connectivities caused by a mesh simplification or subdivision. The similarity calculation between 3D shapes is processed using a coarse-to-fine strategy while preserving the consistency of the graph structures, which results in establishing a correspondence between the parts of objects. The similarity calculation is fast and efficient because it is not necessary to determine the particular pose of a 3D shape, such as a rotation, in advance. Topology Matching is particularly useful for interactively searching for a 3D object because the results of the search fit human intuition well.
---
paper_title: Attributed String Matching with Merging for Shape Recognition

paper_content:

A new structural approach to shape recognition using attributed string matching with merging is proposed. After illustrating the disadvantages of conventional symbolic string matching using changes, deletions, and insertions, attributed strings are suggested for matching. Each attributed string is an ordered sequence of shape boundary primitives, each representing a basic boundary structural unit, line segment, with two types of numerical attributes, length and direction. A new type of primitive edit operation, called merge, is then introduced, which can be used to combine and then match any number of consecutive boundary primitives in one shape with those in another. The resulting attributed string matching with merging approach is shown useful for recognizing distorted shapes. Experimental results prove the feasibility of the proposed approach for general shape recognition. Some possible extensions of the approach are also included.
---

Title: A Survey of Shape Similarity Assessment Algorithms for Product Design and Manufacturing Applications
Section 1: Introduction
Description 1: Introduce the importance and applications of shape similarity assessment in product design and manufacturing, and outline the organization of the paper.

Section 2: Basic Terminology and Background
Description 2: Define basic terms and concepts necessary to understand shape similarity assessment in 3D models, including shape signatures and distance functions.

Section 3: Overview of Techniques
Description 3: Provide a classification and brief overview of various techniques used for shape similarity assessment, divided into different types of shape signatures.

Section 4: Feature-Based Shape Signatures
Description 4: Discuss techniques that use feature-based shape signatures for similarity assessment, highlighting key features and limitations of representative methods.

Section 5: Local Curvature Distributions Over Mesh Representations
Description 5: Describe techniques that utilize local curvature distributions over mesh representations for comparing 3D shapes, including their advantages and limitations.

Section 6: Shape Histogram Based Shape Signatures
Description 6: Explore methods that use shape histograms derived from sampled points on 3D models' surfaces, and evaluate their effectiveness and challenges.

Section 7: Section Images Based Shape Signatures
Description 7: Delve into techniques that create shape signatures based on section images, including the use of neural networks for part classification.

Section 8: Model Signature Graphs
Description 8: Explain the use of Model Signature Graphs for topological comparison of solid models, including the use of spectral graph theory and graph invariance vectors.

Section 9: Multiresolutional Reeb Graphs
Description 9: Discuss the creation and comparison of Multiresolutional Reeb Graphs for assessing shape similarity, covering resolution and function selection.

Section 10: Graphs of Aligned Models
Description 10: Present a technique based on aligning models using Brep model and CSG tree information, focusing on major sweep directions and attributed string matching.

Section 11: Shape Statistics
Description 11: Describe techniques that use global shape metrics such as surface area/volume ratio, compactness, and crinkliness for shape similarity assessment, highlighting their role as filters.

Section 12: Conclusions
Description 12: Summarize the findings of the survey, discuss key learnings, challenges, and suggest directions for future research in shape similarity assessment for product design and manufacturing.