A Review on Graph Based Segmentation <s> B. Irregular pyramids <s> A novel multiresolution image analysis technique based on hierarchies of irregular tessellations generated in parallel by independent stochastic processes is presented. Like traditional image pyramids these hierarchies are constructed in a number of steps on the order of log(image-size) steps. However, the structure of a hierarchy is adapted to the image content and artifacts of rigid resolution reduction are avoided. Two applications of these techniques are presented: connected component analysis of labeled images and segmentation of gray level images. In labeled images, every connected component is reduced to a separate root, with the adjacency relations among the components also extracted. In gray level images the output is a segmentation of the image into a small number of classes as well as the adjacency graph of the classes. > <s> BIB001 </s> A Review on Graph Based Segmentation <s> B. Irregular pyramids <s> Irregular pyramids are made of a stack of successively reduced graphs embedded in the plane. Each vertex of a reduced graph corresponds to a connected set of vertices in the level below. One connected set of vertices reduced into a single vertex at the above level is called the reduction window of this vertex. In the same way, a connected set of vertices in the base level graph reduced to a single vertex at a given level is called the receptive field of this vertex. The graphs used in the pyramid may be region adjacency graphs, dual graphs or combinatorial maps. This last type of pyramids are called Combinatorial Pyramids. Compared to usual graph data structures, combinatorial maps encode one graph and its dual within a same formalism and offer an explicit encoding of the orientation of edges around vertices. This paper describes the construction scheme of a Combinatorial Pyramid. We also provide a constructive definition of the notions of reduction windows and receptive fields within the Combinatorial Pyramid framework. <s> BIB002 </s> A Review on Graph Based Segmentation <s> B. Irregular pyramids <s> This paper presents a new segmentation technique for color images. It relies on building an irregular pyramid into a regular one, presenting only nodes associated to homogeneous color regions. Hence, the size of the irregular pyramid is bounded. Segmentation is performed by rearranging the set of links among pyramid nodes. Unlike other hierarchical methods based on relinking procedures, our algorithm does not operate in an iterative way and it preserves region connectivity. <s> BIB003 </s> A Review on Graph Based Segmentation <s> B. Irregular pyramids <s> In this paper, we present a segmentation method that provides perceptually relevant partitions without any a priori knowledge of the image content: first a local homogeneity analysis detects the image areas that have to be segmented. Then segmentation using a similarity criterion is locally performed. At last, segmented regions are grouped using Gestalt criteria. The whole method is presented in a hierarchical framework. <s> BIB004 </s> A Review on Graph Based Segmentation <s> B. Irregular pyramids <s> The main goal of this work is to compare pyramidal structures proposed to solve segmentation tasks. Segmentation algorithms based on regular and irregular pyramids are described, together with the data structures and decimation procedures which encode and manage the information in the pyramid. In order to compare the different segmentation algorithms, we have employed three types of quality measurements: the shift variance measure, the F function and the Q function. <s> BIB005
In opposite to the regular ones, spatial relationships and the reduction factors are not constants in irregular pyramids; hence, the size and the layout are not predictable. However, these types of pyramid solve the problems associated with the regular pyramids such as shift variance and inability to segment elongated objects. A few segmentation methods have been proposed based on irregular pyramids. Montanvert et al. BIB001 exploited a hierarchy of region adjacency graph, which performs stochastic decimation which in turn uses two binary state variables and a random variable, to achieve segmentation. This method yields different segmentation results depending on different outcomes of the random variable for the same input settings. To overcome this drawback, Jolion and Montanvert  proposed an adaptive pyramid in which the random variable is replaced by an interest variable in the decimation process. A localized pyramid was proposed by Huart et al. BIB004 to achieve segmentation. The bounded irregular pyramid was proposed by Marfil et al. BIB003 which combines features from regular and irregular pyramids. Brun and Kropatsch BIB002 combined a combinatorial pyramid and a union-findbased decimation algorithm to attain segmentation. With the aid of empirical methods, Marfil et al. BIB005 showed that irregular pyramids yield better results than regular pyramids in segmenting objects. Though irregular pyramids resolve the problems posed by the regular pyramids, they possess unpredictable structures which account for unbounded execution time for local operations within each level.