In this paper we apply ideas of our earlier paper to provide novel methods for studying the qualitative properties of one-dimensional spaces in the plane [18] . Our method is based on studying the connected components of a complex constructed from a curve using its tangential information. Our method generates a compact shape descriptor called a barcode for a given PCD. We illustrate the feasibility of our methods by applying them for classification and parametrization of several families of shape PCDs with noise. We also provide an effective metric for comparing shape barcodes for classification and parametrization. Finally, we discuss the limitations of our methods and possible extensions. An important property of our methods is that they are applicable to any curve PCD without any need for specialized knowledge about the curve. The salient feature of our work is its reliance on theory, allowing us to extend our methods to shapes in higher dimensions,such as families of surfaces embedded in R3 where we utilize higher-dimensional barcodes.

Our work suggests a number of enticing research directions:

_� Implementing density estimation techniques to remove spurious components arising from noise,

_� A systematic study of the thickness problem of scanned curves,

_� Implementing the strategy for identifying boundary points,further strengthening our method,

_� Applying our methods to surface point cloud data.

Read more →

Predictive Point-Cloud Compression

Stefan Gumhold∗ Zachi Karni Martin Isenburg Hans-Peter Seidel

MPI f¨ur Informatik Saarbr¨ucken

Read more →

In this section,we discuss the application of our work to shape parametrization and classification. We have implemented a complete system for computing and visualizing filtered tangent complexes,and for computing,displaying,and comparing barcodes.

Read more →

In Section 3,we assumed that our PCD was sampled from a closed smooth curve in the plane. Our PCDs in the last section,however,violated our assumption as both families had added noise,and the family of cubics featured boundary points. Our method performed quite well,however,and naturally,we would like our method to generalize to other misbehaving PCDs. In this section, we characterize several such phenomena. For each problem,we describe possible solutions that are restrictions of methods that work in arbitrary dimensions. In

Read more →

Our first family of spaces are ellipses given by the equation ^x_a2 ² _þ^y_b² 2 _¼ 1: We compute PCDs for the five ellipses shown in Fig. 4 with semi-major axis a _¼ 0: 5 an d semi-mino r axe s b equa l t o 0.5,0.4,0.3,0.2,an d 0.1 , fro m to p t o bottom . T o generat e th e poin t sets,w e selec t 5 0 point s pe r uni t lengt h space d evenl y alon g th e x -an d y -axis,an d the n projec t thes e sample s ont o th e tru e curve . Therefore,th e point s ar e roughl y D x _¼ 0: 0 2 apart . W e the n ad d Gaussia n nois e t o eac h poin t wit h mea n 0 an d standar d deviatio n equa l t o hal f th e inter-poin t distanc e o r 0.01 . Fo r ou r metric,w e us e a scalin g facto r o _¼ 0: 1 : T o determin e a n appropriat e valu e fo r � fo r computin g th e Rip s complex,w e utiliz e ou r rule-of thumb : Eq . (2 ) fro m Sectio n 3.2 . Th e maximu m curvatur e fo r th e ellipse s show n i s kmax _¼ 50; so

0: 0 2 1 _þ 5 ² =2 0: 05 : Thi s valu e successfull y connect s point s wit h clos e basepoint s an d tangen t directions , whil e stil l keepin g antipoda l point s i n th e individua l fiber s separated .

Read more →

In this section,we present a complete pipeline for computing barcodes for a PCD . Throughout this section,we assume that our PCD P contains samples from a smooth closed curve X R ² : Before we comput e the barcode,we need to construct the tangent complex . Since we only have samples from the original space,we can only approximate the tangent complex . We begin by computing a new PCD , p ¹_ð P_Þ T_ð X _Þ ; that sample s the tangen t comple x fo r ou r shape . T o captur e it s homol ogy,w e firs t approximat e the underlyin g spac e an d the n comput e a simplicia l comple x tha t represent s it s connectivity . W e filte r thi s comple x b y estimatin g the curvatur e a t eac h poin t o f p ¹_ð P_Þ : We conclude this section by describing the barcode computation and giving an algorithm for computing the metric on the barcode space.

Read more →

Part2

2.1. Filtered simplicial complex

Le t S b e a se t o f points . A k-simplex i s a subse t o f S o f siz e k _þ 1 (19). A simplex may be realized geometrically as the convex hull of k _þ 1 affinely independent points in R^d ; dX k : A realizatio n give s u s th e familia r low-dimensiona l k -simplices : vertices , edges ,an d triangles . A simplicial complex i s a se t K o f simplice s o n S suc h tha t i f s ₂ K the n t s implies t ₂ K : A subcomplex o f K i s a simplicia l comple x L K : A filtration o f a comple x K i s a neste d sequenc e o f complexe s _;¼ K ⁰

K ¹ K^m _¼ K : W e cal l K a filtered complex an d sho w a smal l exampl e i n Fig. 1.

2.2. Persistent homology

Suppos e w e ar e give n a shap e X tha t i s embedde d i n R ³ : Homology i s a n algebrai c invarian t tha t count s th e topologica l attribute s o f thi s shap e i n term s o f it s Betti numbers bi [19]. Specifically , b 0 count s th e numbe r o f component s o f X . b 1 i s th e ran k o f a basi s fo r th e tunnels throug h X . Thes e tunnel s ma y b e viewe d a s formin g a grap h wit h cycle s [20] . b ₂ count s th e numbe r o f voids i n X ,o r space s tha t ar e enclose d b y th e shape . I n thi s

Read more →

Computers & Graphics 28 (2004) 881–894

a) Department of Mathematics, Stanford University, 450 Serra Mall, Bldg. 380, Stanford, CA 94305 2125, USA

b) Department of Computer Science, Stanford University, Stanford, CA 94305, USA

Abstract

I n thi s paper,w e presen t a complet e computationa l pipelin e fo r extractin g a compac t shap e descripto r fo r curv e poin t clou d dat a (PCD) . Ou r shap e descriptor,calle d a barcode ,i s base d o n a blen d o f technique s fro m differentia l geometr y an d algebrai c topology . W e als o provid e a metri c ove r th e spac e o f barcodes,enablin g fas t compariso n o f PCD s fo r shap e recognitio n an d clustering . T o demonstrat e th e feasibilit y o f ou r approach,w e implemen t ou r pipelin e an d provid e experimenta l evidenc e i n shap e classificatio n an d parametrization . r 200 4 Elsevie r Ltd . Al l right s reserved .

Keywords: Barcode ; Descriptor ; Persistence ; Tangent complex ; Point cloud data ; Curves

Read more →

Raw 3D digitized, or point cloud data, is memory hungry, static, and awkward. While it is possible to export raw data directly into CAD software, it can be very painful. Software such as Imageware’s Surfacer©, STRIM©, Pro/Scan Tools©, Alias Eval Viewer©, or similar programs are vital. The following is a description of how software is used for point cloud manipulation:

• Curves: Cross-sectional and 3D curves can easily be extracted from the point cloud data. The point cloud data is sectioned through any plane, and 3D curves are created through ridges or features. These curves are created quickly. The curves are only going to be used as a template during the model creation.
• Manipulation of Data: Often the final product is a variation of the part that was digitized. Therefore, data manipulation is required to reflect the desired changes. Scaling data is the most common manipulation.
• Extraction of Reference Curves and Base Geometry: After data orientation and manipulation, information is extracted, one piece at a time.
• Verification of Final Surfaces: Software is used for verification of the CAD model. Surfaces are exported several times during CAD model creation and compared, via a color variance plot, to the point cloud.
• Geometric Features: Points that make up a flat surface, cylinder, or sphere are isolated, and a best-fit surface is created.
• Data Orientation: Orienting data is the first step. For injection molded parts, the data is often oriented relative to the parting plane of the tool. If symmetrical the point cloud is oriented such that the mirror plane is defined. Next, data is exported to CAD software.

7. CONCLUSIONS

In this paper a description of all the processes to convert a measured point cloud into a polygonal surface and then visualize it with a computer has been presented. An almost complete overview of the modeling/visualization solutions has been reported, including also spline-based packages, but many other solutions are probably implemented in various labs and we are not informed of them. Even if the concepts and algorithms of the modeling software are quite straightforward, the performance of the software is strictly related to the implementation and to the hardware. Moreover all the existing software for modeling and visualize 3D objects are specific for certain data sets. Commercial ‘reverse engineering’ packages do not produce correct meshes without dense point clouds. On the other hand visualization tools can do nothing to improve a badly modeled scene and the rendering can get worse the results if antialiasing or level of detail control are not available.

Read more →