JP7817208B2 - Noise removal device and program - Google Patents

Description

The present invention relates to a device and program for removing noise from a three-dimensional model.

Shape information in three-dimensional (3D) space used in computer graphics, autonomous driving, and other applications is recorded as a 3D model (hereinafter, simply referred to as a "3D model" when there is no need to distinguish between points and meshes). These 3D models are generated from sensor information such as camera images, depth sensors, and Lidar (Light Detection and Ranging). However, due to noise introduced during the recording process, the resulting 3D model data is likely to be unable to accurately represent the true 3D shape information of the subject. To address this issue, various techniques have been proposed to remove noise from the shape information of 3D models. In particular, Non-Patent Publication 1 proposes a noise removal method based on the assumption that "compared to the surface of a true, noise-free subject, the surface of a noisy 3D model (hereinafter, "noisy 3D model") has fine irregularities, resulting in uneven local normal vectors." Specifically, it focuses on the graph structure of the noisy 3D model, which connects nearby vertices with edges, and the normal vectors calculated for each vertex, and achieves noise removal by smoothing the normal vectors to increase the similarity of the local normal vectors between vertices connected by edges. Furthermore, this update simultaneously performs optimization with other constraints, such as increasing the similarity (reducing fluctuations) of the coordinate values between vertices connected by the edges of the graph, thereby achieving both smoothness of normal vectors and smoothness of vertex coordinate values.

Chinthaka Dinesh, Gene Cheung, and Ivan V. Baji´c, "Pointcloud denoising via feature graph laplacian regularization," IEEE Transactions on Image Processing, vol. 29, pp. 4143―4158, 2020.

However, because conventional noise removal techniques use smoothing uniformly, they apply smoothing uniformly to areas where the original shape is not flat (such as curved or sharp areas), which can result in the original shape being distorted while the noise is removed.

As mentioned above, the conventional technology described in Non-Patent Document 1 is designed to increase the similarity of normal vectors and coordinates between two points based on a graph structure. This essentially assumes that the points on the surface of the 3D model being processed are distributed on a plane when viewed locally. However, when considering actual 3D models, even when viewed locally, they may have shapes that are difficult to approximate with a planar distribution of points. For example, if the processing described in Non-Patent Document 1 is applied to a gently curving surface that contains noise, the similarity of the normals of the vertices distributed on the surface may be excessively increased, and the shape information of the 3D model may be over-smoothed by modifying it to a shape closer to a plane, resulting in damage to the shape. This is because "the conventional technology processes the surface shape of the 3D model by basing the strength of the smoothing effect on the surface shape of the 3D model solely on the feature values between two points connected by an edge, so as to create an isotropic plane."

In consideration of the above-mentioned problems with the conventional technology, the present invention aims to provide a noise removal device, method, and program that can appropriately remove noise from noisy 3D data.

To achieve the above-mentioned objective, the present invention provides a noise removal device that removes noise from a three-dimensional model that includes at least information on the coordinates of each point, and is characterized by executing the following steps: a first process that calculates the normal of each point of the three-dimensional model; a second process that calculates, for each point, local shape features of the three-dimensional model from the normals of its surrounding points; a third process that obtains optimized normals by optimizing the normals of each point from the local shape features of each point; and a fourth process that obtains the results of noise removal for the three-dimensional model by optimizing the coordinates of each point from the optimized normals of each point. The present invention is also characterized by a program corresponding to the device.

According to the present invention, normals are optimized in advance based on local shape features, and then the corresponding coordinates are optimized to obtain noise removal results. This makes it possible to obtain noise removal results that suppress the over-smoothing that occurs in conventional techniques that do not take local shape features into account.

1 is a functional block diagram of a noise removal device according to an embodiment; FIG. 10 is a diagram illustrating an application example of the present embodiment. FIG. 10 is a diagram illustrating an example of optimization by anisotropic uniformization of normals of points on a curved surface. FIG. 10 is a diagram illustrating an example of processing performed by a graph weight optimization unit. FIG. 1 is a diagram illustrating a hardware configuration of a typical computer.

1 is a functional block diagram of a noise removal device 10 according to an embodiment. The noise removal device 10 includes a normal vector calculation unit 11, a local shape feature calculation unit 12, a normal vector optimization unit 13, a vertex coordinate optimization unit 14, a local shape classification unit 21, and a graph weight optimization unit 22. The overall operation of the noise removal device 10 is to read a noisy 3D model as input in the normal vector calculation unit 11, and output a noise-removed 3D model, which is the result of applying noise removal to the noisy 3D model. Each of the input and output 3D models represents the 3D shape (3D surface shape) of some object or the like, and includes at least information on each point p _i (i=1, 2, ..., N; N is the total number of points) on the surface and its 3D coordinates.

The 3D model may be configured as a point cloud, for example, and may include information on each point p _i and its 3D coordinates. If the 3D model is configured as a polygon model, for example, each point p _i may be configured as a vertex of a polygon, and may further include information on which two points p _i and p _j form which side of the polygon. The 3D model may also be configured as a point cloud or polygon model, and may also include surface texture information.

Note that the local shape classification unit 21 and/or graph weight optimization unit 22 can be omitted from the configuration shown in Figure 1, but the following explanation will mainly focus on configurations in which they are not omitted, and will also explain cases in which they are omitted as appropriate. Below, we will explain in detail the processing content of each functional unit in Figure 1.

<<Normal vector calculation unit 11>>
Normal vector calculation unit 11 calculates normal vector n _i (i=1, 2, . . . , N) for each point p _i (i=1, 2, . . . , N) of the noise-added 3D model, and outputs it to local shape feature calculation unit 12 .

For 3D models with a mesh structure, the normal vector of each polygon comprising the mesh can be calculated, and a representative value, such as the "average value of the normal vectors of all polygons shared by a vertex," can be used as the normal vector of that vertex. For 3D models consisting of point clouds, a surface polygon with the point cloud as its vertices can be formed, and the normal vectors of each vertex can be obtained by performing the same processing as for a mesh. In this case, since each vertex of the surface polygon is obtained from the point cloud, the normal vector of the vertex can be used as the normal vector of the corresponding point cloud. Note that, to form the surface polygon, any existing surface formation method, such as that described in Non-Patent Document 2, can be used. Once the surface polygon is formed, it can be processed in the same way as for a mesh. In this way, the normal vector n _i =(x, y, z) for each vertex of the point cloud or mesh can be obtained. In addition, any existing technology for estimating normal vectors of general point clouds and meshes can also be used.

[Non-Patent Document 2] F. Bernardini, J. Mittleman, H. Rushmeier, C. Silva, and G. Taubin, "The ball-pivoting algorithm for surface reconstruction," IEEE Transactions on Visualization and Computer Graphics, vol. 5, no. 4, pp. 349-359, 1999.

<<Local shape feature calculation unit 12>>
The local shape feature calculation unit 12 receives the normal vector n _i assigned to each vertex p _i by the normal vector calculation unit 11 as an input, calculates the local shape feature of the surface to which each vertex p _i belongs, and outputs this local shape feature to the local shape classification unit 21 and the normal vector optimization unit 13.

Specifically, for example, a graph consisting of the vertices and edges of a 3D model is first constructed using the k-Nearest Neighbor method (k-NN: a graph construction method that connects a point to its k neighbors with edges). The measure of distance between k-NN points can be Euclidean distance in three-dimensional space, or the distance in color space of the color assigned to the point. Furthermore, when using a mesh model, the graph can be constructed using the edges that make up the polygons as the edges of the graph.

Local features can be obtained from the obtained graph by the following process: tensor T i representing shape information around point p _i is calculated using normal vector n _j of neighboring point p _j of point _{p i} according to the following formulas (1) and (2).

Here, N( _pi ) represents the index set of neighboring points of point _pi . α is a coefficient based on the similarity between point _pi and its neighboring point _pj . For example, similarity α based on the distance between point _pi and point _pj can be used, as in equation (1a). (Note that in equation (1a), σ is a coefficient obtained from a representative value such as the maximum value or variance of the distance to neighboring points.) Alternatively, a constant such as α=1 can be used.

_Ti can be treated as a 3x3 matrix, and local shape information can be obtained by applying eigenvalue decomposition to it. The eigenvalues are arranged in descending order as _λ1 ≥ _λ2 ≥ _λ3 , and the corresponding eigenvectors are _e1 , _e2 , and _e3 . Figure 2 shows an example of the distribution of the first and second eigenvectors and eigenvalues at each point p _i when a cylindrical, noisy 3D model is prepared and eigenvalue decomposition is applied, as an application example of this embodiment. Note that the distributions shown in examples EXb and EXd are drawn in dark colors (closer to black) when the eigenvalues are large and small, and light colors (closer to white) when the eigenvalues are intermediate, as indicated by the legend on the left.

Intuitively, the first eigenvector _e1 represents the vector that is the most principal component of the normal vector in the region of the k-nearest neighbor points, and can be considered a more robust normal vector of point p _i that integrates information from the local region. In Figure 2, as shown in example EXa and explanatory column (a), the first eigenvector _e1 is obtained as a robust normal vector for a cylindrical shape. Furthermore, the first eigenvalue _λ1 is an index that indicates how much the normal vector of point p _i differs from its neighbors in the local region, and exhibits low values at corner points (points on the circumference that form the edges of both circular bases in a cylindrical shape), as shown in example EXb and explanatory column (b) of Figure 2.

The second eigenvector _e2 indicates the direction of the second major component of the local region, and in the case of a cylindrical shape, for example, as in Example EXc and explanation column (c) in Figure 2, it indicates the direction of the largest displacement of the normal vector, along the surface, so as to follow the curved surface of the side of the cylinder. (That is, it indicates the direction of the tangent to the circumference of a circle obtained by cutting the cylinder parallel to the bottom surface on the side of the cylinder.) The second eigenvalue _λ2 indicates the amount of displacement of the normal vector, and indicates a large value for a curved surface, as in Example EXd and explanation column (d) in Figure 2, and a small value indicates a flat surface.

The local shape feature calculation unit 12 outputs the eigenvalues λ ₁ , λ ₂ , λ ₃ and eigenvectors e ₁ , e ₂ , e ₃ for each point p _i and its normal vector n _i as features indicating local shape information.

Note that instead of the neighborhood normal vector _nj in equation (1), the amount of displacement (nj -n^) from the average value n^ of the normal vectors of the k neighborhood (the average value is determined by adding an overline _" n^" to n) may be used, thereby allowing the following equation (1b) to be used instead of equation (1).The normal vector _nj of each neighborhood point _pj itself may be used, but the displacement angle from the normal vector _ni of point _pi may be used.

<<Local shape classification unit 21>>
Using the eigenvalues _λ1 , _λ2 , _λ3 and eigenvectors _e1 , _e2 , _e3 calculated by the local shape feature calculation unit 12, the local shape of each point p _i is classified into plane/curved surface/edge (Note 1), corner, etc., and this classification result is output to the normal vector optimization unit 13 and the graph weight optimization unit 22.
(Note 1) Unlike edges, which refer to the edges of a graph, this refers to the edges of a 3D model.

Specifically, a predetermined first threshold _th1 is set for the first eigenvalue _λ1 , and if _λ1 ≧ _th1 , the vertex to be processed is considered to belong to a plane/surface (plane or curved surface), and otherwise it is considered to belong to an edge/corner (edge or corner). (Note that this classification is also shown in the explanatory column (b) of Figure 2.) Here, to determine the threshold _th1 , any existing threshold determination method such as the k-means method or Otsu's method can be widely used, and if there is a large amount of data similar to the target 3D model, machine learning using training data in which each region is labeled may also be used.

Similarly, a predetermined second threshold value _th2 is set for the second eigenvalue _λ2 , and if _λ2 ≥ _th2 , the vertex is determined to belong to a curved surface (or edge/corner), otherwise it is determined to belong to a plane. (Note that this classification is also shown in the explanatory column (d) of Figure 2.)

The above classification is performed for all points of the 3D model, and information is added as to which local shape classification they belong to. In summary, the local shape feature calculation unit 12 can output classification results as follows.
●First judgment...If λ ₁ ≧ th ₁ is false,
This point p _i corresponds to an edge or a corner.
● Second judgment...If λ ₁ ≧ th ₁ is true and λ ₂ ≧ th ₂ is true,
This point p _i corresponds to a curved surface (or edge/corner).
●Third judgment...If λ ₁ ≧ th ₁ is true and λ ₂ ≧ th ₂ is false,
This point p _i corresponds to the plane.

The third eigenvalue _λ3 may be regarded as an offset indicating an isotropic displacement of the normal vector of the nearby vertex, and the value to be subjected to threshold determination in the first, second, and third determinations may be _λ1 - _λ3 instead of _λ1 . Similarly, the value to be subjected to threshold determination in the second and third determinations may be _λ2 - _λ3 instead of _λ2 .

<<Normal vector optimization unit 13>>
The normal vector optimization unit 13 optimizes the normal vector n _i (the normal vector n i calculated by the normal vector calculation unit 11 ₎ using the local shape feature amount and classification result obtained from the local shape feature amount calculation unit 12 and the local shape classification unit 21, respectively, and outputs this optimized normal vector n _{i [optimized]} to the vertex coordinate optimization unit 14. Specifically, the optimized normal vector n _{i [optimized]} can be obtained by performing processing classified into cases according to the classification result as follows.

● If the third judgment is met and the classification result indicates that point p _i belongs to a local plane: In the case of a plane, the normal vectors can be isotropically homogenized as follows. First, as shown in equation (3), a matrix is calculated that lists all of the normal vectors n _j = (x _j , y _j , z _j ) of the k neighboring points of the target point p _i . When point p _i belongs to a plane, it is ideal for the values of its neighboring normal vectors n _j = (x _j , y _j , z _j ) to be similar. Therefore, the normal vectors can be homogenized by calculating an optimal matrix H that improves the low rank of M, as shown in the following equation (4). In other words, since the matrix H calculated using equation (4) lists the optimized normal vectors n _{i [optimization]} , the optimized normal vectors n _{i [optimization]} can be obtained from matrix H.

In the "argmin" argument in equation (4) (the process of calculating matrix H as a parameter that minimizes it), the first term, || || _* , represents the nuclear norm, and the second term, || || _F , represents the Frobenius norm. In equation (4), β is a parameter that determines the strength of the user-defined optimization. The nuclear norm is the sum of singular values and approximates the rank of a matrix. Therefore, the nuclear norm, ||H|| _* , in the first term of equation (4) acts to reduce the rank of matrix H. The Frobenius norm is the length (L2 norm) of a vector when all elements of a matrix are arranged in a row and considered as a vector. It is a concept that extends the L2 norm to matrices, and the Frobenius norm, ||HM|| _F , in the second term of equation (4) acts to reduce the magnitude of the difference between H and M.

That is, when calculating the optimized normal vector n _i[optimized] from before update M to after update H using equation (4), the second term prevents the vector from changing too much from before update, and the first term increases the low rank property, making it possible to calculate the optimized normal vector n _i[optimized] after update so that it is uniform.

Furthermore, instead of M in equations (4) and (5), M' in the following equation (5) may be used, which is obtained by shaping M into a form close to a square matrix (a form in which the number of rows and columns is as equal as possible). Also, in equation (4), instead of the nuclear norm ∥ ∥ _* , the weighted nuclear norm ∥ ∥ _w,* in the following equation (6) may be used.

In equation (6), δ _m indicates the m-th singular value when the singular values of matrix M are sorted in descending order, and w _m is a positive weight set by the user for the singular value. By setting the weight so that w _m becomes smaller as the singular value of δ _m becomes larger, it becomes possible to solve equation (4) while retaining large singular values, and it becomes possible to effectively homogenize normal vectors while maintaining the structure of matrix M.

If the classification result corresponds to the first or second judgment and point p _i belongs to something other than a local plane, then if point p _i belongs to something other than a plane (if it belongs to a curved surface, edge, or corner), the following processing can be carried out to anisotropically homogenize it in accordance with the local shape, thereby obtaining the optimized normal vector n _{i [optimized]} .

When the object belongs to a curved surface or an edge, the direction in which the second eigenvalue vector _e2 extends tends to accompany changes in the normal vector even in the true 3D model shape, so a measure is taken not to strongly optimize the direction of _e2 . Specifically, when _e2 = ( _xe2 , _ye2 , _ze2 ), optimization is performed by anisotropically homogenizing according to the ratio of the magnitudes of the xyz components, as shown in the following equation (7). In other words, the matrix H = ( _Hx , _Hy , _Hz ) obtained by equation (7) lists the optimized normal vectors n _{i [optimization]} , so the optimized normal vectors n _{i [optimization]} can be obtained from the matrix H.

Here, as can be seen from the commonality between equations (7x), (7y), and (7z), which show the terms to be minimized in equation (7) for each x, y, and z component, and the minimization terms in equation (4), H _x , H _y , H _z and M _x , M _y , and M _z are the matrices of equations (3) and (4) extracted for each x, y, and z component.

For example, consider the case where the second eigenvector _e2 = ( _xe2 , _ye2 , _ze2 ) found for the target point _p1 satisfies | _xe2 |≒| _e2 |, | _ye2 |≒0, and | _ze2 |≒0, i.e., the second eigenvector _e2 is nearly parallel to the x-axis direction and the majority of its components are x-axis components. In this case, the x-axis direction is along the curved surface of the 3D shape, and corresponds to the direction in which the normal vector displacement is greatest, and corresponds to the direction in which the application of homogenization should be weakened as a direction that should accompany normal change. Therefore, the value of the term in equation (7x) in the x-axis direction is reduced by the coefficient (1-| _Xe2 |/| _e2 |)≒0, thereby weakening the effect of homogenization in the x-axis direction relatively compared to the effects of homogenization in the other y and z axes. Conversely, the y-axis and z-axis directions are different from the x-axis (two directions perpendicular to the x-axis) and should be homogenized more strongly and aggressively than the x-axis direction. Therefore, the values of the terms in equations (7y) and (7z) are set to a certain magnitude using the coefficients (1-|Y _e2 |/| _e2 |) ≒ 1 and (1-|Z _e2 |/| _e2 |) ≒ 1, thereby ensuring a relatively large effect of homogenization in the y-axis and z-axis directions.

That is, the degree of homogenization is weakened for the direction along the surface of the local shape (the tangent plane at point p _i ) and the direction in which the normal vector displacement is maximum, which is estimated as the direction of the _second eigenvalue vector e 2, and the degree of homogenization is strengthened for the directions of the first eigenvalue vector e ₁ and the third eigenvalue vector e ₃ which are robust normals of the local shape perpendicular to the direction of the second eigenvalue vector e 2. In other words, when obtaining the optimized normal vector n _i[optimized] from the normal vector n _i before optimization, a fluctuation Δn _i due to homogenization is added as "n _i[optimized] = n _i + Δn _i ", but the main component of this fluctuation Δn _i is configured in the direction of the second eigenvalue vector e ₂ , and the directional components of the first eigenvalue vector e ₁ and the third eigenvalue vector e ₃ can be made small.

Figure 3 shows a schematic example of non-uniform optimization of the normal n _{i to a point p i on} the curved side surface of a cylinder, as shown in Figure 2. As explained in examples EXa and EXc in Figure 2, for the normal n _i to point p _i on the side surface of the cylinder, n _i ≒ e ₁ , and the second eigenvector e _{2 points} in the direction of the circumferential tangent to the side surface. Therefore, when non-uniform optimization is performed using equation (7) as "n _{i [optimization]} = n _i + Δn _i ," the main component of the variation Δn _i is composed of the directional component of the second eigenvector e ₂ . By reducing the directional components of the first and third eigenvectors e ₁ and e ₃ that are orthogonal to this, appropriate optimization of the normal on the curved side surface of the cylinder can be achieved.

In general, not only in the case of a cylindrical side surface as shown in Figure 3, but also in other cases, with respect to the normal n _i of point p _i on a curved surface, n _i ≒ e ₁ , the first normal vector e ₁ is the normal vector of the tangent plane of the local shape, and the second normal vector e ₂ means the tangent direction of the circle tangent to the local shape at point p _i (in the case of a cylindrical shape, the circle obtained by cutting the side surface). In other words, in the case of a curved surface, the second normal vector e ₂ contains information about the circle tangent to the local shape at point p _i .

As a modified example of the optimization of Equation (7), _M'x , _M'y , and M'z may be used, in which the number of rows and columns for each of x, y, and _z are as equal as possible, as in Equation (5). Alternatively, the above optimization may be performed on only the top one or two components of ( _xe2 , _ye2 , _ze2 ) with the smallest absolute values. In addition to the above optimization, when a weighted nuclear norm is used, the weights _wm1 , _wm2 , and _wm3 in Equation (6) ^, which correspond to _M1 , _M2 , and _M3 for each component in descending order of absolute value of ⁽ _xe2 , _ye2 , _ze2) ^, may be set so that _wm1 > _wm2 > ^wm3 , thereby suppressing ^the effect ^of uniforming the normal vector for the component in _the direction of the second eigenvector _e2 .

When using the minimum configuration (a configuration in which the local shape classification unit 21 and graph weight optimization unit 22 are excluded from the noise removal device 10), the information on the classification results from the local shape classification unit 21 cannot be used, so normal vectors optimized for all vertices according to equation (7) may be used.

<<Graph Weight Optimizer 22>>
The graph weight optimization unit 22 uses the local shape features output by the local shape feature calculation unit 12 to construct a graph to be used by the vertex coordinate optimization unit 14 described later, and outputs the graph to the vertex coordinate optimization unit 14.

First, a graph is constructed using the k-NN algorithm or the like, as in the local shape feature calculation unit 12. In this case, existing methods generally use similarity s ij (corresponding to the similarity between points p _i and p _j ) based on the distance in 3D space between vertices or the distance in color space (if local texture information is available, this is used to calculate the distance in color space). However, in this embodiment, instead of using the general weight s _ij as is, weight s' _ij obtained by updating the general weight s _ij based on the local shape feature is used. (Therefore, when using an embodiment in which the graph weight optimization unit 22 is omitted in the noise removal device 10, the general weight s _ij can be used as is as the graph weight used in the _vertex coordinate optimization unit 14.)

This weight update process (s _ij →s' _ij ) may be performed on all data. Alternatively, it may be performed on only a portion of the data. For example, in an embodiment in which the noise removal device 10 includes a local shape classification unit 21, if the results of the local shape classification can be referenced, the weight update process (s _ij →s' _ij ) may be applied to vertices that meet the second judgment and are classified as belonging to a curved surface and/or vertices that meet the first judgment and are classified as belonging to an edge or corner. This weight update prevents excessive smoothing of the curved surface shape when updating coordinates in the vertex coordinate optimization unit 14, described below. When the update is applied, the following relationship holds: the greater the deviation of the local shape from a planar shape (i.e., the closer it is to a curved surface, edge, or corner rather than a planar shape), the smaller the weight is updated, thereby preventing excessive smoothing.
s _ij >s' _ij >0

This is achieved by reducing the weight of graph edges that are nearly parallel to the direction of the second eigenvector _e2 , which has meaning as a local shape feature vector. More specifically, as shown in equation (8-i), the relationship between the edge _fij spanning points _pi and _pj and the second eigenvector _e2 = _e2 ( _pi ) of point _pi and the second eigenvalue _λ2 = _λ2 ( _pi ) normalized as described below, and equation (8-j) which gives a similar relationship with points _pi and _pj swapped, is used to average these to update the value of weight _sij to an optimized weight _s'ij as shown in the following equation (8). (Note that in equations (8-i) and (8-j), _sij = _sji and _fij = _fji .)

Here, cos(,) is a function that returns the cosine similarity between two vectors, and _λ'2 is _λ2 normalized using the maximum value _λ2max of the eigenvalues _λ2 of all points in the input 3D model ( _λ'2 = _λ2 / _λ2max ).

The greater the deviation of the local shape at each location from the planar shape, the more effectively over-smoothing at that location can be suppressed, as follows. For example, in equation (8-i), side f _ij is assumed to lie on the tangent plane (first approximation plane) of the local shape at point p _i , and a large difference in the orientation of side f _ij from the second eigenvector e ₂ = e ₂ (p _i ), which is also assumed to lie on the tangent plane, means that the local shape deviates greatly from the plane and has high curvature. Therefore, the greater the difference in orientation, the higher the curvature, and by reducing cos(f _ij , e ₂ (p _i )), the updated weight s' _ij is updated to a smaller value, thereby suppressing over-smoothing. As explained in the second judgment above, when the second eigenvalue λ ₂ (p _i ) is small, it means that the local shape is flat, and when it is large, it means that the local shape is curved.Similarly, the larger the second eigenvalue λ ₂ (p _i ), the smaller (1-λ ₂ (p _i )), and therefore, by updating the updated weight s' _ij to a smaller value, over-smoothing can be suppressed.

In addition to the above, the following method may be used to obtain a similar effect. Specifically, as shown in the explanatory diagram of FIG. 4 , the normal vectors of neighboring points _u hops away from point p _i and its neighboring point p _j (neighboring points located at the end of u edges on the graph) may be mapped as φ(n _i ^u ) to a plane _F spanned by the average vector a ij of the normal vectors of the target point p _i and its neighboring point p _j and the second eigenvector e 2 of the target point p i ( _where φ() in φ(n _i ^u ) is a mapping function that projects the input vector onto plane F). Then, the minimum value of the cosine similarity cos(a _ij , φ(n _i ^v )) between a _ij and φ(n _i ^v ) corresponding to all neighboring points n _i ^v (v≦u) u hops or less may be defined as v _min (p _i ), and updating may be performed using the following formula (9-i) instead of formula (8-i). Similarly, updating may be performed using the following formula (9-j) instead of formula (8-j).

Here, with regard to formula (9-i) (and formula (9-j) which is symmetric with respect to i, j), it is expected that the greater the deviation of the local shape near the point of interest p _i from the plane F, that is, the more the local shape near the point of interest p _i is not a plane but a curved surface or a shape closer to an edge or corner, the smaller this minimum value v _min (p _i ) will be. (Note that for ordinary continuous shapes, it is expected that the value will be in the range of 1≧v _min (p _i )>0.) Therefore, as mentioned above, when formula (9-i) etc. is used, just as when formula (8-i) etc. is used, the greater the deviation of the local shape from a plane, the smaller the updated weight s' _ij will be, making it possible to increase the degree to which over-smoothing in that area is suppressed.

By using the variance σ _u (p _i ) of the mapped φ(n _i ^u ) instead of v _min (p _i ) (σ _u (p _i ) is normalized by the variance of φ(n _i ^u ) within u hops of all points in the input 3D model), v _min (p _i ) in equation (9-i) can be set to (1-σ _u (p _i )), which can achieve the same effect of suppressing over-smoothing. The same can be done for equation (9-j).

<<Vertex coordinate optimization unit 14>>
The vertex coordinate optimization unit 14 updates the coordinate values (x i , y i , z i ) of the point p _i using the optimized normal vector n _{i [optimized]} for each vertex obtained by the normal vector optimization unit 13 (note that in the following formulas, this is simply indicated as n _{i or} the _{like )} and the graph s' _ij whose weight has been updated by the graph weight optimization unit 22, and actually modifies the shape of the 3D model, outputting the noise removal result. Specifically, this is realized by solving the following optimization formula (10). (Note that if weight updating is not applied to all or part of the edges of the graph, the value of s' _ij should be the unupdated value s _ij ("s' _ij = s _ij ").)

Here, p = (p ₁ , p ₂ , ..., p _N ) is a variable that lists the coordinates of all N vertices, and p _i and p _j are three-dimensional vectors (coordinate values) corresponding to certain indices i and j among all points p. Also, q indicates the initial coordinates of the vertices (i.e., all coordinate values before updating). η and ζ are user-set parameters that determine the weight of each term.

In this optimization, the first term, cost ₁ , in equation (10-1) acts to prevent the change from the original shape q to the updated shape p from becoming too large, the second term, cost ₂ , in equation (10-2) acts to prevent the coordinate difference between neighboring points in the updated shape p from becoming too large, and the third term, cost ₃ , in equation (10-3) acts to make the difference between the direction of the optimization normal vector (n _i ^T and n _j ^T respectively) and the direction of the vector connecting neighboring points ( _pi -p _j respectively) in the updated shape p approach perpendicular (because the dot product term takes the minimum value of zero when perpendicular), and all three terms act as cost terms. With regard to the second term, cost ₂ , the updated weight s' _ij becomes a coefficient, and the weight s' _ij is updated to a smaller value for areas that deviate more from a plane and are closer to a curved surface, etc., thereby allowing for larger coordinate differences between nearby points and promoting updating to a shape closer to the original shape, thereby facilitating appropriate smoothing. Conversely, for areas that correspond to a plane, the weight s' _ij is large, preventing larger coordinate differences between nearby points and preventing unnecessary over-smoothing.

In the case of the minimum configuration (a configuration in which functional units 21 and 22 are omitted from the noise removal device 10), the optimization problem of equation (10) can be solved by omitting the second term, cost ₂ , from equation (10-2). Note that since p _i and p _j in equation (10) are both variables, when actually optimizing the vertex coordinates, point p _j can be fixed and an optimization method such as a gradient method can be used to find the coordinate value of point p _i . This "operation of deriving (updating) the optimal value when a certain point p _i is a variable" is repeated sequentially for all points p _i until the vertex coordinate updates converge (or until a predetermined number of repetitions are completed), thereby obtaining the desired vertex coordinates (3D model shape).

As described above, according to an embodiment of the present invention, by performing adaptive noise removal on local shapes based on local feature amounts obtained from normal vectors, it is possible to remove noise that effectively utilizes detailed shape information from the finer details of a 3D model, compared to conventional noise removal techniques that are uniform across the entire 3D model and isotropic in three-dimensional space.

Below, we will explain various supplementary, alternative, and additional examples.

(1) The noise removal technology of the present invention can be applied as a component technology to a variety of applications. For example, it can improve the accuracy of modeling three-dimensional virtual spaces, increase the utility value of three-dimensional virtual spaces, and encourage users to use three-dimensional virtual spaces. As a result, if the use of remote communication as an example of a use of three-dimensional virtual spaces is promoted, carbon dioxide emissions can be reduced by saving the energy resources required for user movement, which can contribute to Goal 13 of the United Nations-led Sustainable Development Goals (SDGs), which is to "take urgent action to combat climate change and its impacts."

(2) The noise removal device 10 may be configured to perform repeated processing for the entire process or a portion of the process. That is, as shown by line L141 in FIG. 1, the process may be repeated by the entire noise removal device 10 (the nth noise-removed 3D data output is the (n+1)th input), or, as shown by line L142, the noise-removed data may be used to update only the graph weights again, and then the noise-removed data may be obtained again in an updated manner.

(3) Figure 5 is a diagram showing an example of the hardware configuration of a typical computer device 70. The noise removal device 10 can be realized as one or more computer devices 70 having such a configuration. When the noise removal device 10 is realized using two or more computer devices 70, information required for processing may be sent and received via a network. The computer device 70 includes a CPU (central processing unit) 71 that executes predetermined instructions, a GPU (graphics processing unit) 72 as a dedicated processor that executes some or all of the CPU 71's execution instructions in place of or in cooperation with the CPU 71, RAM 73 as main storage that provides a work area for the CPU 71 (and GPU 72), ROM 74 as auxiliary storage, a communication interface 75, a display 76, an input interface 77 that accepts user input via a mouse, keyboard, touch panel, etc., and a bus BS for exchanging data between these.

Each functional unit of the noise removal device 10 can be realized by a CPU 71 and/or a GPU 72, which loads and executes a predetermined program corresponding to the function of each unit from a ROM 74. Both the CPU 71 and the GPU 72 are types of computing devices (processors). Here, when display-related processing is performed, a display 76 also operates in conjunction with the CPU 71 and the GPU 72, and when communication-related processing related to data transmission and reception is performed, a communication interface 75 also operates in conjunction with the CPU 71 and the GPU 72.

10... Noise removal device, 11... Normal vector optimization unit, 12... Local shape feature calculation unit, 13... Normal vector optimization unit, 14... Vertex coordinate optimization unit, 21... Local shape classification unit, 22... Graph weight optimization unit

Claims (10)

A noise removal device that removes noise from a three-dimensional model including at least information on the coordinates of each point,
a first process of calculating a normal to each point of the three-dimensional model;
a second process of calculating, for each of the points, a local shape feature of the three-dimensional model from normals of points adjacent to the point;
a third process of obtaining an optimized normal by optimizing the normal of each point based on the local shape feature of each point;
a fourth process of obtaining a result of noise removal for the three-dimensional model by optimizing the coordinates of each point using the optimized normals of each point ;
further performing a fifth process of classifying the shape of a local neighborhood area of each point in the three-dimensional model as a shape including at least a determination result of whether or not the shape corresponds to a plane, based on the local shape feature amount of each point;
In the third process, the normals of points that correspond to a plane are optimized by isotropically uniformizing them using the classified results, and the normals of points that do not correspond to a plane are optimized by anisotropically uniformizing them . In the second processing, the local shape feature is calculated as including information of a circle tangent to the local shape;
The noise removal device described in claim 1, characterized in that in the third process, the degree to which a component in the tangential direction of the tangent circle is allowed to be included as a fluctuation component to be added to the normal to obtain the optimized normal is made larger than the degree to which a component perpendicular to the tangential direction is allowed to be included, thereby anisotropically uniformizing the normal of points that do not fall on the plane . In the second processing, eigenvalues and eigenvectors are calculated from a tensor that represents shape information around each point and is obtained by enumerating normal vectors of points near each point , and the eigenvalues and eigenvectors are used as local shape features of each point;
2. The noise removal device according to claim 1 , wherein in the fifth process, the classification is performed using a threshold value determination for the eigenvalues. 2. The noise removal device according to claim 1, wherein, when the fifth process determines that the point corresponds to the plane , the third process performs the optimization by determining a matrix H after updating that minimizes a weighted sum of a kernel norm of the matrix H and a Frobenius norm of a matrix HM obtained by taking the difference between the matrix H and the matrix M, where M is a matrix listing the normal vectors of each point and its neighboring points before updating and H is a matrix listing the normal vectors of each point and its neighboring points after updating . The noise removal device described in claim 1, characterized in that in the fourth process, the optimization is performed by minimizing costs that include at least a third cost, the value of which decreases as the difference between the direction of the corresponding optimized normal vector and the direction of the vector connecting each point and its neighboring point becomes closer to perpendicular, for each point and its neighboring point. The noise removal device described in claim 1, characterized in that in the fourth process, the optimization is performed by minimizing costs that include at least a second cost whose value increases as the distance between each point and its neighboring point increases. a sixth process of graphing the relationship between each point and its neighboring points in the three-dimensional model and assigning weights to edges of the graph;
7. The noise removal device according to claim 6 , wherein in the fourth process, the second cost is calculated using the weight of the graph as well. 8. The noise removal device according to claim 7, wherein in the sixth process, a given value is assigned to a weight of an edge of the graph in advance, and the weight of the edge is updated from the given value to a smaller value as a degree to which a local shape in the vicinity of each edge is estimated to deviate from a plane is greater based on the local shape feature. In the fourth process, the optimization is performed by minimizing costs including at least a second cost whose value increases as the distance between each point and its neighboring point increases;
9. The noise removal device according to claim 8 , wherein the weight of the edge of the graph is used as the weight for the second cost. 10. A program that causes a computer to function as the noise removal device according to claim 1.