Persistence barcodes for shapes

ABSTRACT

In this paper, we initiate a study of shape description and classification via the application of persistent homology to two tangential constructions on geometric objects. Our techniques combine the differentiating power of geometry with the classifying power of topology. The homology of our first construction, the tangent complex, can distinguish between topologically identical shapes with different "sharp" features, such as corners. To capture "soft" curvature-dependent features, we define a second complex, the filtered tangent complex, obtained by parametrizing a family of increasing subcomplexes of the tangent complex. Applying persistent homology, we obtain a shape descriptor, called a barcode, that is a finite union of intervals. We define a metric over the space of such intervals, arriving at a continuous invariant that reflects the geometric properties of shapes. We illustrate the power of our methods through a number of detailed studies of parametrized families of mathematical shapes.

REFERENCES

• 1: {BG92} Berger M., Gastiaux B.: Géomtrié différentitelle: variétés, courbes et surfaces. Mathématiques Presses Universitaires de France, Paris, France, 1992.
• 2: {Boo91} Bookstein F.: Morphometric Tools for Landmark Data. Cambridge Univ. Press, Cambridge, UK, 1991.
• 3: {CdS03} Carlsson G., De Silva V.: A geometric framework for sparse matrix problems. Advances in Applied Mathematics (2003). (To appear).
• 4: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 5: {CZCG04} Collins A., Zomorodian A., Carlsson G., Guibas L.: A barcode shape descriptor for curve point cloud data, 2004. To appear in Proc. Symposium on Point-Based Graphics.
• 6: {DK90} Donaldson S. K., Kronheimer P. B.: The Geometry of Four-Manifolds. The Clarendon Press, New York, NY, 1990.
• 7: {ELZ02} Edelsbrunner H., Letscher D., Zomorodian A.: Topological persistence and simplification. Discrete Comput. Geom. 28 (2002), 511--533.
• 8: Ting-Jun Fan, Describing and recognizing 3-D objects using surface properties, Springer-Verlag New York, Inc., New York, NY, 1989
• 9: {Fed69} Federer H.: Geometric Measure Theory. vol. 153 of Die Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, New York, NY, 1969.
• 10: Robert B. Fisher, From surfaces to objects: computer vision and three dimensional scene analysis, John Wiley & Sons, Inc., New York, NY, 1989
• 11: {GH81} Greenberg M. J., Harper J. R.: Algebraic Topology: A First Course, vol. 58 of Mathematics Lecture Note Series. Benjamin/Cummings Publishing Co., Reading, MA, 1981.
• 12: H. N. Gabow , R. E. Tarjan, Faster scaling algorithms for network problems, SIAM Journal on Computing, v.18 n.5, p.1013-1036, Oct. 1989 [doi>10.1137/0218069]
• 13: {Hat01} Hatcher A.: Algebraic Topology. Cambridge Univ. Press, Cambridge, UK, 2001.
• 14: {KBCL99} Kendall D., Barden D., Carne T., Le H.: Shape and Shape Theory. John Wiley and Sons, Inc., New York, NY, 1999.
• 15: {Kuh55} Kuhn H. W.: The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2 (1955), 83--97.
• 16: {LPM01} Lee A. B., Pedersen K. S., Mumford D.: The non-linear statistics of high contrast patches in natural images. Tech. rep., Brown University, 2001. Available online.
• 17: {Mil63} Milnor J.: Morse Theory, vol. 51 of Annals of Mathematical Studies. Princeton Univ. Press, Princeton, NJ, 1963.
• 18: {MS74} Milnor J., Stasheff J. D.: Characteristic Classes, vol. 76 of Annals of Mathematical Studies. Princeton Univ. Press, Princeton, NJ, 1974.
• 19: {ZC04} Zomorodian A., Carlsson G.: Computing topological persistence, 2004. To appear in Proc. 20th Ann. ACM Sympos. Comput. Geom.
• 20: Song Chun Zhu , Alan L. Yuille, FORMS: a flexible object recognition and modeling system, International Journal of Computer Vision, v.20 n.3, p.187-212, Dec. 1996