US 12,118,278 B1 · Difference analysis method for 3D cad models based on key-point matching

Abstract

A difference analysis method for 3D CAD models based on key-point matching. According to the method, a 3D CAD model is firstly transformed into a key-point representation, then a graph representation and a graph matching method are introduced to establish a pre-matching of vertices between the two 3D CAD models, and rigid transformation parameters between the two 3D CAD models are obtained through a mismatch elimination method; and subsequently, a matching relationship of key-points is established by checking their distance after rigid transformation to obtain a key-point matching sequence for hierarchical comparison, so as to identify the differences between vertices, edges, faces and solid models, thereby quickly and accurately identifying the difference between the 3D CAD models.

A difference analysis method for 3D CAD models based on key-point matching, comprising:

step S1, acquiring 3D CAD models from two parts to be compared through a 3D scanner, and transforming the two 3D CAD models to be compared into a STP format;
step S2, extracting three kinds of key-points, namely vertices, edge control points and face control points, from the 3D CAD models, further comprising:
extracting intersections of edges from the 3D CAD models as the vertices, and recording 3D coordinates of the vertices;
transforming the edges of the 3D CAD models into a form of a Non-Uniform Rational B-Spline (NURBS) curve, and taking NURBS control points except the vertices extracted from each of the edges as the edge control points of the 3D CAD models, and recording 3D coordinates and weights of the edge control points;
transforming faces of the 3D CAD models into a NURBS form, and taking the NURBS control points except the vertices extracted from each face as the face control points of the 3D CAD models, and recording 3D coordinates and weights of the face control points;
and
developing a visualization interface based on an Open Cascade platform to display the extracted three kinds of key-points on the 3D CAD models by using three different formats of markers:
step S3, transforming the 3D CAD models into graph representation forms for vertex pre-matching, wherein each face of the 3D CAD models corresponds to one node of a graph, and when two faces in the 3D CAD models share a common edge, there is one link between two nodes in the graph, corresponding to the common edge of the two faces, otherwise there is no link between the two nodes;
step S4, calculating a similarity between nodes and a similarity between links of two graphs, further comprising:
sub-step S4.1, uniformly sampling on a model face corresponding to a node by a NURBS representation:
{
l
n
i
}
=
{
S
i
(
0
,
0
)
,
S
i
(
0
,
1
N
1
-
1
)
,
S
i
(
0
,
2
N
1
-
1
)
,
…
,
S
i
(
0
,
1
)
,
S
i
(
1
N
1
-
1
,
0
)
,
S
i
(
1
N
1
-
1
,
1
N
1
-
1
)
,
…
,
S
i
(
1
,
1
)
}
where {lni} is a set of sampling points of an ith node Gi, n=1, . . . , N1×N1, N1 is a sampling number, Si(u,v) is a sampling point on a model face Si corresponding to the node Gi obtained by the NURBS representation;
uniformly sampling on a model edge corresponding to a link by a NURBS representation, namely:
{
l
m
ij
}
=
{
C
ij
(
0
)
,
C
ij
(
1
N
2
-
1
)
,
C
ij
(
2
N
2
-
1
)
,
…
.
C
ij
(
1
)
}
where {lmij} is a set of sampling points of a link Gij between an ith node and a jth node, m=1, . . . , N2, N2 is a sampling number, Cij(u) is a sampling point obtained by the NURBS representation of a model edge Cij corresponding to the link Gij;
sub-step S4.2, calculating an average matching distance error of two point sets based on rigid transformation, and finding an optimal rigid transformation for any two point sets {pk} and {qk} with a same number of points by:
(
R
*
,
T
*
)
=
arg
⁢
min
⁢
∑
k
=
1
K

(
R
·
p
k
+
T
)
-
q
k

2
where K is a number of points in the point sets, R* and T* are an optimal rotation matrix and an optimal translation matrix, respectively, pk and qk are 3D coordinates of a kth point in the two point sets {pk} and {qk}, respectively, and a solution of R* and T* is:
R
*
=
V
⁢
{
1
1
⋱
1
det
⁡
(
VU
T
)
)
⁢
U
T
T*=q−R*p
where
p
_
=
1
K
⁢
∑
k
=
1
K
p
k
,
and
⁢
q
_
=
1
K
⁢
∑
k
=
1
K
q
k
;
U and V are singular value decompositions of a covariance matrix Sc, Sc=XYT, where X and Y comprise column vectors xk=pk−p and yk=qk−q, respectively, k=1, 2, . . . ,K;
and
calculating, after obtaining the optimal rotation matrix and the optimal translation matrix, an average matching distance error as follows:
E
⁡
(
{
p
k
}
,
{
q
k
}
)
=
1
K
⁢
∑
k

(
R
*
·
p
k
+
T
*
)
-
q
k

2
sub-step S4.3, calculating the similarity between the nodes and the similarity between the links, respectively, based on the average matching distance error of the two point sets;
wherein the similarity between two nodes Gi and G′i′ in two graphs G and G′ is:
Snode(Gi,G′i′)=e−E({lni},{l′ni′})
where {lni} is a set of sampling points of the node Gi in a graph G, and {l′ni′} is a set of sampling points of a node G′i′ in a graph G′;
wherein the similarity between two links Gij and G′i′j′ in the two graphs G and G′ is:
Slink(Gij,G′i′j′)=e−E({lmij},{l′mi′j′})
where {lmij} is a set of sampling points of the link Gij in the graph G, and {l′mi′j′} is a set of sampling points of a link G′i′j′ in the graph G′;
step S5, pre-matching the vertices of the two 3D CAD models by using a graph matching method, and defining a matching matrix M of the two graphs G and G′, wherein an element mii′ is 1 when the node Gi of the graph G is matched with the node G′i′ of the graph G′, and otherwise the element mii′ is 0;
finding an optimal matching matrix M* to maximize a total similarity:
M
*
=
arg
⁢
max
M
⁢
(
∑
ii
′
m
ii
′
·
S
node
(
G
i
,
G
i
′
′
)
+
∑
ii
′
∑
jj
′
m
ii
′
·
m
jj
′
·
S
link
(
G
ij
,
G
i
′
,
j
′
′
)
)
solving M* by an integer projected fixed point method to obtain a node matching result of the two graphs G and G′, wherein faces on the 3D CAD models corresponding to the two nodes matched in the graphs are pre-matched faces, and wherein when all the faces adjacent to two edges are correspondingly pre-matched, the two edges are pre-matched edges, and when all the edges adjacent to two vertices are correspondingly pre-matched, the two vertices are pre-matched vertices;
step S6, calculating a rigid transformation between the 3D CAD models by a mismatch elimination method, calculating the average matching distance error of a set of pre-matched vertices after giving a maximum allowable modeling error ε, wherein the optimal rotation matrix and the optimal translation matrix are rigid transformation matrices RM and TM between the 3D CAD models when the average matching distance error is smaller than the maximum allowable modeling error ε;
otherwise, calculating a matching distance error of each pair of the pre-matched vertices, respectively:
Ek({pk},{qk})=∥(R*·pk+T*)−qk∥
where Ek({pk},{qk}) is the matching distance error of a kth pair of the pre-matched vertices in the point sets {pk} and {qk}, pk and qk are 3D coordinates of the kth pair of the pre-matched vertices in the point sets {pk} and {qk};
recalculating the average matching distance error after eliminating a vertex pair with the maximum matching distance error from the sets of pre-matched vertices, and comparing the average matching distance error with the maximum allowable modeling error ε until the rigid transformation parameters RM and TM between the 3D CAD models are solved;
step S7, matching the three kinds of key-points, namely the vertices, the edge control points and the face control points, substituting the rigid transformation parameters RM and TM into every pair of the vertices of the two 3D CAD models, and calculating a matching distance error;
eii′v=∥RM·piv+TM−qi′v∥
where piv and qi′v are 3D coordinates of an ith vertex and an i′th vertex in vertex sets {piv} and {qi′v} of the two 3D CAD models;
and when the matching distance error eii′v is smaller than the maximum allowable modeling error ε, the two corresponding vertices are matched vertices;
substituting the rigid transformation parameters RM and TM into each pair of edge control points, and calculating the matching distance error, respectively:
eii′e=∥RM·pie+TM−qi′e∥+∥w(pie)−w(qi′e)∥
where pie and qi′e are 3D coordinates of an ith edge control point and an i′th edge control point in edge control point sets {pie} and {qi′e} of the two 3D CAD models, w(pie) and w(qi′e) are weights of the corresponding edge control points pie and qi′e;
and when the matching distance error eii′e is smaller than the maximum allowable modeling error ε, the two corresponding edge control points are matched edge control points;
substituting the rigid transformation parameters RM and TM into each pair of face control points, and calculating the matching distance error, respectively:
eii′f=∥RM·pif+TM−qi′f∥+∥w(pif)−w(qi′f)∥
where pif and qi′f are 3D coordinates of an ith face control point and an i′th face control point in face control point sets {pif} and {qi′f} of the two 3D CAD models, w(pif) and w(qi′f) are weights of the corresponding face control points pif and qi′f;
and when the matching error eii′f is smaller than the maximum allowable modeling error ε, the two corresponding face control points are matched face control points;
and
step S8, analyzing differences of the 3D CAD models hierarchically, wherein when all the vertices and the edge control points of every two edges on the two 3D CAD models are matched correspondingly, the two edges are considered identical edges, otherwise the two edges are considered different edges;
when all the face control points of every two faces on the two 3D CAD models are matched correspondingly and all constituent edges of every two faces on the two 3D CAD models are identical edges, the two faces are considered identical faces, otherwise the two faces are considered different faces;
and when all the faces on the two 3D CAD models are identical faces, the two 3D CAD models are identical, and otherwise, the two 3D CAD models have differences;
and
step S9:
outputting an obtained difference analysis result of the 3D CAD models to the visualization interface developed based on the Open Cascade platform, importing and displaying the two 3D CAD models to be compared, and highlighting all different faces of the two 3D CAD models to visually display the difference analysis result of the 3D CAD models:
step S10:
classifying the two parts based on the difference analysis result of the 3D CAD models, when there being no differences between the two parts, classifying the two parts as a same version, otherwise, classifying the two parts as different versions, so as to provide parts of correct version during assembly.

354 more elements

Difference analysis method for 3D cad models based on key-point matching

Life of this patent

Difference analysis method for 3D cad models based on key-point matching

Life of this patent

Abstract

Claims3