CN101916284A - 3D Model Retrieval Method Based on Multi-resolution Analysis of Shape Orientation - Google Patents

Abstract

The invention discloses a three-dimensional model retrieval method based on multi-resolution analysis of shape orientation. The orientation sampling plane is obtained by using the principal component analysis method of the orientation of the three-dimensional shape patch; the orientation distribution of the three-dimensional shape is sampled to generate a sampling function of the orientation distribution; analysis The sampling function extracts the multi-resolution low-frequency wavelet coefficients of the sampling function; the feature distance is calculated by an adaptive multi-resolution feature distance calculation method. The invention can improve the accuracy and speed of three-dimensional model retrieval, and can be applied to the fields of three-dimensional model reuse, model recognition, robot vision, virtual reality and the like.

Description

3D Model Retrieval Method Based on Multi-resolution Analysis of Shape Orientation

technical field

The invention relates to a three-dimensional model retrieval method.

Background technique

In the past two decades, with the popularization of computers, the improvement of hardware performance, and the wide application of multimedia recording and shooting equipment, multimedia information has developed rapidly in various fields, making the whole world very rich and colorful. Multimedia information mainly includes sound, image, video and three-dimensional model. At present, massive amounts of multimedia information have been flooded on the Internet and hard disks of individual and industrial users, resulting in explosive growth of information in various media. How to help users find the multimedia information they need in the mass content has become the research object of multimedia matching and retrieval technology. The design and production of each multimedia work requires a lot of effort and a long time. Designers can obtain similar information through multimedia retrieval and information reuse, and slightly modify and create new data to improve work efficiency; robot vision through Multimedia matching retrieves object images and other identification objects in the robot storage body; uses multimedia matching technology to query matching information such as fingerprint database, 2D/3D face database, and 3D skull database in fields such as prevention, verification, and detection; Image matching automatically determines control information, fault types, etc.; in the traffic field, automatic violation records, highway intersection tolls, etc. are carried out through license plate recognition. However, the matching and retrieval of multimedia content is not as simple as the matching and retrieval of text content. Compared with extracting key text information from a piece of text and extracting description information that can represent the image from multimedia such as an image, the latter only has advanced features. Thinking humans can only be fully realized. Extracting the features of multimedia by computer is an extremely complex task, and it is the core technology of multimedia matching and retrieval.

A 3D digital model is a multimedia data type that is richer and more realistic than a 2D image, more in line with human visual characteristics, and more clearly expressing a real 3D object. digital model. In recent years, the continuous update of new 3D shape acquisition equipment, the progress of 3D shape modeling research and the vigorous promotion of 3D modeling tools such as MAYA, 3DMAX, Pro/E, and CATIA have made the design of 3D shapes easier and easier. 3D models have been widely used in multimedia fields, virtual reality, industrial design and manufacturing CAD/CAM, MRI medical 3D images, biomolecular and genetic structures, games, animated characters, human-computer interaction, etc. These wide applications have resulted in the generation of trillions of 3D models every day, and at the same time, they have spread rapidly under the influence of Internet technology, and there is an urgent need for matching and retrieval of 3D models. Moreover, 3D model matching and retrieval technology can be applied to 3D model reuse. Since 3D models require a lot of modeling work, it can help designers quickly find similar models and construct new models based on existing models, saving modeling time. In addition, it can also be applied in multimedia information retrieval, CAD model matching, robot 3D vision, biomolecular and medical organ model matching, mechanical model design support, 3D object recognition and verification, virtual reality scene object matching, animation and game character design support, Lunar and deep space object detection, fault diagnosis and other fields. Research on content-based 3D shape matching and retrieval technology has become very important.

At present, realizing efficient and fast content-based 3D model matching and retrieval technology has become a research hotspot in the field of multimedia information recognition and retrieval at home and abroad. In the published literature at home and abroad, in T.Funkhouser, P.Min, M.Kazhdan, J.Chen, A.Halderman, D.Dobkin, and D.Jacobs, "A search engine for 3Dmodels," ACM Transactions on Graphics, Vol.22, No.1, pp.83-105, 2003. Proposed the use of spherical harmonic functions to analyze the voxelization model, and extracted the harmonic coefficients to describe the characteristics of three-dimensional shapes; H.Laga, H.Takahashi, and M.Nakajima, "Spherical wavelet descriptors for content-based 3D model retrieval," IEEE International Conference on Shape Modeling and Applications, Matsushima, Japan, pp.15-25, Jun.2006. Proposed the use of spherical wavelet coefficients to analyze spherical extension function, and use wavelet coefficients to describe the characteristics of three-dimensional shapes; T.Furuya and R.Ohbuchi, "DenseSampling and Fast Encoding for 3D Model Retrieval Using Bag-of-Visual Features," ACMInternational Conference on Image and Video Retrieval, Santorini, Greece, pp.1-8, Jul.2009. proposed a feature vector dimensionality reduction method for depth buffer maps.

However, the feature extraction method proposed in the above literature has several shortcomings:

(1) The above methods extract shape features by calculating distances. However, when calculating the distance from the shape surface to the centroid, or the depth cache distance from the shape surface to the bounding box, if the centroid or the bounding box changes slightly, the extracted distance function can change greatly, and the stability of the method is poor;

(2) The shape standardization process of some methods adopts the principal component analysis PCA or continuous principal component analysis CPCA method, because the stability of the main axis calculated based on the PCA and CPCA method is not high enough, which affects the subsequent feature extraction method;

(3) Some methods pay less attention to the time complexity of the feature extraction algorithm, which makes the feature extraction time longer, loses the balance between feature extraction accuracy and feature extraction time, and affects real-time online applications.

Contents of the invention

In order to overcome the shortcomings of poor stability, long extraction time and low feature discrimination in the prior art, the present invention provides a three-dimensional shape feature extraction method based on shape-oriented multi-resolution analysis, which increases the stability of the method and ensures the prediction The processing has as little impact on the later feature extraction as possible, which improves the speed of feature extraction and enhances the distinguishing power of features.

The technical solution adopted by the present invention to solve its technical problems comprises the following steps:

(1) Use the principal component analysis method of the three-dimensional shape to obtain the orientation sampling plane: use the principal component analysis method of the three-dimensional shape to obtain the three orientation principal axes, and set six shape orientation sampling according to the three vertical axes plane, the sampling plane constitutes a closure in space, enclosing the three-dimensional shape. This step needs to calculate the normal vector of each surface of the three-dimensional shape and the average normal vector of the three-dimensional shape, and thus form the normal vector covariance matrix. In this matrix, the normal vector of each surface is weighted by area size, according to The eigenvalues of the matrix and the corresponding three eigenvectors are sorted in order of magnitude, so that the sampling plane of the shape orientation is calculated according to the determined three eigenvectors as the orientation axis. The sampling plane satisfies two conditions: (a) each eigenvector determines two sampling planes, the eigenvector is perpendicular to the two sampling planes, and the two sampling planes should be located on both sides of the 3D model and do not intersect with the 3D model , the three eigenvectors determine a total of six sampling planes; (b) the six sampling planes completely surround the 3D model, since the sampling planes will collect the orientation parameters of the 3D shape, the distance between the sampling plane and the 3D model can be set arbitrarily Certainly, this is different from the concept of bounding box.

(2) Sampling the orientation distribution of the three-dimensional shape to generate a sampling function for the orientation distribution: the sampling plane generated by step (1) uniformly emits sampling rays according to a certain order of magnitude, intersects with the surface of the three-dimensional shape, and calculates the sampling rays and the intersecting surface For the inner product of the normal line, the inner product value is used as the function value of the shape orientation function, and the exponential multiple of 2 is used for uniform sampling when sampling, so as to facilitate the analysis of the sampling function by a fast method.

(3) Analyze the sampling function and extract the multi-resolution low-frequency wavelet coefficients of the sampling function: choose a simple and efficient wavelet mother function. Since the orientation function is a regional function, the mother functions such as Daubechies are good at regional operations. Through the mother function Displacement and scale transformation can constitute a group of function bases, and use the function base to decompose the orientation function according to the scale function and wavelet function. For the two-dimensional sampling function, the method of row transformation and then column transformation is used. Dimensionality reduction, obtaining multiple sets of low-frequency wavelet coefficients at multiple resolutions, and the low-frequency wavelet coefficients constitute multi-resolution features.

(4) Calculate the feature distance through the adaptive multi-resolution feature distance calculation method: use the minimum Manhattan distance of the multi-sampling function to calculate the feature distance at a certain resolution between two 3D models, and use the resolution weighting method to calculate all resolutions Rate the characteristic distance of two 3D models. The weighting method adopted is adaptive weighting, using the sample database to maximize the First Tier parameter in the retrieval theory to obtain the optimal multi-resolution feature weighting coefficient. The feature distance is maximized and optimized by this distance measure.

The beneficial effect of the present invention is that: the present invention considers the orientation of the three-dimensional shape, and abandons the traditional method of extracting distance features, thereby increasing the stability of the method. Careful consideration and demonstration have been carried out on the preprocessing stage before the three-dimensional shape feature extraction, and it is found that the preprocessing method based on principal component analysis PCA and continuous principal component analysis CPCA has a certain influence on the subsequent feature extraction, so the present invention proposes a The shape sampling plane is obtained based on the shape-oriented principal component analysis method. Since the principal component of the shape orientation is relatively stable, compared with the preprocessing process of ordinary PCA or continuous principal component analysis CPCA, it has less impact on the later feature extraction. When acquiring the original features, the present invention proposes the shape orientation as the most original analysis object. Compared with the previous method based on distance original features, while enhancing the robustness of feature extraction, the shape orientation can be sampled with few Get a large number of features at a low rate. It adopts the multi-resolution wavelet analysis method to quickly analyze the shape orientation function, which improves the speed of low-frequency feature extraction and is conducive to pushing the method to real-time online applications. The present invention proposes an adaptive multi-resolution feature distance calculation method to ensure that different resolutions have different distance measurement methods, to ensure the maximization and optimization of feature distances, and to improve feature discrimination.

The present invention will be further described below in conjunction with the accompanying drawings and implementation examples.

Description of drawings

Fig. 1 is the system flowchart of three-dimensional model retrieval described in the present invention;

Fig. 2 is the flowchart of three-dimensional model feature extraction of the present invention;

3 is an explanatory diagram of the shape orientation sampling method of the present invention;

Fig. 4 is an explanatory diagram of the acceleration method of the shape orientation sampling method of the present invention;

FIG. 5 is an explanatory diagram of multi-resolution coefficient acquisition towards a sampling function of the present invention.

Detailed ways

The system flowchart of 3D model retrieval is explained in detail as shown in Fig. 1. The technology of the present invention can realize the system function of three-dimensional model network search. The user inputs a 3D model in the query interface and plans to search for all similar models of the model. The retrieval system sends the retrieval request of the model to the search engine through the network, and the search engine responds by sending the retrieved 3D models that meet the requirements to users, and sort the 3D models according to the degree of similarity. The specific process is that when the system receives the retrieval request of the 3D model sent by the client user, it first obtains the feature vector of the 3D model through a feature extraction algorithm. The feature vector can uniquely express a 3D model and has a high degree of discrimination, which can It is different from other 3D models. Feature extraction algorithms analyze shape orientation to obtain multi-resolution features. The system uses an adaptive feature comparison method to calculate the distance between the feature vector and the feature database one by one, and obtains the 3D model in the 3D model database corresponding to the feature database. The 3D model database calculates the features of each model in the database through offline feature extraction, and stores these features in the feature database. Therefore, there is a one-to-one correspondence between the feature database and the 3D model database. This feature extraction work is performed offline and does not take up the time of online operation. The retrieval system generates a similarity ranking based on the results of feature comparison, so that the 3D models are sorted from large to small according to the similarity. The top of the list represents the most similar 3D models. The sorting method can use mature methods such as quick sorting. The retrieval system will return the sorted model list to the client user through the network response. The list is composed of two-dimensional thumbnails, and each thumbnail corresponds to a corresponding three-dimensional model. At the same time, the retrieval time of the algorithm will be returned, and the user can browse to Similar to the 2D thumbnail of the 3D model, when you click the 2D thumbnail, you can see the 3D view of the 3D model, and the 3D view can be used to observe the detailed three-dimensional content of the 3D model by sliding the mouse.

As shown in Fig. 2, the process of feature extraction of the three-dimensional model of the present invention is shown. Firstly, the facet orientation principal component analysis is performed on the 3D model, the three perpendicular principal axes of the facet normal vector of the model are calculated, and six corresponding orientation sampling planes perpendicular to the principal axes are obtained. According to a certain resolution, each facing sampling plane is evenly divided, and the facing sampling ray is emitted from each facing sampling plane, and the heading sampling function is generated, and the multi-resolution analysis is performed on the function to obtain the multi-resolution wavelet coefficient, which is finally used as the heading Multiresolution features. It should be noted that this feature is not a single feature, but contains multiple features with different resolutions.

In conjunction with the accompanying drawings, the specific implementation steps are described in detail below.

1. Obtain the orientation sampling plane by using the facet orientation principal component analysis method of the three-dimensional shape.

In this step, the principal component analysis method of the three-dimensional shape is used to obtain three oriented principal axes, and six shape-oriented sampling planes are set according to the three vertical principal axes. The sampling plane forms a closed space and encloses the three-dimensional shape. . This step needs to calculate the normal vector of each surface of the three-dimensional shape and the average normal vector of the three-dimensional shape, and thus form the normal vector covariance matrix. In this matrix, the normal vector of each surface is weighted by area size, according to The eigenvalues of the matrix and the corresponding three eigenvectors are sorted in order of magnitude, so that the sampling plane of the shape orientation is calculated according to the determined three eigenvectors as the orientation axis. Calculated as follows:

Assuming any three-dimensional shape, there are N patches in total. Take any patch T _i , the surface area is f _i , and the normal vector representing the orientation of the patch is n _{i .} The covariance matrix C is:

$\mathrm{<span\; class="notranslate">\; C</span>}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; f</span>}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; no</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; no</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; )</span>{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; no</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; no</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; T</span>}}$

where f is the total surface area of the three-dimensional shape, expressed as:

$\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}$

where n ₀ is the average normal vector of all patch orientations.

Perform feature operations on the covariance matrix of the shape orientation, the formula is as follows:

Ce _i = λ _i e _i

Find the eigenvalues as follows:

{λ ₁ ,λ ₂ ,λ ₃ }

And the corresponding eigenvectors are as follows:

{e ₁ , e ₂ , e ₃ }

And arrange the eigenvectors according to the order of the eigenvalues from large to small.

According to the determined three eigenvectors, the sampling plane of the shape orientation is calculated, and the sampling plane satisfies two conditions:

(a) Each eigenvector determines two sampling planes, the eigenvector is perpendicular to the two sampling planes, and these two sampling planes should be located on both sides of the 3D model, not intersecting the 3D model, and the three eigenvectors are determined together Out of six sampling planes;

(b) The six sampling planes completely surround the 3D model. Since the sampling planes will collect the orientation parameters of the 3D shape, the distance between the sampling planes and the 3D model can be set arbitrarily, which is different from the concept of a bounding box.

2. Sampling the orientation distribution of the three-dimensional shape and generating a sampling function of the orientation distribution.

The sampling plane generated by step (1) uniformly emits sampling rays according to a certain order of magnitude, intersects with the surface of the three-dimensional shape, calculates the inner product of the sampling ray and the intersecting surface normal, and uses the inner product value as the function value of the shape orientation function , the exponential multiple of 2 is used for uniform sampling in order to facilitate the analysis of the sampling function with a fast method.

The purpose of obtaining the orientation distribution is: the orientation distribution is an important feature of the three-dimensional shape patch set, and humans can distinguish any three-dimensional shape according to the orientation, and the orientation has the representativeness of the three-dimensional shape feature. The orientation feature has the characteristic that it does not change with the sampling distance, which is more robust than the sampling distance function. For example, if a three-dimensional shape changes slightly, the three-dimensional bounding box will change, and the distance of the acquired depth buffer will change, but the sampling orientation is not affected by the distance.

As shown in Figure 3, the specific method is as follows:

(1) Divide each sampling plane into N×N small cubes, then the sampling resolution is N. For fast calculation and analysis convenience, N should be any exponential multiple of 2, such as N=64, and the division should be uniform ;

(2) emit a ray V from the center O of each small cube, intersecting with the first facet of the three-dimensional shape;

(3) Obtain the normal vector L of the first surface, and calculate the vector inner product (L, -V) with the ray normal vector V. The reason for the negative sign here is to reverse the direction of the ray. You can use the right-hand rule to L rotates to -V.

(4) The vector inner product (L, -V) value is assigned to the center of the small cube as a sampling value, and all small cubes are subjected to sampling operations. Both vectors must be prenormalized before assignment.

(5) In this way, an N×N two-dimensional uniform sampling function f(x, y) can be obtained.

The formula of the final two-dimensional sampling function is as follows:

$\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\left[\begin{array}{ccc}{\mathrm{<span\; class="notranslate">\; o</span>}}_{\mathrm{<span\; class="notranslate">\; 0,0</span>}}& <span\; class="notranslate">\; \&CenterDot;</span><span\; class="notranslate">\; \&CenterDot;</span><span\; class="notranslate">\; \&CenterDot;</span>& {\mathrm{<span\; class="notranslate">\; o</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}\\ {\mathrm{<span\; class="notranslate">\; o</span>}}_{\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 0</span>}}& {\mathrm{<span\; class="notranslate">\; o</span>}}_{\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}}& {\mathrm{<span\; class="notranslate">\; o</span>}}_{\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}\\ {\mathrm{<span\; class="notranslate">\; o</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1,0</span>}}& <span\; class="notranslate">\; \&CenterDot;</span><span\; class="notranslate">\; \&CenterDot;</span><span\; class="notranslate">\; \&CenterDot;</span>& {\mathrm{<span\; class="notranslate">\; o</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}\end{array}\right]$

Since there are six sampling planes, the sampling function also consists of six corresponding functions, as follows:

f _o (x, y), ..., f _l (x, y), ..., f _s (x, y), l ∈ [0, 5]

where l represents the lth sampling plane.

In actual operation, the invention designs a sampling acceleration method based on the candidate method, which is shown in FIG. 4 . In the figure, a triangular patch i is randomly selected, and the enclosing surface composed of 6 squares in the sampling plane is calculated. The enclosing surface encloses the triangle at a minimum, and 6 sampling rays that may intersect with it are determined. In Fig. 4, two solid The circle and four rings represent the origins of the 6 rays. This method no longer considers other sampling rays, and directly from the rays emitted by the six sampling points, two rays that actually intersect the triangle face are determined by calculation. The solid circle shown in the figure is the starting point of the two rays. Calculate the sampling inner product value of the corresponding 2 sampling points. This candidate method-based sampling acceleration method can greatly save sampling time.

3. Analyze the sampling function and extract the multi-resolution low-frequency wavelet coefficients of the sampling function.

In this step, a simple and efficient wavelet mother function is selected. Since the orientation function is a regional function, mother functions such as Daubechies are good at regional operations. Through the displacement and scale transformation of this mother function, a set of function bases can be formed. Using the function base and combining According to the scale function and wavelet function, the orientation function is decomposed according to the scale. For the two-dimensional sampling function, the method of row transformation and then column transformation is used to reduce the dimension, and multiple sets of low-frequency wavelet coefficients at multiple resolutions are obtained. , the low-frequency wavelet coefficients constitute multi-resolution features.

The feature of the present invention in processing the sampling function is that low-resolution coefficients are obtained by means of wavelet decomposition to characterize the low-frequency characteristics of the sampling function. There are many ways to obtain low-frequency features, such as Fourier analysis. First, Fourier analysis cannot provide multi-resolution mode, which cannot provide support for the adaptive multi-resolution feature distance calculation in the next step; another important reason is , for two-dimensional functions, the computational complexity of Fourier analysis is O(n ² lgn), however, the computational complexity of wavelet analysis is O(n ² ), choosing Fourier analysis has an advantage in the feature extraction time of the entire 3D model big impact. Therefore, the present invention adopts wavelet decomposition to obtain multi-resolution low-frequency features.

As shown in Figure 5, the specific steps are as follows:

(1) Choose a simple and efficient wavelet mother function. Since the orientation function is a regional function, Daubechies and other mother functions are good at regional operations. Through the displacement and scale transformation of this mother function, a set of function bases can be formed;

(2) Decompose the orientation function according to the scale according to the scale function and wavelet function. Generally, for two-dimensional functions, the method of row transformation and then column transformation is used to reduce the dimension.

(3) Obtain multiple sets of low-frequency wavelet coefficients at multiple resolutions (for example, 4-5). The dimension of each group of wavelet coefficients is 2 ^s ×2 ^s , where s represents the sth resolution. When s=1, it converges to 4 points, which contains too little information, which affects the feature expression. The present invention starts from s=2, and the dimension of the lowest resolution should be 4×4. If s=5 , then the dimension of high resolution should be 32×32, and so on. In practical application, the wavelet low-frequency coefficients under 5 sets of resolutions can be taken out for analysis.

Since there are six sampling planes and corresponding six sampling functions, wavelet decomposition should analyze each sampling function separately.

Fourth, the feature distance is calculated by an adaptive multi-resolution feature distance calculation method.

In this step, the minimum Manhattan distance of the multi-sampling function is used to calculate the feature distance between the two 3D models at a certain resolution, and at the same time, the feature distance of the two 3D models at all resolutions is calculated using a resolution weighting method. The weighting method adopted is adaptive weighting, using the sample database to maximize the First Tier parameter in the retrieval theory to obtain the optimal multi-resolution feature weighting coefficient. The feature distance is maximized and optimized by this distance measure.

In this invention, an adaptive feature distance calculation method is designed mainly for multi-resolution features. This method has different discrimination power according to the features at different resolutions, and improves a certain distance with high discrimination power through adaptive weighting. The proportion of resolution features, thereby improving the distance discrimination of the entire multi-resolution feature.

The specific calculation is as follows:

(1) The minimum Manhattan distance of the multi-sampling function is used to calculate the feature distance between two 3D models at a certain resolution.

Assuming that at any resolution k, the minimum Manhattan distance of the multi-sampling function is used to calculate the distance d _k between two 3D models at this resolution. Among them, l represents the lth sampling plane function, here a total of six sampling planes are used, which can be surrounded by a closed cube. In a specific implementation, 12 or 24 sampling planes can also be used to form a closed dodecahedron or icosahedron, in order to sample all shape orientations without omission. The distance between two 3D models at resolution k is:

d _k = min{d _{k, l} }, l ∈ [0, 5]

_dk takes the closest distance from the distances between all sampled plane functions. The distance between any sampling plane function l of two 3D models at resolution k can be calculated according to the following characteristic distance formula:

d _kl =||V _{1, k, l} -V _{2, k, l} ||

Among them, V _{1, k, l} represent the wavelet low-frequency coefficients of the lth sampling plane of the first 3D model at resolution k _{, and V2, k, l} represent the lth sampling plane of the second 3D model at resolution k The wavelet low-frequency coefficients of . Wavelet low-frequency coefficients can be similar to human vision, so the Manhattan distance is used as the similarity distance measure.

(2) Calculate the characteristic distance of two 3D models by weighting the resolution.

Since the wavelet low-frequency coefficients at different resolutions have different feature discrimination capabilities, how to measure the feature discrimination capabilities at a certain resolution, the present invention designs two distance calculation methods, the first method is a fixed weighting method, for different Different features under the resolution are weighted with a fixed coefficient w _k ; the second method is an adaptive weighting method, which automatically calculates the weight coefficient w _k according to the query content and classification. The disadvantage of the first method is that it does not yield optimal results for all classes of retrieval. In the present invention, the second adaptive weighting method is adopted to perform adaptive weighting on the wavelet coefficient features at different resolutions. The distance formula calculated by the weighting method is as follows:

$\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}$

(3) Using the method of self-adaptive weighting, using the sample database to maximize the First Tier parameter in the retrieval theory.

The calculation method of First Tier is given below. Assuming that there is a 3D model _mi in the sample database D of 3D models, the 3D model belongs to class C _j , the size of the model database is N, the size of class C _j is R, and the 3D model _mi belongs to For class C _j , ie

m _i ∈ C _j

The model is queried in the database, and the query results excluding the object itself are sorted in descending order of distance, that is, the most similar model is ranked first. Now we only care about the model list sorted in the first R-1, R is the dimension of the belonging class, and the purpose of subtracting 1 from R is not to count the object itself. Assuming that there are P models belonging to the same category C _j in the model list of the previous R-1, relative to the model _mi ,

FT _i =P/(R-1)

Where FT _i represents the First Tier parameter value of the model _mi . The ideal First Tier value should be 1.0, which means that when the retrieval object is input, the first R-1 (excluding the input object itself) all belong to the same category, indicating that the feature distance has the most complete discrimination ability. In the case of less than 1.0, the larger the First Tier value, the better, indicating that the distance discrimination ability is stronger.

The First Tier of all models is counted by the above method, and the average value is calculated for the dimension N of the sample database. The average First Tier is,

$\mathrm{<span\; class="notranslate">\; FT</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; FT</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}$

The First Tier parameter in the formula is the calculation result at a certain resolution.

Then calculate the First Tier value at all resolution k, and assign w _k as the weight, thus weighting the distance at resolution k. The expression is as follows:

w _k =FT _k

The final calculation result of this adaptive multi-resolution feature distance calculation method can be expressed as:

$\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; FT</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}$

This adaptive weighting method is used to determine the optimal feature distance distribution. Then, during actual online retrieval, by calculating this characteristic distance between the input model and the 3D model database, similar 3D data models can be sorted.

Claims (6)

1. based on the method for searching three-dimension model of shape orientation multi-resolution analysis, it is characterized in that comprising the steps:

(1) adopt the dough sheet of 3D shape to obtain towards sample plane towards principal component analytical method;

(2) the sampling 3D shape towards distribution, generate towards the sampling function that distributes;

(3) analytical sampling function, the multi-resolution low-frequency wavelet coefficient of extraction sampling function;

(4) by self-adaptation multiresolution features distance calculating method calculated characteristics distance.

2. the method for searching three-dimension model based on shape orientation multi-resolution analysis according to claim 1, it is characterized in that: the dough sheet that described step (1) adopts 3D shape towards principal component analytical method obtain three towards main shaft, and six shape orientation sample plane are set according to these three vertical major, this sample plane spatially constitutes sealing, in 3D shape is enclosed in; This step need calculate each dough sheet of 3D shape towards normal vector and the method for average vector of 3D shape, the normal vector covariance matrix of Gou Chenging thus, in this matrix, normal vector to each dough sheet carries out the weighting of area size, the eigenwert of rank order matrix and corresponding three proper vectors by size, thus according to three proper vectors determining as towards main shaft to calculate the sample plane of shape orientation.

3. the method for searching three-dimension model based on shape orientation multi-resolution analysis according to claim 1, it is characterized in that described sample plane satisfies two conditions: (a) each proper vector is determined two sample plane, this proper vector is vertical with two sample plane, and these two sample plane should lay respectively at the both sides of three-dimensional model, do not intersect with three-dimensional model, three proper vectors are determined six sample plane altogether; (b) in six sample plane are fully enclosed in three-dimensional model and since sample plane will gather 3D shape towards parameter, so sample plane can be set arbitrarily apart from the distance of three-dimensional model.

4. the method for searching three-dimension model based on shape orientation multi-resolution analysis according to claim 1, it is characterized in that: described step (2) is evenly launched the sampling ray by sample plane, intersect with the surface of 3D shape, the inner product of calculating sampling ray and the surface normal that intersects with it, with the functional value of inner product value as the shape orientation function, the index of employing 2 doubly carries out uniform sampling during sampling, is beneficial to adopt fast method that sampling function is analyzed.

5. the method for searching three-dimension model based on shape orientation multi-resolution analysis according to claim 1, it is characterized in that: described step (3) is selected generating functions such as Daubechies, displacement and change of scale by this generating function, constitute one group of function base, utilize function base and according to scaling function and wavelet function to decomposing according to yardstick towards function, for two-dimentional sampling function employing is advanced every trade conversion, carry out the method for rank transformation again and carry out dimensionality reduction, obtain the many groups low frequency wavelet coefficient under a plurality of resolution, the low frequency wavelet coefficient constitutes the feature of multiresolution.

6. the method for searching three-dimension model based on shape orientation multi-resolution analysis according to claim 1, it is characterized in that: described step (4) is utilized the characteristic distance under certain resolution between two three-dimensional models of minimum Manhattan distance calculation of many sampling functions, utilizes the characteristic distance that the resolution method of weighting is calculated following two three-dimensional models of all resolution simultaneously; The method of weighting that is adopted is adaptive weighted, utilizes sample database that the First Tier parameter in the search theory is maximized, to obtain optimum multiresolution features weighting coefficient.

Images