Geometric similarity search - What is it?

Users often wonder what is meant by geometric similarity search, how it works, and where it can be applied. Perhaps we will be able to answer some of these questions here.

What is the geometric similarity search?

There are basically a lot of mathematical papers on this topic with the corresponding scientific theory. At its core, it is ultimately about capturing 3D objects or bodies and extracting features from them that can be used to evaluate a geometric comparison with another 3D object or body. At the end of this paper, some sources and publications on this topic are listed. They give enough starting points to research further if one is interested in the theory and can check out our download free info brochure on this topic.

Basic procedure

These methods for geometric search are referred to as Shape Indexing, Geometric Retrieval, or 3D Content Retrieval. All these methods are based on feature extraction from 3D objects. However, the methods differ in terms of which object types and bodies are to be checked and evaluated with regard to their similarity. Thus, methods for the evaluation of facial shapes, sculptures, and biological form elements differ from methods for the examination of discrete geometric shapes and objects as they are used in the industrial environment.

Prerequisites for the use of the methods are 3D data

A prerequisite for the application of Shape Indexing or the 3D Content Retrieval method to compare bodies or 3D geometries with each other is the existence of a 3D representation of the respective 3D objects in the form of a Boundary Representation Model (B-REP) of a Constructive Solid Geometry (CSG) or triangulated or meshed representations of the surfaces, e.g. as an STL model. Images, scans, or 2D representations do not work for this process at first. They would first have to be converted into a 3D representation.

In industrial practice, these first two object shapes are predominantly generated by CAD systems. This is done by the geometry engine of the CAD software, the geometry kernel, or also modeling kernel of the CAD software. Widely used geometry kernels are e.g. the ACIS kernel from the company Spatial or the PARASOLID kernel from SIEMENS. In addition to these systems, there are a number of other systems, some of which are used in very specific industries. For example, special programs are used in tool and mold making, medical technology, and electrical engineering. Ultimately, these systems also only generate 3D representations of the respective geometric objects. These systems can then exchange model data with each other via well-known interface formats such as STEP, JT, IGS, or ACIS.

The commercially available 3D CAD systems such as Catia, Solid Works, Creo, Inventor, Siemens NX, Solid Edge, etc. generate their models on the basis of the above two modeling kernels.

For use in practice, the Shape Indexing method for geometric similarity search should therefore be able to easily recognize and process these object shapes. Relevant features must then be extracted from these 3D objects to enable a geometric comparison for evaluating and assessing the similarity of the objects.

Requirements for geometric search

The requirements from practice for geometry matching, geometric-part search, shape matching, shape comparison, or 3D search - as it is often also called among users - are diverse. Obviously, each user spectrum has a different requirement profile. The user essentially has the expectation of not having to deal with complex theory and technical matters. They do not want to have to make complicated parameter settings. In this respect, the software must be easy to use in practical applications. When processing geometry data from the aforementioned formats, the system should be robust, i.e. not susceptible to interference, and process the original data quickly. The latter is a relative variable and again depends on the hardware parameters. Here, too, the desire is to get by with conventional standard hardware.

Another very important requirement is that the geometry comparison or shape comparison must be invariant to rotation, coordinates, and symmetry. This means that the objects to be compared may be positioned completely independently of each other at different coordinates in space and rotated relative to each other. Their position and rotation in space must not influence the result of the geometry comparison. Even if they are mirror-symmetrical parts (right-left parts), they must be recognized as similar to each other.

Here is an example from the Cost calculation: It happens very often that a user receives, for example, a Catia model of the right side of a part or a ZSB in a customer inquiry, and similar left-hand parts or ZSBs from the left side exist in the old inquiry inventory. Only via this capability of mirror-symmetrical invariance can right-left parts be easily compared and evaluated.

Another example from vehicle supply practice: In vehicle development, parts and components are always designed and laid out in vehicle coordinates. A manufacturer of production tools swivels these parts and components into tool position in his design and then continues working with them. Thus, a coordinate transformation from vehicle coordinates to tool coordinates has taken place. If a toolmaker now wants to compare similar objects with each other, the position of the parts and components in space should not play a role. This is achieved via the coordinate and rotation invariance.

The required target quantities for determining a similarity value are calculated by a weighted measure of several multi-dimensional vectors. The special feature of this method is that, in addition to the holistic identification of similar objects (components or assemblies), similar geometric segments or subdomains can also be recognized from the 3D objects. This is also called subdomain search or subdomain retrieval in the literature.

In this way, any areas of a geometry can be marked using this procedure, which can then be found again in other - even non-specified - components or assemblies.

The shape indexing or 3D content retrieval method used here is also capable of classifying or clustering 3D objects. This can be fully automated or "learned" by means of reference parts. In this way, a large number of 3D objects can be ordered and structured. The automatic clustering or classification is done based on the specific geometric features from the above-mentioned Shape Indexing procedure for geometric search and geometric similarity search. For clustering, e.g. and optimized and adapted forms of the k-means algorithm can be used. These used methods are characterized by a short response time compared to other methods like e.g. Nearest-Neighbor-Heuristic, Support Vector Machines, and artificial neural networks.

Conclusion

The geometric search, CAD part search, or geometric similarity search is a robust and very powerful method to quickly and easily find suitable parts and assemblies for reuse in large heterogeneous databases in industrial practice. The areas of application range from technical cost calculation in sales, design, and development to standardization and norming, mechanical machining CAM, quality assurance QA, work preparation, and equipment design to purchasing and procurement. It increases efficiency in practice in a very effective way. In conjunction with other methods such as clustering, automatic shape matching can be used for the clustering and automatic classification of CAD data.

You are welcome to experience the geometric similarity search live:

or download our free info brochure here:

Weblinks

• 3D-Contant Retrieval (https://en.wikipedia.org/wiki/3D_Content_Retrieval)
• Similarity of geometric figures (https://www.tutoria.de/wiki/mathematik/2776/aehnlichkeit-zwischen-geometrischen-figuren)
• Informatics - University of Konstanz (https://kops.uni-konstanz.de/handle/123456789/5814)
• Informatics - Free University of Berlin (http://www.inf.fu-berlin.de/users/alt/dfgAl253.html)
• Informatics – University of Princeton (http://gfx.cs.princeton.edu/proj/shape/)
• Community – Computer Vision Foundation (http://www.cv-foundation.org)
• Clusteranalysis (https://de.wikipedia.org/wiki/Clusteranalyse)
• Next-Neighbor Heuristic (https://de.wikipedia.org/wiki/Nearest-Neighbor-Heuristik)
• k-Means method for clustering data (https://de.wikipedia.org/wiki/K-Means-Algorithmus)
• Support Vector Machin as a classification method (https://de.wikipedia.org/wiki/Support_Vector_Machine)

Individual references

Petrakis E., Faloutsos C.: ‘Similarity Searching in Large Image DataBases’, Technical Report CS-TR-3388, University of Maryland, 1994.

Mehrotra R., Gary J. E.: ‘Feature-Index-Based Similar Shape retrieval’, Proc. Of the 3rd Working Conf. on Visual Database Systems, March 1995.

Mehrotra R., Gary J. E.: ‘Feature-Based Retrieval of Similar Shapes’, Proc. 9th Int. Conf. on Data Engineering, Vienna, Austria, 1993, pp. 108-115.

Jagadish H. V.:‘A Retrieval Technique for Similar Shapes’, Proc. ACM SIGMOD Int. Conf. on Management of Data, 1991, pp. 208-217.

Helmer-Citterich M., Tramontano A.: ‘PUZZLE: A New Method for Automated Protein Docking Based on Surface Shape Complementarity’, Journal of Molecular Biology, Vol. 235, pp.1021-1031, 1994.

Alt H., Mehlhorn K., Wagener H., Welzl E.: ‘Congruence, Similarity, and Symmetries of geometric Objects’, Discrete Computational Geometry 3, 1988, pp. 237-256.

Patents:

Patent 10 2007 039 337 B3 (http://google.com/patents/DE102007039337B3?hl=de&cl=fi)

Patent EP 2188747A1

(http://google.com/patents/EP2188747A1?cl=fi)

US-Patent 8,489,368 B2

(http://google.com/patents/US20110218778?hl=de&cl=fi)

Patent WO 2009/024130 A1 (http://google.com/patents/WO2009024130A1?hl=de&cl=en)