Graph Pyramids and First Applications

                     Walter Kropatsch

The structural component of a computer vision model expresses
qualitative image and scene properties.
In our approach a hierarchy of plane graphs forms the structure
to represent a variety of different levels of abstraction.
Repeated parallel application of dual graph contractions generates
a stack of successively smaller graphs bottom-up:
a dual irregular pyramid.
This process preserves topological relations among the 'surviving'
components. Decimation parameters control one single dual contraction
of the graph. Equivalent contraction kernels (ECKs) combine several
sets of decimation parameters.

In line image understanding a minimal line property preserving (MLPP)
graph of the image complements the structural information in geometric
graph representations like the run graph. With such a graph and its dual
it is possible to efficently detect topological features like loops and
holes and to make use of relations like containment. A new rule based
dual graph contraction transforms the initial run graph and its dual
into MLPP graphs. A parallel O(log(curvelength)) implementation
of the algorithm is described along with results on a selection of real
world line images.