Building Irregular Pyramids by Dual Graph Contraction (bibtex)
by Walter G. Kropatsch
Abstract:
Many image analysis tasks lead to or make use of graph structures that are related through the analysis process with the planar layout of a digital image. This paper presents a theory that allows to build different types of hierarchies on top of such image graphs. The theory is based on the properties of a pair of dual image graphs that the reduction process should preserve, e.g. the structure of a particular input graph. The reduction process is controlled by decimation parameters, i.e. a selected subset of vertices, called survivors, and a selected subset of the graph's edges, the parent-child connections. It is formally shown that two phases of contractions transform a dual image graph to a dual image graph built by the surviving vertices. Phase one operates on the original (neighborhood) graph and eliminates all non-surviving vertices. Phase two operates on the dual (face) graph and eliminates all degenerated faces that have been created in phase one. The resulting graph preserves the structure of the survivors, it is minimal and unique with respect to the selected decimation parameters. The result is compared with two modified specifications, the one already in use for building stochastic and adaptive irregular pyramids.
Reference:
Building Irregular Pyramids by Dual Graph Contraction (Walter G. Kropatsch), Technical report, PRIP, TU Wien, 1994.
Bibtex Entry:
@TechReport{TR035,
  author =	 "Walter G. Kropatsch",
  institution =	 "PRIP, TU Wien",
  number =	 "PRIP-TR-035",
  title =	 "Building {I}rregular {P}yramids by {D}ual {G}raph
                  {C}ontraction",
  year =	 "1994",
  url =		 "ftp://ftp.prip.tuwien.ac.at/pub/publications/trs/tr35.pdf",
  abstract =	 "Many image analysis tasks lead to or make use of
                  graph structures that are related through the
                  analysis process with the planar layout of a digital
                  image. This paper presents a theory that allows to
                  build different types of hierarchies on top of such
                  image graphs. The theory is based on the properties
                  of a pair of dual image graphs that the reduction
                  process should preserve, e.g. the structure of a
                  particular input graph. The reduction process is
                  controlled by decimation parameters, i.e. a selected
                  subset of vertices, called survivors, and a selected
                  subset of the graph's edges, the parent-child
                  connections. It is formally shown that two phases of
                  contractions transform a dual image graph to a dual
                  image graph built by the surviving vertices. Phase
                  one operates on the original (neighborhood) graph
                  and eliminates all non-surviving vertices. Phase two
                  operates on the dual (face) graph and eliminates all
                  degenerated faces that have been created in phase
                  one. The resulting graph preserves the structure of
                  the survivors, it is minimal and unique with respect
                  to the selected decimation parameters. The result is
                  compared with two modified specifications, the one
                  already in use for building stochastic and adaptive
                  irregular pyramids.",
}
Powered by bibtexbrowser