A barcode shape descriptor for curve point cloud data (Part 1)

 

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

1. Introduction

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 para metrization .

Corresponding author.

E-mail addresses: collins@math.stanford.ed u (A . Collins) , afra@cs.stanford.ed u (A . Zomorodian) , gunnar@math.stanford.ed u (G . Carlsson) , guibas@cs.stanford.ed u (L.J . Guibas) .

1) Research supported,in part,by NSF under grant DMS 0101364.

2) Researc h supported,i n part,b y NSF/DARP A unde r gran t CARG O 013845 6 an d b y NS F unde r gran t IT R 0086013 .

1.1. Prior work

Shap e analysi s i s a well-studie d proble m i n man y area s o f compute r science,suc h a s vision,graphics,an d patter n recognition . Researcher s i n visio n firs t intro duce d th e ide a o f usin g compac t representation s o f shapes,o r shape descriptors ,fo r two-dimensiona l dat a o r images . The y derive d descriptor s usin g divers e methods , suc h a s topologica l invariants,momen t invariants , morphologica l method s fo r skeleton s o r media l axes , an d ellipti c Fourie r parameterization s [1–3] . More recently,the availability of large sets of digitized three-dimensional shapes has generated interest in 3D descriptors [4,5] ,with techniques such as shape distributions [6] and multi-resolution Reeb graphs [7] . Ideally,a shape descriptor should be invariant to rigid transformations and coordinatize the shape space in a meaningful way.

Th e ide a o f usin g point cloud data o r PCD a s a displa y primitiv e wa s introduce d earl y [8] ,bu t di d no t becom e popular until the recent emergence of massive datasets. PCDs are now utilized in rendering [9,10] ,shap e representation [11,12] ,and modeling [13,14] ,among

0097-8493/ $ -se e fron t matte r r 200 4 Elsevie r Ltd . Al l right s reserved . doi:10.1016/j.cag.2004.08.01 5

A. Collins et al. / Computers & Graphics 28 (2004) 881–894

other uses. Furthermore,PCDs are often the only possible primitive for exploring shapes in higher dimensions [15–17].

 

In a previous paper,we initiated a study of shape description via the application of persistent homology to tangential constructions [18] . W e propose d a robus t metho d tha t combine s th e differentiatin g powe r o f geometr y wit h th e classifyin g powe r o f topology . W e als o showe d th e viabilit y o f ou r metho d throug h explici t calculation s fo r one-an d two-dimensiona l mathematica l object s (curve s an d surfaces. ) I n thi s paper,w e shif t ou r focu s fro m theor y t o practice,illustratin g th e feasibilit y o f ou r metho d i n th e PC D domain . W e focu s o n curve s i n orde r t o explor e th e issue s tha t aris e i n th e applicatio n o f ou r techniques . W e mus t emphasize,however,tha t w e vie w curve s a s one-dimensiona l manifolds,an d insis t tha t al l ou r solution s exten d t o n -dimensiona l manifolds . Therefore,w e avoi d heuristic s base d o n abusin g characteristic s o f curv e PCD s an d searc h fo r genera l technique s tha t wil l b e suitabl e i n al l dimensions . W e briefl y discus s computin g ou r structure s fo r two-dimen siona l manifolds,o r surfaces,i n Sectio n 5.5 .

The rest of the paper is organized as follows. In Section 2 we review the theoretical background for our shape descriptor. We believe that an intuitive understanding of this material is sufficient for appreciating the results of this paper. As such,this section is brief in its treatment,and we refer the interested reader to our previous paper for a detailed description [18]. Section 3 contains the algorithms for computing barcodes for PCDs sampled from closed smooth curves. We also describe the computation of the metric over the space of barcodes. We apply our techniques to families of algebraic curves in Section 4 to demonstrate their effectiveness. In Section 5,we extend our system to general PCDs that may include non-manifold points, singularities,boundary points,or noise. We then illustrate the power of our methods through applications to shape classification and parametrization in Section 6.

2. Background

In this section,we review the theoretical background necessary for our work. To make the discussion accessible to the non-specialist,our exposition will have an intuitive flavor.