# Feature Preserving Filling of Holes on Point Sampled Surfaces Based on Tensor Voting

Authors: Hongbin Lin; Jieyun Chen; Yaru Zhang; Wei Wang; Deming Kong
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

This paper presents a novel hole filling method for the scattered point sampled surfaces, particularly for recovering the missing points at featured curves or corners. Firstly, a tensor voting based multicriterion is proposed to identify the hole boundary points; accordingly, the holes on point sampled surface are classified into featured holes and nonfeatured holes. Secondly, a novel spline curve guided tensor voting mechanism is proposed and used in inference of missing feature points. Thirdly, the featured holes are split into nonfeatured holes using local projection. Then, a plane guided tensor voting mechanism is proposed to recover the missing surface points. Experimental results validate the effectiveness and accuracy of proposed methods in filling holes on point sampled surface including the sharp features.


---

## Body

## 1. Introduction

Point sampled surfaces are sets of data points and can be acquired through three-coordinate measuring equipment. It is an important data source in reverse engineering and is widely used in many fields, such as industrial measurement, restoration of cultural relics, fashion design, and medical research [1]. Point cloud or point sampled surface has become an important form of digital media. However, for many reasons, such as occlusion, the damaging of original models, or limitation of scanners, the point cloud model of the original object may be incomplete and form different types of holes. These holes influence many subsequent operations, such as model rebuilding, rapid prototyping, and finite element analysis. Therefore it is necessary to fill and repair them in a reasonable manner.Although several hole filling methods have been proposed, it is worthy pointing out that most of them are suitable for some holes located on smooth regions (without missing feature points). However, an ideal hole filling algorithm should be able to deal with the complex holes including an island or one with missing sharp features. In addition, it should be able to preserve the geometric features of the original object. Due to the diversity and complexity of the holes, none of existing methods work for all holes.In this paper, we focus on the different holes that may have some locating on feature regions and present a novel feature preserving hole filling algorithm. Firstly, we determine the hole boundary and the incomplete feature curves and categorize the holes on point sampled surface into two types, the featured holes and the nonfeatured holes. Then, spline guided tensor voting was proposed and used to restore the missing part of feature curves. And these reconstructed feature curves split the original hole into simple subholes. Finally, all the nonfeatured holes were filled by the plane guided tensor voting. The main contributions of our algorithm can be summarized as follows:( 1 ) A multicriterion is developed in order to improve the reliability of hole boundary point identification. In the construction, the tensor voting based hole boundary identification criterion is proposed and combined with half disk criterion and maximum angle criterion.( 2 ) A spline curve guided tensor voting mechanism is proposed and used in inference of missing feature points, which gets rid of either the oversmoothed reconstruction of direct spline curve fitting or the inefficiency of traditional Single Sub-Voxel C Marching.( 3 ) A plane guided tensor voting mechanism is proposed and used in inference of surface points, to improve the accuracy and efficiency of the algorithm.The rest of this paper is organized as follows. The related work is briefly reviewed in Section2. Section 3 presents the outline of our method. Hole boundary point identification and hole classification methods are proposed in Section 4. Section 5 presents our feature point filling method. Our subhole filling method is described in Section 6. Section 7 presents the experimental results. And, in the last section, the limitations of our method and proposals for future research are indicated.


## 2. Related Work

Many holes filling algorithms have been proposed in recent years. In general, existing algorithms can be categorized into two types: mesh-based methods and point-based methods. At present, a large portion of methods is based on mesh models, which make use of topological information. Topological connection make the hole boundary identification and geometrical estimation easy; meanwhile, the topological reconstruction of incomplete point itself is still challenging. On the other hand, the point model is often obtained by scanning equipment and is easily affected by noise and not being able to deal directly with it. Thus, the geometrical estimation as well as hole filling directly on point sampled surface is more challenging than that on meshed surface.


### 2.1. Mesh-Based Methods

Mesh-based methods often fill holes locally with the rest of the surface unchanged. Liepa [2] used refinement and fairing to refine the obtained patch mesh, so that the triangle density coincide with that of the surrounding mesh. This method was further used by Attene [3]. Pernot et al. [4] filled holes by minimizing the curvature variant between the surrounding and inserted meshes.Another class of mesh-based methods is the volumetric based methods in which the mesh model is firstly converted into a volume representation. During the repairing process, the generation of a signed volume is the key step. Davis et al. [5] defined a signed distance function in the vicinity of the observed surface and applied a diffusion process to extend this function until its zero set bridged all holes. Ju [6] employed a space-efficient octree grid and generated blobby surfaces by recording Hermite data, to reproduce the sharp features.NURBS curves and surfaces are also a kind of repair tools for the holes located on smooth regions of a model. For these types of methods, one needs to choose weights and solve a large system of equations to compute the knot vectors. Piegl and Tiller [7] used NURBS patches to fill an n-sided region. Besides, Xu et al. [8] and Park et al. [9] proposed the surface filling method based on PDEs independently. Zhao et al. [10] proposed the mesh repair algorithm based on the Poisson equation.


### 2.2. Point-Based Method

The point model are often obtained by scanning equipment, and is easily affected by noise and not being able to deal directly with it. Thus, the geometrical estimation as well as hole filling directly on point sampled surface is more challenging than that on meshed surface. In this field, Sharf et al. [11] proposed a context-based method, in which, the characteristics of the given surface were analyzed, and the holes were iteratively filled by copying patches from valid regions of the given surface. Pavel and Bert [12] described a method for identifying and filling holes on point sampled surfaces; they fitted an algebraic surface patch to the neighborhood and sample auxiliary points. Chen et al. [13] proposed an algorithm based on the average error and average curvature to fill up hole areas of point sampled surfaces.Above-mentioned algorithms including the mesh-based methods and the point-based methods are able to fill certain holes precisely, while when the hole exhibits complex shapes, e.g., containing the sharp corners or edges of original model, the filling quality declines significantly. In response to this issue, a sensible strategy is to split the original complex hole into small subholes according to a feature analysis and then fill those small holes, respectively. The key step is to reconstruct missing parts of the feature curves in advance. Jun [14] presented a piecewise hole filling algorithm for complex holes. This algorithm incrementally splits a complex hole into small subholes with respect to the shape of the holes boundary and then fills 104 simple holes each with planar triangulation method. Li et al. [15] proposed a feature preserving mesh holes filling algorithm, which used a polynomial blending curve to construct the missing parts of the feature curves and used the Bézier-Lagrange hybrid patch to fill each subhole. Similarly, Wang et al. [16] used Gaussian mapping and convex/concave analysis to produce missing feature curves and filled each subhole by a modified advancing front method individually. Lin and Wang [17] presented a tensor voting based hole filling method for the scattered point cloud, particularly for recovering the missing points at featured curves or corners.It is worth mentioning that these methods are suitable for mesh model rather than point models. Feature preserving filling of complex holes directly on point sampled surface is still an issue. This paper extended the tenor voting based hole filling method proposed in [17] through novel feature curves reconstruction using spline guided tensor voting and recovering of nonfeatured points using plane guided tensor voting.


## 2.1. Mesh-Based Methods

Mesh-based methods often fill holes locally with the rest of the surface unchanged. Liepa [2] used refinement and fairing to refine the obtained patch mesh, so that the triangle density coincide with that of the surrounding mesh. This method was further used by Attene [3]. Pernot et al. [4] filled holes by minimizing the curvature variant between the surrounding and inserted meshes.Another class of mesh-based methods is the volumetric based methods in which the mesh model is firstly converted into a volume representation. During the repairing process, the generation of a signed volume is the key step. Davis et al. [5] defined a signed distance function in the vicinity of the observed surface and applied a diffusion process to extend this function until its zero set bridged all holes. Ju [6] employed a space-efficient octree grid and generated blobby surfaces by recording Hermite data, to reproduce the sharp features.NURBS curves and surfaces are also a kind of repair tools for the holes located on smooth regions of a model. For these types of methods, one needs to choose weights and solve a large system of equations to compute the knot vectors. Piegl and Tiller [7] used NURBS patches to fill an n-sided region. Besides, Xu et al. [8] and Park et al. [9] proposed the surface filling method based on PDEs independently. Zhao et al. [10] proposed the mesh repair algorithm based on the Poisson equation.


## 2.2. Point-Based Method

The point model are often obtained by scanning equipment, and is easily affected by noise and not being able to deal directly with it. Thus, the geometrical estimation as well as hole filling directly on point sampled surface is more challenging than that on meshed surface. In this field, Sharf et al. [11] proposed a context-based method, in which, the characteristics of the given surface were analyzed, and the holes were iteratively filled by copying patches from valid regions of the given surface. Pavel and Bert [12] described a method for identifying and filling holes on point sampled surfaces; they fitted an algebraic surface patch to the neighborhood and sample auxiliary points. Chen et al. [13] proposed an algorithm based on the average error and average curvature to fill up hole areas of point sampled surfaces.Above-mentioned algorithms including the mesh-based methods and the point-based methods are able to fill certain holes precisely, while when the hole exhibits complex shapes, e.g., containing the sharp corners or edges of original model, the filling quality declines significantly. In response to this issue, a sensible strategy is to split the original complex hole into small subholes according to a feature analysis and then fill those small holes, respectively. The key step is to reconstruct missing parts of the feature curves in advance. Jun [14] presented a piecewise hole filling algorithm for complex holes. This algorithm incrementally splits a complex hole into small subholes with respect to the shape of the holes boundary and then fills 104 simple holes each with planar triangulation method. Li et al. [15] proposed a feature preserving mesh holes filling algorithm, which used a polynomial blending curve to construct the missing parts of the feature curves and used the Bézier-Lagrange hybrid patch to fill each subhole. Similarly, Wang et al. [16] used Gaussian mapping and convex/concave analysis to produce missing feature curves and filled each subhole by a modified advancing front method individually. Lin and Wang [17] presented a tensor voting based hole filling method for the scattered point cloud, particularly for recovering the missing points at featured curves or corners.It is worth mentioning that these methods are suitable for mesh model rather than point models. Feature preserving filling of complex holes directly on point sampled surface is still an issue. This paper extended the tenor voting based hole filling method proposed in [17] through novel feature curves reconstruction using spline guided tensor voting and recovering of nonfeatured points using plane guided tensor voting.


## 3. Algorithm Overview

In this paper, we make use of the robust structure inference ability of tensor voting technique to identify the hole boundary points and infer the missing curve points and the surface points. Fundamental usage and further application of tensor voting technique can be found in [18–23].The procedure of the proposed hole filling method is illustrated in Figure1. Firstly, the multicriterion hole boundary point identification method is proposed based on tensor voting. Secondly, the feature points are identified using tensor voting; refer to [24]. Then, holes are classified into featured holes and nonfeatured holes by checking whether feature points are contained in the hole boundary points sets. Featured holes are firstly treated with feature sets matching [16], and then spline guided tensor voting is proposed and used in feature curves reconstruction. Finally, the featured holes are split into nonfeatured hole through local projection, and the nonfeatured holes are filled by proposed plane guided tensor voting. Due to this split and inference strategy, structures as well as sharp features of original model could be preserved effectively.Figure 1
Overview of the holes filling method.


## 4. Hole Classification

### 4.1. Hole Boundary Point Identification

Identification of hole boundary points can be challenging due to the deficiency of topological connection information in point sampled surface. Hence, a multicriterion hole boundary point identification method is proposed in this section based on tensor voting.LetP be a point sampled surface, p(x0,y0,z0) be a 3D point in P, and p1,p2,⋯,pk are neighbors of p. n(nx,ny,nz) is the normal at p, as illustrated in Figure 2.Figure 2
Illustration of neighboring projection.The local tangent plane Π atp can be expressed as nxx+nyy+nzz-(nxx0+nyy0+nzz0) = 0. Let pj′,  j=1,2,⋯,k, be the projected neighbors on Π along normal n.SupposeT∈R3×3 is voted tensor at point p and e1, e2, e3 and λ1, λ2, λ3 (where λ1≥λ2≥λ3≥0) are the eigen vectors and corresponding eigenvalues of T. Let us construct the tensor voting decision vector η=[η1,η2,η3]T by(1)η1=λ1λ1+λ2+λ3,η2=λ2λ1+λ2+λ3,η3=λ3λ1+λ2+λ3.According to tensor voting theory, the relationship between point type and constructed tensor voting decision vector can be concluded as in Table1.Table 1
The classification of points.
Decision vector Point type η1≫η2≈η3 Inner point η1≈η2≫η3 Curve point η1≈η2≈η3 Corner point or noise η1≫η2≫η3 Hole boundary pointLet us construct our tensor voting criterionfT(p,k) by(2)fTp,k=9η1-η2η2-η3,where p is the point to be analyzed and kis the neighboring number.Supposefθp,k is the hole boundary identifying function composed of the half disk criterion, defined as follows [25]:(3)fθp,k=θmax-2π/kπ-2π/k,where θmax is the maximum separated angle.Supposefgp,k is the hole boundary identifying function composed of the half disk criterion, defined as follows [25]:(4)fgp,k=3πg-p4r,where g=1/k∑i=1kpi′ is the gravity center of projected neighbors and r=1/k∑i=1kp-pi′ is the averaged distance between projected neighbors and point p.Finally, we construct our multicriterion hole boundary point identification functionF(p,k) by normalizing and weighting fθ(p,k), fg(p,k) and proposed fT(p,k) by(5)Fp,k=ωθGfθp,k+ωgGfgp,k+ωTGfTp,k,where Gx=x-xmin/xmax-xmin is the normalization function, ωθ, ωg, and ωT (fulfilling ωθ+ωg+ωT=1) are weights of the three identifying criterion, and xmin and xmax are the minimum and maximum value of the variable.Figure3 shows identifying results of hole boundary points using different methods, which reveals that the proposed multicriterion function is able to identify the hole boundary points reliably.Figure 3
Hole boundary points identifying results: (a) original point cloud, (b) partial enlarged detail of hole region, (c) identified result by maximum angle criterion, (d) identified result by half disk criterion, (e) identified result by tensor voting criterion, (f) identified result by proposed multicriterion method, (g) partial enlarged detail of identified result by maximum angle criterion, (h) partial enlarged detail of identified result by half disk criterion, (i) partial enlarged detail of identified result by tensor voting criterion, and (j) partial enlarged detail of identified result by proposed multicriterion method.
(a) (b) (c) (d) (e) (f) (g) (h) (i) (j)


### 4.2. Hole Classification

Considering the variety of holes and the efficiency of holes filling methods we simply classify the holes based on their feature. In recent years some methods of hole classification have been presented, and the general method are showed in [26]. This paper reclassifies the holes by checking whether the feature points are contained in the hole boundary point sets. Accordingly, all holes on point sampled surfaces are classified into featured holes, as shown in Figures 4(a), 4(b), and 4(c) or nonfeatured holes as shown in Figures 4(d) and 4(e).Figure 4
The basic hole classification: (a) single-close hole, (b) island-close hole, (c) unclosed hole, (d) featured closed hole, and (e) featured unclosed hole.
(a) (b) (c) (d) (e)


## 4.1. Hole Boundary Point Identification

Identification of hole boundary points can be challenging due to the deficiency of topological connection information in point sampled surface. Hence, a multicriterion hole boundary point identification method is proposed in this section based on tensor voting.LetP be a point sampled surface, p(x0,y0,z0) be a 3D point in P, and p1,p2,⋯,pk are neighbors of p. n(nx,ny,nz) is the normal at p, as illustrated in Figure 2.Figure 2
Illustration of neighboring projection.The local tangent plane Π atp can be expressed as nxx+nyy+nzz-(nxx0+nyy0+nzz0) = 0. Let pj′,  j=1,2,⋯,k, be the projected neighbors on Π along normal n.SupposeT∈R3×3 is voted tensor at point p and e1, e2, e3 and λ1, λ2, λ3 (where λ1≥λ2≥λ3≥0) are the eigen vectors and corresponding eigenvalues of T. Let us construct the tensor voting decision vector η=[η1,η2,η3]T by(1)η1=λ1λ1+λ2+λ3,η2=λ2λ1+λ2+λ3,η3=λ3λ1+λ2+λ3.According to tensor voting theory, the relationship between point type and constructed tensor voting decision vector can be concluded as in Table1.Table 1
The classification of points.
Decision vector Point type η1≫η2≈η3 Inner point η1≈η2≫η3 Curve point η1≈η2≈η3 Corner point or noise η1≫η2≫η3 Hole boundary pointLet us construct our tensor voting criterionfT(p,k) by(2)fTp,k=9η1-η2η2-η3,where p is the point to be analyzed and kis the neighboring number.Supposefθp,k is the hole boundary identifying function composed of the half disk criterion, defined as follows [25]:(3)fθp,k=θmax-2π/kπ-2π/k,where θmax is the maximum separated angle.Supposefgp,k is the hole boundary identifying function composed of the half disk criterion, defined as follows [25]:(4)fgp,k=3πg-p4r,where g=1/k∑i=1kpi′ is the gravity center of projected neighbors and r=1/k∑i=1kp-pi′ is the averaged distance between projected neighbors and point p.Finally, we construct our multicriterion hole boundary point identification functionF(p,k) by normalizing and weighting fθ(p,k), fg(p,k) and proposed fT(p,k) by(5)Fp,k=ωθGfθp,k+ωgGfgp,k+ωTGfTp,k,where Gx=x-xmin/xmax-xmin is the normalization function, ωθ, ωg, and ωT (fulfilling ωθ+ωg+ωT=1) are weights of the three identifying criterion, and xmin and xmax are the minimum and maximum value of the variable.Figure3 shows identifying results of hole boundary points using different methods, which reveals that the proposed multicriterion function is able to identify the hole boundary points reliably.Figure 3
Hole boundary points identifying results: (a) original point cloud, (b) partial enlarged detail of hole region, (c) identified result by maximum angle criterion, (d) identified result by half disk criterion, (e) identified result by tensor voting criterion, (f) identified result by proposed multicriterion method, (g) partial enlarged detail of identified result by maximum angle criterion, (h) partial enlarged detail of identified result by half disk criterion, (i) partial enlarged detail of identified result by tensor voting criterion, and (j) partial enlarged detail of identified result by proposed multicriterion method.
(a) (b) (c) (d) (e) (f) (g) (h) (i) (j)


## 4.2. Hole Classification

Considering the variety of holes and the efficiency of holes filling methods we simply classify the holes based on their feature. In recent years some methods of hole classification have been presented, and the general method are showed in [26]. This paper reclassifies the holes by checking whether the feature points are contained in the hole boundary point sets. Accordingly, all holes on point sampled surfaces are classified into featured holes, as shown in Figures 4(a), 4(b), and 4(c) or nonfeatured holes as shown in Figures 4(d) and 4(e).Figure 4
The basic hole classification: (a) single-close hole, (b) island-close hole, (c) unclosed hole, (d) featured closed hole, and (e) featured unclosed hole.
(a) (b) (c) (d) (e)


## 5. Feature Curve Reconstruction

In order to acquire satisfactory results in filling of complex holes (with missing sharp features), a reasonable method is to split the complex hole region combining the neighboring points into nonfeatured ones. In fact, multiple choices can be made for segmentation of the neighboring points. An effective way is the feature based region segmentation. Hence, reconstruction of feature curve and inference of curve structure within the hole region become the key operation.For inference of missing curve structure, a straight way is fitting or interpolating of the neighboring feature points. Unfortunately, this type of operation often achieves oversmoothed curve structure, leading to distortion in complex hole filling. Another substitution is the robust machine learning method, such as Single Sub-Voxel C march [27], which is highly related on tensor voting and Marching Cubes. This type of methods tends to repair the missing points accurately with feature preserving. But, the filling-and-judge strategy of Single Sub-Voxel C march restricts its potential efficiency, preventing its further application. Thus, this section presents a novel curve structure inference method, benefiting both from spline fitting and tensor voting.Firstly, feature sets are matched using tangent projection [16]. As shown in Figure 5, points v1 and v4 are matched. Meanwhile, points v2 and v3 are also matched.Figure 5
Illustration of the hole with missing feature.Afterwards, a new spline guided tensor voting strategy is proposed to infer the missing feature points, as illustrated in Figure6.Figure 6
Illustration of the feature curve reconstruction.Supposep1,p2,⋯ is the matched featured points and L is the fitted spline curve. o is a point on L, u and v span the normal plane of L at o, and ω is the normal of plane uv.(6)x=Fxt,y=Fyt,z=Fzt,Since L is the approximated feature curve, the real feature point must locate on the normal plane of L and receives local maximum plate tensor saliency (most probably being a curve point). Thus, we construct our local coordinate systemuvw as shown in Figure 6 and place four imagined points q1,q2,q3,q4 on uv around the circle centered at o, with radius r. The imagined points receive and accumulate tensor tokens voted from neighboring matched featured points p1,p2,···. Denote the tensor token at the four imaginary points by T1,T2,T3, and T4 independently. Similarly, denote the plate saliency at the four imaginary points by s1,s2,s3, and s4 independently. According to tensor voting theory, the real feature point holds the local maximum plate saliency on plane uv, which means ds/du=ds/dv=0, where s is the plate saliency of points on plane uv. Hence, the real feature point can be computed through interpolate of derivation of s1,s2,s3, and s4.Mechanism of the proposed feature point estimation method is illustrated in Figure7. Suppose gi,u=dsi/du,  gi,v=dsj/dv, where i,j=1,2,3,4. Since g2,u<0 and g3,u>0, hence a point g5,u=0 can be estimated by linear interpolation of g2,u and g3,u. Similarly, g6,u=0 can also be estimated. Thus, the points on the line connecting g5,u and g6,u are considered to hold ds/du=0. Similarly, another line with ds/dv=0 can also be estimated. And the feature point located on plane uv can be estimated by intersecting the two lines. In fact, the distribution of gi,u and gi,v on uv can be rather complicated, and the readers can refer to the Marching Cube type algorithms.Figure 7
Illustration of proposed feature point estimation.


## 6. Subhole Filling

After feature curves reconstruction, the complex holes combining with their neighbors can be split into simple ones. For this, we constructed a local projection plane through gravity center and averaged normal of hole boundary points. And then project the neighboring points and feature points on to the projection plane and segment the neighbor points by their relationship with the projected feature curve. Thus, the hole region and the neighboring points can be split into simple ones, as shown in Figure8.Figure 8
Illustration of holes filling without missing feature.In order to fill the nonfeatured simple holes, this section proposed a plane guide tensor voting method as follows.Step 1.
Project all hole boundary points onto a local projection plane defined by gravity center and averaged normal of hole boundary points, as shown in Figure9(a). In fact, the gravity center p- of the hole and the averaged normal n- of the projection plane can be computed by(7)p-=1l∑j=1lpj=x0,y0,z0T,(8)n-=1l∑j=1lnj=nx,ny,nzT,where pj is the jth hole boundary point, nj is the normal of the pj. The projection plane defined by p- and n- can be expressed as follows:(9)xj′yj′zj′=xjyjzj-kjnxnynz,where(10)kj=nxxj-x0+nyyj-y0+nzzj-z0nx2+ny2+nz2.Figure 9
Illustration of holes filling without missing feature: (a) hole boundary projection, (b) distribution of distribution points, and (c) distribution of imaginary points.
(a) (b) (c)Step 2.
Distribute the distribution points on hole projection plane evenly, as shown in Figure9(b). Denote the distance between pj′ and p- by dj. Suppose the average distance between neighboring points within the original point sampled surface is d; then distribute the distribution points with regular distances as shown in Table 2.Table 2
The number of distribution points.
Interval ( 0 ,  d / 2 ] ( d / 2 ,  d ] ( d ,  3 d / 2 ] ( 3 d / 2 ,  2 d ] ⋯ Count 0 1 2 3 ⋯The coordinates of each distribution point can be precisely computed. As shown in Figure9(b), the coordinates of distribution points p1a′ and p1b′ between p1′ and p- can be computed by(11)x1a′y1a′z1a′=x1′y1′z1′+d3d1x0-x1′y0-y1′z0-z1′,and(12)x1b′y1b′z1b′=x1′y1′z1′+2d3d1x0-x1′y0-y1′z0-z1′.Step 3.
Distribute evenly the imaginary points along the normal of the hole projection plane, and each surface saliencies of the imaginary points is accurately computed. As shown in Figure9(c), the point set p1a1′,p1a2′,⋯,p1a7′, for example, is the imaginary points of the distribution point p1a1′ along the normal n-, and the spacing of two consecutive imaginary points is the original point cloud density d. The coordinates of imaginary point p1ak′,  1≤k≤7, can be computed as follows:(13)x1ai′y1ai′z1ai′=x1a′y1a′z1a′+i-4dnxnynz,i=1,2,⋯,7.After determining the coordinates of imaginary points, their refined tensor tokens are required by dense tensor voting using existing points belonging to the same areas and decomposed to compute the surface saliencies.Step 4.
In order to further accurately calculate the filling point coordinates, two-order polynomial method fit method is put forward to estimate the extreme of surface saliencies.Suppose the set of imaginary pointsp1a1′,p1a2′,⋯,p1a7′ corresponding surface saliencies, respectively, is s1a1,s1a2,⋯,s1a7. We firstly construct the 2D local coordinate system where the normal n- corresponds to horizontal axle and the surface saliency corresponds to vertical axle, as shown in Figure 10, where b is the vertical distance from the imaginary point and the projection plane, and its sign is decided by their relative location. Then, the coefficients of a quadratic curve equation are estimated. The extreme of surface saliency is computed, when b′=-B/2A.(14)y=Ax2+Bx+C.Figure 10
Illustration of the two-order polynomial method fit method.


## 7. Experimental Results

This section performs our feature preserving holes filling experiments, which is coded with C++, running on Visual Studio 2010 software and Windows systems. In order to examine the performances of the algorithm on filling four types of holes (holes on plane, smoothed surface, with missing sharp curve, with missing corner), the Fandisk model was selected as the fundamental model for its possession of all these features. In our experiments, the techniques by Davis et al. [5] and by Centin et al. [28] were also used to fill the same holes for comparison. In order to better observe the experimental results, we demonstrate the meshed Fandisk models and hole areas.


### 7.1. Filling of Simple Holes

In order to examine the performances of the algorithm on filling simple holes, holes on plane (Hole I) and smooth surface (Hole II) are artificially generated and then filled by [5, 28] and proposed method.As shown in Figure11, Davis yields biased estimation for missing plane points, Centin’s methods and proposed method achieve almost flat recovery without error, and numerical static error can be found in Table 3. This type of hole can also be ideally filled by plane extension for simplicity.Table 3
The distances from repair points to the original surface.
type Hole Maximum(mm) Average(mm) Davis et al. Centin et al. Our method Davis et al. Centin et al. Our method I 0.19 0.00 0.00 (σ= 0.3) 0.14 0.00 0.00 (σ= 0.3) II 0.21 0.07 0.15 (σ= 0.2) 0.04 0.03 0.04 (σ= 0.2) III 0.33 0.87 0.01 (σ= 0.3) 0.05 0.60 0.00 (σ= 0.3) IV 0.52 0.96 0.25 (σ= 0.3) 0.06 0.43 0.03 (σ= 0.3) V 1.10 2.20 0.14 (σ= 0.2) 0.13 0.88 0.02 (σ= 0.2)Figure 11
Visualization of filled results of Hole I. (a) Hole located on plane. (b) Filling result of Davis et al. (c) Filling result of Centin et al. (d) Proposed result.
(a) (b) (c) (d)As shown in Figure12, Centin’s method yields ideal smoothed recovery of missing points on surface; the other two methods yield biased estimation. Numerical static error shows that the proposed method yields better maximum error than Davis’s. And the three methods yield similar averaged error. Centin’s methods achieve best performance on smooth surface filling. Plane extension filling of this type of holes tends to yield relative large residue distortion near the center of the hole, while the NURBS surface extension often yields better accuracy.Figure 12
Visualization of filled results of Hole II. (a) Hole located on smooth surface. (b) Filling result of Davis et al. (c) Filling result of Centin et al. (d) Proposed result.
(a) (b) (c) (d)


### 7.2. Filling of Complex Holes

In order to examine the performances of the algorithm on filling complex holes, holes with missing curve points (Hole III and Hole IV) or corner points (Hole V) are artificially generated. And then, they are filled by [5, 28] and proposed method.As shown in Figure13, Davis’s and Centin’s methods yield biased estimation for filling of holes with missing feature points, and our proposed method achieves almost ideal recovery without error. Numerical results in Table 3 also validate the accuracy of our proposed method in filling of these types of holes.Figure 13
Visualization of filled results of Hole III. (a) Hole with sharp feature missing. (b) Filling result of Davis et al. (c) Filling result of Centin et al. (d) Our result.
(a) (b) (c) (d)As shown in Figure14, our proposed method performs far better than Davis’s and Centin’s methods for filling of holes with missing curve points. Numerical results in Table 3 also validate the accuracy of our proposed method in filling of these types of holes.Figure 14
Visualization of filled results of Hole IV. (a) Hole with sharp feature missing. (b) Filling result of Davis et al. (c) Filling result of Centin et al. (d) Our result.
(a) (b) (c) (d)As shown in Figure15, our proposed method performs far better than Davis’s and Centin’s methods for filling of holes with missing corner points. Numerical results in Table 3 also validate the accuracy of our proposed method in filling of these types of holes.Figure 15
Visualization of filled results of hole V. (a) Fandisk with a missing corner. (b) Filling result of Davis et al. (c) Filling result of Centin et al. (d) Our result.
(a) (b) (c) (d)In fact, the complex holes are difficult to be filled through simple plane or fitted surface extension without reliable neighboring segmentation and robust surface fitting. In addition, post-point sampled surface smoothing is often involved for better transition between different surfaces.


### 7.3. Accuracy Analysis

In this subsection, the maximum and averaged errors in filling of hole using three methods are computed and arranged in Table3. It can be summarized from Table 3 that the proposed hole filling method for point sampled surface yields better accuracy than Centin’s and Davis’s methods, especially for holes with missing sharp features.


### 7.4. Parameter Analysis

In our method, the scale parameterσ in tensor voting is also a user defined parameter. This parameter influences both the accuracy and the robustness of the algorithm. Thus, experiments with different σ values are performed, and the maximum and averaged error are computed and plotted in Figure 16. In our experiments, σ increase from 0.1 to 0.9. As shown in Figure 16, the algorithm achieves best performance for both maximum and averaged error for σ ≈ 0.25. In fact, σ determines the attenuating rate of the energy decay function in tensor voting. Larger σ tends to achieve smoothed but biased estimation. And smaller σ tends to achieve unbiased but noisy estimation.Figure 16
Distances comparison between different attenuation factors. (a) Maximum distances. (b) Average distances.
(a) (b)


### 7.5. Complexity and Efficiency Analysis

This paper presented a novel feature preserving hole filling method for point sampled surface, especially on multicriterion based hole boundary identification, spline guided tensor voting based missing feature point estimation, and plane guided tensor voting based surface point estimation.The spline guided tensor voting based missing feature point estimation strategy gets rid of either the oversmoothed reconstruction caused by direct spline curve fitting, or the inefficiency of traditional Single Sub-Voxel C Marching. The spline curve provides the most probable estimation for the potential feature point. Then, the tensor voting is used to rectify the estimation in order to achieve a more accurate estimation. Concerning efficiency, the proposed method needs only 4 votes, while the traditional Single Sub-Voxel C Marching needs at least 8 votes (8 vertex of a cube), for one estimation. Furthermore, the traditional Single Sub-Voxel C Marching needs to try multiple cubes for one estimation. Thus, the proposed spline guided tensor voting based missing feature point estimation strategy yields far better efficiency than Single Sub-Voxel C Marching.The plane guided tensor voting based surface point estimation makes use of plane prediction and tensor voting rectification. Concerning accuracy, the proposed method achieves quadratic estimation for surface point estimation while the traditional Marching Cubes algorithm provides linear estimation. Concerning efficiency, the proposed method needs 3 votes for each surface point estimation, while the traditional Marching Cubes algorithm needs at least 8 votes.


## 7.1. Filling of Simple Holes

In order to examine the performances of the algorithm on filling simple holes, holes on plane (Hole I) and smooth surface (Hole II) are artificially generated and then filled by [5, 28] and proposed method.As shown in Figure11, Davis yields biased estimation for missing plane points, Centin’s methods and proposed method achieve almost flat recovery without error, and numerical static error can be found in Table 3. This type of hole can also be ideally filled by plane extension for simplicity.Table 3
The distances from repair points to the original surface.
type Hole Maximum(mm) Average(mm) Davis et al. Centin et al. Our method Davis et al. Centin et al. Our method I 0.19 0.00 0.00 (σ= 0.3) 0.14 0.00 0.00 (σ= 0.3) II 0.21 0.07 0.15 (σ= 0.2) 0.04 0.03 0.04 (σ= 0.2) III 0.33 0.87 0.01 (σ= 0.3) 0.05 0.60 0.00 (σ= 0.3) IV 0.52 0.96 0.25 (σ= 0.3) 0.06 0.43 0.03 (σ= 0.3) V 1.10 2.20 0.14 (σ= 0.2) 0.13 0.88 0.02 (σ= 0.2)Figure 11
Visualization of filled results of Hole I. (a) Hole located on plane. (b) Filling result of Davis et al. (c) Filling result of Centin et al. (d) Proposed result.
(a) (b) (c) (d)As shown in Figure12, Centin’s method yields ideal smoothed recovery of missing points on surface; the other two methods yield biased estimation. Numerical static error shows that the proposed method yields better maximum error than Davis’s. And the three methods yield similar averaged error. Centin’s methods achieve best performance on smooth surface filling. Plane extension filling of this type of holes tends to yield relative large residue distortion near the center of the hole, while the NURBS surface extension often yields better accuracy.Figure 12
Visualization of filled results of Hole II. (a) Hole located on smooth surface. (b) Filling result of Davis et al. (c) Filling result of Centin et al. (d) Proposed result.
(a) (b) (c) (d)


## 7.2. Filling of Complex Holes

In order to examine the performances of the algorithm on filling complex holes, holes with missing curve points (Hole III and Hole IV) or corner points (Hole V) are artificially generated. And then, they are filled by [5, 28] and proposed method.As shown in Figure13, Davis’s and Centin’s methods yield biased estimation for filling of holes with missing feature points, and our proposed method achieves almost ideal recovery without error. Numerical results in Table 3 also validate the accuracy of our proposed method in filling of these types of holes.Figure 13
Visualization of filled results of Hole III. (a) Hole with sharp feature missing. (b) Filling result of Davis et al. (c) Filling result of Centin et al. (d) Our result.
(a) (b) (c) (d)As shown in Figure14, our proposed method performs far better than Davis’s and Centin’s methods for filling of holes with missing curve points. Numerical results in Table 3 also validate the accuracy of our proposed method in filling of these types of holes.Figure 14
Visualization of filled results of Hole IV. (a) Hole with sharp feature missing. (b) Filling result of Davis et al. (c) Filling result of Centin et al. (d) Our result.
(a) (b) (c) (d)As shown in Figure15, our proposed method performs far better than Davis’s and Centin’s methods for filling of holes with missing corner points. Numerical results in Table 3 also validate the accuracy of our proposed method in filling of these types of holes.Figure 15
Visualization of filled results of hole V. (a) Fandisk with a missing corner. (b) Filling result of Davis et al. (c) Filling result of Centin et al. (d) Our result.
(a) (b) (c) (d)In fact, the complex holes are difficult to be filled through simple plane or fitted surface extension without reliable neighboring segmentation and robust surface fitting. In addition, post-point sampled surface smoothing is often involved for better transition between different surfaces.


## 7.3. Accuracy Analysis

In this subsection, the maximum and averaged errors in filling of hole using three methods are computed and arranged in Table3. It can be summarized from Table 3 that the proposed hole filling method for point sampled surface yields better accuracy than Centin’s and Davis’s methods, especially for holes with missing sharp features.


## 7.4. Parameter Analysis

In our method, the scale parameterσ in tensor voting is also a user defined parameter. This parameter influences both the accuracy and the robustness of the algorithm. Thus, experiments with different σ values are performed, and the maximum and averaged error are computed and plotted in Figure 16. In our experiments, σ increase from 0.1 to 0.9. As shown in Figure 16, the algorithm achieves best performance for both maximum and averaged error for σ ≈ 0.25. In fact, σ determines the attenuating rate of the energy decay function in tensor voting. Larger σ tends to achieve smoothed but biased estimation. And smaller σ tends to achieve unbiased but noisy estimation.Figure 16
Distances comparison between different attenuation factors. (a) Maximum distances. (b) Average distances.
(a) (b)


## 7.5. Complexity and Efficiency Analysis

This paper presented a novel feature preserving hole filling method for point sampled surface, especially on multicriterion based hole boundary identification, spline guided tensor voting based missing feature point estimation, and plane guided tensor voting based surface point estimation.The spline guided tensor voting based missing feature point estimation strategy gets rid of either the oversmoothed reconstruction caused by direct spline curve fitting, or the inefficiency of traditional Single Sub-Voxel C Marching. The spline curve provides the most probable estimation for the potential feature point. Then, the tensor voting is used to rectify the estimation in order to achieve a more accurate estimation. Concerning efficiency, the proposed method needs only 4 votes, while the traditional Single Sub-Voxel C Marching needs at least 8 votes (8 vertex of a cube), for one estimation. Furthermore, the traditional Single Sub-Voxel C Marching needs to try multiple cubes for one estimation. Thus, the proposed spline guided tensor voting based missing feature point estimation strategy yields far better efficiency than Single Sub-Voxel C Marching.The plane guided tensor voting based surface point estimation makes use of plane prediction and tensor voting rectification. Concerning accuracy, the proposed method achieves quadratic estimation for surface point estimation while the traditional Marching Cubes algorithm provides linear estimation. Concerning efficiency, the proposed method needs 3 votes for each surface point estimation, while the traditional Marching Cubes algorithm needs at least 8 votes.


## 8. Conclusions and Remarks

This paper proposed a new feature preserving hole filling algorithm to point sampled surface. A novel hole multicriterion based boundary identification method for point sampled surface is proposed to improve the reliability of hole boundary point identification. A spline curve guided tensor voting method is proposed to infer the missing feature points. A plane guided tensor voting mechanism is proposed to infer the missing surface points. Experimental results validate the effectiveness and accuracy of our proposed methods in recovering holes on point sampled surface including the sharp features.In future research, the authors tend to work on adaptive scaling and higher order tensor voting and its application in repairing of higher order data, e.g., simultaneous repairing of texture and geometrical information of 373 textured point cloud.



---

*Source: 8076910-2018-08-14.xml*