CN110910492B - A point-to-point matching method between non-rigid 3D models - Google Patents

Abstract

The invention discloses a point-to-point matching method between non-rigid three-dimensional models. The method includes the following steps: firstly establishing an anisotropic spectral manifold wavelet descriptor; then using the established descriptor as a descriptor constraint of model points, using The thermal core relationship of each point on the model is used as a point-to-point relationship constraint to establish an objective function to achieve the optimal matching between model points. The present invention first establishes an anisotropic spectral manifold wavelet descriptor in the early stage, and then uses the thermal kernel relationship as a point-to-point relationship constraint. Compared with the existing methods, the anisotropic spectral manifold wavelet descriptor has the advantages of equidistant deformation invariance, intrinsic symmetry that can distinguish models, high resolution and localization capabilities, high computational efficiency, and compact structure. ; The thermonuclear relationship as a point-to-relation constraint is more efficient and stable than other methods using geodesic distances; thus, this method ensures that the calculation is clear, the results are robust, and the matching is accurate.

Description

A point-to-point matching method between non-rigid 3D models

technical field

The invention belongs to the field of computer graphics and computer vision, and particularly relates to a point-to-point matching method between non-rigid three-dimensional models.

Background technique

In the past ten years, with the rapid development of 3D model acquisition equipment and related technologies, digital 3D models can be used to represent very rich objects, and their related applications involve traditional computer-aided design, medical engineering and emerging industries such as multimedia technology. , entertainment industry, etc. Retrieval of 3D models, recognition and classification, semantic segmentation, and migration are basic and important applications that widely exist in these fields, and the important premise for realizing these applications is to establish accurate and efficient point-to-point matching between 3D models (below). referred to as model matching).

The core technology of the mainstream method for establishing model matching lies in the following two steps:

(1) First, establish point descriptors that accurately describe the geometric features of the model;

By encoding the multi-scale shape information and geometric features of each point of the model, a point descriptor (usually expressed as a high-dimensional vector) that can describe the overall geometric feature at each point of the model is constructed. This descriptor requires high resolution and computational efficiency;

(2) Establish an optimal descriptor matching method in the descriptor space of the model to achieve accurate matching of points on the model.

Due to the complex and diverse forms of the actual 3D model, it may also undergo various deformations. At the same time, the limitations of digital scanning equipment may also lead to a large amount of noise in the model, or even partial loss of the model, which makes the realization of high-performance matching become a computer graphics. Challenging problems in the fields of science and vision.

At this stage, the spectral point descriptor established by diffusion geometry (which can be regarded as a set of filters acting on the eigenvalues and eigenvectors of the Laplace-Beltemi operator) has high computational efficiency and intrinsic (equidistant) Deformation) invariance and other characteristics have become the main method to analyze the shape characteristics of non-rigid models. Representative works include Heat Kernel Signature (HKS, Heat Kernel Signature) and Wave Kernel Signature (WKS, Wave Kernel Signature), but neither of these two methods can fully analyze the details or contour information of the model, and cannot realize the point-to-point relationship between the model. The precise positioning is easy to generate matching noise. Other methods still have deficiencies in the computational efficiency, resolving power, and stability of descriptors. In particular, the vast majority of these methods fail to recognize the symmetries inherent in the model, which greatly reduces the accuracy of descriptor and model matching.

After establishing accurate model point descriptors, matching between models can be achieved by minimizing distortion. There are two main strategies in the current approach. One is to find matching points by using the nearest neighbor method in the descriptor space. This method is simple and easy to implement, but the matching performance depends heavily on the descriptors used, and this type of method fails to consider the relationship between points on the model. Geometric associativity can easily lead to discontinuity in matching. To this end, another approach constrains the geometric relationship between the descriptors while considering the point descriptors with as little distortion as possible. This class of methods is significantly more accurate than simply using the nearest neighbor method. However, the performance of the descriptors used in the early stage and the correct establishment of the geometric association between point pairs still seriously affect the accuracy of the final matching.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a method that can improve the accuracy of point-to-point matching between non-rigid three-dimensional models in view of the shortcomings of the prior art.

The method for point-to-point matching between this non-rigid three-dimensional model provided by the present invention includes the following steps:

Step 1. Establish an anisotropic spectral manifold wavelet descriptor;

In step 2, the descriptor established in step 1 is used as the descriptor constraint of the model point, and the thermal kernel relationship of each point on the model is used as the point-to-point relationship constraint, and an objective function is established to realize the optimal matching between the model points.

In a specific implementation manner, when establishing the anisotropic spectral manifold wavelet descriptor in step 1, the steps are as follows:

Step (1), calculate the anisotropic Laplace-Bermit matrix of the model and perform generalized eigendecomposition,

Step (2), define anisotropic spectral manifold wavelet transform,

Step (3), establishing an anisotropic spectral manifold wavelet descriptor.

Further, in step (1), the anisotropic Laplace-Bermite matrix L _αθ =-A ^-1 B _αθ ,

where A=diag(a ₁ ,...,a _N ) is a diagonal matrix, and the elements on the diagonal represent the neighborhood area of the corresponding vertex,

广义特征分解，求解方程B_αθφ_αθ,k＝λ_αθ,kAφ_αθ,k，Matrix β _αθ = (b _ij ) is the weight matrix, where

Generalized eigendecomposition, solve the equation B _αθ φ _αθ,k =λ _αθ,k Aφ _αθ,k ,

和特征向量集

get eigenvalues

and eigenvector set

for1≤x≤2，相应的尺度函数生成核函数为

其中γ设置为与g(x)的最大值相等。Correspondingly, in step (2), the wavelet generation kernel function is:

for1≤x≤2, the corresponding scale function generation kernel function is

where γ is set equal to the maximum value of g(x).

Further, in step (3), the descriptor at mesh vertex i is denoted as ASMWD(i),

in,

During specific implementation, in the second step,

Given a grid model X and Y, compute the anisotropic spectral manifold wavelet descriptor for each point of X and Y to get the matrix F _X ,

计算热核确定的点对关系矩阵K_X,

Select time t, according to the formula

Calculate the point-to-point relationship matrix K _X determined by the heat kernel,

求解即可。Establish an optimization objective function for the descriptors of points and point-to-point relationships:

Solve it.

The present invention first establishes an anisotropic spectral manifold wavelet descriptor in the early stage, and then uses the thermal kernel relationship as a point-to-relationship constraint. Compared with existing methods, the anisotropic spectral manifold wavelet descriptor has the advantages of equidistant deformation invariance, intrinsic symmetry that can distinguish models, high resolution and localization capabilities, high computational efficiency, and compact structure. ; The thermonuclear relationship as a point-to-relationship constraint is more efficient and stable than other methods using geodesic distances; thus, this method ensures that the calculation is clear, the results are robust, and the matching is accurate.

Description of drawings

FIG. 1 is a schematic flowchart of a preferred embodiment of the present invention.

Fig. 2 is a graph showing the characteristics of anisotropic spectral manifold wavelet descriptor (equidistant deformation invariance).

Fig. 3 is a graph showing the characteristics of anisotropic spectral manifold wavelet descriptor (intrinsic symmetry distinction).

4(a)-4(f) are schematic diagrams of performance comparison results between the descriptor in this embodiment and other existing descriptors.

FIG. 5 is a schematic diagram of comparing the results of the matching method in this embodiment and the existing matching method.

6(a)-6(d) are schematic diagrams of visual comparison of matching results between the matching method in this embodiment and the existing matching method.

Detailed ways

The high-performance three-dimensional model matching method disclosed in this embodiment is called ASMWD-PMF (Product Manifold Spatial Filtering Based on Anisotropic Spectral Manifold Wavelet Descriptors). The matching between models with approximately equidistant deformation can be very accurately realized, the method has high calculation efficiency, and the performance is far superior to the existing matching methods, and can provide an important technical guarantee for the subsequent application of the three-dimensional model.

As shown in Figure 1, in the specific implementation, the detailed calculation steps are:

1. Establish an anisotropic spectral manifold wavelet descriptor.

The descriptor algorithm can be divided into the following three steps:

1.1 The anisotropic Laplace-Belthemi matrix of the computational model and its eigendecomposition;

表示定义在网格上的函数。First calculate the anisotropic Laplace-Bertemi operator, and generally express the discrete form of the three-dimensional model as a triangular mesh M(V,E,F), which includes a vertex set V={1,...,N }, edge set E and patch set F={(i,j,k)}, vector

Represents a function defined on the grid.

其中n为面片上的单位法向。计算在坐标系U_ijk下表示的张量矩阵Given the anisotropy parameter α and the rotation angle θ, first calculate the principal curvature directions V _M , V _m on each patch, and establish an orthogonal coordinate system on the patch

where n is the unit normal on the patch. Compute the tensor matrix represented in the coordinate system U _ijk

表示从三角形顶点i指向顶点j的单位向量，定义边e_kj和e_ki的H_θ-内积

vector

represents the unit vector from triangle vertex i to vertex j, defining the H _θ -inner product of edges e _kj and e _ki

The anisotropic Laplacian-Beltemi operator is discretely represented as an N×N sparse matrix L _αθ =-A ^-1 B _αθ , where A=diag(a ₁ ,...,a _N ) is a diagonal matrix, Elements on the diagonal represent the neighborhood area of the corresponding vertex. Matrix β _αθ = (b _ij ) is the weight matrix, where

Generalized eigendecomposition of the above anisotropic Laplace-Bermite matrix L _αθ , that is, solving the equation

B _αθ φ _αθ,k =λ _αθ,k Aφ _αθ,k (2)

和对应的特征向量

它们分别称为流形上的频率和傅里叶基函数。相应的，信号f的傅里叶系数

可由下式计算：obtained eigenvalues

and the corresponding eigenvectors

They are called the frequency and Fourier basis functions on the manifold, respectively. Correspondingly, the Fourier coefficients of the signal f

It can be calculated by the following formula:

In particular, the Fourier coefficients of the impulse function at point n are

1.2 Anisotropic spectral manifold wavelet transform;

First create an anisotropic spectral manifold wavelet transform on the manifold. In essence, the classical wavelet transform filters the Fourier coefficients in the frequency domain. Therefore, the anisotropic spectral manifold wavelet transform can be defined with the help of the frequency domain defined by the characteristic system of the anisotropic Laplace-Beltemi operator.

位于点m处尺度为s_j的各向异性谱流形小波函数

定义为In practical applications, J discrete scales are first sampled

Anisotropic spectral manifold wavelet function with scale s _j at point m

defined as

为The corresponding scaling function at that point

for

We define the anisotropic spectral manifold wavelet transform of the signal as the inner product of the signal f and the corresponding wavelet function, namely

In the calculation of the above wavelet function, the wavelet kernel function g(x) and the scale kernel function h(x) are equivalent to the filter function in the frequency domain, and the cubic B-spline wavelet can be selected to generate the kernel function

The corresponding scaling function generates the kernel function

where γ is set equal to the maximum value of g(x).

The discrete wavelet scale is determined by the upper bound of the _Lαθ spectrum by _sj . The maximum scale and the minimum scale are respectively taken as s _J =x ₁ /λ _max , λ _min =λ _max /k, k>0, the rest s _J ≤s _j ≤s ₁ are equal logarithmic distributions, and the parameter k is selected by the user .

1.3 Anisotropic Spectral Manifold Wavelet Descriptor

For vertex i on the grid, the multi-scale anisotropic spectral wavelet transform coefficients of the impulse function located at the point are selected to encode the multi-scale geometric information of the neighborhood around the point.

我们可得because

we can get

For each direction θ, we first obtain the descriptor in that direction, namely

In order to fully capture the geometric information in each direction, we use L equally distributed rotation angles, that is, let

Finally, we concatenate the descriptors of each sub-direction into a (J+1)×L high-dimensional vector as the descriptor at the mesh vertex i, namely

The pseudocode for calculating ASMWD in this step is shown in the following table:

2. Matching of descriptors.

After calculating the ASMWD at each model vertex, we need to design an optimization algorithm to use this descriptor to find the optimal point-to-point match between models. We now describe our method in detail by taking the matching between two models as an example.

在离散情况下，这两个网格上所有顶点处的ASMWD形成矩阵F_X,

Given grid models X and Y, first compute their q-dimensional ASMWD at each point, denoted as

In the discrete case, the ASMWDs at all vertices on these two meshes form the matrix F _X ,

The matching between two models can be regarded as a mapping: π:{x ₁ ,x ₂ ,...,x _N }→{y ₁ ,y ₂ ,...,y _N }, where i=1,2...,Nx _i , y _i are the vertices on X and Y, respectively. This mapping is represented as a permutation matrix Π∈{0,1} ^N×N that satisfies Π ^T 1 =Π1=1, where 1 is a column vector with all elements 1. Denote the N×N permutation matrix space as P _N .

A heat kernel is used to represent the relationship between pairs of points on each model. The heat kernel is the solution of the thermal diffusion equation on the manifold X, which can be expressed as the exponential relationship of the intrinsic operator, that is, the heat kernel relationship between x and y at time t is:

Its value represents the heat transferred from point x to y at time t. In the discrete case, the thermal kernel relationship between all points on X and Y is expressed as K _X , respectively,

Now build the optimization objective function with regard to the descriptors of points and point-to-point relationships:

The solution of the optimization problem can be converted into a corresponding convex optimization problem, and can be obtained.

The pseudo code of the model matching algorithm in this step is shown in the following table

Take the deformations that joints undergo when the human body has different postures.

As shown in Figure 2, a three-dimensional model of the human body is established, on which joints of different parts are selected as selection points, and each point has the invariance of isometric deformation.

As shown in Figure 3, the 3D model of the human body has intrinsic symmetry distinction, and the use of anisotropy, that is, when establishing the descriptor, the intrinsic direction information of the model is considered, so that the descriptor can distinguish the symmetry and overcome the general spectral descriptor. It is more in line with the actual matching requirements.

Comparing the performance of this method (ASMWD-PMF) with the existing descriptors, the descriptors are superior to the existing methods in terms of their ability to distinguish and locate, and the matched regions are only concentrated in a small neighborhood of the correct matching points.

As shown in Figures 4a-4f, this method has the advantages of high computational efficiency and compact structure compared with the existing methods; the dimension of the descriptor is lower than that of similar methods, and there is no need to calculate the complex function representing the model features in advance, The solution process does not need to rely on high-dimensional equations or the calculation of geodesic distances.

For different vertex models, the time statistics of different descriptors are shown in the following table,

The comparison of the matching results between this method and other methods is shown in Figure 5, and the visual comparison of the matching results between this method and other methods is shown in Figures 6(a)-6(d). , and connect the corresponding points with straight lines.

To sum up, the advantages of this algorithm are: using the ASMWD established in the early stage of this technical solution, the optimization result is not easy to produce the whole block flip of the model matching area; using the thermonuclear relationship as the point-to-relationship constraint, it is more efficient than other methods using geodesic distances. The stability is better; all in all, this technology proposes a new matching method for the shortcomings of the existing three-dimensional model matching methods in terms of accuracy and computational efficiency. The method has clear calculation, robust results, accurate matching, and is suitable for dealing with complex models with equidistant deformations. This technology will greatly promote the subsequent application based on 3D model matching and the development of related industries.

Claims (5)

1. A method of point matching between non-rigid three-dimensional models, the method comprising the steps of:

step one, establishing an anisotropic spectrum manifold wavelet descriptor;

(1) calculating the anisotropic Laplace-Bell meter matrix of the model and carrying out generalized characteristic decomposition,

(2) defining anisotropic spectral manifold wavelet transform,

(3) establishing an anisotropic spectrum manifold wavelet descriptor;

and step two, taking the descriptor established in the step one as descriptor constraint of the model point, adopting the thermonuclear relation of each point on the model as point pair relation constraint, establishing a target function, and realizing optimal matching between the model points.

2. The method of point matching between non-rigid three-dimensional models according to claim 1, characterized in that: in step (1), an anisotropic Laplace-Bell Meter matrix L_αθ＝-A^-1B_αθ，

Wherein A ═ diag (a)₁,…,a_N) For a diagonal matrix, the elements on the diagonal represent the neighborhood area of the corresponding vertex,

matrix B_αθ＝(b_ij) Is a weight matrix, wherein

Generalized characteristic decomposition, solving equation B_αθφ_αθ,k＝λ_αθ,kAφ_αθ,k，

Obtaining the characteristic value

And feature vector set

3. The method of point matching between non-rigid three-dimensional models according to claim 2, characterized in that: in the step (2), the wavelet generating kernel function is as follows:

the corresponding scale function generating kernel function is

Where γ is set equal to the maximum value of g (x).

4. The method of point matching between non-rigid three-dimensional models according to claim 2, characterized in that: in step (3), the descriptor at the mesh vertex i is denoted as ASMWD (i),

wherein,

5. the method of point matching between non-rigid three-dimensional models according to claim 1, characterized in that: in the second step, the first step is carried out,

given a grid model X and a grid model Y, calculating an anisotropic spectral manifold wavelet descriptor of each point X and each point Y to obtain a matrix

Selecting time t according to formula

Computing a point-to-point relationship matrix determined by thermokernels

Establishing an optimization objective function for point descriptors and point pair relationships:

and (6) solving.

Images