1 Randomized Algorithms for Comparing and Understanding 3D Geometry Niloy J. Mitra Department of Electrical Engineering Advisor: Leonidas J. Guibas Associate Advisor: Marc Levoy

2 Comparing and Understanding 3D Geometry Need for Digital 3D Models games movies architectural design medicine Google earth manufacturing

3 Comparing and Understanding 3D Geometry Creating Geometry: 3D Modelers

4 Comparing and Understanding 3D Geometry Capturing Geometry: 3D Scanners laser scanner 3D geometryentertainment

5 Comparing and Understanding 3D Geometry Shape Acquisition

6 Comparing and Understanding 3D Geometry Shape Acquisition

7 Comparing and Understanding 3D Geometry Shape Acquisition Partial similarity between shapes

8 Comparing and Understanding 3D Geometry Shape Acquisition Partial similarity between shapes

9 Comparing and Understanding 3D Geometry Shape Acquisition Partial similarity between shapes Efficient shape retrieval for partial queries

10 Comparing and Understanding 3D Geometry Geometry Processing [Funkhouser et al. `05] [Katz and Tal `04] [Gelfand et al. `05] [Sharf et al.`04]

11 Comparing and Understanding 3D Geometry Model Organization and Retrieval [Kazdhan et al. `04]

12 Comparing and Understanding 3D Geometry Partial Shape Similarity Self-similarity of an object  symmetry partial similarity

13 Comparing and Understanding 3D Geometry Total vs Partial Matching Total matching is easy PCA (Principal Component Analysis) Axes

14 Comparing and Understanding 3D Geometry Total vs Partial Matching Partial matching is difficult Which region matches which other region(s)? Space of rigid transforms  rotation + translation Brute force approach  not feasible Instead of exhaustive searching, use local geometry to guide where to search Easy to verify a transform

15 Comparing and Understanding 3D Geometry Contributions Algorithms to: Identify and extract similar (symmetric) patches of different size Estimate partial shape similarity between models without explicitly aligning them Properties: Scalable and parallel Theoretical error bounds Output sensitive  depends on complexity of solution and not on the complexity of model(s)

16 Comparing and Understanding 3D Geometry Outline Introduction Related Work Symmetry Detection Probabilistic Fingerprints Conclusion and Future Work

17 Comparing and Understanding 3D Geometry Related Work: Global Alignment [Huber and Hebert`01][Li and Guskov `05][Gelfand et al. `05] Feature based alignment Combinatorial search, need multiple objects together

18 Comparing and Understanding 3D Geometry Related Work: Desc. Based Align. [Kazhan et al. `03][Osada et al. `02] Feature based alignment Combinatorial search, need multiple objects together Descriptor based alignment Fails for partial similarity

19 Comparing and Understanding 3D Geometry Related Work: Geometric Hashing [Gal and Cohen-Or`05] [Wolfson and Rigoutsos`97] Feature based alignment Combinatorial search, need multiple objects together Descriptor based alignment Fails for partial similarity Geometric hashing Tradeoff memory for time

20 Comparing and Understanding 3D Geometry Related Work: Symmetry Detection [Podolak et al. `06] brute force : O(n 6 ) [Loy and Eklundh `06] Hough transform on feature points [Thrun and Wegbreit `05] Shape from symmetry

21 Comparing and Understanding 3D Geometry Outline Introduction Related Work Symmetry Detection Probabilistic Fingerprints Conclusion and Future Work

22 Comparing and Understanding 3D Geometry Symmetry in Nature “Symmetry is a complexity-reducing concept [...]; seek it everywhere.” - Alan J. Perlis "Females of several species, including […] humans, prefer symmetrical males." - Chris Evan

23 Comparing and Understanding 3D Geometry Partial Symmetry Detection ( SIGGRAPH 2006) Given Object/shape (represented as point cloud, mesh,... ) Identify and extract similar (symmetric) patches of different size across different resolutions Goal

24 Comparing and Understanding 3D Geometry Partial Symmetry Transform Types: Reflection Rotation + Translation Uniform Scaling

25 Comparing and Understanding 3D Geometry Reflective Symmetry

26 Comparing and Understanding 3D Geometry Reflective Symmetry : A Pair Votes

27 Comparing and Understanding 3D Geometry Reflective Symmetry : Voting Continues

28 Comparing and Understanding 3D Geometry Reflective Symmetry : Voting Continues

29 Comparing and Understanding 3D Geometry Reflective Symmetry : Largest Cluster Height of cluster ! size of patch Spread of cluster ! approximation level

30 Comparing and Understanding 3D Geometry Pipeline

31 Comparing and Understanding 3D Geometry Pruning: Local Signatures Local signature  invariant under transforms Signatures disagree  points don’t correspond Use (  1,  2 ) for curvature based pruning

32 Comparing and Understanding 3D Geometry Reflection: Normal-based Pruning

33 Comparing and Understanding 3D Geometry Point Pair Pruning all pairs curvature based curvature + normal based

34 Comparing and Understanding 3D Geometry Transformations Reflection  point-pairs Rigid transform  more information Robust estimation of principal curvature frames [Cohen-Steiner et al. `03]

35 Comparing and Understanding 3D Geometry Mean-Shift Clustering Kernel: Type  radially symmetric hat Radius

36 Comparing and Understanding 3D Geometry Verification Clustering gives a good guess Verify  build symmetric patches Locally refine solution using ICP algorithm [Besl and McKay `92]

37 Comparing and Understanding 3D Geometry Random Sampling Height of clusters related to symmetric region size Random samples ! larger regions likely to be detected earlier Output sensitive

38 Comparing and Understanding 3D Geometry Analysis Assumptions: Smooth surface  -sampled No noise Relates number(n’) of random samples to: Size of symmetric patch (p) Confidence (1-  ) Sampling spacing, kernel radius, continuity of signature Tools for Analysis: Signature continuity Chernoff bound

39 Comparing and Understanding 3D Geometry Compression: Chambord

40 Comparing and Understanding 3D Geometry Compression: Chambord

41 Comparing and Understanding 3D Geometry Compression: Chambord

42 Comparing and Understanding 3D Geometry Approximate Symmetry: Dragon correction field UNITS: fraction of bounding box diagonal detected symmetries

43 Comparing and Understanding 3D Geometry Limitations Cannot differentiate between small sized symmetries and comparable noise [Castro et al. `06]

44 Comparing and Understanding 3D Geometry Articulated Motion: Horses registration  symmetry detection between two objects

45 Comparing and Understanding 3D Geometry Outline Introduction Related Work Symmetry Detection Probabilistic Fingerprints Conclusion and Future Work

46 Comparing and Understanding 3D Geometry Partial Shape Similarity (SGP 2006) Are two shapes similar in parts? Efficient tests require compact signatures database query online setting

47 Comparing and Understanding 3D Geometry partial similarity Probabilistic Fingerprints probabilistic fingerprint compare compact independent

48 Comparing and Understanding 3D Geometry Insight Partial matching ! difficult problem Total matching ! easy problem Reduce partial matching ! many small total matching problems Results in few false positives ! quick to verify and discard

49 Comparing and Understanding 3D Geometry Input Shapes

50 Comparing and Understanding 3D Geometry Sample Points

51 Comparing and Understanding 3D Geometry Shingles: Overlapping Patches

52 Comparing and Understanding 3D Geometry Shingles: Overlapping Patches

53 Comparing and Understanding 3D Geometry Bag of Patches: Ordering Discarded

54 Comparing and Understanding 3D Geometry Pipeline

55 Comparing and Understanding 3D Geometry Pipeline: Uniform Sampling Uniform spacing  use [Turk`92] Sample spacing  

56 Comparing and Understanding 3D Geometry Pipeline: Shingle Generation Shingles: overlapping unordered patches Shingle radius: 

57 Comparing and Understanding 3D Geometry Pipeline: Signatures Stable signatures Invariant to rigid transforms Spin-images Shape  unordered high-dimensional point set with rigid transform factored out

58 Comparing and Understanding 3D Geometry Similarity/resemblance Defined wrt. signatures Compare two bag of points in high-dim space No alignment required Brute force evaluation impractical Pipeline: Resemblance

59 Comparing and Understanding 3D Geometry How to Compare Point Sets Compare two point sets  no need to align Don’t have red and blue points together

60 Comparing and Understanding 3D Geometry Reduce Sample Size Randomly sample red points Randomly sample blue points still need to solve for correspondence independently

61 Comparing and Understanding 3D Geometry Min-hashing [Broder`97] Each of m random ‘experts’ Has an ordering of space-boxes Selects the point that lies in lowest ordered box 23

62 Comparing and Understanding 3D Geometry Min-hashing [Broder`97] Each of m random ‘experts’ Has an ordering of space-box Selects the point that lies in lowest ordered box 23 11

63 Comparing and Understanding 3D Geometry Pipeline: Min-hashing [Broder`97] Feature selection by random experts ‘Features’ only useful for correspondence Need not have any visual importance Reduces set comparison to element-wise comparison

64 Comparing and Understanding 3D Geometry Applications: Adaptive Features

65 Comparing and Understanding 3D Geometry Applications: Adaptive Features merged scan

66 Comparing and Understanding 3D Geometry Applications: Shape Space Partial similarity Articulated motion

67 Comparing and Understanding 3D Geometry Applications: Database Retrieval

68 Comparing and Understanding 3D Geometry Pre-processing time in seconds: Query time → 15 msec/model Fingerprint size → 10kb model# verticesuniform sampling spin imageRabin hashmin-hash skull54k0.87.50.054.5 Caesar65k1.47.30.0810.3 bunny121k1.813.80.042.9 horse8k0.75.70.057.3 Statistics

69 Comparing and Understanding 3D Geometry Limitations Fails if resemblance is small How to handle uniform scaling? Stability of spin-images

70 Comparing and Understanding 3D Geometry Outline Introduction Related Work Symmetry Detection Probabilistic Fingerprints Conclusion and Future Work

71 Comparing and Understanding 3D Geometry Conclusion Simple probabilistic framework Local evidence → global reasoning Geometric information for guidance Complexity of problem, not complexity of model Symmetry information → High level model understanding Possible to compare two shapes using very compact fingerprints without aligning the models Local reasoning → possible false positives → verification

72 Comparing and Understanding 3D Geometry Future Works Continuous scanning, assembly, hole filing Extension to deformable, time varying models Understanding of high dimensional data Online transmission, authentication, and security Data courtesy: Prof. B. Chen

73 Comparing and Understanding 3D Geometry Collaborators Natasha Gelfand, Stanford Joachim Giesen, MPII Saarbrücken Markus Gross, ETH Zürich Leonidas Guibas, Stanford An Nguyen, Stanford Mark Pauly, ETH Zürich Helmut Pottmann, Vienna University of Technology

74 Comparing and Understanding 3D Geometry Acknowledgements Gunnar Carlson Leonidas Guibas Jean-Claude Latombe Marc Levoy Mark Pauly Mike Cammarano, Billy Chen, Milton Chen, Kayvon Fatahalian, Gaurav Garg, Eran Guendelman, Daniel Horn, Mike Houston, Jeff Klingner, David Koller, Manu Kumar, Ren Ng, John Owens, Doantam Phan, Marie Ringel, Pradeep Sen, Eino-Ville Talvala, Vaibhav Vaish, Ron Yeh Emilio Antunez, Qing Fang, Natasha Gelfand, Olaf A. Hall-Holt, Kyle Heath, Rachel Kolodny, Nikola Milosavljevic, An Nguyen, Steve Oudot, Maksim Ovsjanikov, Daniel Russel, Aneesh Sharma, Jaewon Shin, Primoz Skraba, Michael Wand, Yusu Wang, Danny Yang, Afra Zomorodian Pierre Alliez, Mario Botsch, Pat Hanrahan, Michael Hoffer, Rajiv Motwani, Richard Keiser, Doo Young Kwon, Bob Sumner, Martin Wicke Manuela Cavegn, Heather Gentner, John Gerth, Ada Glucksman, Hoa Nguyen Joseph W. and Hon Mai Goodman Stanford Graduate Fellowship Cargo, Darpa, ITR, NIH, and NSF funding

75 Comparing and Understanding 3D Geometry Acknowledgements Stanford Cricket Club Stanford Outing Club Stanford Climbing Wall Stanford Alpine Club Kamran Ahsan, Abhishek Bapna, Akanksha Bapna, Indrahit Bhattacharya, Gaurav Chandra, Anirban Dasgupta, Anupam Datta, Amal Ekbal, Gaurav Garg, Mahesh Hardikar, Sara Kalantari, Uma Kelkar, Neha Kumar, Subhasish Mitra, Shoubhik Mukhopadhyay, Subha Nabar, Anindya Pathak, Inam Ur-Rehman, Mitul, Saha, Debasis Sahoo, Sriram Sankaranarayanan, Arjun Singh, Padma Sundaram, Vaibhav Vaish, gsb-SIE fellows, climbing buddies, cricket club folks, … many I missed

76 Comparing and Understanding 3D Geometry Acknowledgements Parents Brother Devasree

77 Comparing and Understanding 3D Geometry Acknowledgements

78 Comparing and Understanding 3D Geometry thank you!