Reduction Factors of Pyramids on Undirected and Directed Graphs (bibtex)
by Yll Haxhimusa, Walter G. Kropatsch
Abstract:
We present two new methods to determine contraction kernels for the construction of graph pyramids. The first method is restricted to undirected graphs and yields a reduction factor of at least. This means with our method the number of vertices in the subgraph induced by any set of contractible edges reduces to half or less by a single parallel contraction. Our second method also works for directed graphs. Our methods yield better reduction factors than Meer s stochastic decimation algorithm, in all tests. The lower bound of the reduction factor becomes crucial with large images. We also give a method to compare the structure of the image pyramid.
Reference:
Reduction Factors of Pyramids on Undirected and Directed Graphs (Yll Haxhimusa, Walter G. Kropatsch), Technical report, PRIP, TU Wien, 2002.
Bibtex Entry:
@TechReport{TR074,
  author =	 "Yll Haxhimusa and Walter G. Kropatsch",
  title =	 "Reduction {F}actors of {P}yramids on {U}ndirected
                  and {D}irected {G}raphs",
  institution =	 "PRIP, TU Wien",
  number =	 "PRIP-TR-074",
  year =	 "2002",
  url =		 "ftp://ftp.prip.tuwien.ac.at/pub/publications/trs/tr74.pdf",
  abstract =	 "We present two new methods to determine contraction
                  kernels for the construction of graph pyramids. The
                  first method is restricted to undirected graphs and
                  yields a reduction factor of at least. This means
                  with our method the number of vertices in the
                  subgraph induced by any set of contractible edges
                  reduces to half or less by a single parallel
                  contraction. Our second method also works for
                  directed graphs. Our methods yield better reduction
                  factors than Meer s stochastic decimation algorithm,
                  in all tests. The lower bound of the reduction
                  factor becomes crucial with large images. We also
                  give a method to compare the structure of the image
                  pyramid.",
}
Powered by bibtexbrowser