CN102024036B

CN102024036B - Three-dimensional object retrieval method and device based on hypergraphs

Info

Publication number: CN102024036B
Application number: CN201010571681A
Authority: CN
Inventors: 戴琼海; 高跃; 张乃尧
Original assignee: Tsinghua University
Current assignee: Tsinghua University
Priority date: 2010-11-29
Filing date: 2010-11-29
Publication date: 2012-09-05
Anticipated expiration: 2030-11-29
Also published as: CN102024036A

Abstract

The present invention proposes a hypergraph-based three-dimensional object retrieval method and device, wherein the method includes the following steps: calculating the distance matrix between all views of the three-dimensional object in the database; Clustering to obtain multiple clustering results, and constructing multiple hypergraphs corresponding to the three-dimensional objects according to the multiple clustering results; fusing the multiple hypergraphs to form a fused hypergraph, and Analyzing the fused hypergraph, and establishing the association between the three-dimensional objects according to the analysis result; retrieving the three-dimensional object according to the association. Through the method of the present invention, the problem of low retrieval accuracy caused by the complexity of three-dimensional object information is well solved. The method uses hypergraphs to model, and can effectively perform correlation analysis of three-dimensional objects, thereby obtaining More accurate and more effective retrieval results.

Description

Hypergraph-based three-dimensional object retrieval method and device

Technical Field

The invention relates to the technical field of three-dimensional object processing and three-dimensional object analysis, in particular to a three-dimensional object retrieval method based on a hypergraph.

Background

Advances in computer and multimedia technology have accelerated the rapid growth of three-dimensional stereoscopic object data. In recent years, three-dimensional objects have been increasingly used in various fields such as computer-aided manufacturing, virtual reality, medicine, and entertainment, and therefore, a fast and efficient three-dimensional object retrieval method has become more important.

The traditional three-dimensional object description method is mainly based on a virtual model, but when the traditional three-dimensional object description method is applied to representing a real three-dimensional object, a three-dimensional reconstruction process is usually required. Due to the large calculation amount of the three-dimensional reconstruction, the traditional three-dimensional object description method cannot be well applied to the analysis and processing of the real three-dimensional object.

With the rapid development of camera technology, more methods are focused on multi-view based three-dimensional object analysis. The multi-view-based method describes the information of the three-dimensional object through a group of multi-views, and further completes the further work of searching the three-dimensional stereo object and the like.

Since a three-dimensional object contains a large number of multiple views, how to apply multiple views to perform relevance description of the three-dimensional object is a difficult topic. In the method proposed in the european Graphics conference in 2003 (d.y.chen, x.p.tie, y.t.shen, and m.ouhyong.on visual basis based 3d model retrieval. computer Graphics form), a light field Descriptor (Lighting Filed Descriptor) is proposed, which describes an original three-dimensional object by performing data acquisition on a camera array disposed at 20 vertex positions of a regular dodecahedron, obtaining a plurality of sets of views describing spatial structure information of the three-dimensional object from different angles, and on the other hand, matching between three-dimensional stereoscopic objects by performing matching for such a multiview array. The Zernike moments and fourier descriptor features of the view in binary values are used as the features of the view, however, there are fixed setting requirements for the camera array in this approach. 2007 in the Multimedia exchange of the international institute of electrical and electronics engineers (t.f. analysis, m.daoudi, and j.p. vandeborre, "a basic 3-d search engine using adaptive views clustering," ieee transactions on Multimedia, vol.9, No.1, pp.78-88, 2007.) proposes a three-dimensional object retrieval method based on bayesian analysis, where view acquisition also uses a fixed 320 camera array. The method comprises the steps of firstly obtaining 320 original pictures, wherein for the original views, 49-dimensional Zernike moments are selected as image features, firstly carrying out representative view selection from the original views, carrying out K-means iterative clustering by calculating overall similarity between the views, wherein each step tries to re-cluster the existing classification results, and K is selected to be 2. Here, bayesian information preparation is used to determine the clustering effect and the stopping condition, and in the following process, only representative views are applied to a specific retrieval analysis, and the correlation degree between the entire three-dimensional objects is obtained by bayesian probability analysis between the views, thereby completing the view-based retrieval work of the three-dimensional stereoscopic objects.

These conventional view-based three-dimensional object analysis methods mainly perform comparison between three-dimensional objects by performing direct or indirect matching or the like on multiple views of the three-dimensional objects. However, due to the complexity of the three-dimensional object information, the method of directly applying view matching of the three-dimensional object cannot effectively analyze the correlation of the three-dimensional object.

Disclosure of Invention

The object of the present invention is to solve at least one of the above technical drawbacks.

In order to achieve the above object, the present invention provides a method for searching three-dimensional objects based on a hypergraph, which performs correlation analysis between three-dimensional objects by modeling three-dimensional images using the hypergraph.

Therefore, the invention provides a three-dimensional object retrieval method based on a hypergraph, which comprises the following steps: calculating a distance matrix between all views of the three-dimensional object in the database; clustering all the views according to the distance matrix to obtain a plurality of clustering results, and constructing a plurality of hypergraphs corresponding to the three-dimensional object according to the plurality of clustering results; fusing the hypergraphs to form a fused hypergraph, analyzing the fused hypergraph, and establishing the relevance between the three-dimensional objects according to the analysis result; and retrieving the three-dimensional object according to the relevance.

In an embodiment of the present invention, the calculating a distance matrix between all views of the three-dimensional object in the database further comprises: performing feature extraction on all the views by taking Zernike Moments as image features to obtain feature extraction results; and calculating the distance between any two views by applying Euclidean distance according to the feature extraction result until the distance between all the views is calculated, and obtaining a distance matrix between all the views.

In an embodiment of the present invention, the clustering all the views according to the distance matrix to obtain a plurality of clustering results further includes: and clustering all the views by adopting a K-means clustering method, wherein the clustering result is changed according to the difference of the K values.

In an embodiment of the present invention, the constructing a plurality of hypergraphs corresponding to the three-dimensional object according to the plurality of clustering results further includes: and taking the corresponding view set of the three-dimensional objects as a hyper-edge of the hyper-graph, and connecting the vertexes taking each three-dimensional object as the corresponding hyper-graph to form a plurality of hyper-graphs.

In an embodiment of the present invention, the fusing the plurality of hypergraphs to form a fused hypergraph, analyzing the fused hypergraph, and establishing the association between the three-dimensional objects according to the analysis result further includes: performing average fusion on the plurality of hypergraphs to form a fused hypergraph; and analyzing the labels between the vertexes of the fused hypergraph according to a preset objective function to obtain the relevance between any three-dimensional objects in the database, wherein the vertexes meeting the relevance requirement have similar labels.

Another aspect of the present invention further provides an apparatus for three-dimensional object based retrieval, including: a distance matrix calculation module for calculating a distance matrix between all views of a three-dimensional object in a database; the hypergraph construction module is used for clustering all the views according to the distance matrix to obtain a plurality of clustering results and constructing a plurality of hypergraphs corresponding to the three-dimensional object according to the clustering results; the association module is used for fusing the hypergraphs to form a fused hypergraph, analyzing the fused hypergraph and establishing association between the three-dimensional objects according to an analysis result; and a retrieval module for retrieving the three-dimensional object according to the relevance.

In an embodiment of the present invention, the calculating a distance matrix between all views of the three-dimensional object in the database further comprises: performing feature extraction on all the views by taking Zernike Moments as image features to obtain feature extraction results; and calculating the distance between any two views by applying Euclidean distance according to the feature extraction result.

In an embodiment of the present invention, the hypergraph construction module includes a clustering module and a construction module, wherein the clustering module is configured to cluster all the views by using a K-means clustering method, and the clustering result varies according to the difference of the K values; the building module is used for connecting the vertexes of the corresponding hypergraphs which are the three-dimensional objects by taking the corresponding view sets of the three-dimensional objects as the hypergraph edges of the hypergraph so as to form a plurality of hypergraphs.

In an embodiment of the present invention, the association module includes a fusion module and an association establishment module, wherein the fusion module is configured to perform average fusion on the plurality of hypergraphs to form a fused hypergraph; the association establishing module is used for analyzing the labels between the vertexes of the fused hypergraph according to a preset objective function so as to obtain the association between any three-dimensional objects in the database, wherein the vertexes meeting the association requirement have similar labels.

By the method, the defects of low retrieval accuracy, high calculation complexity and the like caused by the complexity of the three-dimensional object information can be effectively overcome. The method carries out modeling through the hypergraph, and can effectively carry out relevance analysis on the three-dimensional object, so that more accurate and more effective three-dimensional object retrieval effect can be obtained.

Additional aspects and advantages of the invention will be set forth in part in the description which follows and, in part, will be obvious from the description, or may be learned by practice of the invention.

Drawings

The foregoing and/or additional aspects and advantages of the present invention will become apparent and readily appreciated from the following description of the embodiments, taken in conjunction with the accompanying drawings of which:

FIG. 1 is a flow chart of a hypergraph-based three-dimensional object retrieval method according to an embodiment of the present invention;

FIG. 2 is a graph showing the comparison of the search result of the method according to the embodiment of the present invention with the search results of the other three search methods, an

FIG. 3 is a block diagram of a hypergraph-based three-dimensional object search apparatus according to an embodiment of the present invention.

Detailed Description

Reference will now be made in detail to all embodiments of the invention, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to the same or similar elements or elements having the same or similar function throughout. The embodiments described below with reference to the drawings are illustrative only and should not be construed as limiting the invention.

The invention provides a hypergraph-based three-dimensional object retrieval method aiming at the defects of poor accuracy and difficult analysis of the existing three-dimensional object retrieval.

The following describes in detail a three-dimensional object retrieval method based on a hypergraph according to an embodiment of the present invention with reference to the drawings.

As shown in fig. 1, which is a flowchart of a method for retrieving a three-dimensional object based on a hypergraph according to an embodiment of the present invention, the method includes the following steps:

step S101, a distance matrix between all views of the three-dimensional object in the database is calculated.

Specifically, Zernike momentas are used as image features of three-dimensional object views in a database, Zernike momentas feature extraction is carried out on the views according to a feature extraction algorithm, so that feature extraction results of all the views are obtained, then, the obtained Zernike momentas feature extraction results are used, Euclidean distances are used as calculation distances, a distance calculation method is applied to the views, the distance between any two views is calculated, and accordingly a distance value between any two views is calculated. Similarly, for all the views, the distance between all the views is calculated by adopting the distance calculation method, so that a distance matrix between all the views is obtained.

And S102, clustering all the views according to the distance matrix to obtain a plurality of clustering results, and constructing a plurality of hypergraphs corresponding to the three-dimensional object according to the plurality of clustering results.

Specifically, all views are clustered by using a K-means clustering method, wherein different clustering results are generated by setting different K values, each three-dimensional object is used as a vertex of a hypergraph on the basis of each group of clustering results, and each view set obtained is used as a hyper-edge of the hypergraph and is used for connecting the vertices of the hypergraph, so that a plurality of hypergraphs are formed.

In specific embodiments of the present invention, such as: g₁＝(V₁，E₁，w₁)，G₂＝(V₂，E₂，w₂)，...G_κ＝(V_κ，E_κ，w_κ) To represent the K hypergraphs obtained, where in a particular embodiment, the value of K may take a positive integer greater than 1. According to a specific embodiment of the invention, for the definition of the hypergraph, H₁，H₂，L H_κIs used to represent G₁＝(V₁，E₁，w₁)，G₂＝(V₂，E₂，w₂)，...G_κ＝(V_κ，E_κ，w_κ) Correlation matrix of hypergraphs, D_v1，D_v2，L D_vκThe vertex degree matrix used to represent the hypergraph, D_e1，D_e2，L D_eκThe edge matrix used to represent the hypergraph is described above.

Wherein, H matrix (with H)_iFor example) the establishment method is as follows:

according to the above formula, when a vertex belongs to a super edge, the corresponding position of the H matrix is 1, otherwise, the corresponding position is 0.

According to the embodiment of the invention, the other two matrixes are established as follows:

d(v_i)＝∑_e∈Eh(v_i，e)；

<math> <mi>d</mi> <mrow> <mrow> <mo>(</mo> <msub> <mi>e</mi> <mi>i</mi> </msub> <mo>)</mo> </mrow> <mo>=</mo> <msub> <mi>Σ</mi> <mrow> <mi>v</mi> <mo>&Element;</mo> <msub> <mi>e</mi> <mi>i</mi> </msub> </mrow> </msub> <mi>h</mi> <mrow> <mo>(</mo> <mi>v</mi> <mo>,</mo> <msub> <mi>e</mi> <mi>i</mi> </msub> <mo>)</mo> </mrow> <mo>.</mo> </mrow> </math>

and S103, fusing the hypergraphs to form a fused hypergraph, analyzing the fused hypergraph, and establishing the relevance between the three-dimensional objects according to the analysis result.

Specifically, all the acquired hypergraphs are fused to form a fused hypergraph. Further, all hypergraphs are fused averagely, namely each hypergraph has the same weight, and then labels among nodes on the hypergraphs are analyzed by applying the set objective function, so that the relevance among any three-dimensional objects in the database is obtained. In an embodiment of the present invention, the three-dimensional object retrieval method requires vertices with more relevance to have similar labels.

In the embodiment of the present invention, let the vector of the label be f, and define the objective function on the fused hypergraph as:

wherein

<math> <mrow> <mi>Ω</mi> <mrow> <mo>(</mo> <mi>f</mi> <mo>)</mo> </mrow> <mo>=</mo> <munderover> <mi>Σ</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>κ</mi> </munderover> <msub> <mi>α</mi> <mi>i</mi> </msub> <munder> <mi>Σ</mi> <mrow> <mi>e</mi> <mo>&Element;</mo> <msub> <mi>E</mi> <mi>l</mi> </msub> </mrow> </munder> <munder> <mi>Σ</mi> <mrow> <mi>u</mi> <mo>,</mo> <mi>v</mi> <mo>&Element;</mo> <mi>e</mi> </mrow> </munder> <mfrac> <mrow> <msub> <mi>w</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>e</mi> <mo>)</mo> </mrow> <msub> <mi>h</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>u</mi> <mo>,</mo> <mi>e</mi> <mo>)</mo> </mrow> <msub> <mi>h</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>v</mi> <mo>,</mo> <mi>e</mi> <mo>)</mo> </mrow> </mrow> <mrow> <mi>δ</mi> <mrow> <mo>(</mo> <mi>e</mi> <mo>)</mo> </mrow> </mrow> </mfrac> <mrow> <mo>(</mo> <mfrac> <mrow> <msup> <mi>f</mi> <mn>2</mn> </msup> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> </mrow> <msqrt> <msub> <mi>d</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> </msqrt> </mfrac> <mo>-</mo> <mfrac> <mrow> <mi>f</mi> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> <mi>f</mi> <mrow> <mo>(</mo> <mi>v</mi> <mo>)</mo> </mrow> </mrow> <msqrt> <msub> <mi>d</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> <msub> <mi>d</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>v</mi> <mo>)</mo> </mrow> </msqrt> </mfrac> <mo>)</mo> </mrow> </mrow> </math>

<math> <mrow> <mo>=</mo> <munderover> <mi>Σ</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>κ</mi> </munderover> <msub> <mi>α</mi> <mi>i</mi> </msub> <mo>{</mo> <munder> <mi>Σ</mi> <mrow> <mi>u</mi> <mo>&Element;</mo> <msub> <mi>V</mi> <mi>i</mi> </msub> </mrow> </munder> <msup> <mi>f</mi> <mn>2</mn> </msup> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> <munder> <mi>Σ</mi> <mrow> <mi>e</mi> <mo>&Element;</mo> <msub> <mi>E</mi> <mi>i</mi> </msub> </mrow> </munder> <mfrac> <mrow> <msub> <mi>w</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>e</mi> <mo>)</mo> </mrow> <msub> <mi>h</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>u</mi> <mo>,</mo> <mi>e</mi> <mo>)</mo> </mrow> </mrow> <mrow> <msub> <mi>d</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> </mrow> </mfrac> <munder> <mi>Σ</mi> <mrow> <mi>v</mi> <mo>&Element;</mo> <msub> <mi>V</mi> <mi>i</mi> </msub> </mrow> </munder> <mfrac> <mrow> <msub> <mi>h</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>v</mi> <mo>,</mo> <mi>e</mi> <mo>)</mo> </mrow> </mrow> <mrow> <mi>δ</mi> <mrow> <mo>(</mo> <mi>e</mi> <mo>)</mo> </mrow> </mrow> </mfrac> </mrow> </math>

<math> <mrow> <mo>-</mo> <munder> <mi>Σ</mi> <mrow> <mi>e</mi> <mo>&Element;</mo> <msub> <mi>E</mi> <mi>i</mi> </msub> </mrow> </munder> <munder> <mi>Σ</mi> <mrow> <mi>u</mi> <mo>,</mo> <mi>v</mi> <mo>&Element;</mo> <mi>e</mi> </mrow> </munder> <mfrac> <mrow> <mi>f</mi> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> <msub> <mi>h</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>u</mi> <mo>,</mo> <mi>e</mi> <mo>)</mo> </mrow> <msub> <mi>w</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>e</mi> <mo>)</mo> </mrow> <msub> <mi>h</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>v</mi> <mo>,</mo> <mi>e</mi> <mo>)</mo> </mrow> <mi>f</mi> <mrow> <mo>(</mo> <mi>v</mi> <mo>)</mo> </mrow> </mrow> <msqrt> <msub> <mi>d</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> <msub> <mi>d</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>v</mi> <mo>)</mo> </mrow> <mi>v</mi> </msqrt> </mfrac> <mo>}</mo> </mrow> </math>

Wherein,

order to

Wherein

Thereby. Can obtain omega (f) ═ f^TΔf。

R_emp(f) For empirical risk, it is defined as follows:

<math> <mrow> <msup> <mrow> <mo>|</mo> <mo>|</mo> <mi>f</mi> <mo>-</mo> <mi>y</mi> <mo>|</mo> <mo>|</mo> </mrow> <mn>2</mn> </msup> <mo>=</mo> <munder> <mi>Σ</mi> <mrow> <mi>u</mi> <mo>&Element;</mo> <mi>V</mi> </mrow> </munder> <msup> <mrow> <mo>(</mo> <mi>f</mi> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> <mo>-</mo> <mi>y</mi> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> <mo>)</mo> </mrow> <mn>2</mn> </msup> </mrow> </math>

where y is the existing label vector and f is the optimized label vector.

Thus, the analysis on the hypergraph is to optimize the following equation:

Φ(f)＝f^TΔf+λ||f-y||²wherein λ > 0.

By the operation, the following results can be obtained:

as can be seen from the results, given a three-dimensional object for retrieval, the corresponding element in y is set to 1, and the other elements are set to 0. Finally, f is obtained as the correlation between other three-dimensional objects in the database and the retrieval object for retrieval.

And step S104, retrieving the three-dimensional object according to the relevance.

In order to clearly understand the method of the present invention, the following detailed description will be made of the searching method of the present invention with reference to specific examples.

[ examples ] A method for producing a compound

This embodiment is a 3D object database based on image collection, which selects National Taiwan University, where each object is represented by 20 images, and a total of 500 objects are selected as an experimental database. In the experiment, each object is taken as an object to be retrieved respectively, retrieval is carried out, and the final comprehensive retrieval effect is analyzed.

Firstly, Zernike Moments are adopted as image features of three-dimensional object views in a 3D object database, Zernike Moments feature extraction is carried out on the views according to a feature extraction algorithm, so that feature extraction results of all the views are obtained, then, the obtained Zernike Moments feature extraction results are used, Euclidean distances are adopted as calculation distances, a distance calculation method is applied to the views, the distance between any two views is calculated, and therefore a distance value between any two views is calculated. Similarly, for all the views, the distance between all the views is calculated by adopting the distance calculation method, so that a distance matrix between all the views is obtained.

Then, all attempts are clustered using a K-means clustering method, wherein different clustering results are generated by setting different K values. In this example, K takes values of 50, 100, 200, 400, 600, 1000, 1500, 2000, and 3000, respectively. And on the basis of each group of clustering results, each object is used as a vertex of the hypergraph, and each obtained view set is used as a hyperedge of the hypergraph and is used for connecting the vertices of the hypergraph, so that a plurality of hypergraphs are formed. Where G is₁＝(V₁，E₁，w₁)，G₂＝(V₂，E₂，w₂)，...G_κ＝(V_κ，E_κ，w_κ) Used to represent the κ hypergraphs obtained. Definition for hypergraphs, H₁，H₂，L H_κ，D_v1，D_v2，L D_vκ，...D_e1，D_e2，L D_eκThe correlation matrix, vertex degree matrix, and edge degree matrix used to represent these hypergraphs.

<math> <mrow> <msub> <mi>h</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>v</mi> <mo>,</mo> <mi>e</mi> <mo>)</mo> </mrow> <mo>=</mo> <mfenced open='{' close=''> <mtable> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mi>if</mi> </mtd> <mtd> <mi>v</mi> <mo>&Element;</mo> <mi>e</mi> </mtd> </mtr> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mi>f</mi> </mtd> <mtd> <mi>v</mi> <mo>&NotElement;</mo> <mi>e</mi> </mtd> </mtr> </mtable> </mfenced> <mo>,</mo> </mrow> </math>

wherein E ∈ E_i。

d(v_i)＝∑_e∈Eh(v_i，e)；

<math> <mrow> <mi>d</mi> <mrow> <mo>(</mo> <msub> <mi>e</mi> <mi>i</mi> </msub> <mo>)</mo> </mrow> <mo>=</mo> <msub> <mi>Σ</mi> <mrow> <mi>v</mi> <mo>&Element;</mo> <msub> <mi>e</mi> <mi>i</mi> </msub> </mrow> </msub> <mi>h</mi> <mrow> <mo>(</mo> <mi>v</mi> <mo>,</mo> <msub> <mi>e</mi> <mi>i</mi> </msub> <mo>)</mo> </mrow> <mo>.</mo> </mrow> </math>

and finally, fusing all the obtained hypergraphs to form a fused hypergraph. Further, all hypergraphs are fused averagely, namely each hypergraph has the same weight, and then labels among nodes on the hypergraphs are analyzed by applying the set objective function, so that the relevance among any three-dimensional objects in the database is obtained. In an embodiment of the present invention, the three-dimensional object retrieval method requires vertices with more relevance to have similar labels.

The specific steps are explained by combining a formula:

let the vector of the label be f, and define the objective function on the fused hypergraph as:

wherein

<math> <mrow> <mi>Ω</mi> <mrow> <mo>(</mo> <mi>f</mi> <mo>)</mo> </mrow> <mo>=</mo> <munderover> <mi>Σ</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>κ</mi> </munderover> <msub> <mi>α</mi> <mi>i</mi> </msub> <munder> <mi>Σ</mi> <mrow> <mi>e</mi> <mo>&Element;</mo> <msub> <mi>E</mi> <mi>i</mi> </msub> </mrow> </munder> <munder> <mi>Σ</mi> <mrow> <mi>u</mi> <mo>,</mo> <mi>v</mi> <mo>&Element;</mo> <mi>e</mi> </mrow> </munder> <mfrac> <mrow> <msub> <mi>w</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>e</mi> <mo>)</mo> </mrow> <msub> <mi>h</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>u</mi> <mo>,</mo> <mi>e</mi> <mo>)</mo> </mrow> <msub> <mi>h</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>v</mi> <mo>,</mo> <mi>e</mi> <mo>)</mo> </mrow> </mrow> <mrow> <mi>δ</mi> <mrow> <mo>(</mo> <mi>e</mi> <mo>)</mo> </mrow> </mrow> </mfrac> <mrow> <mo>(</mo> <mfrac> <mrow> <msup> <mi>f</mi> <mn>2</mn> </msup> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> </mrow> <msqrt> <msub> <mi>d</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> </msqrt> </mfrac> <mo>-</mo> <mfrac> <mrow> <mi>f</mi> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> <mi>f</mi> <mrow> <mo>(</mo> <mi>v</mi> <mo>)</mo> </mrow> </mrow> <msqrt> <msub> <mi>d</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> <msub> <mi>d</mi> <mi>i</mi> </msub> <mrow> <mo>(</mo> <mi>v</mi> <mo>)</mo> </mrow> </msqrt> </mfrac> <mo>)</mo> </mrow> </mrow> </math>

Wherein,

order to

Wherein

Thereby. We can obtain Ω (f) ═ f^TΔf。

R_emp(f) For empirical risk, it is defined as follows:

where y is the existing label vector and f is the optimized label vector.

Thus, the analysis on the hypergraph is to optimize the following equation:

Φ(f)＝f^TΔf+λ||f-y||²wherein λ > 0.

By the operation, the following results can be obtained:

The three-dimensional object search result of the embodiment is shown in fig. 2, which is a comparison graph of the search result of the method applied to the embodiment of the present invention and the search results of the other three search methods. The recall-precision curve is given in fig. 2, the first method 203 calculates the Hausdorff distance (HAUS) in two sets of three-dimensional object views, the second method 204 calculates the MEAN of the sum of all image distances (MEAN) in the two sets of views, and the third method 202 first calculates the minimum distance in each view of the retrieved object from the respective view of the other object and then sums all distances (SumMin). The retrieval method 201(Hypergraph) in the embodiment of the present invention can achieve a better effect on the retrieval effect of the three-dimensional object than the conventional method.

In an embodiment of the present invention, a three-dimensional object retrieving apparatus based on a hypergraph is further provided, and as shown in fig. 3, the structure diagram of the three-dimensional object retrieving apparatus based on a hypergraph according to the embodiment of the present invention is shown. The hypergraph-based three-dimensional object retrieval apparatus 300 includes a distance matrix calculation module 310, a hypergraph construction module 320, an association module 330, and a retrieval module 340. The distance matrix calculation module 310 is configured to calculate a distance matrix between all views of the three-dimensional object in the database; the hypergraph construction module 320 is configured to cluster all the views according to the distance matrix to obtain a plurality of clustering results, and construct a plurality of hypergraphs corresponding to the three-dimensional object according to the plurality of clustering results; the association module 330 is configured to fuse the hypergraphs to form a fused hypergraph, analyze the fused hypergraph, and establish an association between the three-dimensional objects according to an analysis result; the retrieving module 340 is configured to retrieve the three-dimensional object according to the relevance.

Further, the hypergraph construction module 320 includes a clustering module 321 and a construction module 322. The clustering module 321 is configured to cluster all the views by using a K-means clustering method, where the clustering result changes according to the difference of the K values; the building module 322 is configured to connect vertices of the respective hypergraphs with the respective sets of views of the three-dimensional objects as the hypergraphs to form a plurality of hypergraphs.

The association module 330 includes a fusion module 331 and an association establishment module 332. The fusion module 331 is configured to perform average fusion on the plurality of hypergraphs to form a fused hypergraph; the association establishing module 332 is configured to analyze the labels between the vertices of the fused hypergraph according to a preset objective function to obtain the association between any three-dimensional objects in the database, where the vertices meeting the association requirement have similar labels.

The hypergraph-based three-dimensional object retrieval method and the hypergraph-based three-dimensional object retrieval device can change the traditional three-dimensional object correlation method directly based on view matching, perform modeling by applying the hypergraph through the correlation of the bottom view, and further obtain the higher-level correlation of the three-dimensional object by applying the learning on the hypergraph. And the method can effectively avoid the following two problems, wherein the first problem is that when only a few views of the same type of three-dimensional objects are similar, the method of direct matching based on the views can generate wrong results, and the second problem is that when the individual images of two non-same type of objects are very similar, the wrong results can be generated. Of course, the method can more effectively perform the relevance analysis of the three-dimensional object, thereby obtaining a better retrieval result. In addition, the method provided by the invention is simple in design and easy to realize.

Although embodiments of the present invention have been shown and described, it will be appreciated by those skilled in the art that changes, modifications, substitutions and alterations can be made in these embodiments without departing from the principles and spirit of the invention, the scope of which is defined in the appended claims and their equivalents.

Claims

1. A hypergraph-based three-dimensional object retrieval method, characterized in that, comprising the following steps:

Compute the distance matrix between all views of the 3D object in the database;

Clustering all the views according to the distance matrix to obtain multiple clustering results, wherein the K-means clustering method is used to cluster all the views, wherein the clustering results vary according to the K value , and construct a plurality of hypergraphs corresponding to the three-dimensional objects according to the plurality of clustering results, wherein the corresponding view set of the three-dimensional objects is used as a hyperedge of the hypergraph, and each three-dimensional object is used as a hypergraph A vertex of the hypergraph, and each view set obtained is used as a hyperedge of the hypergraph to connect the vertices of the hypergraph to form multiple hypergraphs;

performing average fusion on the plurality of hypergraphs to form a fused hypergraph and each of the plurality of hypergraphs has the same weight, and analyzing the fused hypergraph, and according to the analysis result Establishing the correlation between the three-dimensional objects includes analyzing the labels between the vertices of the fused hypergraph according to a preset objective function, so as to obtain the correlation between any three-dimensional objects in the database, wherein, said vertices satisfying the associativity requirement have similar labels; and

The three-dimensional object is retrieved based on the association.

2. the three-dimensional object retrieval method based on hypergraph as claimed in claim 1, is characterized in that, the distance matrix between all views of three-dimensional object in the described computing database, further comprises:

Using Zernike Moments as an image feature to carry out feature extraction to all views to obtain feature extraction results;

Applying the Euclidean distance to calculate the distance between any two views according to the feature extraction result until the distances between all the views are calculated to obtain the distance matrix between all the views.

3. A hypergraph-based three-dimensional object retrieval device, characterized in that, comprising:

A distance matrix calculation module, the distance matrix calculation module is used to calculate the distance matrix between all views of the three-dimensional object in the database;

A hypergraph building module, the hypergraph building module is used to cluster all the views according to the distance matrix to obtain multiple clustering results, wherein the K-means clustering method is used to cluster all the views , wherein the clustering results vary according to the K value, and multiple hypergraphs corresponding to the three-dimensional objects are constructed according to the multiple clustering results, wherein the corresponding view sets of the three-dimensional objects are used as the hypergraphs The hyperedge of the graph uses each three-dimensional object as a vertex of the hypergraph, and each view set obtained as a hyperedge of the hypergraph is used to connect the vertices of the hypergraph to form multiple hypergraphs;

an associating module, the associating module is used to fuse the multiple hypergraphs to form a fused hypergraph, analyze the fused hypergraph, and establish the relationship between the three-dimensional objects according to the analysis results , wherein the association module includes a fusion module and an association establishment module, wherein the fusion module is used to averagely fuse the multiple hypergraphs to form a fused hypergraph and the multiple hypergraphs Each in the graph has the same weight, and the association building module is used to analyze the labels between the vertices of the fused hypergraph according to a preset objective function, so as to obtain the relationship between any three-dimensional objects in the database. associativity, wherein said vertices satisfying the associativity requirement have similar labels; and

A retrieval module, configured to retrieve the three-dimensional object according to the association.

4. The three-dimensional object retrieval device based on hypergraph as claimed in claim 3, is characterized in that, the distance matrix between all views of the three-dimensional object in the described computing database, further comprises:

Calculate the distance between any two views based on the feature extraction results and the Euclidean distance.