A connected graph based shape descriptor for comparing 3D CAD models/3D CAD modeliu palyginimas naudojant jungtiniu grafu profilio vaizda.

Zhang, Xutang ; Jin, Tianguo ; Chen, Xiaofeng 等

1. Introduction

Local shape feature extraction and representation has been the focus of research interests in the field of computer vision and computer-aided design (CAD). Varieties of local image feature descriptors have been developed by detecting the gradients, edges and corner points, and have been successfully applied to a wide range of computer vision and image analysis tasks [1]. Recently, with the increasing interests on reverse engineering and 3D model retrieval, local feature representation and recognition of three-dimensional shape has been received extensive attentions.

By far, a number of local feature representation approaches have been developed for 3D shape matching and retrieval. Bespalov et al. proposed a scale-space based approach for the recursive decomposition of the surface to form the surface characteristics tree of a 3D model [2]. Gal and Cohen-Or used the rectangular approximation to represent the local curvature patches, calculated the geometric properties of these patches, and clustered these patches to produce the local salient shape features [3]. Sundar et al. presented a method to generate skeleton graph by using the thinning algorithm, and successfully applied it to voxel description of any 3D models [4]. Tung and Schmitt calculated the multiresolution Reeb graph from 3D shapes of the objects, and then introduced a topology similarity method to assess the similarity for 3D shapes [5]. Recently, the Reeb graph has been further extended such that its nodes can be attached with a variety of geometric information to improve their describing ability [6]. Using skeleton graph or extended Reeb graph as the shape descriptors of 3D models can reflect the local features of the shape to a certain extent, but both methods can not accurately represent and extract the local surface feature information.

In this paper, by taking both the local features and their connections into account, we propose a novel local shape feature representation method, geodesic connected graph, for 3D CAD model analysis. In our method, extended Gaussian image [7] is first used to divide the 3D model surfaces and to obtain basic feature areas on the model, then the geodesic curves are generated to connect some selected feature areas, and finally a connected graph descriptor of local features is generated based on the geodesic path. To utilize the connected graph descriptor for CAD model analysis, we further propose a subgraph matching method for the extraction, matching, and retrieval of the typical predefined local features.

2. Surface segmentation

Gaussian image is the mapping of surface normals of a 3D object onto the unit sphere (Gaussian sphere). Gaussian sphere is a unit sphere where any point on a 3D surface can be mapped onto one point on Gaussian sphere if the following conditions can be met, i.e. the two corresponding points have the same normal vector direction. For each point p in Gaussian sphere, we assign a value by accumulating the area of all the triangle-meshes of which the normal direction are the same with direction of the point p [6].

Two types of adjacent relationships between two triangle facets are defined as follows:

(1) geometric adjacency: two triangle facets are geometric adjacent if they share the same edge;

(2) gaussian adjacency: two triangle facets are Gaussian adjacent if the angle between the two normal vectors on Gaussian sphere of these two triangle facets is less than a threshold (e.g. 30[degrees]).

We define the two adjacent triangle facets are connected. The connectivity between triangle facets is transitive, i.e., suppose e,f and g are triangle facets on the model, if e and f are connected,f and g are connected, then e and g are also connected. Based on the connectivity, we define the connected area A as the set of triangle facets where any two of them are connected. According to the types of adjacency relationship, the connected area A can also be categorized into two types:

(1) geometric connected area: any two triangle facets in the set are connected by Geometric adjacency.

(2) gaussian connected area: any two triangle facets in the set are connected by Gaussian adjacency.

If the area A is both Geometric and Gaussian connective, it is a segmentation area of model surface, which is also called a basic feature area. For a basic feature area, four attributes are defined as follows:

(1) The type of feature area: the basic feature area can be further classified into three types: plane, cylindrical surface, and free-form surface:

(A) plane: the corresponding Gaussian connective area is a point;

(B) cylindrical surface: the corresponding Gaussian connective area consists of several points which lie on one circle;

(C) free-form surface: the corresponding Gaussian connective area consists of several points, which do not lie on one circle.

(2) The center of feature area is defined as a point on a triangle facet of this feature area. It can be calculated as follows:

Step 1: calculating the center q of Gaussian connective area corresponding to the feature area. There are three possible circumstances:

if Gaussian connective area is one point on Gaussian sphere, then this point can be regarded as the center q;

if Gaussian connective area is one circle on Gaussian sphere, then selecting one point on the circle randomly as the center q;

if Gaussian connective area is circle surface on Gaussian sphere, then the center of this surface can be regarded as the center q.

Step 2: searching for the n triangle facets on the feature area corresponding to the center q, whose centers are [m.sub.1], [m.sub.2], [m.sub.n], respectively. Thus, the center c of this feature area can be defined as

c = ([m.sub.1] + [m.sub.2] + ... + [m.sub.n])/n

(3) The visibility of feature areas. Starting from the center of feature area, a half-line is created along with the direction of the normal of triangle. If this half-line does not intersect with any other triangles, then this area is visible, otherwise, it is invisible.

(4) The connectivity between feature areas. Two feature areas are of connectivity if and only if there exist geometric adjacent relation between triangles of two features.

3. Geodesic connected graph based local feature descriptor

In differential geometry, geodesic line has a strict definition, i.e. a curve on a surface, whose geodesic curvature on each point is zero, is called a geodesic line. In engineering, geodesic line is intuitively regarded as the shortest path of connecting two points on the surface, and the length of this shortest path is called geodesic distance. The visible areas obtained by the analysis of normal vectors in Gaussian image are connected with geodesics along a certain direction. The normal vector in Gaussian image, which describes the normal vectors of triangle facets on a model surface, may correspond to one or several areas mainly distributed on a side of the model. Indexing with the normal vectors in Gaussian image, the corresponding areas are connected by geodesics, and then connected graph can be created via the geodesics paths to describe local features and their relations. Based on the normal vectors on Gaussian sphere, two concepts can be defined as follows:

The aspect of a model: if there exists a normal vector n on the Gaussian Sphere, and the number M of its corresponding basic areas is not less than 1, then these regions corresponding to the vector n constitute an aspect of the model. The vector n is called the direction of this aspect of model.

The view direction of the aspect: if the direction of the aspect is n, then the opposite direction n is called the view direction of the aspect.

From the above definitions one can see that the areas included in the aspect of the model are visible along the view direction of the aspect. For example, for the model shown in Fig. 1, the areas 2, 4, 6 and 9 constitute an aspect of the model. The direction of this aspect is along the positive Y axis, the view direction is along the negative Y axis. A model may consist of a few aspects {[A.sub.1], [A.sub.2], [A.sub.k]}, and the number of areas that these aspects own are {[N.sub.1], [N.sub.2], ..., [N.sub.k]}. Without loss of generality, we suppose [N.sub.1] > [N.sub.2] > ... > [N.sub.k]. Thus, these aspects can be processed to extract local features by geodesics connection one by one according to the sequence sorted by the number of areas. In addition, for the hole, cylinder or the free-form areas which are geometric adjacent with the areas of the model, they should be handled together with the local feature extraction. Let the areas contained in an aspect, together with holes, cylinders and free surfaces that have geometric connection relationships with these areas form a set F = {[f.sub.i]}. The centers of elements in the set are connected with geodesics to form a graph according to distances among these centers. The detailed connection process can refer to [8]. The graph produced by the method is defined as the geodesic connection graph (Gcg). Fig. 1 shows the geodesics and the Gcg for one aspect. The aspect contains main areas 2, 4, 6 and 9.

[FIGURE 1 OMITTED]

4. CAD models comparing method

In the proposed representation scheme, the model can be described as a set composed of Gcgs. The problem of comparing two models can be transformed into corresponding elements in the two sets. Once solve the corresponding problem, the model's feature matching also can be acquired. In the following, we first give the method of computing the similarity of two Gcgs and then present the matching process of two Gcg sets.

The similarity of two Gcgs can be evaluated by using graph matching technology. The VF2 algorithm proposed by Cordelia et al [9] is used in our work. Different from other approaches, the VF2 explores a new data structure to store the node information, which reduces the searching space. Meanwhile, VF2 does not constrain the topology structure of subgraphs, and can also discover graph-subgraph isomorphism. Comparing with other subgraph matching algorithms, VF2 is superior in solving the subgraph matching problem of graphs [10].

Supposed we have two Gcg sets, G = {[g.sub.1], [g.sub.2], [g.sub.3]}, K = {[k.sub.1], [k.sub.2], [k.sub.3], [k.sub.4], [k.sub.5]}, the procedure of matching two set can be stated as following:

Step 1: randomly select one Gcg, e.g., [g.sub.1], from set G, and remove [g.sub.1] from the set G.

Step 2: compare [g.sub.1] with every Gcg in the set K, and assume that [g.sub.1] matches best with [k.sub.2], then output the best matching pair <[g.sub.1],[k.sub.2]> and remove [k.sub.2] from the set K.

Step 3: end the matching stage if the set G or the set K is empty, else go to Step 1.

[FIGURE 2 OMITTED]

[FIGURE 3 OMITTED]

[FIGURE 4 OMITTED]

5. Examples

To test the effectiveness of the proposed comparison methods, we take sevral CAD models as computation examples (note: these models are from Purdue's ESB library [11]). First, as shown in the Fig. 2, the model is divided into surfaces and the model's aspects represented by Gcgs are computed. Then, using subgraph matching techniques, we compare and the Gcg sets of the two models, and the results are shown in the Figs. 3 and 4. According to Gcg mathcing pair, we can verify the correspondence of the main aspects (omit some trivial Gcgs maching pairs) and compute the number of nodes of matching subgraphs betwwen two Gcgs. The number of nodes can be used to evalute the similiarity of two Gcgs which reflects similarity of two models. From the experiment, one can see that the comparison and matching results are consistent with human's intuition of judging similiarity between two models.

6. Conclusions

In this paper, based on the triangle mesh of 3D CAD models, according to the characteristics of CAD models, i.e. CAD models mainly consist of planes and quadric surfaces, and functional features generally lie on a few surfaces, an extended Gaussian image and geodesics approach for local shape representation and extraction is proposed. This method describes the local shape features as a few geodesic graphs consisting of several feature areas. We also present the generation procedure of geodesic connected graph. Based on the geodesic connected graph and subgraph matching, CAD models can be compared. We conduct some experiments to comparing 3D models. The results show that the proposed method can obtain the similarity and the feature corresponding relation between two models.

Acknowledgment

This work was supported by national natural science foundation of china (Grant No. 51001121).

References

[1.] Tuytelaars, T.; Mikolajczyk, K. 2007. Local invariant feature detectors: a survey, Foundations and Trends in Computer Graphics and Vision, Vol. 3, No. 3: 177-280.

[2.] Bespalov, Dmitriy; C. Regli, William: Shokoufandeh, Ali. 2006. Local feature extraction and matching parial objects, Computer-Aided Design 38:1020-1037.

[3.] Ga, R.; Cohen-Or, D. 2006. Salient geometric features for partial shape matching and similarity, ACM Transactions on Graphics 25(1): 130-150.

[4.] Sundar, H.; Silver, D.; Gagvani, N.; Dickenson, S. 2004. Skeleton based shape matching and retrieval. In: Proc. shape modeling international 2004: 130-139.

[5.] Tung, T.; Schmitt, F. 2005. Augmented multipesolution reeb graph approach for content-based retrieval of 3D shapes, International Journal of Shape Modeling, vol.11, no. 1, June 2005: 157-166.

[6.] Tierny, Julien; Vandeborre, Jean-Philippe; Daoudi; Mohamed. 2009. Partial 3D shape retrieval by reeb pattern unfolding, Computer Graphics Forum., vol. 28 Issue 1: 41-55.

[7.] Horn, B.K.P. Extended Gaussian images. AI Memo No. 740, AI Lab., MIT, 1983.7.

[8.] XuTang, Zhang; XiaoFeng, Chen; PengYu, Yang et al. 2010. Geodesic connected graph representation of 3D prismatic CAD models. Proceedings - 2010 International Conference on Digital Manufacturing and Automation, ICDMA 2010: 776-779.

[9.] Cordella, L. P.; Foggia, P.; Sansone, C.; Vento, M. 2001. An improved algorithm for matching large graphs. Proceedings of the 3rd IAPR-TC-15 International Workshop on Graph-based Representations, Italy: 149-159.

[10.] Foggia, P.; Sansone, C.; Vento, M. 2001. A performance comparison of five algorithms for graph isomorphism, In Proc. 3rd IAPR-TC15 Workshop GraphBased Representations in Pattern Recognition: 188-199.

[11.] Jayanti, S.; Kalyanaraman, Y.; Iyer, N.; et al. 2006. Developing an engineering shape benchmark for CAD models [J], Computer-Aided Design 38: 939-953.

Received March 10, 2011

Accepted August 23, 2011

Xutang Zhang *, Tianguo Jin **, Xiaofeng Chen ***, Wangmeng Zuo ****

* School of Mechatronics Engineering, Harbin Institute of Technology, Harbin, 150001, China, E-mail: zxt@hit.edu.cn

** School of Mechatronics Engineering, Harbin Institute of Technology, Harbin, 150001, China, E-mail: jintg@hit.edu.cn

*** School of Mechatronics Engineering, Harbin Institute of Technology, Harbin, 150001, China, E-mail: cxf@hit.edu.cn

**** School of Computer Science and Technology, Harbin Institute of Technology, Harbin, 150001, China, E-mail: cswmzuo@gmial.com