May 27, 1998

GENESIS
Morphological handling of shapes

Project leader : Prof. B.B. Kimia , email: kimia@lems.brown.edu

Project members :

A paradigm for shape creation, deformation, manipulation, updating, ... and the study of evolution through transitions (and eventually morphometric dynamics).

For 1998 we will limit ourselves to (at first, function of progress) :

Goal:

References (previous work):

  1. Z.F.Roadhouse & B.B.Kimia, "A morphogenetic approach to generating shape queries" CVPR'97.
  2. P.J.Giblin & B.B.Kimia, "On the local form and transitions of symmetry sets, and medial axes, and shocks in 2D", LEMS TR 170, April 1998.
  3. R.C.Zeleznik, K.P.Herndon & J.F.Hughes, "SKETCH: An interface for sketching 3D scenes", SIGGRAPH'96.
  4. K.Siddiqi & B.B.Kimia, "Parts of visual form: Computational aspects", PAMI, vol.17(3), pp.239-251, March 1995.
  5. D.Sharvit, J.Chan & B.B.Kimia, "Symmetry-based indexing of image databases", CVPR'98.
  6. H.Tek, F.Leymarie & B.B.Kimia, "Multiple generation shock detection & labeling using CEDT", in "Visual Form", 1997.
  7. M.Leyton, "Symmetry, Causality, Mind", MIT Press, 1992.
  8. J.Bloomenthal, "Skeletal design of natural forms", PhD thesis, Computer Sci. Dept, U. of Calgary, Alberta, Canada, January 1995.
  9. Fabrizio Capobianco, "FORMAFLUENS: a tool for describing evolving forms", Dipartimento di Informatica e Sistemistica, Pavia University, Italy, 1997.
  10. S.C.Zhu & A.Yuille, "FORMS: A flexible object recognition & modeling system" IJCV, vol.20(3), 1996.

Early challenges

How to:

  1. draw a "simple" axis (with the mouse, in a gesture-based manner);
  2. bend an axis;
  3. compose 2 shapes : bring a part or on another one and unify their representation;
  4. de-compose 2 shapes : e.g. separate a protrusion from a "corps"
  5. pull out a protrusion (of a certain shape, along an axis);
  6. push in an indentation
  7. ...

Dense Space of Shapes (changes)

Examples (suggestions) of interaction:

  1. click on a shock --> reconstruct points on the bounding contour
  2. click on a shock group --> reconstruct bounding curves or part
  3. 2 clicks (or other button) on a shock or shock group --> reconstruct the contours of a shock group + its parents/children
  4. "simplify" the shape or part (e.g. rectify it or un-bend)
  5. Menu of operations on a shock group : bend, protrude, adds, ...

DRAFT - PLAN

Step I - Background + Elementary Reconstruction

  1. Read some literature, with an emphasis on:
  2. Look at Brandon Roy's code (in Raphael) and meet him if needed.
  3. Implement from scratch - or debug/modify Brandon's code - the following "elementary" functions (assuming an available shock graph: ask Daniel):

Step II - Bending of shapes

  1. Consider existing shock datum: bend these ? (the trace of)
  2. "Knobs" on curvature functions

Step III - "Erosions" of shape

Modification by deletion/transform of branches

  1. Deletion of skeletal features (shock groups)
  2. Deletion from the boundary (select a boundary segment --> look for significant curvature minima : see Siddiqi&Kimia)
  3. De-compose: send waves to modify (locally) the shock graph (see Tek, Leymarie&Kimia).
  4. "Simplify" (to be defined; but see Step IV).
  5. "Complexify" by "adding" (empty "stuff") indents, holes, ... (to be defined).

Step IV - Rectification of shape

Straightening, simplification or mapping to "primitives" of shape sub-parts.

  1. Transform on accelerations : constant or null
  2. Transform on velocities: constant
  3. "Simplify": remove parts (protrusions, indents), separate (at necks), ...
  4. Map to canonical parts: transform toward cylindrical parts with simple cross-sections (constant, linear) or circular arcs.

Step V - "Dilation" of shape

Modification by addition/transform of branches

  1. Addition of skeletal features (shock groups): create an axis.
  2. Addition from the boundary (select a boundary segment --> create significant curvature extrema : see Leyton )
  3. Gesture-based: draw the (coarse) outline of a part and merge it with the core shape.
  4. Re-compose: send waves to modify (locally) the shock graph (see Tek, Leymarie&Kimia).
  5. "Simplify" (to be defined; but see Step IV).
  6. "Complexify" by "adding" (new "stuff") protrusions, filing holes, ... (to be defined).

Step VI - Other transforms

  1. Displacement of parts (protrusions/indents) along a boundary.
  2. Displacement of "stuff": moving and deforming holes
  3. Fusion: merge parts with a core shape
  4. Fission: separate parts from a core shape, but keep/create the identity of these parts/shapes.
  5. "Fractalize/randomize": add micro-structure to the bounding contours.
  6. "Smooth": remove micro-structure from the bounding contours (e.g. with implicit polynomials)

Step VII - Creation from scratch

No shock graph given; have to create a purely synthetic shape.

  1. Axis-based:
  2. Gesture-based:

Step VIII - Evolutions

Study the characterization of the evolution/appearance of species through shape "transitions".

Study/compare variations across a specie (say humans) in terms of shape "morphings".

Step IX - Image Analysis with Genesis

Use the machinery developed for Genesis on images to extract 2D shapes.

Page created by Frederic Leymarie, 1998.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu