点云特征提取详细实用经典的讲述过程及方法_点云_湘西

<html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta charset="utf-8"> <meta name="generator" content="pdf2htmlEX"> <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> <link rel="stylesheet" href="https://static.pudn.com/base/css/base.min.css"> <link rel="stylesheet" href="https://static.pudn.com/base/css/fancy.min.css"> <link rel="stylesheet" href="https://static.pudn.com/prod/directory_preview_static/62d68dea864d5c73accb8912/raw.css"> <script src="https://static.pudn.com/base/js/compatibility.min.js"></script> <script src="https://static.pudn.com/base/js/pdf2htmlEX.min.js"></script> <script> try{ pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({}); }catch(e){} </script> <title></title> </head> <body> <div id="sidebar" style="display: none"> <div id="outline"> </div> </div> <div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/62d68dea864d5c73accb8912/bg1.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0">submitted for publication</div><div class="t m1 x2 h3 y1 ff1 fs1 fc0 sc0 ls0 ws0">1</div><div class="t m1 x3 h4 y2 ff2 fs2 fc0 sc0 ls0 ws0">Feature Extraction from Point Clouds</div><div class="t m1 x4 h5 y3 ff1 fs3 fc0 sc0 ls0 ws0">Stefan Gumhold</div><div class="t m2 x5 h6 y4 ff3 fs4 fc0 sc0 ls0 ws0"></div><div class="t m1 x6 h5 y3 ff1 fs3 fc0 sc0 ls0 ws0">Xinlong Wang</div><div class="t m2 x7 h6 y4 ff3 fs4 fc0 sc0 ls0 ws0">y</div><div class="t m1 x8 h5 y5 ff1 fs3 fc0 sc0 ls0 ws0">Scientiﬁc Computing and Imaging Institute</div><div class="t m1 x9 h5 y6 ff1 fs3 fc0 sc0 ls0 ws0">University of Salt Lake City, Utah</div><div class="t m1 xa h5 y7 ff1 fs3 fc0 sc0 ls0 ws0">Rob MacLeod</div><div class="t m2 xb h6 y4 ff3 fs4 fc0 sc0 ls0 ws0">z</div><div class="t m1 x1 h3 y8 ff1 fs1 fc0 sc0 ls0 ws0">Figure 1: a) input point cloud. b) the neighbor graph. c) point classiﬁcation. d) crease pattern forming. e) puriﬁed crease pattern. f) spline</div><div class="t m1 x1 h3 y9 ff1 fs1 fc0 sc0 ls0 ws0">representation of crease pattern</div><div class="t m1 x1 h7 ya ff2 fs5 fc0 sc0 ls0 ws0">Abstract</div><div class="t m1 x1 h3 yb ff1 fs1 fc0 sc0 ls0 ws0">This paper describes a new method to extract feature lines directly</div><div class="t m1 x1 h3 yc ff1 fs1 fc0 sc0 ls0 ws0">from a surface point cloud. No surface reconstruction is needed</div><div class="t m1 x1 h3 yd ff1 fs1 fc0 sc0 ls0 ws0">in advance, only the inexpensive computation of a neighbor graph</div><div class="t m1 x1 h3 ye ff1 fs1 fc0 sc0 ls0 ws0">connecting nearby points.</div><div class="t m1 xc h3 yf ff1 fs1 fc0 sc0 ls0 ws0">The feature extraction is performed in two stages. The ﬁrst stage</div><div class="t m1 x1 h3 y10 ff1 fs1 fc0 sc0 ls0 ws0">constists of assigning a penalty weight to each point that indicates</div><div class="t m1 x1 h3 y11 ff1 fs1 fc0 sc0 ls0 ws0">the unlikelihood that the point is part of a feature and assigning</div><div class="t m1 x1 h3 y12 ff1 fs1 fc0 sc0 ls0 ws0">these penalty weights to the edges of a neighbor graph. Extracting</div><div class="t m1 x1 h3 y13 ff1 fs1 fc0 sc0 ls0 ws0">a subgraph of the neighbor graph that minimizes the edge penalty</div><div class="t m1 x1 h3 y14 ff1 fs1 fc0 sc0 ls0 ws0">weights then produces a set of feature patterns. The second stage</div><div class="t m1 x1 h3 y15 ff1 fs1 fc0 sc0 ls0 ws0">is especially useful for noisy data. It recovers feature lines and</div><div class="t m1 x1 h3 y16 ff1 fs1 fc0 sc0 ls0 ws0">junctions by ﬁtting wedges to the crease lines and corners to the</div><div class="t m1 x1 h3 y17 ff1 fs1 fc0 sc0 ls0 ws0">junctions.</div><div class="t m1 xc h3 y18 ff1 fs1 fc0 sc0 ls0 ws0">As the method works on the local neighbor graph only, it is fast</div><div class="t m1 x1 h3 y19 ff1 fs1 fc0 sc0 ls0 ws0">and automatically adapts to the sampling resolution. This makes</div><div class="t m1 x1 h3 y1a ff1 fs1 fc0 sc0 ls0 ws0">the approach ideal as a preprocessing step in mesh generation.</div><div class="t m1 x1 h8 y1b ff4 fs1 fc0 sc0 ls0 ws0">CR Categories: I.4.6 Segmentation [Edge and feature</div><div class="t m1 x1 h3 y1c ff1 fs1 fc0 sc0 ls0 ws0">detection]—;</div><div class="t m1 x1 h8 y1d ff4 fs1 fc0 sc0 ls0 ws0">Keywords: feature detection, scattered data</div><div class="t m1 x1 h7 y1e ff2 fs5 fc0 sc0 ls0 ws0">1 Introduction</div><div class="t m1 x1 h3 y1f ff1 fs1 fc0 sc0 ls0 ws0">In this paper we consider the feature detection and reconstruction</div><div class="t m1 x1 h3 y20 ff1 fs1 fc0 sc0 ls0 ws0">problem for the case of the input surface being described by a point</div><div class="t m1 x1 h3 y21 ff1 fs1 fc0 sc0 ls0 ws0">cloud. Figure 2 illustrates for the surface of the well known Stan-</div><div class="t m1 x1 h3 y22 ff1 fs1 fc0 sc0 ls0 ws0">ford bunny the different types of feature elements that we want to</div><div class="t m1 x1 h3 y23 ff1 fs1 fc0 sc0 ls0 ws0">extract. The crease pattern, shown in dark blue, consists of crease</div><div class="t m1 x1 h3 y24 ff1 fs1 fc0 sc0 ls0 ws0">lines that either terminate in junctions or singleton ends or they</div><div class="t m1 x1 h3 y25 ff1 fs1 fc0 sc0 ls0 ws0">close to form a loop. The border pattern consists only of border</div><div class="t m1 x1 h3 y26 ff1 fs1 fc0 sc0 ls0 ws0">loops. Input points that lay on a crease are called crease points,</div><div class="t m1 x1 h3 y27 ff1 fs1 fc0 sc0 ls0 ws0">points on the border loops are border points. At a junction the cor-</div><div class="t m1 x1 h3 y28 ff1 fs1 fc0 sc0 ls0 ws0">responding data point is called a corner or junction point and at</div><div class="t m1 x1 h3 y29 ff1 fs1 fc0 sc0 ls0 ws0">singleton ends we ﬁnd end points. The feature extraction algorithm</div><div class="t m2 xc h6 y2a ff5 fs4 fc0 sc0 ls0 ws0"></div><div class="t m1 xd h9 y2b ff1 fs6 fc0 sc0 ls0 ws0">stefan@gumhold.com</div><div class="t m2 xc h6 y2c ff5 fs4 fc0 sc0 ls0 ws0">y</div><div class="t m1 xd h9 y2d ff1 fs6 fc0 sc0 ls0 ws0">wangxl@cs.utah.edu</div><div class="t m2 xc h6 y2e ff5 fs4 fc0 sc0 ls0 ws0">z</div><div class="t m1 xd h9 y2f ff1 fs6 fc0 sc0 ls0 ws0">macleod@cvrti.utah.edu</div><div class="t m1 xe h3 y30 ff1 fs1 fc0 sc0 ls0 ws0">Figure 2: different elements in the crease and border patterns</div><div class="t m1 xf h3 y31 ff1 fs1 fc0 sc0 ls0 ws0">that we describe here is fully automated and no seed or junction</div><div class="t m1 xf h3 y32 ff1 fs1 fc0 sc0 ls0 ws0">points need to be marked by the user.</div><div class="t m1 x10 h3 y33 ff1 fs1 fc0 sc0 ls0 ws0">Figure 1 illustrates our feature extraction pipeline. The input</div><div class="t m1 xf h3 y34 ff1 fs1 fc0 sc0 ls0 ws0">is a point cloud a); in this case the underlying surface is a model</div><div class="t m1 xf h3 y35 ff1 fs1 fc0 sc0 ls0 ws0">of the human torso. In the analysis stage we construct a neighbor</div><div class="t m1 xf h3 y36 ff1 fs1 fc0 sc0 ls0 ws0">graph b) on the point cloud that reﬂects proximity. The classiﬁca-</div><div class="t m1 xf h3 y37 ff1 fs1 fc0 sc0 ls0 ws0">tion stage that follows ﬁts ellipsoids c) to the neighborhoods of the</div><div class="t m1 xf h3 y38 ff1 fs1 fc0 sc0 ls0 ws0">input points, approximates the surface curvature and the maximum</div><div class="t m1 xf h3 y39 ff1 fs1 fc0 sc0 ls0 ws0">open angle; the latter is used to detect border points. From these</div><div class="t m1 xf h3 y3a ff1 fs1 fc0 sc0 ls0 ws0">vertex properties we deﬁne crease and border penalty weights that</div><div class="t m1 xf h3 y3b ff1 fs1 fc0 sc0 ls0 ws0">measure the unlikelihood that a speciﬁc point is on a crease or bor-</div><div class="t m1 xf h3 y3c ff1 fs1 fc0 sc0 ls0 ws0">der line, respectively. From the penalty weights at the vertices we</div><div class="t m1 xf h3 y3d ff1 fs1 fc0 sc0 ls0 ws0">compute penalty weights at the edges of the neighbor graph. The</div><div class="t m1 xf h3 y3e ff1 fs1 fc0 sc0 ls0 ws0">feature line linkage stage ﬁnds spanning patterns in the neighbor</div><div class="t m1 xf h3 y3f ff1 fs1 fc0 sc0 ls0 ws0">graph that minimize the crease or border penalty weights, respec-</div><div class="t m1 xf h3 y40 ff1 fs1 fc0 sc0 ls0 ws0">tively. A minimum crease spanning pattern is shown in d). The</div><div class="t m1 xf h3 y41 ff1 fs1 fc0 sc0 ls0 ws0">minimum spanning pattern is similar to a minimum spanning tree</div><div class="t m1 xf h3 y42 ff1 fs1 fc0 sc0 ls0 ws0">but allows for signiﬁcantly long cycles. A pruning algorithm cuts</div><div class="t m1 xf h3 y43 ff1 fs1 fc0 sc0 ls0 ws0">off short branches e). For noisy data the resulting crease lines are</div><div class="t m1 xf h3 y44 ff1 fs1 fc0 sc0 ls0 ws0">jittered because no input points lay directly on the actual crease</div><div class="t m1 xf h3 y45 ff1 fs1 fc0 sc0 ls0 ws0">line, in which case we apply a crease line and junction recovery al-</div><div class="t m1 xf h3 y46 ff1 fs1 fc0 sc0 ls0 ws0">gorithm. This algorithm ﬁts wedges, a simple crease representation</div><div class="t m1 xf h3 y47 ff1 fs1 fc0 sc0 ls0 ws0">consisting of two half planes meeting at a line, to the crease neigh-</div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div> </body> </html>

<div id="pf2" class="pf w0 h0" data-page-no="2"><div class="pc pc2 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/62d68dea864d5c73accb8912/bg2.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0">submitted for publication</div><div class="t m1 x2 h3 y1 ff1 fs1 fc0 sc0 ls0 ws0">2</div><div class="t m1 x1 h3 y48 ff1 fs1 fc0 sc0 ls0 ws0">borhood along the crease lines. We next ﬁt the neighborhood of</div><div class="t m1 x1 h3 y49 ff1 fs1 fc0 sc0 ls0 ws0">junction points to corners that consist of a corner point and several</div><div class="t m1 x1 h3 y4a ff1 fs1 fc0 sc0 ls0 ws0">incident planes. The number of planes incident to a corner equals</div><div class="t m1 x1 h3 y4b ff1 fs1 fc0 sc0 ls0 ws0">the degree of the crease junction. The jittered crease points are</div><div class="t m1 x1 h3 y4c ff1 fs1 fc0 sc0 ls0 ws0">projected onto the wedges and corners. In a ﬁnal step the feature</div><div class="t m1 x1 h3 y4d ff1 fs1 fc0 sc0 ls0 ws0">lines and loops are converted to a spline representation f) by a least</div><div class="t m1 x1 h3 y4e ff1 fs1 fc0 sc0 ls0 ws0">squares ﬁtting approach.</div><div class="t m1 x1 ha y4f ff2 fs3 fc0 sc0 ls0 ws0">1.1 Related Work</div><div class="t m1 x1 h3 y50 ff1 fs1 fc0 sc0 ls0 ws0">The feature extraction problem is closely related to surface recon-</div><div class="t m1 x1 h3 y51 ff1 fs1 fc0 sc0 ls0 ws0">struction, which has important applications in laser range scanning,</div><div class="t m1 x1 h3 y52 ff1 fs1 fc0 sc0 ls0 ws0">scientiﬁc computing, computer vision, medical imaging, and com-</div><div class="t m1 x1 h3 y53 ff1 fs1 fc0 sc0 ls0 ws0">puter assisted surgical planning. Our algorithm addresses some of</div><div class="t m1 x1 h3 y54 ff1 fs1 fc0 sc0 ls0 ws0">the problems that arise in surface reconstruction of datasets that</div><div class="t m1 x1 h3 y55 ff1 fs1 fc0 sc0 ls0 ws0">contain creases and corners [16, 8, 15, 6, 3]. For these approaches</div><div class="t m1 x1 h3 y56 ff1 fs1 fc0 sc0 ls0 ws0">it is very helpful to extract the feature lines and junctions before-</div><div class="t m1 x1 h3 y57 ff1 fs1 fc0 sc0 ls0 ws0">hand.</div><div class="t m1 xc h3 y58 ff1 fs1 fc0 sc0 ls0 ws0">Most of the reconstruction algorithms that can accomodate</div><div class="t m1 x1 h3 y59 ff1 fs1 fc0 sc0 ls0 ws0">creases and corners do so either implicitly or in a post process-</div><div class="t m1 x1 h3 y5a ff1 fs1 fc0 sc0 ls0 ws0">ing step. The graph-based surface reconstruction of Mencl and</div><div class="t m1 x1 h3 y5b ff1 fs1 fc0 sc0 ls1 ws0">M¨uller [12] handles sharp edges by maximizing for each point the</div><div class="t m1 x1 h3 y5c ff1 fs1 fc0 sc0 ls0 ws0">sum of dihedral angles of the incident faces. The optimization is</div><div class="t m1 x1 h3 y5d ff1 fs1 fc0 sc0 ls0 ws0">performed only locally and depends on the order in which the in-</div><div class="t m1 x1 h3 y5e ff1 fs1 fc0 sc0 ls0 ws0">put points are processed. Especially in degenerate cases this ap-</div><div class="t m1 x1 h3 y5f ff1 fs1 fc0 sc0 ls0 ws0">proach can produce ”cripsy” crease lines i.e., lines that are bro-</div><div class="t m1 x1 h3 y60 ff1 fs1 fc0 sc0 ls0 ws0">ken by notches. A problematic constellation of points that often</div><div class="t m1 x1 h3 y61 ff1 fs1 fc0 sc0 ls0 ws0">arises at sharp edges occurs when two points on the crease form</div><div class="t m1 x1 h3 y62 ff1 fs1 fc0 sc0 ls0 ws0">an equilateral tetrahedron with two points on different sides of the</div><div class="t m1 x1 h3 y63 ff1 fs1 fc0 sc0 ls0 ws0">crease. There is no guarantee that the crease edge is preferred over</div><div class="t m1 x1 h3 y64 ff1 fs1 fc0 sc0 ls0 ws0">the edge connecting the two points on the two sides. The tetrahe-</div><div class="t m1 x1 h3 y65 ff1 fs1 fc0 sc0 ls0 ws0">dron described by the problematic points need not be exactly equi-</div><div class="t m1 x1 h3 y66 ff1 fs1 fc0 sc0 ls0 ws0">lateral as the locations of the input points could accidentally favor</div><div class="t m1 x1 h3 y67 ff1 fs1 fc0 sc0 ls0 ws0">constellations that cut the crease. Adamy et al. [2] described cor-</div><div class="t m1 x1 h3 y68 ff1 fs1 fc0 sc0 ls0 ws0">ner and crease reconstruction as a post processing step of ﬁnding</div><div class="t m1 x1 h3 y69 ff1 fs1 fc0 sc0 ls0 ws0">a triangulation describing a valid manifold surface. The previously</div><div class="t m1 x1 h3 y6a ff1 fs1 fc0 sc0 ls0 ws0">described case is again a problem. Both constellations for trian-</div><div class="t m1 x1 h3 y6b ff1 fs1 fc0 sc0 ls0 ws0">gulating the four points on a near equilateral tetrahedron are per-</div><div class="t m1 x1 h3 y6c ff1 fs1 fc0 sc0 ls0 ws0">fectly manifold and there is no reason why the crease edge should</div><div class="t m1 x1 h3 y6d ff1 fs1 fc0 sc0 ls0 ws0">be preferred over the crease cutting edge. The power crust algo-</div><div class="t m1 x1 h3 y6e ff1 fs1 fc0 sc0 ls0 ws0">rithm of Amenta et al. [13] treats sharp edges and corners also in a</div><div class="t m1 x1 h3 y6f ff1 fs1 fc0 sc0 ls0 ws0">post processing step. However, they reconstructed the features by</div><div class="t m1 x1 h3 y70 ff1 fs1 fc0 sc0 ls0 ws0">extending the surfaces adjacent to the features and calculating the</div><div class="t m1 x1 h3 y71 ff1 fs1 fc0 sc0 ls0 ws0">intersections. This idea is quite similar to our approach but their</div><div class="t m1 x1 h3 y72 ff1 fs1 fc0 sc0 ls0 ws0">simple approach of surface extension does not tolerate noisy data.</div><div class="t m1 xc h3 y73 ff1 fs1 fc0 sc0 ls0 ws0">In the computer vision literature there exist quite old approaches</div><div class="t m1 x1 h3 y74 ff1 fs1 fc0 sc0 ls0 ws0">for depth images that can handle features correctly and extract the</div><div class="t m1 x1 h3 y75 ff1 fs1 fc0 sc0 ls0 ws0">feature lines. The weak constraint optimization technique by Blake</div><div class="t m1 x1 h3 y76 ff1 fs1 fc0 sc0 ls0 ws0">and Zisserman [7] used a non linear ﬁtting approach. The global</div><div class="t m1 x1 h3 y77 ff1 fs1 fc0 sc0 ls0 ws0">energy functional, which was minimized, contained a term that pe-</div><div class="t m1 x1 h3 y78 ff1 fs1 fc0 sc0 ls0 ws0">nalizes the generation of a crease line in order to avoid permanent</div><div class="t m1 x1 h3 y79 ff1 fs1 fc0 sc0 ls0 ws0">creation of creases. This approach can also reconstruct the crease</div><div class="t m1 x1 h3 y7a ff1 fs1 fc0 sc0 ls0 ws0">lines and junctions. Sinha and Schunk [14] ﬁt spline patches to</div><div class="t m1 x1 h3 y7b ff1 fs1 fc0 sc0 ls0 ws0">depth images and adjusted the spline parameters such that the spline</div><div class="t m1 x1 h3 y7c ff1 fs1 fc0 sc0 ls0 ws0">patches could bend sharply around creases.</div><div class="t m1 xc h3 y7d ff1 fs1 fc0 sc0 ls0 ws0">Guy and Medioni [10] described a robust algorithm to ex-</div><div class="t m1 x1 h3 y7e ff1 fs1 fc0 sc0 ls0 ws0">tract surfaces, feature lines and feature junctions from noisy point</div><div class="t m1 x1 h3 y7f ff1 fs1 fc0 sc0 ls0 ws0">clouds. They discretized the space around the point cloud into a vol-</div><div class="t m1 x1 h3 y80 ff1 fs1 fc0 sc0 ls0 ws0">ume grid and accumulated for each cell surface votes from the data</div><div class="t m1 x1 h3 y81 ff1 fs1 fc0 sc0 ls0 ws0">points. From the accumulated votes they deﬁned a saliency func-</div><div class="t m1 x1 h3 y82 ff1 fs1 fc0 sc0 ls0 ws0">tion for junctions and a combined scalar and vector valued saliency</div><div class="t m1 x1 h3 y83 ff1 fs1 fc0 sc0 ls0 ws0">function for the crease lines. Junctions are simply global maxima</div><div class="t m1 x1 h3 y84 ff1 fs1 fc0 sc0 ls0 ws0">of the saliency functions and crease lines are extracted with a mod-</div><div class="t m1 x1 h3 y85 ff1 fs1 fc0 sc0 ls0 ws0">iﬁed marching cubes algorithm. One of our goals was to avoid the</div><div class="t m1 x1 h3 y86 ff1 fs1 fc0 sc0 ls0 ws0">discretization into a volume grid in order to allow for efﬁcient han-</div><div class="t m1 x1 h3 y87 ff1 fs1 fc0 sc0 ls0 ws0">dling of non uniformly sampled point clouds.</div><div class="t m1 xf ha y88 ff2 fs3 fc0 sc0 ls0 ws0">1.2 Paper Overview</div><div class="t m1 xf h3 y89 ff1 fs1 fc0 sc0 ls0 ws0">The paper is partitioned into three different sections corresponding</div><div class="t m1 xf h3 y8a ff1 fs1 fc0 sc0 ls0 ws0">to the stages of the feature extraction pipeline. Section 2 describes</div><div class="t m1 xf h3 y8b ff1 fs1 fc0 sc0 ls0 ws0">the analysis stage, where the neighbor graph is constructed. In sec-</div><div class="t m1 xf h3 y8c ff1 fs1 fc0 sc0 ls0 ws0">tion 3 we explain the feature detection stage in detail. The recovery</div><div class="t m1 xf h3 y8d ff1 fs1 fc0 sc0 ls0 ws0">of crease lines and junctions is the topic of section 4. Applications</div><div class="t m1 xf h3 y8e ff1 fs1 fc0 sc0 ls0 ws0">and results are presented in section 5 before we end with a brief</div><div class="t m1 xf h3 y8f ff1 fs1 fc0 sc0 ls0 ws0">discussion in section 6.</div><div class="t m1 xf h7 y90 ff2 fs5 fc0 sc0 ls0 ws0">2 Analysis</div><div class="t m1 xf h3 y91 ff1 fs1 fc0 sc0 ls0 ws0">The analysis phase of this approach consists of computing a neigh-</div><div class="t m1 xf h3 y92 ff1 fs1 fc0 sc0 ls0 ws0">bor graph on the input points and estimating for each point the sam-</div><div class="t m1 xf h3 y93 ff1 fs1 fc0 sc0 ls0 ws0">pling density. The neighbor graph connects points that are probably</div><div class="t m1 xf h3 y94 ff1 fs1 fc0 sc0 ls0 ws0">close on the underlying surface. On the one hand, the neighbor</div><div class="t m1 xf h3 y95 ff1 fs1 fc0 sc0 ls0 ws0">graph will be used to ﬁnd the neighborhood of each data point,</div><div class="t m1 xf h3 y96 ff1 fs1 fc0 sc0 ls0 ws0">which allows for fast local computations. On the other hand it</div><div class="t m1 xf h3 y97 ff1 fs1 fc0 sc0 ls0 ws0">serves as the domain for detecting the feature line patterns.</div><div class="t m1 xf ha y98 ff2 fs3 fc0 sc0 ls0 ws0">2.1 Neighbor Graph</div><div class="t m1 x11 h3 y99 ff1 fs1 fc0 sc0 ls0 ws0">a) b)</div><div class="t m1 x11 h3 y9a ff1 fs1 fc0 sc0 ls0 ws0">c) d)</div><div class="t m1 xf h3 y9b ff1 fs1 fc0 sc0 ls0 ws0">Figure 3: a) Delaunay ﬁltered graph misses important edges for</div><div class="t m1 xf h3 y9c ff1 fs1 fc0 sc0 ls0 ws0">feature line detection, b) Riemannian graph with</div><div class="t m2 x12 h6 y9d ff7 fs4 fc0 sc0 ls0 ws0">k</div><div class="t m2 x13 h6 y9d ff8 fs4 fc0 sc0 ls3 ws0">=16</div><div class="t m1 x14 h3 y9d ff1 fs1 fc0 sc0 ls0 ws0">contains</div><div class="t m1 xf h3 y9e ff1 fs1 fc0 sc0 ls0 ws0">these edges, c) triangles recovered by Delaunay ﬁltering, d) prob-</div><div class="t m1 xf h3 y9f ff1 fs1 fc0 sc0 ls0 ws0">lems at creases</div><div class="t m1 x10 h3 ya0 ff1 fs1 fc0 sc0 ls0 ws0">We follow two approaches to compute the neighbor graph. If we</div><div class="t m1 xf h3 ya1 ff1 fs1 fc0 sc0 ls0 ws0">know that the noise of the dataset is low as, for example, in laser</div><div class="t m1 xf h3 ya2 ff1 fs1 fc0 sc0 ls0 ws0">range scan data, we extract a suitable subset of the Delaunay com-</div><div class="t m1 xf h3 ya3 ff1 fs1 fc0 sc0 ls0 ws0">plex, which is deﬁned by the point cloud. This method fails under</div><div class="t m1 xf h3 ya4 ff1 fs1 fc0 sc0 ls0 ws0">conditions of very noisy data, in which case some important con-</div><div class="t m1 xf h3 ya5 ff1 fs1 fc0 sc0 ls0 ws0">nections between close points are missing that are need for feature</div><div class="t m1 xf h3 ya6 ff1 fs1 fc0 sc0 ls0 ws0">line detection. Then we use the Riemannian Graph.</div><div class="t m1 xf hb ya7 ff2 fs1 fc0 sc0 ls0 ws0">Delaunay Filtering First we computed the Delaunay tetrahe-</div><div class="t m1 xf h3 ya8 ff1 fs1 fc0 sc0 ls0 ws0">dralization of the input point set with the public domain software</div><div class="t m1 xf h3 ya9 ff1 fs1 fc0 sc0 ls0 ws0">package Qhull [5]. Then we followed the approach of Adamy et</div><div class="t m1 xf h3 yaa ff1 fs1 fc0 sc0 ls0 ws0">al. [2] and ﬁrst ﬁltered out all triangles of the Gabriel complex.</div><div class="t m1 xf h3 yab ff1 fs1 fc0 sc0 ls0 ws0">These are the triangles, which do not contain any fourth point</div><div class="t m1 xf h3 yac ff1 fs1 fc0 sc0 ls0 ws0">within their minimum circumsphere. Triangles not in the Gabriel</div><div class="t m1 xf h3 yad ff1 fs1 fc0 sc0 ls0 ws0">complex are most probably not part of the surface because a fourth</div><div class="t m1 xf h3 yae ff1 fs1 fc0 sc0 ls0 ws0">data point is close to these triangles and the surface more likely</div><div class="t m1 xf h3 yaf ff1 fs1 fc0 sc0 ls0 ws0">passes through this point. The Gabriel triangles can be found by</div><div class="t m1 xf h3 yb0 ff1 fs1 fc0 sc0 ls0 ws0">investigating the incident tetrahedra. If there is only one incident</div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div>

点云特征提取 详细 实用 经典的讲述过程及方法

点云特征提取详细实用经典的讲述过程及方法