Combinatorial Pyramids

Luc Brun &
Walter Kropatsch.

An irregular pyramid consists of a stack of successively reduced graphs. Each smaller graph is deduced from the preceding one by the contraction or the removal of a set of edges. Using a fixed decimation ratio we need approximately O(log(image size)) graphs to encode the whole pyramid. A combinatorial map encodes a planar graph thanks to two permutations encoding the edges and their orientation around the vertices. We present in this article an encoding of a combinatorial pyramid which allows to fold the whole pyramid in the base level layer and provides at the same time a measure of the relevance of every pixel. This encoding is used to retreive any reduced combinatorial map of the pyramid from its base and to compute the borders of the partition encoded by the combinatorial maps.