With the objective of having the best properties of both types of pyramids, the bounded irregular pyramid (BIP) was proposed by Marfil et al (2004). The BIP is a hierarchical structure whose data structure combines the simplest regular and irregular structures: the 2x2/4 regular one and the simple graph irregular representation. The decimation scheme is also decomposed into two stages, one of them dealing with the regular structure and the other one with the irregular structure. Both decimation processes employ the sequential union-find scheme. The aim is to apply the regular decimation in the homogeneous parts of the image, meanwhile the heterogeneous parts are decimated using the irregular process. Thus, the BIP approximates or even outperforms previously proposed hierarchical segmentation approaches, yet it can be computed much faster (Marfil et al, 2006). However, it was originally highly affected by the shift variance problem, i.e. it provides an image segmentation which varies when the image is shifted slightly. This problem has been recently solved (Vázquez-Martín et al, 2009).

However, the new versions of the BIP employs still the simple graph to encode the relationships among nodes of the same level. Simple graphs only take into account adjacency relationships, being unable to distinguish from the graph an adjacency relation from an inclusion relation between two regions. Besides, if there is two non-connected boundaries which will join one region to another one, the simple graph only joins these nodes by one arc. These limitations can be raised if dual graphs are employed because their structure is adapted to the processed data and they correctly encode the topology in 2D. In this project, we will employ the dual graph data structure and the maximal independent edge set (MIES) decimation process proposed by Haxhimusa and Kropatsch (2004) to deal with the heterogeneous parts of the image. The use of the dual graph will allow to preserve the topology of the image and to correctly encode the relation of adjacency and inclusion between image regions.
 

Y. Haxhimusa and W.G. Kropatsch. Segmentation graph hierarchies. In A.L.N. Fred et al.(Ed.), SSPR2004 and SPR2004, 3138 LNCS, 343–351, Springer, 2004.

R. Marfil, L. Molina-Tanco, A. Bandera, J.A. Rodriguez, and F. Sandoval. Pyramid segmentation algorithms revisited. Pattern Recognition, 39: 1430–1451, 2006.

R. Marfil, J.A. Rodriguez, A. Bandera, and F. Sandoval. Bounded irregular pyramid: a new structure for color image segmentation. Pattern Recognition, 37(3): 623–626, 2004.

R. Vázquez-Martín, R. Marfil, P. Núñez, A. Bandera, and F. Sandoval. A novel approach for salient image regions detection and description. Pattern Recognition Letters, 30: 1464–1476, 2009.