点云双边滤波算法

所需积分/C币:39 2019-06-12 11:08:38 2.58MB PDF
收藏 收藏
举报

将双边滤波算法应用于点云噪点滤除,可有效提高点云质量。高质量的输入数据对提高点云学习的人工智能训练效率与质量有显著的帮助。
JULIE DIGNE. CARLO DE FRANCHIS position v. Let No be the 1-ring neighborhood of vertex v(i.e the set of vertices sharing an edge with u. Then, the filtered position of v is +6 where ∑esN(o)(p-?)n(n,p-0))(n,p-0) pEN(v)Wd(p-vlwn(n,,p-v Where wa and wn are two decreasing functions In a nutshell, Equation 3) means that vertex v is shifted along its normal toward a weighted average of points that are both close to v in the ambient space and close to the plane passing through v with normal n,,. To better see the link with the bilateral filter in image processing, recall that a pixel is denoised with respect to neighboring pixels that look similar, and this similarity is computed in terms of distance between gray values. For meshes, the similarity is measured in terms of distance to the tangent plane. If u belongs to a sharp edge, then the only points close to the tangent plane at v are the points on the edge: these points will be the principal contributors to the denoising of v thus preserving the edge Interestingly, another version of the bilateral filter for meshes was introduced by Jones et al. [9 but its adaptation to point clouds is less simple since it takes into account local areas of the surface around each point, based, for example, on a local Voronoi diagram computation For a non oriented point cloud p, the bilateral filter can be extended as follows First a unit unoriented normal vector n, is estimated for each point p via its neighbors Nr(p) {q∈P-pl2<r} Then the point position is updated via p=p+ dp. np and p= 2gEMr(wa(g-pl)wn(I(np, q-p)(np, q- pr EA(p)U'd d q- pLan((np, q-pD) Where wd and wn are two decreasing functions In our implementation wa and wn are two centered Gaussian functions whose variance(oa and On resp. are chosen by the user. As can be seen on Figure 1, the weights on the distances will be balanced by the weights on the normal distances, thus favoring nearby points that are close to the tangent plane: the points that lie on the same side of the edge as p P (a) Initial point p(b) Distance weights (c)Regression plane(d)Normal distances(e) Normal distance with its neighborhood estination Iiq-p, np? weights Figure 1: Contributions of neighbors to the denoising of a point p in the bilateral framework. Weights are depicted in a color scale in 1(b)and le)(blue= small weights, red =large weights The normal np is estimated by computing the least squares regression plane of the set of neighbors Nr(p) and setting n to be the normal to this plane. Computing the least squares regression plane is 280 THE BILATERAL FILTER FOR POINT CLOUDS done trivially by computing the mean and covariance matrix of the neighbors, which yields a point on the plane(the mean) and the normal (the eigenvector corresponding to the least eigenvalues of the covariance matrix). Interestingly enough the orientation of the estimated normal np is irrelevant for the computation: inverting it will yield the same denoised point p 3 Implementation The bilateral filter for a given point p E P is suNned up in Algorithm 1. Two distances are taken into account: the distance to p and the distance to the regression plane at p. One can see that the denoised point p' is guaranteed to stay within a T-ball centered around p since it is a positively weighted average of the projections on the line(p, Ip) of points lying in a T-ball centered around p Algorithm 1: bilateral(p, r, od. 0n) Input: A point p E P, a radius r, two Gaussian weights od and on Output: a denoised point p N(p)← neighbors of p 2 Compute the unit normal to the regression plane n, from M(p) 30m2=0 5forg∈M(p)do 6789 dn←(q-p,n) exp- 2g2 ex on=sn+wd sum=slma,+ar 11pp+6n1 4 Parallelization The bilateral filter implementation uses an octree as a space partition structure to accelerate neigh borhood queries. An octree is a tree data structure in which each node(or cell has either no children or 8 children. The root of the octree encodes the shape loose bouding box and the octree recursively subdivides the bounding box into eight octants. We call processing depth the depth of the nodes that will be processed in parallel (the root having depth 0). This depth should be small enough to ensure that there is no thread confict, and large enough to ensure an efficient parallelization. We refer the reader to 3] for more details on this particular octree implementation The bilateral filter consisting in very local computations, the process parallelizes nicely provided some precautions are taken. An octree data structure is used to sort cells into sets, each set containing cells that can be processed independently by a different thread (see Algorithm 2), as shown on Figure 2. Thus, each thread applies the bilateral filter to the points included in a different cell. The exulting filtered points Inight not be located in the same cell and should be stored in the appropriate cell. The only precaution to take is to check that the denoised points obtained in two different threads will not be stored in the same cell. since that would cause conficts between the threads. since the filtered point p' of a point p lies inside a ball with radius r centered at p, it is enough to ensure that for two cells processed simultaneously, their dilations of radius r do not contain a common leaf cell 281 JULIE DIGNE. CARLO DE FRANCHIS The processing depth is therefore set as the minimum depth such that the size of the cell is above d=2. 1r and at least 1(Algorithm 2, line 1-2). This is easily done by computing octree.s2≈e level= max(octree.depth-Llog2 d The only remaining possible conflict happens when two threads simultaneously try to add a point in a branch not yet created. Although this case is rare, it is handled by preventing the simultaneous The complete parallelized algorithm is summed up n Algorithm, ee) creation of branches(critical section in method addPoint of class Octr Figure 2: Parallelization principle in 2D. Cells that can be processed simultaneously are depicted in the same color Algorithm 2 Parallelization of the bilateral filter Input: An unoriented input point cloud p sorted into an octree O with given depth, a radius r, two Gaussian weights on. od Output: A denoised point set stored in the octree O d←2.1r 2<max(1, smallest level at which cells have size larger than d) 3fori=0…·7do cells t cells of the octree at level l and with child index forC∈ cells do in parallel 6 forp∈Cdo p< bilateral(p, r, 0d, 0n C"<octree cell where p' is located Store p in the point list of C" corresponding to the next index We review next the parameters of the bilateral filter and how they should be tuned 5 Parameter Choice The parameters for the bilateral filter are the following . n the number of iterations r the radius for the neighborhood search o od the gaussian weight for the euclidean distance THE BILATERAL FILTER FOR POINT CLOUDS On the gaussian weight for the distance to the tangent plane The problem of setting the parameters can be simplified by considering that r and od are related the contribution of the neighbors which are at distance larger than Bod barely contribute to the denoising since their weight is a. most 0. To avoid unnecessary computations, these points should simply be ignored. Therefore one can set, both parameters by choosing a radius r and setting od =3 on represents the size of the offset around the tangent plane(Figure 3). Hence, it is clear that setting od and on amounts to setting the size of two neighborhoods: a radius r(defining the neighborhood depicted in red on Figure 3) and a normal radius rn(defining the neighborhood depicted in blue on O Figure 3: Schematic representation of the parameters of the bilateral filter In practice, a coarse heuristic for set ting r consists in considering the number of points Npoints the size of the bounding box and deduce the radius: r=lv20/Npoints(see[4 for a, derivation of this formula; on can be set equal to d. In our implementation, this heuristic is used if no parameters are provided 6 Code 6.1 Dependencies Thecodeprovidedisastand-aloneC++codeavailableathttps://doi.org/10.5201/ipol.2017 179. It uses the C++ standard template library extensively. The user can choose between the single-threaded inplementation and its parallel version. The single-threaded version does not rely on any external libraries. The parallelization is done through OpenMP3, a standard API for shared memory multiprocessing prograinning. The code was tested successfully on Ubuntu 16.04 and 14.04 with g++ 4.7. The compilation is performed through the CMake build system 6.2 Integration in a Larger Project The code is templated and the structures are kept as simple as possible in order for a better integration into different C++ projects. In particular, it should be easy to interface it with the CGaL library 5 and thus benefit from CGaL geometry kernels. Nevertheless, the goal here is to have a stand-alone code, avoiding the need to link against such a heavy library as CgaL. The next section presents the results for this implementation of the bilateral filter 3arcHitccturcRcvicwBoardOpcnmpApplicationProgramIntcrfaccVcrsion3.0,mAy2008,http://www.openmp org/mp-documents/spec30 pdf 283 JULIE DIGNE. CARLO DE FRANCHIS 7 Experiments For a better visualization, all point sets were first meshed using the scale space meshing algorithm with the implementation of [4]. The parameters for this reconstruction step were always: 4 iterations and the radius equal to half of r(the parameter for the bilateral filter) 7.1 Synthetic Examples We display the result of the bilateral filter on some synthetic shapes, a sphere(Figure 4) a cube (Figure 5)and a sharp edge(Figure 6). One can observe, that for the cube and the sharp edge setting a larger rn yields rounder edges. For open surfaces(as opposed to closed surfaces), this filter creates artifacts near the surface borders. This can be seen on Figure 6: the surface border near the edge appears to bend toward the concavity. Iterating the filter allows for a better preservation of sharp edges as can be seen on Figure 6 (a) Noisy sphere (b)r=0.05,7n=0.01(c)r=0.05,7n=0.04(d)r=0.05,mn=10 Figure 4: A noisy sphere(added noise with variance equal to 0.5% of the bounding box size) and its denoising with one iteration of the bilateral filter with various parameters (a)Noisy cube (b)?=004.Tn (c)r=0.04.ra=0.0 Figure 5: A noisy cube (added noise with variance equal to 0. 1% of the bounding box size)and its denoising with one iteration of the bilateral filter with various parameters 7.2 Real-world Examples The result of the filter is then demonstrated on some real data starting with the Stanford bunny (Figure 8)and the Brassempouy dataset(Figure 9). Computation times are given in Table 1 and 284 THE BILATERAL FILTER FOR POINT CLOUDS (a) Noisy sharp edge (b)r=0.04,rn=1 (c)r=0.04,rn=100 Figure 6: A noisy sharp edge (added noise with variance equal to 0.5%c of the bounding box size) and its denoising with 4 iterations of the bilateral filter with various parameters Figure 7: Iterations 1-4 of the bilateral filter with parameters r=0.04, rn=0.01. From left to right: noisy shape iteration 1,2, 3 and 4 show that for typical point sets of 300k points the filtering is fast with a low memory footprint Shape n Time Max Memory usage Brassempouy 312k050513s 12MB Brassempouy 312k 0.2 0.21 ls 35MB Cube 600k0.030.05213 22MB Fandisk 600k0.10.05111s 17MB Table 1: Typical filtering times and memory usage(Ubuntu 14.04-Intel Xeon CPU E5-2630 V3 @2. 4GHz x16) 8 Conclusion We presented a simple implementation of the bilateral filter adapted to point clouds. This filter allows to better preserve sharp edges during the denoising of a point set. It is a good trade-off between processing speed and denoising quality. Indeed, although more recent filters such as the non local means filter [1 produce much better results, they are also much slower The code for this implementation is available for download on the web page of the article https://doi.org/10.5201/ipol.2017.179 285 JULIE DIGNE, CARLO DE FRANCHIS C)Laplacian fil (d)Bilateral N-4,r-C.01, Tn-001 (e) Bilateral N-4,r-0.01 0.C05 gure 8: Com parison of the denoising of the bunny shape using the Laplacian filter and the bilateral filter with various arameters (a)No Bilateral filter Figure 9: Denoising of the Brassempouy dataset. Parameters: N=1, r=0.5, rI=0.5 Acknowledgments This work was partially funded by Agence Nationale de la recherche, ANR PAPS Project (ANR 14CE270003 286 THE BILATERAL FILTER FOR POINT CLOUDS Data Credits dataset is taken from the Farman Institute 3D Point Seto canning Repository. The Brassempouy The Stanford Bunny is taken fromfrom the Stanford 3D Se References [1 A. BUADES, B COLL, AND J-M. MOREL, A non-local algorithm for image denoising, in IEEE Conference on Computer Vision and Pattern Recognition(CVPR), 2005, pp. 60-65 2 M. DESBRUN, M. MEYER, P. SCHRODER, AND A II. BARR, Implicit fairing of irregular meshesusingdiffusionandcurvatureflou,inSigGraPii99,Usa,1999,pp.317-324.http //doi.acm.org/10.1145/311535.311576 3J. DIGNE, An Analysis and Implementation of a Parallel Ball Pivoting Algorithm, Image Pro- cessingOnLine,4(2014),pp.149-168.http://dx.doi.org/10.5201/ipol.2014.81 An implementation and parallelization of the scale space meshing algorithm, Image Pro cessingOnLine,5(2015),pp.282-295.http://dx.doi.org/10.5201/ipol.2015.102 5A. FABRI, CGAL- the computational geometry algorithm library, in Proceedings of the 10th Annual international meshing roundtable. California. U.S.A.. October 2001 6S. FLEISHMAN, I. DRORI, AND D. COHEN-OR, Bilateral mesh denoising, ACM Transactions onGraphics22(2003),pp.950-953.http://doi.acmorg/10.1145/882262.882368 7 M. GROSS AND A. HUBELI, Eigenmeshes, tech report, ETH Zurich. 2000 8 K. HILDEBRANDT AND K. POLTHIER, Anisolropic filtering of non-linear surface fealures. Com- puter Graphics Forum, 23(2004), pp. 391-400 9 T R. JONES, F. DURAND, AND M. DESBRUN, Non-iterative, feature-preserving mesh smooth ing, in SIGGRAPH 03: ACM SIGGRAPH 2003 Papers, USA, 2003, ACM, pp. 943-949 http://doi.acm.org/10.1145/1201775.882367 [10 C. LANGE AND K. POLTHIER, Anisotropic smoothing of point sets, Computer Aided Geometric Design22(2005),pp.680-692.http://dx.doi.org/10.1016/j.cagd2005.06.010 [11 G. TAUBIN, A signal processing approach to fair surface design, in SIGGRAPH 95, USA, 1995, ACM Press,pp.351358.htp://doi.acm.org/10.1145/218380.218473 [12 C. TOMASI AND R. MANDUCHI, Bilateral filtering for gray and color inages, in ICCV 98 Proceedings of the Sixth International Conference on Computer Vision, Washington, DC, USA 1998,IEEE.p.839. 13 B. VALLET AND B. LEVY, Spectral geometry processing with manifold harmonics, Computer GraphicsForuin,27(2008),pp.251-260.http://dx.doi.org/10.1111/j.1467-8659.2008 01122.X [14 L. P YAROSLAVSKY, Digital picture processing. An introduction., vol. 9 of Springer Series in Information Sciences, Springer-Verlag, Berlin- Heidelberg, 1985 5http://graphics.stanfordedu/data/3dscanrep/ 6http://www.ipol.im/pub/art/2011/dalmm_ps/ 287

...展开详情
试读 10P 点云双边滤波算法
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    点云双边滤波算法 39积分/C币 立即下载
    1/10
    点云双边滤波算法第1页
    点云双边滤波算法第2页
    点云双边滤波算法第3页

    试读已结束,剩余7页未读...

    39积分/C币 立即下载 >