CN101719140B - Graph retrieval method - Google Patents

Abstract

The present invention discloses a graphic retrieval method. The method comprises: (1) performing polygon modeling and pre-establishing a three-dimensional mesh model library; (2) matching the three-dimensional mesh model with a two-dimensional image or graphic; (3) extracting the skeleton of the three-dimensional mesh model; (4) performing three-dimensional model retrieval based on the skeleton; (5) extracting feature points of the three-dimensional mesh model; (6) calculating the control points of the three-dimensional mesh model; (7) calculating the frequency spectrum of the control points of the three-dimensional mesh model; (8) calculating the frequency spectrum similarity, and retrieving the corresponding graphic based on the similarity. The technical solution of the present invention can make retrieval more convenient and support multi-modal retrieval.

Description

A Graphic Retrieval Method

technical field

The invention relates to the technical field of graphic processing, in particular to a graphic retrieval method.

Background technique

The network and computer graphics have gradually penetrated into daily life, and people are no longer satisfied with only seeing two-dimensional images on the Internet. On the other hand, with the increasing maturity of 3D modeling technology and the rapid development of computer software and hardware technology, the number of 3D models has increased dramatically in the last ten years. Compared with two-dimensional images, people can browse their interested parts from any angle, so they are more popular and widely used. The media of 3D graphics cannot be lacked in the research of hot fields such as online game and animation technology, network education technology, key technologies and products of Web-based information services, and database and data mining technology.

Making full use of existing 3D model data resources can greatly reduce the workload of designing new models, and can also promote the circulation of 3D data and its application in various fields. However, how to quickly search for the model you are interested in in the massive 3D model library and build a search engine for the 3D model library is a difficult problem. The graphic retrieval method in the prior art is to classify and retrieve the 3D model according to the geometric content, and the user cannot conveniently express the retrieval requirement through the retrieval interface.

Contents of the invention

The technical problem to be solved by the present invention is to provide a graphic retrieval method, which can overcome the deficiencies of the prior art, realize the multi-modal retrieval of graphics, make retrieval more convenient, perfect the current multimedia search technology and fill the current network three-dimensional graphic search The blank of the engine will promote the realization of the next generation of intelligent multi-modal search engine.

The technical scheme provided by the invention is as follows:

The invention provides a graphic retrieval method, comprising:

1) Establish a 3D grid model library;

2) When the user inputs a 2D graphic or image, match it with the outline of the 3D grid model in the 3D grid model library, project the 3D grid model into a 2D space according to the matching parameters, and obtain the projected 2D images or graphics, and then calculate the correlation between the projected two-dimensional image or graphics and the input graphics or images, and retrieve the three-dimensional grid model according to the correlation;

3) When the user input is a 3D mesh model, the skeleton of the input 3D mesh model is extracted, and according to the extracted 3D mesh model skeleton, the 3D mesh model is initially retrieved in the 3D mesh model library;

4) Extract the feature points from the retrieved 3D mesh model and the 3D mesh model input by the user, replace the original 3D mesh model, and then perform triangulation, and perform segmental fitting on the segmented dividing line to obtain The control points of the original 3D mesh model, and then perform frequency domain transformation on the control points according to the topology;

5) Calculate the similarity between the frequency domain coordinates of the control points of the 3D grid model input by the user and the frequency domain coordinates of the control points of the 3D grid model in the 3D grid model library, and retrieve the corresponding graphics;

Wherein, step 4) carries out frequency-domain transformation to the obtained control points according to the topological structure of the three-dimensional grid model, including:

(1) Sort the control points of the rough grid with the modulus of the vector from the control point to the center of the grid;

(2) Obtain the Kirchhoff matrix from the grid topological relationship

K＝D-A (6)

D is a diagonal matrix, the element Dii on the diagonal corresponds to the valence of the vertex vi, and A is the adjacency matrix of the grid;

The n eigenvectors w _i obtained by performing eigenvalue decomposition on the Kirchhoff matrix are arranged in ascending order to form an n*n mapping matrix W;

(3) Construct 3 vectors from the spatial coordinates of the previously sorted n control points:

X = (x ₁ , x ₂ , ..., x _n ), Y = (y ₁ , y ₂ , ..., y _n ), Z = (z ₁ , z ₂ , ..., z _n ) (8)

Project these 3 vectors onto the eigenvector base W to get the frequency domain vector:

$\left\{\begin{array}{c}{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; WX</span>}\\ {\mathrm{<span\; class="notranslate">\; Y</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; WY</span>}\\ {\mathrm{<span\; class="notranslate">\; Z</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; WZ</span>}\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 9</span>}<span\; class="notranslate">\; )</span>$

The formula for calculating the magnitude S _i of the frequency spectrum corresponding to each vertex is:

${\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; =</span>\sqrt{{<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; Y</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; Z</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 11</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; .</span>$

Preferably, the 3D mesh model library in step 1) is obtained after reorganizing various 3D data formats and polygon modeling.

Preferably, the skeleton extraction process is as follows: firstly establish a progressive grid representation for the input grid model, and then continuously perform edge collapse transformation on the progressive grid, if an edge does not have adjacent triangles during the collapse process, then the The edges are marked as skeleton edges and are kept until the end of the collapse, and the resulting edges constitute the skeleton of the model.

Preferably, in step 4), for the retrieved 3D grid model and the 3D grid model input by the user, feature point extraction is performed according to their spatial shapes, and the original 3D grid model is replaced with umbilical cord points as feature points.

Preferably, in step 4), the three-dimensional mesh model is triangulated according to the feature points, and the segmentation line after segmentation is fitted in segments to obtain segmentation points, and these segmentation points are used as control points of the original three-dimensional mesh model .

The present invention has the following beneficial effects:

(1) Three-dimensional graphics can be retrieved according to a single two-dimensional image, and the user can input pictures in common formats such as bmp, jpeg, tiff, etc., and the corresponding graphics can be retrieved through the method of the present invention.

(2) The representation method of the input 3D model is more extensive, and it is applicable to triangular mesh data, point cloud data, volume data or polygonal mesh models.

(3) Hierarchical search is adopted, which is faster and more accurate. Firstly, a rough search is carried out according to the skeleton of the 3D graphics, and other feature extraction techniques are used to accurately search the 3D graphics in the search results, which ensures real-time performance and accuracy.

Description of drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present invention or the prior art, the following will briefly introduce the drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only These are some embodiments of the present invention. Those skilled in the art can also obtain other drawings based on these drawings without creative work.

Fig. 1 is a schematic diagram of the processing of user inputting two-dimensional graphics or images;

Fig. 2 is the matching flowchart of three-dimensional and two-dimensional;

FIG. 3 is a flowchart of processing when a user inputs three-dimensional grid data.

Detailed ways

The following will clearly and completely describe the technical solutions in the embodiments of the present invention with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some, not all, embodiments of the present invention. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without creative efforts fall within the protection scope of the present invention.

The method of the present invention mainly studies the multi-modal retrieval of graphics, and its principle is to calculate the similarity between the graphics input by the user or the graphics and the three-dimensional graphics through information such as two-dimensional images, two-dimensional graphics, and three-dimensional models according to the characteristics of three-dimensional graphics , so as to realize the multi-modal retrieval of 3D graphics. Multimodal here refers to supporting users to query in common formats of 2D images, 2D graphics and 3D models.

Aspects of the present invention extract a small amount of data from the three-dimensional data, and use it as the main feature of the corresponding graphic or image, which can be retrieved based on the main feature. This feature is basically not affected by factors such as noise, similarity transformation, and different resolution sampling.

The inventive method mainly comprises following 8 links:

(1) First, reorganize the 3D model data in various data formats, perform polygon modeling, obtain a 3D mesh model, and establish a 3D mesh model library.

(2) When the user inputs a 2D graphic or image, match it with the outline of the 3D mesh model in the 3D mesh model library, and then project the 3D mesh model into the 2D space according to the matching parameters to obtain the projected The two-dimensional image or figure, and then calculate the correlation degree between the projected two-dimensional image or figure and the input figure or image, and retrieve the three-dimensional grid model according to the correlation degree.

(3) When the user inputs a 3D grid model, the skeleton is extracted from the input 3D grid model.

(4) According to the skeleton of the extracted 3D mesh model, a rapid preliminary search is performed in the 3D mesh model database, and the 3D mesh model retrieved initially is obtained.

(5) According to the graphics theory, the 3D grid model retrieved initially and the 3D grid model input by the user are extracted according to their spatial shape to replace the original 3D grid model, greatly reducing the amount of data.

(6) Triangulate the 3D mesh model according to the extracted feature points, and perform segment fitting on the segmented dividing line to obtain segmentation points, which are used as the control points of the original 3D mesh model.

(7) According to the topological structure of the three-dimensional grid model, the control points are transformed in the frequency domain to obtain the frequency domain coordinates of the control points.

(8) Calculate the similarity between the frequency domain coordinates of the control points of the 3D grid model input by the user and the frequency domain coordinates of the control points of the 3D grid model in the 3D grid model library, and retrieve the corresponding graphics.

Technical characteristics of the present invention are mainly embodied as follows:

(1) The system can retrieve 3D graphics from a single 2D image. Users can input pictures in common formats such as bmp, jpeg, tiff, etc., and the system will segment the object from the picture and extract contour information, match it with the 3D graphics in the 3D mesh model library, and return the matched 3D mesh model to the user.

(2) The system supports a wider range of representation methods for the input 3D model. Triangular mesh data, point cloud data, volume data or polygonal mesh models are all suitable.

(3) The system adopts hierarchical search. Firstly, a rough search is carried out according to the skeleton of the 3D graphics, and then the 3D graphics in the search results are searched accurately by using the feature extraction technology, which ensures real-time and accuracy.

The present invention will be described in further detail below.

The main steps of the graphic retrieval method supporting multimodality of the present invention include:

(1) Carry out polygonal modeling and establish a three-dimensional grid model library in advance;

(2) Matching of 3D grid model and 2D image or graph;

(3) Extraction of the skeleton of the three-dimensional mesh model;

(4) Retrieve the 3D model according to the skeleton;

(5) Feature point extraction of 3D mesh model;

(6) Calculation of the control points of the 3D mesh model;

(7) Calculation of the frequency spectrum of the control points of the three-dimensional grid model;

(8) Calculate the frequency spectrum similarity, and retrieve the corresponding graphics according to the similarity.

The above steps are described in detail below.

(1) Carry out polygonal modeling and establish a 3D mesh model library in advance.

According to the three-dimensional grid model data, the invention performs polygonal modeling to construct a polygonal three-dimensional grid model. Polygonal modeling is carried out by using many polygonal simulated surfaces. The more polygons, the closer the model is to the real surface. Polygonal modeling is the most extensive and easy-to-implement modeling technique, and can obtain high-precision models, usually in the form of triangular meshes.

For the convenience and unity of the following description, the definition of the three-dimensional grid model is given using mathematical symbols. The grid model M={V, C} is composed of a vertex set V and a connection relationship set C, where the set V contains N vertices v _i and the coordinate value of each vertex is determined by (xi _, y _i , zi ₎ ,Right now

V={v _i }, i=0, 1, . . . , N-1, v _i =(x _i , y _i , z _i ) (1)

And the connection relationship set C is expressed as

C={{i _k , j _k }} _k=0,...m-1 , 0≤i _k ≤N-1, 0≤j _k ≤N-1 (2)

Here {i _k , j _k } denotes the k-th edge determined by the i _k -th vertex and the j _k- th vertex.

(2) Matching of 3D mesh model and 2D image or graph

FIG. 1 is a schematic diagram of a process for a user to input two-dimensional graphics or images.

As shown in Figure 1, for a single image/graphic, contour matching is performed with the model library graphics, followed by 2D projection, and then graphic matching correlation calculation.

In many cases, the user's retrieval input is a two-dimensional image or graph, and the specific process of matching with the three-dimensional mesh model is shown in Figure 2. First, the present invention uses the profile of the image (or graphic profile) to perform initial matching with the profile of the 3D grid model in the 3D grid model library; after the profile is matched, the obtained 3D grid model is projected into the 2D space according to the matching parameters, The projection image is obtained, and then the image correlation matching method is used for further precise matching.

All grid models in the 3D grid model library have completed contour extraction and projection calculation in the three positive directions of X, Y, and Z.

For the three-dimensional grid model, the method of the present invention traverses each edge in the grid to extract the outline, and the specific method is as follows:

1. If the current edge is connected with only one triangle, then it belongs to the contour;

和

，当前镜头位置与当前边的一个顶点之间的向量为

。如果，即和

相对于镜头的轴处于不同的方向，说明F₁和F₂一个正对着镜头一个背对着镜头，因此当前边为轮廓边，否则，当前边不是显著的轮廓边。2. If the current side is connected to two triangles F ₁ and F ₂ , then define their normal vectors as

and

, the vector between the current camera position and a vertex of the current edge is

. if ,Right now and

The axes relative to the camera are in different directions, indicating that F ₁ and F ₂ are facing the camera and facing away from the camera, so the current edge is a silhouette edge, otherwise, the current edge is not a significant silhouette edge.

For graphics, no contour extraction process is required.

For images, operators such as Sobel and Prewitt can be used to extract contours.

The contour matching process of the present invention can adopt a matching method based on corresponding shapes, such as Hausdoff distance; or a polygon decomposition matching method, such as performing line segment processing, and performing triangulation with the center of gravity of the contour as the center, determining the boundary vertices, and connecting them to form a convex polygon , use this convex polygon to approximate the original graphics, and connect the center of gravity of the polygon with the vertices to form a series of triangles to match the outline of the graphics. The contour matching process is simple and efficient, enabling quick initial retrieval.

The image correlation matching method of the present invention is to calculate the correlation degree between the two-dimensional image or figure projected by the three-dimensional grid model and the input figure or image, such as using the normalized correlation measure to calculate the similarity of each pair of pixels in the image area . For the two images I ₁ (x, y) and I ₂ (x, y) to be matched, the normalized correlation measure at the position (i, j) of the image to be detected is defined as:

$\mathrm{<span\; class="notranslate">\; \&rho;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\underset{\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; I</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>{\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; I</span>}}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&CenterDot;</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; I</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>{\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; I</span>}}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; )</span>}{\sqrt{\underset{\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; I</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>{\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; I</span>}}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}\underset{\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; I</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>{\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; I</span>}}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}}$

When the correlation is greater than a set threshold, a matching 3D mesh model is retrieved.

(3) Extraction of 3D mesh model skeleton

Skeleton is an excellent graphic geometric feature, also known as Medial Axis, which is an effective means of graphic description. As the name implies, the skeleton is a linear geometry, located at the symmetrical center of the graph, having the same topology as the original graph, and retaining the shape information of the original graph.

FIG. 3 is a flowchart of processing when a user inputs three-dimensional grid data.

The process of Fig. 3 comprises following process, namely (3) extraction of 3D grid model skeleton; (4) carry out 3D model retrieval according to skeleton; (5) 3D grid model feature point extraction; (6) 3D grid model control (7) Calculate the frequency spectrum of the control points of the three-dimensional grid model; (8) Calculate the similarity of the spectrum, and retrieve the corresponding graphics according to the similarity. Refer to the description below for specific content.

The present invention designs a fast skeleton extraction algorithm based on multi-resolution grids: first, a progressive grid representation is established for the 3D grid model, and then the progressive grid is continuously collapsed and transformed. If an edge has no adjacent triangles, then this edge is marked as a skeleton edge and is kept until the end of the collapse, and the resulting edge constitutes the skeleton of the mesh model. All mesh models in the 3D mesh model library have completed skeleton extraction calculations. The skeleton needs to be extracted when the user inputs the mesh model.

(4) 3D model retrieval based on the skeleton

Skeleton extraction is the process of converting 3D graphics into 3D line segments. Compared with the original 3D graphics, the data volume of 3D line segments is greatly reduced, so the retrieval speed can be accelerated.

The 3D grid model input by the user is compared with the grid model in the library. The PCA analysis method is used to compare the skeleton. First, the skeleton is positioned, and the distance of the skeleton is calculated in sections. As a result of information comparison, the one with the smallest Euclidean distance difference is the 3D mesh model for preliminary retrieval.

(5) Feature point extraction of 3D mesh model

According to the graphics theory, the 3D grid model input by the user is extracted according to its spatial shape to replace the original 3D grid model, which greatly reduces the amount of data. All grid models in the 3D grid model library have completed feature point extraction and control point spectrum calculation.

The present invention uses umbilical cord points as feature points of any triangular three-dimensional mesh model. Using the umbilical cord points as the feature points on the surface of the 3D mesh model has strong robustness against the effects of different acquisition devices such as noise, shearing, rotation, translation, scaling, and different resolution sampling. Since the curvature across the edge of the mesh model is large, a curvature tensor can be defined for each point of the edge of the mesh model. In any grid region B, the curvature tensor of a fixed point v can be estimated by the following formula:

$\mathrm{<span\; class="notranslate">\; T</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{<span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; B</span>}<span\; class="notranslate">\; |</span>}\underset{\mathrm{<span\; class="notranslate">\; e</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; B</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}\mathrm{<span\; class="notranslate">\; \&beta;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; e</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; e</span>}<span\; class="notranslate">\; \&cap;</span>\mathrm{<span\; class="notranslate">\; B</span>}<span\; class="notranslate">\; |</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}{\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}}^{\mathrm{<span\; class="notranslate">\; T</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; )</span>$

是沿着边e的单位法向量。v的邻接区域B是由以v为球心，以r为半径的球体与网格模型的相交圆定义的。半径r是指定曲率估计的尺度参数。where |B| is the area of the neighborhood of v, β(e) is the angle between the normal vectors of two adjacent triangles of side e, |e∩B| is the length of side e in region B,

is the unit normal vector along edge e. The adjacency area B of v is defined by the intersecting circle between the sphere with v as the center and the radius r as the mesh model. The radius r is a scale parameter specifying the curvature estimate.

After obtaining the curvature tensor of each vertex, linear interpolation is performed on each triangle mesh to obtain a continuous curvature tensor field. The normal vector direction of the vertex corresponds to the eigenvalue with the smallest magnitude of the curvature tensor, and the other two eigenvalues correspond to the minimum curvature and maximum curvature of the vertex v respectively. When these two eigenvalues are equal, the vertex v is called the umbilical cord Points are the feature points of the 3D mesh model used in the present invention.

Obviously the key to curvature estimation is the scale parameter. The present invention uses different scales to estimate the curvature tensor, so as to smooth the tensor field and estimate the robustness of umbilical points at different scales to factors such as noise and affine transformation. In order to avoid loss of local information on the surface of the mesh model and reduce computational complexity, the scale parameter should not be too large. In the present invention, when searching for the scale parameter with the highest robustness, an adaptive genetic algorithm is selected as an optimization search technique. Among the scale parameters with the highest robustness, we choose the point that maximizes the average curvature in region B, that is, the point where the trace of the curvature tensor is the largest.

(6) Calculation of control points of 3D mesh model

According to the extracted feature points, the 3D mesh model is triangulated, and the segmented dividing lines are segmented and fitted to obtain the segmentation points, which are used as the control points of the original 3D mesh model.

After obtaining the feature points, the next task is to reduce the amount of data, which is very important for feature registration and retrieval of 3D mesh models.

After obtaining the feature points, the first step is to triangulate the mesh. In 2D space, Delaunay triangulation can produce triangles with uniform shape and uniqueness. In 3D surfaces, Delaunay triangulation uses geodesic distance instead of Euclidean distance (geodesic distance refers to the shortest distance along the surface between two vertices of a mesh surface in 3D space). The present invention uses the wave front method to estimate the entire Voronoi diagram and its double Delaunay triangulation. The advantage of adopting this method is that the triangulation is not affected by the size of the sampling rate. The wavefront is obtained by calculating the intersection circle of a sphere with increasing radius and the surface of the 3D mesh with the seed point as the center. The wavefront method based on different sphere radii gives better results than the wavefront method based on mesh topology.

(7) Calculation of control point spectrum of 3D grid model

According to the topological structure of the three-dimensional mesh model, the control points are transformed in the frequency domain to obtain the frequency domain coordinates of the control points.

Since the 3D grid is a graph rather than an image, each vertex coordinate does not have its own image function, so the transformation domain processing of the 3D grid must first construct an image function in order to apply the classic transformation domain processing algorithm to 3D Grid handling.

First, sort the control points. The invention sorts the control points of the coarse grid by the modulo of the vector from the control point to the center of the grid.

The coordinates defining the center of the grid are

${\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; g</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; g</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; g</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; z</span>}}_{\mathrm{<span\; class="notranslate">\; g</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; )</span>$

The magnitude of the vector from each control point to the center of the grid is defined as follows

${\mathrm{<span\; class="notranslate">\; \&rho;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; =</span>\sqrt{{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; g</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; g</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; z</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; z</span>}}_{\mathrm{<span\; class="notranslate">\; g</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; )</span>$

After the control points are arranged in ascending order according to the modulus, the frequency domain transformation is started. First, the combined Laplacian or Kirchhoff matrix is obtained from the grid topology. The matrix is defined as follows:

K＝D-A (6)

Among them, D is a diagonal matrix, and the element Dii on the diagonal corresponds to the valence of the vertex vi (the valence is the number of edges radiating from the vertex), A is the adjacency matrix of the grid, and its elements are defined as follows :

For a grid model with n control points, the dimensions of matrices A, D and K are n*n. Decompose the eigenvalues of the Kirchhoff matrix to obtain n eigenvalues λ _i and n eigenvectors w _i . Arrange the n eigenvectors in ascending order to obtain their corresponding eigenvectors, and these sorted eigenvectors are function bases with increasing frequency. This function base depends only on the topology of the mesh model and has nothing to do with the geometric properties of the mesh model. Denote the n*n mapping matrix composed of n sorted eigenvectors as W.

Construct 3 vectors from the previously sorted spatial coordinates of n control points:

X = (x ₁ , x ₂ , ..., x _n ), Y = (y ₁ , y ₂ , ..., y _n ), Z = (z ₁ , z ₂ , ..., z _n ) (8)

By projecting these three vectors onto the eigenvector base W, the frequency-domain decomposition vector of the spatial coordinates can be obtained:

$\left\{\begin{array}{c}{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; WX</span>}\\ {\mathrm{<span\; class="notranslate">\; Y</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; WY</span>}\\ {\mathrm{<span\; class="notranslate">\; Z</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; WZ</span>}\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 9</span>}<span\; class="notranslate">\; )</span>$

The spatial coordinates can also be obtained by restoring the frequency coordinates:

$\left\{\begin{array}{c}\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; W</span>}}^{<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}\\ \mathrm{<span\; class="notranslate">\; Y</span>}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; W</span>}}^{<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; Y</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}\\ \mathrm{<span\; class="notranslate">\; Z</span>}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; W</span>}}^{<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; Z</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 10</span>}<span\; class="notranslate">\; )</span>$

The magnitude S _i of the spectrum corresponding to each vertex can be calculated by the following formula:

${\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; =</span>\sqrt{{<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; Y</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; Z</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 11</span>}<span\; class="notranslate">\; )</span>$

(8) Calculate the frequency spectrum similarity, and retrieve the corresponding graphics according to the similarity.

Calculate the correlation between the control point frequency domain coordinates of the 3D grid model input by the user and the control point frequency domain coordinates of the 3D grid model in the library, and retrieve the corresponding graphics according to the correlation.

When comparing the similarity of two grid models, it is judged by comparing the waveform similarity of the frequency domain coefficients. A criterion when comparing similarities can be the normalized correlation coefficient:

in is the spectrum value calculated from the 3D mesh model input by the user, is the 3D grid spectrum value in the library. The larger the NC, the more correlated the spectral coefficients are.

Given a threshold T, if NC>T, it is considered that the 3D grid input by the user matches the 3D grid in the library, and the retrieval process ends.

The present invention has the following beneficial effects:

(1) Three-dimensional graphics can be retrieved according to a single two-dimensional image, and the user can input pictures in common formats such as bmp, jpeg, tiff, etc., and the corresponding graphics can be retrieved through the method of the present invention.

(2) The representation method of the input 3D model is more extensive, and it is applicable to triangular mesh data, point cloud data, volume data or polygonal mesh models.

(3) Hierarchical search is adopted, which is faster and more accurate. Firstly, a rough search is carried out according to the skeleton of the 3D graphics, and other feature extraction techniques are used to accurately search the 3D graphics in the search results, which ensures real-time performance and accuracy.

Those of ordinary skill in the art can understand that all or part of the steps in the various methods of the above-mentioned embodiments can be completed by instructing related hardware through a program, and the program can be stored in a computer-readable storage medium, and the storage medium can include: Read Only Memory (ROM, Read Only Memory), Random Access Memory (RAM, Random Access Memory), disk or CD, etc.

The above is a detailed introduction to a graphic retrieval method provided by the embodiment of the present invention. In this paper, specific examples are used to illustrate the principle and implementation of the present invention. The description of the above embodiment is only used to help understand the present invention. method and its core idea; at the same time, for those of ordinary skill in the art, according to the idea of the present invention, there will be changes in the specific implementation and application scope. Invention Limitations.

Claims (5)

1. a figure retrieving method is characterized in that, comprising:

1) sets up the three-dimensional grid model storehouse;

2) when user input be X-Y scheme or image the time; Mate with the profile of three-dimensional grid model in the three-dimensional grid model storehouse; According to matching parameter three-dimensional grid model is projected to two-dimensional space; Obtain the two dimensional image or the figure of projection, calculate two dimensional image or the figure of figure and input or the degree of correlation between the image that projection obtains then, retrieval obtains three-dimensional grid model according to the degree of correlation;

3) when user input be three-dimensional grid model the time, the three-dimensional grid model of input is carried out skeletal extraction, according to the three-dimensional grid model skeleton that extracts, preliminary search obtains three-dimensional grid model in the three-dimensional grid model storehouse;

The three-dimensional grid model of the three-dimensional grid model that 4) retrieval is obtained and user's input carries out feature point extraction; Replace original three-dimensional grid model; Carry out triangulation again; Cut-off rule behind the subdivision is carried out piecewise fitting, obtain the reference mark of original three-dimensional grid model, according to topological structure frequency domain transform is carried out at the reference mark then;

5) user who calculates imports the similarity between the reference mark frequency domain coordinate figure of reference mark frequency domain coordinate figure and the three-dimensional grid model in the three-dimensional grid model storehouse of three-dimensional grid model, goes out graph of a correspondence according to similarity retrieval;

Wherein, the topological structure according to three-dimensional grid model in the step 4) carries out frequency domain transform to the reference mark that obtains, and comprising:

(1) with the mould of reference mark sorted in the reference mark of coarse grids to the vector of grid element center;

(2) obtain the Kirchhoff matrix from the network topology relation

K＝D-A (6)

D is a diagonal matrix, and the element Dii on its diagonal line is corresponding with the valency of vertex v i, and A is the adjacency matrix of grid;

The Kirchhoff matrix is carried out n the proper vector w that characteristic value decomposition obtains _iCarry out ascending order and arrange the n*n mapping matrix W of composition;

(3) 3 vectors of the volume coordinate at sorted n reference mark structure before before:

X＝(x ₁，x ₂，…，x _n)，Y＝(y ₁，y ₂，…，y _n)，Z＝(z ₁，z ₂，…，z _n)?(8)

These 3 vector projections are obtained frequency domain vector to the proper vector base W:

$\left\{\begin{array}{c}{X}_s=\mathrm{WX}\\ Y_s=\mathrm{WY}\\ Z_s=\mathrm{WZ}\end{array}\right.---\left(9\right)$

The amplitude S of the frequency spectrum that each summit is corresponding _iComputing formula is:

$S_i=\sqrt{{\left|\right|X_s\left|\right|}^2+{\left|\right|Y_s\left|\right|}^2+{\left|\right|Z_s\left|\right|}^2}---\left(11\right).$

2. figure retrieving method according to claim 1 is characterized in that:

Three-dimensional grid model storehouse in the step 1) to various three-dimensional data forms reorganize with the polygon modeling after obtain.

3. figure retrieving method according to claim 1 and 2 is characterized in that:

The skeletal extraction process is: at first set up progressive grid representation for the grid model of input; Then progressive grid is constantly carried out the limit conversion of collapsing; If a limit does not have adjacent triangle in the process of collapsing; Then this limit is labeled as the skeleton limit, and remains into the end of collapsing always, the skeleton of the final limit component model that obtains.

4. figure retrieving method according to claim 1 and 2 is characterized in that:

The three-dimensional grid model of the three-dimensional grid model that obtains for retrieval in the step 4) and user's input carries out feature point extraction according to its spatial form, replaces original three-dimensional grid model with umbilical cord point as unique point.

5. figure retrieving method according to claim 1 and 2 is characterized in that:

According to unique point three-dimensional grid model is carried out triangulation in the step 4), the cut-off rule behind the subdivision is carried out piecewise fitting, obtain cut-point, with the reference mark of these cut-points as original three-dimensional grid model.

Images