Each level of an irregular pyramid can be encoded using a graph. One possibility is to employ simple graphs, but these have two main drawbacks for image processing tasks: (i) they do not permit to know if two adjacent regions have one or more common boundaries, and (ii) they do not allow to differentiate an adjacency relationship between two regions from an inclusion relationship. Instead of simple graphs, each hierarchy level could be represented using a dual graph. Dual graphs preserve the topology information at upper levels representing each level of the pyramid as a dual pair of graphs and computing contraction and removal operations within them. Thus, they solve the drawbacks of the RAG approach. The problem of this structure is the high increase of memory requirements and execution times since two data structures need now to be stored and processed. To avoid this problem, each level of the pyramid can be encoded using a combinatorial map. The combinatorial map encodes explicitly the orientation of edges around the graph vertices. Then, it uses a planar graph to represent each level of the pyramid instead of a pair of dual graphs. This reduces the memory requirements and execution times. The Combinatorial Pyramid (Brun and Kropatsch, 2001) is then defined by an initial combinatorial map which can be successively reduced using the general scheme proposed by Walter G. Kropatsch (1995).

The structure of the Combinatorial Pyramid has been employed for image segmentation by the PRIP Group (TU Vienna). Specifically, the MST pyramid takes as input an image graph and obtains a hierarchy of partitions by using the minimum spanning tree (MST) algorithm and the region internal/external differences (Felzenszwalb and Huttenlocher, 2004). The internal difference (contrast) of a region is defined as the largest weight of the arcs on its MST. The approach was initially proposed in the dual graph-based irregular pyramid framework, and posteriorly adapted to the Combinatorial Pyramid framework (Haxhimusa et al, 2006). Within this integrated action, the MST pyramid method has been extended. The segmentation is now conducted in two stages, which takes into account region and edge properties (Antúnez et al, 2011). The evaluation of this algorithm using the Berkeley Segmentation Data Set and Benchmark (BSDS300) (Arbeláez et al, 2011) has provided a F-measure equal to 0.65 (see here our results).

Y. Haxhimusa, A. Ion and W.G. Kropatsch. Evaluating graph-based segmentation algorithms. In Proc. of the 18th Int. Conf. on Pattern Recognition, 2006

P.F. Felzenszwalb and D.P. Huttenlocher, Efficient graph-based image segmentation. Int. Journal of Computer Vision 59: 167-181, 2004

W.G. Kropatsch. Building irregular pyramids by dual graph contraction. IEE-Proc. Vis. Im. and Sig. Proc. 142(6): 366-374, 1995

E. Antúnez, R. Marfil and A. Bandera. Combining contour and region features inside the Combinatorial Pyramid for topology-preserving perceptual image segmentation. Submitted to Pattern Recognition Letters, 2011

P. Arbeláez, M. Maire, C. Fowlkes and J. Malik. Contour detection and hierarchical image segmentation. IEEE Trans. on Pattern Analysis Machine Intell. 33, 2011

L. Brun and W.G. Kropatsch. Introduction to combinatorial pyramids. Lecture Notes in Computer Science 2243: 108-128, 2001