Title:

   Reversing Subdivision Rules:
   Local Linear Conditions and
   Observations on Inner Products

Speaker:

   Richard Bartels
   University of Waterloo
   Computer Science Department

Abstract:

   Subdivision systems provide rules whereby simple affine combinations
   are applied repetetively, starting with relatively few points, to yield
   successively larger and larger sets of points that converge to continuous
   curves and surfaces in the limit.  Subdivision techniques are becoming
   quite useful in computer aided geometric design and computer graphics.

   In this talk we consider the approximate reversal of a given subdivision.
   Starting with a large number of data points, we seek to resolve that data
   into successively smaller and smaller sets of points.  We want each set to
   serve as possible starting points for the given subdivision to reproduce
   the given data.  Motivations for doing this, coming from computer graphics,
   include displaying objects efficiently at different resolutions and
   compressing images.

   We show how local least-squares data fitting can be used to reverse a
   subdivision rule and how this reversal is related to biorthogonal wavelet
   systems. We are able to produce multiresolution structures for some common
   subdivision rules that have both sparse reconstruction and decomposition
   filters.  We observe that each biorthogonal system we produce can be
   interpreted as a semiorthogonal system with an inner product induced
   on the multiresolution that is quite different from that normally used.
   Some examples of the use of our approach on images and geometry will
   be given.