Signal Processing
Digital image compression and transmission is a problem that (with the growth of the world wide web) is rapidly growing in prominence, and may be a fertile source of links between geometry and signal processing. One example is a recent note in the 11th ACM Symp. Comp. Geom., in Schwarz et al. describe a fast algorithm for finding the minimum area parallelogram enclosing a given polygon, motivated by a problem in signal processing of compressing image data via "rational decimation systems".
- Designing
two-dimensional filter banks based on geometric decompositions of the
frequency domain,
W. Chen and E. Lee, Berkeley.
- Image
pyramids and trees, quadtree data structures for
binary tree predictive image coding.
- Level set
methods for following the evolution of interfaces, J. Sethian,
Berkeley. The basic idea is to solve various "advancing front" type problems
such as finding shortest paths around obstacles, by evolving a surface
in one higher dimension that describes the dynamics of the front.
Includes movies and Java applets describing applications to
VLSI design, medical image processing, noise removal from images, and
robot motion planning.
- A Quadtree Structured Video-phone Codec, L. Hanzo and A. Schober,
Southampton.
- Dr. Christian Schwarz's home page at the Max-Planck-Inst. fuer
Informatik includes pointers to longer versions of his papers on
finding minimal enclosing parallelograms and on the application of
this problem to rational decimation systems.
- US Patents
5134480,
5228098,
5444489,
5446806,
5452104,
and
5469212
describe video and image coding methods based on quadtrees.