Shape Segmentation and Matching with Flow Discretization

Tamal K. Dey, Joachim Giesen, Samrat Goswami

Proceedings of the Workshop on Algorithms and Data Structures (WADS)

Lecture Notes in Computer Science 2748, Frank K. H. A. Dehne, Jörg-Rüdiger Sack, Michiel H. M. Smid Eds., Pages 25-36, 2003

Motivation

Problems such as object recognition, classification, matching, and tracking require a way to segment a shape into features.

Goal of This Research

Dynamical systems have been studied as a topological way to define features of continuous shapes. The authors wish to use similar ideas to segment discrete shapes into features.

Goal of This Paper

Given a point sample P mathend000# of a surface, the authors describe how to define features of the discrete shape P mathend000# by mimicking the definition of a feature of a continuous shape from earlier papers [12] [15]. They describe the resulting algorithm for segmenting P mathend000# into its features and then describe a shape matching algorithm based on this segmentation.

This paper gives a segmentation algorithm for shapes in 1#1² mathend000#. For shapes in 1#1³ mathend000#, features are approximated by mimicking the two-dimensional algorithm.

This paper's shape matching algorithm works by first computing a feature segmentation and then representing each feature segment as a point with a weight equal to the segment's volume. Then the algorithm simply matches between the two weighted point sets from two shapes. The whole process is rotation-, translation-, mirroring-, and scaling-invariant.

Related Work

Applications listed above require a way to segment shapes into features [9] [10] [18] [24] [28] [35]. Known structures for segmenting shapes include shock graphs [31] [29], medial axes [23], and Reeb graphs [18]. Topological approaches include level sets [30] and topological persistence [14].

This paper's topological approach, namely dynamical systems, has been used for surface reconstruction [12] [15]. This earlier work contains the definition of features for continuous shapes using dynamical systems. The discrete definition of features in this paper is derived from the continuous definition.

Shape matching methods often compute a signature for each of two shapes and then compare their signatures. Types of shape signatures include curvature distribution [3] [32], wavelet coefficients [20], Fourier descriptors [2], geometric statistics [4] [33], spin images [21] and shape distribution [25]. See the survey articles [1] [7] [24] [25] for details.

Another shape matching approach is to segment each of two shapes into a set of features and then compare their features [5] [6] [8] [17]. This paper's shape matching algorithm uses such an approach, but ends up only matching between two small weighted point sets instead of matching large point sets derived from the boundary of the shapes [19].

Other relevant work: [11] [13] [22] [16] [26] [27] [34] [36].

Results

This paper's segmentation algorithm is robust against small variations in shapes, a typical property of topologically defined features. The segmentation appears to be quite effective for shapes in both two and three dimensions. The computed segments are often close to the intuitive ones.

Since this paper deals with discrete shapes (point sets), it would be nice to have a way to measure how close the features of the discrete point sets are to their corresponding features on the continuous shapes from which they were derived. The authors mention this as an issue which has not yet been solved.

There may also be more effective ways to define the signature of a feature. This paper's algorithm took the signature of a feature to be its volume.

Bibliography

1

H. Alt and L. J. Guibas.
Discrete geometric shapes: Matching, interpolation, and approximation: a survey.
Technical Report B 96-11, EVL-1996-142, Institute of Computer Science, Freie Universität Berlin, 1996.

2

K. Arbter, W. E. Snyder, H. Burkhardt, and G. Hirzinger.
Application of affine-invariant fourier descriptors to recognition of 3-d objects.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 12:640-647, 1990.

3

E. M. Arkin, L. P. Chew, D. P. Huttenlocher, K. Kedem, and J. S. Mitchell.
An efficiently computable metric for comparing polygonal shapes.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 13:209-216, 1991.

4

A. P. Askbrook, N. A. Thacker, P. I. Rockett, and C. I. Brown.
Robust recognition of scaled shapes using pairwise geometric histograms.
In Proceedings of the British Machine Vision Conference, pages 503-512, 1995.

5

R. Basri, L. Costa, D. Geiger, and D. Jacobs.
Determining the similarity of deformable shapes.
Vision Research, 38:2365-2385, 1998.

6

S. Belongie and J. Malik.
Matching with shape contexts.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 24:509-522, 2002.

7

P. Besl and R. C. Jain.
Three-dimensional object recognition.
Computing Surveys, 17:75-145, 1985.

8

P. J. Besl and N. D. McKay.
A method for registration of 3-d shapes.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 14:239-256, 1992.

9

T. A. Cass.
Robust affine structure matching for 3d object recognition.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 20:1265-1274, 1998.

10

Y. Chen and G. Medioni.
Object modelling by registration of multiple range images.
Image and Vision Computing, 10:145-155, 1992.

11

L. P. Chew, M. T. Goodrich, D. P. Huttenlocher, K. Kedem, J. M. Kleinberg, and D. Kravets.
Geometric pattern matching under euclidean motion.
Computational Geometry: Theory and Applications, 7:113-124, 1997.

12

H. Edelsbrunner.
Surface reconstruction by wrapping finite point sets in space.
In B. Aronov, S. Basu, J. Pach, and M. Sharir, editors, Ricky Pollack and Eli Goodman Festschrift. Springer-Verlag, to appear.

13

H. Edelsbrunner, M. A. Facello, and J. Liang.
On the definition and the construction of pockets in macromolecules.
Discrete Applied Mathematics, 88:83-102, 1998.

14

H. Edelsbrunner, D. Letscher, and A. Zomorodian.
Topological persistence and simplification.
In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (FOCS), pages 454-463, 2001.

15

J. Giesen and M. John.
The flow complex: a data structure for geometric modeling.
In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 285-294, 2002.

16

K. Grove.
Critical point theory for distance functions.
In Proceedings of Symposia in Pure Mathematics, volume 54, pages 357-385, 1993.

17

S. K. Gupta, W. C. Regli, and D. S. Nau.
Manufacturing feature instance: Which ones to recognize?
In Proceedings of the Symposium on Solid Modeling and Applications, pages 141-152, 1995.

18

M. Hilaga, Y. Shinagawa, T. Komura, and T. Kunni.
Topology matching for fully automatic similarity estimation of 3d shapes.
In Proceedings of SIGGRAPH 2001, pages 203-212, 2001.

19

D. P. Huttelnocher, G. A. Klanderman, and W. J. Rucklidge.
Computing images using the hausdorff distance.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 15:850-863, 1993.

20

C. E. Jacobs, A. Finkelstein, and D. H. Salesin.
Fast multiresolution image querying.
In Proceedings of SIGGRAPH '95, pages 277-286, 1995.

21

A. E. Johnson and M. Hebert.
Using spin-images for efficient multiple model recognition in cluttered 3-d scenes.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 21:433-449, 1999.

22

I. D. Kuntz.
Structure-based strategies for drug design and discovery.
Science, 257:1078-1082, 1992.

23

F. Leymarie and B. Kimia.
The shock scaffold for representing 3d shape.
In Proceedings of the 4th International Workshop on Visual Form, volume 2059 of Lecture Notes in Computer Science, pages 216-229. Springer-Verlag, 2001.

24

S. Loncaric.
A survey of shape analysis techniques.
Pattern Recognition, 31:983-1001, 1998.

25

R. Osada, T. Funkhouser, B. Chazelle, and D. Dobkin.
Matching 3d models with shape distribution.
In Proceedings of Shape Modeling International, 2001.

26

R. J. Prokop and A. P. Reeves.
A survey of moment based techniques for unoccluded object representation and recognition.
Graphics Models and Image Processing (CVGIP), 54(5):438-460, 1992.

27

Y. Rubner, C. Tomasi, and L. Guibas.
A metric for distributions with applications to image databases.
In Proceedings of the 6th International Conference on Computer Vision, pages 59-66, 1998.

28

S. Sclaroff and A. P. Pentland.
Modal matching for correspondence and recognition.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 17:545-561, 1995.

29

T. B. Sebastian, P. N. Klein, and B. Kimia.
Recognition of shapes by editing shock graphs.
In Proceedings of the International Conference on Computer Vision, pages 755-762, 2001.

30

J. A. Sethian.
Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science.
Cambridge University Press, 2000.

31

K. Siddiqi, A. Shokoufandeh, S. J. Dickinson, and S. W. Zucker.
Shock graphs and shape matching.
In Computer Vision, pages 222-229, 1998.

32

R. Sonthi, G. Kunjur, and R. Gadh.
Shape feature determination using the curvature region representation.
In Proceedings of the Symposium on Solid Modeling and Applications, pages 285-296, 1997.

33

G. Taubin and D. Cooper.
Object Recognition Based on Moment (of algebraic) Invariants, chapter Geometric Invariance in Computer Vision.
MIT Press, 1992.

34

R. C. Veltkamp and M. Hagedoorn.
State-of-the-art in shape matching.
Technical Report UU-CS-1999-27, Utrecht University, the Netherlands, 1999.

35

I. Weiss and M. Ray.
Model-based recognition of 3d object from single vision.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 23:116-128, 2001.

36

D. Zhang and M. Hebert.
Harmonic maps and their applications in surface matching.
In Computer Vision and Pattern Recognition '99, 1999.