October 2001

2001 Workshop on Shape-Based Retrieval and Analysis of 3D Models

• Shock graph:
   
  • Directed planar graph
     
                                                            
     
     
  • Augments the Medial Axis (MA)
     

• Computation of the Shock graph:
   
  • Originally using singularities of the Hamilton-Jacobi equation using an embedding in a higher dimension (level set approach).
     
    • Drawback: Cannot deal with junctions, open curves.
       
  • Wave propagation alternative:
     
    • Combine Computational Geometry (i.e., bisectors) with the PDE approach [Tek:ICCV'99].
       
    • Use flow along bisectors originating at sources only :
      • Exact, efficient, allows for deformations, etc.

• Use in Reconstruction of 2D Shape [CVPR'99] :
   

• Use in Recognition of 2D Shape [ICCV'01]
   
  • Edit-distance shock matching [Sebastian, Ph.D. Thesis, Oct. 2001]

• Perceptual Grouping as object recognition divided by two ! [POCV'01]
   
  • Hierarchical grouping

• Use in Recognition of 3D Shape [ICCV'01]
   
  • Aspect graph approach

• Classic definition due to Blum :
   

  Loci of maximal inscribed spheres (Figure from Leyton's PISA description, e.g., see "Symmetry, Causality, Mind," MIT Press, 1992).
  Loci of wavefront intercepts (quenching grassfire)

   

   

  • Traditional methods :
     
    • Thinning
       
    • Distance maps
       
    • Surface evolution
       
    • Boundary modeling
       
    • Graphs, Voronoi diagrams, Crust
       
    • Bisectors
       

   

  • Issues related to the Use of 3D Skeletons :
     
    • Redundancy : Numerous 3D medial axis points. Need for a compact representation.
       
    • Lack of a graph structure (for discrete representations)
       
    • Computational efficiency for large datasets.
       

   

  • Curve Skeletons :
     
    • It is desirable to reduce the dimensionality of the MA.
       
    • Tubular shapes are important (trees, blood vessels, etc.). E.g., many medical applications (path planning for VR, surgery training, etc.).
       
    • Relates to the Generalized Cylinders [Binford et al. ; Ponce et al.]
       
    • Recent approaches :
       
      • Discrete curve skeleton [Sanniti di Baja et al. : 2000]
        (thin set of connected voxels initiated at significant surface features, e.g., corners)
         
      • Continuous curve skeleton based on Voronoi Diagram [Montanvert, Attali : 1997]
        (Iterative prunning of the VD)
        Application in the representation of realistic trees [Seth Teller et al. : 2001]
         
      • Continuous curve skeleton based on path climbing in (induced) Morse (height) functions [Verroust & Lazarus : 2000]
        (height is taken to be the distance from pre-selected surface points: e.g., the toes/feet of a human body scan)
         
      • Snake-like relaxation in a distance potential field [Leymarie & Levine: 1990 ; Chuang et al. : 2000]
         
         
    • Simple example : scan of a cylindrical object (e.g., typical of a CT scan) :

  White spheres: input points; Green spheres: A_1^3-2 shocks; Red spheres: A_1^4 shocks

  Scaffold minus sheets and curves receding to infinity.	Same scaffold after regularization.

   

  ---

  III. A Formal Classification of the Local Form of 3D Skeletons

  [Joint work with Peter Giblin : CVPR'00 ]

   

  
  Order of contact
   
  A_k^n : k+1 degree of contact at n distinct points
  NB: Only "odd" orders of contacts (i.e., k = 1, 3) can contribute to the MA.

   

  In 3D, there are generically FIVE principal types of shocks [Giblin & Kimia: ICCV'01]:

  A_1^2 : SHEETS   A_1^3 : Axial CURVES   A_3 : "Surface" CURVES (e.g., ridges)   A_1^4 : "Internal" NODES (e.g., Voronoi nodes)        A_1 A_3 : "Surface" NODES      (e.g., end of ridges)

   

  ---

  Shock Flow

   

  Flow on surfaces : Radial expansion

  2 skewed edges give rise to a saddle MA sheet.	Flow is initiated at a single point.

   

  Flow on curves : Bi-directional expansion

  
  Regular (1), Initial (2), Final (4) flow points. Degenerate (3) not shown.

   

  Flow on nodes : Inward / Outward flows

  
  Labeling based on inward (curve) flows.

   

  Final classification of 18 possible shock points in 3D based on contact with spheres, A^n_k, and flow types.

   

   

  ---

  IV. Shock Scaffold

   

  • Hypergraph representation of shape :
     
    • Nodes : Isolated points (A_1 A_3 and A_1^4)
       
    • Links : Curves (A_3 and A_1^3)
       
    • Hyperlinks : Sheets (A_1^2)

   

  • The Shock Scaffold denotes the three-tier hierarchical representation :
     
    • Retain all details.
       
    • Ignore the geometry of sheets, but retain their existence and connectivity.
       
    • Ignore the geometry of sheets and curves, but retain their existence and connectivity.

   

  • Towards a generalized cylinder/ridge description of shape.
     

   

  ---

  V. Computing the Shock Scaffold

   

  • Propagation from sources to sinks.
     
    • Computational geometry approach (from Huseyin Tek's thesis)

  
  Click for ANIMATION

   

                    o Wave propagation approach

  
  Click for DETAILS

   

  • Any geometric model for sources as long as the equations for bisectors can be computed analytically or numerically :
     
    • Points, circles, spheres, lines, Euler spirals, polygons, etc.
      

   

  • Similarly in 3D, we use flow along the scaffold :
     
    • Detect all initial sources of propagation.
       
    • Propagate along bisectors, detect intersections, and initiate new sources.
       
    • Repeat until all sources have propagated.

   

  Constructive example:   Point sources create MA sheets by pairs: identified and represented by A_1^2-2 (bi-tangent, initial) shocks.   In turn, radial flow along sheets create at intercepts MA axial curves relating a triplet of input sources: identified and represented by A_1^3-2 (tri-tangent, initial) shocks.   Flow along curves create at intercepts (not shown) MA nodes...

   

   

  • Results in a directed (hyper)graph :
     
    • Exact (based on the concept of bisector intercepts)
       
    • Extremeley efficient (robustness and low practical numerical complexity):
       
      • E.g. : 22K points under 9 secs., 50K points in 20 secs. on a 360 MHz Octane.
          
    • We have applied this technology to unorganized clouds of points.
       
    • Can be generalized to other forms of inputs of practical interest (unorganized polygons, splines, other surface patches and manifolds).

  ---

  VI. Regularizing the Shock Scaffold

   

  • Giblin and Kimia: Transition of the 2D MA
     
    • Examples :
       

  L shape (click for ANIMATION)	Noisy quadrangle (click for ANIMATION)

   

   

  • Giblin and Kimia: Transition of the 3D MA (ECCV2002)
     

  

   

  

   

  • Illustrations of possible transitions in 3D (after [Bogaevski, Arnold et al.]) :

   

  A_1^5 transition

   

  A_1^4 transition

   

  A_1 A_3 - I transition

   

  A_1 A_3 - II transition

   

  A_1^2 A_3 - I transition

   

  A_1^2 A_3 - II transition

   

  A_5 transition

   

  • For a complete picture [Bogaevski, Arnold et al.] : CLICK here.

   

  ---

   

   Aorta/Branching shape

  Pruning the graph/scaffold using flow, shock labels and impact on the original surface/object.

  
  

  
   
   

  
   
  

  
  

   

   

  ---

  More examples :

  • Mask/Face : http://www.lems.brown.edu/vision/people/leymarie/Zurich/Scaffold/scaffold8.html
       
  • Polygonal Samples : http://www.lems.brown.edu/vision/people/leymarie/Zurich/Scaffold/future.html
     
  • Pot and Sherds : http://www.lems.brown.edu/vision/people/leymarie/Zurich/Scaffold/next3.html
     
  • Most recent results: http://www.lems.brown.edu/vision/researchAreas/Shocks3D/ResultsApril02/

   

  ---

  TOP

  Last Updated: April 30, 2002