参考文献Reconstruction and Representation of 3D Objects with Radial Basis

1、Reconstruction and Representation of 3D Objects with Radial Basis Functions J. C. Carr1,2R. K. Beatson2J. B. Cherrie1T. J. Mitchell1,2W. R. Fright1B. C. McCallum1 T. R. Evans1 1Applied Research Associates NZ Ltd 2University of Canterbury (a)(b) Figure 1: (a) Fitting a Radial Basis Function (RBF) to

2、a 438,000 point-cloud. (b) Automatic mesh repair using the biharmonic RBF. Abstract We use polyharmonic Radial Basis Functions (RBFs) to reconstruct smooth, manifold surfaces from point-cloud data and to repair in- complete meshes. An objects surface is defi ned implicitly as the zero set of an RBF

3、fi tted to the given surface data. Fast methods for fi tting and evaluating RBFs allow us to model large data sets, con- sisting of millions of surface points, by a single RBFpreviously an impossible task. A greedy algorithm in the fi tting process re- ducesthenumberofRBFcentersrequiredtorepresentas

4、urfaceand results in signifi cant compression and further computational advan- tages. The energy-minimisation characterisation of polyharmonic splines result in a “smoothest” interpolant. This scale-independent characterisation is well-suited to reconstructing surfaces from non- uniformly sampled da

5、ta. Holes are smoothly fi lled and surfaces smoothly extrapolated. We use a non-interpolating approximation when the data is noisy. The functional representation is in effect a solid model, which means that gradients and surface normals can be determined analytically. This helps generate uniform mes

6、hes and we show that the RBF representation has advantages for mesh simplifi cation and remeshing applications. Results are presented for real-world rangefi nder data. CR Categories:I.3.5 Computer Graphics: Computational Ge- ometry and Object ModelingCurve, surface, solid, and object representations

7、; Keywords:Variational implicit surfaces, Radial Basis Function, RBF, mesh repair, point-cloud surfacing, surface reconstruction, geometry compression, solid modeling. Applied Research Associates NZ Ltd, PO Box 3894, Christchurch, New Zealand.Email:j.carr,j.cherrie,r.fright,b.mccallum Web: Dept. Mat

8、hematics and Statistics,University of Canterbury, Christchurch, New Zealand, Email: r.beatsonmath.canterbury.ac.nz 1Introduction Interpolating incomplete meshes (hole-fi lling) and reconstructing surfaces from point-clouds derived from 3D range scanners are ubiquitous problems in computer graphics a

9、nd Computer Aided Design (CAD). Smoothly blending between surfaces and ensuring surfaces are manifold, and therefore manufacturable, are related problems in CAD. Similarly, smoothing and remeshing existing noisy surfaces are important problems in both CAD and computer graphics. These problems have m

10、ostly been considered indepen- dent from one another and received much attention in the litera- ture (see 8 and the references therein). In this paper we propose that the implicit representation of object surfaces with Radial Basis Functions (RBFs) simplifi es many of these problems and offers a uni

11、fi ed framework that is simple and elegant. An RBF offers a com- pact functional description of a set of surface data. Interpolation and extrapolation are inherent in the functional representation. The RBF associated with a surface can be evaluated anywhere to pro- duce a mesh at the desired resolut

12、ion. Gradients and higher deriva- tives are determined analytically and are continuous and smooth, depending on the choice of basic function. Surface normals are therefore reliably calculated and iso-surfaces extracted from the im- plicit RBF model are manifold (i.e., they do not self-intersect). Th

13、e benefi ts of modeling surfaces with RBFs have been recog- nised by Savchenko 19, Carr et al. 10 and by Turk estimating surface normals and determining the appropriate projection distance. If we have a partial mesh, then it is straightforward to defi ne off- surface points since normals are implied

14、 by the mesh connectivity at each vertex. In the case of unorganised point-cloud data, nor- mals may be estimated from a local neighbourhood of points. This requires estimating both the normal direction and determining the sense of the normal. We locally approximate the point-cloud data with a plane

15、 to estimate the normal direction and use consistency and/or additional information such as scanner position to resolve the sense of the normal. In general, it is diffi cult to robustly es- timate normals everywhere. However, unlike other methods 16 which also rely on forming a signed-distance funct

16、ion, it is not crit- ical to estimate normals everywhere. If normal direction or sense is ambiguous at a particular point then we do not fi t to a normal at that point. Instead, we let the fact that the data point is a zero-point (lies on the surface) tie down the function in that region. Given a se

17、t of surface normals, care must be taken when pro- jecting off-surface points along the normals to ensure that they do not intersect other parts of the surface. The projected point is constructed so that the closest surface point is the surface point that generated it. Provided this constraint is sa

18、tisfi ed, the recon- structed surface is relatively insensitive to the projection distance |di|. Fig. 3(c) illustrates the effect of projecting off-surface points inappropriate distances along normals.Off-surface points have been chosen to lie a fi xed distance from the surface. The result- ing surf

19、ace, where f is zero, is distorted in the vicinity of the fi n- gers where opposing normal vectors have intersected and generated off-surface points with incorrect distance-to-surface values, both in sign and magnitude. In Fig. 3(a) & (b) validation of off-surface dis- tances and dynamic projection

20、has ensured that off-surface points produce a distance fi eld consistent with the surface data. Fig. 4 is a cross section through the fi ngers of the hand. The fi gure illustrates how the RBF function approximates a distance function near the objects surface. The approximately equally spaced iso-con

21、tours at +1, 0 and 1 in the top of the fi gure and the corresponding function profi le below, illustrate how the off-surface points have generated a function with a gradient magnitude close to 1 near the surface (which corresponds to the zero-crossings in the profi le shown). Figure 4: Cross section

22、 through the fi ngers of a hand reconstructed from the point-cloud in Fig. 3. The iso-contours corresponding to +1, 0 and -1 are shown (top) along with a cross sectional profi le of the RBF (bottom) along the line shown. 3Radial Basis Function interpolation Given a set of zero-valued surface points

23、and non-zero off-surface points we now have a scattered data interpolation problem: we want to approximate the signed-distance function f(x) by an interpolant s(x). The problem can be stated formally as follows, Problem 3.1. Given a set of distinct nodes X = xiN i=1 R3 and a set of function values f

24、iN i=1 R, fi nd an interpolant s : R3 R such that s(xi) = fi,i = 1,.,N.(2) Note that we use the notation x = (x,y,z) for points x R3. The interpolant will be chosen from BL(2)(R3), the Beppo-Levi space of distributions on R3with square integrable second deriva- tives. This space is suffi ciently lar

25、ge to have many solutions to Problem 3.1, and therefore we can defi ne the affi ne space of inter- polants: S = s BL(2)(R3) : s(xi) = fi,i = 1,.,N.(3) The space BL(2)(R3) is equipped with the rotation invariant semi- norm defi ned by ksk2= Z R3 ?2s(x) x2 ?2 + ?2s(x) y2 ?2 + ?2s(x) z2 ?2 +2 ?2s(x) xy

26、 ?2 +2 ?2s(x) xz ?2 +2 ?2s(x) yz ?2 dx.(4) Thissemi-normisameasureoftheenergyor“smoothness”offunc- tions: functions with a small semi-norm are smoother than those with a large semi-norm. Duchon 12 showed that the smoothest interpolant, i.e., s?= argmin sS ksk, has the simple form s?(x) = p(x)+ N i=1

27、 i|xxi|,(5) where p is a linear polynomial, the coeffi cients iare real numbers and | is the Euclidean norm on R3. This function is a particular example of a radial basis function (RBF). In general, an RBF is a function of the form s(x) = p(x)+ N i=1 i(|xxi|),(6) where p is a polynomial of low degre

28、e and the basic function is a real valued function on 0,), usually unbounded and of non- compact support (see, e.g., Cheney & Light 11). In this context the points xiare referred to as the centers of the RBF. Popular choices for the basic function include the thin-plate spline (r) = r2 log(r) (for f

29、i tting smooth functions of two vari- ables), the Gaussian (r) = exp(cr2) (mainly for neural net- works), and the multiquadric (r) = r2 +c2(for various appli- cations, in particular fi tting to topographical data). For fi tting functions of three variables, good choices include the biharmonic (r) =

30、r, i.e., Equation (5) and triharmonic (r) = r3) splines. RBFs are popular for interpolating scattered data as the associ- ated system of linear equations is guaranteed to be invertible under very mild conditions on the locations of the data points 11, 18. For example, the biharmonic spline of Equati

31、on (5) only requires that the data points are not co-planar, while the Gaussian and mul- tiquadric place no restrictions on the locations of the points. In par- ticular, RBFs do not require that the data lie on any sort of regular grid. An arbitrary choice of coeffi cients iin Equation (5) will yiel

32、d a function s?that is not a member of BL(2)(R3). The requirement that s? BL(2)(R3) implies the orthogonality or side conditions N i=1 i= N i=1 ixi= N i=1 iyi= N i=1 izi= 0. More generally, if the polynomial in Equation (6) is of degree m then the side conditions imposed on the coeffi cients are N i

33、=1 iq(xi) = 0, for all polynomials q of degree at most m.(7) These side conditions along with the interpolation conditions of Equation (2) lead to a linear system to solve for the coeffi cients that specify the RBF. Let p1,.,p be a basis for polynomials of degree at most m and let c=(c1,.,c ) be the

34、 coeffi cients that give p in terms of this basis. Then Equations (2) and (7) may be written in matrix form as ? AP PT0 ? c ? = B ? c ? = ? f 0 ? ,(8) where Ai,j= (|xixj|),i, j = 1,.,N, Pi,j= pj(xi),i = 1,.,N,j = 1,.,. In the specifi c case of the biharmonic spline in 3D, if it is assumed that the p

35、olynomial part of the RBF in Equation (5) has the form p(x) = c1+c2x+c3y+c4z, then Ai,j= |xixj|,i, j = 1,.,N, P is the matrix with ith row (1,xi,yi,zi), = (1,.,N)Tand c = (c1,c2,c3,c4)T. Solving the linear system (8) determines and c, and hence s(x). However, the matrix B in Equation (8) typically h

36、as poor condi- tioning as the number of data points N gets larger. This means that substantial errors will easily creep into any standard numerical so- lution. On initial inspection, the essentially local nature of the Gaus- sian, inverse multiquadric (r) = (r2+c2)1/2) and compactly supported basic

37、functions appear to lead to more desirable prop- erties in the RBF. For example, the matrix B now has special struc- ture (sparsity) which can be exploited by well-known methods and evaluation of Equation (6) only requires that the sum be over nearby centers instead of all N centers. However, non-co

38、mpactly supported basic functions are better suited to extrapolation and interpolation of irregular, non-uniformly sampled data. Indeed, numerical exper- iments using Gaussian and compactly supported piecewise polyno- mialsforfi ttingsurfacestopoint-cloudshaveshownthatthesebasic functions yield surf

39、aces with many undesirable artifacts in addition to the lack of extrapolation across holes. The energy minimisation properties of biharmonic splines make them well suited to the representation of 3D objects. Since the corresponding basic function (r) = r is not compactly supported and grows arbitrar

40、ily large as r tends to infi nity, the correspond- ing matrix B of Equation (8) is not sparse and, except for symme- try, has no obvious structure that can be exploited in solving the system. Storing the lower triangle of matrix B requires space for N(N +1)/2 real numbers. Solution via a symmetric s

41、olver will re- quire N3/6+O(N2 ) fl ops. For a problem with 20,000 data points this is a requirement for approximately 1.6109bytes (1.5GB) of core memory, and 1013 fl ops, which is impractical. Further- more, ill-conditioning of the matrix B is likely to make any solution one gets from such a direct

42、 computation highly unreliable. Thus, it is clear that direct methods are inappropriate for problems with N & 2,000. Moreover, a single direct evaluation of Equation (6) requiresO(N) operations. These factors have led many authors to conclude that, although RBFs are often the interpolant of choice,

43、they are only suitable for problems with at most a few thousand points 13, 14, 20. The fast methods described in the following section demonstrate that this is no longer the case. Figure 6: A greedy algorithm iteratively fi ts an RBF to a point cloud resulting in fewer centers in the fi nal function

44、. In this case the 544,000 point cloud is represented by 80,000 centres to a relative accuracy of 5104 in the fi nal frame. output surface evaluation accuracy fitted RBF fitting accuracies output evaluation points interpolation nodes Figure 5: Illustration of the fast fi tting and evaluation paramet

45、ers. Direct methodsFast methods Fitting storage requiredN(N+1)/2O(N) fl ops to solve systemN3/6+O(N2)O(NlogN) Evaluation fl ops per evaluationO(N)O(1) after O(NlogN) setup Table 1: Comparison of direct and fast methods. 4Fast methods Fast evaluation of RBFs is performed via the Fast Multipole Method

46、 (FMM) of Greengard & Rokhlin 15. The FMM was de- signed for the fast evaluation of potentials (harmonic RBFs) in two and three dimensions. However Beatson et al. 7 have adapted the expansion and translation theory for the potential to higher order polyharmonic RBFs. Note that polyharmonic RBFs incl

47、ude the bi- harmonic spline of Equation (5). The FMM may also be used with polyharmonic splines in two 5 and four dimensions 3. A full description of the FMM is beyond the scope of this paper and the interested reader is directed towards the introductory short course 4 for an expository treatment of

48、 the FMM. However, we give a brief outline of the method. The FMM makes use of the simple fact that when computations are performed, infi nite precision is neither required nor expected. Once this is realised, the use of approximations is allowed. For the evaluation of an RBF, the approximations of

49、choice are far- and near-fi eld expansions. With the centers clustered in a hierarchical manner, far- and near-fi eld expansions are used to generate an ap- proximation to that part of the RBF due to the centers in a particular cluster. A judicious use of approximate evaluation for clusters “far” fr

50、om an evaluation point and direct evaluation for clusters “near” to an evaluation point allows the RBF to be computed to any prede- termined accuracy and with a signifi cant decrease in computation time compared with direct evaluation. These fast evaluation methods, when used together with fi tting

51、methods particular to RBFs 2, 6, greatly reduce the storage and computational costs of using RBFs. They reduce the cost of evalu- ating s(x) at M points fromO(MN) toO(M+NlogN) operations. The cost of simultaneously computing the gradient s(x) with s(x) is approximately twice that of computing s(x) a

52、lone. Table 1 sum- marises the gains of fast methods over direct methods. Fig. 5 illustrates two parameters introduced by fast methods: a fi tting accuracy and an evaluation accuracy. The fi tting accuracy specifi es the maximum allowed deviation of the fi tted RBF value from the specifi ed value at

53、 the interpolation nodes. If desired, a dif- ferent fi tting accuracy may be specifi ed at each data point, as illus- trated by the varying error bars in Fig. 5. The evaluation accuracy specifi es the precision with which the fi tted RBF is then evaluated. Fig. 5 shows an RBF evaluated at regular in

54、tervals lying between the dashed evaluation accuracy bands either side of the actual func- tion. It is sensible to choose the evaluation accuracy to be numeri- cally smaller than the fi tting accuracy. The resulting dotted curve is an approximation to the smooth and continuous RBF. 5RBF center reduc

55、tion Conventionally, an RBF approximation uses all the input data points (the xis in Equation (2) as nodes of interpolation, and as centers of the RBF. However, the same input data may be able to be approximated to the desired accuracy using signifi cantly fewer RBF centersreduced subset of RBF cent

56、ers Figure 7: Illustration of center reduction. centers, as illustrated in Fig. 7. A greedy algorithm can therefore be used to iteratively fi t an RBF to within the desired fi tting accuracy. A simple greedy algorithm consists of the following steps: 1. Chooseasubsetfromtheinterpolationnodesxi andfi

57、 tanRBF only to these. 2. Evaluate the residual, i= fis(xi), at all nodes. 3. If max|i | fi tting accuracy then stop. 4. Else append new centers where iis large. 5. Re-fi t RBF and goto 2. If a different accuracy i is specifi ed at each point, then the condi- tion in step 3 may be replaced by |i| i.

58、 Center reduction is not essential when using the fast methods described in Section 4. For example, no reduction was used when fi tting to the LIDAR example of Fig. 8. However, reducing the number of RBF centers results in smaller memory requirements and faster evaluation times, without a loss in ac

59、curacy. Fig. 6 illustrates the fi tting process with center reduction. As more centers are added to the RBF, the zero-surface more closely approximates the entire set of data points. In this case, a laser scan of a Buddha fi gurine, consisting of 544,000 points, has been approximated by an RBF with 80,000 centers to a relative accuracy of 1.4104(achieved at all the data points). The greedy algorithm often re