CN105243137B - A kind of three-dimensional model search viewpoint selection method based on sketch - Google Patents

Abstract

The invention discloses a sketch-based three-dimensional model retrieval viewpoint selection method, comprising the following steps: step 1, manually classifying the models in the database; step 2, determining the complete collection of viewpoints by triangulating the icosahedron Step 3, calculate the entropy value of each model at each viewpoint; Step 4, determine the number of viewpoints of each type of model by the calculation result of step 3; Step 5, cluster the complete set of viewpoints by the calculation result of step 4 Operation, determine the selected viewpoint; step 6, generate a two-dimensional projection view according to the viewpoint generated in step 5. The invention has the advantages of good matching results, effectively improving the operating efficiency of the system and the like.

Description

A Viewpoint Selection Method for 3D Model Retrieval Based on Sketch

technical field

The invention relates to a sketch-based three-dimensional model retrieval technology in the field of computer image processing, in particular to a sketch-based three-dimensional model retrieval viewpoint selection method, which is mainly applied to viewpoint selection in the sketch-based three-dimensional model retrieval.

Background technique

At present, in the field of viewpoint selection in sketch-based 3D model retrieval, there are mainly two strategies for viewpoint selection. One is to use a preset fixed viewpoint as the common viewpoint for all models. Shao et al. proposed in "Discriminative Sketch-Based 3D Model Retrieval Through Robust Model Matching": a method for matching 3D models based on 7 fixed viewpoints. The advantage of this method is obvious. Whether it is a ball model or a person model, it will use a predefined viewpoint for matching. During the matching process, it can reduce the amount of calculation in viewpoint selection, which is helpful Improve the operating efficiency of the system. But its shortcomings are also obvious, ignoring the different requirements of different models for the number of viewpoints and viewpoint positions, not every viewpoint can well reflect the characteristics of the model, and fixed viewpoints will affect the matching results to a certain extent.

Another viewpoint selection strategy is to match sketches with viewpoints generated by viewpoint clustering. Currently, there is little research work based on this strategy.

Contents of the invention

The purpose of the present invention is to overcome the shortcomings and deficiencies of the prior art, and provide a method for selecting a viewpoint for 3D model retrieval based on sketches. The method of clustering viewpoints is used for viewpoint selection.

The object of the present invention is achieved through the following technical solutions: a sketch-based three-dimensional model retrieval viewpoint selection method, comprising the following steps:

Step 1. Manually classify the models in the database;

Step 2, determine the complete set of viewpoints by triangulating the icosahedron;

Step 3, calculating the entropy value of each model at each viewpoint;

Step 4, determine the number of viewpoints of each type of model by the calculation result of step 3;

Step 5, performing a clustering operation on the complete set of viewpoints based on the calculation results in step 4, to determine the selected viewpoint;

Step 6. Generate a two-dimensional projection view according to the viewpoint generated in step 5.

Compared with the prior art, the present invention has the following advantages and effects:

1. The present invention classifies the models in the model database, then calculates the complexity of each model in each type of model to determine the number of viewpoints, and finally determines the final selected viewpoint by clustering. According to the different requirements of different models for the number of viewpoints and viewpoint positions, each viewpoint can well reflect the characteristics of the model, thereby fixing viewpoints, good matching results, and effectively improving the operating efficiency of the system.

2. In the viewpoint selection part of the existing 3D model retrieval field, there is basically no research on viewpoint selection based on cluster viewpoints. The present invention uses a viewpoint selection method based on cluster viewpoints to fill the technical gap in this respect.

Description of drawings

Figure 1 is a flow chart of the present invention.

Fig. 2 is an analysis diagram of the Loop subdivision algorithm of the present invention.

Detailed ways

The present invention will be further described in detail below in conjunction with the embodiments and the accompanying drawings, but the embodiments of the present invention are not limited thereto.

Example

As shown in Figure 1, a sketch-based 3D model retrieval viewpoint selection method includes the following steps:

Step 1. Manually classify the models in the database;

Step 2. Determine the complete set of viewpoints by triangulating the icosahedron.

Step 2 specifically includes the following steps:

Step 2-1, taking the origin of the three-dimensional Cartesian coordinate system as the center of the circumsphere of the icosahedron, and drawing an icosahedron with a radius of 2;

Step 2-2. Subdivide the surface by splitting a triangular surface into 4 small triangular surfaces.

According to different methods of point generation, the points generated after subdivision can be divided into two categories:

(1) The first type of point: the point calculated by the edge of the original triangle, such as the Vq, Vp and Vr points in Figure 2;

(2) The second type of point: the point calculated by the vertices of the original triangle, such as the V ₁ ', V ₂ ' and V ₃ ' points in Figure 2;

For the above two types of points, the first type point and the second type point, according to whether the edge it belongs to is a boundary, the coordinates of the newly generated point are calculated in two cases:

For the first kind of points:

(1) If the side of the original triangle is a boundary side, the formula for calculating the coordinates of the newly generated point is:

Wherein, V ₁ and V ₂ are two vertices of the boundary edge respectively. From formula (1), it can be seen that,

(2) If the side of the original triangle is not a boundary side, the calculation formula of the coordinates of the newly generated point is:

Wherein, V ₂ , V ₃ are two vertices of the non-boundary edge, and V ₁ , V ₄ are the two vertices closest to the non-boundary edge on both sides of the non-boundary edge that intersect with these two vertices. From formula (2), it can be seen that:

For the second type of points:

(1) If the side of the original triangle is a boundary side, the formula for calculating the coordinates of the newly generated point is:

Wherein, V ₁ is the corresponding vertex on the original triangle, and V ₂ and V ₃ are respectively two adjacent vertices of V1 on the original triangle. From formula (3), it can be seen that:

If the side of the original triangle is not a boundary side, the calculation formula of the coordinates of the newly generated point is:

in,

When n=3, When n>3, V _i represents a vertex in the original polygon that has an edge connected to V. From formulas (4) and (5), it can be seen that:

Step 3. Calculate the entropy value of each model at each viewpoint. Step 3 specifically includes the following steps:

Step 3-1: The formula for calculating the entropy value of model x at viewpoint p _j is as follows:

Among them, E represents the entropy value of the model at the viewpoint, m represents the number of faces of the model, A _i represents the visible area of the i-th face at the viewpoint, and S represents the total area of the model rendering area (due to The model has been scaled into the unit sphere, so the area of the unit circle can be used to represent S); A ₀ represents the area of the background part, that is, the total area of the rendering area S minus the total area of the model projected on the surface, That is A ₀ . The larger the value of E, the greater the complexity of the model. Generally speaking, the more viewpoints are required.

Step 3-2: A(xx ₀ )+B(yy ₀ )+C(zz ₀ )=0, (9)

Among them, A, B, and C are equal to x _n , y _n , z _n respectively, that is, the three-dimensional coordinates of the normal vector of the plane, x ₀ , y ₀ , z ₀ represent the coordinates of a certain known point on the plane, The plane equation can be used to represent the plane equation of the projection surface.

For each vertex v _i (x _i , y _i , z _i ) of the model, the equation of a straight line passing through the point and having the same normal vector as the normal vector of the viewpoint can be calculated. Since it is an orthographic projection, the normal vector of the vertex and the line that maps the point on the projection surface can be regarded as: the viewpoint p _i (x _p ,y _p ,z _p ) and the center of the projection surface p _i '(x ₀ ,y ₀ , z ₀ ), so the space linear equation can be expressed as:

Among them, x _i , y _i , z _i are the coordinates of each vertex vi, m, n, r are the normal vectors of the straight line, and the solution of the equation system formed by formula (9) and formula (10) can be obtained. The mapping point v _i '(x _i ', y _i ', z _i ') of the vertex on the projection surface, regenerate the mapping f'(v ₁ ', v ₂ ', v ₃ ' of the vertex and the surface on the projection surface ).

Step 3-3: Just find a set of basis vectors e ₁ and e ₂ that pass through p' and are perpendicular to each other on the plane where p' is located (using these two sets of basis vectors). For a point q(x _q ,y _q ,z _q ) on the projection plane, its two-dimensional coordinate q'(x _q ',y _q ') on the projection plane can be calculated by the following formula:

PQ=PO+OQ, (12)

Among them, PQ, PO, and OQ are vectors from p to q, p to o, and o to q, respectively.

which is:

xq'*e1+yq*e2=PO+OQ, (13)

Among them, e1 is the basis vector of q on the x-axis direction on the plane, and e2 is the basis vector of q on the y-axis direction on the plane.

In formula (12), the right side of the formula is known, and e ₁ and e ₂ can also be calculated. At this time, the formula can be regarded as a binary linear equation about x _q ', y _q '. The two sides of the equation can be multiplied by e ₁ and e ₂ respectively, that is:

xq'*e1·e1+yq*e2·e1=(PO+OQ)·e1,

xq'*e1·e2+yq*e2·e2=(PO+OQ)·e2,

Among them, e1 is the basis vector of q on the x-axis direction on the plane, and e2 is the basis vector of q on the y-axis direction on the plane. PQ and OQ are vectors from p to q and o to q respectively;

Since e ₁ and e ₂ are perpendicular to each other, e ₂ · e ₁ = 0, from which x _q ' and y _q ' can be calculated respectively, that is, the coordinates of Q on the projection plane with P' as the origin;

Step 3-4: In Matlab, there is a built-in function to calculate the union of two polygons - polybool. It is defined as follows:

[x,y]=function(operation,x ₁ ,y ₁ ,x ₂ ,y ₂ );

Among them, x and y are the return values of the function, x is the x-axis direction coordinate of the clockwise sequence of polygon vertices after the union of two polygons (x ₁ , y ₁ ), (x ₂ , y ₂ ), and y is It coordinates in the y-axis direction. operation indicates the operation performed on two polygons. When the input operation is 'union', it is the union of two polygons.

Step 4. Determine the number of viewpoints of each type of model by the calculation results of step 3. Step 4 specifically includes the following steps:

Step 4-1: first calculate the average entropy value E _m of all viewpoints of each model, and then calculate the standard deviation S _d of each viewpoint of each model relative to the average entropy value E _m .

Step 4-2: Euclidean distance C=sqrt(S _d ^2+E _m ^2). Among them, S _d and E _m represent the values normalized by the maximum value of the corresponding value in each type of model respectively.

Step 4-3: Nc=a*C*N ₀ (14)

Among them, N ₀ is the full set of feature viewpoints extracted, here, N ₀ is half of the 42 viewpoints, namely 21. a is a constant, since only half of the viewpoint area is considered, let a be equal to 0.5. C is obtained from step 4-2, and represents the model complexity. N _C is the final number of viewpoints.

Step 5. Perform a clustering operation on the complete set of viewpoints based on the calculation results in step 4 to determine the selected viewpoint. Step 5 specifically includes the following steps:

(1) Input: k (number of clusters) and p=m*n matrix, randomly select k initial cluster centers, such as: let q=k*n, q(i,:)=p(i,:) ;

(2) For each object in p, p(i,:), compare its distance with q(i,:), if it is added to another r=k*n matrix, its The subscript is r(i,j);

(3) For each row in the matrix r, recalculate the centroid of the elements in p subscripted by the elements in the same row in r, and then exchange the value of q(i,:) with this value;

(4) Repeat (2) (3) until the change of all q(i,:) values is less than a given threshold;

Step 6. From the viewpoints generated in step 5, a two-dimensional projected view of the model under these viewpoints is generated.

The above-mentioned embodiment is a preferred embodiment of the present invention, but the embodiment of the present invention is not limited by the above-mentioned embodiment, and any other changes, modifications, substitutions, combinations, Simplifications should be equivalent replacement methods, and all are included in the protection scope of the present invention.

Claims (3)

1. A sketch-based three-dimensional model retrieval viewpoint selection method is characterized by comprising the following steps:

step 1, manually classifying models in a database;

step 2, determining a complete set of viewpoints by triangulating the regular icosahedron;

step 3, calculating the entropy value of each model at each viewpoint;

step 4, determining the number of viewpoints of each type of model according to the calculation result of the step 3;

step 5, clustering operation is carried out on the viewpoint complete set according to the calculation result of the step 4, and the selected viewpoint is determined;

step 6, generating a two-dimensional projection view according to the viewpoint generated in the step 5;

the step 2 comprises the following steps:

step 2-1, drawing a regular icosahedron with the origin of the three-dimensional rectangular coordinate system as the sphere center of the external sphere of the regular icosahedron and the radius of 2;

step 2-2, subdividing the surfaces by splitting 1 triangular surface into 4 small triangular surfaces;

according to different modes of point generation, points generated after subdivision are divided into two types:

(3) the first type is as follows: calculating points from the edges of the original triangle;

(4) the second kind of points: calculating points from the vertexes of the original triangles;

and for the first-class point and the second-class point, calculating the coordinates of the newly generated point according to two conditions according to whether the edge to which the first-class point and the second-class point belong is a boundary:

for the first category:

(1) if the edge of the original triangle is a boundary edge, the calculation formula of the coordinates of the newly generated point is:

wherein, V₁、V₂Two vertexes of the boundary edge, respectively, can be seen from the formula (1),

(2) if the edge of the original triangle is not a boundary edge, the calculation formula of the newly generated point coordinate is as follows:

wherein, V₂、V₃Is the two vertices of the non-boundary edge，V₁、V₄Two vertices that intersect both of the vertices and are on both sides of the non-boundary edge and closest to the edge are known from equation (2):

for the second type of points:

if the edge of the original triangle is a boundary edge, the calculation formula of the coordinates of the newly generated point is:

wherein, V₁Is the corresponding vertex, V, on the original triangle₁、V₃Two vertexes adjacent to V1 on the original triangle respectively, and it can be known from equation (3):

if the edge of the original triangle is not a boundary edge, the calculation formula of the newly generated point coordinate is as follows:

wherein,

when n is 3, the compound is added,when n is greater than 3, the compound is,V_irepresents the vertex in the original polygon with one side connected with V, and can be known from the formula (4) and the formula (5):

wherein Vi is V2, V3 or V5;

the step 3 comprises the following steps:

step 3-1, model x is at viewpoint p_jThe formula for calculating the entropy value is as follows:

where E represents the entropy value of the model at the viewpoint, m represents the number of faces of the model, A_iRepresenting the visible area of the ith surface at the viewpoint, S representing the total area of the rendering region of the model, S being represented equally by the area of a unit circle since the model has been scaled into a unit sphere; a. the₀The area representing the background part, i.e. the total area S of the rendering area minus the total area projected by the model on the surface, is A₀(ii) a The larger the value of E is, the larger the complexity of the model is, and the more the number of required viewpoints is;

step 3-2, A (X-X)₀)+B(y-y₀)+C(z-z₀)＝0， (9)

Wherein A, B, C are each equal to x_n、y_n、z_nI.e. the three-dimensional coordinates of the normal vector of the plane, (x)₀，y₀，z₀) The coordinates of a certain known point on the plane are expressed, and the plane equation can be used for expressing the plane equation of the projection plane;

for each vertex v of the model_i(x_i，y_i，z_i) A linear equation which passes the point and has the same normal vector as the normal vector of the viewpoint can be calculated; because of the front projection, the normal vector of the straight line between the vertex and the projection point on the projection surface can be regarded as: viewpoint p_i(x_p，y_p，z_p) From the center p of the plane of projection_i’(x₀，y₀，z₀) The normal phasor is formed, so the space linear equation can be expressed as:

wherein x is_i、y_i、z_iFor the coordinates of each vertex vi, m, n, r are normal vectors of straight lines, and by solving the equation system formed by the formula (9) and the formula (10), the mapping point v of the vertex on the projection plane can be obtained_i’(x_i’，y_i’，z_i') to regenerate the mapping f' (v) of the vertex and the surface on the projection plane₁’，v₂’，v₃’)；

Step 3-3: so long as a set of p ' over-p ' and mutually perpendicular basis vectors e on the plane of p ' is found₁、e₂Then the method is finished; for a point q (x) on the projection plane_q，y_q，z_q) Calculating its two-dimensional coordinate q' (x) on the projection plane_q’，y_q') can be calculated using the following formula:

PQ＝PO+OQ， (12)

PQ, PO and OQ are vectors from p to q, p to o and o to q respectively;

namely:

xq’*e1+yq*e2＝PO+OQ， (13)

wherein e1 is a base vector of q in the x-axis direction on the plane, and e2 is a base vector of q in the y-axis direction on the plane;

in equation (12), the equation is known to the right, e₁、e₂Can also be calculated; in which case the formula can be viewed as relating to x_q’、y_q' a linear equation of two; can multiply the two sides of the equation by e₁、e₂Namely:

xq’*e1·e1+yq*e2·e1＝(PO+OQ)·e1，

xq’*e1·e2+yq*e2·e2＝(PO+OQ)·e2，

wherein e1 is a base vector of q in the x-axis direction on the plane, and e2 is a base vector of q in the y-axis direction on the plane; PQ and OQ are vectors from p to q and from o to q respectively;

due to e₁、e₂Are perpendicular to each other, e₂·e₁X can be calculated from the values 0_q’、y_q', the coordinates of Q on the projection plane with P' as the origin;

step 3-4: a function polyborol for calculating the union of two polygons is built in Matlab, and the polyborol is defined as follows:

[x，y]＝function(operation，x₁，y₁，x₂，y₂)；

wherein x and y are the return values of the function, and x is two polygons (x)₁，y₁)、(x₂、y₂) Solving the coordinate of the vertex of the polygon in the x-axis direction of the clockwise sequence after the union, wherein y is the coordinate of the vertex in the y-axis direction; the operation represents an operation performed on two polygons, and when the operation is 'union', the two polygons are merged.

2. The sketch-based three-dimensional model retrieval viewpoint selecting method as described in claim 1, wherein said step 4 comprises the steps of:

step 4-1: firstly, calculating the average entropy value E of all viewpoints of each model_mThen, calculating the relative average entropy value E of each viewpoint of each model_mStandard deviation of (S)_d；

Step 4-2: euclidean distance C ═ sqrt (S)_d^2+E_m^ 2); wherein S is_d、E_mRespectively representing the values after normalization processing through the maximum value of the corresponding values in each type of model;

step 4-3: nc ═ a ═ C ═ N₀， (14)

Wherein N is₀Is a complete set of feature viewpoint extractions, let N₀Half of 42 views, namely: n is a radical of₀21; a is a constant, since only half of the view area is considered, let a equal to 0.5; c is obtained from step 4-2 and represents the model complexity, N_CI.e. the final number of views.

3. The sketch-based three-dimensional model retrieval viewpoint selecting method as described in claim 1, wherein said step 5 comprises the steps of:

(1) inputting: randomly selecting k initial clustering centers, and enabling q to be k, n and q (i, i) to be p (i,: in);

(2) for each object in p, p (i,: it is compared to the distance of q (i,: respectively) and if it is added to another matrix of r ═ k ×, n, its subscript is r (i, j);

(3) for each row in the matrix r, re-computing the centroid of the elements in p subscripted to the elements in the same row in r, and then exchanging the value of q (i,: with this value;

(4) repeating (2) (3) until all changes in q (i:) values are less than a given threshold.