3D scanning of real-world objects has become an integral step of many manufacturing processes and digital image processing applications. Despite the impressive progress in modern 3D scanning technology, the produced 3D models often sufer from defects due to occlusions, poor light conditions, special surface reflection properties, scanner displacements, imperfect algorithms, etc. Point cloud completion is a standard post-processing step aiming at removing or smoothing such irregularities. In this article, we propose a novel method for damage completion of 3D objects possessing reflection symmetry. Such symmetries are identified by matching local shape features such as curvatures and edges in mesh and point cloud representations of the objects. We describe the pipeline of our method, justify its steps, and evaluate its performance on the ModelNet40, a Princeton 3D object dataset. The results demonstrate comparable improvement in the damaged 3D object completion to popular neural network-based and symmetry-based approaches.
ings that often sufer from significant time damage).
The main idea is that in mirror-symmetric objects, all Advances in modern 3D scanning technology have led local shape features are also symmetrically distributed. to a significant boost in computer vision post-processing For instance, the principal curvatures of symmetric tools for 3D models. One of the standard tasks of 3D points are the same, and the principal directions enjoy scanning is completing the obtained 3D models that sufer the same symmetry; likewise, all linear edges in symmetfrom poor light conditions, occlusions, surface reflection, ric objects can be split into symmetric pairs. The search etc. This completion task has been approached in many for global mirror symmetries can be based on pairs of diferent ways, in particular, using neural networks pre- points with similar curvatures and/or edges. Each such trained on certain object classes. Although such methods pair creates a potential symmetry plane, and the majority show good results for new objects from these classes, vote determines the best mirror symmetry. The latter their performance on previously unseen object types is then used to compare and combine the object and its drops significantly. Therefore, alternative algorithms mirror image and thus complete the missing or damaged capable of completing previously unseen objects are of parts. vital importance. That approach demonstrated competitive results in
In this paper, we suggest a novel approach to 3D model comparison to a known traditional symmetry-based completion based on the geometric features of mirror- method of point cloud completion and three deep learnsymmetric objects. Since this type of symmetry is typi- ing method. More details on the methods for comparison cal in man-made environments, such an assumption is are given in the following sections. not very restrictive. Finding plane symmetry in approximately symmetric 3D models is the most important step; we then use it to complete any damages and holes which 2. Related work could occur during scanning or were already present in the real-life scanned object (e.g., in archaeological find
As mentioned above, damages in 3D objects can be repaired by using missing information from their symmetrically transformed images. There are two main directions for symmetry plane detection in 2D/3D data: classical and deep learning approaches. In this paper, we aim to extend the classical approach as more robust for previously unseen objects and thus review the corresponding algorithms first.
One of the approaches for symmetry-based point cloud
completion is discussed in [
Closest Point (ICP), and, finally, hole detection and filling.
The paper [
The principal idea of our geometry-aware symmetry 1. 3D model representation: triangle mesh, point
detection is based on the paper [
The paper [
Recently, deep learning algorithms have become state- point characterize locally extremal surface bending in
of-the-art solutions in diferent areas, especially for com- the respective principal directions in the tangent plane.
puter vision tasks. Various neural networks were pro- Principal curvatures and directions describe well the
apposed for symmetry detection, data completion, segmen- proximate local surface shape. For example, principal
tation, classification, and other tasks for processing 3D curvatures of a small absolute value represent a
reladata. Examples of successful solutions include but are tively flat surface, while greater curvatures correspond
not limited to [
The authors of MSN (Morphing and Sampling Net- of principal curvatures indicate a possible edge.
work) thoroughly describe their model in [
PoinTr – a transformer encoder-decoder model. They We use the principal_curvature function from represented point clouds as unordered groups of points the libigl library [15] to calculate the principal curvatures with position embeddings and added a geometry-aware of the mesh. As suggested in [16], this function first fits neighborhood search in later stages. Also, for each verlocally a quadratic polynomial tex xi, we calculate the corresponding principal curvaf (x, y) = ax2 + 2bxy + cy2 + dx + ey (1) tures k1(i), k2(i) and save the results in a separate file as a dictionary with keys xi and principal curvatures as to the surface and then computes the principal curva- values. tures and directions as eigenvalues k1, k2 and eigenvectors d1, d2 of the corresponding shape operator (a 2 × 2 3.2.2. Curvature-based point clustering matrix) explicitly given in terms of the parameters a to e.
Observe that signs of the principal curvatures depend on Candidates for symmetry planes are collected by detectthe surface orientation: if d1 and d2 are interchanged, ing symmetric patches in the point cloud. We start with then the curvatures k1, k2 become −k2, −k1. We, there- two compatible points, determine their symmetry plane, fore, order the principal curvatures so that k1 ≥ |k2|. and then verify if it matches some neighborhoods of these
We would like to mention that the points. Since symmetric patches have symmetric local principal_curvature function does not allow shapes, we run through point pairs with close principal small triangle clusters (i.e., sets of triangles connected in curvatures. We cluster the vertices of the point cloud a mesh). Therefore, before computing curvatures, we with similar curvatures using the Mean Shift algorithm. extract information about triangle clusters in the mesh To speed up bandwidth estimation for the Mean Shift aland delete the clusters of size less than 10. gorithm, we fix the quantile at 0.005 and use only point samples of size 500; we also enable the bin_seeding op3.2. Curvature-based algorithm tion for the Mean Shift algorithm to decrease its running time.
Curvature-based algorithm uses principal curvature information to match potentially symmetric points on the point cloud representing the 3D object. It proceeds in the following steps:
The result of these steps is an array-like structure of approved planes that take part in the final best symmetry plane voting described in Section 3.4.
Given a 3D mesh with vertices xi, i = 1, . . . , n, we form the point cloud and then create a k-d tree for fast
For each cluster, we iterate through all point pairs A and B and first check that their principal curvatures (1,, 2,) and (1, , 2, ) are approximately equal, in the sense that ⃒⃒ 1, ⃒ ⃒ 1, − 1⃒⃒ ≤ 1, ⃒⃒ 2, ⃒ ⃒ 2, − 1⃒⃒ ≤ 1, with some predefined curvature closeness threshold 1; if |1, | ≤ 1 or |2, | ≤ 1, then we require instead that |1,| ≤ 1 or |2,| ≤ 1, respectively.
For each point pair , that has passed the above test, we draw the median perpendicular plane and represent it via its Hough coordinates—the unit normal vector n and the (signed) distance to the origin. The mirror reflection is then given by
(x) = (3 − 2nn⊤)x + 2n, where 3 is the 3 × 3 identity matrix. We fix the direction of n so that its first non-zero entry is positive; the signed distance is then the scalar product of d and the vector −−→ from the origin to the midpoint of and .
In the next step, we perform the patch symmetry validation of . We form patches and of the points and consisting of their closest = 200 points of the point cloud. Then we mirror reflect to get ′ = () and check if adding it to does not significantly change the geometry of the latter. We transform ′ ∪ into a mesh, recalculate the curvatures (1′(x), 2′(x)) of each point x ∈ in this larger mesh, and compare them with the initial curvatures (1(x), 2(x)). If the mean squared error (MSE) (2) (3) 1 ∑︁
x∈ mse() = ︀( |1′(x)−1(x)|2+|2′(x)−2(x)|2)︀ (4) does not exceed some threshold , then the potential symmetry plane is validated, gets the weight () := 1/mse(), and is passed to the final majority vote.
To speed up the algorithm, we keep an array of planes that have already been rejected, and if a new plane is very close to one in the array, we skip the patch symmetry step and update the array with . To transform point clouds into meshes, we used the Ball Pivoting algorithm from the Open3D library [17]. 3.3. Edge-based algorithm Many man-made objects have edges or planar parts, for which curvatures are not well-defined or are uninformative. However, the edge lines in mirror-symmetric objects are also symmetric and can be used for symmetry detection. The edge-based algorithm exploits this and proceeds as follows:
1–8
Here we work directly with the point cloud representation of the 3D object. The point cloud is obtained from the mesh using the Poisson Disc Sampling algorithm implemented in the Open3D library [17].
The edge-based algorithm requires several parameters; most remain default (see Section 4.3). However, the following need to be tuned for each model: • quantile in the edge point clustering afects the number of clusters and thus the number of fitted lines; • line closeness threshold 2 sets tolerance within which two lines are considered parallel or intersecting and thus influences mirror symmetry precision; • line expansion option leads to improvement in some models; • edge detection threshold parameter can be left at the default value for most 3D objects, but, in some cases, a smaller value (allowing more edge candidates) leads to better performance.
In the first step, we iterate over points in the point cloud
and apply the detection algorithm of [
Following this observation, we fix = 200, denote by (p) the kNN of p, by c(p) the centroid of (p), introduce the spacing parameter and declare p a potential edge point if := q∈min(p) ‖p − q‖, ‖p − c(p)‖ > (5) (6) with edge detection threshold parameter . In that case, p is added to the list of potential edge points.
In the next step, we apply the Mean Shift clustering algorithm to detect clusters in the set of potential edge points, which will be fitted to lines. We enable bin_seeding for speed-up and use a predefined set of the quantile parameters for bandwidth estimation.
For each cluster of potential edge points of size at least 3, we run RANSAC with the LineModelND least square estimation [18] to fit a line. The algorithm returns a point on the fitted line and its unit direction vector. We save the number of inliers for each fitted line to be used as weights during the final symmetry plane voting. To ensure reproducibility, we set 100 as a predefined random state in RANSAC.
If the line expansion option is on, for each fitted line ℓ, we calculate the largest distance from ℓ to its inliers from the respective potential edge points cluster, then ifnd all the points of the point cloud that are within neighbourhood of ℓ, join them to the inlier set, and refit the line ℓ to this enlarged inlier set using LineModelND. Line expansion often helps in cases where edge detection is not accurate and some of the points on edges are missing.
At this point, we have a set of lines fitted to the edges of the 3D object, each parametrized by one of its points and unit direction vector d. Now we iterate through all line pairs, for those that are parallel or intersect, construct the corresponding symmetry planes, and skip pairs of skew lines.
Assume that given are the lines ℓ1(1, d1) and ℓ2(2, d2); we set q = −−1−→2 and perform the following steps.
1. Coplanarity check: The lines ℓ1 and ℓ2 are considered coplanar if the mixed product of the vectors d1, d1, and q is suficiently small, in the sense that
|(d1 × d2) · q| < 2‖q‖ with line closeness threshold 2. Otherwise, the lines are considered skew and thus are skipped. 2. Parallel lines: The lines ℓ1 and ℓ2 are parallel if their direction vectors d1 and d2 are collinear up to some tolerance, e.g., if
|d1 · d2| > 1 − 2; to make sure the lines do not coincide, we require that also ‖q‖ > 2 and |d1 · q| < (1 − 2)‖q‖. (7) (8) (9) 1–8 If the lines ℓ1 and ℓ2 have been declared parallel, then their symmetry plane is determined by its point that is the midpoint of 1 and 2 and the unit normal vector n that is collinear to q − (q · d1)d1; the distance from the plane to the origin in the Hough parametrization is then = (−−→1 + −−→2) · n/2. 3. Intersecting lines: Once the lines ℓ1 and ℓ2 have been found coplanar, not coincident, and not parallel, they are considered intersecting. Then there are two symmetry planes through the intersection point and with the unit normal vectors n collinear to d1 + d2 or d1 − d2, respectively. We identify as the midpoint of the interval 12 of the shortest length when 1 ∈ ℓ1 and 2 ∈ ℓ2. We find 1 = 1 + 1d1 and 2 = 2 +2d2 by noting that the vector −−1−→2 must be orthogonal to d1 and d2, so that (q + 2d2 − 1d1) · d1 = 0, (q + 2d2 − 1d1) · d2 = 0. (10) (11)
1, 2, their midpoint , and thus the two symmetry planes.
Symmetry planes constructed this way get their weights () equal to the smaller inlier numbers for the lines ℓ1 and ℓ2. After all symmetry planes have been found, we start the final symmetry plane voting. 3.4. Voting for the best symmetry plane In the previous two steps, we constructed lists of potential symmetry planes for the 3D object using curvaturebased and edge-based approaches. The best symmetry plane can now be chosen in three diferent ways: among the curvature-based planes only, among the edge-based planes only, or the best in the combined list. In the latter case, some preprocessing is needed to eliminate the efect of diferent scales of plane weights generated by the two methods.
The first option is to take best symmetry planes from each list, where is the smaller of two sizes, and the planes are ordered by their weights, from the largest to the smallest one. The second option is to rescale the weights for the curvature-based planes so that the total weights in both sets become equal. Experiments show that for some 3D objects, the first option is better, while for others—the second one, so we try both during the grid search of parameters.
Given the list of potential symmetry planes, we apply the Mean Shift clustering algorithm to determine the largest cluster. As a pre-processing step, we rescale the Hough coordinate for the planes to ˜ := /(max ||) (12) set. n* =
︀∑
cf. (12).
so that it should lie within the interval [
Now we choose the biggest cluster ℒ
weighted average as the best symmetry plane:
and take its
︀∑
∈ℒ
∈ℒ
()n()
()
,
˜* =
︀∑
︀∑
∈ℒ
∈ℒ
()()
()
(13)
we then rescale ˜* to its actual value * = ˜* · (max ||),
3.5. Model completion
cloud ∪
After the best hypothetical mirror symmetry for the
point cloud has been chosen, we use it to fill in the
missing or damaged parts of following the steps described
in [
′ decide if it should be added to .
We do that if and only if there are no points of among the = 6 nearest neighbors of p in the combined point ′. To speed up the kNN search, a k-d tree from this combined point cloud is constructed beforehand. measures are used (see Section 4.2).
If the ground truth model 0 is available, we can decide on the quality of completion using the Chamfer distance between 0 and the completed ; otherwise, some other
4.1. Dataset The suggested completion algorithm described in Section 3 uses both mesh representation of objects as well as point clouds created from these meshes. We chose the Princeton ModelNet40 3D object dataset [19] for algorithm evaluation. It ofers objects in 40 diferent categories. We selected 5 objects from each category that visually seemed symmetric. In this 200-object dataset, we transformed every mesh into a point cloud (of 50,000 points each) so that each original undamaged object is represented both by a mesh and a point cloud.
To make 3D objects suitable for the completion task, we inflicted damage to each of the meshes. From each object, a random number (between 1 and 10) of randomly placed regions of random size totaling approximately 15% of the original size was removed; in addition, for the curvature computing algorithm to work, we removed all small triangle clusters. Before damaging, each mesh was scaled to have approximately a unit surface area; this makes the resulting metrics better comparable. In some cases, we performed subdivision of triangles of original meshes to create more realistic damages. 4.2. Results and analysis We evaluated the developed algorithm on the generated dataset. For each object, we used a grid search with a time limit to find optimal parameters for solo and combined versions of the algorithm (see Section 4.3). With those optimal parameters, we ran the algorithm to produce the symmetry planes and the corresponding completion metrics and saved the best results for solo and combined algorithms. We used following metrics for result evaluation: 1. The Chamfer distance between the original undamaged object and the completed object. This metric tells us how well the damaged object was completed by our algorithm. 2. Improvement rate metric shows how much better is completion * relative to leaving the object uncompleted. When we get 0 it means that there was no completion, positive values indicate successful completion, and negative shows that during completion, points were added in places where they originally did not belong, and the object was deformed to some extent. With original (undamaged) object, this value is standing for the Chamfer distance and 0 the 100 * (1 − ( , 0)/( *, 0)).
(14)
Statistics, such as mean, median, minimum, and maximum values of the improvement rate, are presented in Completion Method
MSN [
GRNet [13]
Symmetry-Based [
Edge-based Curvature-based
Combined
Mean 4.3. Parameter tuning There are several parameters that control diferent aspects of the method. Some can only slightly alter precision, while others significantly afect the performance of the algorithm. To fine-tune the most important parameters for each object, we performed a grid search over a set of predefined choices established in numerous experiments on diferent meshes from several datasets; here is the resulting list: edge detection. Small quantiles create more edge clusters but slower computation; too big quantiles lead to fewer clusters and make the algorithm less accurate. Predefined range: 0.001, 0.00525, 0.007, 0.01, 0.0125, 0.025, 0.03, 0.035, 0.0375, 0.05, 0.07, 0.075, 0.1, 0.125, 0.15, 0.2. • Line closeness threshold 2 decides when points are considered coplanar and direction vectors collinear (absolute tolerance). Predefined range: 0.0001, 0.001, 0.003, 0.007, 0.01, 0.025, 0.0375, 0.05, 0.075, 0.1, 0.525, 0.7, 1, 1.5, 2. • In RANSAC and linear model for line fitting, we used a default value 10 for error and limited maximum number of iterations by 1000. • The boolean Enabling/disabling line expansion determines if the algorithm will perform an additional refitting step for each line or not. • Symmetry plane clustering quantile for bandwidth estimation, used during Mean Shift clustering for best symmetry plane detection; should not be too big as otherwise plane averaging over the largest cluster will sufer from noise. Predefined range: 0.0005, 0.001, 0.005, 0.008, 0.01, 0.015, 0.02, 0.05, 0.08, 0.1, 0.15, 0.2, 0.25, 0.3, 0.5, 0.7, 0.8, 1, 1.1, 1.5, 2, 2.5. • Curvature closeness threshold 1 controls the strictness of the comparison of curvatures of two points. The smaller it is (e.g., 0.001), the fewer points will be used to create symmetry planes, but the accuracy can be better. Usually, the real-world data contain noise and damages, so it is better to use a less strict threshold (e.g., 0.1) and mostly rely on a symmetry plane check on a neighboring patch of the points. Predefined range: 10−8, 10−3, 10−3, 0.01, 0.05, 0.07, 0.1, 0.8, 1. • Surface patch closeness threshold defines how strict the patch symmetry verification is. We mirror reflect a neighbourhood (the kNN with = 200) of the point , superimpose it with a neighbourhood of its symmetric candidate , and detect a change in the geometric shape. The threshold bounds from above the MSE of curva- Predefined sets of parameters, which we used for the tures in the neighbourhood of and thus con- grid search, were established through numerous experitrols the number of planes that pass. Predefined ments, including manual fine-tuning, modified bisection range: 0.001, 0.01, 0.05, 0.08, 0.1, 0.5, 0.8, 1, search, incrementing, etc. The grid search was then per1.2, 1.5, 1.8, 2, 2.5, 3. formed on each object from the dataset. • Number of neighbours in edge detection (200 by default) gives the size of a neighbourhood of a point p to determine if it is an edge point or not. 5. Conclusions • Edge detection threshold parameter (default 3 or 0.1 ) determines which points are regarded as In this paper, we proposed, described, and evaluated a edge points. Smaller softens the condition and four-stage pipeline (curvature matching, edge matching, increases the number of edge points. symmetry plane voting, object completion) of solving the • Edge points clustering quantile for bandwidth esti- completion task for previously unseen 3D objects posmation is used during Mean Shift clustering for sessing global mirror symmetry. This method uses the local geometries of an object represented by principal curvatures and/or edges. We presented the results by solo algorithms (based on curvatures matching or on edges matching) and a combined algorithm (that performs the voting on a combined set of weighted planes) on the part of the ModelNet40 dataset with random occlusions. The approach demonstrates competitive results in comparison with the best deep learning and a symmetry-based method.
Limitations of the proposed method are that